Совершенные дизъюнктивная и конъюнктивная

Нормальные формы

Итак, любая формула A(x₁ , … , x_n) определяет таблицу истинности, в которой можно опустить столбцы с промежуточными вычислениями. При этом равносильным формулам A(x₁ , … , x_n) º B(x₁ , … , x_n) соответствуют одинаковые таблицы истинности (если предположить, что в первых n столбцах этих таблиц всевозможные наборы значений пропозициональных переменных x₁ , … , x_n (интерпретации) перечислены в одном и том же порядке). Возникает вопрос: каждая ли таблица рассматриваемого вида будет таблицей истинности некоторой формулы ?

Пример. Найти формулу со следующей таблицей истинности:

Если формула A(x₁ , x₂ , x₃ ) – искомая, то

A(x₁ , x₂ , x₃ ) = 1 Û

Û (x₁ = 0 Ù x₂ = 0 Ù x₃ = 1)Ú (x₁ = 0 Ù x₂ = 1 Ù x₃ = 1) Ú

Ú (x₁ = 1 Ù x₂ = 0 Ù x₃ = 1) Û

Û ( Ù Ù x₃ = 1) Ú ( Ù x₂ Ù x₃ = 1) Ú

Ú (x₁ Ù Ù = 1) Û

Û ( Ù Ù x₃ ) Ú ( Ù x₂ Ù x₃ ) Ú (x₁ Ù Ù ) = 1.

Таким образом, в качестве искомой формулы можно взять

A(x₁ , x₂ , x₃ ) = ( Ù Ù x₃ ) Ú ( Ù x₂ Ù x₃ ) Ú (x₁ Ù Ù ) .

Полученное в примере выражение для формулы A(x₁ , x₂ , x₃ ) устроено регулярно: оно является дизъюнкцией выражений вида y₁ Ù y₂ Ù y₃ , где каждое y_i является или переменной x_i или её отрицанием . Аналогичные построения можно применить и в общем случае, используя соответствующие общие обозначения, к описанию которых теперь и переходим.

Для пропозициональной переменной x и фиксированного значения e Î {0, 1} введём следующее обозначение x^e = . Выражение x^e можно считать булевой функцией переменного x, вычисляя её значение при x = d Î {0, 1} естественным образом: d ^e = .

Найденная в предыдущем примере формула в этих обозначениях может быть записана так: A(x₁ , x₂ , x₃ ) = (x₁⁰ Ù x₂⁰ Ù x₃¹) Ú (x₁⁰ Ù x₂¹ Ù x₃¹ ) Ú (x₁¹ Ù x₂⁰ Ù x₃⁰ ). Следует заметить, что наборы степеней при переменных x₁ , x₂ , x₃ , т.е.наборы (0; 0; 1), (0; 1; 1), (1; 0; 0), – это в точности те интерпретации из исходной таблицы, при которых в последнем её столбце стоит значение 1:

A(x₁ , x₂ , x₃ ) = .

Лемма (о значениях выражения x^e ) .(1) x^e = 1 Û x = e.

(2) .

(3) = 1 Û (x₁ = e₁) Ù … Ù (x_n = e_n) .

(4) .

Доказательство.Следующая таблица показывает, что x^e = 1 тогда и только тогда, когда x = e , а также, что :

e	формула xe	x	значение xe		формула	x	значение	значение
0		0	1	1	x	0	0	0
1	0	1	1	1
1	x	0	0	0		0	1	1
1	1	1	0	0

Остальные утверждения отсюда следуют:

( = 1) Û ( = 1) Ù … Ù ( = 1) Û (x₁ = e₁ Ù … Ù x_n = e_n), .

Лемма доказана.

