ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ЭВМ

.Алгебра логики. Основные понятия

Для структурно-функционального описания логических схем, составляющих основу любого дискретного вычислительного устройства, ЭВМ или ВС в целом, используется аппарат булевой алгебры, или алгебры логики, созданной английским математиком Дж. Булем. На практике булеву алгебру применил К. Шеннон. Он разработал метод описания любой сети, состоящей из совокупности переключателей и реле, математическими выражениями и принцип их преобразования на основе правил булевой алгебры. Поскольку между релейными и современными электронными схемами существуют аналогии, аппарат булевой алгебры находит широкое применение для анализа, описания и проектирования последних.

Булева алгебра оперирует двумя понятиями — истинность и ложность высказывания. Высказывание — некоторое предложение, о котором можно однозначно сказать, истинно оно или ложно. Например, «сейчас идет снег». Это утверждение может быть истинным или ложным. Истинное значение высказывания можно принимать за 1, а ложное — за 0, что позволяет рассматривать высказывание как двоичную переменную х е {0, 1}. Такое сходство с двоичной системой счисления удобно при использовании алгебры логики для анализа и синтеза схем цифровых устройств. Во всех случаях в тех или иных точках логических схем сигналы двух различных уровней могут представляться двоичными символами {0, 1}. Поэтому множество элементов булевой алгебры называется бинарным, а сама алгебра — бинарной или переключательной. В алгебре логики все высказывания обозначаются буквами латинского алфавита — х, у, z. В дальнейшем этими буквами будем обозначать булевы переменные. Набор переменных х, у, z может рассматриваться как n-разрядный двоичный код, разрядами которого являются эти переменные.

Булева алгебра позволяет удобно оперировать с булевыми выражениями, описывающими те или иные электронные узлы, а также на формальном уровне упрощать их путем эквивалентных преобразований, благодаря чему появляются возможности создавать технически более совершенные электронные устройства.

Из простых высказываний с помощью определенных операций можно строить более сложные высказывания, т.е. функции алгебры логики. Операции булевой алгебры часто встречаются в программном обеспечении вычислительных устройств, где они используются для замены аппаратной логики на программную. Основными или базовыми операциями булевой алгебры являются операции «И» (AND), «ИЛИ» (OR) и «НЕ» (NOT).

Операция «И» называется логическим умножением или конъюнкцией и обозначается одним из знаков « • », «л» или «& (амперсанд)». Операция «ИЛИ» называется логическим сложением или дизъюнкцией и обозначается знаком «+» или «V». Операция «НЕ» называется логическим отрицанием или инверсией и обозначается знаком « ' » или « —. ». При выполнении операций применяются отношение эквивалентности «=» и скобки «()», которые определяют порядок выполнения операций. Если скобок нет, то операции выполняются в следующей последовательности: логическое отрицание, логическое умножение и логическое сложение. Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий. Основные соотношения {теоремы) булевой алгебры можно сформулировать в виде законов, представленных в табл. 4.8.

Таблица 4.8

Основные законы булевой алгебры

Формульное представление

Закон булевой алгебры

О

II

о

xv0=x-1=x; xv1=1; x-0=0

Операции с константами

xvx=x;

xx=x

Идемпотентность

(х')-х

Двойное отрицание

xvy=yvx;

xy=y X

Коммутативность

xvxy=x(xvy)=x;

xvx’ y=xvy; x (x'vy)=x y

Поглощение

(xvy)'=x'y';

(xy)'=x'vy'

Закон Моргана

(xvy)vz=xv (yvz)=xvyvz;

(xy)z=x(yz)=x-yz

Ассоциативность

xvyz=(xvy)(xvz);

x(yvz)=xyvxz

Дистрибутивность

Истинность перечисленных законов легко доказывается методом совершенной индукции, т.е. перебором всех возможных случаев на основе таблицы истинности. Основные законы (см. табл. 4.8) дают правила преобразования булевых выражений, позволяющие получать эквивалентные выражения.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >