СВ: Новая страница: «Использование табличного задания функций часто неудобно. Во-первых, число строк в табли...»

2026-10-24T18:15:43Z

Новая страница: «Использование табличного задания функций часто неудобно. Во-первых, число строк в табли...»

Новая страница

Использование табличного задания функций часто неудобно. Во-первых, число строк
в таблице экспоненциально зависит от числа переменных функции. Уже при 10 переменных,
число строк таблицы должно быть 1024.

Во-вторых, что более важно, при анализе свойств функции нельзя выполнять какие-либо
алгебраические преобразования для облегчения этого процесса.

В связи с этим будет удобно ввести понятие формулы, как еще одного представления функции.

Выберем некоторую систему функций из $P_2$: $\mathcal P=\{f_1, f_2, ..., f_k\}\subseteq P_2$, $k\geq 1$.
Назовем функции из системы $\mathcal P$ элементарными функциями.
Тогда формула над $\{f_1, f_2, ..., f_k\}$ определяется рекурсивно:

{{Определение
|definition=
1. Если $f\in\mathcal P$ {{---}} функция от $n$ аргументов, то $f(x_1, ..., x_n)$ {{---}} формула над $\mathcal P$.<br>
2. Если $f\in\mathcal P$ {{---}} функция от $n$ аргументов и $\mathcal U_1$, $\mathcal U_2$, ..., $\mathcal U_n$ {{---}} формулы или логические переменные, то $f(\mathcal U_1, ..., \mathcal U_n)$ {{---}} формула над $\mathcal P$.
}}

{{Замечание
|content=Мы определили формулу над $\mathcal P$. Формула всегда мыслится в связи с каким-то указанным множеством элементарных функций.
}}

Каждой формуле можно однозначно сопоставить функцию:
* Если $\mathcal U = f(x_1, ..., x_n)\in\mathcal P$, то формуле $\mathcal U$ сопоставляется функция $f_{\mathcal U}=f(x_1, ..., x_n)$.
* Пусть $\mathcal U = f(\mathcal U_1, ..., \mathcal U_n)$, где $f(x_1, ..., x_n)\in\mathcal P$ и $\mathcal U_1$, $\mathcal U_2$, ..., $\mathcal U_n$ {{---}} формулы или логические переменные.
Тогда $f_{\mathcal U}=f(f_{\mathcal U_1},...,f_{\mathcal U_n})$, где $f_{\mathcal U_i}$ {{---}} функция, сопоставленная формуле $\mathcal U_i$, если $\mathcal U_i$ {{---}} формула, и $f_{\mathcal U_i}=x_i$, если $\mathcal U_i = x_i$ {{---}} логическая переменная.

Говорят, что формула $\mathcal U$ реализует функцию $f_{\mathcal U}(x_1,...,x_n)$.

{{Пример
|content=Пусть дано множество элементарных функций $\mathcal P=\{f(x,y), g(x,y), h(x,y)\}$,где функции $f(x,y)$, $g(x,y)$, $h(x,y)$ заданы следующей таблицей:

<math>
\begin{array}{cc|ccc}
x & y & f & g & h\\
\hline
0 & 0 & 1 & 1 & 0\\
0 & 1 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 1\\
1 & 1 & 1 & 1 & 1\\
\end{array}
</math>

Пусть дана формула $\mathcal U = f(g(x,y), h(y,z))$.

Найдем функцию $f_{\mathcal U}$, реализованную формулой $\mathcal U$.

[[Файл:p34-01-formula-tree-evaluation.svg|frame|none|900px|alt=Дерево формулы f(g(x, y), h(y, z)): в узлах g = 0, h = 1, f = 0 на наборе (1, 0, 1); внизу цепочка вычисления и ответ 0|Рис. 1. Формула <math>f(g(x,y),h(y,z))</math> — это дерево: листья — переменные, внутренние узлы — элементарные функции. На наборе <math>(1,0,1)</math> значения считаются снизу вверх: сначала <math>g(1,0)=0</math> и <math>h(0,1)=1</math>, затем <math>f(0,1)=0</math>.]]

Для этого сначала найдем столбцы значений для функций, заданных
подформулами $g(x,y)$ и $h(y,z)$, а затем, уже получив нужные значения,
подставим их в качестве аргументов для функции $f$:

<math>
\begin{array}{ccc|ccc}
x & y & z & g(x,y) & h(y,z) & f(g(x,y), h(y,z))\\
\hline
0 & 0 & 0 & 1 & 0 & f(1,0)=0\\
0 & 0 & 1 & 1 & 1 & f(1,1)=1\\
0 & 1 & 0 & 1 & 1 & f(1,1)=1\\
0 & 1 & 1 & 1 & 1 & f(1,1)=1\\
1 & 0 & 0 & 0 & 0 & f(0,0)=1\\
1 & 0 & 1 & 0 & 1 & f(0,1)=0\\
1 & 1 & 0 & 1 & 1 & f(1,1)=1\\
1 & 1 & 1 & 1 & 1 & f(1,1)=1\\
\end{array}
</math>

}}

