Логические основы цифровой техники

Все цифровые устройства построены на элементах, которые выполняют те или иные логические операции. Для формального описания логической стороны процессов в цифровых устройствах используется алгебра логики (АЛ).

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

Логические функции и законы алгебры логики

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

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

Число возможных наборов п аргументов составляет 2п, а число различных функций составляет 2. Так, для одного аргумента различных ЛФ будет 4, для двух — 16 и т.д. В табл. 11.3 приведены логические функции одной переменной.

Таблица 11.3

ЛФ одной переменной

Обозначение

Наименование

X

0

1

Константа 0

0

0

Повторение

0

1

Инверсия

1

0

Константа 1

1

1

Аналитический способ представления ЛФ предполагает ее запись в виде математического выражения f(x1} х2, ..., хп), в котором аргументы ЛФ связываются определенными математическими (логическими) операциями.

Простейших логических операций три: отрицание (инверсия, операция «НЕ»), логическое сложение (дизъюнкция, операция «ИЛИ») и логическое умножение (конъюнкция, операция «И»). Более сложные логические преобразования можно свести к указанным операциям.

Рассмотрим логические выражения и таблицы истинности основных логических операций для двух аргументов:

1) логическое сложение (дизъюнкция), операция «ИЛИ»:

2) логическое умножение (конъюнкция), операция «И»:

3) отрицание (инверсия), операция «НЕ»:

4) операция (стрелка) Пирса, «ИЛИ-НЕ»:

5) операция (штрих) Шеффера, «И-НЕ»:

6) операция эквивалентность, равнозначность:

7) операция неэквивалентность, неравнозначность, «Исключающее ИЛИ»:

Результаты основных логических операций для двух аргументов приведены в таблице истинности (табл. 11.4).

Таблица 11.4

Таблица истинности основных логических операций

*1

*2

У

или

и

НЕ

ИЛИ-НЕ

И-НЕ

Экв.

Искл.ИЛИ

0

0

0

0

1

1

1

1

0

1

0

1

0

0

1

0

1

0

1

1

0

0

1

0

1

1

1

1

1

0

0

0

1

0

Алгебра логики базируется на нескольких аксиомах, из которых выводят основные законы АЛ для преобразований с двоичными переменными. Каждая аксиома представляется в двух видах, что вытекает из принципа дуальности (двойственности) логических операций, согласно которому операции дизъюнкции и конъюнкции допускают взаимную замену, если поменять лог.1 на лог.О, лог.О — на лог.1, знак v — на -, а • — на v.

Аксиомы операции отрицания: 0 = 1, 1 = 0.

Аксиомы операций дизъюнкции и конъюнкции:

  • 1) 1 v 1 = 1; 0-0 = 0.
  • 2) 0vl = lv0 = l; 1 • 0 = 0 • 1 = 0.
  • 3) 0 v 0 = 0; 1-1 = 1.

Законы АЛ вытекают из аксиом и также имеют две формы выражения: для дизъюнкций и конъюнкций. Рассмотрим законы АЛ:

1) переместительный закон:

2) сочетательный закон:

3) закон повторения (тавтологии):

4) закон обращения: если хг = х2> то Xi = х2",

5) закон двойной инверсии (двойного отрицания):

6) закон нулевого множества:

7) закон универсального множества:

8) закон дополнительности:

9) распределительный закон:

10) закон поглощения:

11) закон склеивания:

12) Закон инверсий (закон де Моргана):

Для сложного логического выражения установлен следующий порядок выполнения операций: вначале выполняются операции инверсии «НЕ», затем — операции конъюнкции «И» и в последнюю очередь — операции дизъюнкции «ИЛИ». Если требуется изменить порядок выполнения логических операций, то используются скобки.

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