Равносильность формул.

Определение. Две формулы алгебры высказываний f₁(x₁, x₂, ...., x_n) и f₂(x₁, x₂, ...., x_n) называются равносильными (f₁(x₁, x₂, ...., x_n) ≡ f₂(x₁, x₂, ...., x_n)), если

В высказываниях нас не интересует содержательная часть, а только значения истинности (0 или 1). Множество таких наборов конечно и равно 2ⁿ, и функцию можно задать таблично. Такая таблица называется таблицей истинности формулы.

П р и м е р 1 .Составить таблицу истинности формулы f =

Для построения таблицы истинности f вычислим ее значения на каждом из восьми наборов переменных.

0 0 0 1 1 0 0

0 0 1 1 1 0 0

0 1 0 1 1 0 0

0 1 1 1 1 0 0

1 0 0 0 0 0 1

1 0 1 0 0 1 1

1 1 0 0 1 0 0

1 1 1 0 1 1 1

П р и м е р 2 . Доказать равносильность формул

0 0 0 1 1 1 1

0 1 1 0 0 1 0

1 0 1 0 0 1 0

Левая и правая части рассматриваемой формулы принимают одни и те же значения для одинаковых наборах переменных x₁ и x₂, что и доказывает равносильность формул.

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

Примерами функционально полных систем являются { }, { } и др. Особое значение имеет базис .

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