Некоторые применения алгебры логики

Еще в 1910 году физик Эренфест указал на возможность применения аппарата алгебры логики при исследовании релейно-коммутационных схем (РКС). Однако его идеи стали использовать гораздо позже, когда создание общей теории РКС стало остро необходимым. Это было связано с появлением ЭВМ. Кстати, первая релейная ЭВМ Марк-1 была создана в США в 1944 году Г.Айткеном и установлена в Гарвардском университете. А уже в 1945 году в Пенсильванском университете был осуществлен проект первой электронной ЭВМ, получившей название ЭНИАК, которая была публично продемонстрирована в 1946 году.

Использование алгебры логики при создании РКС основано на том, что в них основным техническим элементом является электромагнитное реле, имеющее два устойчивых состояния (включено/выключено). При включенном состоянии ток в цепи, в которой стоит реле, протекает через его контакты и не протекает при выключенном состоянии. Включенному состоянию сопоставляют цифру 1, а выключенному – цифру 0.

Как мы уже видели ранее, в алгебре логики тоже используются два логических значения, которые мы обозначали теми же цифрами 0 и 1. Исходя из этого, оказалось возможным каждой РКС поставить в соответствие некоторую формулу (логическую функцию), а каждой формуле – некоторую РКС. Тогда изучение свойств РКС и ее упрощение можно заменить изучением и упрощением соответствующей формулы. Затем от упрощенной формулы можно перейти к схеме.

Простейшая РКС содержит один переключатель P,имеет один вход А и один выход В. Переключателю Р можно поставить в соответствие высказывание “переключатель Р замкнут”. Если высказывание Р истинно, то сигнал, поступающий на вход А появится на выходе В. В этом случае схема проводит ток. Если высказывание Р ложно, то схема ток не проводит и на выход В сигнал не пройдет.

Таким образом, наше высказывание можно представить простейшей РКС (рис.11).

или

а) б)

Рис. 11

Отрицанием высказывания “переключатель Р замкнут” будет высказывание “переключатель Р разомкнут” и этому высказыванию будет соответствовать РКС, представленная на рис.12.

или

Если два переключателя соединить последовательно, как показано на рис.13, то такая РКС будет проводить ток лишь в одном случае, а именно тогда, когда оба переключателя P и Q замкнуты.

В других трех случаях: “ P замкнут и Q разомкнут”, “ P разомкнут и Q замкнут”, “ P замкнут и Q разомкнут” ток со входа А поступать на вход В не будет. А это есть не что иное, как конъюнкция высказываний P, Q, т.е. .

Аналогичные рассуждения приводят к тому, что параллельная РКС, представленная на рис. 14, является дизъюнкцией .

	а)				б)
				б)

Если высказывание есть отрицание высказывания P, то РКС,

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

или

а)

Рис.15

б)

Тождественно ложной формуле , очевидно, будет соответствовать приведенная на рис. 16 РКС

а)

, которая ток никогда не проводит, так как в ней один из контактов всегда разомкнут.

или

	а)		б)
		Рис.16

Из схем, приведенных на рис.10 – 16, путем последовательного и параллельного их соединения могут быть построены РКС любой сложности.

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

Рассмотрим примеры представления формулы в виде РКС, упрощение этой формулы и последующее представление ее в виде схемы.

Пример 1. .Этой формуле соответствует схема

Пример 2. этой формуле соответствует схема

Упростим формулу , введя в нее 2 дополнительные конъюнкции (формула от этого не изменится на основании комбинационного закона III.1) и объединив каждую из конъюнкций со 2, 3 и 4-м членами формулы :

Последней формуле будет соответствовать схема

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

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

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

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

Будем считать, что каждая переменная в формуле алгебры логики соответствует одному входу в некоторой логической схеме. Над одной переменной x в алгебре логики, как мы знаем, может выполняться единственная операция отрицания. Для реализации операции отрицания логической схемой необходимо, чтобы эта схема имела один вход x и один выход , и в виде схемы это будет выглядеть так:

или

Такая схема называется инвертором или схемой НЕ. Она инвертирует сигнал, т.е. переворачивает фазу сигнала на 180 ⁰ (иначе говоря, если мы подадим на вход инвертора сигнала , то на его выходе появится сигнал ).

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

или

или

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

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

При числе входов, т.е. переменных, больше двух соответствующие схемы будет отличаться от приведенных выше лишь числом входов и они будут называться соответственно: 2-входовая, 3-входовая и т.д. n -входовая схемы И, 2-входовая, 3-входовая и т.д. n -входовая схемы ИЛИ.

Если над некоторым числом переменных, соединенных операцией или , выполняется операция отрицания, то начертание логических схем будет выглядеть так:

На вход логической схемы могут подаваться уже инвертированные сигналы. Тогда 3-входовые схемы И и ИЛИ будут соответственно такие:

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

Пример. Представить формулу в виде логической схемы, упростить эту формулу и нарисовать соответствующую ей схему.

Решение

Упростим исходную формулу:

.

Соответствующая этой формуле схема будет иметь вид

При переходе от схемы к формуле её удобно сначала разметить, т.е. обозначить все выходы какими-либо символами (например, большими буквами латинского алфавита A, B, C,…). Затем, двигаясь от последнего выхода к началу, надо последовательно раскрывать каждый символ в соответствии с операциями и теми предшествующими символами, которые используются для получения данного символа. Продвижение по схеме прекращается, когда в формулу будут подставлены только входные переменные. Эту формулу можно затем упростить и по ней построить новую, более простую схему.

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

Теперь упростим эту формулу:

Последней конъюнкции соответствует следующая схема: