Логические основы организации компьютера

Понятие об алгебре логики
Основу логических схем и устройств ЭВМ составляет специальный математический аппарат, называемый алгеброй логики или исчислением высказываний. При этом под высказыванием понимается любое утверждение, о котором можно сказать, что оно истинно или ложно.
Если высказывание истинно, то считают, что его значение равно единице; если высказывание ложно, то считают, что его значение равно нулю. Таким образом, значение высказываний можно рассматривать как переменную величину, принимающую только два дискретных значения: 0 или 1.
Это приводит к полному соответствию между логическими высказываниями в математической логике и двоичными цифрами в двоичной системе счисления, что позволяет описывать работу логических схем компьютера, проводить их анализ и синтез с помощью математического аппарата алгебры логики.
Иное название алгебры логики – булева алгебра.
из 21

Джорж Буль и Клод Шеннон
Данный раздел математики назван в честь английского математика Джорджа Буля (Georg Boole, 1815 - 1854), изложившего основные положения этой алгебры в своем трактате «Исследование законов мышления с помощью математических теорий логики и вероятностей», опубликованном в 1854 г.
В 1937 г. Клод Шеннон (Claude Shannon, 1916-2001), в то время ассистент электротехнического факультета МИТ (Массачуссетского института технологий), предположил, что алгебру Буля можно использовать для решения проблем проектирования релейных переключающих схем. Предложенные Шенноном методы в дальнейшем были использованы при анализе и проектировании электронных цифровых схем.
из 21

Основные логические операции
Как и любая другая, булева алгебра использует переменные и операции над ними. В данном случае переменные и операции являются логическими переменными и логическими операциями. Переменные могут принимать только два значения – ИСТИНА (1) и ЛОЖЬ (0). Базовые логические операции – конъюнкция (AND), дизъюнкция (OR) и инверсия (NOT), которые символически представляются знаками точки, плюса и надчеркиванием:
A AND B = A ●B
A OR B = A + B
NOT A = Ā
Результатом операции AND будет 1 ( ИСТИНА) в том и только в том случае, если оба операнда имеют значение 1. Операция OR дает результат 1 в том случае, если любой из операндов (или оба вместе) имеют значение 1. Унарная операция NOT инвертирует значение операнда. При отсутствии скобок существует приоритет операции AND над операцией OR. При обозначении операции AND символ точки часто опускается, если это не порождает двусмысленного толкования.
В курсе математической логики вы изучите еще ряд логических операций, а здесь мы остановимся на этих трех базовых: AND, OR, NOT и лишь поясним еще некоторые
из 21

Операция «исключающее ИЛИ»
Высказывание «A ⊕ B» истинно тогда, когда истинно А или B, но не оба одновременно (то есть A ≠ B).
«Либо пан, либо пропал».
0
0
также:
A xor B (Паскаль),
A ^ B (Си)
1
1
сложение по модулю 2: А ⊕ B = (A + B) mod 2
арифметическое сложение, 1+1=2
остаток

Свойства операции «исключающее ИЛИ»
A ⊕ A =
(A ⊕ B) ⊕ B = A ⊕ 0 =
A ⊕ 1 =
A
0
?

Импликация («если …, то …»)
Высказывание «A → B» истинно, если не исключено, что из А следует B.
A – «Работник хорошо работает».
B – «У работника хорошая зарплата».
1
1
1
0

Импликация («если …, то …»)
«Если Вася идет гулять, то Маша сидит дома». A – «Вася идет гулять».
B – «Маша сидит дома».
Маша может пойти гулять
(B=0), а может и не пойти (B=1)!

Эквивалентность («тогда и только тогда, …»)
Высказывание «A ↔ B» истинно тогда и только тогда, когда А и B равны.

Основные тождества булевой алгебры
из 21

Комбинационные схемы (дизъюнктивная нормальная форма)
из 21

Комбинационные схемы (конъюнктивная нормальная форма)
из 21

Упрощение логических выражений
В общем случае возможно получить более простое выражение, чем то, которое дает и ДНФ, и КНФ.
Иногда предпочтительнее искать выражение, которое можно реализовать с помощью операций только одного типа.
Следует ожидать, что более простое логическое выражение будет и реализовано меньшим количеством операций. Существует несколько методов упрощения логических выражений, из которых мы рассмотрим два:
• алгебраический;
• с помощью карт Карно.
из 21

Алгебраический метод упрощения
из 21

Проверка с помощью таблиц истинности
из 21

Карты Карно
С помощью карт Карно довольно удобно упрощать булевы функции неболь-шого числа переменных (теоретически – не более шести, а практически – четырех).
Карта для задания функции, зависящей от n переменных, это таблица из 2n клеток, в которых представлены значения функции для всех возможных комбинаций значений переменных
Булева функция представляется в карте Карно следующим образом. Каждая клетка, в которой проставлено значение 1, соответствует определенному конъюнктивному члену в ДНФ функции. В этот конъюнктивный член входят переменные, имеющие значение 1 в комбинации для этой клетки, и инверсии переменных, имеющих в комбинации для этой клетки значение 0
Если необходимо заполнить карту для функции, заданной некоторым булевым выражением, то сначала это выражение нужно привести к канонической форме, т.е. к форме, в каждом члене которой будут присутствовать все переменные, а уже затем приступить к заполнению клеток карты Карно
из 21

Карта Карно для функции 4-х переменных
из 21

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

Пример: упростить функцию
Видим, что 1-й и 3-й член объединяются с поглощением С.
Объединяются также 2-й и 4-й с поглощением А. В итоге имеем:
.
из 21

Проверка через таблицу истинности
(Слева – До упрощения, справа – После)
из 21