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

ДНФ и импликанты
Функция f имплицирует функцию g, если .
Замечание: Если , то .

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

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

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

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

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

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

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

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

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

Пример
Пусть функция представлена своей ДНФ.
Тогда ее единичное множество имеет вид:

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

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