Построение совершенной дизъюнктивной и конъюнктивной нормальных форм

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

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

Если система - полная и любая  из функций f1, f2,...,fm может быть выражена с помощью суперпозиций через  функции g1, g2,…, gk, то система также  полная.

 

 

 

 

 

 

Глава 2. Двойственность функций

2.1 Принцип двойственности.

Двойственной для булевой функции   называется  булева функция:

.

ПРИМЕР

Функция  f  называется самодвойственной если  

Утверждение 1. Если функция f(x1, x2, …, xn) самодвойственная, то функция   тоже самодвойственная.

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

Противоположными называются те наборы, которые в сумме дают         двоичный код числа (2ⁿ-1).

ПРИМЕР

Функция   является самодвойственной, т.к.    

 

ТЕОРЕМА (Закон двойственности)

Если формула равносильна формуле  ,  то формула  равносильна формуле 

(Если две равносильные формулы  заменить двойственными, то равносильность  сохранится). 

 

ТЕОРЕМА  (Принцип двойственности)

Двойственная к булевой  формуле может быть получена заменой  констант 0 на 1,1 на 0, Ù на Ú, Ú на Ù и сохранением структуры формулы (т.е. соответствующего порядка действий).

Примеры самодвойственных функций.

f(x)=(01) 
f(x,y)=(0101) 
f(x,y)=(1010) 
f(x,y)=(0011) 
f(x,y)=(1100) 
f(x,y,z)=(01010101) 
f(x,y,z)=(10101010) 
f(x,y,z)=(00001111) 
f(x,y,z)=(11110000) 
f(x,y,z)=(00110011) 
f(x,y,z) =(11001100)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 3.1 СДНФ и СКНФ.

 Определим степень следующим образом:

 , т.е.    

Выражение вида:  - называется полной совершенной элементарной конъюнкцией.

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

Выражение вида:  - называется полной совершенной элементарной дизъюнкцией.

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

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

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

ПРИМЕР

Составим  СДНФ и СКНФ для функции .

Формула:

 ,

таким образом, получили СКНФ для функции, состоящую из одной элементарной дизъюнкции.

Продолжим преобразования, получим:

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

 

На этом примере покажем связь  между таблицей истинности функции  и ее совершенными нормальными формами:

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

 

  

 

 

  

 

                                                Таблица 5.Таблица истинности  формулы

СДНФ:

СКНФ:

Инверсия  в логике (от лат. inversio — переворачивание, перестановка) 

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

 

х1	х2		элементарные конъюнкции
0	0	1
0	1	1
1	0	0
1	1	1

 

                                                        Таблица 6.Таблица нахождения СДНФ

Совершенная дизъюнктивная нормальная форма (СДНФ) – такая дизъюнкция конъюнкций, в которой:

1. Различны все члены конъюнкции ("множители");
2. Различны все члены каждой дизъюнкции ("слагаемые");
3. В каждой дизъюнкции нет одновременно переменной и ее отрицания;
4. Каждая дизъюнкция содержит все переменные, входящие в данную формулу или их отрицания.

 СДНФ:  

Приведение формулы к СДНФ с помощью равносильных преобразований:

1. Привести формулу к нормальному виду (т.е. избавиться от импликации, эквиваленции и отрицания неэлементарных формул).
2. Из всех одинаковых членов дизъюнкции ("слагаемых") оставить только один.
3. Если в каком-то члене дизъюнкции ("слагаемом") не хватает переменной Xi, то "домножаем" его с на, т.е. на 1 .
4. Раскрыть скобки и из всех одинаковых членов дизъюнкции ("слагаемых") оставить только один.

Для построения СДНФ по таблице истинности необходимо:

1. Выбрать из таблицы истинности те строки, в которых значение формулы - "Истина".
2. Для каждой выбранной строки составить конъюнкцию переменных или их отрицаний так, чтобы эта конъюнкция была истинной (для этого переменные, которые в соответствующей строке имеют значение "Ложь" нужно взять с отрицанием, а переменные, имеющие значение "Истина" - без отрицания).
3. Составить дизъюнкцию полученных конъюнкций.

X	Y	Z	F	СДНФ	СКНФ
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

 

 

                                                  

 

 

 

 

                Таблица 7. Таблица истинности для построения СДНФ и СКНФ

CДНФ:

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

Перечислим свойства совершенства для СДНФ:

1. Каждое логическое слагаемое  формулы содержит все переменные, входящие в функцию.

2. Все логические слагаемые различны.

3. Ни одно слагаемое не содержит  одновременно переменную и ее  отрицание.

4. Ни одно слагаемое не содержит  одну и ту же переменную  дважды.

Алгоритм получения СДНФ по таблице истинности:

1. Отметить те строки таблицы  истинности, в последнем столбце  которых стоят 1:

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

3. Все полученные конъюнкции  связать в дизъюнкцию: 

4. Упрощаем формулу, применяем  законы логики.

 

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

Перечислим свойства совершенства для СКНФ:

1.Каждый логический множитель  формулы содержит все переменные, входящие в функцию.

2.Все логические множители различны.

3.Ни один множитель не содержит  одновременно переменную и ее  отрицание.

4.Ни один множитель не содержит  одну и ту же переменную  дважды.

 

Алгоритм получения СКНФ по таблице истинности

1. Отметить те строки таблицы  истинности, в последнем столбце  которых стоят 0:

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

3. Все полученные дизъюнкции  связать в конъюнкцию:  

4. Упрощаем формулу, применяем  законы логики (если это необходимо).

Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. СДНФ       и  СКНФ   

Можем проверить, построив таблицу  истинности по найденной формуле.

 

X	Y
0	0	1	1
0	1	0	0
1	0	1	1
1	1	0	1

                                Таблица 8.Таблица эквивалентности СДНФ и СКНФ

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

 

х1	х2		элементарные дизъюнкции
0	0	1
0	1	1
1	0	0
1	1	1

 

                                                                     Таблица 9.Таблица нахождения СКНФ

Литерал в логике высказываний

В логике высказываний литералом называют переменную или ее логическое отрицание.

Соответственно, положительным литералом называют непосредственно переменную, а отрицательным литералом — логическое отрицание переменной.

 

3.2 ДНФ И КНФ

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