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

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

Вся информация в ЭВМ представляется в двоичной системе счисле­ния. Поставим в соответствие входным сигналам отдельных устройств ЭВМ значения переменных х_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₄ представляет собой функцию логического сложения, дизъюнкцию. Она принимает значение единицы, если хотя бы одна пе­ременная х_{ или х₂ имеет значение единицы:

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

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