§ 19. Конъюнктивные нормальные формы
1. Сразу перейдём к рассмотрению тернарных конъюнктивных нормальных форм, как наиболее значимых в учебном процессе. Элементарные дизъюнкты, из которых будут составляться конъюнктивные нормальные формы, обозначим по аналогии с предыдущими обозначениями для элементарных конъюнктов, полагая:
а) для одноместных дизъюнктов
(19.1)
б) для двуместных дизъюнктов
(19.2)
в) для трёхместных дизъюнктов
(19.3)
Таким образом, тернарная конъюнктивная нормальная форма может быть представлена в виде последовательности конъюнкций:
(19.4).
Здесь параметры
принимают значения из множества
Если все входящие в данную формулу элементарные дизъюнкты являются трехместными, то сама форма называется совершенной.
2. Для трёхместных конъюнктов также применяются сокращённые обозначения, в которых используются десятичные эквиваленты двоичной записи индексов, что приводит к виду:
(19.5)
По законам двойственности конъюнкции и дизъюнкции мы можем сопоставить элементарным дизъюнктам соответствующие им элементарные конъюнкты, учитывая законы де Моргана:
(19.6)
В упрощенной записи эти формулы имеют вид:
(19.7)
Аналогично может быть найдена взаимосвязь между любыми уровнями конъюнктов и дизъюнктов. Затем строятся соответствующие внешние конъюнкции для получения конъюнктивной нормальной формы.
3. Рассмотрим несколько поясняющих примеров.
3.1. Найти ДНФ и КНФ для тернарной операции:
(19.8)
Сначала строим дизъюнктивную нормальную форму. Для этого вводим обозначение внутренней бинарной операции
Для внутренней бинарной операции находим по формулам дизъюнкции
(19.9)
Поэтому для всей формулы получаем
(19.10)
Последняя из формул (19.9) является дизъюнктивной нормальной формой и может быть записана в виде
(19.11)
В упрощенной записи эта формула записывается так:
(19.12)
Теперь составляем для неё матрицу Карно:
Z
|
Y X |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
Отсюда делаем
вывод о наличии нулевых блоков, на базе
которых можно перейти к построению
конъюнктивной нормальной формы, учитывая
формулы (19.6):
Таким образом, получаем вид совершенной конъюнктивной нормальной формы для данной формулы:
(19.13)
В упрощенной записи находим:
(19.14)
Или – в явном виде:
(19.15)
3.2. Найдём обе нормальные формы для формулы:
(19.15)
Сначала ищем дизъюнктивную нормальную форму. Для этого вводим обозначения бинарных операций:
(19.16)
Для них находим выражения через конъюнкции по соответствующим формулам бинарных операций. При этом сразу записываем сами формулы
и их отрицания:
(19.17)
Теперь для всей формулы получаем:
(19.18)
При вычислении результата следует учитывать, что конъюнкции одинаковых элементов объединяются в один, а для противоположных (отрицаний) дают пустое множество, то есть, исключаются из формулы.
Таким образом, получаем:
(19.19)
После раскрытия скобок и приведения подобных членов, находим:
(19.20)
Записываем матрицу Карно для этой формулы:
Z
|
Y X |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Таким образом, приходим к выводу, что
(19.21)
Поэтому сразу можем записать конъюнктивную нормальную форму:
. (19.22)
Таким образом, можно сделать вывод, что на базе матрицы Карно просто можно найти все виды нормальных форм.
Контрольные вопросы:
1. Вид одноместных дизъюнктов.
2. Вид двухместных дизъюнктов.
3. Вид трёхместных дизъюнктов.
4. Общая формула для тернарной дизъюнктивной формы.
5. Сокращенная запись тернарных дизъюнктов.
6. Взаимосвязь между тернарными дизъюнктами и конъюнктами.
7. Методы построения дизъюнктивных нормальных форм.