Класс линейных функций и его замкнутость относительно суперпозиции

Определение: Арифметические функции в алгебре логики есть сложение и умножение по модулю 2.

Следующие свойства математических операций проверяются непосредственно.
1) x+(y+z) = (x+y)+z
2) x+y=y+x
3) x+0=x
4) x+(-x) = 0
5) x(yz) = (xy)z
6) xy = yx
7) x*1 =x
8) x*x-1 =1, x≠0
9) x(y+z) = xy+xz
10) x+x=0
11) x*x =x (идемпотентность)

Замечание: Двухэлементное множество {0,1} с определенными на нем операциями сложения и умножения по mod 2 образуют поле F.

Замечание: Поле F (по свойству 10) имеет характеристику 2, а операция умножения идемпотентна. Следующие 4 равенства устанавливают связь между арифметическими и логическими операциями.

1) ¬x=x+1
2) x&y = x*y
3) x*y = ¬(¬x&¬y) = (x+1)(y+1)+1 = xy+x+y +1+1 = xy+x+y
4) x+y = ¬xy∨x¬y (СДНФ)

Теорема: Класс линейных функций замкнут относительно суперпозиции.

Доказательство: Пусть линейная функция f(x1, x2,…,xn) = a1x1 + a2x2+…+anxn+an+1, а также функции
gi(x1, x2,…,xm) = bi1x1 + bi2x2+…+binxn+bim+1, i=1,2,..n
Тогда их суперпозиции:
f(g1, g2, …, gn)=a1(b11x1+b12x2+…+b1mxm+b1m+1xm,)+a2(b21x1+b22x2+…+b2mxm+b2m+1)+
…+an(bn1x1+bn2x2+…+bnmxm+bnm+1)+an+1 =
={сгрупируем по столбцам } =
= (b11a1+b12a2+…+bn1an)x1+(b12a1+b22a2+…+bn2an)x2 +…+(b1ma1+b2ma2+…+bnman)xm+
+(b1m+1a1+…+bnm+1an)+an+1 = c1x1 + …+ cmxm + cm+1 — линейная функция.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru