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

Алгебра логики – это раздел математики, изучаю­щий высказывания, рассматриваемые со стороны их логи­ческих значений (истинности или ложности) и логических опера­ций над ними.

Алгебра логики возникла в середине ХIХ века в тру­дах английского математика Джорджа Буля. Ее созда­ние представляло собой попытку решать традиционные логиче­ские задачи алгебраическими методами.

Логическое высказывание – это любое повество­ва­тельное пpедлoжение, в oтнoшениикoтopoгo можно oднoзначнo сказать, истинно оно или лoжнo.

Так, например, предложение " 6 – четное число " сле­дует считать высказыванием, так как оно истинное. Пред­ложение " Рим – столица Франции " тоже высказыва­ние, так как оно ложное.

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

Предложения типа " в городе A более миллиона жи­телей ", " у него голубые глаза " не являются высказыва­ниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно го­роде или человеке идет речь. Такие предложения называ­ются выска­зывательными формами.

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Заметим, что зачастую трудно установить ис­тинность высказывания. Так, например, высказывание " площадь поверхности Индийскогоокеана равна 75 млн кв. км " в одной ситуации можно посчитать ложным, а в дру­гой – истинным.

Ложным – так как указанное значение неточное и во­обще не является постоянным.

Истинным – если рассматривать его как некоторое приближение, при­емлемое на практике.

Употребляемые в обычной речи слова и словосоче­та­ния "не", "и", "или", "если..., то", "тогда и только то­гда" и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочета­ния назы­ваются логическими связками.

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

Так, например, из элементарных высказываний " Петров – врач ", " Петров – шахматист " при помощи связки " и " можно получить составное высказывание " Пет­ров – врач и шахматист ", понимаемое как " Петров – врач, хорошо играющий в шахматы ".

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

Истинность или ложность получаемых таким обра­зом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть черезА обозначено высказыва­ние "Тимур поедет летом на море", а через В – высказы­вание "Тимур летом отправится в горы". Тогда составное выска­зывание "Тимур летом побывает и на море, и в го­рах" можно кратко записать какА и В. Здесь "и" – логическая связка, А, В – логические переменные, ко­торые могут при­нимать только два значения – "истина" или "ложь", обозна­чаемые, соответственно, "1" и "0".

Каждая логическая связка рассматривается как опе­рация над логическими высказываниями и имеет свое на­звание и обозначение:

НЕ Операция, выражаемая сло­вом "не", называется отрицанием и обозначается чертой над высказыванием (или знаком Ø). Высказывание ис­тинно, когда A ложно, и ложно, когда A истинно. При­мер. " Луна – спутник Земли " (А); " Луна – не спутник Земли " ().

И Операция, выражаемая связ­кой "и" называется конъюнкцией (лат. conjunctio – со­единение) или логическим умножением и обозначается точкой" " (может также обозна­чаться знаками Ù или &).

ВысказываниеАÙВ истинно тогда и только тогда, ко­гда оба высказывания А и В истинны. Например, высказыва­ние "10 делится на 2 и 5 больше 3" истинно, а высказы­вания "10 делится на 2 и 5 не больше 3", "10 не де­лится на 2 и 5 больше 3", "10 не делится на 2 и 5 не больше 3" – ложны.

ИЛИ Операция, выражаемая связкой "или" (в не­ис­ключающем смысле этого слова), называ­ется дизъюнкцией (лат. disjunctio – разделение) или логи­ческим сложением и обозначается знаком Ú (или плюсом).

ВысказываниеАÚ В ложно тогда и только тогда, ко­гда оба высказывания А и В ложны. Например, высказыва­ние "10 не делится на 2 или 5 не больше 3" ложно, а вы­ска­зывания "10 делится на 2 или 5 больше 3", "10 делится на 2 или 5 не больше 3", "10 не делится на 2 или 5 больше 3" – истинны.

ЕСЛИ-ТО Операция, выражаемая связками "если..., то", "из... следует", "... влечет...", называ­ется импликацией (лат. implico – тесно связаны) и обозна­чается знаком ®.

Высказывание A®B ложно тогда и только тогда, ко­гдаА истинно, а В ложно.

Каким же образом импликация связывает два эле­ментарных высказывания? Покажем это на примере выска­зываний: "данный четырёхугольник — квадрат" (А) и "около данного четырёхугольника можно описать ок­руж­ность" (В). Рассмотрим составное высказыва­ние A®B, понимаемое как "если данный четырёхуголь­ник квадрат, то около него можно описать окруж­ность".

Есть три варианта, когда высказывание A®B ис­тинно:

1. А истинно иВистинно, то есть данный четы­рёх­угольник квадрат, и около него можно описать окруж­ность;

2. А ложно иВистинно, то есть данный четырёх­уголь­ник не является квадратом, но около него можно опи­сать окружность (разумеется, это справедливо не для вся­кого четырёхугольника);

3. A ложно и B ложно, то есть данный четырёх­уголь­ник не является квадратом, и около него нельзя опи­сать окружность.

Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадра­том, но около него нельзя описать окружность.

