Тема 4 Логические основы ЭВМ (Все лекции Шамаевой в формате PDF)

Тема 4. Логические основы ЭВМ1.ОСНОВНЫЕ СВЕДЕНИЯ ИЗ АЛГЕБРЫ ЛОГИКИ ...................................................................................... 12. ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ ......................................................................................................................... 43. ПОНЯТИЕ О МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ ...................................................................

54.ТЕХНИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ .......................................................... 71.Основные сведения из алгебры логикиТеоретической основой построения ЭВМ являются специальные математическиедисциплины. Одна из них - алгебра логика или булева алгебра, названная по имениосновоположника этой дисциплины Дж. Буля - английского математика 19-го столетия.Аппарат алгебры логики широко используют для описания схем ЭВМ, их оптимизации ипроектирования.Вся информация в ЭВМ представляется в двоичной системе счисления.

Поставим всоответствие входным сигналам отдельных устройств ЭВМ соответствующие значенияхi(i=1,n), а выходным сигналам - значения функций yj(j=1,m) (рис.1).Рис. 1. Представление схемы ЭВМВ этом случае зависимостямиyj=f(x1,x2,…,xi,…,xn),(1)где xi – i-й вход; n – число входов; yj– j-й выход; m – число выходов в устройстве,можно описывать алгоритм работы любого устройства ЭВМ. Каждая такая зависимость у ,является “булевой функцией, у которой число возможных состояний и каждой еенезависимой переменной равно двум” (стандарт ISO 2382/2-76), т.е. функцией алгебрылогики, а ее аргументы определены на множестве {0,1}. Алгебра логика устанавливаетосновные законы формирования и преобразования логических функций. Она позволяетпредставить любую сложную функцию в виде композиции простейших функций.Известно, что количество всевозможных функций N от п аргументов выражаетсязависимостью:N=2 2nРассмотрим наиболее употребительные из них.(2)При n=0 можно определить две основные функции (N=2), не зависящие от какихлибо переменных:у0 , тождественно равную нулю (у0=0), иу1 , тождественно равную единице (у1=1).Технической интерпретацией функции у1=1 может быть генератор импульсов.При отсутствии входных сигналов на выходе этого устройства всегда имеются импульсы(единицы).

Функция у0=0 может быть интерпретирована отключенной схемой, сигналыот которой не поступают ни к каким устройствам.При п=1 зависимость (3) дает N=4. Представим зависимость значений этихфункций от значения аргумента х в виде специальной таблицы истинности (табл. 1).Таблица 1.Таблица функций от одной переменнойYY0Y1Y2Y3x0100110110Таблицы истинности получили такое название, потому что они определяютзначение функции в зависимости от комбинации входных сигналов.

В этой таблице, как иранее, у0=0 и y1=1. Функция y2=х, а функция у3=⌐x - (инверсия x).Этим функциям соответствуют определенные технические аналоги. Схема, реализующаязависимость у2=х, называется повторителем, а схема y3=⌐х - инвертором.При п=2, N=l6, т.е. от двух переменных, можно построить 16 различных функций.В табл. 2 представлена часть из них, имеющая фундаментальное значение при построенииосновных схем ЭВМ.Таблица 2.Таблица функций от двух переменныхYiX1 X2Y0Y1Y2Y3Y4Y5Y6Y7Y8Y9Y100001101100001111001111000111100000011110100101101.101Y4 – логическое сложение, дизъюнкция Y4 = X1 V X2Y5 – инверсная функция Y4 – «не-или» , «стрелка Пирса», Y5 =⌐Y4 = X1 ○X2Y6 – логическое умножение – конъюнкция Y6 = X1 & X2 Y9Y7 – инверсная функция Y6 – «не-и» , «штрих Шеффера», Y7 = X1/ X2Y8 – логическая равнозначность или эквивалентность Y8= x1 * x2 VX1*X2Y9 – логическая разноименность или сложение по модулю 2, Y9 =⌐ Y8, Y9=X1∆X2Y10 – логическая импликация, Y10 = X1→X2Y15В левой части таблицы перечислены всевозможные комбинации входныхпеременных (наборы значений), а в правой - возможные реакции выходных сигналов.

Втабл. 2. представлены функции у0-у3, полностью соответствующие функциям табл. 1, атакже новые, часто используемые и интересные функции у4-у10. При этом местоположениефункций и их нумерация в таблице особого значения не имеют. По данной таблиценетрудно составить аналитическое выражение (зависимость) для каждой функции от двухаргументов вида (1). Для этого наборы переменных, на которых функция принимаетзначение единицы, записываются как конъюнкции (логическое умножение) и связываютсязнаками логического сложения. Такие формы функций получили названиедизъюнктивных нормальных форм (ДНФ).

