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

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

Определение. Пусть $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$

Таблица 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)$.

1. Правила де Моргана.

$\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 }$.

1. $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$.