Уроки 63 - 65
Логические основы построения компьютера

Изучив эту тему, вы узнаете:

- что изучает алгебра логики;
- какие операции возможны над высказываниями;
- как составляется таблица истинности;
- каким законам подчиняются логические выражения;
- что такое логические элементы компьютера.

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

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

Алгебра — это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными латинскими буквами, например а, b, х, у и т. д. Действия над переменными величинами записываются в виде математических выражений. Обобщенное представление о сути содержания алгебры, изучаемой в школе, с позиций объектного подхода представим в виде таблицы 23.1.

Термин "логика" происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон».

Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями. 

Высказывание - это предложение, относительно которого имеет смысл говорить истино оно или ложно.

Таблица 23.1. Что изучает школьная алгебра

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

Но не все выражения можно назвать высказываниями. В таблице 23.2 приведены примеры выражений, которые не являются высказываниями.

Алгебру логики называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: А, В, X, У. В алгебре Буля введены три основные логические операции с высказываниями: сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.

Обобщенное содержание предмета «алгебра логики» приведено в таблице 23.3. 

Таблица 23.2. Выражения, не являющиеся высказываниями

Таблица 23.3. Что изучает алгебра логики

Алгебра логики рассматривает высказывания не с точки зрения их содержания, а с точки зрения их истинности или ложности. И в этом смысле можно сказать, что высказывание может принимать только два значения — ИСТИНА (обозначим 1) и ЛОЖЬ (обозначим 0). 

Логические выражения и логические операции

Общее представление

Логические выражения могут быть простыми и сложными.

Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».

Сложное логическое выражение содержит высказывания, объединенные логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания.

В качестве основных логических операций в сложных логических выражениях используются следующие:

- НЕ (логическое отрицание, инверсия);
- ИЛИ (логическое сложение, дизъюнкция);
- И (логическое умножение, конъюнкция).

Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два высказывания. Существуют и другие операции, например операции следования и эквивалентности, правило работы которых можно вывести на основании основных операций.

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении, например:
- таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
- в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
- если число высказываний в логическом выражении N, то таблица истинности будет содержать 2^N строк, так как существует 2^N различных комбинаций возможных значений аргументов.

Операция НЕ — логическое отрицание (инверсия)

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

- если исходное выражение истинно, то результат его отрицания будет ложным;
- если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения: ; not А. Результат операции отрицания НЕ определяется следующей таблицей истинности:

Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Приведем примеры отрицания.

1. Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно.

2. Высказывание «Пушкин — гениальный русский поэт» истинно. Высказывание «Пушкин — не гениальный русский поэт» ложно.

3. Высказывание «Уравнение у = 4х + 3 в промежутке -2 ≤ х ≤ 2 не имеет корня» ложно. Высказывание «Уравнение у = 4х + 3 в промежутке -2 ≤ х ≤ 2 имеет корень» истинно. 

4. Высказывание «4 — простое число» ложно. Высказывание «4 — не простое число» истинно.

5. Принцип работы переключателя настольной лампы таков: если лампа горела, переключатель выключает ее, если лампа не горела — включает ее. Такой переключатель можно считать электрическим аналогом операции отрицания.

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

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

Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений. Результат операции ИЛИ определяется следующей таблицей истинности:

Применяемые обозначения: А или В; A ∨ В; A or В. При выполнении сложных логических преобразований для наглядности условимся пользоваться обозначением А + В, где А, В — аргументы (исходные высказывания). О том, что это логическое сложение, говорят прописные буквы в обозначении высказываний. 

Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.

Приведем примеры логического сложения.

1. Рассмотрим высказывание «В библиотеке можно взять книгу или встретить знакомого». Это высказывание формально можно представить так: С = A ∨ В, где высказывание А — «В библиотеке можно взять книгу», а В — «В библиотеке можно встретить знакомого». Объединение этих высказываний при помощи операции логического сложения означает, что события могут произойти как отдельно, так и одновременно.

2. Рассмотрим высказывание «Знания или везение — залог сдачи экзаменов». Успешно сдать экзамен может тот, кто все знает, или тот, кому повезло (например, вытянут единственный выученный билет), или тот, кто все знает и при этом выбрал «хороший» билет.

