Функцию типа f: Mn→M будем называть n — арной операцией на множестве М; n называется арностью операции f.
Алгеброй А называется совокупность множества М с заданными на нём операциями S={f11, f12,…, f1k, f21, f22, …, f2l, …, fn1, …, fnm}
A=, где М — называется основным или несущим множеством (или просто носителем) алгебры А. Вектор арностей алгебры называется её типом, совокупность операций S — сигнатурой алгебры.
Первый индекс у идентификатора операции указывает её местность. Для идентификации единого целого, содержащего объекты, которые имеют различное математическое строение, например множество операций в нём, было предложено использовать термин совокупность и обозначать его угловыми скобками.
В этой главе особую роль будет играть двухэлементное множество В и двоичные переменные, принимающие значения из В. Его элементы часто обозначаются 0 и 1, однако они не являются числами в обычном смысле. Наиболее распространённая интерпретация переменных — логическая: 1 — истинно, 0 — ложно. В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация фиксируется явно: например, в языках программирования (Паскаль и др.) вводится специальный тип переменной — логическая переменная, значения которой обозначаются true и false.
Алгебра, образованная множеством В вместе с всеми возможными операциями на нём, называется алгеброй логики. Функцией алгебры логики (или логической функцией) от n переменных называется n — арная операция на B. Множество всех логических функций обозначается P2, множество всех логических функций от n переменных – P2(n). Алгебра, образованная к — элементным множеством вместе со всеми операциями на нём, называется алгеброй к — значной логики, а n — арные операции на к — элементном множестве называются к — значными логическими функциями n переменных; множество всех к — значных функций обозначается Pk. Множество всех к — значных логических функций от n переменных обозначается Pk(n).
Всякая логическая функция n переменных может быть задана таблицей истинности, в левой части которой перечислены все 2n наборов переменных (т.е. двоичных векторов длины n), а в правой части — значения функций на этих наборах. Наборы, на которых функция f = 1, часто называют единичными наборами функции f, а множество единичных наборов — единичным множеством f. Соответственно наборы, на которых f = 0, называют нулевыми наборами f.
В таблице истинности наборы расположены в определённом порядке — лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Этим упорядочением будем пользоваться и в дальнейшем. При любом фиксированном упорядочении наборов логическая функция n-переменных полностью определяется вектор — столбцом значений функции, т.е. 2n. Поэтому мощность множества |P2(n)| т.е. число различных логических функций n переменных равно числу различных двоичных векторов длины 2n, т.е. N =.
Переменная xi в функции f(x1, x2, …, x(i-1), xi, x(i+1), …, xn) называется несущественной (или фиктивной), если f(x1, x2, …, x(i-1), 0, , x(i+1), …, xn) = f(x1, x2, …, x(i-1), 1, x(i+1), …, xn) при любых значениях остальных переменных, если изменение значения xi в любом наборе x1,…, xn не меняет значения функции.
В этом случае функция f(x1,…, xn) по существу зависит от n-1 переменной, т.е. представляет собой функцию g(x1, x2, …, x(i-1), x(i+1), …, xn-1) от n-1 переменной. Говорят, что функция g получена из функции f удалением фиктивной переменной xi, а функция f получена из g введением фиктивной переменной, причём эти функции по определению считаются равными. Например, запись f(x1, x2, x3)=g(x1, x2) означает, что при любых значения x1 и x2 f = g независимо от значения переменной x3.
Смысл удаления фиктивных переменных при минимализации функции очевиден, поскольку они не влияют на значения функции и являются с этой точки зрения лишними. Однако иногда бывает полезно вводить фиктивные переменные. Благодаря такому введению всякую функцию от n переменных можно сделать функцией большего числа переменных.
В частности, только это доказанное равенство |P2(n)|= справедливо при условии, что P2(n) содержит все возможные функции n переменных, в том числе и функции с фиктивными переменными.