ДНФ и импликанты

1. Дискретная математика

2. ДНФ и импликанты

• Функция f имплицирует
функцию g, если f g 1 .
• Замечание: Если f g 1 ,
M f Mg
то .

3. Импликант

Если f имплицирует g, и f
представлена единственной
элементарной конъюнкцией, то f
называется импликантом g.
• Если из импликанта нельзя
удалить ни одной переменной, то
оно называется простым
импликантом.

4. Теорема

Теорема
Если функция f x1 , x2 , ... , xn
представима единственной
элементарной конъюнкцией
– всех n переменных, то
– m < n переменных, то
Mf 2
n m
.
M f 1 ;

5. Пример

Пусть f ( x , y , z ) xyz .
Она принимает значение 1 тогда и
только тогда, когда x = 1, y = 1, z = 1.
Значит M f 111 .

6. Пример

Пусть f ( x, y , z ) yz .
Она принимает значение 1 тогда и
только тогда, когда y = 0, z = 1.
Значит, чему равняется переменная
х – неважно, и она может принимать
любые значения. Поэтому
M f 001,101 .

7. Утверждение 1

Утверждение 1
Представление функции в виде ДНФ
соответствует представлению ее
единичного множества в виде
объединения единичных множеств
входящих в эту ДНФ элементарных
конъюнкций.

8. Пример

Пусть функция представлена своей ДНФ.
f ( x , y , z ) xyz y z x y
.
Тогда ее единичное множество может
быть представлено в виде:
M f M xyz M y z M x y
101 000 ,100 000 , 001
Получилось, что M f 000 , 001,100 ,101

9. Утверждение 2

Утверждение 2
Любая конъюнкция ДНФ функции
является импликантом данной
функции.

10. Утверждение 3

Утверждение 3
Если конъюнкция ДНФ функции
не является простым
импликантом, то можно найти
соответствующий ей простой
импликант (или импликанты) и
заменить им (или их
дизъюнкцией) непростой
импликант.

11. Определение

ДНФ, состоящая только из
простых импликантов,
называется сокращенной.
.

12. Пример

Пусть функция представлена своей
ДНФ.
f ( x , y , z ) x xyz
Тогда ее единичное множество
имеет вид:
M f M x M xyz 000, 001, 010, 011 101
000, 001, 010, 011,101

13. Пример

Очевидно, что
x
– это простой
импликант. Он состоит из одной
буквы, и если ее вычеркнуть,
получится вырожденная конъюнкция
(конъюнкция не имеющая
переменных), что возможно только в
случае, если
f 1 .

14. Пример

Проверим, будет ли простым
импликант
k xyz
Вычеркнем из него
переменную х.
.

15. Пример

Получим конъюнкцию
k1 yz
Ее единичное множество содержит 2
набора: M k1 001, 101 M f
то есть
k1 по-прежнему является
импликантом f.
Значит
k xyz
импликант.
– не простой