8. ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ И СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ
Исследования, связанные с описанием работы комбинационных схем, появились в середине 30-х годов. Впервые возможность такого описания была рассмотрена К. Шенноном и В. И. Шестаковым в работах [5,6]. Они изучали схемы, построенные из контактов или переключателей. Такие схемы представляют собой в простейшем случае двухполюсную электрическую цепь, содержащую ряд контактов. Каждый контакт в цепи может находиться в замкнутом или разомкнутом состоянии. Пример такой электрической цепи приведен на рис.8.1.
Электрическая цепь может проводить или не проводить ток между внешними полюсами А и В. Можно говорить о проводимости такой цепи Y AB, которая является функцией положения контактов, образующих цепь. Функции, подобные проводимости контактной цепи, получили в дальнейшем название переключательных функций. Если обозначить контакты малыми латинскими буквами x с индексами, как это сделано на рис. 8.1, то можно записать:
Обозначим проводимость разомкнутого контакта символом 0, проводимость замкнутого контакта символом 1, а последовательное и параллельное соединение контактов знаками конъюнкции (∧ или &) и дизъюнкции (∨). В этом случае проводимость контактной цепи можно записать в виде формулы. Например, схеме, изображенной на рис. 8.1, соответствует формула:
По этой формуле можно вычислять проводимость цепи при различных значениях проводимостей контактов, полагая, что результат операции конъюнкции равен 1, когда оба операнда равны 1, а результат операции дизъюнкции равен 0, когда оба операнда равны 0.
Первые цифровые вычислительные машины практически были построены из контактных схем. Однако в современных машинах контактные схемы почти не используются по причине большого времени переключения. Современные ЭВМ строятся из быстродействующих транзисторных схем, которые называются логическими элементами. На вход логических элементов подаются, как правило, сигналы, имеющие два уровня, а на выходе элемента вырабатываются также сигналы с двумя уровнями. Такими сигналами могут быть, например, уровни напряжения +3 В и –3 В или 0 В и +5 В и т.п. Если обозначить один из уровней напряжения (например, низкий уровень) символом 0, а другой уровень 1, то работу логических элементов можно описывать с помощью формул, используемых в анализе контактных схем. Подобно последовательному и параллельному соединению контактов можно построить логические элементы, реализующие операции конъюнкции и дизъюнкции. Элемент, реализующий операцию конъюнкции (рис. 8.2, а), должен вырабатывать на выходе потенциал, соответствующий 1, только в том случае, когда оба входных потенциала соответствуют 1. Аналогично элемент, реализующий дизъюнкцию (рис. 8.2,б), создает на выходе потенциал, соответствующий 1, если хотя бы на один вход подается сигнал, соответствующий 1. Символическое изображение основных логических элементов и реализуемые ими функции приведены на рис.8.2, а, б.
Схемы, построенные из логических элементов, называются логическими схемами. Работа логических схем, так же как и работа контактных схем, может быть описана с помощью формул. Например, переключательной функции
соответствует схема из логических элементов, изображенная на рис.8.2,б.
Возможность описания контактных и логических схем с помощью формул является весьма ценной по двум причинам. Во-первых, по формулам гораздо удобнее проверять работу схемы, чем по рисунку. Во-вторых, выгода от использования формул заключается в том, что при задании условий работы схемы в виде формул процесс построения схемы, реализующей эти условия, становится весьма простым. Этот процесс заключается в том, что каждой операции конъюнкции (дизъюнкции) ставится в соответствие либо последовательное (параллельное) соединение контактов, либо соответствующий логический элемент. При этом оказывается, что число элементов, образующих схему, или число последовательных и параллельных соединений определяется числом знаков операций в формуле, задающей работу схемы. Существует ряд алгебраических преобразований, в результате которых удается получить формулы, эквивалентные заданным, с меньшим числом знаков операций. Использование таких преобразований позволяет строить более простые схемы с меньшим числом элементов.
Общим свойством логических и контактных схем является то, что выходной сигнал схемы (проводимость цепи) в каждый момент времени определяется только комбинацией входных сигналов, действующих в рассматриваемый момент времени, и не зависит от сигналов, присутствовавших на входе в предшествующие моменты времени. Схемы, обладающие таким свойством, называют комбинационными схемами.
Математический аппарат для описания работы и преобразования алгебраических выражений комбинационных схем в дальнейшем получил название алгебры переключательных функций, которая, в свою очередь, является частным случаем более общей математической системы, называемой дистрибутивной решеткой с дополнениями или алгеброй Буля.
В данном разделе излагаются алгебраические основы теории переключательных функций (ПФ). Основное внимание при этом уделяется алгебраическому объекту, называемому решеткой, поскольку алгебра ПФ является одной из интерпретаций дистрибутивной решетки с дополнениями. Изучение свойств решеток позволяет выполнить ряд эквивалентных преобразований, которые затем могут быть использованы в алгебре ПФ.