Приложения алгебры логики в технике

Лекция 7

Контрольные вопросы

Приложения алгебры логики в технике (релейно-контактные схемы).

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

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

Еще в 1910 году физик П. С. Эренфест указал на воз­можность применения аппарата алгебры логики при исследовании релейно-контактных схем (РКС). Однако его идеи стали реализовываться значительно позже, когда создание общей теории конструирования РКС стало ост­ро необходимым.

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

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

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

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

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

1) переключателей, которыми могут быть механичес­кие действующие устройства (выключатели, переключа­ющие ключи, кнопочные устройства и т. д.), электромаг­нитные реле, электронные лампы, полупроводниковые элементы и т.п.;

2) соединяющихих проводников;

3) входов в схему и выходов из нее (клемм, на кото­рые подается электрическое напряжение). Они называ­ются полюсами схемы.

Сопротивления, конденсаторы и т.д. на схемах не изображаются.

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

Рассмотрим простейшую схему, содержащую один переключатель Р и имеющую один вход А и один выход В. Переключателю Р поставим в соответствие высказы­вание р, гласящее: «Переключатель Р замкнут». Если ристинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения. Будем в этом случае говорить, что схема проводит ток. Если рложно, то переключатель разомкнут, и схема тока не проводит или на полюсе В снимается минимальное напря­жение при подаче на полюс А максимального напряже­ния.

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

Формулам, включающим основные логические опе­рации, также могут быть поставлены в соответствие пе­реключательные схемы.

Конъюнкция двух высказываний р v q будет представ­лена двухполюсной схемой с последовательным соедине­нием двух переключателей Р и q (схема 2).

Эта схема пропускает ток тогда и только тогда, когда истинны высказывания р и q одновременно, то есть pqº 1.

Дизъюнкция двух высказываний рvqдвухполюсной схемой с параллельным соединением переключателей Р и Q (схема 3).

Эта схема пропускает ток в случае, если истинно высказывание р или истинно высказывание q, то есть р v q º 1.

Если высказывание есть отрицание высказывания р, то тождественно истинная формула изображается схемой, которая проводит ток всегда (схема 4), а тождественно ложная формула р&изобразится схемой, которая всегда разомкнута (схема 5).

Из схем 1, 2 и 3 путем последовательного и парал­лельногоих соединения могут быть построены новые двухполюсные переключательные схемы, которые назы­вают П-схемами.

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

Примеры.

1. Формуле соответствует схема 6:

2.

 

Для схемы 7 соответствующая формула алгебры логики имеет вид:

Упростим эту формулу следующим образом:

Последней формуле соответствует П-схема 8:

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

Приведем пример построения РКС по заданным усло­виям с оценкой числа контактов.

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

Работа нужной РКС описывается функцией Буля трех переменных F(x, у, z), где перемен­ные высказывания х, у, z означают:

х - судья х голосует «за»,

у - судья у голосует «за»,

z - судья z голосует «за».

Таблица истинности функции F(x, у, z) имеет вид:

х	y	z	F(x, у, z)

Функции соответствует формула:

А этой формуле соответствует РКС, изображенная на схеме 7, которая содержит двенадцать переключателей.

Но как было показано, в результате равносильных преобразований формула F(x, у, z) может быть приведена к виду:

которому соответствует РКС, изображенная на схеме 8, содержащей пять переключателей.

Задачи для самостоятельного решения.

1. По таблице истинности найти формулы, определяющие функции F₁, F₂.

x	y	z	F1	F2

2. Составьте формулу для булевой функции F(x,y,z) = 1, если а) только одна какая-либо переменная равна нулю; б) если большинство переменных равны нулю. Упростите полученные формулы.

3. Составить РКС для формул:

4. Построить схемы, реализующие следующие булевы операции:

1. импликацию;
2. эквиваленцию.

5. Построить РКС для функций, если известно, что:

1. F(0,1,0)=F(1,0,1)=F(1,1,1)=1;
2. F(1,0,1)=F(1,1,0)=1;

 

6. Упростить РКС:

 

 

7. Проверить равносильность схем:

 

1. Какое множество называется алгеброй Буля?

2. Какие интерпретации алгебры Буля нам знакомы?

3. Определение функции алгебры логики.

4. Как представить заданную таблицей истинности функцию в виде формулы алгебры логики?

5. Что называется релейно-контактной схемой?

6. Какие виды соединений переключателей соответствуют основным логическим операциям?

7. Как нужно представить формулу, чтобы для нее можно было бы составить РКС?

ТЕМА: СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ.

ПЛАН:

1. Совершенная дизъюнктивная нормальная форма.

2. Совершенная конъюнктивная нормальная форма.

Главная

1. Совершенная дизъюнктивная нормальная форма.

Формула, составленная для заданной таблицей истинности функции, по выше приведенному правилу обладает свойствами, которые называются свойствами совершенства. Перечислим их:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.

2. Все логические слагаемые различны.

3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание.

4. Ни одно слагаемое не содержит одну и ту же переменную дважды.

Каждой не тождественно ложной формуле соответствует единственная формула с такими свойствами.

Для одной и той же формулы можно составить множество равносильных ей ДНФ. Но среди них существует единственная ДНФ с перечисленными свойствами совершенства.

ДНФ, для которой выполняются свойства совершенства называется совершенной ДНФ (СДНФ).

Составленная формула по таблице истинности и является СДНФ формулы.

Если функция задана какой – либо формулой, то для получения СДНФ формулы необходимо составить таблицу истинности. Если формула содержит большое количество переменных высказываний, то этот способ практически не приемлем. В этом случае получают СДНФ формулы путем равносильных преобразований.

Приведем соответствующий алгоритм:

1. Путем равносильных преобразований получить какую – либо ДНФ.

2. Если какая-либо элементарная конъюнкция В не содержит переменную х_i, то вводят ее, используя равносильность . И раскрывают скобки.

3. Если в ДНФ входят две одинаковые конъюнкции В, то лишнюю отбрасывают, используя свойство идемпотентности ВV B º B.

4. Если какая-либо конъюнкция содержит x_i вместе с отрицанием, то В º 0. И В исключают из ДНФ.

5. Если какая-либо конъюнкция содержит переменную x_i дважды, то одну из них отбрасывают, используя свойство x_i x_i º x_i.

Примеры.

1. Составить СДНФ для формулы по таблице истинности и путем равносильных преобразований.

Составим таблицу истинности, которая содержит 4 строки.

х	у

Получим какую-либо ДНФА и преобразованиями доведем до совершенства:

2. Аналогичное задание для формулы

Составим таблицу истинности, содержащую 8 строк.

a	b	c

Преобразуем формулу:

3. Путем равносильных преобразований получить СДНФА.