Совершенные нормальные формы истинностных функций

Имеется два способа задания истинностных функций — формулой и истинностной таблицей. По формуле легко составляется истинностная таблица. На практике при конструировании различных электронных устройств возникает обратная задача – от истинностной таблицы перейти к формуле.

Для ее решения имеются два алгоритма. Пусть имеется истинностная функция

F(P₁,..., Р_п), заданная истинностной таблицей.

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

1. Рассмотрим все те наборы значений атомов P₁,..., Р_п, для которых

f(P₁,..., Р_п)=И.

В примере такими наборами будут (И, И, И), (И, И, Л), (И, Л, И), (Л, И, И).

2. Для каждого из отобранных наборов составляем конъюнкцию из атомов P₁,..., Р_п или их отрицаний, принимающую при данном наборе значение И.

Конъюнкции, содержащие все п атомов P₁,..., Р_п (с отрицаниями или без них), называются элементарными конъюнкциями (длины п).

В нашем примере элементарными конъюнкциями будут такие формулы:

P₁ Ù P₂ Ù P_з

P₁ Ù P₂ Ù ¬P_з

P₁ Ù ¬P₂ Ù P_з

¬P₁ Ù P₂ Ù P_з.

в) Составляем дизъюнкцию выписанных элементарных конъюнкций. Для нашего примера получим такую дизъюнкцию:

P₁ Ù P₂ Ù P_з Ú P₁ Ù P₂ Ù¬ P_з Ú P₁ Ù¬ P₂ Ù P_з Ú¬ P₁ Ù P₂ Ù P_з.