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

В теории переключательных функций особо важное значение имеет теорема разложения Шеннона: любую функцию можно разложить по переменной в форме

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

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

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

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

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

Приведем доказательство дистрибутивного закона (1.21) для операции сумма по модулю два относительно операции конъюнкции:

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

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

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

Пусть требуется упростить функцию

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

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

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

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

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

Далее легко получить, что

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

Результат получился также простым, но за счет вынесения общего члена за скобки. Цель приведенного преобразования состояла в исключении инверсных сигналов х и у.

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

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

Инверсные мультиплексные функции, соответствующие (1.34) и (1.35), определяются выражениями:

Истинность данных соотношений легко доказывается с помощью теоремы разложения (1.29) по переменным

Представление переключательных функций в форме (1.34) или (1.35) часто позволяет лучше понять их практическое назначение. Например, разложим функцию по переменным

Полученная функция описывает функциональный коммутатор, называемый функциональным мультиплексором, так как производится коммутация не только самих информационных сигналов , но и некоторых функций от них Понятие функциональных мультиплексоров имеет особое значение для аналитического описания интегральных микросхем. Например, выпускается 4-разрядный функциональный мультиплексор 1561КП4, реализующий функции

где управляющие сигналы, и входные информационные сигналы, выходные сигналы,

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

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

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

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

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

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

получим

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

Аналогично можно показать, что любую функцию переменных можно представить в виде полинома степени. В таком представлении функций используются только операции и константа или 1. Функции, описываемые полиномом первой степени, называются линейными. Так, любая линейная функция двух переменных, как это следует из (1.37), представляется выражением

Из трех двоичных коэффициентов можно составить восемь комбинаций их значений, поэтому, как это следует из (1.38), имеется восемь различных линейных функций двух переменных:

Линейные функции переменных описываются полиномом первой степени

(здесь коэффициенты не являются значениями функции в точках ).