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

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

Пример. 1) Дизъюнктивный одночлен от 2-х переменных: .

2) Конъюнктивный одночлен от 3-х переменных: .

Теорема 1. Дизъюнктивный одночлен тогда и только тогда будет тождественно истинным, когда он содержит хотя бы одну дизъюнкцию вида , то есть дизъюнкцию некоторого высказывания и его отрицания.

Доказательство. 1) Пусть ДО И. Докажем, что он содержит . Предположим противное, то есть что ДО не содержит такой дизъюнкции. Тогда каждой переменной x_k, не стоящей под знаком отрицания присвоим значение Л, а каждой переменной x_p, стоящей под знаком отрицания присвоим значение И.

Рассмотрим .По определению эта дизъюнкция принимает значение лжи.

Следовательно, ДО будет принимать значение лжи или истины в зависимости от значений истинности остальных переменных, то есть не будет ТИ. Но это противоречит условию теоремы. Значит наше допущение неверно и справедливость 1-й части теоремы (то есть необходимость) доказана.

2) Пусть ДО содержит дизъюнкцию . Докажем, что ДО И. Так как ДО содержит дизъюнкцию , то по формуле равносильности 13 она является истинной, а значит и ТИ. Поэтому ДО по определению дизъюнкции будет истинным независимо от значений остальных переменных, а значит и ТИ.

Теорема 2. Конъюнктивный одночлен тогда и только тогда будет тождественно ложным, когда он содержит хотя бы одну конъюнкцию вида , то есть конъюнкцию некоторого высказывания и его отрицания.

Доказательство (аналогично теореме 1).

Определение 3, 4. Дизъюнктивной (конъюнктивной) нормальной формой формулы алгебры высказываний называется равносильная ей дизъюнкция (конъюнкция), состоящая из конъюнктивных (дизъюнктивных) одночленов.

Примеры.

1) Дизъюнктивная нормальная форма от 3-х переменных: .

2) Конъюнктивная нормальная форма от 2-х переменных:

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

Доказательство. Пусть дана произвольная формула F алгебры высказываний, содержащая даже все пять логических операций. Тогда на основании равносильностей 1-29 ее всегда можно преобразовать к равносильной ей формуле F₁ относительно трех операций: отрицание, конъюнкция, дизъюнкция, которая будет содержать хотя бы одну скобку с дизъюнкцией. Такая скобка на основании первого дистрибутивного закона всегда может быть представлена в виде дизъюнкции двух конъюнкций, то есть в ДН форме.

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

Доказательство (аналогично теореме 3).