Функции 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$ соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции.