2.5.1. Реализации булевых функций. Контактные схемы

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

Пример. Схема для голосования. У каждого депутата имеется переключатель (кнопка) нажатием которой он голосует “за”. Условие: на выходе проходит сигнал только в том случае, когда больше половины депутатов проголосовали “за”.

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

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

Параллельное соединение контактов X и Y замкнуто тогда и только тогда, когда хотя бы один контакт замкнут. Поэтому параллельному соединению двух контактов X и Y, следует поставить в соответствие дизъюнкцию. Аналогично, последовательному соединению контактов X и Y соответствует конъюнкция Xy.

Описанное соответствие позволяет на данной контактной схеме построить с помощью операций ù , Ù и булеву функцию.

Схемы, состоящие их замыкающих и размыкающих контактов и допускающие их параллельные и последовательные соединения, называются “-схемами”.

Обратно, представив любую функцию в виде дизъюнктивной формы, по ней можно построить соответствующую “-схему”.

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

Пример 1. Проанализировать и упростить следующую схему:

Построим и упростим функцию, соответствующую схеме:

Полученной формуле соответствует следующая более простая схема:

Пример 2. Реализовать схему для голосования трех депутатов.

Построим функцию, описывающую условие принятия решения:

. Данной формуле соответствует схема:

< Предыдущая		Следующая >