Совершенные нормальные формы

Совершенная нормальная форма данной формулы – это формула, равносильная данной, содержащая только отрицания, конъюнкции и дизъюнкции.

Конъюнктивный одночлен или конъюнт от переменных , ,…, – это конъюнкция этих переменных или их отрицаний.

Конъюнктивный (дизъюнктивный) одночлен от переменных ,…, называется совершенным, если от каждой пары – ¬ входит ровно 1 представитель. Например, (¬ ) ۸ ۸ ).

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

i=1…p, - конъюнктивный одночлен.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктивных одночленов, то есть выражение вида i=1…e

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

Алгоритм приведения формулы к СДНФ (СКНФ):

1. Выбрать все наборы переменных, при которых формула истинна (ложна).

2. Для каждого набора выписать совершенный конъюнктивный (дизъюнктивный) одночлен, логическое значение которого равно 1 (0) на нем и только на нем.

Полученные одночлены соединить знаками дизъюнкции (конъюнкции)