5.1 Упрощение логических выражений.
Строиться на основе теорем алгебры и логики
1.Закон нулевого множества:
0 v x = x;
0 & x = 0;
0 & x1 & x2 &... & xn &... = 0.
2.Закон универсального множества:
1 & x = x;
1 v x = 1;
1 v x1 v x2 v... v xn v... = 1.
3.Закон повторения:
x & x = x;
x v x = x.
4.Закон двойной инверсии: --х = x.
5.Законы дополнительности:
а) исключенного третьего x v x = 1.
б) логическое противоречие x & x = 0.
6.Коммутативный (переместительный) закон: x & y = y & x; x v y = y v x.
7.Ассоциативный (сочетательный) закон:
x&(y&z) = (x&y)&z = x&y&z;
x v (yvz) = (xvy) v z = x v y v z.
8.Дистрибутивный (распределительный) закон:
x&(y v z) = x&y v x&z;
x v y&z = (x v y)&(x v z).
9.Законы поглощения:
x & (x v y) = x;
x v x&y = x.
x & (x v y) = x & y;
x v x&y = x v y.
10.Законы склеивания:
а) полного
x&y v x&y = x;
(x v y)&(x v y) = x.
б) неполного
x&y v x&y = x v x&y v x&y;
(xvy)&(xvy) = x&(x v y)&(x v y).
11.Законы инверсии (теоремы де Моргана):
x1&x2&... &xn = x1vx2v... vxn;
x1vx2v... vxn = x1&x2&... &xn.
12.Теоремы разложения (декомпозиции ЛФ):
f (x,y,...,z) = x& f (1,y,...,z) v x& f (0,y,...,z); (1.16a)
f (x,y,...,z) = (xv f (0,y,...,z))&(xv f (1,y,...,z)). (1.16b)
13.Теорема Шеннона (обобщение теорем де Моргана):
f (x,y,...,z,&,v)=f (x,y,...,z,v,&).
Данная теорема утверждает, что инверсия любой функции в АЛ получается путем замены каждой переменной ее инверсией и одновременно взаимной заменой символов конъюнкции и дизъюнкции.