Пример. Функцию представим в виде: 00-Ú0-1.

Функцию представим в виде: 00-Ú 0-1.

Тогда, подставляя вместо «–» всевозможные комбинации 0, 1, получим:

Таким образом, получили номера 000, 001, 011, которые соответствуют членам СДНФ.

СДНФ переключательной функции, тождественно равной 1 (тождественно истинной), содержит 2ⁿ констинтуэнт (n – число переменных).

Переключательная функция может быть представлена в конъюнктивной форме.

Выражение вида , содержащее множество попарно различных переменных или их инверсий, называется элементарной дизъюнкцией (ЭД).

Если переключательная функция, зависящая от n переменных, записана в виде конъюнкции элементарных дизъюнкций ЭД₁·ЭД₂·...·ЭД_r и хотя бы одна ЭД не содержит все n переменных, то такая форма задания называется конъюнктивной нормальной формой (КНФ). КНФ – конъюнкция конечного множества попарно различных элементарных дизъюнкций.

Например: f(аbсd)=а( Ú с)(bÚ d).

Произвольная функция, например, скобочная форма, может быть всегда приведена к КНФ следующим образом:

· заданную функцию инверсировать, получить ДНФ инверсной функции;

· ДНФ инверсной функции инверсировать еще раз, получить тождественную исходной функцию в КНФ;

· на каждом этапе следует производить необходимые упрощения.

Пример.

f(х₁х₂х₃)= ;

(х₁х₂х₃)= =

= ;

(х₁х₂х₃)= .

Получили КНФ.

Второй способ получения КНФ заключается в выполнении всех операций инверсии, применяемой к группе переменных (логическим выраженииям), затем используется распределительных закон.

Пример.

f(х₁х₂х₃)=

=

=

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

СКНФ может быть получена по запрещенным (нулевым) наборам функции, например по таблице истинности. Для получения СКНФ по таблице истинности необходимо составить элементарные дизъюнкции всех переменных для каждой строки таблицы, в которой функция равна 0. При этом в дизъюнкцию входит сама переменная, если ее значение равно 0, и отрицание переменной, если ее значение равно 1.

Так, для функции сложения по модулю 2 (табл. 32) СКНФ имеет вид:

.

Элементарные дизъюнкции, входящие в СКНФ функции, называются конституентами нуля (макстермами).

Конституента нуля обращается в нуль на единственном наборе переменных, который является запрещенным (нулевым) набором функции. Например, для функции сложения по модулю 2 конституента нуля (аÚ b) обращается в 0 на наборе 00, а конституента нуля – на наборе 11.

От СКНФ можно перейти к номерам запрещенных наборов в различных системах счисления. Для получения двоичных номеров в порядке базы функции (например, аb) необходимо заменить символы переменных с инверсией на 1, а без инверсии – на 0 и записать вместо элементарных дизъюнкций соответствующие совокупности двоичных чисел.

Если дополнительной информации нет, то все остальные числа из области задания функции считаются рабочими.

Для преобразования КНФ в СКНФ можно выполнить дизъюнкцию каждой элементарной дизъюнкции, не содержащей i-ю переменную, с тождественно ложным выражением . Таких недостающих переменных может быть несколько; тогда надо добавлять соответствующие тождественно истинные выражения. Затем применяется распределительный закон и производятся необходимые упрощения.

Например:

Соответствующие запрещенные наборы: 100, 110, 101, 111, 010 (база х₁х₂х₃).

Получим СДНФ и СКНФ ПФ, заданной десятичным номером №174₁₀.

Таблица истинности ПФ №174₁₀ показана в табл. 33

Таблица 33

Таблица истинности

СДНФ – совершенная дизъюнктивная нормальная форма:

СКНФ – совершенная конъюнктивная нормальная форма: