Формулы. Равенство функций и эквивалентность формул. Основные эквивалентности
Формулы. Как и в анализе, исходя из элементарных функций, можно строить формулы.
Определение. Пусть $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$.
Далее:
Инвариантное определение дивергенции
Нормальные формы
Определение криволинейного интеграла второго рода
Переход от двойного интеграла к повторному. Изменение порядка интегрирования. Переход к полярным координатам
Определение двойного интеграла
Упрощение логических функций
Логические следствия
Полином Жегалкина. Пример.
Теорема Остроградского
Нахождение потенциала
Механические приложения тройного интеграла
Специальные векторные поля
Механические приложения криволинейного интеграла 1-го рода
Введение
Логические операции над высказываниями
Огравление $\Rightarrow $
Комментарии ()