3 Суперпозиция функций
Нами рассмотрены одиннадцать элементарных функций: Const 0, Const 1, повторение, конъюнкция, дизъюнкция, сумма по mod2, стрелка Пирса, штрих Шеффера, эквиваленция, импликация, отрицание. С помощью метода суперпозиции элементарных функций, можно получать более сложные функции от любого числа переменных, применяя различные композиции.
3.1 Методы суперпозиции
К основным методам суперпозиции относятся:
-метод перенумерации аргументов;
-метод подстановки в функцию новых функций вместо аргументов.
К методам перенумерации аргументов можно отнести, например, функцию x2 → x1, являющуюся суперпозицией функции импликации x1 → x2.
Рассмотрим таблицу 2.4. Каждому i-му кортежу можно поставить в соответствие терм Тi составляющий некоторое множество G функций алгебры логики. Каждой функции из G сопоставим функциональный символ Y. Пусть Х1, Х2,...,Хn счетное множество символов называемых переменными.
Определим понятие терм как:
-переменная есть терм;
-если Y функция из G и Т1, ... ,Тm - термы, то Y(Т1, …,Тm) также терм.
Других определений термов нет.
Определим значение терма Т при значениях переменных Х1, Х2,...,Хn из множества{0,1}:
-если Т переменная, то значение Т совпадает со значением этой переменной;
-если T=Y(T1,...,Tm), а значения T1,...,Tm суть E1,..,Em соответственно, то, значение Т есть f(E1,...,Em), где E1,...,Em конкретное значение переменных функции из {0,1} для конкретного кортежа переменных.
Функция g есть суперпозиция функций y1,y2,…,ym если g представлена термом, все функциональные символы которого содержатся среди y1,y2,…,ym.
Например:
x2;
x1x2
x1
.
Существует и другое эквивалентное определение.
Функцию, полученную из функций y1,y2,…,ym путем применения (возможно многократного) следующих правил:
-перенумерации аргументов;
-подстановки в функцию новых функций вместо аргументов - будем называть суперпозицией функций y1,y2,...ym.
Имея, например, из таблицы для двух переменных элементарные функции: отрицания, конъюнкции, дизъюнкции, эквивалентности и импликации, можно составить следующие новые функции алгебры логики, являющиеся суперпозициями этих функций:
x2→
;
x1
;
x1x2
x1;
(x1
x2)→
;
Используя таблицы, определяющие элементарные функции, можно задавать любую функцию алгебры логики, являющуюся суперпозицией этих функций, соблюдая при этом приоритет скобок {[( )]}.
Например:
f(x1,x2,x3)={[( ~x3) (x1↓x2)](x1 x2)}→x3.
3.2 Выражение одних элементарных функций через другие
Анализ таблицы функций для одной и двух переменных показывает, что между функциями имеются зависимости
yi
=
3-i,
где i = 0, 1,2,3;
(3.1)
yi
=
15-i,
где i = 0, 1, ... ,15.
На основании этих зависимостей можно записать соотношения, выражающие одни элементарные функции через другие. Для подтверждения равносильности полученных равенств, можно использовать таблицы истинности. Непосредственно по формулам 3.1 устанавливаем следующие равенства, которые в дальнейшем будем широко применять.
Для одной переменной:
0 =
;
1 =
;
х =
.
(3.2)
Для двух переменных:
x1x2
=
;
x1
← x2
=
;
(3.3)
x1
x2
=
;
x1+x2
=
;
x1
/ x2
=
;
x1
→ x2
=
;
(3.4)
или
x1
~ x2
=
;
x1
↓ x2
=
.
По таблицам соответствия (истинности) можно доказать следующее равенство, получившее наибольшее распространение.
x1
→ x2
=
+x2;
x1
~ x2
= (
+
x2)(
x1
+
).
Из подстановки в 3.3 последнего равенства (эквиваленции) получим:
x1
x2
=
;
(3.5)
x1+
x2
=
;
x1x2
=
.
(3.6)
Как обобщение 3.6 получаем следующие формулы, названные правилом де Моргана:
x1+x2
+x3+…+
xn
=
;
(3.7)
x1x2x3
·…· xn
=
.
(3.8)
Закон де Моргана построен на принципе двойственности.
Определение: логическое сложение n-переменных равно отрицанию логического умножения отрицаний этих переменных.
Логическое умножение n-переменных равно отрицанию логического сложения отрицаний этих переменных.
Операции + и & являются взаимно двойственными.
Для лучшего усвоения правила де-Моргана важно запомнить следующее:
логический знак между переменными изменяется, а черта общего отрицания делится на все переменные.
,
.
Если теперь над левой и правой частями уравнений поставить общее отрицание, что не изменит знак равенства, то получим следствие правила де-Моргана
,
.
Учтя взаимно уничтожающие двойные отрицания, получим то же определение
,
.
Это можно записать в более сокращенном виде как обобщенный закон дуальности (закон де-Моргана –Шеннона), который выражается:
=
, 
=
,
=
, 
=
.
Правило де Моргана и его следствие широко используется в аналитических преобразованиях логических функций при их минимизации.