Теоретическая часть. 
Применение алгебры высказываний в информатике

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

Для иллюстрации рассмотрим следующий пример: один незадачливый бизнесмен подал в компьютерную фирму жалобу на приобретённый компьютер. По словам бизнесмена, компьютер неверно отвечал на поставленные вопросы. Прибывший для проверки жалобы специалист предложил бизнесмену продемонстрировать один из ошибочных ответов. Тот потребовал вывести список клиентов, проживающих в штатах Теннеси и Кентукки, на что компьютер объявил, что таковых не имеется. «Вот видите!» — кипятился бизнесмен. — «А я точно знаю, что и в том, и в другом штате есть множество клиентов!». Консультант попытался объяснить, что машина по-своему права и что человек не может жить одновременно в обоих штатах. Консультант повторил запрос, заменив единственное слово (список клиентов, проживающих в штатах Теннеси ИЛИ Кентукки), и через полминуты вручил распечатку требуемого списка.

Главной причиной возникшего курьёза послужило незнание трёх основных логических операций, лежащих в основе всех выводов компьютера: И, ИЛИ, НЕ.

При записи логических выражений используется специальный язык, который принят в математической логике. Основоположником математической логики (математической дисциплины, изучающей технику доказательств) является немецкий математик Готфрид Вильгельм Лейбниц. Он сделал попытку построить универсальный язык, с помощью которого споры между людьми модно было бы решать посредством вычислений. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки — математической логики, — которая в отличии от обычной алгебры оперирует не числами, а высказываниями. В честь Буля логические переменные в языке программирования Паскаль впоследствии назвали булевскими.

Высказывание — это любое утверждение, относительно которого можно сказать истинно оно или ложно, т. е. соответствует оно действительности или нет. Таким образом высказывания являются двоичными объектами, и поэтому истинному значению высказывания ставят в соответствии 1, а ложному — 0.

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

Простейшими операциями в алгебре логики являются операции логического сложения (иначе, операция ИЛИ, операция дизъюнкции) и логического умножения (иначе, операция И, операция конъюнкции). Для обозначения операции логического сложения используют символы + или /, а логического умножения — символы * или /. Составное высказывание, образованное в результате операции логического сложения, истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний. Составное высказывание, образованное в результате операции логического умножения, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.

Правила выполнения операций в алгебре логики определяются рядом аксиом, теорем и следствий.

В частности, для алгебры логики выполняются законы:

• 1) сочетательный:
  • (a + b) + c = a + (b + c);
  • (a * b) * c = a * (b * c);
• 2) переместительный:

a + b = b + a;

a * b = b * a;

3) распределительный:

a * (b + c)=a * b + a * c;

a + b * c = a * b + a * c.

Справедливы соотношения:

а + а = а;

а * а = а;

a + a * b = a;

a + b = a, если a >= b;

a + b = b, если a < =b;

a * b = a, если a < =b;

a + b = b, если a >=b и т. д.

Наименьшим элементом алгебры логики является 0, наибольшим элементом — 1.

В алгебре логики также вводится ещё одна операция — операция отрицания (иначе, операция НЕ, операция инверсии), обозначаемая чертой над элементом. Логическое отрицание делает истинное высказывание ложным, и, наоборот, ложное — истинным.

По определению: a + a = 1, a * a = 0, 0 = 1, 1 = 0.

Справедливы такие соотношения: a = a, a + b = a * b, a * b = a + b.

Существует шесть вариантов отношений:

• 1. = равно
• 2. не равно
• 3. > больше
• 4. < меньше
• 5. >= больше или равно
• 6. <= меньше или равно

Отношение «равно» истинно для двух символьных величин, если их длина одинакова и все соответствующие символы совпадают. (Следует учитывать, что пробел — это тоже символ).

Символьные величины можно сопоставлять и в отношениях, =. Сравниваются между собой не сами символы, а их внутренние коды.

Функция в алгебре логики — это алгебраическое выражение, содержащее элементы алгебры логики a, b, c …, связанные между собой операциями, определёнными в этой алгебре.

Примеры логических функций:

• (a, b, c) = a + a*b*c + a+c;
• (a, b, c) = a*b + a*c + a*b*c.

Согласно теоремам разложения функций на составляющие любая функция может быть разложена на конституэнты «1» :

• (2) (a) = (1)*a + (0)*a;
• (a, b) = (1,b)*a + (0,b)*a = (1,1)*a*a + (1,0)*a*b + (0,1)*a*b + (0,0)*a*b и т. д.

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

Логический синтез вычислительных схем Рассмотрим логический синтез (создание) вычислительных схем на примере одноразрядного двоичного сумматора, имеющего два входа («a» и «b») и два выхода («S» и «P») и выполняющего операцию сложения в соответствии с заданной таблицей:

Таблица 1.

где (a, b) = S — значение цифры суммы в данном разряде;

(a, b) = P — цифра переноса в следующий (старший) разряд.

Согласно соотношению (2), можно записать:

S = (a, b) = 0*a*b + 1*a*b + 1*a*b + 0*a*b = a*b + a*b;

P = (a, b) = 1*a*b + 0*a*b + 0*a*b + 0*a*b = a*b.

Самой простой логической операцией является операция НЕ (по-другому отрицание, дополнение или инверсия; обозначают NOT X). Результат отрицания всегда противоположен значению аргумента. Операция Не является унарной, т. е. имеет всего один операнд. В отличии от неё операции И (AND) и ИЛИ (OR) являются бинарными, так как представляют собой результаты действий над двумя логическими величинами.

Логическое И называют конъюнкцией, или логическим умножением, а ИЛИ — дизъюнкцией, или логическим сложением.

Операция И имеет результат «истина» только в том случае, если оба её операнда истинны. Например, рассмотрим высказывание «Для установки ОС „Windows'95“ требуется процессор не ниже 80 386 и не менее 4 Мбайт оперативной памяти». Из него следует, что установка будет успешной только при одновременном выполнении обоих условий: даже если у вас в машине Pentium, но мало ОЗУ, «Windows'95» работать откажется.

Операция ИЛИ «менее привередлива» к исходным данным. Она даёт истину, если значение «истина» имеет хотя бы один из операндов. Разумеется, в случае, когда справедливы оба аргумента одновременно, результат по-прежнему истинный.

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

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

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

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

В вычислительной технике также часто используется операция, исключающая ИЛИ (XOR), которая отличается от обыкновенного ИЛИ только при X=1 и Y=1.

Таблица 3. Дополнительные логические операции.

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

Схемная реализация элементарных логических операций Любую достаточно сложную функцию можно реализовать, имея относительно простой набор базовых логических операций. Первоначально были разработаны и выпускались микросхемы, соответствующие основным логическим действиям. Потребитель, комбинируя имеющиеся в его распоряжении элементы, мог получить схему с реализацией необходимой логики. Но подобное «строительство здания из отдельных кирпичиков» не может удовлетворить практические потребности. Промышленность начала выпускать более сложные узлы: триггеры, регистры, счетчики, дешифраторы, сумматоры и др. новые микросхемы давали возможность реализовать ещё более сложные электронные логические устройства. Последовал переход к большим интегральным схемам (БИС), представлявшим из себя функционально законченные узлы, а не отдельные компоненты для их создания. Наконец, дальнейшая эволюция технологий производства ИМС привела к настолько высокой степени интеграции, что в одной БИС содержалось функционально законченное изделие: часы, калькулятор, небольшая специализированная ЭВМ…

Если посмотреть на внутреннее устройство современного компьютера, то там присутствуют ИМС очень высокого уровня интеграции: микропроцессор, модули ОЗУ, контроллеры внешних устройств и др. фактически каждая микросхема или небольшая группа микросхем образуют функционально законченный блок.

Обработка информации в ЭВМ происходит путём последовательного выполнения элементарных операций. Эти операции менее многочисленны, нежели набор команд ЭВМ. К элементарным операциям относятся: установка — запись в операционный элемент (например, регистр) двоичного кода; приём — передача (перезапись) кода из одного элемента в другой; сдвиг — изменение положения кода относительно исходного; преобразование — перекодирование; сложение — арифметическое сложение целых двоичных чисел и т. д. Для выполнения каждой из этих операций сконструированы электронные узлы, являющиеся основными узлами вычислительных машин — регистры, счётчики, сумматоры, преобразователи кодов и т. д.

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

+110.

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

Для дальнейшего рассмотрения необходимо знать условные обозначения базовых логических элементов.

Простейшие логические элементы, изображённые выше, можно реализовать аппаратно. Это означает, что можно создать электронные устройства на транзисторах, резисторах и т. п., каждый из которых имеет один или два входа для подачи управляющих напряжений и один выход, напряжение на котором определяется соответствующей таблицей истинности. На практике логическому «да» («истина», или цифра 1 в таблицах истинности) соответствует наличие напряжения, логическому «нет» («ложь», или цифра 0) — его отсутствие.

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

Простейший вариант триггера собирается из четырёх логических элементов И-НЕ, причём два из них играют вспомогательную роль. Триггер имеет два входа, обозначенные на схеме R и S, а также два выхода, помеченные буквой Q — прямой и инверсный (черта над Q у инверсного выхода означает отрицание). Триггер устроен таким образом, что на прямом и инверсном выходах сигналы всегда противоположны.

