Формулы

Использование табличного задания функций часто неудобно. Во-первых, число строк в таблице экспоненциально зависит от числа переменных функции. Уже при 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\}$ определяется рекурсивно:

Определение:

1. Если $f\in\mathcal P$ — функция от $n$ аргументов, то $f(x_1, ..., x_n)$ — формула над $\mathcal P$.
2. Если $f\in\mathcal P$ — функция от $n$ аргументов и $\mathcal U_1$, $\mathcal U_2$, ..., $\mathcal U_n$ — формулы или логические переменные, то $f(\mathcal U_1, ..., \mathcal U_n)$ — формула над $\mathcal P$.

Замечание

Мы определили формулу над $\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)$.

Пример

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

[math]\displaystyle{ \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$.

Рис. 1. Формула [math]\displaystyle{ f(g(x,y),h(y,z)) }[/math] — это дерево: листья — переменные, внутренние узлы — элементарные функции. На наборе [math]\displaystyle{ (1,0,1) }[/math] значения считаются снизу вверх: сначала [math]\displaystyle{ g(1,0)=0 }[/math] и [math]\displaystyle{ h(0,1)=1 }[/math], затем [math]\displaystyle{ f(0,1)=0 }[/math].

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

[math]\displaystyle{ \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]

Определение:

Будем говорить, что формулы $\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]\displaystyle{ \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$.

Замечание

Может показаться, что излишне говорить о 0, 1 и x здесь, как о функциях.

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

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

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

[math]\displaystyle{ \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\}$ будем также называть операциями.

Пример

Рассмотрим пример формулы над $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$ не являются ассоциативными.

Пример

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

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

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