1.4 Теоремы разложения

Теорема разложения К. Шеннона

Любую функцию можно разложить по переменнойв форме

(1.28)

Эта теорема легко доказывается методом перебора:

т.е. при получено явное тождество, следовательно, теорема справедлива независимо от значения других переменных;

т.е. при тоже получено явное тождество, а значит, теорема справедлива независимо от других значений переменных. Из этого следует, что теорема истинна для любых значений переменных.

По принципу двойственности получаем вторую теорему разложения

(1.29)

Теорема (1.29) является удобным инструментом для преобразования логических выражений, содержащих операцию сумма по модулю два, так как в ряде практических случаев свести данную операцию к простейшим, например, проведя разложение по переменной , можно упростить следующее выражение:

С теоремой разложения (1.28) связаны тождества

(1.30)

По принципу двойственности этим тождествам соответствуют двойственные тождества

(1.31)

Тождества (1.30) и (1.31) является мощным средством упрощения логических выражений. Пусть необходимо упростить функцию

Используя первое из тождеств (1.30) относительно , получим

Для упрощения выражения можно использовать второе из тождеств (1.31), тогда

По принципу подстановки можно записать

(1.32)

Соотношения (1.32) позволяют повысить эффективность аналитических методов упрощения логических выражений. К примеру, следует упростить функцию

Обозначим , тогда

Далее следует, что

С практической точки зрения переменные, являющиеся аргументами переключательной функции, можно разделить на два типа:- информационные и- управляющие. Функциии, имеющие по переменнымразложения

(1.33)

(1.34)

называются мультиплексными функциями. Такие функции описывают коммутаторы сигналов, так как для каждой комбинации управляющих сигналов функция принимает значение одного из информационных сигналов. Данные коммутаторы называютмультиплексорами(Multiplexers).

Рассмотрим другой вид разложения функций – разложение Рида. Если , то. Действительно,. Поэтому разложение Шеннона

где примет вид:

Полученное выражение

(1.35)

называют разложением Рида.

Выполним разложение Рида функции по двум переменным:

_где

. Введя обозначения

получим

(1.36)

Данное выражение представляет собой полином второй степени от переменных

Аналогично можно показать, что любую функцию nпеременных можно представить в виде полиномаn – ой степени. При таком представлении функций используются только операции &, сумма по модулю два, + и константы 0 и 1. Функции, описываемые полиномом первой степени, называютсялинейными. Так любая линейная функция двух переменных, как следует из (1.36), представляется выражением

(1.37)