§6.Основные равносильности булевых формул.

1. aÚbºbÚa 1¢. aÙbºbÙa

2. aÚ(bÚc)º(aÚb)Úc 2¢. aÙ(bÙc)º(aÙb)Ùc

3. aÚ(bÙc)º(aÚb)Ù(aÚc) 3¢. aÙ(bÚc)º(aÙb)Ú(aÙc)

4.aÚ(aÙb)ºa 4¢. aÙ(aÚb)ºa

5. Ú º`aÙ`b 5¢. Ù º`aÚ`b

6. aÚaºa 6¢. aÙaºa

7. aÚ`aº1 7¢. aÙ`aº0

8. aÚ1º1 8¢. aÙ0º0

9. aÚ0ºa 9¢. aÙ1ºa

10. =a

Все эти равносильности могут быть доказаны с помощью таблицы истинности.

Замечания:

1. Нетрудно убедиться в том, что данные равносильности аналогичны таблице равенства множеств, в которой пересечение заменено конъюнкцией, а объединение - дизъюнкцией, пустое множество - тождественно ложным, а универсальное множество - тождественно истинным высказыванием. Сами эти равносильности называются так же, как и соответствующие равенства. Так 5 и 5¢ называются законами де Моргана, а 10 - закон снятия двойного отрицания.

2. Можно заметить, что правый столбец получается из левого заменой конъюнкции на дизъюнкцию, дизъюнкции на конъюнкцию, 1 заменяется на 0, а 0 на 1.

Вернёмся к теореме. Не проводя доказательства, покажем на примере, как найти равносильную булевую формулу.

Пример. F=(a®(bÚс))®aº(`aÚ(bÚс))®aºÚÚ Úaº ÙÚ Úaº(aÙ(`bÙ`c)Úaºa`b`cÚa

Приведённой булевой формулой называется булева формула, в которой символ отрицания относится только к символам простых компонент. Так, формула ÚÚ Úa является булевой, но не приведённой, а равносильная ей a`b`cÚa - приведённая.

Следствие. Всякая формула логики высказываний равносильна приведённой булевой формуле.

Это следует из правил подстановки, законов до Моргана и снятия двойного отрицания.

§7.Дизъюнктивные и конъюнктивные нормальные формулы (днф и кнф).

Назовём элементарной дизъюнкцией (суммой) дизъюнкцию простых компонент и их отрицаний. Аналогично, элементарной конъюнкцией (произведением) назовём конъюнкцию простых компонент и их отрицаний. Дизъюнктивной нормальной формулой (формой) назовём дизъюнкцию элементарных конъюнкций (сумму элементарных произведений) и обозначим ДНФ. И аналогично КНФ - это конъюнкция элементарных дизъюнкций (произведение элементарных сумм).

Теорема. Для всякой формулы логики высказываний существуют равносильные ей ДНФ и КНФ.

Это следует из законов дистрибутивности и из предыдущих теорем.

Пример. Для формулы F=Ù®Ú ®ae построить равносильные ей ДНФ и КНФ.

Сначала избавимся от импликаций FºÙÚÚ Úaeº((Ù )Ú`cÚ`d)Úaeº(`aÚ`b)Ú`cÚ`dÚaeº`aÚ`bÚ`cÚ`dÚae - это и есть ДНФ. Теперь применив правило 3, получим Fº(`aÚ`bÚ`cÚ`dÚa)Ù(`aÚ`bÚ`cÚ`dÚe)º`aÚ`bÚ`cÚ`de - это одновременно и ДНФ и КНФ. Здесь `aÚ`bÚ`cÚ`dÚaº1

Замечание. Данный пример показывает, что равносильные ДНФ и КНФ не единственны. Однако, существуют единственные (с точностью до порядка) ДНФ и КНФ, называемыми совершенными ДНФ и КНФ (СДНФ и СКНФ).

§8.Представление булевой функции сднф и скнф (проблема разрешимости).

Пусть булева функция f(x₁,…,x_n) задана своей таблицей, и пусто f не является тождественным нулём. Каждому набору значений переменных, для которого f равна 1 составим элементарную конъюнкцию по следующему правилу: если в наборе x_i=1, то в конъюнкцию войдёт x_i, а если x_i=0, то _i. Дизъюнкция всех таких конъюнкций и будет ДНФ, равносильной данной функции. Она называется совершенной ДНФ (СДНФ). Число слагаемых в такой сумме равно числу наборов, для которых f равно 1, а сами слагаемые определяются единственным образом по этим наборам.

Аналогично строится совершенная КНФ. Если f не является тождественной 1, то каждому набору, для которого f равна 0, сопоставляется элементарная дизъюнкция: если x_i=0, то входит x_i, а если x_i=1, то входит _i. Конъюнкция всех таких дизъюнкций равносильна f.

Пример 1. Построить СДНФ и СКНФ, равносильные функции

x	y	f
0	0	1
0	1	1
1	0	0
1	1	1

fºÚÚºÚ

Пример 2. Построить СДНФ и СКНФ для функции, заданной столбцом своих значений (11001110).

Мы уже говорили, что для удобства наборы располагаются в порядке, соответствующем двоичной записи порядкового номера. Так, данная функция f принимает значение 1 для наборов с номерами 0,1,4,5,6, т.е. для наборов: 000, 001,100,101,110, а потому

fºÚÚÚÚ

Поскольку f равна 0 для наборов 010,011 и 111, то fºЪЪЪЪЪЪ

Замечание 1. Если функция f задаётся 2^k своими значениями, то совершенные нормальные формулы для f содержит k переменных. Если число существенных переменных меньше k, то для f можно построить совершенные нормальные формы с меньшим числом переменных.

Замечание 2. Если СДНФ функции f содержит r слагаемых, то СКНФ содержит 2^k - r сомножителей, где k - число переменных функции f.

Дадим теперь аналитическое определение СДНФ и СКНФ.

Определение. Совершенной дизъюнктивной нормальной формулой (СДНФ) от переменных x₁, x₂,…, x_k называется ДНФ, обладающая следующими свойствами:

1. Нет одинаковых конъюнкций.

2. Каждая конъюнкция для каждого переменного x_i содержит либо x_i, либо _i, но не может содержать их одновременно.

3. Все сомножители в каждой конъюнкции различны.

Аналогично определяется совершенная конъюктивная нормальная формула (СКНФ) заменой слова "конъюнкция" на слово "дизъюнкция".