Сопоставим каждой переменной v0, v1, … ее значение в множестве { 0, 1} . Определим значение терма Т при данных значениях переменных:
(а) если Т—переменная, то значение Т совпадает со значением этой переменной;
(б) если T = f (T1,…, Tn), а значения T1,…, Tn суть e 1,…, e п соответственно, то значение Т есть f(e1,…, e п).
Сопоставим каждой переменной v0, v1, … ее значение в множестве { 0, 1} . Определим значение терма Т при данных значениях переменных:
(а) если Т—переменная, то значение Т совпадает со значением этой переменной;
(б) если T = f (T1,…, Tn), а значения T1,…, Tn суть e 1,…, e п соответственно, то значение Т есть f(e1,…, e п).
Говорим, что п-местной функция g алгебры логики представима термом Т, если все переменные Тv1, …, vп и для любых значений переменных v1, …, vп значение терма Т совпадает со значением g(v1, …, vп). Говорим, что функция g есть суперпозиция функций f1,…, fn если g представима термом, все функциональные символы которого содержаться среди f1,…, fn. содержаться среди
Система функций G называется полной, если любая функция алгебры логики есть некоторая суперпозиция функций из G. Система функций G называется независимой, если никакая функция fG не представима суперпозициями функций из G\{f}. системы
Класс функций G называется замкнутым, если вместе с любыми функциями он содержит и все их суперпозиции. Замкнутый класс G называется предполным , если G¹ С1 и G не содержится ни в каком другом замкнутом классе, отличном от С1. Независимая система функций G называется базисомК, если всякая функция из К есть суперпозиция функций из G. замкнутого класса
Введем специальные обозначения для основных функций алгебры логики:
0(х) = 0, 1(х) = 1 для всех х, i(x) = x,
ù x = 
x*y= x & y = 
x È y = 
x + y= 
x É y = ù x È y , x º y = ù (x + y), x | y = ù (x*y).
Через С2 обозначается класс функций, удовлетворяющих условию f(1,1,…, 1) = 1, а через С3—класс функций, удовлетворяющих условию f(0,0,…, 0) = 0. L есть класс всех линейных функций, т.е. функций вида x1+ x2+…+xn + e , где e Î {0,1}. D есть класс самодвойственных функций, т.е. функций удовлетворяющих условию f(x1,…, xn) = ù f (ù x1,…, ù xn). Через М обозначается класс всех монотонных функций, т.е. функций, удовлетворяющих условию
x1£ y1,… , xn £ yn Þ f (x1,…, xn) £ f (y1,…, yn).
Будем интерпретировать функции алгебры логики как электрические цепи, содержащие двухпозиционные переключатели. (Рассматриваемые здесь цепи являются частным случаем так называемых релейно-контактных схем.) 1 интерпретируется как состояние переключателя “ток проходит”, а 0 – “ ток не проходит”, х—замыкающий контакт, ù х – размыкающий контакт, & -- последовательное соединение, È - параллельное. Две цепи считаются эквивалентными, если через одну из них ток проходит тогда и только тогда, когда он проходит через другую. Из двух эквивалентных схем более простой считается та, которая содержит меньшее число контактов.
Пусть f – функция алгебры логики от переменных а1,…,ак , представимая термом, в записи которого встречаются только связки &, È и ù . Обозначим через fÎ (x) формулу теории множеств, полученную из терма для f подстановками вместо переменных а1,…,ак соответственно выражений xÎ Z1,…, x Î Zk. Обозначим через Zf выражение, которое получается из терма для f заменой переменных ai символами Zi, символов &, È ,ù -- соответственно символами Ç , È , ¾ . При интерпретации Zf в теории множеств символы Zi будут обозначать подмножества универсального множества U.