Совершенная конъюнктивная нормальная форма.

Пусть зафиксирован набор булевых переменных x_1, x₂, ..., x_n.

Определение 1 . Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Если число переменных равноn, то такая элементарная дизъюнкция называется полной.

Теорема. Любая булева формула может быть представлена и притом единственным образом в виде СКНФ.

Приведение формулы к СКНФ.

Способ перехода от табличного задания к булевой формуле: для каждого набора переменных x₁, x₂, ... x_n , для которого функция f(x₁, x₂, ... x_n) равна 0, выписывается дизъюнкция всех переменных: над теми переменными, которые на этом наборе равны 1, ставятся отрицания; все такие дизъюнкции соединяются знаком конъюнкции.

Полученная таким образом формула является совершенной конъюнктивной нормальной формой ( СКНФ) логической функции f(x₁, x₂, ..., x_n).

П р и м е р 1.

0 0 1

0 1 1

1 0 0

1 1 1

П р и м е р 2. . f(x₁, x₂) ≡ x₁ ~ x₂ x₁ x₂ x₁ ~ x₂ f(x) ≡

0 0 1

0 1 0

1 0 0

1 1 1

Как уже говорилось, одна и та же логическая формула может быть представлена с помощью различных наборов логических операций. Существуют наборы логических операций, с помощью которых можно выразить любую логическую формулу. Такие наборы называют функционально полными системами или базисами. Примером, базиса является набор Этот базис обозначается буквой B.

Формулы алгебры высказываний, при образовании которых не использовались операции, отличные от , называют булевыми формулами алгебры высказываний.

Множество всех булевых формулназывают логической оболочкой базиса Ви обозначают P₂(B).