3. Кто хоть однажды использовал елочную гирлянду с параллельным соединением лампочек, знает, что гирлянда будет светить до тех пор, пока цела хотя бы одна лампочка. Логическая операция ИЛИ чрезвычайно схожа с работой подобной гирлянды, ведь результат операции ложь только в одном случае — когда все аргументы ложны.

Операция И — логическое умножение (конъюнкция)

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

Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения. Результат операции И определяется следующей таблицей истинности:

Применяемые обозначения: А и В; А ∧ В; А & В; A and В.

Условимся пользоваться при выполнении сложных логических преобразований обозначением А • В, где А, В — аргументы (исходные высказывания). О том, что это логическое умножение, говорят прописные буквы в обозначении высказываний.

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

Приведем примеры логического умножения.

1. Рассмотрим высказывание «Учитель должен быть умным и справедливым». Это высказывание формально можно представить так: С = А ∧ В, где высказывание А — «Учитель должен быть умным», а В — «Учитель должен быть справедливым». Объединение этих высказываний при помощи операции логического умножения означает, что учитель должен быть одновременно и умным, и справедливым.

2. Рассмотрим высказывание «Умение и настойчивость приводят к достижению цели». Достижение цели возможно только при одновременной истинности двух предпосылок — умения и настойчивости. выражения. Результат операции И определяется следующей таблицей истинности:

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

Операция «ЕСЛИ-TO» — логическое следование (импликация)

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.

Применяемые обозначения:

если А, то В; А влечет В; if A then В; А —> В.

Таблица истинности:

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствии) ложно.

Приведем примеры операции следования.

1. Рассмотрим высказывание «Если идет дождь, то на улице сыро». Здесь исходные высказывания «Идет дождь» и «На улице сыро». Если не идет дождь и не сыро на улице, результат операции следования — истина. На улице может быть сыро и без дождя, например, когда прошла поливочная маши¬на или дождь прошел накануне. Результат операции ложен только тогда, когда дождь идет, а на улице не сыро.

2. Рассмотрим два высказывания: А {х делится на 9}, В {х делится на 3}. Операция А —> В означает следующее: «Если число делится на 9, то оно делится и на 3». Рассмотрим возможные варианты:

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Применяемое обозначение: А ~ В.

Таблица истинности:

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Приведем примеры операции эквивалентности.

1. «День сменяет ночь тогда и только тогда, когда солнце скрывается за горизонтом»;

2. «Добиться результата в спорте можно тогда и только тогда, когда приложено максимум усилий». 

Составление таблиц истинности по логической формуле

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

С помощью таблиц истинности можно проверить истинность любых сложных высказываний.

При составлении таблиц истинности можно, как и в математике, применять простые правила-подсказки:

1) дизъюнкция — это логическое сложение. Значит, если среди слагаемых есть хотя бы одно истина (1), то результат не может быть ложным, то есть результат истина (1):

А + 1 = 1.

2) конъюнкция — логическое умножение. Значит, если среди сомножителей есть хотя бы один ложный (0), то результат ложь (0):

А • 0 = 0.

Рассмотрим примеры.

1. Дано логическое выражение А • . Требуется построить таблицу истинности. Выражение содержит две операции: отрицание и конъюнкцию.

По правилам приоритетного выполнения операций сначала следует определить отрицание для всех возможных значений, которые может принимать . Затем можно применить операцию конъюнкции для полученных значений с высказыванием А.

Построим таблицу истинности (таблица 23.4). Сначала заполним столбцы значениями для аргументов А и В. Затем заполним столбец значениями В. Результат заданного логического выражения отражен в последнем столбце.

Таблица 23.4. Таблица истинности для примера 1

2. Дано логическое выражение (А + ) • С. Требуется построить таблицу истинности.

Логическое выражение содержит три высказывания А, В, С.

Значит, таблица истинности будет содержать 2³ = 8 строк возможных сочетаний значений исходных высказываний (аргументов) А, В и С. Первые три столбца таблицы истинности будут заполнены различными сочетаниями значений аргументов. Далее будут располагаться результаты промежуточных вычислений и конечный результат (см. таблицу 23.5).

Таблица 23.5. Таблица истинности для примера 2

Некоторые законы булевой алгебры

Изучив эту тему, вы узнаете:

