Логические основы ЭВМ
Основные понятия алгебры логики
| О |
снову любого дискретного вычислительного устройства составляют элементарные логические схемы, работа которых базируется на законах и правилах алгебры логики.
Алгебра логики (булева алгебра) – раздел дискретной математики, изучающий высказывания и логические операции над ними.
Высказывание – связное повествовательное предложение, о котором можно сказать, истинно оно или ложно. Высказывание не содержит внутреннего противоречия и несет смысловую нагрузку. Каждое составное высказывание можно выразить в виде логической формулы (выражения), в которую входят логические переменные, обозначающие высказывания, и логические операции.
Основными, или базовыми, операциями булевой алгебры являются: НЕ (NOT), ИЛИ (OR) и И (AND).
Операция НЕ называется логическим отрицанием, или инверсией, и обозначается знаком (—, Ø). Результат операции логического отрицания равен 1, если значение переменной равно 0 и, наоборот, равна 0, если переменная равна 1.
Операция ИЛИ называется логическим сложением, или дизъюнкцией, и обозначается знаком сложения (+, Ú). Дизъюнкция двух переменных равна 1, если хотя бы одна переменная равна 1 и равна 0, если обе переменные равны 0.
Операция И называется логическим умножением, или конъюнкцией, и обозначается знаком умножения (×, Ù, &). Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0 и равна 1, если обе переменные равны 1.
Таблица истинности – табличное представление логической операции, в котором перечислены все возможные сочетания логических значений операндов вместе со значением результата операции для каждого из этих сочетаний. Для указанных выше операций таблицы истинности имеют следующий вид.
| Инверсия | Дизъюнкция | Конъюнкция | |||||||
| A | ØA | A | B | AÚB | A | B | A&B | ||
В алгебре логики кроме базовых логических операций используются и другие операции, например импликация и эквивалентность.
Операция импликации (логическое следование) образуется соединением двух переменных с помощью связки «если…то» и обозначается знаком (®). Импликация принимает значение 0 тогда и только тогда, когда первая переменная имеет значение 1, а вторая – 0. Это означает, что составное высказывание ложно только тогда, когда из истинной предпосылки (первое высказывание) вытекает ложный вывод (второе высказывание). Например, высказывание «Если число делится на 10, то оно делится на 3» принимает значение ложь, так как из истинной предпосылки «число делится на 10» делается ложный вывод «оно делится на 3».
Операция эквивалентности (логическое равенство) образуется соединением двух переменных с помощью связки «…тогда и только тогда, когда…» и обозначается знаком (~). Результат операции эквивалентности равен 1 тогда и только тогда, когда обе переменные одновременно имеют значение либо 0 либо 1. Это означает, что составное высказывание истинно, когда входящие в него высказывания одновременно либо истинны либо ложны. Например, высказывание «Компьютер может производить вычисления тогда и только тогда, когда он включен» принимает значение истины, так как оба высказывания «Компьютер может производить вычисления» и «когда он включен» являются истинными.
Таблицы истинности для операций импликации и эквивалентности имеют следующий вид.
| Импликация | Эквивалентность | |||||
| A | B | A®B | A | B | A~B | |
Для преобразования логических формул с целью их упрощения используются законы алгебры логики: законыоднопарных элементов, законы отрицания и комбинационные законы.
Законы однопарных элементов: а) универсального множества: x+1=1; x×1=x; б) нулевого множества: x+0=x; x×0=0.
Законы отрицания: а) двойного отрицания: 
=x; б) дополнительности: x+ 
=1; x 
=0; в) двойственности (правило де Моргана): 
; 
.
Комбинационные законы:
а) тавтологии: x+x=x; x×x=x;
б) коммутативные: x1+x2=x2+x1; x1×x2=x2×x1;
в) ассоциативные (сочетательные): x1+(x2+x3)=(x1+x2)+x3; x1(x2x3)=(x1x2)x3;
г) дистрибутивные (распределительные): x1(x2+x3)=x1x2+x1x3; x1+x2x3=(x1+x2)(x1+x3);
д) закон абсорбции (поглощения): x1+x1x2=x1; x1(x1+x2)=x1;
е) склеивания: 
; 
.
Логической функцией(булевой, двоичной)называется логическая (двоичная) переменная y, значение которой зависит от значений двоичных переменных (x1, x2, …, xn), являющихся аргументами: y=y(x1, x2, …, xn). Любое составное высказывание можно рассматривать как логическую функцию y(x1, x2, …, xn), аргументами которой являются простые высказывания (логические переменные x1, x2, …, xn). Задание логической функции означает, что каждому из возможных сочетаний аргументов соответствует определенное значение функции y. Если число аргументов равно n, то количество возможных сочетаний определяется как 2n. Для каждой логической функции можно построить таблицу истинности, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов.
В алгебре логики все логические операции путем логических преобразований могут быть сведены к трем базовым: логическому умножению, логическому сложению и логическому отрицанию. Приоритеты выполнения логических операций в логических функциях следующие: инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность. Рассмотрим на примерах приемы и способы упрощения логических формул и составления таблиц истинности для логических функций.
Пример 1. Используя законы алгебры логики, упростить логические формулы.
а) 
. При преобразовании законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, законы дополнительности и нулевого множества.
б) 
. Применяется правило де Моргана; общий множитель выносится за скобки; используется закон дополнительности.
в) 
. Общие множители выносятся за скобки; применяется закон универсального множества.
Пример 2. Преобразовать логическую функцию 
. В этом примере для обозначения дизъюнкции и конъюнкции используются знаки Ú и &.
Решение
.
Пример 3. При каких значениях переменных A и B логическая функция 
принимает значение, равное 0.
Решение
Составим таблицу истинности для заданной логической функции.
| A | B | 
|  &B
| A&B | 
| &BÚ 
|
Из таблицы видно, что логическая функция F принимает значение 0 только при A=1 и B=1.
Логические основы ЭВМ
| Л |
юбое вычислительное устройство компьютера (например, двоичный сумматор) представляет собой электронную логическую схему, состоящую из логических элементов.
Логический элемент(простой функциональный узел)– это простая электронная схема, которая реализует элементарную логическую функцию. К базовым логическим элементам относятся электронные схемы И, ИЛИ, НЕ, И–НЕ, ИЛИ–НЕ, а также триггер. На входы логического элемента поступают сигналы – значения аргументов, на выходе появляется сигнал – значение функции. Входные и выходные сигналы логических элементов могут иметь одно из двух логических состояний: 1 (истина) или 0 (ложь). Работу логического элемента (преобразование сигналов) описывают с помощью таблицы истинности (состояния), соответствующей определенной логической функции.
Схема И реализует конъюнкцию двух или более логических значений. Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Условное графическое изображение логического элемента представлено на рисунке
| y=x1x2 |
| x2 |
| x1 |
| & |
Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Единица на выходе схемы ИЛИ будет тогда и только тогда, когда на любом из входов будет единица. Условное графическое изображение логического элемента представлено на рисунке.
| y=x1Úx2 |
| x2 |
| x1 |
Схема НЕ (инвертор) реализует операцию логического отрицания. Единица на выходе схемы НЕ будет тогда, когда на входе будет ноль. Когда на входе единица, то на выходе будет ноль. Условное графическое изображение логического элемента представлено на рисунке.
|
| x |
Схема И-НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Условное графическое изображение логического элемента и таблица истинности представлены ниже.
| x1 | x2 | 
|
|
| x1 |
| & |
| x2 |
| x1 | x2 | 
|
Схема ИЛИ-НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Условное графическое изображение логического элемента и таблица истинности представлены ниже.
|
| x1 |
| x2 |
Триггер – электронное устройство с двумя устойчивыми состояниями, предназначенное для хранения 1 бита данных. Триггер является важнейшей структурной единицей оперативной памяти компьютера, а также внутренних регистров процессора. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop («хлопанье»). Самый распространенный тип триггера – RS-триггер. Он содержит защелку из двух элементов ИЛИ-НЕ и два раздельных статических входа управления: вход R (сброс – reset) и вход S (установка – set). Для RS-триггера с прямыми входами, когда за активный уровень принят уровень логической единицы, принципиальная схема и таблица истинности имеют следующий вид.
| Вход | Выходы | ||
| R | S | Q | 
|
| Без изменений | |||
| Не определено |
|
| Q |
| S |
| R |
Режим работы триггера, при котором R=1, а S=0, называется режимом очистки, при R=0, S=1 – режимом записи, а при R=0, S=0 – режимом хранения. Комбинация R=1, S=1 является запрещенной, так как на выходе Q может установиться состояние, как логического ноля, так и логической единицы. Рассмотрим пример построения электронной схемы, состоящей из базовых логических элементов.
Пример. Одноразрядный двоичный сумматор имеет два входа (x1 и x2) и два выхода (S – сумма и P – перенос в старший разряд). Таблица истинности для сумматора имеет следующий вид.
| Входы | Выходы | ||
| x1 | x2 | S=f1(x1, x2) | P=f2(x1, x2) |
Записать логические функции для S и P и составить электронную логическую схему сумматора, используя основные логические элементы.
Решение
Выходные функции S и P можно представить следующим образом: 
; P=f2(x1, x2)=x1x2.
Тогда структурная схема сумматора будет иметь следующий вид.
| P |
| S |
| x1 |
| & |
| & |
| & |
| x2 |
Тесты
2. 
3. 
4. 
3. (AÚB)ÚC
4. 
2. 
3. 
4. 
4. 
равносильно выражение …
2. 
3. 
4. 
2. 
3. 
4. 
3. 
4. 