Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Аксиомы, законы, тождества и теоремы алгебры логики




 

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

Математическим аппаратом анализа и синтеза цифровых систем служит алгебра логики (булева алгебра), которая изучает связь между переменными (сигналами), принимающими только два («0», «1») значения. Символы «0» и «1» в алгебре логики характеризуют состояния переменных или состояния их функций, в связи с чем эти символы нельзя рассматривать как арифметические числа. Алгебра логики является алгеброй состояний, а не алгеброй чисел, и для нее характерны основные действия, отличные от принятых в обычной алгебре действий над числами. В алгебре логики любая переменная может иметь состояние «0» или «1». Поэтому в алгебре логики каждой двоичной переменной, например х, ставится в соответствие обратная или дополнительная к ней (инверсная) переменная, такая, что:

Переменную следует читать как НЕ х.

В алгебре логики в случае одной переменной х действуют следующие правила (аксиомы):

(2.1)

Правила 1-4 характеризуют операцию логического сложения (дизъюнкции), правила 6-9 — операцию логического умножения (конъюнкции) и правила 5,10 — операцию инверсии. Знак логического сложения «+» читается ИЛИ (например, правило 1: «х или 0 равен х»). Знак логического умножения «•» читается И (например, «х и 0 равен 0»).

Правила 1-4, 6-9 поясняются схемами (рис. 2.2 а - з) на двух ключах в соответствии с числом слагаемых (сомножителей) в соотношениях.

Рис. 2.2. Схемы, иллюстрирующие операции логического сложения (а-г) и логического умножения (д-з)

 

Положению «Ключ включен» соответствует состояние «1», а положению «Ключ выключен» — состояние «0». Для логического сложения (правила 1-4) ключи в схемах соединены параллельно. Уровень высокого напряжения на выходе (F = 1) будет иметь место, если хотя бы один ключ находится в состоянии «1» (правила 2,4; рис.2.2, б,г). Результат суммы в правилах 1, 3 зависит от значения х (при x =1, F= 1, при х =0 F = 0; рис.2.2,а, в). Для логического умножения ключи соединены последовательно (рис.2.2 д-з). Уровень высокого напряжения на выходе (F = 1) будет только в том случае, если оба сомножителя равны единице (оба ключа включены). В противном случае результат умножения равен нулю (правила 6,9; рис.2.2 д,з). Результат умножения в правилах 7,8 зависит от значения х (рис.2.2 е,ж).

Для алгебры логики, как и для обычной алгебры, действительны следующие законы.

Переместительный закон (закон коммутативности) для логического сложения и умножения:

(2.2)

Сочетательный закон (закон ассоциативности) для логического сложения и умножения:

(2.3)

Распределительный закон (закон дистрибутивности логического умножения по отношению к сложению):

х (у +z ) = ху + хz. (2.4)

Для многих случаев алгебраических преобразований полезными являются тождества, относящиеся к двум и трем переменным:

(2.5)

Выражения 2) и 3) называют законом поглощения; 1),5) – законом склеивания.

В справедливости тождеств 1 и 2 нетрудно убедиться, вынося за скобку в левой части переменную х. Тождество 3 доказывается с помощью распределительного закона х(х + у) = хх + ху = х + ху = х. Аналогично доказывается и тождество 4. Для доказательства тождества 5 раскроем скобки в левой части:

(х + у)(х + z) = х + хz + ху + уz= х + ху + уz = х + уz.

К основным законам алгебры логики относятся законы инверсии для логических сложения и умножения (теоремы де Моргана):

(2.6)

т.е. инверсия суммы переменных есть произведение их инверсий;

(2.7)

т.е. инверсия произведения переменных есть сумма их инверсий.

В общем случае теоремы де Моргана могут быть представлены в виде, предложенном Шенноном:

(2.8)

Теорема в таком виде утверждает, что инверсия любой функции получается заменой каждой переменной ее инверсией и одновременно взаимной заменой символов сложения и умножения. При практическом применении теоремы необходимо строго соблюдать группировки членов, выраженные как явными, так и неявными скобками. В качестве примера определим инверсию функции F = ху + ху. По правилу (2.8) находим:

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





Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 926 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Самообман может довести до саморазрушения. © Неизвестно
==> читать все изречения...

2617 - | 2453 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.009 с.