Булевы функции
Математическая логика окончательно оформилась как самостоятельная математическая дисциплина к 30-м годам XX века. Основная причина ее появления — математические парадоксы, например парадокс Рассела.
Сложно проводить математические рассуждения, не будучи уверенным в их непротиворечивости, а также в существовании объектов, которые они определяют.
Противоречие в антиномии Рассела возникает из-за использования в рассуждении понятия множества всех множеств и представления о возможности неограниченного применения законов классической логики при работе с множествами. Для преодоления этой антиномии было предложено несколько путей. Наиболее известный состоит в предъявлении для теории множеств непротиворечивой формализации , по отношению к которой являлись бы допустимыми все "действительно нужные" (в некотором смысле) способы оперирования с множествами. В рамках такой формализации утверждение о существовании множества всех множеств было бы невыводимым.
Возникла идея исследовать язык логики и математики, подойти к доказательству на основе понятий аксиом и правил вывода.
Будем рассматривать булевы функции (функции алгебры логики) — функции, аргументы и значения которых лежат в множестве {"истина" , "ложь"}. "Истину" и "ложь" будем обозначать соответственно 1 и 0. Таким образом, булева функция $f$ от $n$ аргументов есть $f : \underbrace{E_2 \times E_2 \times ... \times E_2 }_{n} \rightarrow E_2 .$ Аргументы этих функций будем называть логическими переменными и обозначать буквами $x$, $y$ и $z$, возможно, с индексами. Множество всех булевых функций (функций алгебры логики) будем обозначать $P_2$.
[math]\displaystyle{ \begin{array}{rrr|c} x & y & z & f(x,y,z)\\ \hline 2^3 \left\{ \begin{array}{r} 0\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 1\\ \end{array} \right. & \begin{array}{r} 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ 1\\ 1\\ \end{array} & \begin{array}{r} 0\\ 1\\ 0\\ 1\\ 0\\ 1\\ 0\\ 1\\ \end{array} & \begin{array}{r} 1\\ 0\\ 1\\ 0\\ 0\\ 1\\ 0\\ 1\\ \end{array} \end{array} }[/math]
Всего существует $2^3$ различных наборов значений трех переменных. Если их нумеровать от $0$ до $2^3-1$, то набор с номером $i$ оказывается представлением числа $i$ в двоичной системе счисления. Всего различных функций от 3-х аргументов — $2^{2^3}$ В общем случае число строк в таблице для функции от $n$ аргументов равно $2^n$.
Число различных булевых функций от $n$ аргументов — $2^{2^n}$.
Пусть [math]\displaystyle{ \gamma'=(\alpha_1, 0, \alpha_3) }[/math] и [math]\displaystyle{ \gamma''=(\alpha_1, 1, \alpha_3) }[/math] — два набора с произвольными значениями $\alpha_1$ и $\alpha_3$. Тогда по таблице выше можно убедиться, что [math]\displaystyle{ f(\gamma')=f(\gamma'') }[/math]: $f(0, 0, 0)=f(0, 1, 0)$, $f(0, 0, 1) = f(0, 1, 1)$ и так далее. В таком случае, можно сказать, что функция $f$ не зависит существенно от переменной $y$,
или, что $y$ — несущественная переменная функции $f$.
($x_n$ — фиктивная (несущественная) переменная функции $f(x_1, x_2, ..., x_n)$), если для любых значений $\alpha_1, \alpha_2, ..., \alpha_{n-1}\in E_2 $ выполняется равенство $f(\alpha_1, \alpha_2, ..., \alpha_{n-1}, 0)=f(\alpha_1, \alpha_2, ..., \alpha_{n-1}, 1)$.
Переменные функции $f$, которые не являются фиктивными, называют существенными переменными
и говорят, что функция $f$ существенно от них зависит.
Удалим из таблицы для функции $f$ по одной из каждой пары строк, соответствующих разным значениям переменной $y$ при одинаковых $x$ и $z$, а также удалим столбец со значениями переменной $y$. Получим таблицу для новой функции $f'(x,z)$:
[math]\displaystyle{ \begin{array}{cc|c} x & z & f'\\ \hline 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ 1 & 1 & 1\\ \end{array} }[/math]
Функции $f$ и $f'$ по определению различны: у них разная область определения. С другой стороны, если учитывать только существенные переменные, эти две функции
полностью совпадают. В дальнейшем будем считать такие функции равными.
если после удаления всех несущественных переменных получаются функции с одинаковыми таблицами.
В таком случае будем писать $f=g$.