Функции алгебры логики.

Определение. Алгебра, образованная множеством вместе со всеми возможными операциями на нём, называется алгеброй логики.

Определение. Функцией алгебры логики (логической функцией) называется арная операция на множестве .

Первый термин является более точным, однако второй более распространён, особенно в приложениях. Он и будет использоваться в дальнейшем. Итак, логическая функция - это функция, принимающая значения 0 или 1. Множество всех логических функций будем обозначать , множество всех логических функций переменных - .

Определение. Алгебра, образованная элементным множеством вместе со всеми операциями на нём, называется алгеброй значной логики, а арная операция на элементном множестве называется значной логической функцией.

Множество всех значных логических функций обозначается . Мы в дальнейшем будем рассматривать логические функции только из .

Всякая логическая функция переменных может быть задана таблицей, в левой части которой перечислены все наборы значений переменных (которых всего ), а в правой части – значение функции на этих наборах значений. Ниже приведена таблица, задающая некоторую функцию трёх переменных.

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

Таблица 1.

Заметим, что наборы в таблице расположены в определённом порядке – лексикографическом, который совпадает с возрастанием наборов, если рассматривать их как двоичные числа. Этим упорядочением будем пользоваться в дальнейшем. При любом фиксированном упорядочении наборов логическая функция переменных полностью определяется вектор-столбцом значений функции, то есть . Поэтому число различных функций переменных равно числу различных двоичных векторов длины .

Определение. Переменная в функции называется несущественной (фиктивной), если при любых значениях остальных переменных.

Иначе говоря, переменная считается несущественной, если изменение её значения в любом наборе не изменяет значения функции. В этом случае функция по существу зависит от переменной, то есть представляет собой некоторую функцию от переменной. Говорят, что функция получена из функции удалением фиктивной переменной или, наоборот, что функция получена из функции добавлением фиктивной переменной. Например, запись означает, что при любых значениях выполняется независимо от значения .

Практический смысл удаления фиктивных переменных очевиден, поскольку они не влияют на значение функции и являются с этой точки зрения лишними. Однако иногда бывает полезно вводить фиктивные переменные. Благодаря такому введению можно всякую функцию переменных сделать функцией любого большего числа переменных. Поэтому любую конечную совокупность функций можно считать зависящей от одного и того же множества переменных (которое является объединением множеств переменных всех взятых функций).