Контактные схемы. Другая замечательная алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции

Алгебра Жегалкина

Другая замечательная алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина по имени предло­жившего ее советского ученого. Непосредственной проверкой по таблицам соответствия устанавливаются следующие основные свой­ства этой алгебры:

- коммутативность х + у = у + х; ху = ух;

- ассоциативность х + (у + z) = (х + у) + z; х(уz) = (ху)z;

- дистрибутивность умножения относительно сложения х(у + z) = ху + хz;

- свойства констант.;;

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

- закон приведения подобных членов при сложении х + х =0;

- закон идемпотентности для умножения хх = х.

Таким образом, в формулах алгебры Жегалкина, как и в буле­вой алгебре, не могут появляться коэффициенты при переменных и показатели степени. С помощью табл. 8.1 выводятся также следую­щие соотношения:

Первые два тождества позволяют перейти от любой формулы булевой алгебры к соответствующей ей формуле алгебры Жегал­кина, а с помощью третьего тождества осуществляется обратный переход.

Пример.

Через операции алгебры Жегалкина можно выразить все другие булевы функции:

.

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

Действительно, если привести данную функцию к совершенной нормальной форме и заменить все дизъюнкции через суммы по модулю 2, а отрицание переменных представить в соответствии с тождеством, то после раскрытия скобок получим некоторое алгебраическое выражение. Оно приводится к канониче­скому многочлену на основе соотношений х + х = 0 и хх = х. Такое представление всегда возможно и единственно (с точностью до по­рядка расположения членов).

Пример.

(1 + х + у) (1 + ху) + (х + ху) у = 1 + х + у + ху + хху + уху + ху + хуу =

= 1 + х + у + ху + ху + ху + ху + + ху = 1 + х + у + ху.

Преимущество алгебры Жегалкина состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций, используя опыт преобразования обычных алгебраических выраже­ний. Ее недостаток по сравнению с булевой алгеброй - сложность формул, что особенно сказывается при значительном числе перемен­ных, например:

х Ú у Ú z = х + у + z + ху + хz + уz + хуz.

10.1. Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей х ₁ и x ₂. Ключи управляются кнопками с двумя состояния­ми: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается. Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т. е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим через и.

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х ₁ и x ₂,а со­стояние лампочки - со значением функций этих переменных.

Операции отрицания соответствует схема с одним нормально замкнутым ключом (рис. 10.1а). Если кнопка нажата (х = 1), ключ разомкнут и лампочка не горит, т. е. f(x) = 0; при отпущенной кнопке (х = 0) ключ замкнут и лампочка горит, т. е. f(x) = 1. Операциям дизъюнкции и конъюнкции соответствуют схемы с двумя нормально разомкнутыми ключами (рис. 10.1б, в).Легко убедиться, что в схеме рис. 1б лампочка горит при нажатии хотя бы одной из кнопок, а в схеме рис. 1в - только при нажатии обеих кнопок одновременно.

Рис. 10.1 – Элементарные контактные схемы

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

Рис. 10.2 - Контактная схема до и после упрощения

В реальных устройствах используются ключи различной кон­струкции и физической природы (механические, электромагнитные, электронные, гидравлические, пневматические и т. д.). Однако при реализации логических функций многие технические особенности не имеют значения. Существенными свойствами контактных схем являются исходные положения ключей (нормально разомкнуты или нормально замкнуты) и способ их соединения между собой и внешними устройствами. Эта информация полностью отображается графом, ребра которого соответствуют ключам, а вершины - точкам их соединения. Ребра нормально разомкнутых ключей обозначаются соответствующей переменной (х), а нормально замкнутых - отрицанием переменной (). Например, контактная схема (рис. 10.2б)изображается графом, как показано на рис. 10.3а. При изображении контактных схем графами принимаются неко­торые специфические условия и упрощения. Обычно переменные обозначаются в разрывах линий, изображающих ребра. При этом ребрами считаются только такие линии, которые обозначены какой-либо переменной или ее отрицанием. Другие линии, не являющиеся ребрами графа, могут изображать входы и выходы схемы, связи с другими схемами и т. п. Кроме того, вершины второй степени могут не изображаться, так как им инцидентны пары последовательно соединенных ребер, из которых каждое обозначено соответствующей переменной. На рис. 10.3бпоказана контактная схема в обычно принятом виде.

