Представление булевой функции формулой логики высказываний

Булевы функции.

DEF. Булевой функцией f( , ,…, ) называется произвольная функция от п-переменных, отображающая множество {0;1} на это же самое множество {0;1}.

Таким образом, все аргументы булевой функции (Б.ф.) принимают значения из множества {0;1} и сама функция принимает значения из этого же множества.

Всякую булеву функцию можно задать таблицей. Если f зависит от n переменных в таблице будет строк, в каждой из которых записан один из возможных наборов списка переменных.

Пример: Если f(x) , то n=1; 2¹=2 строки в таблице;

Если f(x₁,x₂) , то n=2; 2²=4 строки в таблице;

Если f(x₁,x₂,x₃) , то n=3; 2³=8 строки в таблице и т.д.

Например, для случая n=2 булеву функцию можно задать таблицей:

Т.е. f(0,0)=f(1,1)=1 и f(0,1)=f(1,0)=0.

Если булева функция содержит n переменных, то различных наборов переменных будет 2ⁿ, а различных функций .

Пример: Если f(x), то n=1. Тогда = 4 различных булевых функций:

x	f1	f2	f3	f4
0	0	1	0	1
1	0	0	1	1
Б.ф.	0			1

Очевидно, что каждой формуле логики высказываний можно поставить в соответствие булеву функцию, причем если формуле соответствует функция , а соответствует функция и при этом и тождественно равны ( ≡ ), то = .

Докажем, что формулы алгебры логики дают все булевы функции. Для этого сформулируем:

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	1	1	1	×
1	1	0	0
1	0	1	0
1	0	0	1	×
0	1	1	0
0	1	0	1	×
0	0	1	0
0	0	0	0

F = ( & & )Ú( & & )Ú( & & )

Замечания к теореме:

1. Из доказанной теоремы следует утверждение: для любой не тождественно ложной формулы А существует равносильная ей формула F, находящаяся в совершенной дизъюнктивной нормальной форме. Это утверждение было ранее доказано (формулу F получали с помощью равносильных преобразований). Таким образом, данная теорема дает второй способ получения совершенной дизъюнктивной нормальной формы.

2. Из доказанной теоремы следует утверждение об единственности совершенной дизъюнктивной нормальной формы для любой формулы А: если формула А выражает булеву функцию f, то и любая совершенная дизъюнктивная нормальная форма должна выражать собой ту же функцию, поэтому все совершенные дизъюнктивные нормальные формы должны совпадать с точностью до порядка элементарных конъюнкций.

Аналогично совершенной дизъюнктивной нормальной форме можно рассмотреть совершенную конъюнктивную нормальную форму и для нее справедлива следующая теорема:

Th: Пусть f( , ,…, ) – булева функция от k переменных, где k ³ 1 и f не равна тождественно 1, тогда существует такая формула F, зависящая от списка переменных < , ,…, > и находящаяся с совершенной конъюнктивной нормальной форме, что формула F выражает собой функцию f( , ,…, ). Формула F определена однозначно с точностью до порядка своих конъюнктивных членов.

Доказывается аналогично теореме о совершенной дизъюнктивной нормальной форме.

Пример: Найти СКНФ.

			f
1	1	1	1
1	1	0	0	×
1	0	1	0	×
1	0	0	1
0	1	1	0	×
0	1	0	1
0	0	1	0	×
0	0	0	0	×

F = (x₁\/x₂\/x₃)&( x₁\/x₂\/x₃)&( x₁\/x₂\/x₃)&( x₁\/x₂\/x₃)&( x₁\/x₂\/x₃)

Рассмотри все булевы функции от двух переменных.

Если n = 2,то = 16различных булевых функций:

		f1	f2	f3	f4	f5	f6	f7	f8	f9
Булева функция		&	&	&	&			Û

		f10	f11	f12	f13	f14	f15	f16
Булева функция			Ú	Ú	Ú	Ú