Формулы логики булевых функций
Определение 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 есть суперпозиция функций f1, f2, ... , fn если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.
Пример 4.3.
f1 = x1&x2 (конъюнкция); f2 = Øx (отрицание).
Возможны две суперпозиции:
1) f = f1(f2) = (Øx1)&(Øx2) – конъюнкция отрицаний;
2) f = f2(f1) = Ø(x1&x2) – отрицание конъюнкции.
Порядок подстановки задается формулой.
Всякая формула задает способ вычисления функции, если известны значения переменных.
Пример 4.4.
Построим таблицу значений функции f(x1, x2, x3) = Ø(x2 
Øx3) ~ (Øx1Vx2).
Таблица 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, É и ~.
Равносильные преобразования формул
В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы
Øx1VØx2 и Ø(x1&x2)
реализуют одну функцию – штрих Шеффера.
Две формулы, реализующие одну и ту же функцию, называются равносильными.
Равносильность формул A и B будем обозначать следующтм образом: A º B.
Для того, чтобы установить равносильность формул, можно составить таблицы значений функции для каждой формулы и сравнить их. Для равносильных формул эти таблицы совпадают. Другой способ установления равносильности формул заключается в использовании некоторых установленных равносильностей булевых формул.