Дизъюнктивные и конъюнктивные нормальные формы. Совершенные нормальные формы. Алгоритм построения.

Дизъюнктивным одночленом от n переменных называется дизъюнкция этих переменных или их отрицаний

X1 / X2(отриц.)/ X3, X1 / X 3(отриц.) , X 1 / X 2 / X3

Аналогично конъюнктивным одночленом называется конъюнкция переменных или их отрицания

X1 / X2 ; X1 / X2 / X3

Формула являющаяся конъюнкцией дизъюнктивных одночленов называется КНФ.

(X1 / X2(отриц) / X3) / (X1 / X3(отриц)) / (X1 / X2 / X3)

Аналогично ДНФ выглядит так:

(X1 / X2) / (X1(отриц) / X2(отриц) / X3)

Алгоритм построения ДНФ и КНФ:

1. Избавиться от логических операций импликации, эквиваленции, если они есть в формуле

2. Применить закон Де Моргана

3. Избавиться от двойного отрицания

4. Если нужно применить законы дистрибутивности и

поглощения.