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

Таблица 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$ в анализе, поэтому их называют ** элементарными**.

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

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