4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы

Любая булева функция может иметь много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, в которой в каждый конъюнктивный одночлен каждая переменная х_i, из набора входит ровно один раз, причем входит либо сама х_i, либо ее отрицание .

Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, обладающая следующими свойствами:

1. ДНФ не содержит двух одинаковых конъюнкций,

2. ни одна конъюнкция не содержит одновременно двух одинаковых переменных,

3. ни одна конъюнкция не содержит одновременно некоторую переменную и ее отрицание,

4. каждая конъюнкция содержит либо переменную х_i либо ее отрицание для всех переменных, входящих в формулу.

Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, в которой в каждый дизъюнктивный одночлен каждая переменная х_i, из набора входит ровно один раз, причем входит либо сама х_i, либо ее отрицание .

Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам:

1. КНФ не содержит двух одинаковых дизъюнкций,

2. ни одна из дизъюнкций не содержит одновременно двух одинаковых переменных,

3. ни одна из дизъюнкций не содержит одновременно некоторую переменную и ее отрицание,

4. каждая дизъюнкция СКНФ содержит либо переменную х_i, либо ее отрицание для всех переменных, входящих в формулу.

Для построения СКДФ функции выписываем наборы такие, что f(x) = 1, составляется конъюнкция , а затем все эти конъюнкции соединяем знаком дизъюнкции.

Для построения СКНФ функции выписываем наборы = ( , ,..., ) такие, что f ( )= 0. Для такого набора составляется дизъюнкция

V V…V ,

а затем все такие дизъюнкции соединяют знаком конъюнкции.

Приведенные формулы позволяют сформулировать следующие утверждения:

1. Каждая булева функция от «переменных, отличная от константы 0, имеет единственную СДНФ.

2. Каждая булева функция от п переменных, отличная от константы 1, имеет единственную СКНФ.

Эти утверждения называются теоремой о функциональной полноте.

Задачи по теме «Булевы функции.»

Задача 1. Составьте таблицу истинности булевой функции трех переменных и найдите ее двоичный набор.

Решение. Для вычисления значений функции следует определить порядок выполнения операций. Это можно сделать многими способами. Пусть, например, порядок выполнения операций будет следующим:

, , , , .

Последовательно составляются таблицы истинности всех указанных функций.

Таблица 24.

x1	x2	хз				f1	f2	f3	f4	f5
0	0	0	1	1	1	0	1	1	1	1
0	0	1	1	1	0	0	1	1	1	1
0	1	0	1	0	1	1	0	1	1	1
0	1	1	1	0	0	1	0	1	1	1
1	0	0	0	1	1	1	0	1	1	1
1	0	1	0	1	0	1	0	1	1	1
1	1	0	0	0	1	0	0	1	1	1
1	1	1	0	0	0	0	0	1	1	1

Лексикографическое упорядочение наборов в таблице истинности булевой функции позволяет задать функцию двоичным набором длины 2ⁿ, который будем обозначать буквой F. Двоичный набор данной функции F = 11111111. Отметим, что двоичный набор определяет булеву функцию в том и только в том случае, когда его длина есть степень двойки, а соответствующий показатель степени определяет число переменных данной функции.

Задача 2. Докажите тождественную истинность формулы .

Решение. Необходимо показать, что двоичный набор данной формулы F = 1111.

Составим таблицу истинности:

Таблица 25.

х	у		х→у	→(х→у)
0	0	1	1	1
0	1	1	1	1
1	0	0	0	1
1	1	0	1	1

Задача 3. Докажите эквивалентность функций: и .

Решение. Для доказательства необходимо построить таблицы истинности этих функций, и если их двоичные наборы совпадут, то эквивалентность будет доказана.

Таблица 26.

х	у	z	x v z	у v z	х л (х v z)	х л (х v г) л (у v z)
0	0	0	0	0	0	0
0	0	1	1	1	0	0
0	1	0	0	1	0	0
0	1	1	1	1	0	0
1	0	0	1	0	0	0
1	0	1	1	1	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