- что изучает алгебра логики;
- какие операции возможны над высказываниями;
- как составляется таблица истинности;
- каким законам подчиняются логические выражения;
- что такое логические элементы компьютера.

Некоторые законы булевой алгебры

Существуют законы (аксиомы), позволяющие преобразовывать сложные логические выражения с целью их упрощения. Некоторые из них приведены в таблице 23.6.

Таблица 23.6. Основные законы булевой алгебры

Таблица 23.6. Основные законы булевой алгебры (Продолжение)

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

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

- воспользоваться простыми правилами-подсказками;
- сравнить таблицы истинности для правой и левой части равенства;
- привести правую часть равенства к левой части (или наоборот), применив уже известные или доказанные законы;
- привести обе части равенства к одному выражению.

Приведем примеры доказательств некоторых законов.

Пример 23.1

Для приведенного выше правила раскрытия скобок больше подойдет способ сравнения таблиц истинности (таблица 23.7).

Таблица 23.7. Доказательство при помощи сравнения таблиц истинности

Таким же способом можно доказать законы де Моргана.

Пример 23.2

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

А + А • В = А • (1 + В) = А • 1 = А.

Пример 23.3

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

А + • В = • В + А = ( + А) • (В + А) = 1 • (А + В) = А + В.

Доказательства остальных законов проведите самостоятельно.

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

Нахождение логической формулы

Условимся называть задачу построения таблицы истинности по формуле сложного высказывания — прямой задачей. Тогда обратная задача — построение логической формулы по таблице истинности. Полученную формулу будем записывать в виде логической функции.

Рассмотрим несколько примеров.

Пример 23.4

Приведена таблица истинности для аргументов А, В, по которой надо составить логическое выражение F(A,B).

Алгоритм нахождения искомой формулы таков:

1. Выделить в таблице истинности строки, в которых выражение истинно (1);

2. Соединить операцией И (умножением) содержимое столбцов аргументов для выбранных строк. При этом если в таблице «О», пишем входной сигнал с отрицанием, а если в таблице «1», то без отрицания:

3. Соединить операцией ИЛИ полученные выражения.

F(A, В) = • + А • .

4. Это и есть искомая формула. Однако она громоздка и ее следует упростить. Получаем очень простой результат.

F(A,B) = • + А • = • ( +А) = .

Пример 23.5

Приведена таблица истинности для аргументов А, В, С, по которой надо составить логическое выражение F(A,B,C). Дополняем таблицу столбцами, названными «Отмечаем» и «Записываем». Выполняем действия в соответствии с алгоритмом, описанным в примере 23.1.

Соединим полученные формулы операцией ИЛИ и получим формулу:

F(A,B,C) = + А - В - С.

Пример 23.6

Приведена таблица истинности для аргументов А, В, по которой надо составить логическое выражение F(A,B). Дополняем таблицу столбцами, названными «Отмечаем» и «Записываем» и выполняем действия в соответствии с алгоритмом, описанным в примере 1.

Получаем формулу:

F(A,B) = • В + А • + А • В.

Внимательно посмотрите на таблицу истинности. Не соответствует ли она логической операции ИЛИ?

Если это так, то полученная формула должна быть эквивалентна формуле А + В.

Попробуем это доказать, пользуясь правилами преобразований, которые приведены выше.

Вынесем за скобки «общий множитель» В из 1-го и 3-го «слагаемых» нашего выражения, а 2-е оставим без изменения:

Подчеркнутые выражения упрощаем по правилам 9 и 10, приведенным в таблице 23.6.

Пример 23.7

Приведена таблица истинности для аргументов А, В, С, по которой надо составить логическое выражение F(A,B,C). 

Если внимательно посмотреть на таблицу истинности, становится очевидным, что результат преобразования не зависит от А и В. Результирующий столбец является отрицанием содержимого столбца С. Попробуйте самостоятельно доказать, что громоздкое логическое выражение, которое можно получить по приведенному выше алгоритму, упрощается до , то есть F(A, В,С) = .

Пример 23.8

Приведена таблица истинности для аргументов А, В, по которой надо составить логическое выражение F(A,B).

Очевидно, что результирующий столбец повторяет 1-й, то есть искомая формула упростится до F(A,B) = А.

На приведенных примерах вы убедились, что:

