Меню
Главная
Авторизация/Регистрация
 
Главная arrow Товароведение arrow Электроника

Алгебра логики

На первый взгляд цифровые устройства кажутся относительно сложными. Однако они основаны на принципе многократного повторения относительно простых базовых логических схем. Связи между этими схемами строятся на основе чисто формальных методов. Инструментом такого построения служит булева алгебра, названная по имени одного из ее разработчиков – английского математика Джорджа Буля. Применительно к цифровой технике она называется также алгеброй логики. В отличие от переменной в обычной алгебре логическая переменная имеет только два значения, которые обычно называются логическим нулем и логической единицей. В качестве обозначений используется "0" и "1" или просто 0 и 1. В дальнейшем по тексту учебника, чтобы отличить их от обычных 0 и 1, будем использовать обозначения лог. 0 и лог. 1, "0" и "1", а в данном параграфе – просто 0 и 1.

Существуют три основные операции между логическими переменными: конъюнкция (логическое И), дизъюнкция (логическое ИЛИ) и инверсия (логическое НЕ). В алгебре логики используются следующие обозначения операций:

  • • конъюнкция: F = A Ù B = A • B = АВ;
  • • дизъюнкция: F = A Ú В = А + В;
  • • инверсия: F = ͞A.

Таблица 33

Таблица истинности для логических функций

И: F = A Ù B

ИЛИ: F = A Ú В

НЕ: F = ͞A

A

В

F

A

В

F

А

F

0

0

0

0

0

0

0

1

0

1

0

0

1

1

1

0

1

0

0

1

0

1

1

1

1

1

1

1

Как следует из табл. 3.3, для конъюнкции – логического И – F только тогда равна 1, когда ее аргументы А и В равны 1. При дизъюнкции (логическом ИЛИ) F равна 1 тогда, когда А или В равны 1. Отсюда и следуют названия этих функций. Обе эти функции можно распространить на сколь угодно большое число переменных. Инверсия – логическая функция только одной переменной.

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

Принцип двойственности

Запишем правила выполнения операций ИЛИ и И, расположив строчки И в обратном (снизу вверх) порядке:

Сравним построчно операции ИЛИ и И. Нетрудно видеть, что если заменить в строках ИЛИ и И все 0 на 1, все 1 на 0 и знаки дизъюнкции на знаки конъюнкции, то правила меняются местами: строка ИЛИ превращается в строку И и наоборот.

В этом состоит принцип двойственности, который в общем виде записывается так:

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

В процессе преобразования формул используются также теоремы алгебры логики.

Теоремы для одной переменной (легко проверяемые подстановкой А = 1 и А = 0):

Заметим, что эти теоремы (как и последующие) остаются справедливыми и для случая, если под А понимать не только одну переменную, но и целое выражение.

Теоремы для двух и более переменных:

  • 10а. ; 10б. переместительный закон;
  • 11а.
  • 11б. сочетательный закон;
  • 12а. 12б. распределительный закон.

Если теоремы 10, 11 очевидны и совпадают с правилами обычной алгебры, то очевидность теоремы 126 (как и ряда следующих теорем) следует из принципа двойственности.

В самом деле, заменим в левой и правой частях теоремы 12а все переменные их отрицаниями и поменяем знаки конъюнкции и дизъюнкции друг на друга, получим:

.

Введем новые обозначения:

.

Получим , а это и есть теорема 126;

13а. закон поглощения (читается поглощает В").

Доказательство теоремы 13а: (используя теоремы 2 и 6); доказательство теоремы 13б следует из принципа двойственности;

14а. 14б.

Доказательство теоремы 14а:

(используя теоремы 8 и 1), доказательство теоремы 14б следует из принципа двойственности;

15а. 15б. закон склеивания (читается "склеивание по А"),

Доказательство теоремы 15а: (используя теоремы 4 и 6); доказательство теоремы 15б следует из принципа двойственности.

16а. 16б. теорема де Моргана, представляющая наиболее общую формулировку принципа двойственности.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы