Основные сведения из алгебры логики

Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является алгебра логики, или булева алгебра (Дж. Буль — английский математик прошлого столетия, основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их оптимизации и проектиро­вания.

Вся информация в ЭВМ представляется в двоичной системе счисле­ния. Поставим в соответствие входным сигналам отдельных устройств ЭВМ значения переменных х_i (i = 1, n), а выходным сигналам — значе­ния функций y _j (j=1,m)(рис. 2.1).

Рис. 2.1. Представление схемы ЭВМ

В этом случае зависимостями

где: х_i, — i-йвход;

п — число входов;

у_j —j-й выход;

т — число выходов в устройстве,

можно описывать алгоритм работы любого устройства ЭВМ. Каж­дая такая зависимость у_j является «булевой функцией, у которой чис­ло возможных состоянии и каждой ее независимой переменной равно двум» (стандарт ISO 2382/2-76), т.е. функцией алгебры логики, а ее аргументы определены на множестве {0,1}. Алгебра логики устанав­ливает основные законы формирования и преобразования логических функций. Она позволяет представить любую сложную функцию в виде композиции простейших функций. Рассмотрим наиболее употреби­тельные из них.

Известно, что количество всевозможных функций N от п аргу­ментов выражается зависимостью

(2.3)

При n=0 можно определить две основные функции (N=2), не зави­сящие от каких-либо переменных: у₀, тождественно равную нулю (у₀≡0), и у₁ тождественно равную единице (y₁≡1). Технической интер­претацией функции y₁≡1 может быть генератор импульсов. При от­сутствии входных сигналов на выходе этого устройства всегда име­ются импульсы (единицы). Функция может быть интерпретиро­вана отключенной схемой, сигналы от которой не поступают ни к каким устройствам.

При п=1 зависимость (2.3) дает N=4. Представим зависимость зна­чений этих функций от значения аргумента х в виде специальной таб­лицы истинности (табл. 2.4).

Таблица 2.4. Таблица функций от одной переменной

Таблицы истинности получили такое название, потому что они определяют значение функции в зависимости от комбинации вход­ных сигналов. В этой таблице, как и ранее, у₀≡0 и y₁≡1. Функция у₂=х, а функция у₃=x (инверсия х).

Этим функциям соответствуют определенные технические анало­ги. Схема, реализующая зависимость у₂₌х,называется повторите­лем, а схема у₃=x — инвертором.

При п=2, N=16, т.е. от двух переменных можно построить шест­надцать различных функций. В табл. 2.5 представлена часть из них, имеющая фундаментальное значение при построении основных схем ЭВМ.

Таблица 2.5 Таблица функций от двух переменных

Заметим, что в левой части таблицы перечислены всевозможные комбинации входных переменных (наборы значений), а в правой — возможные реакции выходных сигналов. В табл. 2.5 представлены функции у₀-у₃, полностью соответствующие функциям из табл. 2.4, а также новые, часто используемые и интересные функции у₄-у₉. При этом местоположение функций и их нумерация в таблице особого зна­чения не имеют. По данной таблице нетрудно составить аналитичес­кое выражение (зависимость) для каждой функции от двух аргумен­тов вида (2.2). Для этого наборы переменных, на которых функция принимает значение единицы, записываются как конъюнкции (логи­ческое умножение) и связываются знаками логического сложения. Такие формы функций получили название дизъюнктивных нормаль­ных форм (ДНФ). Если в этих функциях конъюнкции содержат все без исключения переменные в прямом или инверсном значении, то та­кая форма функций называется совершенной.

Функция y₄ представляет собой функцию логического сложения, дизъюнкцию. Она принимает значение единицы, если хотя бы одна пе­ременная х_{ или х₂ имеет значение единицы:

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

Функция у, является инверсной функцией по отношению к у₄:

Она имеет название «отрицание дизъюнкции». Иногда в литера­туре встречается ее специальное название — «стрелка Пирса», по фа­милии математика, исследовавшего ее свойства.

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

У₆ = х₁ ● х₂.

Функция у₇ является инверсной функцией по отношению к у₆:

Она называется «отрицание конъюнкции» или «штрих Шеффера».

Функция y₈ называется логической равнозначностью. Она прини­мает значение единицы, если все ее переменные имеют одинаковое значение (или 0, или 1):

Функция у ₉ является инверсной функцией по отношению к у₈

Она принимает значение единицы, если ее переменные имеют про­тивоположные значения. Далее будет показано, что функции у₈ и у₉являются основой для построения сумматоров, так как они соответ­ствуют правилам формирования цифр двоичных чисел при сложении (вычитании).

Из перечисленных функций двух переменных можно строить сколь угодно сложные зависимости, отражающие алгоритмы преобразова­ния информации, представленной в двоичной системе счисления. Ал­гебра логики устанавливает правила формирования логически пол­ного базиса простейших функций, из которых могут строиться лю­бые более сложные. Наиболее привычным базисом является набор трех функций {инверсия —｢, дизъюнкция —V, конъюнкция — Λ или &}. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.

Алгебра логики устанавливает, что существуют и другие комби­нации простейших логических функций, обладающих свойством ло­гической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и (инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции {«отрицание дизъюнкции ()»} и {«отрицание конъ­юнкции ()»}- Однако работа с функциями, представленными в ука­занных базисах, требует от специалистов по проектированию ЭВМ определенных навыков.

Законы алгебры логики

Из определения вышеприведенных функций можно установить целый ряд простейших свойств:

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

• коммутативный (переместительный):

• ассоциативный (сочетательный):

Эти законы полностью идентичны законам обычной алгебры;

• дистрибутивный (распределительный):

• закон поглощения. В дизъюнктивной форме ЛФ конъюнкция мень­шего ранга, т.е. с меньшим числом переменных, поглощает все конъ­юнкции большего ранга, если ее изображение содержится в них. Это же справедливо и для конъюнктивных форм:

• законы склеивания:

где F — логическая функция общего вида, не зависящая от переменной х;

• закон свертки:

• правило де Моргана:

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

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: