Формулы. Равенство функций и эквивалентность формул. Основные эквивалентности

Формулы. Как и в анализе, исходя из элементарных функций, можно строить формулы.

Определение. Пусть $F$ — некоторое {не обязательно конечное} подмножество функций из $P_2$

а) Базис индукции. Каждая функция $f(x_1, x_2,..., x_n)$ из $F$ называется формулой над $F$.

б) Индуктивный переход. Пусть $f_0(x_1, ..., x_n)$ — функция из $F$ и $A1,..., An$ — выражения, являющиеся либо формулами над $F$, либо символами переменных из алфавита $U$. Тогда выражение $f_0(A_1, ..., A_n)$ называется формулой над $F$.

Замечание. В дальнейшем будем обозначать формулы заглавными готическими буквами (\mathfrak{M}, \mathfrak{N}), а системы функций — заглавными каллиграфическими буквами $(A, B, F)$.

Пример 1.1. Пусть $F$ — множество элементарных функций. Следующие выражения являются формулами над $F$:

1) $((x_1x_2) + x_1) \rightarrow x_2$;

2) $ \bar{x_1}(x_2 \vee x_3)$;

3) $\overline {x_1 \vee ((x_2 \wedge x_3)(x_3 \wedge x_2))}$.

Сопоставим теперь каждой формуле $\mathfrak{M}$ над $F$ функцию из $P_2$, опираясь на индуктивное определение формул.

а) Базис индукции. Если $\mathfrak{M} = f(x_1 ,..., x_n)$, где $f \in F$, то формуле $\mathfrak{M}$ сопоставим функцию $f(x_1 ,..., x_n)$.

б) Индуктивный переход. Пусть $\mathfrak{M} = f_0(A_1 ,..., A_n)$, гдe $A_1 ,..., A_n$ — выражения, являющиеся либо формулами над $F$, либо символами переменных из алфавита $U$. Тогда по предположению индукции каждому $A_i$ сопоставлена либо функция $f_i$ из $P_2$, либо тождественная функция $f_i = x_s$. Сопоставим формуле $\mathfrak{M}$ функцию $f(x_1 ,..., x_n) = f_0(f_1 ,..., f_n)$.

Пример 1.2. Формула $((x_1x_2) + x_1)\rightarrow x_2$, строится за три шага. Мы имеем следующие подформулы:

$((x_1x_2) + x_1, ((x_1x_2) + x_1)\rightarrow x_2$

$x_1$ $x_2$ $x_1x_2$ $(x_1x_2)+x_1$ $((x_1x_2)+x_1)\rightarrow x_2$
0 0 0 0 1
0 1 0 0 1
1 0 0 1 0
1 1 1 0 1

Таблица 4. Построение таблицы функции, заданной формулой $((x_1x_2) + x_1)\rightarrow x_2$

Равенство функций и эквивалентность формул

Введенное понятие функции не позволяет рассматривать функции от меньшего числа аргументов как функции от большего числа аргументов.

Определение. Функция $f(x_1,...,x_{i—1},x_i,x_{i+1},... ,x_n)$ из $P_2$ существенно зависит от переменной $x_i$, если существуют такие значения $\alpha ,1,..., \alpha_{i—1}, \alpha_{i+1},..., \alpha_n$ переменных $x_1,...,x_{i—1}, x_{i+1},...,x_n$, что

$f(\alpha_1,...,\alpha_{i-1},0,\alpha_{i+1},...,\alpha_n) \neq f(\alpha_1,...,\alpha_{i-1},1,\alpha_{i+1},...,\alpha_n)$.

В этом случае переменная $x_i$ называется существенной. Если $x_i$ не является существенной переменной, то она называется фиктивной.

Пусть для функции $f(x_1,..., x_n)$ перемениая $x_i$ является фиктивной. По таблице функции $f(x_1,... ,x_n)$ построим новую таблицу, вычеркивая все строки вида $(\alpha_1,...,\alpha_{i-1},1,\alpha_{i+1},...,\alpha_n)$ и вычеркивая столбец переменной $x_i$. Полученная таблица определяет некоторую функцию $g(x_1,..., x_{i—1},x_{i+1},..., x_n)$. Будем говорить, что функция $g$ получена из $f$ путем удаления фиктивной переменной $x_i$ а также, что функция $f$ получается из $g$ путем введения фиктивной переменной $x_i$.

Определение. Функции $f_1$ и $f_2$ называются равными, если функцию $f_2$ можно получить из $f_1$ путем введения и удаления фиктивных переменных.

Напомним, что каждой формуле над $F$ соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.

Определение. Формулы $\mathfrak{M}$ и $\mathfrak{N}$ над $F$ называются эквивалентными, если соответствующие им функции равны. Записи $\mathfrak{M}$ = $\mathfrak{N}$ будет означатв, что формулы $\mathfrak{M}$ и $\mathfrak{N}$ эквивалентны.

Пример 1.3. $x\bar{x} = 0$

Приведем список основных эквивалентностей, характеризующих некоторые свойства элементарных функций. Обозначим через $x_i\circ x_2$ любую из функций $x_1\wedge x_2$, $x_1\vee x_2$, $x_1 + x_2$.

  1. Ассоциативность. $(x_1\circ x_2)\circ x_3 = x_1\circ (x_2\circ x_3)$.
  2. Коммутативность. $x_1\circ x_2 = x_2\circ x_1$.
  3. Дистрибутивность.
    $x_1\wedge(x_2\vee x_3) = (x_1\wedge x_2) \vee (x_1\wedge x_3)$, $x_1\vee (x_2 \wedge x_3) = (x_1 \vee x_2) \wedge (x_1 \vee x_3)$, $x_1 \wedge (x_2 + x_3) = (x_1 \wedge x_2) + (x_1 \wedge x_3)$.
  4. Правила де Моргана. $\overline{x_1 \wedge x_2} = \bar{x_1} \vee \bar{x_2}$, $\overline{x_1 \vee x_2} = \bar{x_1} \wedge \bar{x_2}$.
  5. $0 = x \wedge \bar{x} = x \wedge 0 = x + x$, $1 = x \vee \bar{x} = x \vee 1 = x \sim x$, $x = \bar{\bar{x}} = x \wedge x = x \vee x = x \wedge 1 = x \vee 0$, $\bar{x} = x + 1, x_1 \sim x_2 = \overline{x_1 + x_2}$, $x_1 \rightarrow x_2 = \bar{x_1} \vee x_2$.

Замечание. С целью упрощения записи формул мы условимся, что конъюнкция сильнее других элементарных функций. Более того, знак конъюнкции можно не писать. Например, записи $x_1x_2 \vee x_3$ означает $(x_1 \wedge x_2) \vee x_3$.

Замечание. Очевидно, что если $\mathfrak{M}$ — подформула формулы $\mathfrak{M}$ и если заменитв любое из ее вхождений на эквивалентную формулу $\mathfrak{N}$, то формула $\mathfrak{M}$ перейдет в формулу $\mathfrak{N}$, которая будет эквивалентна $\mathfrak{M}$.

Пример 1.4. $x_1 \vee x_1 x_2 = x_1 \wedge 1 \vee x_1x_2 = x_1(1 \vee x_2) = x_1 \wedge 1 = x_1$.