Лекция п Булевы функции. Существенная и фиктивная переменная

путем удаления фиктивной переменной x_i, а также, что функция получается из путем введения фиктивной переменной x_i.

Определение 5.3. Функции f₁ и f₂ называются равными, если функцию f₂ можно получить из f₁ путем введения и (или) удаления фиктивных переменных.
В дальнейшем всюду функции рассматриваются с точностью до фиктивных переменных, т.е. мы считаем, что если задана функция f₁, то задана и любая равная ей функция f₂. Это накладывает некоторые естественные ограничения на классы функций, которые будут здесь рассматриваться. В частности, класс функций, обладающих определенными свойствами, будет рассматриваться только в том случае, если эти свойства инвариантны относительно операций введения и удаления фиктивных переменных.

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

п.6. Реализация функций формулами.
6.1. Формулы. Реализация функций формулами.
Как известно, в математическом анализе из «элементарных» функций можно составить формулы. Так и из «элементарных» булевых функций можно строить формулы.

Пусть X – некоторый фиксированный алфавит переменных, = - множество функциональных символов (базис) и  - множество булевых функций, соответствующих функциональным символам , т.е. являющиеся подмножеством множества функций P₂.