В обычной речи связка "если..., то" описывает при­чинно-следственную связь между высказываниями. Но в ло­гических операциях смысл высказываний не учитыва­ется. Рассматривается только их истинность или ложность. По­этому не надо смущаться "бессмысленностью" импли­каций, образованных высказываниями, совершенно не свя­занными по содержанию. Например, такими: "если прези­дент США – демократ, то в Африке водятся жирафы", "если арбуз – ягода, то в бензоколонке есть бензин".

РАВНОСИЛЬНО. Операция, выражаемая связками " тогда и только тогда ", " необходимо и достаточно ", "... равносильно...", называется эквиваленцией или двой­ной импликацией и обозначается знаком или Вы­сказывание истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывания "24 делится на 6 то­гда и только тогда, когда 24 делится на 3", "23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны, а высказывания "24 делится на 6 тогда и только тогда, ко­гда 24 делится на 5", "21 де­лится на 6 тогда и только то­гда, когда 21 делится на 3" ложны.

ВысказыванияА и В, образующие составное выска­зывание , могут быть совершенно не связаны по содер­жанию, например: "три больше двух" (А), "пин­гвины живут в Антарктиде" (В). Отрицаниями этих вы­сказыва­ний являются высказывания "три не больше двух" (), "пин­гвины не живут в Антарктиде" (). Образованные из выска­зыванийА и В составные высказы­вания и истинны, а высказывания и – ложны.

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

Импликацию можно выразить через дизъюнкцию и отрицание: .

Эквиваленцию можно выразить че­рез отрицание, дизъюнкцию и конъюнкцию: .

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

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок до­говорились считать, что сначала выполняется операция от­рицания ("не"), затем конъюнкция ("и"), после конъюнк­ции – дизъюнкция ("или") и в последнюю очередь – им­пликация.

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

Определение логической формулы:

1. Всякая логическая переменная и символы "ис­тина" ("1") и "ложь" ("0") – формулы.

2. Если А и В – формулы, то , А В, А В, А B, А В – формулы.

Никаких других формул в алгебре логики нет.

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде . Такая же формула соответствует высказыванию "если Игорь знает английский или японский язык, то он получит место переводчика".

Как показывает анализ формулы , при оп­ределённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других соче­таниях – значение "ложь" (разберите само­стоятельно эти случаи). Такие формулы называ­ются выполнимыми.

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них пере­мен­ных. Таковой будет, например, формула , соответ­ствую­щая высказыванию "Этот треугольник пря­моуголь­ный или косоугольный". Эта формула истинна и то­гда, когда треугольник прямоугольный, и тогда, когда тре­угольник не прямоугольный. Такие формулы называ­ются тождественно истинными форму­лами или тавтологиями. Высказывания, которые форма­лизуются тавтологиями, называются логиче­ски истин­ными высказываниями.

В качестве другого примера рассмотрим фор­му­лу , которой соответствует, например, высказыва­ние "Катя самая высокая девочка в классе, и в классе есть де­вочки выше Кати". Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие фор­мулы назы­ваются тождественно ложными форму­лами или проти­воречиями. Высказывания, которые фор­мализуются проти­воречиями, называются логически ложными высказыва­ниями.

Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них перемен­ных, принимают одинаковые значения, то они называ­ются равно­сильными.

Равносильность двух формул алгебры логики обо­значается символом "=" или символом " " Замена фор­мулы другой, ей равносильной, называется равносильным преоб­разованием данной формулы.

Математический аппарат алгебры логики очень удо­бен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счис­ления в компьютере является двоичная, в которой исполь­зуются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”.

Из этого следует два вывода:

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

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

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

 

Рисунок 5 – Кодирование информации

Логический элемент компьютера – это часть элек­тронной логической схемы, которая реализует элемен­тар­ную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И–НЕ, ИЛИ–НЕ и дру­гие (называемые также вентилями), а также триггер.

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

Чтобы представить два логических состояния – “1” и “0” в вентилях, соответствующие им входные и выход­ные сигналы имеют один из двух установленных уровней на­пряжения. Например, +5 вольт и 0 вольт.

Высокий уровень обычно соответствует значению “истина” (“1”), а низкий – значению “ложь” (“0”).

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

Работу логических элементов описывают с помо­щью таблиц истинности.

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

Схема И. Схема И реализует конъюнкцию двух или более ло­гических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено (рисунок 6).

 

Рисунок 6 – Логический элемент И

 

Таблица 3. Таблица истинности схемы И

х	y	x y

 

Единица на выходе схемы И будет тогда и только то­гда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x y (читается как"x и y"). Операция конъюнкции на структурных схемах обозна­чается знаком "&" (читается как "амперсэнд"), являю­щимся сокра­щенной записью английского слова and.

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

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами. Знак"1"на схеме – от устаревшего обозначения дизъ­юнкции как ">=1" (т.е. значение дизъюнк­ции равно еди­нице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как"x или y") на рисунке 7.

 