Как же работает триггер? Пусть на входе R установлена 1, а на S — 0. логические элементы D1 и D2 инвертируют эти сигналы, т. е. меняют их значения на противоположные. В результате на вход элемента D3 поступает 1, а на D4 — 0. Поскольку на одном из входов D4 есть 0, независимо от состояния другого входа на его выходе (он является инверсным выходом триггера) обязательно установится 1. Эта единица передаётся на вход элемента D3 и в сочетании с 1 на другом входе порождает на выходе D3 логический 0. Итак, при R=1 и S=0 на прямом выходе триггера устанавливается 0, а на инверсном — 1.

Обозначение состояния триггера по договорённости связывается с прямым выходом. Тогда при описанной выше комбинации входных сигналов результирующее состояние можно условно назвать нулевым: говорят, что триггер «устанавливается в 0» или «сбрасывается. Сброс по-английски называется «Reset», отсюда вход, появление сигнала на котором приводит к сбросу триггера, обычно обозначают буквой R.

Проведя аналогичные рассуждения для «симметричного» случая R=0 и S=1, мы увидим, что на прямом выходе получится логическая 1, а на инверсном — 0. триггер перейдёт в единичное состояние — «установится» (установка по-английски «Set»).

Теперь рассмотрим наиболее интересную ситуацию R=0 и S=0 — входных сигналов нет. Тогда на входы элементов D3 и D4, связанные с R и S, будет подана 1 и их выходной сигнал будет зависеть от сигналов на противоположных входах. Такое состояние будет устойчивым. Пусть, например, на прямом выходе 1. Тогда наличие единиц на обоих вводах элемента D4 «подтверждает» нулевой сигнал на его выходе. В свою очередь, наличие 0 на инверсном выходе передаётся на D3 и поддерживает его выходное единичное состояние. Аналогично доказывается устойчивость картины и для противоположного состояния триггера, когда Q=0.

Таким образом, при отсутствии входных сигналов триггер сохраняет своё «предыдущее» состояние. Иными словами, если на вход R подать 1, а затем убрать, триггер установится в нулевое состояние и будет сохранять его, пока не поступит сигнал на другой вход S. В последнем случае он перебросится в единичное состояние и после прекращения действия входного сигнала будет сохранять на прямом выходе 1. Из выше сказанного видно, триггер обладает замечательным свойством: после снятия входных сигналов он сохраняет своё состояние, а значит может служить устройством для хранения одного бита информации.

В заключение проанализируем последнюю комбинацию входных сигналов: R=1 и S=1. В этом случае на обоих выходах триггера установится 1! Такое состояние помимо своей логической абсурдности ещё и является неустойчивым: после снятия входных сигналов триггер случайным образом перейдёт в одно их своих устойчивых состояний. Вследствие этого, комбинация R=1 и S=1 никогда не используется на практике и является запрещённой.

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

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

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

Начнём с изучения логической структуры простейшего возможного устройства, являющегося звеном сумматора. Это устройство — полусумматор — реализует сложение двух одноразрядных двоичных чисел, которые обозначим, А и В. В результате получается двухразрядное двоичное число. Его младшую цифру обозначим S, а старшую, которая при сложении многоразрядных чисел будет перенесена в старший разряд, через С0.

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

S=(A^B) (A^B), C0=A^B.

(черта над символом обозначает операцию NOT, знак ^ - конъюнкцию, знак — дизъюнкцию). Это модно проверить перебором всех четырёх возможных случаев сочетания значений, А и В, пользуясь таблицей.

Таблица 4. истинности для полусумматора.

Мысленно объединим столбцы А, В и С. полученная таблица напоминает базовый логический элемент И. аналогично, сравнив первые три столбца А, В и S с имеющимися таблицами истинности для распространённых логических элементов, обнаружим подходящий для наших целей элемент «исключающее ИЛИ». Таким образом, для полусумматора достаточно соединить параллельно входы двух логических элементов.

Логическая схема поусумматора Выше приведены два варианта логической схемы полусумматора: с использованием лишь базовых логических элементов и с использованием логического элемента «исключающее ИЛИ». Видно, что вторая схема существенно проще. Полный одноразрядный сумматор «умеет» при сложении двух цифр учитывать возможное наличие единицы, переносимой из старшего разряда. Обозначим этот «бит переноса» через C .

При построении схемы сумматор удобно представить в виде двух полусумматоров, из которых первый суммирует разряды, А и В, а второй к полученному результату прибавляет бит переноса С .

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

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