1.6.4. Теорема Шенона

Широке використання при перетворенні логічних функцій знаходять теорема Шенона та ряд тотожностей, які витікають з неї.

Теорема Шенона формулюється так: будь-яку функцію n зміних можна зобразити в формі:

.

(1.17)

Теорема Шенона виявляється дуже корисною при виконанні перетворень логічних виразів, що містять операцію ВИКЛ. АБО.

Приклад 1.26. Виконати перетворення логічної функції:

.

Розв’язання. Використовуючи теорему Шенона, виконаємо наступний ряд перетворень:

З теоремою Шенона (1.17) пов’язані тотожності:

(1.18)

Виходячи з теореми де Моргана, тотожностям (1.18) відповідають наступні тотожності:

(1.19)

Тотожності (1.18) і (1.19) широко використовуються для спрощення логічних виразів. З них витікають формули, які широко використовуються:

Приведені тотожності дають можливість суттєво спрощувати складні функції багатьох змінних, особливо при наявності заперечень.

Приклад 1.27. Спростити логічну функцію:

.

Використовуючи тотожність (1.18) відносно , маємо:

З тотожності (1.19) знаходимо:

.

В результаті знаходимо:

.

Приведені вище тотожності використовуються для того, щоб розкладати складні логічні функції на більш прості.

1.6.5. Розкладання Ріда

Широке використання знаходить також інший тип розкладання функцій – розкладання Ріда. Воно базується на використанні наступної умови: якщо , то .

Дійсно,

.

Це дає можливість розкладання Шенона

,

де

; ,

зобразити у вигляді:

Отриманий вираз називається розкладанням Ріда. Воно дає можливість будь-яку функцію n змінних зобразити у вигляді полінома n-го ступеня виду:

де а₀ , b₁ , b₂ , … – коефіцієнти ряду Ріда.

Так, наприклад, функція двох змінних може бути записана у вигляді:

.

Якщо функція описується поліномами першого ступеня, вона називається лінійною. Для таких функцій коефіцієнт при логічних добутках змінних дорівнює нулю. У такому випадку для функції двох змінних можемо записати:

,

а для функції з кількістю змінних n

.

Приклад 1.28. Зобразити функцію

у вигляді лінійного полінома.

Розв’язання. Виконуючи перетворення, знаходимо:

У цифрових пристроях, які реалізують ті чи інші логічні функції, сигнали здебільшого розділяються за функціональним призначенням – наприклад, інформаційні, адресні, керуючі – і, відповідно, мають свої умовні позначення. Це дає можливість за виглядом логічних функцій чітко бачити особливості взаємодії між сигналами, взаємозалежність між ними. Деякі приклади таких функцій:

Приведені функції описують роботу простих мультиплексорів. Як буде зрозуміло з подальшого матеріалу (Розділ III), коефіцієнти а₀  і а₁ є також логічними змінними, які мають інше функціональне призначення.

У той же час, остання функція може бути представлена у вигляді:

,

де b₁…b₄ – коефіцієнти, функціонально залежні від a₀ і a₁ .

У якості логічних сигналів можуть використовуватись функції. У такому випадку описана логічна функція реалізує функціональний комутатор.