Рисунок 7 – Логический элемент ИЛИ

 

Таблица 4. Таблица истинности схемы ИЛИ

x	y	x v y

 

Схема НЕ. Схема НЕ (инвертор) реализует операцию отрица­ния. Связь между входом x этой схемы и выходом z можно записать соотношением z= , xгде читается как "не x" или "инверсия х".

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение на струк­турных схемах инвертора – на рисунке 8.

 

Рисунок 8 – Логический элемент НЕ

 

Таблица 5. Таблица истинности схемы НЕ

x

Схема И-НЕ. Схема И-НЕсостоит из элементаИи инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и y схемы записывают следующим образом: , где читается как "инвер­сия x и y". Условное обозначение на структурных схемах схемы И-НЕ с двумя входами представлено на рисунке 9.

Рисунок 9 – Логический элемент И-НЕ

 

Таблица 6. Таблица истинности схемы И- НЕ

 

x	y

Схема ИЛИ-НЕ. Схема ИЛИ-НЕсостоит из элемента ИЛИ и ин­вертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: , где , чита­ется как "инверсия x или y". Условное обо­значение на структурных схемах схемы ИЛИ-НЕ с двумя входами пред­ставлено на рисунке 10.

 

Рисунок 10 – Логический элемент ИЛИ-НЕ

 

Таблица 7. Таблица истинности схемы ИЛИ-НЕ

 

x	y

 

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

Термин триггерпроисходит от английского слова trigger – защёлка, спусковой крючок. Для обозна­чения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает “хлопанье”. Это звукоподра­жательное название электронной схемы указы­вает на её способность почти мгновенно переходить (“пе­ребрасы­ваться”) из одного электрического состояния в другое и на­оборот.

Самый распространённый тип триггера – так назы­ваемый RS-триггер (S и R, соответственно, от англий­ских set – установка, и reset – сброс). Условное обозна­чение триг­гера – на рисунок 11.

 

Рисунок 11 – Логический элемент RS-триггер

 

Он имеет два симметричных входа S и R и два сим­метричных выхода Q и , причем выходной сигнал Q явля­ется логическим отрицанием сигнала .

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

Наличие импульса на входе будем считать едини­цей, а его отсутствие – нулем.

На рисунке 12 показана реализация триггера с помо­щью вентилей ИЛИ-НЕ и соответствующая таблица ис­тин­ности.

Рисунок 12 – Логический элемент RS-триггер

на элементах ИЛИ-НЕ

 

Таблица 8. Таблица истинности RS-триггер

S	R	Q
		запрещено
		хранение бита

Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу ис­тинности схемы ИЛИ-НЕ (таблица 8).

1. Если на входы триггера подать S=“1”, R=“0”, то (не­зависимо от состояния) на выходе Q верхнего вен­тиля появится “0”. После этого на входах нижнего вентиля ока­жется R=“0”, Q=“0” и выход станет равным “1”.

2. Точно так же при подаче “0” на вход S и “1” на вход R на выходе появится “0”, а на Q – “1”.

3. Если на входы R и S подана логическая “1”, то со­стояние Q и не меняется.

4. Подача на оба входа R и S логического “0” может привести к неоднозначному результату, поэтому эта комби­нация входных сигналов запрещена.

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответст­венно, 8 2¹⁰ = 8192 триггеров. Современные микросхемы па­мяти содержат миллионы триггеров.

Сумматор – это электронная логическая схема, вы­полняющая суммирование двоичных чисел.

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

Многоразрядный двоичный сумматор, предназна­чен­ный для сложения многоразрядных двоичных чи­сел, представляет собой комбинацию одноразрядных сум­маторов, с рассмотрения которых мы и начнём. Условное обозначение одноразрядного сумматора на рисунке 13.

 

Рисунок 13 – одноразрядного сумматора

 

При сложении чисел A и B в одном i -ом разряде при­ходится иметь дело с тремя цифрами:

- цифра a _i первого слагаемого;

- цифра b _i второго слагаемого;

- перенос p _i–1 из младшего разряда.

В результате сложения получаются две цифры:

- цифра c _i для суммы;

- перенос p _i из данного разряда в старший.

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

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

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

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

 

Таблица 9. Таблица истинности одноразрядного дво­ичного сумматора

Входы	Выходы
Первое слагаемое	Второе слагаемое	Перенос	Сумма	Перенос

 

Для формулы, которая содержит две переменные, та­ких наборов значений переменных всего четыре:

(0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то воз­мож­ных наборов значений переменных восемь:

(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя пере­менными равно шестнадцати и т.д.

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

 

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

Закон	Для ИЛИ	Для И
Перемести­тельный
Сочета­тельный
Распреде­ли­тельный
Правила де Мор­гана
Идемпотен­ции
Поглоще­ния
Склеива­ния
Операция перемен­ной с ее инвер­сией
Операция с констан­тами
Двойного отрицания