§ 2. Формулы

Введем понятие формулы, с помощью которых можно задавать булевы функции. Эти формулы иногда называют пропозициональными формами или формулами алгебры (логики) высказываний.

Индуктивное определение формулы:

1. каждая булева переменная (x,y,z,…,x1,x2,…) является формулой;
2. если А и В формулы, то (¬А), (А&В), (А∨В), (А⇒В), (А≡В), (А | В) и (А↓ В) тоже формулы;
3. только те выражения являются формулами, для которых это следует из пп. 1) и 2).

Примеры формул: x, (¬ y), ((x&y)⇒(¬ z)).

Заглавные буквы латинского алфавита (А,В,C ,...) или те же буквы с числовыми индексами (А1,А2,...,В1,В2,...,С1,С2,...) употребляются для обозначения произвольных формул.

Как определено выше, каждая булева переменная может принимать значения 1 либо 0, которые считаем их (истинностными) значениями. Формулы являются аналитической записью булевых функций. В предыдущем параграфе были введены основные булевы функции, представленные в виде формул, и определены (истинностные) значения этих функций (формул).

Истинностное значение формул (булевых функций) можно определить с помощью таблиц истинности. Существуют различные методы построения таблиц истинности. Первый метод состоит в подробных вычислениях.

Например, для формулы (((x&y)∨z)⇒x) имеем следующую таблицу истинности.

Составление таблицы истинности можно сократить, выписывая шаг за шагом под каждой операцией значения той составляющей формулы, для которой применяется эта операция. Например, для той же формулы (((x&y)∨z)⇒ x) получаем таблицу:

Следующий метод построения таблиц истинности называют алгоритмом Квайна. В формуле выбирается некоторая переменная, например, та, которая чаще всего встречается в рассматриваемой формуле. Выбранной переменной (для формулы D=(((x&y)∨z)⇒ x) это будет переменная x) приписывается значение 1 либо 0. Далее проводят вычисления, где возможно, при выбранном значении этой переменной. Если x=1, то для формулы D=(((x&y)∨z)⇒ x), вне зависимости от значении y и z, легко получить, что D=1. При x=0 и z=0 получим снова, что D=1. Наконец, если x=0 и z=1, то D=0. В результате получим сокращенную запись таблицы истинности, содержащую всего три строки (в данном случае результат не зависит от значений переменной y):