Логика - доступно для всех

      Функцию типа 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 переменных, в том числе и функции с фиктивными переменными.