Разложение Шеннона
Разложения функций по переменным
Законы алгебры логики
1. Законы коммутативности:
a Ù b = b Ù a, a Ú b = b Ú a.
2. Законы ассоциативности:
a Ù (b Ù с) = (а Ù b) Ù с, a Ú (b Ú с) = (а Ú b) Ú с.
3. Законы дистрибутивности:
a Ù (b Ú с) = (а Ù b) Ú (а Ù с), a Ú (b Ù с) = (а Ú b) Ù (а Ú с).
4. Законы идемпотентности:
а = a Ù а, a = а Ú a.
5. Законы нуля и единицы:
a Ù ù а = 0, а Ù 1 = а, a Ú ù а = 1, а Ú 0 = а.
6. Законы де Моргана:
ù (a Ú b) = ù a Ù ù b, ù (a Ù b) = ù a Ú ù b.
7. Законы поглощения:
a Ú (а Ù b) = а, a Ù (a Ú b) = а.
8. Законы склеивания:
(а Ú ù b) Ù (а Ú b) = а, (а Ù ù b) Ú (а Ù b) = а.
9. Закон двойного отрицания:
ù ù а = а.
Не все законы независимы друг от друга. Так, например, закон идемпотентности можно получить из закона поглощения с использованием законы дистрибутивности:
а = a Ú (а Ù b) = (a Ú а) Ù (а Ú b) = (a Ù (а Ú b)) Ú (a Ù (а Ú b)) = а Ú а.
Закон поглощения может быть выведен из закона нуля и единицы:
a Ú (а Ù b) = (a Ù 1) Ú (а Ù b) = a Ù (1 Ú b) = a Ù 1 = а.
Закон идемпотентности относительно дизъюнкции непосредственно выводится из законов нуля и единицы:
a Ú а = (a Ú а) Ù 1 = (а Ú а) Ù (ù а Ú а) = а Ú (ù а Ù а) = а Ú 0 = а.
При доказательствах логических выражений нужно всегда учитывать принцип двойственности. Так, вышеперечисленная цепочка равенств для закона поглощения может быть представлена следующим образом:
a Ù (а Ú b) = (a Ú 0) Ù (а Ú b) = a Ú (0 Ù b) = a Ú 0 = а.
Т.о. в качестве независимой системы законов можно выбрать законы: коммутативности, ассоциативности, дистрибутивности, нуля и единицы.
Введем следующие обозначения:
х0 = ù х; х1 = х.
Пусть s - параметр, равный 0 или 1.
Тогда: хs = 1, если х = s;
хs = 0, если х ¹ s.
Теорема Шеннона: всякая логическая функция F (х1, … ,хn) может быть представлена в виде:
F (х1, … , хm, хm+1, … , хn) = 
x1s1… xmsm F (s1, … ,sm, хm+1, … , хn), (2.1)
где m £ n, а дизъюнкция берется по всем 2mнаборам значений переменных х1, … , хm.
Это равенство называется разложением по переменным х1, … , хm.
{Пример: n = 4, m = 2.
Разложение будет иметь вид:
F (х1, х2 , х3 , х4) = ù х1 ù х2 F (0, 0 , х3 , х4) Ú ù х1 х2 F (0, 1 , х3 , х4) Ú
Ú х1 ù х2 F (1, 0 , х3 , х4) Ú х1 х2 F (1, 1 , х3 , х4).
Доказательство.
Производим подстановкой в обе части (2.1)произвольного набора (s1, … , sm, sm+1, …, sn) всех n переменных.
Т.к. хa = 1 только тогда, когда х = a, то среди 2 m конъюнкций x1a1… xmam правой части (2.1)в единицу обратится только одна, в которой a1 = s1, … , am = sm. Все остальные конъюнкции равны 0. Поэтому получим:
F (s1, … , sn) = s1s1… smsm F (s1, … , sm, sm+1, … , sn) = F (s1, … , sn).
Особое значение на практике имеет случай, когда m = n, т.е. разложение функции n переменных по n переменным:
F (х1, … ,хn) = 
x1s1… xnsn.
Т.е. все переменные в правой части (2.1)получают фиксированное значение и функции в конъюнкциях правой части становятся равными 0 или 1. Т.о. дизъюнкция берется по всем наборам (s1, … , sn), на которых F = 1. Такое разложение называется СДНФ – совершенной дизъюнктивной формой функции F. СДНФ содержит ровно столько конъюнкций, сколько единиц в таблице истинности для F. Каждому единичному набору (s1, … , sn) соответствует конъюнкция всех переменных, в которой хi взято с отрицанием, если si = 0, и без отрицания, если si = 1. Такие конъюнкции называются конституентами единицы.}