Элементарной конъюнкцией (соответственно дизъюнкцией) от n пропозициональных переменных x₁ , … , x_n назовём формулу вида (соответственно ), где k £ n, 1 £ i₁ < … < i_k £ n, Î {0, 1}. Менее формально, элементарная конъюнкция (дизъюнкция) – это выражение y₁ Ù … Ù y_k (соответственно y₁ Ú … Ú y_k ), где каждое y_s является либо пропозициональной переменной, либо её отрицанием, причём переменные, участвующие в этом выражении упорядочены по возрастанию своих номеров. Если в элементарной конъюнкции (соответственно дизъюнкции) участвуют все переменные, т.е. k = n, то такая элементарная конъюнкция (соответственно дизъюнкция) называется совершенной элементарной конъюнкцией (соответственно дизъюнкцией). Любая дизъюнкция различных элементарных конъюнкций (соответственно конъюнкция различных элементарных дизъюнкций) называется дизъюнктивной нормальной формой (соответственно конъюнктивной нормальной формой). Любая дизъюнкция различных совершенных элементарных конъюнкций (соответственно конъюнкция различных совершенных элементарных дизъюнкций) называется совершенной дизъюнктивной нормальной формой, или кратко СДНФ (соответственно совершенной конъюнктивной нормальной формой, или кратко СКНФ). Таким образом, СДНФ (соответственно СКНФ) может быть записана так: (соответственно ).

Примеры: 1. конъюнкция x Ù не является элементарной конъюнкцией, т.к. одна переменная в ней участвует дважды – вначале без отрицания, а потом с отрицанием.

2. x Ù – совершенная элементарная конъюнкция от двух переменных x и y, но она не является совершенной элементарной конъюнкцией от трёх переменных x, y, z (т.к. переменная z не участвует в этом выражении). Эта формула будет совершенной дизъюнктивной нормальной формой от переменных x, y, но она не будет совершенной, если рассматривать её от трёх переменных.

3. (x₁ Ú x₂ Ú x₃) Ù ( ) – совершенная конъюнктивная нормальная форма от переменных x₁ , x₂ , x₃ .

4.(x₁ Ú x₂ Ú x₃) Ù (x₁ Ú x₂ Ú x₃) Ù ( ) – не является совершенной конъюнктивной нормальной формой от переменных x₁ , x₂ , x₃ , т.к. содержит две одинаковые элементарные дизъюнкции.

5. Любая дизъюнктивная нормальная форма принимает значение 1 хотя бы на одном наборе пропозициональных переменных. Докажем это для совершенной дизъюнктивной нормальной формы – в общем случае рассуждения аналогичны. Действительно, формула истинна тогда и только тогда, когда истинна хотя бы одна её элементарная конъюнкция . Ввиду леммы она истинна при x₁ = e₁ , … , x_n = e_n , что и требовалось доказать.

6. Как следует из предыдущего примера, для противоречий не существует СДНФ. Однако легко записать формулу от n переменных, равносильную противоречию: например, x₁ Ù .

7. Любая конъюнктивная нормальная форма принимает значение 0 хотя бы на одном наборе пропозициональных переменных. Доказательство аналогично предыдущему.

8. Как следует из предыдущего примера, для законов логики не существует СКНФ. Однако, легко записать формулу от n переменных, равносильную закону логики: например, x₁ Ú .

Возвращаемся к общей задаче построения формулы с заданной таблицей истинности.

Теорема (о СДНФ и СКНФ).(1) Для любой таблицы, последний столбец которой состоит не из одних нулей, существует СДНФ с этой таблицей истинности.

(2) Эта СДНФ единственна с точностью до порядка совершенных элементарных конъюнкций.

(3) В частности, для любой формулы A(x₁ , … , x_n ), не являющейся противоречием, существует единственная (с точностью до перестановки элементарных конъюнкций) равносильная ей СДНФ.

(1¢) Для любой таблицы, последний столбец которой состоит не из одних единиц, существует СКНФ с этой таблицей истинности.

(2¢) Эта СКНФ единственна с точностью до порядка совершенных элементарных дизъюнкций.

(3¢) В частности, для любой формулы A(x₁ , … , x_n ), не являющейся законом логики, существует единственная (с точностью до перестановки элементарных дизъюнкций) равносильная ей СКНФ.

Доказательство. (1) Вначале докажем существование СДНФ для таблицы слева с неизвестной формулой A(x₁ , … , x_n ) 0. Для этого по данной таблицеобразуем следующее выражение Д(x₁ , … , x_n ) = . Это – СДНФ, причём

