2020-05-12
150
Определение 1. Формула вида 
(соответственно, вида 
), где все фигурирующие в ней переменные попарно различны, называется элементарной конъюнкцией (соответственно, элементарной дизъюнкцией); 
– любой из литералов – x или 
.
Примеры: а) 
– элементарная дизъюнкция;
б) 
– элементарная конъюнкция.
Определение 2. Дизъюнктивная нормальная форма (ДНФ) – это формула вида 
... 
, где 
, i = 
– элементарная конъюнкция, содержащая некоторые из литералов 
,..., 
. В том случае, когда в каждую конъюнкцию для каждого номера j = 
входит в точности один из литералов 
, ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).
Теорема 1.5.1. Любая булева функция, отличная от константы 0 (соответственно, от константы 1) представима в виде СДНФ (соответственно, в виде СКНФ):
а) 
(,..., )СДНФ= 
;
|
б) (,..., )СКНФ= 
,
|
= i =
Алгоритм перехода от табличного задания
Булевой функции к СДНФ.
1. В таблице выбрать все конституенты единицы, т.е. те наборы 
=< 
> значений переменных 
,..., 
, на которых 
=1.
2. Каждому набору поставить в соответствие элементарную конъюнкцию 
= 
.
3. Все полученные элементарные конъюнкции логически сложить, т.е. искомая СДНФ для заданной функции будет:
(,..., )СДНФ= 
С использованием принципа двойственности для булевых алгебр определяется конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Алгоритм перехода от табличного значения
Булевой функции к СКНФ.
1. В таблице выбрать все конституенты нуля, т.е. те наборы =< 
> значений переменных ,..., , на которых 
=0.
2. Каждому набору 
поставить в соответствие элементарную дизъюнкцию 
= 
.
3. Все полученные элементарные дизъюнкции логически умножить, т.е. искомая СКНФ для заданной функции будет:
(,..., )СКНФ= 
.
Пример 1. Построить СДНФ и СКНФ булевой функции, заданной таблицей 1.5.1.
| Таблица 1.5.1 | ||||||
| № | x 1 | x 2 | x 3 | f (x 1, x 2, x 3) | Конституенты 1 | Конституенты 0 |
   0
| 0 | 0 | 0 | 1 | x 1 x 2 x 3 | |
 1
| 0 | 0 | 1 | 0 | x 1Ú x 2Ú x 3 | |
 2
| 0 | 1 | 0 | 1 | x 1 x 2 x 3 | |
 3
| 0 | 1 | 1 | 0 | x 1Ú x 2Ú x 3 | |
 4
| 1 | 0 | 0 | 0 | x 1Ú x 2Ú x 3 | |
 5
| 1 | 0 | 1 | 1 | x 1 x 2 x 3 | |
| 6
| 1 | 1 | 0 | 0 | x 1Ú x 2Ú x 3 | |
| 7 | 1 | 1 | 1 | 1 | x 1 x 2 x 3 | |
(, 
, 
)СДНФ= 
(
, , )СКНФ=(
)(
)(
)(
)
