§ 18. Нормальные дизъюнктивные формы

1.Рассмотрим сначала общее представление о нормальных формах.

Для их определения вводится символическая степенная функция

, (18.1)

причем:

Для таких функций естественно определяются все ранее рассмотренные логические операции: если дан набор высказываний то их элементарным конъюнктом (или конъюнктивным одночленом) называется высказывание

. (18.2)

Аналогично, их элементарным дизъюнктом (или дизъюнктивным одночленом) называется высказывание вида

(18.3)

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

(18.4)

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

(18.5)

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

Нормальная форма называется совершенной, если в каждый её элементарный конструкт входят все исходные высказывания (возможно – с внутренними отрицаниями).

2.Более подробно остановимся на случае тернарных нормальных форм. В этом параграфе мы рассмотрим строение дизъюнктивных нормальных форм от трёх переменных. Для них мы получаем следующие слои элементарных конъюнктов:

а) одноместные конъюнкты

(18.6)

б) двуместные конъюнкты

(18.7)

В) трёхместные конъюнкты

(18.8)

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

(18.9)

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

Для трёхместных тернарных конъюнктов вводится также сокращённая запись, соответствующая десятичной индексации (вместо двоичной). Применяя её, получим:

(18.10)

Именно такие выражения мы применяли для построения матриц Карно для тернарных операций и, в частности, полей Канта.

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

3. Чтобы не загромождать запись многочисленными скобками, мы будем пользоваться традиционным представлением о порядке выполнения бинарных операций: если не выставлены скобки, то выполняются сначала все конъюнкции в элементарных конъюнктах, затем они последовательно соединяются дизъюнкциями. Отметим, что отрицания легко переносятся к самим внутренним высказываниям с помощью законов да Моргана. Если в исходной формуле присутствуют какие-либо другие операции, то с помощью законов взаимосвязи между бинарными операциями все они приводятся к формулам, содержащим конъюнкции, дизъюнкции и их отрицания. Отметим, что традиционно считается, что противоречивая исходно формула не имеет дизъюнктивной нормальной формы, хотя в реальности эта форма – просто нулевая, так как отсутствуют рабочие блоки на карте (или в матрице) Карно.

Теперь перейдём к некоторым примерам.

3.1. Пусть задана исходная формула

(18.11)

Эта формула – только от двух переменных, поэтому в её преобразовании будут принимать участие элементарные конъюнкты первого и второго уровней. Представим исходную формулу в виде конъюнкции двух высказываний:

(18.12)

Для этих выражений по формулам бинарных операций получаем:

(18.13)

Следовательно, их конъюнкция имеет вид

,

Что приводит к выводу о виде ДНФ:

(18.14)

3.2. Задана формула

(18.15)

Требуется построить для неё ДНФ.

Для решения подразделяем всю исходную формулу на две части:

(18.16)

В первой формуле вводим обозначение .

Теперь получаем

Поэтому

(18.17)

Для этой формулы построим матрицу Карно:

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

Аналогично проводится преобразование второй формулы. Для этого вводится обозначение внутренней бинарной операции

В этом случае находим

Поэтому

(18.18)

Значит, для неё матрица Карно имеет вид

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

Замечаем, что для построения импликации составляющих формул нужно знать их отрицания, которые находятся или непосредственно (вычитанием из общей формулы универсума), или с помощью построения матриц Карно. Мы применим первый способ, и получим:

(18.19)

Окончательная формула представляет собой импликацию, в которой

подставляя найденные выражения, получаем:

(18.20)

Для неё также построим матрицу Карно

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

Данная формула представляет собой вид совершенной дизъюнктивной формы.

Заметим, что полученная формула не является тавтологией (всюду истинной формулой), хотя оказывается выполнимой.

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

1.Смысл символической степенной функции и её применение.

2. Понятие об элементарных конъюнктах.

3. Понятие об элементарных дизъюнктах.

4. Определение дизъюнктивной нормальной формы.

5. Определение конъюнктивной нормальной формы.

6. Понятие о совершенных нормальных формах.

7. Тернарные элементарные конъюнкты.

8. Общий вид тернарной дизъюнктивной нормальной формы.

9. Применение матриц Карно в анализе дизъюнктивных нормальных форм.