Если в этих функциях конъюнкциисодержат все без исключения переменные в прямом или инверсном значениях, то такаяформа функций называется совершенной.Рассмотрим по отдельности логические функции с у4 по у9.Функция у4 представляет собой функцию логического сложения, дизъюнкцию.Она принимает значение единицы, если значение единицы имеет хотя бы одна переменнаях1 или х2:Тождественность приведенных аналитических зависимостей можно установить, пользуясьзаконами алгебры логики, приведенными ниже.Функция y5 является инверсной функцией по отношению к y4:Она имеет название “ отрицание дизъюнкции”. Иногда в литературе встречается ееспециальное название “стрелка Пирса”, по фамилии математика, исследовавшего еесвойства.Функция у6 является функцией логического умножения. Она очень похожа наоперацию обычного умножения и принимает значение единицы в тех случаях, когда всеее переменные равны единице:Функция y7 является инверсной функцией по отношению к у6:Она называется “отрицание конъюнкции” или “ штрих Шеффера”.

Функция y8 называетсялогической равнозначностью, она принимает значение единицы, если все еепеременные имеют одинаковое значение (или 0 или 1):Функция y9 является инверсной по отношению к y8:Она принимает значение единицы, если ее переменные имеют противоположныезначения. Ниже будет показано, что функции у8 и у9 являются основой для построениясумматоров, так как они соответствуют правилам формирования цифр двоичных чиселпри сложении (вычитании).Из перечисленных функций двух переменных можно строить сколь угодносложные зависимости, отражающие алгоритмы преобразования информации,представленной в двоичной системе счисления.

Алгебра логики устанавливает правилаформирования логически полного базиса простейших функций, из которых могутстроиться любые более сложные.Наиболее привычным базисом является набор трех функций:{инверсия - ⌐ , дизъюнкция - v, конъюнкция - Λ или &}.Работа с функциями, представленными в этом базисе, очень похожа наиспользование операций обычной алгебры.Алгебра логики устанавливает, что существуют и другие комбинации простейшихлогических функций, обладающих свойством логической полноты. Например, наборылогических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} такжеявляются логически полными. Наиболее интересны минимальные базисы, включающиепо одной операции {“отрицание дизъюнкции (¬∨ )”} и {“отрицание конъюнкции (¬Λ )”}.Однако работа с функциями, представленными в указанных базисах, требует отспециалистов по проектированию ЭВМ определенных навыков.2.

Законы алгебры логикиИз определения вышеприведенных функций можно установить целый ряд простейшихсвойств:•В алгебре логики установлен целый ряд законов, с помощью которых возможнопреобразование логических функций (ЛФ):• коммутативный (переместительный)x1&x2=x2&x1• ассоциативный (сочетательный)(x1&x2)&x3=(x1&x3)&x2=x1&(x2&x3)Эти законы полностью идентичны законам обычной алгебры;• дистрибутивный (распределительный)• Закон поглощения.

В дизъюнктивной форме ЛФ конъюнкция меньшего ранга, т.е.с меньшим числом переменных, поглощает все конъюнкции большего ранга, если ееизображение содержится в них. Это же справедливо и для конъюнктивных форм:• Закон склеиваниягде F - логическая функция общего вида, не зависящая от переменной х.• Закон свёртки.• Правило де МорганаУбедиться в тождественности приведенных зависимостей можно путеманалитических преобразований выражений или путем построения таблицы истинностидля логических функций, расположенных в левой и правой частях.Используя данные зависимости, можно преобразовывать исходные выражения вболее простые (минимизировать их), а далее по упрощенным выражениям построитьтехническое устройство, имеющее минимальные аппаратурные затраты.3.

Понятие о минимизации логических функцийПроблема минимизации логических функций решается на основе применениязаконов склеивания и поглощения с последующим перебором получаемыхдизъюнктивных форм и выбором из них оптимальной (минимальной). Существуетбольшое количество методов минимизации ЛФ. Все они отличаются друг от другаспецификой применения операций склеивания и поглощения, а также различнымиспособами сокращения переборов. Среди аналитических методов наиболее известнымявляется метод Квайна-Маккласки, среди табличных - метод с применением диаграммВейча.

Графические методы минимизации отличаются большей наглядностью и меньшейтрудоемкостью. Однако их применение эффективно при малом числе переменных п<5.Рассмотрим последовательность действий минимизации ЛФ на примере.Пример 1. Найти минимальную дизъюнктивную форму функции, заданной таблицейистинности (табл. 3).Таблица 3Таблица истинности функции Y=f(X1,X2,X3)X100001111Х200110011Х301010101Y10111101Эта функция интересна тем, что имеет несколько минимальных форм.

По даннымтаблицы запишем аналитическое выражение:Пунктирными линиями в этом выражении отмечены пары конъюнкций, к которымможно применить операцию склеивания типа FX\/F⌐X=F. Особенно это видно прииспользовании диаграммы Вейча, в которой “склеиваемые” конъюнкции находятся пососедству друг с другом. Диаграмма Вейча просто по-другому интерпретирует таблицуистинности (табл.