Приведение формулы к скнф.

Способ перехода от табличного задания к булевой формуле: для каждого набора переменных 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).