ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Представление булевой функции формулой логики высказыванийБулевы функции.
DEF. Булевой функцией f(, ,…, ) называется произвольная функция от п -переменных, отображающая множество {0;1} на это же самое множество {0;1}.
Таким образом, все аргументы булевой функции (Б.ф.) принимают значения из множества {0;1} и сама функция принимает значения из этого же множества. Всякую булеву функцию можно задать таблицей. Если f зависит от n переменных в таблице будет строк, в каждой из которых записан один из возможных наборов списка переменных. Пример: Если f(x), то n=1; 21=2 строки в таблице; Если f(x1,x2), то n=2; 22=4 строки в таблице; Если f(x1,x2,x3), то n=3; 23=8 строки в таблице и т.д.
Например, для случая n =2 булеву функцию можно задать таблицей:
Т.е. f(0,0)=f(1,1)=1 и f(0,1)=f(1,0)=0.
Если булева функция содержит n переменных, то различных наборов переменных будет 2n, а различных функций .
Пример: Если f(x), то n=1. Тогда = 4 различных булевых функций:
Очевидно, что каждой формуле логики высказываний можно поставить в соответствие булеву функцию, причем если формуле соответствует функция , а соответствует функция и при этом и тождественно равны ( ≡ ), то = . Докажем, что формулы алгебры логики дают все булевы функции. Для этого сформулируем: DEF. , (т.е. при = 1 под будем подразумевать формулу , а при = 0 – формулу ). При этом с каждым набором переменных < > будем ассоциировать элементарную конъюнкцию .
Лемма: Конъюнкция , ассоциированная с набором < > обращается в единицу на одном и только одном наборе переменных < , ,…, >, а именно на наборе < >.
Доказательство: В самом деле, элементарная конъюнкция принимает значение единицы на наборе < >, так как каждый её конъюнктивный член принимает значение единицы. Действительно, возможны два случая: 1) если =1, то ; 2) если = 0, то = 1, где l =1, 2, …, n. Таким образом, в каждом из этих случаев конъюнктивный член =1, но т.к. l- произвольное значение, тоэлементарная конъюнкция принимает значение единицы на наборе < >. С другой стороны, пусть некоторый набор < > не совпадает с набором < >, следовательно, при некотором номере l: ¹ . Здесь также возможны два случая: 1) =1, = 0; 2) =0, = 1. В первом случае: = = = = 0; во втором случае = = =0. Тогда в любом из этих случаев на наборе < > конъюнктивный член =0. А значит, элементарная конъюнкция принимает значение 0 на этом наборе. Лемма доказана.
Th: Пусть f(, ,…, ) – булева функция от k переменных, где k ³ 1. Если функция f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных < , ,…, > и находящаяся с совершенной дизъюнктивной нормальной форме, что формула F выражает собой функцию f(, ,…, ). Формула F определена однозначно с точностью до порядка дизъюнктивных членов.
Доказательство: Существование Пусть функция f(, ,…, ) задана с помощью таблицы. Выберем в таблице все строки, соответствующие наборам, на которых функция f принимает значение истины. Такие строки существуют, так как по условию функция не равна тождественно нулю. Для каждого такого набора построим ассоциированную с ним элементарную конъюнкцию и составим дизъюнкцию таких конъюнкций. Полученная таким образом формула и будет искомой. Для подтверждения этого необходимо доказать два утверждения: 1) f () = 1, то и F=1 на этом наборе; 2) f () = 0, то и F=0 на этом наборе. Итак: 1) Пусть на некотором наборе < > функция f равна 1, тогда в таблице соответствующая строка находится среди выбранных, а значит, элементарная конъюнкция находится среди дизъюнктивных членов. По лемме данная конъюнкция принимает значение 1, а, следовательно, вся формула F равна 1 на этом наборе. 2) Пусть на некотором наборе < > функция f равна 0. Любой дизъюнктивный член формулы F имеет вид , причем набор < >отличен от набора < >, так как строка, соответствующая набору < > не могла быть выбрана. По лемме каждая такая конъюнкция обращается в 0, а, следовательно, и вся формула F будет равна 0. Единственность Предположим противное: Пусть и - две формулы, находящиеся в совершенной дизъюнктивной нормальной форме и выражающие функцию f, причем ¹ . Тогда либо в формуле есть элементарная конъюнкция, не содержащаяся в , либо в формуле есть элементарная конъюнкция, не содержащаяся в . Рассмотрим первый случай: Если - элементарная конъюнкция, содержащаяся в и не содержащаяся в , то она будет ассоциирована с набором < >. С одной стороны, т.к. она содержится в , то на данном наборе она принимает значение 1, а следовательно, и вся формула принимает значение 1. С другой стороны, любая элементарная конъюнкция, содержащаяся в , будет ассоциирована с другим набором, значит, на этом наборе < > будет принимать значение равное 0, а следовательно, = 0. Тогда и будут выражать собой различные булевы функции. Таким образом, предположение о существовании двух формул неверно – единственность доказана.
Пример: Найти СДНФ.
F = ( & & )Ú( & & )Ú( & & ) Замечания к теореме: 1. Из доказанной теоремы следует утверждение: для любой не тождественно ложной формулы А существует равносильная ей формула F, находящаяся в совершенной дизъюнктивной нормальной форме. Это утверждение было ранее доказано (формулу F получали с помощью равносильных преобразований). Таким образом, данная теорема дает второй способ получения совершенной дизъюнктивной нормальной формы. 2. Из доказанной теоремы следует утверждение об единственности совершенной дизъюнктивной нормальной формы для любой формулы А: если формула А выражает булеву функцию f, то и любая совершенная дизъюнктивная нормальная форма должна выражать собой ту же функцию, поэтому все совершенные дизъюнктивные нормальные формы должны совпадать с точностью до порядка элементарных конъюнкций.
Аналогично совершенной дизъюнктивной нормальной форме можно рассмотреть совершенную конъюнктивную нормальную форму и для нее справедлива следующая теорема:
Th: Пусть f(, ,…, ) – булева функция от k переменных, где k ³ 1 и f не равна тождественно 1, тогда существует такая формула F, зависящая от списка переменных < , ,…, > и находящаяся с совершенной конъюнктивной нормальной форме, что формула F выражает собой функцию f(, ,…, ). Формула F определена однозначно с точностью до порядка своих конъюнктивных членов.
Доказывается аналогично теореме о совершенной дизъюнктивной нормальной форме.
Пример: Найти СКНФ.
F = (x1\/x2\/x3)&(x1\/x2\/x3)&(x1\/x2\/x3)&(x1\/x2\/x3)&(x1\/x2\/x3)
Рассмотри все булевы функции от двух переменных. Если n = 2,то = 16различных булевых функций:
Не нашли, что искали? Воспользуйтесь поиском:
|