(Д(e₁ , … , e_n ) = 1) Û (найдётся такая интерпретация (d₁ ; … ; d_n ), что

A(d₁ , … , d_n) = 1, и = 1) Û (найдётся такая интерпретация

(d₁ ; … ; d_n ), что A(d₁ , … , d_n) = 1, и (d₁ = e₁) Ù … Ù (d_n = e_n )) Û

Û (A(e₁ , … , e_n) = 1), что и требовалось.

(2) Докажем теперь единственность (с точностью до перестановки элементарных конъюнкций) СДНФ с заданной таблицей истинности. Пусть нашлись две такие СДНФ Д₁(x₁ , … , x_n ) и Д₂(x₁ , … , x_n ), что Д₁(x₁ , … , x_n ) º Д₂(x₁ , … , x_n ). Будет показано, что любая элементарная конъюнкция формулы Д₁(x₁ , … , x_n ) участвует и в Д₂(x₁ , … , x_n ), и наоборот, любая элементарная конъюнкция формулы Д₂(x₁ , … , x_n ) участвует в Д₁(x₁ , … , x_n ). Таким образом, будет показано, что эти СДНФ состоят из одного и того же набора элементарных конъюнкций.

Пусть элементарная конъюнкция участвует в Д₁(x₁ , … , x_n ). То­гда эта конъюнкция принимает значение 1 при x₁ = e₁ , … , x_n = e_n , а значит, Д₁(e₁ , … , e_n ) = 1. Ввиду Д₁(x₁ , … , x_n ) º Д₂(x₁ , … , x_n ) имеем Д₂(e₁ , … , e_n ) = 1. Значит, найдётся такая элементарная конъюнкция в Д₂(x₁ , … , x_n ), что = 1. Однако, ( = 1) Û (d₁ = e₁ Ù … Ù d_n = e_n ), т.е. элементарная конъюнкция участвует и в формуле Д₂(x₁ , … , x_n ).

Аналогично доказывается, что любая элементарная конъюнкция формулы Д₂(x₁ , … , x_n ) участвует и в формуле Д₁(x₁ , … , x_n ), а значит, эти СДНФ состоят из одних и тех же совершенных элементарных конъюнкций (с точностью до их перестановки).

(3) следует из (1) и (2): достаточно по заданной формуле A(x₁ , … , x_n ) 0 построитьтаблицу истинности, и найти единственную СДНФ Д(x₁ , … , x_n ) с этой таблицей истинности. Тогда A(x₁ , … , x_n ) º Д(x₁ , … , x_n ).

(1¢) выведем это из (1). По условию, искомая формула A(x₁ , … , x_n ) не тождественно истинна,так что (x₁ , … , x_n ) 0. По доказанному в (1), найдётся СДНФ Д(x₁ , … , x_n ) = º (x₁ , … , x_n). Значит,

A(x₁ , … , x_n ) º (x₁ , … , x_n ) º º {де Морган} º

º

– искомая СКНФ.

(2¢) Если найдены две равносильные СКНФ К₁(x₁ , … , x_n ) º К₂(x₁ , … , x_n ), то у формулы (x₁ , … , x_n ) существовали бы две СДНФ (x₁ , … , x_n ) и (x₁ , … , x_n ). По доказанному в (1), (x₁ , … , x_n ) и (x₁ , … , x_n ) отличаются только порядком элементарных конъюнкций, а значит, К₁(x₁ , … , x_n ) и К₂(x₁ , … , x_n ) отличаются только порядком элементарных дизъюнкций, что и требовалось.

(3¢) выводится из (1¢) и (2¢) аналогично тому, как (3) выведено из (1) и (2).

Теорема доказана.

На практике СКНФ можно получать, как следует из приведённых при доказательстве теоремы вычислений, без привлечения отрицания формулы. По заданной таблице истинности формулы для каждого набора значений (e₁ ; … ; e_n ) со свойством A(e₁ , … , e_n) = 0 построим элементарную дизъюнкцию и конъюнкцию всех таких дизъюнкций: , которая и будет СКНФ для исходной не тождественно истинной формулы A(x₁ , … , x_n ).

