Введение в схемы, автоматы и алгоритмы

Формулы


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

Мы будем рассматривать формулы, построенные над множеством элементарных функций

. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 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

Каждая строка этой таблицы задает процесс вычисления функции

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



Содержание раздела