Нормальные формы. 
Информатика и математика

Как и в теории высказываний, в алгебре логики рассматриваются нормальные формы. Порядок их вычисления совершенно аналогичен вычислению нормальных форм высказываний.

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

Правильные элементарные дизъюнкция и конъюнкция называются полными относительно рассматриваемого набора переменных, если в них представлены все переменные.

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

Пример 3.7.

По таблице истинности разложить булеву функцию z (х_1; х₂) по переменным в СДНФ и СКНФ.

		].

Алгоритм построения СДНФ и СКНФ совершенно аналогичен алгоритму построения ДНФ и КНФ в теории высказываний.

1. Для записи формулы в СДНФ выбираем те строки, в которых z (x_bx₂) = 1. Как очевидно из таблицы, таких две — вторая и третья. В этих строках переменные соединяем между собой знаком логического умножения, причем переменные, равные нулю, записываем с отрицанием.

Полученные выражения в строках соединяем между собой знаком логического сложения. Запишем.

При необходимости полученную формулу можно упростить.

2. Для записи формулы в СКНФ выбираем те строки, в которых z (х_1; х₂) = = 0. В таблице таких две строки: первая и четвертая. В этих строках переменные соединяем между собой знаком логического сложения, причем переменные, равные единице, записываем с отрицанием.

Полученные выражения в строках соединяем между собой знаком логического умножения. Окончательно запишем.

При необходимости полученную формулу также можно упростить. ?

Пример 3.8.

Пусть по таблице истинности была получена формула в СДНФ.

Чтобы получить СКНФ, следует произвести двойное отрицание этой формы.

Преобразуем ее по законам де Моргана и двойного отрицания, т. е. отрицание логического умножения заменяем на логическое сложение отрицаний, а отрицание логического сложения — на логическое умножение отрицаний, отрицание отрицания — на саму переменную.

Имеем.

Последняя зависимость представляет собой СКНФ. ?

В заключение заметим, что обе нормальные формы формулы логики являются равносильными. Путем элементарных преобразований легко перейти с использованием законов де Моргана от первой формы ко второй и наоборот.

Вопросы и задания для самоконтроля

• 1. Дайте определение функции алгебры логики.
• 2. Чем отличаются существенные переменные от несущественных?
• 3. Какие функции называются равными?
• 4. Запишите основные функции алгебры логики и их таблицы истинности.
• 5. Чем отличается совершенная дизъюнктивная нормальная форма булевой функции от ее совершенной дизъюнктивной нормальной формы?

Задачи для самостоятельного решения

1. По таблице истинности формулы z = z (х_х, х₂, х₃) найти ее СДНФ и СКНФ. Упростить полученную формулу.

2. Упростить формулу элементарными преобразованиями.