Примеры: 1. Построить СКНФ для формулы (x ® y) Ù z Ú (y ® x) Ù .

x	y	z	x ® y	((x ® y) Ù z	y ® x		((y ® x) Ù	A
0	0	0	1	0	1	1	1	1
0	0	1	1	1	1	0	0	1
0	1	0	1	0	0	1	0	0
0	1	1	1	1	0	0	0	1
1	0	0	0	0	1	1	1	1
1	0	1	0	0	1	0	0	0
1	1	0	1	0	1	1	1	1
1	1	1	1	1	1	0	0	1

Вначале строим таблицу истинности формулы. Далее, выбираем нулевые значения формулы с интерпретациями (0; 1; 0) и (1; 0; 1) соответственно и строим по этим наборам элементарные дизъюнкции

.

Таким образом, СКНФ такова: К(x, y, z) = .

2. Предыдущую задачу можно решить и без построения таблицы истинности, воспользовавшись основными равносильностями:

((x ® y) Ù z) Ú ((y ® x) Ù ) º (( Ú y) Ù z) Ú (( Ú x) Ù ) º {дистрибутивность} º (( Ú y) Ú (( Ú x) Ù ))) Ù (z Ú (( Ú x) Ù ))) º

º (( Ú y)Ú ( Ú x)) Ù (( Ú y) Ú ) Ù (z Ú ( Ú x)) Ù (z Ú ) º

º { Ú yÚ Ú x º 1, z Ú º 1} º ( Ú y Ú ) Ù (x Ú Ú z) – СКНФ.

3. Построим СДНФ для формулы примера 1.

Выбираем все единичные значения формулы, которым отвечают интерпретации (0; 0; 0), (1; 0; 0), (1; 1; 0), (0; 0; 1), (0; 1; 1) и (1; 1; 1) соответственно. Строим по этим наборам элементарные конъюнкции x⁰ Ù y⁰ Ù z⁰ = , x¹ Ù y⁰ Ù z⁰ = , x¹ Ù y¹ Ù z⁰ = , x⁰ Ù y⁰ Ù z¹ = , x⁰ Ù y¹ Ù z¹ = и x¹ Ù y¹ Ù z¹ = x Ù y Ù z . Таким образом, СДНФ такова:

.

4.Предыдущую задачу можно решить и без построения таблицы истинности, воспользовавшись основными равносильностями:

((x ® y) Ù z)Ú ((y ® x) Ù ) º (( Ú y) Ù z)Ú (( Ú x) Ù ) º {дистрибутивность} º ( Ù z)Ú (y Ù z)Ú ( Ù )Ú (x Ù ) º {склейка} º

º ( Ù y Ù z)Ú ( Ù Ù z)Ú (x Ù y Ù z)Ú ( Ù y Ù z)Ú (x Ù Ù )Ú

Ú ( Ù Ù ) Ú (x Ù y Ù )Ú (x Ù Ù ) º {идемпотентность} º

º ( Ù y Ù z) Ú ( Ù Ù z) Ú (x Ù y Ù z)Ú ( Ù Ù )Ú (x Ù y Ù )Ú (x Ù Ù ).

Упражнение.Постройте СДНФ и СКНФ для следующих формул:

а) a Ú b ® Ù , б) a « , в) , г) a ® b Ù c « c Ù , д) Ú a Ù bÚ , е) (a « b) Ù c ® c Ú .

Зададимся следующим вопросом: сколько можно выписать подряд попарно неравносильных формул исчисления высказываний от n пропозициональных переменных ? С одной стороны, каждая формула имеет таблицу истинности. С другой стороны, в этом параграфе было доказано, что для каждой таблицы значений существует реализующая её формула исчисления высказываний. Поэтому максимальное количество попарно неравносильных формул равно количеству различных таблиц истинности (при фиксированном порядке перечисления наборов значений переменных в первых n столбцах этих таблиц).

