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

Содержание

Слайд 2

Понятие об алгебре логики

Основу логических схем и устройств ЭВМ составляет специальный математический

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

из 21

Слайд 3

Джорж Буль и Клод Шеннон

Данный раздел математики назван в честь английского математика

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

из 21

Слайд 4

Основные логические операции

Как и любая другая, булева алгебра использует переменные и операции

Основные логические операции Как и любая другая, булева алгебра использует переменные и
над ними. В данном случае переменные и операции являются логическими переменными и логическими операциями. Переменные могут принимать только два значения – ИСТИНА (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

Слайд 5

Операция «исключающее ИЛИ»

Высказывание «A ⊕ B» истинно тогда, когда истинно А или

Операция «исключающее ИЛИ» Высказывание «A ⊕ B» истинно тогда, когда истинно А
B, но не оба одновременно (то есть A ≠ B).
«Либо пан, либо пропал».

0

0

также: A xor B (Паскаль), A ^ B (Си)

1

1

сложение по модулю 2: А ⊕ B = (A + B) mod 2

арифметическое сложение, 1+1=2

остаток

Слайд 6

Свойства операции «исключающее ИЛИ»

A ⊕ A =
(A ⊕ B) ⊕ B =

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

A

0

?

Слайд 7

Импликация («если …, то …»)

Высказывание «A → B» истинно, если не исключено,

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

1

1

1

0

Слайд 8

Импликация («если …, то …»)

«Если Вася идет гулять, то Маша сидит дома».

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

Слайд 9

Эквивалентность («тогда и только тогда, …»)

Высказывание «A ↔ B» истинно тогда и

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

Слайд 10

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

из 21

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

Слайд 11

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

из 21

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

Слайд 12

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

из 21

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

Слайд 13

Упрощение логических выражений

В общем случае возможно получить более простое выражение, чем то,

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

из 21

Слайд 14

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

из 21

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

Слайд 15

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

из 21

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

Слайд 16

Карты Карно

С помощью карт Карно довольно удобно упрощать булевы функции неболь-шого числа

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

из 21

Слайд 17

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

из 21

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

Слайд 18

Упрощение по карте Карно

После того как карта будет заполнена на основании таблицы

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

из 21

Слайд 19

Пример: упростить функцию


Видим, что 1-й и 3-й член объединяются с поглощением

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

.

из 21

Слайд 20

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

из 21

Проверка через таблицу истинности (Слева – До упрощения, справа – После) из 21
Имя файла: Логические-основы-организации-компьютера-.pptx
Количество просмотров: 194
Количество скачиваний: 0