Логические основы ЭВМ. Теоретической основой построения ЭВМ являются специальные математические дисциплины

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

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

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

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

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

(2.3)

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

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

Таблица 2.4

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

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

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

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

Таблица 2.5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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