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

Пусть $U = {u_1,u_2,..., u_m,...}$ — исходный алфавит переменных (аргументов) и $ E_2 = {0,1} $.

Определение. Функция $f(u_{i_1}, u_{i_2},... ,u_{i_n})$, где $u_{i_s} \neq u_{i_t}$ при $s \neq t$, аргументы и значение которой определены на множестве $E_2$, называется функцией алгебры логики или булевой функцией.

Замечание. Чтобы избежать сложных обозначений для индексов переменных, мы будем употреблять в качестве произвольных символов алфавита $U$ символы $x,y,z,..$, а также эти символы с индексами $x_1, x_2, . . . , y_1,y_2, . . .$

Опишем два способа задания функций алгебры логики.

$\textbf{Таблица.}$ Для задания функции $f (x_1,..., x_n)$ достаточно указать, какое значение функции соответствует каждому из наборов значений аргументов, т.е. выписать таблицу.

$x_1$ ... $x_{n-1}$ $x_{n}$ $f(x_1, ..., x_{n-1}, x_n)$
0 ... 0 0 $f(0, ..., 0, 0)$
0 ... 0 1 $f(0, ..., 0, 1)$
0 ... 1 0 $f(0, ..., 1, 0)$
0 ... 1 0 $f(0, ..., 1, 1)$
... ...
1 ... 1 1 $f(1, ..., 1, 1)$

Таблица 1. Таблица функции $f(x_i,...,x_n)$

Обозначим через $P_2$ систему всех функций алгебры логики над алфавитом $U$, содержащую также константы $0$ и $1$.

Лемма 1.1. Число всех функций из $P_2$, зависящих от, переменных $x_i,x_2,...,x_n$, равно $2^{2^{n}}$.

Доказательство. Легко видеть, что $n$ переменных принимают $2^{n}$ различных значений. Поэтому таблица функции $f (x_i,... ,x_n)$ содержит $2^{n}$ строк (наборов). Наборы принято располагать в соответствии с естественным порядком следования двоичных записей чисел $0,1,..., 2^{n} — 1$. Поскольку на каждом наборе функция принимает одно из двух значений {$0$ или $1$}, то число различных функций равно $2$ в степени "количество наборов", т.е. $2^{2^{n}}$.

Следовательно, уже при сравнительно небольших значениях $n$ перебор функций становится практически невозможным, даже с использованием компьютера.

Рассмотрим примеры функций алгебры логики. Данные функции часто употребляются в математической логике и кибернетике и играют такую же роль, как, например, $x^n$ или $sin x$ в анализе, поэтому их называют элементарными.

$x$ константа $0$ константа $1$ тождественная $x$ отрицание $\bar{x} $
0 0 1 0 1
1 0 1 1 0

Таблица 2. Элементарные функции одной переменной.

$x_1$ $x_2$ коньюнкция $x_1\wedge x_2$ дизъюнкция $x_1\vee x_2$ импликация $x_1\rightarrow x_2$ сложение по mod2 $x_1\oplus x_2$ эквиваленция $x_1\equiv x_2$ штрих шеффера $x_1|x_2$
0 0 0 0 1 0 1 1
0 1 0 1 1 1 0 1
1 0 0 1 0 1 0 1
1 1 1 1 1 0 1 0

Таблица 3. Элементарные функции двух переменных.

Замечание. Часто вместо $x_1\wedge x_2$ пишут $x_1x_2$. Также заметим, что $x_1\wedge x_2 = min(x_1; x_2) = x_1\cdot x_2$, $x_1\vee x_2 = max(x_1, 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) = 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)$ построим новую таблицу, вычеркивая все строки вида $(0,..., а_{i—1},1, a_{i+1},..., a_n)$ и вычеркивая столбец переменной $x_i$. Полученная таблица определяет некоторую функцию $g(x_1,..., x_{i—1},x_{i+1},..., x_n)$. Будем говорить, что функция $g$ получена из $f$ путем удаления фиктивной переменной $x$, а также, что функция $f$ получается из $g$ путем введения фиктивной переменной $x_i$.

Определение. Функции $f_1$ и $f_2$ называются равными, если функцию $f_2$ можно получить из $f$ путем введения и удаления фиктивных переменных.

Напомним, что каждой формуле над $F$ соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.