Элементарные функции алгебры логикиОбозначения: E 2={0, 1}; Е Определение 1. Функцией алгебры логики называется закон, осуществляющий отображение Е Так как множество Е Пример 1. Пусть n =2, тогда Е Тем самым задана функция, для которой мы будем использовать стандартное обозначение f (x 1, x 2), записывая эту функцию в виде таблицы:
Здесь x 1 и x 2 обозначают названия столбцов, а f – символ, обозначающий отображение. Следует обратить внимание, что функции f (x 1, x 2) и f (y 1, y 2) задают одно и то же отображение, и их таблицы отличаются только названиями столбцов. Определение 2. Таблица, задающая функцию f (x 1, x 2,..., xn), называется таблицей истинности для этой функции. Рассмотрим функции одной переменной. Их будет всего 4, они задаются следующими таблицами истинности:
функция называется константой 0, записывается f 0(x)
функция называется тождественной, записывается f 1(x)= x;
функция называется «не x» и записывается f 2 (x)=
функция записывается f 3(x) Рассмотрим функции двух переменных f (x 1, x 2). Функции двух переменных определены на множестве Е
Некоторые из этих функций носят специальные названия и играют такую же роль, как элементарные функции в анализе, поэтому называются элементарными функциями алгебры логики. Перечислим их. 1) f 1(x 1, x 2) = (x 1& x 2), читается «конъюнкция х 1 и х 2», иногда вместо знака & употребляют знак 2) f 6(x 1, x 2) = (x 1Å x 2) – сложение х 1 и х 2 по модулю два, иногда пишут (х 1+ х 2) mod 2. 3) f 7(x 1, x 2) = (x 1Ú x 2), читается «х 1 дизъюнкция х 2», она совпадает с max(x 1, x 2), ее называют логическим сложением. 4) f 8(x 1, x 2) = (x 1 5) f 9(x 1, x 2) = (x 1~ x 2), читается «х 1 эквивалентно х 2». 6) f 13(x 1, x 2) =(x 1 7) f 14(x 1, x 2) = (x 1| x 2), читается «х 1 штрих Шеффера х 2», она является отрицанием конъюнкции. Cимволы Рассмотрим функции f (x 1... xn), где (x 1... xn)Î Е С ростом n число Р 2(n) быстро растет: P 2(1)=4, P 2(2)=16, P 2(3)=256, P 2(4)=65536. При больших n табличный способ задания функций становится неприемлемым, используется формульное задание функций. Но прежде чем ввести понятие формулы, дадим определение существенной переменной. Определение 3. Функция f (x 1,..., xi –1, xi, xi +1,..., xn) существенно зависит от хi, если существуют такие значения a 1,... ai –1, ai +1,... an переменных x 1,... xi –1, xi +1,... xn, что f (a 1,... ai –1, 0, ai +1... an)¹ f (a1... ai –1, 1, ai +1... an). Тогда переменная хi называется существенной переменной. В противном случае хi называется фиктивной переменной.
|
= E 2´ E 2´...´ E 2 – прямое произведение n сомножителей; (x 
,.., xn)Î E 2, | E 2| – мощность E 2, | E 2|=2, тогда | Е 
E 2, причем отображение всюду определено и функционально.
конечно, то задать отображение Е 
={(0 0), (0 1), (1 0), (1 1)}, отображение Е 
0;
;
E 2|=4. Для удобства функции пронумерованы так, что двоичный код номера совпадает с набором значений функции.
. Следовательно, число функций двух переменных равно 24=16, занумеруем их числами от 0 до 15 так, чтобы двоичный код номера совпадал с набором значений функции.
или вообще его опускают, пишут (х 1 х 2). (х 1& х 2) совпадает с обычным произведением х 1 х 2 и совпадает с min(x 1, x 2). Эту операцию называют также логическим умножением.
x 2), читается «х 1 стрелка Пирса х 2» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.
x 2), читается «х 1 импликация х 2», иногда обозначается (х1É х2), т. е. х1 влечет х2.
, &, Ú, 