Сколько же существует таблиц истинности ? Если зафиксировать один и тот же порядок перечисления наборов значений переменных в первых n столбцах этих таблиц, то каждая таблица полностью определяется своим последним столбцом, который является набором из нулей и единиц длины 2ⁿ. Всего существует таких наборов, т.е. всего существует таблиц истинности, а значит, и попарно неравносильных формул от n переменных.

Поскольку каждая не тождественно ложная формула имеет однозначно определённую СДНФ, общее количество СДНФ (с точностью до перестановки их совершенных элементарных конъюнкций) равно – 1. Столько же существует и различных СКНФ (с точностью до перестановки их совершенных элементарных дизъюнкций). Значит доказана

Теорема (о количестве неравносильных формул от n переменных).(1) Максимальное количество попарно неравносильных формул исчисления высказываний от n пропозициональных переменных равно .

(2) Существует ровно – 1 неравносильных между собой СДНФ и столько же неравносильных между собой СКНФ.

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

После того как каждой формуле A(x₁ , … , x_n) при любом наборе x₁ = e₁ , … … , x_n = e_n (e_i Î {0, 1}, 1 £ i £ n) значений её пропозициональных переменных приписано единственным образом некоторое значение A(e₁ , … , e_n ) Î {0, 1}, такую формулу можно рассматривать как функцию A : ® B от n переменных x₁ , … , x_n Î B = {0, 1} со значениями во множестве B. Любая всюду определённая функция f : ® B называется булевой. Таким образом, каждая формула исчисления высказываний является булевой функцией. При этом две формулы равносильны тогда и только тогда, когда совпадают определеяемые ими булевы функции. С другой стороны, произвольная булева функция

f : ® B может быть задана с помощью таблицы,являющейся (в силу § 5) таблицей истинности некоторой формулы исчисления высказываний. Таким образом, доказана

Теорема (о реализации булевых функций формулами).Любая булева функция реализуется формулой исчисления высказываний.

Эту теорему можно было доказать иначе: подсчитав количество булевых функций от заданного числа переменных и сравнив его с максимальным количеством попарно не равносильных формул исчисления высказываний от тех же переменных. Булевых функций от n переменных x₁ , … , x_n будет столько же, сколько таблиц вышеприведённого вида, задающих эти функции, т.е. столько же, сколько таблиц истинности от тех же переменных, – а именно – . Это совпадает с максимальным количеством попарно неравносильных формул исчисления высказываний от переменных x₁ , … , x_n .Учитывая, что множество формул содержится во множестве функций, причём две формулы равносильны тогда и только тогда, когда совпадают определеяемые ими булевы функции, получим, что булевых функций столько же, каково максимальное число попарно неравносильных формул исчисления высказываний. Значит, любая булева функция реализуется формулой исчисления высказываний.

Можно перечислить все булевы функции от заданного числа n аргументов. Например, следующие таблицы задают все = 16 булевых функций от n = 2 аргументов:

x	y	f1 = 0		x	y	f2 = x Ù y		x	y	f3 = Ù y		x	y	f4 = y
0	0	0		0	0	0		0	0	0		0	0	0
1	0	0		1	0	0		1	0	0		1	0	0
0	1	0		0	1	0		0	1	1		0	1	1
1	1	0		1	1	1		1	1	0		1	1	1

x	y	f5 = x Ù		x	y	f6 = x		x	y	f7 = x Å y		x	y	f8 = x Ú y
0	0	0		0	0	0		0	0	0		0	0	0
1	0	1		1	0	1		1	0	1		1	0	1
0	1	0		0	1	0		0	1	1		0	1	1
1	1	0		1	1	1		1	1	0		1	1	1

x	y	f9 = Ù		x	y	f10 = x « y		x	y	f11 =		x	y	f12 = Ú y
0	0	1		0	0	1		0	0	1		0	0	1
1	0	0		1	0	0		1	0	0		1	0	0
0	1	0		0	1	0		0	1	1		0	1	1
1	1	0		1	1	1		1	1	0		1	1	1

