Совершенная конъюнктивная нормальная формула

Канонические формы представления логических функций

Совершенная конъюнктивная нормальная формула

Определение 1. Элементарной дизъюнкцией n переменных называется дизъюнкция переменных или их отрицаний.

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

Определение 3. Совершенной конъюнктивной нормальной формулы (СКНФ) называется КНФ, удовлетворяющая следующим условиям:

1. все элементарные дизъюнкции, входящие в КНФ, содержат все переменные;

2. все элементарные дизъюнкции, входящие в КНФ, различны;

3. каждая элементарная дизъюнкция, входящая в КНФ, содержит переменную один раз;

4. ни одна элементарная дизъюнкция, входящая в КНФ, не содержит переменную и ее отрицание.

СКНФ можно получить двумя способами: а) с помощью таблицы истинности; б) с помощью равносильных преобразований.

ПОСТРОЕНИЕ СКНФ ПО ТАБЛИЦЕ ИСТИННОСТИ Алгоритм:

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

2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.

3. Все полученные дизъюнкции связать в конъюнкцию.

4. Упростить логическое выражение.

ПРИМЕР 1 (а). По заданной таблице истинности построить СДНФ и упростить ее.

1. Выбираем строки, в которых F=0

2. Выписать для каждой отмеченной строки дизъюнкции: 3 строка 4 строка 5 строка 6 строка 7 строка

3. Объединяем полученные дизъюнкции конъюнкцией.

4. Упрощаем логическое выражение.