Рис. 10.3 – Граф контактной схемы

10.2. Контакты. Как уже отмечалось, любую булеву функцию можно реализовать схемой, состоящей из последова­тельно и параллельно соединенных ключей. Каждый такой ключ может находиться в двух состояниях — разомкнут (0) и замкнут (1), а переход из одного состояния в другое осуществляется каким-либо управляющим органом.

В электрических цепях роль ключей играют многочисленные устройства, предназначенные для коммутации (замыкания и размыкания): выключатели, электромагнитные реле, телеграфные ключи, электронные ключевые схемы и т. п. Обычные выключатели, телеграфные ключи и подобные им устройства управляются рукой человека. Состояние электромагнитного реле изменяется под воз­действием электрического тока, протекающего по обмотке катушки. Ключом в широком смысле является всякое устройство, способное принимать только одно из двух возможных состояний: механические защелки, дверные замки, рычаги управления, желез­нодорожные светофоры и т. п. Более того, двузначную переменную, независимо от ее конкретного смысла, можно рассматривать, как ключ, состояние которого соответствует значению этой переменной. В рамках общей теории целесообразно отвлечься от конструктивных и специфических особенностей ключевых объектов и интерпретировать ключ как отрезок проводника с контактом, который может быть разомкнут или замкнут. Разомкнутое состояние контакта отождествляется с нулем, а замкнутое - с единицей.

Замыкающие (нормально разомкнутые) контакты обозначаются х_i, размыкающие (нормально замкнутые) контакты — через. При управляющем воздействии контакт меняет свое состояние: нормально разомкнутый контакт замыкается, а нормально замкнутый - размыкается. В зависимости от своего состояния контакты пропускают электрический ток или препятствуют его прохождению.

Процессы переключения в реальных устройствах занимают некоторое, иногда довольно большое время. Однако во многих задачах время переключения можно не учитывать, считая, что кон­такты переходят из одного состояния в другое мгновенно.

10.3. Анализ контактных схем. Задача анализа контактной схемы состоит в построении соответствующей ей булевой функции. Для параллельно-последовательных схем эта задача решается на основе того, что параллельное соединение контактов соответствует дизъюнк­ции, а последовательное соединение — конъюнкции переменных, которыми эти контакты обозначены в схеме. Например, для двух­полюсной контактной схемы (рис. 10.4)

Рис. 10.4

Если схема (или ее часть) имеет произвольную структуру, то ее анализ проводится путем выделения всех путей между входным и выходным полюсами схемы. Каждый такой путь представляется конъюнкцией переменных входящих в нее контактов, а вся схема — дизъюнкцией этих конъюнкций. Например, для мостиковой схемы (рис. 10.5)

Рис. 10.5

10.4. Синтез контактных схем. При построении контактной схемы по заданной булевой функции (задача синтеза) исходная функция может быть задана как логической формулой, так и таблицей. В обоих случаях прежде всего необходимо выразить функции через операции конъюнкции, дизъюнкции и отрицания. Каждая опера­ция конъюнкции соответствует последовательному соединению контактов, а операция дизъюнкции — параллельному соединению. В результате получаем последовательно-параллельную контактную схему.

Пусть, например, функция задана таблицей соответствия, приве­денной ниже.

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

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

Этому выражению соответствует схема рис. 10.6б, которая со­держит на два контакта меньше. Еще проще мостиковая схема (рис. 10.5), которая реализует ту же функцию.

Рис. 10.6

Центральной проблемой синтеза является построение наиболее простой или в каком-то смысле оптимальной схемы. Часто эта проблема сводится к минимизации булевых функций, т. е. к такому их представлению, в котором соответствующие формулы содержат минимальное количество вхождений переменных. Проблема опти­мального синтеза еще далека от полного решения, но разработан­ные методы позволяют существенно упрощать формулу и схемы, а в сравнительно простых случаях получать и оптимальные схемы.