x	y	f13 =		x	y	f14 = x Ú		x	y	f15 = Ú		x	y	f16 = 1
0	0	1		0	0	1		0	0	1		0	0	1
1	0	1		1	0	1		1	0	1		1	0	1
0	1	0		0	1	0		0	1	1		0	1	1
1	1	0		1	1	1		1	1	0		1	1	1

Подписанные обозначения функций не единственны: их можно заменить на любые равносильные формулы. Здесь x Å y = (x Ù ) Ú ( Ù y) º – операция “исключающего или”, называемая также сложением по модулю 2 (т.к. с точки зрения программиста x Å y = (x+y) mod 2). Специальные названия есть и у других важных функций. Например, функция f₁₅ , подписанная Ú ,носит название штрих Шеффера и обозначается x | y, а функция f₉ ( Ù ) – стрелка Пирса и обозначается x ¯ y.

Чтобы уяснить связь между булевыми функциями от разного количества аргументов докажем следующую лемму:

Лемма (о разложении булевой функции по k переменным).Пусть f : Bⁿ ® B – булева функция от n аргументов. Тогда для любого k от 1 до n верна формула:

,

где дизъюнкция берётся по всем интерпретациям (e₁ ; … ; e_k) Î B^k.

Доказательство. Рассмотрим формулу , где дизъюнкция берётся по всем интерпретациям (e₁ ; … ; e_k) Î B^k , и проверим, что она тождественно истинна. Действительно, пусть e = (e₁ ; … ; e_k) – произвольная интерпретация. Тогда совершенная элементарная конъюнкция от k переменных участвует в Ф(x₁ , … , x_k), и по лемме о значениях выражения x^e из прошлого параграфа имеем , и значит, будучи дизъюнкцией, Ф(e₁ , … , e_k) = 1. Таким образом, Ф(x₁ , … , x_k) º 1.

Теперь сразу получаем

.

Остаётся доказать, что . Для этого вычислим значения левой и правой частей при произвольной интерпретации (d₁ ; … ; d_n) Î Bⁿ : =

.

Аналогично получим

=

.

Таким образом, , а значит, .

Лемма доказана.

Эта лемма не только позволяет выражать булевы функции от n переменных через булевы функции от меньшего числа аргументов, но и открывает другой путь к получению СДНФ :

Следствие (о СДНФ). Если f(x₁ , … , x_n) – не тождественно нулевая булева функция, то .

Доказательство: Из предыдущей теоремы при k = n получаем разложение:

.

Если f(e₁ , … , e_n) = 0, то конъюнкцию º 0 в этой дизъюнктивной форме можно опустить. Таким образом, в правой части останутся только конъюнкции, в которых f(e₁ , … , e_n) = 1, т.е. º º , что и требовалось.

Следствие доказано.

Теорема о СДНФ и СКНФ показывает, что любую булеву функцию можно записать, используя только три логических связки: – отрицание, Ù – конъюнкцию и Ú – дизъюнкцию. На самом деле, используя равносильности (A Ù B) º º , (A Ú B) º , можно обойтись и двумя связками – либо отрицанием и конъюнкцией, либо отрицанием и дизъюнкцией.

Примеры: 1.Записать формулу x Ú Ú z, используя только отрицание и конъюнкцию.

x Ú Ú z º (x Ú )Ú z º Ú z º = .

2.Записать Ù Ù , используя только отрицание и дизъюнкцию.

Имеем Ù Ù º = .

3. Функцию f₁(x, y) = 0 невозможно выразить, используя только конъюнкцию и дизъюнкцию. Действительно, любая формула A(x₁ , … , x_n ), выразимая через конъюнкцию и дизъюнкцию, принимает значение 1 при x₁ = … = x_n = 1.

Таким образом, предыдущие примеры показывают, что через некоторые наборы функций можно выразить любую булеву функцию, а через некоторые – нельзя. Это приводит к следующему определению: множество булевых функций {f₁ , … , f_k} называется полным, если любую булеву функцию можно выразить через f₁ , … , f_k , используя операцию подстановки значений одних ф