Как мы видели, табличное представление булевых функций подходит лишь для функций с небольшим числом аргументов. Формулы позволяют удобно представлять многие функции от большего числа аргументов и оперировать различными представлениями одной и той же функции.
Мы будем рассматривать формулы, построенные над множеством элементарных функций
. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.
Зафиксируем некоторое счетное множество переменных
. Определим по индукции множество формул над
с переменными из
. Одновременно будем определять числовую характеристику
формулы
, называемую ее глубиной, и множество ее подформул.
Определение 1.2.
а) Базис индукции. 0, 1 и каждая переменная
является формулой глубины 0, т.е.
. Множество ее подформул состоит из нее самой.
б) Шаг индукции. Пусть
и
- формулы,
. Тогда выражения
и
являются формулами. При этом
, а
. Множество подформул
включает саму формулу
и для
все подформулы формулы
, а для
все подформулы формул
и
Каждой формуле
сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.
Базис индукции. Пусть
. Тогда
или
В первом случае
задает функцию
, во втором - функцию, тождественно равную константе
.
Шаг индукции. Пусть
- произвольная формула глубины
. Тогда
или
для некоторой булевой связки
. Так как
то формулам
и
соответствующие функции
и
уже сопоставлены. Тогда формула
задает функцию
, а формула
задает функцию
.
Для определения функции, задаваемой небольшой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующей подформулой.
Пример 1.1. Например, для формулы
функция
задается выделенным столбцом
следующей таблицы.
Таблица 1.3. Функция
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 0 1 0
0 0 0 1 0
0 1 1 0 1
0 1 1 0 1
1 1 0 1 0
1 1 0 1 0
1 1 1 0 1
1 1 1 0 1
1
1
0
1
1
0
0
1
0 0 0 0 1 0
1 1 0 0 1 0
0 0 0 0 0 1
1 1 0 0 0 1
0 1 1 1 1 0
1 0 1 1 1 0
0 0 1 0 0 1
1 1 1 0 0 1
Каждая строка этой таблицы задает процесс вычисления функции
на соответствующих аргументах изнутри-наружу: вместо каждого вхождения переменной в формулу подставляется ее значение, затем в полученной формуле, состоящей из констант и булевых связок, последовательно вычисляются значения самых внутренних функций (подформул), для которых уже определены значения их аргументов, до тех пор, пока не будет получено значение всей формулы.