♦ алгоритм, по которому получается формула, верен;
♦ полученная формула часто требует упрощения (минимизации).

С какой целью следует упрощать полученную формулу?

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

Логические элементы и основные логические устройства компьютера

Представление о логическом элементе

Любая информация при обработке на компьютере представляется в двоичной форме, то есть кодируется некоторой последовательностью, состоящей из 0 и 1. Упрощенно можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих 0 и 1. Такую обработку в компьютере выполняют логические элементы (вентили). Логический элемент — это электронное устройство, выполняющее одну из основных логических операций: И, ИЛИ, НЕ (рисунок 23.1). Условные обозначения логических элементов являются стандартными и используются при составлении логических схем компьютера.

Технически логический элемент реализуется в виде электрической схемы, которая представляет собой соединение различных деталей: диодов, транзисторов, резисторов, конденсаторов.

На вход логического элемента поступают электрические сигналы высокого и низкого уровней напряжения, которые интерпретируются в зависимости от реализуемых функций и на выход выдается один выходной сигнал также либо высокого, либо низкого уровня. Эти уровни соответствуют одному из состояний двоичной системы: 1 — 0; ИСТИНА — ЛОЖЬ.

Рис. 23.1. Логические элементы НЕ, ИЛИ, И

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

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

Проектирование логических схем

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

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

Рис. 23.2. Логическая схема по неупрощенной формуле

По таблице истинности можно получить логическую формулу:

F(A,B) = • В + А • .

В полученной формуле 5 операций: 2 — операции отрицания, 2 — конъюнкции и 1 — дизъюнкции.

Логическая схема будет иметь вид, представленный на рисунке 23.2. 

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

• В + А • = • (А + В).

Докажите эквивалентность этих формул самостоятельно.

В упрощенной формуле 4 операции: 1 операция отрицания, 2 — конъюнкции и 1 — дизъюнкции.

Логическая схема для упрощенной формулы будет иметь вид, представленный на рисунке 23.3.

Рис. 23.3. Логическая схема по минимизированной формуле

Примером проектирования логической схемы может служить построение полусумматора для сложения двух двоичных цифр. Если учесть, что все математические операции, осуществляемые компьютером — умножение, деление, возведение в степень, вычисление интегралов, решение дифференциальных уравнений и т. д., — в конечном счете, сводятся к выполнению по определенным правилам операций сложения, то станет ясно, что сумматор — один из важных узлов ЭВМ.

Полусумматор — схема соединения логических элементов, которая обеспечивает сложение двух бит. На вход полусумматора поступает два сигнала, каждый из которых может быть равен О или 1. На выходе также два сигнала — один является двоичной суммой входных сигналов, другой — значение разряда переноса в старший разряд. 

Схема полусумматора не имеет третьего входа, на который мог бы поступать бит переноса от предыдущего разряда суммы. Поэтому обычно полусумматор реализует сложение только младших разрядов двоичных слагаемых.

Итак, изобразим таблицу истинности полусумматора:

По таблице истинности составим формулы для разряда суммы и разряда переноса:

S = (• В) + (А • В);

R = А • В.

Для разряда сложения (по формуле S) нами уже составлена логическая схема в предыдущем примере. Значение для разряда переноса (по формуле R) можно взять как промежуточное значение из той же схемы.

В более компактном виде схема полусумматора представлена на рис. 23.4.

Рис. 23.4. Схема полусумматора

Контрольные вопросы и задания

1. Что изучает алгебра логики?

2. Приведите примеры простых высказываний.

3. Являются ли следующие предложения высказываниями:

■ если D < 0, то уравнение не имеет решения;
■ алгоритм — последовательность действий (план);
■ в гелиоцентрической системе все планеты вращаются вокруг Земли.

4. Приведите примеры сложных высказываний.

5. Сколько строк будет в таблицах истинности для сложных высказываний:

■ + В;
■ (А + В) • .

6. Постройте таблицу истинности для сложного высказывания

■ ( + ) • C .

7. Упростите следующие логические выражения:

■ ( + В) • ;
■ А + • В + С • В;
■ (А + В) • (А + ) • С.

8. По заданным таблицам истинности найдите логические выражения и упростите их:

9. Постройте логические схемы по заданным логическим выражениям:

■ ( + В) • С;
■ + + ;
■ .