Заказать перевод

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

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

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

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

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

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

y_j=f(x₁,x₂,…,x_i,…,x_n), (2.2)

где x_i – i-й вход; n – число входов; y_i – i-й выход; m – число выходов в устройстве,

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

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

N=2²ⁿ. (2.3)

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

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

Таблица 2.4

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

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

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

Таблица 2.5