Упражнения

1. Минимизировать расчетным методом логические функции:

_{1) ;}

2) ;

3) ;

4) .

2. Упростить с помощью карт Карно функции, заданные в числовой форме:

1) ; 2) ;

3) ; 4).

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

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

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

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

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

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

или

а б

Рис. 3.9. Схематическое изображение высказывания «переключатель Р замкнут»

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

или

а б

Рис. 3.10. Схематическое изображение отрицания высказывания «переключатель Р замкнут»

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

Рис. 3.11. Схематическое изображение конъюнкции двух

высказываний

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

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

б)

или

б

а

Рис. 3.12. Схематическое изображение дизъюнкции двух высказываний

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

или

б

а

Рис. 3.13. Схематическое изображение тождественно истинного

высказывания

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

а)

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

или

б

а

Рис. 3.14. Схематическое изображение тождественно ложного

высказывания

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

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

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

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

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

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

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

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

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

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

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

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

или

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

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

или

или

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

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

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

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

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

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

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

Решение

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

.

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

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

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

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

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