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

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

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

(2.4)

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

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

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

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

(2.5)

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

(2.6)

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

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

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

Розв'язання. Використовуючи тотожність (1.8) відносно , маємо:

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

У результаті визначаємо:

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

Дата добавления: 2014-01-07