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


Формулы


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

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

\mathcal{B}=\{ 0, 1, \neg, \wedge, \vee, \rightarrow, +, \sim,\ | \}
. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.

Зафиксируем некоторое счетное множество переменных

V=\{ X_1, X_2, \ldots \}
. Определим по индукции множество формул над
\mathcal{B}
с переменными из
V
. Одновременно будем определять числовую характеристику
dep(\Phi)
формулы
\Phi
, называемую ее глубиной, и множество ее подформул.

Определение 1.2.

а) Базис индукции. 0, 1 и каждая переменная

X_i \in V
является формулой глубины 0, т.е.
dep(X_i)= dep(0)= dep(1)=0
. Множество ее подформул состоит из нее самой.

б) Шаг индукции. Пусть

\Phi_1
и
\Phi_2
- формулы,
\circ \in \{ \wedge, \vee, \rightarrow, +, \sim,\ | \}
. Тогда выражения
\Phi= \neg \Phi_1
и
\Phi= ( \Phi_1 \circ \Phi_2)

являются формулами. При этом

dep(\neg \Phi_1)=1 + dep( \Phi_1)
, а
dep((\Phi_1 \circ \Phi_2))=1 + \max\{dep( \Phi_1), dep( \Phi_2)\}
. Множество подформул
\Phi
включает саму формулу
\Phi
и для
\Phi= \neg \Phi_1
все подформулы формулы
\Phi_1
, а для
\Phi= ( \Phi_1 \circ \Phi_2)
все подформулы формул
\Phi_1
и
\Phi_2.

Каждой формуле

\Phi(X_1,\ldots, X_n)
сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

Базис индукции. Пусть

dep(\Phi)=0
. Тогда
\Phi = X_i \in V
или
\Phi =c \in \mathcal{B}

В первом случае

\Phi
задает функцию
f_{\Phi}(X_i)=X_i
, во втором - функцию, тождественно равную константе
c
.

Шаг индукции. Пусть

\Phi
- произвольная формула глубины
dep(\Phi)= k+1
. Тогда
\Phi(X_1,\ldots, X_n)= \neg \Phi_1(X_1,\ldots, X_n)

или

\Phi(X_1,\ldots, X_n)= ( \Phi_1(X_1,\ldots, X_n) \circ \Phi_2(X_1,\ldots, X_n))

для некоторой булевой связки

\circ \in \{ \wedge, \vee, \rightarrow, +, \sim,\ | \}
. Так как
\max \{dep( \Phi_1), dep( \Phi_2)\} \leq k,
то формулам
\Phi_1
и
\Phi_2
соответствующие функции
f_1(X_1,\ldots, X_n)
и
f_2(X_1,\ldots, X_n)
уже сопоставлены. Тогда формула
\neg\Phi_1

задает функцию

f_{\Phi} =\neg f_1(X_1,\ldots, X_n)
, а формула
\Phi(X_1,\ldots, X_n)= ( \Phi_1(X_1,\ldots, X_n) \circ \Phi_2(X_1,\ldots, X_n))

задает функцию

f_{\Phi} = f_1(X_1,\ldots, X_n) \circ f_2(X_1,\ldots, X_n)
.

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

Пример 1.1. Например, для формулы

\Phi_1= ( (X_1 \vee \neg\neg X_2)\rightarrow (X_3 + (X_1 \wedge \neg X_2)))
функция
f_{\Phi_1}
задается выделенным столбцом
\rightarrow
следующей таблицы.

Таблица 1.3. Функция

f_{\Phi_1}
X_1
 
X_2
 
X_3
((X_1
  
\vee
  
\neg
\neg
  
X_2)
\rightarrow

(X_3
  
+
  
(X_1
  
\wedge\
  
\neg
X_2)))

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

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

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




Начало  Назад  Вперед



Книжный магазин