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

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

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

Далее:

Теорема об алгоритме распознавания полноты

Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах

Вычисление поверхностного интеграла первого рода

Переход от двойного интеграла к повторному. Изменение порядка интегрирования. Переход к полярным координатам

Функции 2-значной логики. Лемма о числе функций. Элементарные функции 1-ой и 2-х переменных

Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина

Теорема об аналоге СДНФ в Pk

Поток векторного поля через поверхность

Теорема о заведомо полныx системаx

Линейный интеграл и циркуляция векторного поля

Механические и физические приложения поверхностного интеграла первого рода

Вычисление площади поверхности

Критерий полноты {теорема Поста о функциональной полноте}

Односторонние и двусторонние поверхности. Ориентация поверхности

Огравление $\Rightarrow $