Нормальные формы в алгебре высказываний: СДНФ, СКНФ

СДНФ
Теорема: Для любой Формулы в алгебры высказываний, отличной от тождественно ложной существует ее представление в виде:
f(x1,x2,..,xn)  (x11.x22….xnn),
сн(1,2,..,n ) | f(1,2,..,n)1 - СДНФ данной формулы.
Пусть f(x1,x2,..,xn) - формула в алгебры высказываний
Разложим эту формулу по переменной x1
Тогда: f(x1,x2,..,xn)снизу(1E2) x11(1,x2,..,xn)  (разложим по x2 и подставим в разложение)   снизу (1E2)( снизу (2E2) x11.x22f(1,2,x3,..,xn))…и т.д. 
  снизу (1,2,..,n ) x11.x22….xnn f(1,2,..,n),
где f(1,2,..,n) - 0 or 1
Мы можем опустить те слагаемые, для которых f(1,1,..,n)0, и получим
f(x1,x2,..,xn) снизу [(1,2,..,n) | f(1,2,..,n)1] x11.x22….xnn
СКНФ, КНФ, ДНФ
Теорема: Для любой формулы в алгебры высказываний, отличной от тождественно истинной существует ее представление в виде:
f(x1,x2,..,xn) (x11x22…xnn) снизу [(1,2,..,n) | f(1,2,..,n)0] - СКНФ данной формулы.
При доказательстве используем принцип двойственности
СКНФ->СДНФ Двойной двойственностью:
f(x1,x2,..,xn)(f*( x1,x2,..,xn))*[не явл.≡0=>СДНФ](x11.x22….xnn)*≡
(1,2,..,nE2)|f*(1,2,..,n)1
≡ [f(x1,x2,..,xn)]  x11x22…xnn,
(1,2,..,n)|f(1,2,..,n)0
Пр: x1→x2 ≡ ( x2) [CКНФ] ≡ (x2 )x2(x1 )≡
≡ x2 x1x2 x2 ≡ x2 x1x2 [СДНФ]
КНФ, ДНФ
Обозначим V={x1,x1,x2,x 2,..,xn,xn}
Элементарная конъюнкция - конъюнкция всех элементов множества υ  V
По опр: ДНФ –дизъюнкция элементарных конъюнкций
Пр: x1x2x3
Аналогично:
Элементарная дизъюнкция - дизъюнкция всех элементов множества υ  V
КНФ – конъюнкция элементарных дизъюнкций.
Змч.: СДНФ является ДНФ, СКНФ является КНФ

Powered by Drupal - Design by artinet