§5 Нормальные формы для формул алгебры высказываний.

Конъюнктивным (дизъюнктивным) одночленом от переменных X₁, X₂, …, X_n называются конъюнкция (дизъюнкция) этих переменных или их отрицаний. Например, X₁X₂X₃, X­₁X₂, X₁ – конъюнктивные одночлены; X₁X₃, X₁X₂, X₃ – дизъюнктивные одночлены.

Дизъюнктивной (конъюнктивной) нормальной формой называется произвольная дизъюнкция (конъюнкция) конъюнктивных (дизъюнктивных) одночленов. Например, (Х₁X₂)(Х₁Х₂) – дизъюнктивная нормальная форма; (Х₁Х₂Х₃)(Х₁Х₂)Х₃ – конъюнктивная нормальная форма.

Сокращенная запись: ДН – форма и КН – форма соответственно.

Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз со знаком отрицания или без знака отрицания.

Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в неё одночлен является совершенным одночленом от тех же самых переменных.

Сокращённая запись: СДН – форма (или СДНФ) – совершенная дизъюнктивная нормальная форма, СКН – форма (или СКНФ) – совершенная конъюнктивная нормальная форма.

Например, (Х₁Х₂)(Х₁Х₂)(Х₁Х₂) – совершенная конъюнктивная нормальная форма от двух переменных X₁ и X₂;

(Х₁Х₂Х₃)(Х₁Х₂Х₃) – совершенная дизъюнктивная нормальная форма от трёх переменных X₁, X₂, X₃.

Теорема 1: Всякая формула алгебры высказываний, отличная от тождественно ложной, имеет единственную совершенную дизъюнктивную нормальную форму. Тождественно ложная формула СДНФ не имеет.

Теорема 2: Всякая формула алгебры высказываний, отличная от тождественно истинной, имеет единственную совершенную конъюнктивную нормальную форму. Тождественно истинная формула СКНФ не имеет.