Совершенные формы

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

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

Коньюктивной нормальной формулой (КНФ) называется коньюнкция элементарных дизьюнктов, при этом дизьюнкты не должны повторяться.

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

Теорема 1: всякая формула отличная от тождественно ложной имеет СДНФ и эта форма единственная с точностью до пеестановки элементарных коньюнктов и порядка переменных в этих коньюнктах.

Теорема 2: всякая формула отличная от тафтологии имеет СКНФ и эта форма единственная с точностью до пеестановки элементарных дизьюнктов и порядка переменных в этих дизьюнктах.

Доказательство 1:

1)Пусть есть функция f (A₁ … Аn) не тождественно ложная

Рассмотрим ее таблицу истинности: каждой строке поставим в соответствии элементарный коньюнкт, где Х_i = А_i , если А_i = И

Х_i = А_i , если А_i = Л

Дизьюнкция берется по все строчкам, в которых f=И.

F - СДНФ

Возьмем любую строку таблицы

1. Если f=И, тогда все коньюнкты в этой строке истинны, следовательно, F=И

2. Если f=Л, тогда все коньюнкты в этой строке ложны, следовательно, F=Л

2)Всякому элементарному коньюнкту, который входит в СДНФ соответствует одна строка таблицы истинности, всякий элементарный коньюнкт истинен только в той строке, которой он соответствует, следовательно, каждый из СДНФ задает именно единственную функцию.

Доказательство 2:

Аналогично доказательству 1.