СДНФ и СКНФ

Нормальная форма логической функции – если логическая функция представлена дизъюнкцией, конъюнкцией и инверсией.

Ранг элементарной конъюнкции или дизъюнкции — это число аргументов ее образующих.

Пример:   

Элементарная конъюнкция третьего порядка.

Элементарная дизъюнкция второго порядка.

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

Пример:

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

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

• нет двух элементарных дизъюнкций;
• ни одна элементарная дизъюнкция не содержит двух одинаковых переменных;
• ни одна элементарная дизъюнкция не содержит переменную вместе с ее инверсией;
• все дизъюнкции имеют один и тот же ранг.

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

• нет двух одинаковых элементарных конъюнкций
• ни одна элементарная конъюнкция не содержит двух одинаковых переменных;
• ни одна элементарная конъюнкция не содержит переменную вместе с ее инверсией;
• все конъюнкция имеют один и тот же ранг.

Убедиться, является ли данная формула ДНФ, КНФ, СДНФ или  СКНФ:

Решение

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

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

в) Формула не является ни ДНФ, ни КНФ, поскольку содержит импликацию.

г) СДНФ, состоящая из одной элементарной полной конъюнкции; либо КНФ, но не СКНФ, так как  состоит из трех элементарных неполных дизъюнкций.

д) СКНФ.

 е) СДНФ.

Алгоритм образования СКНФ и СДНФ по таблице истинности

1. Выделить в таблице истинности все строки, в которых функция принимает значения 0.

2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие переменные:

а) если значение переменной равно 0, то записывается сама переменная,

б) если значение переменной равно 1, то записывается инверсия этой переменной

3. Соединить элементарные дизъюнкции знаком конъюнкции.

Алгоритм образования СКНФ и СДНФ по таблице истинности

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

2. Для каждого выбранного набора записать элементарные конъюнкции, содержащие переменные:

а) если значение переменной равно 0, то записывается инверсия этой переменной,

б) если значение переменной равно 1, то записывается сама переменная.

3. Соединить элементарные конъюнкции знаком дизъюнкции.