Материал: 4553
36
Совершенные дизъюнктивная и конъюнктивная нормальные формы
Функции, которые принимают единичное значение только на одном наборе, получили специальное обозначение. Называют их минимальными термами, а коротко – минтермами. Минтермом n переменных называется такое их произведение, в которое каждая переменная входит один раз (с отрицанием или без). Обозначаются минтермы буквой m с десятичным индексом, являющимся номером минтерма. Двоичный эквивалент номера минтерма – это набор, на котором минтерм принимает единичное значение. Например, если
функция зависит от трех аргументов |
, то |
|
|
, |
, |
, |
, и т.д. |
Если таблица соответствия содержит только одну единицу в колонке , то |
|||
функция представляет собой минтерм. Если же в колонке |
содержится две |
||
единицы (в различных строках), то функцию образует сумма соответствующих
минтермов. Такой случай представлен в табл. 4.3. |
|
|
|
|
|
||||||
В |
ней |
единицы |
расположены |
|
|
|
Таблица 4.3 |
||||
в строках |
2 и |
5, |
следовательно: |
|
|
|
|
|
|
||
№ |
A |
B |
C |
f |
|
||||||
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|||||
Аналогично рассуждая, придем к |
1 |
0 |
0 |
1 |
0 |
|
|||||
|
|
|
|
|
|
|
|||||
выводу о том, что в функцию может |
2 |
0 |
1 |
0 |
1 |
|
|||||
|
|
|
|
|
|
|
|||||
входить три, четыре и так далее |
3 |
0 |
1 |
1 |
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
||
минтермов. |
И |
вообще, |
всякая |
4 |
1 |
0 |
0 |
0 |
|
||
|
|
|
|
|
|
|
|
||||
совокупность единиц в колонке |
дает |
5 |
1 |
0 |
1 |
1 |
|
||||
|
|
|
|
|
|
|
|
|
|||
некоторую |
булеву функцию |
и ее |
6 |
1 |
1 |
0 |
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
||
всегда |
можно |
записать в |
виде |
7 |
1 |
1 |
1 |
0 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
суммы минтермов.
Если функция представлена в виде сумы минтермов n аргументов, то говорят, что она записана в совершенной дизъюнктивной нормальной форме, сокращенно СДНФ.
Пусть функция, принимающая единичное значение на наборах 001, 010, 100, 101 и 110. Тогда ее аналитическое представление в СДНФ примет вид
.
37
Всякая булева функция заданного числа аргументов представима в виде суммы минтермов единственным образом. По этой причине СДНФ называют
иногда стандартной формой, а также
канонической.
Макстерм (максимальный терм) – это булева функция, которая, в отличие от минтерма, принимает единичное значение на всех наборах, за исключением одного. На этом единственном наборе макстерм принимает нулевое значение. В таблице соответствия для таких функций колонка f содержит точно один нуль и 
№ |
A |
B |
C |
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
1 |
0 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
2 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
3 |
0 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
4 |
1 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
5 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
6 |
1 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
7 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
единиц, где n – число аргументов, от которых зависит макстерм.
Макстермы будем обозначать большой буквой M с десятичными индексами по аналогии с обозначением минтермов. Нетрудно заметить, что макстерм – это отрицание минтерма, и наоборот: минтерм – это отрицание макстерма. Воспользуемся этим обстоятельством и найдем аналитическое
выражение макстерма. |
Таблица 4.4 |
||
Пусть функция зависит от аргументов |
|
|
|
, и пусть в таблице соответствия |
|
|
|
в строке 5 колонки |
записан нуль, а во |
|
|
всех остальных строках – единицы (табл. 4.4). |
Добавим справа еще |
одну |
|
колонку и запишем в нее ту же функцию |
, но в инверсной |
форме. |
|
Тогда |
, откуда получаем: |
|
|
.
Индекс макстерма определяется точно так же, как и в случае минтерма.
Макстермом n переменных называется такая их сумма, в которую каждая |
|
переменная входит один раз (с |
отрицанием или без). Очевидно, что число |
различных макстермов такое же, |
как и число минтермов, т.е. , где – число |
переменных макстерма.
Между индексами минтермов и макстермов имеется вполне определенная
связь: |
|
; |
, где |
38
Если задана СДНФ некоторой булевой функции 
, то найти ее СКНФ
очень легко. Сначала находим СДНФ инверсии заданной функции. В f войдут все минтермы, отсутствующие в 
, и ни один минтерм не войдет одновременно в 
и f . Затем записываем аналитическое выражение для f и результат инвертируем по теореме де Моргана. Проиллюстрируем это примером.
Пусть
.
В эту функцию, зависящую от трех аргументов, не входят минтермы 
, 
, 
. Следовательно, они войдут в инверсию функции 
:
.
Инвертируем по теореме де Моргана:
.
Это и есть искомая СКНФ заданной функции 
.
4.2. Практическая часть
Пример 1. Представить функцию |
|
в совершенной |
дизъюнктивной нормальной форме.
Решение. Составим таблицу истинности для данной функции:
x |
y |
z |
x y |
( x y ) z |
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
0 |
1 |
1 |
0 |
0 |
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
1 |
0 |
1 |
0 |
0 |
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
Из таблицы истинности видно, что функция принимает значение 1 на двух наборах 001 и 111. Тогда ее аналитическое представление в СДНФ примет вид
39
Пример 2. Представить функцию 
в совершенной конъюнктивной нормальной форме.
Решение. Составим таблицу истинности для данной функции:
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
0 |
1 |
1 |
0 |
0 |
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
|
|
|
|
|
Из таблицы истинности видно, что функция принимает значение 0 на трех наборах 000, 001 и 011. Тогда аналитическое выражение для 
будет:
.
Инвертируем по теореме де Моргана:
.
Это и есть искомая СКНФ заданной функции 
.
4.3. Задачи для самостоятельного решения
Задача 1. |
Представить функцию |
в совершенной дизъюнктивной |
||||
нормальной форме. |
|
|
|
|
||
|
|
|
|
|
|
|
Вариант |
|
Функция |
Вариант |
Функция |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
8 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
9 |
· |
|
|
|
|
|
|
|
|
3 |
|
|
|
10 |
|
|
|
|
|
|
|
|
|
4 |
|
|
|
11 |
|
|
|
|
|
|
|
|
|
5 |
|
|
|
12 |
|
|
|
|
|
|
|
|
|
6 |
|
(x |
|
13 |
|
|
|
|
|
|
|
|
|
7 |
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
40 |
|
|
|
|
Задача 2. |
Представить функцию |
в совершенной конъюнктивной |
|||||
нормальной форме. |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
Вариант |
|
Функция |
|
Вариант |
Функция |
|
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
22 |
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
23 |
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
24 |
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
25 |
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
26 |
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
27 |
|
|
|
|
|
|
|
|
|
|
21 |
|
|
|
|
28 |
|
|
|
|
|
|
|
|
|
|
Библиографический список
1.Владимирский, Б. М. Математика. Общий курс [Текст] : учеб. / Б.М. Владимирский, А.Б. Горстко, Я.М. Ерусалимский. – СПб. ; М. ; Краснодар : Лань, 2008. – 960 с.
2.Поздняков, С. Н. Дискретная математика [Текст] : учеб. / С.Н. Поздняков, С.В. Рыбин. – М. : Академия, 2008. – 448 с.