Формулы логики булевых функций

Определение 4.2. Формула логики булевых функций определяется индуктивно следующим образом:

1. Любая переменная, а также константы 0 и 1 есть формула.

2. Если A и B – формулы, то ØA, AVB, A&B, A É B, A ~ B есть формулы.

3. Ничто, кроме указанного в пунктах 1–2, не есть формула.

Пример 4.1.

Выражение (ØxVy)&((y É z) ~ x) является формулой.

Выражение Øx&y É z Ø ~x не является формулой.

Часть формулы, которая сама является формулой, называется подформулой.

Пример 4.2.

x&(y Éz) – формула; y Éz – ее подформула.

Определение 4.3. Функция f есть суперпозиция функций f₁, f₂, ... , f_n если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.

Пример 4.3.

f₁ = x₁&x₂ (конъюнкция)_; f₂ = Øx (отрицание).

Возможны две суперпозиции:

1) f = f₁(f₂) = (Øx₁)&(Øx₂) – конъюнкция отрицаний;

2) f = f₂(f₁) = Ø(x₁&x₂) – отрицание конъюнкции.

Порядок подстановки задается формулой.

Всякая формула задает способ вычисления функции, если известны значения переменных.

Пример 4.4.

Построим таблицу значений функции f(x₁, x₂, x₃) = Ø(x₂ Øx₃) ~ (Øx₁Vx₂).

Таблица 4.4 представляет последовательное вычисление этой функции.

Таблица 4.4

x1 x2 x3	Øx3	x2 Øx3	Ø(x2 Øx3)	Øx1	Øx1Vx2	f(x1, x2, x3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Таким образом, формула каждому набору аргументов ставит в соответствие значение функции. Следовательно, формула так же, как и таблица, может служить способом задания функции. В дальнейшем формулу будем отождествлять с функцией, которую она реализует. Последовательность вычислений функции задается скобками. Принято соглашение об опускании скобок в соответствии со следующей приоритетностью операций: Ø, &, V, É и ~.