Таблица 27.

х	у	z	х л у	x v z	(х л y) v (у л z)
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	0	0
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	0	1	1
1	1	0	1	0	1
1	1	1	1	1	1

Получаем F₁ = 00000111 и F₂ = 00000111. Значит, функции эквивалентны.

Задача 4. Используя СДНФ, найдите булеву функцию, принимающую значение 1 на следующих наборах переменных, и только на них: f(0,1,0) = f (1,0,1) = f (1,1,1) = 1.

Решение. Алгоритм построения СДНФ.

1. Наборам 010; 101; 111 соответствуют конъюнкции: л л ; л л ; л л . Напомним, что для каждого набора из нулей и единиц τ₁, τ₂, τ₃ выписываем конъюнкцию л л , причем, если τ₁= 1, то соответствующая переменная х_i входит в конъюнкцию без отрицания.

2. Составим дизъюнкцию полученных конъюнкций, т. е. составляем СДНФ функции:

Задача 5. Составьте СКНФ функции .

Решение.

Таблица 28.

x1	х2	x1 х2
0	0	0
0	1	1
1	0	1
1	1	0

1. Выпишем f(0,0) = 0; f (1,1) = 0, булева функция принимает значение 0 на наборах (0; 0) и (1; 1).

2. Составим дизъюнкции, соответствующие этим наборам: л и л (если = 0, то переменная входит в дизъюнкцию без отрицания, если = 1, то переменная в дизъюнкции берется с отрицанием).

3. Составим конъюнкцию полученных дизъюнкций, т. е. составляем СКНФ функции f(х₁, х₂,) = ( v )л( л ).

Задача 6. Найдите СДНФ и СКНФ функции , заданной следующей таблицей истинности:

Таблица 29.

0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Решение. По теореме о функциональной полноте СДНФ имеет вид:

;

СКНФ имеет вид:

.

Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким. Для нахождения СДНФ данную формулу приводим сначала к ДНФ, а затем преобразовываем ее конъюнкции с помощью следующих действий:

а) если в конъюнкцию входит некоторая переменная со своим отрицанием, то мы удаляем эту конъюнкцию из ДНФ;

б) если в конъюнкцию одна и та же переменная входит несколько раз, то все они удаляются, кроме одной;

в) если в конъюнкцию не входят некоторые переменные, то для каждой из них к конъюнкции добавляется соответствующая формула вида ;

г) если в полученной ДНФ имеется несколько одинаковых конъюнкций, то оставляем только одну из них.

В результате получается СДНФ.

Задача 7. Найдите СДНФ для ДНФ .

Решение.

1. Удаляем конъюнкцию , так как здесь переменная вместе со своим отрицанием. Остается .

2. Из конъюнкции удаляем переменную у, так как она входит сюда два раза. Остается .

3. В первой конъюнкции нет переменной у, поэтому к ней добавляется формула , а во второй конъюнкции нет переменной х, поэтому к ней добавляется формула . Получаем:

.

4. Используем дистрибутивные законы:

.

5. К первой и второй конъюнкциям добавляем и получаем:

.

6. Используем дистрибутивные законы:

.

7. В полученной формуле имеется две одинаковые конъюнкции: . Удалив одну из них, получим:

В итоге мы получили соответствующую СДНФ.

Задача 8. Найдите СКНФ для КНФ .

Решение. Опишем алгоритм приведения КНФ к СКНФ аналогично вышеизложенному приведению ДНФ к СДНФ.

1. Во второй дизъюнкции не хватает переменной у, поэтому в дизъюнкцию добавим и, используя дистрибутивные законы, получаем:

.

2. В третью дизъюнкцию добавим и получим две дизъюнкции: . Добавив в каждую из них , получим:

.

3. Соберем в конъюнкцию все дизъюнкции:

.

4. Избавляемся от одинаковых дизъюнкций, оставляя только одну. В результате получается СКНФ: