Алгоритм Куайна для ДНФ

Алгоритм Куайна для ДНФпозволяет проверить выполнимость и общезначимость приведенной дизъюнктивной нормальной формы.

Пусть р – элементарное высказывание, а S – приведенная ДНФ, которая может быть представлена в виде:

S= S_pÈ S_{ù p} È (S_р\ S^||_p),

где S_p – дизъюнкты, содержащие высказывание р;

S_{ù p} – дизъюнкты, содержащие ùр;

S^||_p = (S\(S_pÈ S_{ù p})).

Алгоритм

1. Если S = Æ, то S – выполнима.

2. Если S = F, то S – невыполнима.

3. Иначе:

а) выбирается p, входящее в S;

б) определяются множества S_p, S_{ù p}, S^||_p;

в) получение S^|_p из S_p удалением р;

г) получение S^| _{ù p} из S_{ù p} удалением ù p .

S – невыполнимо тогда и только тогда, когда невыполнимы два множества (S^|_pÈS^||_р) и (S^|_{ù p} ÈS^||_р). Если р – Т, то S º (S^|_{ù p} È S^||_р), если р – F, то S º (S^|_pÈ S^||_р).

{F, r}- не выполняется.