Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Основы булевой алгебры

Проектирование логических устройств и выбор наиболее оптимальных вариантов их построения производится с использованием алгебры логики, или алгебры Буля, разработанной в середине XIX века ирландским математиком Дж. Булем. В алгебре Буля используется двоичная переменная X, удовлетворяющая условию Х=1, если Х*0 (высказывание истинно), и Х=0, если X* 1 (высказывание ложно).

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

Операция НЕ (F = X) X = 0=>F = 1;X = 1=>F = 0.

Операция НЕ

Отрицанием высказывания X называется операция, результат которой F истинен, когда X ложно, и ложен, когда X истинно. Отрицание обозначается чёрточкой над высказыванием. Электронная схема, реализующая операцию отрицания, называется инвертором, или схемой НЕ, УГО которой приведено на рисунке:

Операция ИЛИ

Это операция над двумя переменными X и Y, результат F которой истинен, если хотя бы одна из составляющих его переменных истинна. Операция ИЛИ обозначается символом v, либо знаком «+». Электронная схема, реализующая операцию ИЛИ называется дизъюнктором или логической схемой ИЛИ. УГО схемы:

На выходе элемента ИЛИ сигнал, соответствующий логической 1, появляется в том случае, если сигнал логической 1 присутствует хотя бы на одном из его входов. Операция ИЛИ справедлива при любом числе логических переменных, то есть F=xvyvzv...vn= x+y+z+...+n.

Операция И

Это операция над двумя переменными X и Y, результат F которой истинен, если истинны значения обеих переменных. Операция И обозначается символом а или знаком умножения «•». Электронная схема, реализующая операцию И, называется конъюнктором, или логической схемой И. УГО схемы:

На выходе элемент я1 сигнал, соответствующий логической 1, появляется в том случае, если есть сигналы 1 на всех входах. Операция И справедлива при любом числе логических переменных, то есть F=xAyAZA... лп.= xyz-... п. Точка, обозначающая знак логического умножения, обычно опускается.

Из сравнения правил, определяющих операции ИЛИ и И, можно заметить, что, если в них заменить все 0 на 1, а все 1 на 0, и, кроме того, заменить знаки v на л и наоборот, то эти правила меняются местами. Первая строка таблицы для операции ИЛИ превращается в четвертую строку таблицы для операции И, вторая - в третью, третья - во вторую, четвёртая - в первую.

В общем случае операция ИЛИ выражается равенством XvY=F. Если заменить переменные X и Y в левой части их отрицаниями и знак v на а, то это равенство не нарушится в том случае, когда в правой части результат операции F будет заменён его отрицанием, т.е. XaY = F. Сравнение таблиц показывает, что это справедливо для любых комбинаций значений переменных X и Y.

Аналогично равенство для операции И F=XaY превращается в равенство для операции ИЛИ при замене всех переменных их отрицаниями, то есть X v Y = F. Указанное свойство таблиц сохраняется при любом числе переменных, над которыми выполняются операции. В этом состоит так называемый принцип двойственности в алгебре Буля.

Кроме знаков операций, в алгебре Буля применяются знак равенства «=» и скобки. Знак «=» означает не количественное равенство, а то, что разделяемые им выражения идентичны, поэтому левую часть всюду можно заменить правой частью и наоборот.

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

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>