§ 8. Совершенные конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний.

Определение 1, 2. Дизъюнктивный (конъюнктивный) одночлен от n переменных высказываний x₁, x₂, ..., x_n называется совершенным, если каждая переменная входит в него ровно один раз: либо сама, либо своим отрицанием.

Из этих определений следует, что совершенный одночлен от n переменных высказываний состоит точно из n членов.

Примеры.

1) СКО от двух переменных:

2) CДО от трех переменных: , .

Определение 3. Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний называется такая ДН форма этой формулы, в которой каждый ее конъюнктивный одночлен является совершенным.

Пример. СДНФ формулы от двух переменных .

Определение 4. Совершенной конъюнктивной нормальной формой формулы алгебры высказываний называется такая КН форма этой формулы, в которой каждый ее ДО является совершенным.

Пример. СКНФ формулы от трех переменных .

Из этих определений и доказанных выше теорем вытекают следующие принципиально важные следствия.

Следствия 1, 2. Для всякой формулы алгебры высказываний, не являющейся ТИ (ТЛ) существует равносильная ей СКН форма (СДН форма) и притом единственная.

Из всего выше изложенного вытекает следующий алгоритм приведения формул алгебры высказываний к совершенным нормальным формам.

1. Приводим данную формулу F алгебры высказываний к равносильной ей формуле F₁ относительно первых трех логических операций.

2. Приводим полученную формулу F₁ к равносильной ей нормальной форме: конъюнктивной или дизъюнктивной.

3. Если в полученной нормальной форме имеются одинаковые одночлены, то из них оставляют только один, остальные отбрасывают.

4. Если в одночлене нормальной формы имеются одинаковые переменных x_k, то из них оставляют только одну, остальные отбрасывают.

5. Если в полученной нормальной форме имеется одночлен, содержащий переменную x_i с ее отрицанием , то все такие одночлены отбрасывают.

6. Если какой-либо одночлен F_j от n переменных не содержит некоторой переменной x_i, то он заменяется двумя одночленами вида для случая ДН форм и двумя одночленами вида для случая КН форм.