Дизъюнктивные и конъюнктивные нормальные формы

Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более одного раза.

Например, формулы: ;

;

- являются элементарными конъюнкциями.

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

Например: F₁=  

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

Например, формулы: ;

;

- являются элементарными дизъюнкциями.

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

Например: F₂=  x₁ x₂ x₃

Алгоритм построения ДНФ и КНФ

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы (см. ПЗ №3).

2) Заменить знак отрицания, относящийся к выражениям типа  или , знаками отрицания, относящимися к отдельным переменным на основании формул:

 

1) ; 

 2) .

 

3) Избавиться от знаков двойного отрицания.

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

 

Пример 1. Приведите к ДНФ функцию f = .

Решение. Выразим логические операции «®» и «¯» через «Ù», «Ú», «-»:

f = .

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

f = = = = .

Используя закон дистрибутивности, приводим формулу к ДНФ:

f = =

 

Пример 2. Постройте КНФ функций и докажите тождественную истинность с помощью таблицы истинности: f(x₁, x₂, x₃) =

Решение. Процедура построения КНФ.

1. Исключаем связку «®» с помощью законов преобразования переменных:

.

2. Исключаем двойное отрицание с помощью правила  и используем законы де Моргана: 

 1) ;   

 2) .

3. Для получения нормальной формы используем дистрибутивные законы:

=

=

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

4. Проверка производится путем построения таблиц истинности для начальной (заданной) формулы и конечной (полученной в результате преобразований формулы).

 

Пример 3. Приведите к КНФ функцию f = .

Решение. Преобразуем формулу f к формуле, не содержащей ®:

f = = .

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

f = = .

По закону дистрибутивности получим:

f = , являющейся КНФ.

Замечание. Если полученную формулу упростить, используя законы дистрибутивности, эквивалентности и поглощения, то получим:

= = .

Таким образом, мы получили формулу, которая является одновременно ДНФ и КНФ.

 

Двойственность

Функция f₁ (x_1,…,x _n) называется двойственной к функции f₂ (x_1,…,x _n), если 

f₁ (x_1,…,x _n) = .

Функция, двойственная самой себе, называется самодвойственной: = f (x_1,…,x _n).

Самодвойственными являются, например, функции .

Пример 4. Определите, является ли функция  самодвойственной. f*= = = = = .

Т.к. f=f*, то функция самодвойственна.

 

Пример 5. Определите, является ли функция g = двойственной к 

f = ?

;

 =  = = .

Функция g двойственна f.

Принцип двойственности для булевых функций.

Если в формуле, представляющей функцию f, все конъюнкции заменить на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу, представляющую функцию, двойственную f.

Пример 6. Найти функцию, двойственную f=

f*= = .

 

Пример 7. Перейти от ДНФ к КНФ.

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

f

КНФ = f* = .

 

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

 

Пример 8. Определить, являются ли самодвойственными функции

f₁ = 10110100; f₂ = 10010110.

 

 

Вывод: f^­₁ не является самодвойственной.      f₂ является самодвойственной.

 

Работу составила преподаватель                      Т.С. Пронина.

                                  Практическое занятие №6

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

2 Цель работы: Научиться представлять булевы функции в совершенных дизъюнктивных и конъюнктивных нормальных формах.

Формирование ОК 2,3,8; овладение знаниями и умениями, необходимыми для освоения ПК 2.4. (спец. 09.02.03.), ПК 1.4, 2.4. (спец. 09.02.04.).

3 Подготовка к занятию: Повторите тему: «Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы».

4 Литература:

4.1 Конспект лекций по учебной дисциплине «Элементы математической логики», 2016

4.2 Приложение к ПЗ №6.

5 Перечень необходимого оборудования и материалов:

5.1 Бланк для отчета.

5.2 Канцелярские принадлежности.

6 Задание на занятие:

Основная часть

6.1 Найдите СДНФ для ДНФ .

6.2 Найдите СКНФ для КНФ .

6.3 Функция трех переменных дана набором 0 и 1: f () = 01011010. Найдите СДНФ и СКНФ для данной функции.

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

6.5 Функция трех переменных задана на единичном трехмерном кубе. Найдите ее СДНФ и СКНФ.

 

Вариативная часть

6.6 Найдите СДНФ и СКНФ для функций, заданных векторно.

а) f = 11001001;

б) f = 1;

в) f = 0.

7 Порядок выполнения работы:

Выполните практическую работу в соответствии с заданием (основная часть 6.1 – 6.5) и сдайте зачет. В случае получения зачета, выполните вариативную часть (6.6).

8 Содержание отчета:

Решения задач в соответствии с заданием.

9 Контрольные вопросы:

1 Что такое СДНФ, СКНФ?

2 Как задать СДНФ и СКНФ на единичном N- мерном кубе?

3 Как построить СДНФ, СКНФ?

4 Всегда ли ДНФ можно привести к СДНФ, КНФ к СКНФ?

5 Можно ли построить для одной функции две и более СДНФ, две и более СКНФ?

 

Приложение к практическому занятию по ЭМЛ № 6