{{Определение
|definition=
Будем говорить, что формулы $\mathcal U$ и $\mathcal B$ эквивалентны, и писать $\mathcal U = \mathcal B$, если $f_{\mathcal U}=f_{\mathcal B}$ с точностью до несущественных переменных.
}}

Рассмотрим основные функции, используемые в качестве элементарных функций в алгебре логики.

Всего существует четыре различные функции от одной переменной: тождественный ноль {{---}} $f(x)=0$;
тождественная единица {{---}} $f(x)=1$; тождественная функция или тождественный $x$ {{---}} $f(x)=x$;
отрицание $x$ или "не $x$" {{---}} $f(x)=\neg x$, так же обозначается $\overline x$.

<math>
\begin{array}{c||c|c|c|c}
x & 0 & 1 & x & \neg x\\
\hline
0 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 0\\
\end{array}

</math>

Из них тождественный ноль и тождественная единица не зависят существенно от $x$.
То есть фактически это две функции без аргументов {{---}} константы: $f = 0$ и $f = 1$.

{{Замечание
|content=Может показаться, что излишне говорить о 0, 1 и x здесь, как о функциях.
Необходимо понимать, что в различном контексте эти символы могут пониматься различным образом.
С одной стороны мы имеем константы 0 и 1 и некоторую переменную x.
Но в контексте, предполагающем использование функций,
эти символы будут пониматься как отображения, указанные в таблице выше.

Численное значение этих величин не меняется, но меняется смысл, который мы вкладываем в запись.
}}

Рассмотрим основные булевы функции от двух переменных.

<math>
\begin{array}{cc||c|c|c|c|c|c|c}
x & y & x\vee y & x\wedge y & x\oplus y & x\supset y & x\equiv y & x|y & x \downarrow y\\
\hline
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\
\end{array}
</math>

$f(x,y) = x\vee y$ {{---}} дизъюнкция, логическое "или" .

$f(x,y) = x\wedge y$ {{---}} конъюнкция, логическое "и" , логическое умножение. Также можно использовать обозначения $x\&y$ или $xy$.

$f(x,y) = x\oplus y$ {{---}} сложение по модулю два, логическое исключающее "или". Также можно использовать обозначение $x+y$.

$f(x,y) = x\supset y$ {{---}} импликация, "если, то".Также можно использовать обозначение $x\!\rightarrow\! y$.

$f(x,y) = x\equiv y$ {{---}} эквивалентность. Также можно использовать обозначение $x \sim y$.

$f(x,y) = x | y$ {{---}} штрих Шеффера.

$f(x,y) = x\downarrow y$ {{---}} стрелка Пирса.

Всего, как мы помним, существует 16 различных функций от двух переменных.
Мы выбрали 7, существенно зависящих от обоих переменных и имеющих наибольшее значение.
Добавив к ним функции от одной переменной и константы (функции от 0 переменных) получим
систему функций, подмножества которой мы в основном будем использовать в
качестве множеств элементарных функций для построения формул
$P=\{0,1,x,\overline{x}, x\vee y, xy, x\oplus y, x\supset y, x\equiv y, x|y, x\downarrow y\}$.

Функции $\{\overline{x}, x\vee y, xy, x\oplus y, x\supset y, x\equiv y, x|y, x\downarrow y\}$ будем также называть операциями.

{{Пример
|content=Рассмотрим пример формулы над $P$:
$\mathcal U = (((xy)\vee (xz))\vee(yz))$.
}}
В этой записи слишком много скобок.

Чтобы облегчить чтение и запись формул
можно установить приоритеты выполнения операций.
Будем считать, что наивысший приоритет имеет операция отрицания.
Из функций от двух переменных наивысший приоритет будет иметь конъюнкция {{---}} $\wedge$.
Все остальные операции имеют одинаковый приоритет.

Кроме того, можно убедиться, что операции $\wedge, \vee, \oplus, \equiv$ являются ассоциативными.
Таким образом, вместо $x\circ (y\circ z)$ или $(x\circ y)\circ z$
можно писать $x\circ y\circ z$, если $\circ\in\{\wedge, \vee, \oplus, \equiv\}$.
Операции $\supset, |, \downarrow$ не являются ассоциативными.

{{Пример
|content=С учетом указанных договоренностей, формула из предыдущего примера примет вид: $\mathcal U = xy\vee xz\vee yz$.
}}

Эта формула задает известную функцию от трех переменных {{---}} функцию голосования.
Функция голосования носит такое название, поскольку моделирует голосование трех человек: функция принимает значение 1 тогда и только тогда, когда по крайней мере двое проголосовали положительно.

Конспект: [[Дискретная математика]]

Формулы - История изменений

СВ: Новая страница: «Использование табличного задания функций часто неудобно. Во-первых, число строк в табли...»