ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ КОМПЬЮТЕРА Изучив эту тему, вы узнаете: основные понятия и операции формальной логики; логические выражения и их преобразование; построение таблиц истинности логических выражений; основные логические устройства компьютера (регистр, сумматор).
. ОСНОВНЫЕ ПОНЯТИЯ ФОРМАЛЬНОЙ ЛОГИКИ в процессе обработки двоичной информации процессор выполняет арифметические и логические операции. Поэтому для получения представлений об устройстве компьютера необходимо познакомиться с основными логическими элементами, лежащими в основе построения компьютера. Для понимания принципа работы таких элементов начнем это знакомство с основных начальных понятий формальной логики. Сам термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон». Логика наука о законах и формах мышления.
Логика использует ряд основных понятий и описывает действия над ними, подчиняющиеся законам логики. К этим основным понятиям логики относятся следующие Высказывание (суждение) некоторое предложение, которое может быть истинно (верно) или ложно. Например, высказывание «сегодня хорошая погода» является истинным (принимает значение «ИСТИНА»), если светит Солнце, нет ветра и дождя и т. д. В противном случае это же высказывание будет ложным (принимает значение «ЛОЖЬ»). Рассуждая аналогично, в другом примере высказывания А>5, очевидно, приходим к тому, что оно истинно, если переменная А принимает любое значение, большее 5, и ложно в противном случае. Заметим, что любое высказывание не может быть одновременно истинным и ложным, а принимает только одно из этих двух возможных логических значений: ИСТИНА или ЛОЖЬ. Эти значения называются логическими постоянными, или логическими константами. Утверждение суждение, которое требуется доказать или опровергнуть, например, сумма внутренних углов треугольника равна 180°. Рассуждение цепочка высказываний или утверждений, определенным образом связанных друг с другом, например, если хотите начать работать на компьютере, то необходимо сначала включить электропитание. Умозаключение логическая операция, в результате которой из одного или нескольких данных суждений получается (выводится) новое суждение
Область знаний, которая изучает истинность или ложность высказываний (суждений), называется математической логикой. Утверждения в математической логике называются логическими выражениями. Логическое выражение представляет собой запись или устное утверждение, в которое, наряду с постоянными, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных логическое выражение может принимать одно из двух возможных значений: ИСТИНА (логическая единица) или ЛОЖЬ (логический ноль ). Приведем некоторые примеры логических выражений: а > 5, где а переменная, принимающая любое значение. При значениях а > 5 это логическое выражение истинно (равно логической 1), иначе ложно (равно логическому 0). Компьютер имеет оперативную память объемом не менее 32Мб. В одном компьютере это справедливо, то есть такое логическое выражение истинно (равно логической 1), а в другом это же выражение может оказаться ложным (равно логическому 0).
Подобно тому, как для описания действий над переменными величинами был разработан раздел математики алгебра, так и для обработки логических выражений в математической логике была создана алгебра высказываний, или алгебра логики. Поскольку основы такой алгебры были заложены в трудах английского математика Джорджа Буля (XIX век), то алгебра логики получила также название булевой алгебры. Вспомним, что ранее мы уже говорили о том, что решение любой задачи на компьютере сводится к выполнению процессором ряда арифметических и логических операций. Последние как раз и выполняются над логическими выражениями на основе законов и правил булевой алгебры. Таким образом, математический аппарат булевой алгебры позволил формализовать действия над логическими выражениями и явился базой для разработки логических элементов и, в целом, логических основ построения компьютеров. Из сказанного становится ясно, что для лучшего понимания работы компьютера как инструмента обработки информации необходимо познакомиться с логическими выражениями, а также их преобразованием с помощью логических операций, определенных в булевой алгебре.
ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ и ЛОГИЧЕСКИЕ ОПЕРАЦИИ Логические выражения могут быть простыми и сложными. Понятие и примеры простых логических выражений уже были рассмотрены выше. Но в основе логики работы компьютера, как правило, лежит преобразование сложных логических выражений. Для объяснения этого понятия нам понадобится ввести ряд операций алгебры логики (логических операций). Рассмотрим пять основных логических операций. Предварительно заметим, что аргументами этих операций являются простые логические выражения, а их результат равен 1 или О (логические значения) и определяется по соответствующей таблице истинности.
Логическая операция КОНЪЮНКЦИЯ определяет соединение двух логических выражений (высказываний) с помощью союза И. Эта операция называется также логическим умножением и обозначается символами & или ^. Рассмотрим таблицу истинности, определяющую результат этой логической операции над двумя аргументами простыми логическими выражениями А и В, каждое из которых может принимать логические значения 0 или 1. В соответствии с таблицей истинности можно дать следующее определение конъюнкцией называется логическая операция, ставящая в соответствие двум простым логическим выражениям новое сложное логическое выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных (простых) логических выражения.
Логическая операция ДИЗЪЮНКЦИЯ определяет логическое соединение двух логических выражений (высказываний) с помощью союза ИЛИ. Эта операция называется также еще логическим сложением и обозначается значком v. Рассмотрим таблицу истинности, определяющую результат этой логической операции над двумя аргументами простыми логическими выражениями А и В, каждое из которых может принимать логические значения 0 или 1. В соответствии с таблицей истинности можно дать определение: дизъюнкцией называется логическая операция, ставящая в соответствие двум простым логическим выражениям новое сложное логическое выражение, которое будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) логических выражений.
Логическая операция ОТРИЦАНИЕ, или ИНВЕРСИЯ определяется над одним аргументом (простым или сложным логическим выражением) следующим образом: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот, если исходное выражение ложно, то его отрицание будет истинным. Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО. Операция ОТРИЦАНИЕ обозначается символом 1, а ее результат определяется следующей таблицей истинности:
Логическая операция ИМПЛИКАЦИЯ (логическое следование). Эта операция связывает два простых логических выражения, из которых первое является условием, а второе следствием из этого условия. В разговорном языке эта операция выражается словами если..., то... Для ее обозначения в алгебре логики используется значок следования =>. Результат операции импликации для условия А (первое логическое выражение) и условия В (второе логическое выражение) определяется в соответствии со следующей таблицей истинности: По определению результатом импликации является ЛОЖЬ тогда и только тогда, когда условие (А) истинно, а следствие (В) ложно.
Логическая операция ЭКВИВАЛЕНТНОСТЬ (равнозначность) определяет результат сравнения двух простых логических выражений А и В, обозначается символом. Результат этой операции новое логическое выражение, которое является истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Это определение описывается следующей таблицей истинности:
Сложным логическим выражением называется логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью рассмотренных логических операций. Пусть, например, А, В и С три простых логических выражения. Одним из примеров составленного из них сложного логического выражения будет: D = 1 (AvBvC) Порядок выполнения логических операций в сложном логическом выражении: 1. инверсия ; 2. конъюнкция & (или л); 3. дизъюнкция v; 4. импликация =>; 5. эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.
ПОСТРОЕНИЕ ТАБЛИЦ ИСТИННОСТИ ДЛЯ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ При изучении работы различных устройств компьютера приходится рассматривать такие его логические элементы, в которых реализуются сложные логические выражения. Поэтому необходимо научиться определять результат этих выражений, то есть строить для них таблицы истинности. Рассмотрим пример построения таблицы истинности для следующего сложного (составного) логического выражения D = 1А л (В v С). Сначала нужно установить число строк и столбцов такой таблицы, то есть спланировать форму таблицы. При определении числа строк необходимо некоторым регулярным образом перебрать все возможные сочетания логических значений 0 и 1 исходных выражений А, В и С, из которых формируется заданное сложное логическое выражение В результате в таблице для трех аргументов окажется 8 строк (+ девятая строка шапка таблицы), и при таком подходе легко проверить, что мы действительно не повторили и не пропустили ни одного возможного сочетания логических значений аргументов исходных выражений А, В, С. Из этих рассуждений можно подметить некоторую общую закономерность: для любого числа N аргументов сложного логического выражения таблица истинности содержит 2 N строк, а также строку заголовка (шапки таблицы).
Количество столбцов таблицы истинности для удобства последовательного ее построения выберем равным шести. Эти столбцы соответствуют значениям исходных выражений А, В, С, промежуточных результатов А и (В v С), а также искомого окончательного результата значения сложного арифметического выражения 1А л (В v С). Построим таблицу истинности для заданного сложного логического выражения: