Формулы. Равенство функций и эквивалентность формул. Основные эквивалентности
Формулы. Как и в анализе, исходя из элементарных функций, можно строить формулы.
Определение. Пусть $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$.
- Ассоциативность. $(x_1\circ x_2)\circ x_3 = x_1\circ (x_2\circ x_3)$.
- Коммутативность. $x_1\circ x_2 = x_2\circ x_1$.
- Дистрибутивность. $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)$.
- Правила де Моргана. $\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 } $.
- $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$.
Далее:
Условия независимости криволинейного интеграла от пути интегрирования
Вычисление поверхностного интеграла первого рода
Равносильные формулы алгебры высказываний
Логические следствия
Вычисление площадей плоских областей
Определение тройного интеграла. Теорема существования тройного интеграла
Определение двойного интеграла
Критерий полноты {теорема Поста о функциональной полноте}
Вычисление площади поверхности
Несобственные интегралы от неограниченной функции
Механические и физические приложения поверхностного интеграла первого рода
Класс $T_1$. Теорема о замкнутости класса $T_1$
Линейный интеграл и циркуляция векторного поля
Булевы функции от $n$ переменных
Огравление $\Rightarrow $
Комментарии ()