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

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

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

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

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

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

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

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

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

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

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