Информатика. Теория и практика_Острейковский В.А_2008
.pdfзначений истинности исходных высказываний по следующим соотношениям:
0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 1. |
(2.20) |
Операцию логического сложения по модулю 2 иногда называют строгой дизъюнкцией и обозначают символом « ». В этом случае связка высказывания А и В понимается в смысле «либо… либо», а не в смысле «или». Из соотношения (2.11) видно, что строго разделительное суждение А В истинно лишь в двух случаях: когда А ложно, а В истинно; когда А истинно, а В ложно.
Для логической операции отрицания равнозначности имеют место переместительный и сочетательный законы, а также распределительный закон относительно операции конъ-
юнкции: |
|
À + Â = Â + À; |
(2.21) |
À + (Â + Ñ) = (À + Â) + Ñ; |
(2.22) |
À (Â + Ñ) = (À Â) + (À Ñ) |
(2.23) |
и соотношения: |
|
À À … À = À; |
(2.24) |
À À … À = À. |
(2.25) |
2.5.2. Решение логических задач с помощью алгебры логики
Булева алгебра допускает множество логических операций, но всего трех из них — И, ИЛИ, НЕ — достаточно для того, чтобы выразить любые логические операции, или функции.
Так, с помощью одного элемента ИЛИ на два входа, двух элементов И на два входа и одного элемента НЕ можно построить логическую схему двоичного полусумматора (рис. 2.2), способного осуществлять операцию двоичного сложения двух одноразрядных двоичных чисел (т. е. выполнять правила двоичной арифметики):
0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0.
111
X 1 |
|
Y |
èëè |
èëè |
X |
è |
èëè |
2 |
|
пит Сигнал переноса
Ðèñ. 2.2. Логическая схема двоичного полусумматора
При этом полусумматор выделяет бит переноса. Однако такая схема не содержит третьего входа, на который можно подавать сигнал переноса от предыдущего разряда суммы двоичных чисел. Поэтому полусумматор используется только в младшем разряде логической схемы суммирования многоразрядных дво- ичных чисел, где не может быть сигнала переноса от предыдущего двоичного разряда. Полный двоичный сумматор (рис. 2.3) складывает два многоразрядных двоичных числа с учетом сигналов переноса от сложения в предыдущих двоичных разрядах.
|
сигнал переноса из |
|
|
|
|
предыдущего разряда |
|
|
|
|
двоичный |
èëè |
Y |
|
X 1 |
полусумматор |
|||
|
|
|||
X 2 |
|
|
|
|
|
èëè |
|
|
|
|
èëè |
èëè |
сигнал |
|
|
|
|||
|
èëè |
|
переноса |
|
|
èëè |
в следующий |
||
|
|
|
разряд |
|
|
Ðèñ. 2.3. Логическая схема двоичного сумматора |
|
||
112
Соединяя двоичные сумматоры в каскад, можно получить |
||
логическую схему сумматора для двоичных чисел с любым чис- |
||
лом разрядов. С некоторыми изменениями эти логические схе- |
||
мы применяются для вычитания, умножения и деления двоич- |
||
ных чисел. С их помощью построены арифметические уст- |
||
ройства современных компьютеров. |
|
|
Все описанные логические схемы являются однотактными. |
||
Значения их выходов однозначно определяются значениями их |
||
входов. Фактор времени в них отсутствует. Наряду с ними су- |
||
ществуют многотактные логи- |
|
|
ческие схемы, в которых значе- |
|
|
ния их выходов определяются не |
S |
èëè |
только значениями их входов, |
|
|
|
T |
|
но и их состоянием в преды- |
|
|
|
è |
|
дущем такте. Фактор времени |
|
|
и определяется этими тактами. |
R |
íå |
К таким логическим схемам от- |
||
носятся схемы памяти (рис. 2.4). |
|
питание |
Они строятся с помощью об- |
|
Ðèñ. 2.4. Логическая схема |
ратной связи с выхода на вход |
|
оперативной памяти |
логической схемы. |
|
|
Даже простейшая логическая схема памяти на один бит |
||
обязательно содержит обратную связь с выхода на вход. Она со- |
||
стоит из трех логических элементов, реализующих логические |
||
функции НЕ (отрицание), И, ИЛИ. |
|
|
В этой схеме с помощью обратной связи образуется замкну- |
||
тая цепь с выхода на вход для запоминания входного сигнала. |
||
Эта цепь сохраняется после снятия входного сигнала неограни- |
||
ченное время, вплоть до появления сигнала стирания. |
||
Такая схема памяти имеет еще и другое название: триггер |
||
с раздельными входами — для запоминания (S) и стирания (R). |
||
Широко используется в вычислительной технике и триггер со |
||
счетным входом. Он имеет только один вход и один выход. Та- |
||
кая схема осуществляет деление на 2, т. е. состояние ее выхода |
||
изменяется только после подачи подряд двух входных импуль- |
||
сов. Соединяя триггеры со счетным входом в последовательный |
||
каскад, можно осуществлять деление на 2, 4, 8, 16, 32, 64 и т. д. |
||
Схема оперативной памяти играет важную роль при по- |
||
строении систем управления машинами повышенной опаснос- |
||
113
|
|
схема оперативной памяти |
|
||
èëè |
íå |
èëè |
|
|
|
S 1 |
|
|
|
|
|
S 2 |
|
|
è |
T |
|
R |
íå |
è |
|||
|
|||||
|
|
|
|||
è |
|
ïèò |
|
|
|
|
|
|
|
||
Ðèñ. 2.5. Логическая схема безопасного двуручного управления машинами повышенной опасности
ти, такими, как прессы и одноножевые бумагорезательные машины («гильотины») (рис. 2.5). Чтобы обезопасить руки оператора, такие машины строят с системами двуручного управления. Подобные системы заставляют оператора держать обе руки на кнопках управления во время каждого рабочего цикла машины. Это исключает попадание рук в опасную зону, где происходит прессование детали или резание стопы бумаги.
Приведенный пример еще раз показывает, насколько, казалось бы, абстрактная наука алгебра логики близка к практиче- ской жизни. Она позволяет решать самые разные задачи управления.
Входные и выходные сигналы электромагнитных реле, подобно высказываниям в булевой алгебре, также принимают только два значения. Когда обмотка обесточена, входной сигнал равен нулю, а если по обмотке протекает ток, входной сигнал равен единице. Когда контакт реле разомкнут, выходной сигнал равен нулю, а если контакт замкнут, выходной сигнал равен единице.
Именно это сходство между высказываниями в булевой алгебре и поведением электромагнитных реле заметил известный физик Пауль Эренфест. Еще в 1910 г. он предложил использовать булеву алгебру для описания работы релейных схем в телефонных системах. По другой версии идея использования булевой алгебры для описания электрических переключательных схем принадлежит Ч. Пирсу. В 1936 г. основатель современной теории информации Клод Шеннон в своей докторской диссертации объединил двоичную систему счисления, математиче- скую логику и электрические цепи.
114
Связи между электромагнитными реле в схемах удобно обозначать с помощью логических операций НЕ, И, ИЛИ, повторения (ДА) и т. д. Например, последовательное соединение контактов реле реализует логическую операцию И, а параллельное соединение этих контактов — логическую операцию ИЛИ. Аналогично выполняются операции И, ИЛИ, НЕ в электронных схемах, где роль реле, замыкающих и размыкающих электрические цепи, выполняют бесконтактные полупроводниковые элементы — транзисторы, созданные в 1947—1948 гг. американскими учеными Джоном Бардином, Уильямом Шокли
èУолтером Браттейном.
Âсовременных компьютерах микроскопические транзисторы в кристалле интегральной схемы сгруппированы в системы «вентилей», выполняющих логические операции над дво- ичными числами. Так, с их помощью построены описанные выше двоичные сумматоры, позволяющие складывать многоразрядные двоичные числа, производить вычитание, умножение, деление и сравнение чисел между собой. Логические «вентили», действуя по определенным правилам, управляют движением данных и выполнением инструкций в компьютере.
Òåìà 2.6
ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ. ФУНКЦИОНАЛЬНЫЕ СХЕМЫ ЛОГИЧЕСКИХ УСТРОЙСТВ
Главной причиной, по которой ЭВМ используют не привычную десятичную, а двоичную систему счисления, является то, что в природе встречается множество явлений с двумя устойчивыми состояниями, например: «включено — выключено», «есть напряжение — нет напряжения», «ложное высказывание — истинное высказывание». В то же время явлений с десятью устойчивыми состояниями в природе нет. Почему же десятичная система так широко распространена? Повторим: потому, что у человека на двух руках десять пальцев и их удобно использовать для простого устного счета. Но в ЭВМ гораздо проще использовать двоичную систему счисления всего с двумя устойчивыми состояниями элементов и простейшими таблицами
115
сложения и умножения. В современных ЭВМ двоичная система используется не только для записи чисел, над которыми нужно производить вычислительные операции, но и для записи самих команд этих вычислений и даже целых программ операций. При этом все вычисления и операции сводятся в компьютере к простейшим арифметическим действиям над двоич- ными числами.
Таким образом, в двоичной системе (ее часто называют дво- ичным кодом) с помощью двух цифр можно представить любое число. Простое написание числа в двоичной системе, в отли- чие от десятичной, получается длиннее. Чем больше основание системы счисления, тем запись числа короче, зато таблицы сложения и умножения — длиннее.
Так, таблицы сложения и умножения чисел в двоичной системе счисления — самые короткие из всех возможных; напомним их:
— таблица сложения в двоичной системе счисления:
0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0 и 1 переносится
âследующий старший двоичный разряд;
—таблица умножения в двоичной системе счисления: 0 0 = 0; 0 1 = 0; 1 0 = 0; 1 1 = 1.
Подводя итоги использования алгебры логики в современной ВТ, рассмотрим сводную таблицу логических операций над высказыванием, которые часто называют логическими связками.
Логические связки — это операции, преобразующие тот или иной набор высказываний в более сложные высказывания. То есть логические связки — это логические операции над высказываниями, рассматриваемыми целиком, без учета их внутренней структуры. В формализованных языках логические связки выполняют функции, аналогичные функциям союзов и союзных слов в естественных языках. Так, отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность истолковываются соот-
ветственно как частица íå, ñîþç è, ñîþç èëè, ñîþç åñëè…òî, оборот тогда и только тогда.
Правда, соответствие между логическими связками и союзными словами естественного языка не является вполне адекватным, точным, так как в формализованных языках игнорируются любые смысловые оттенки высказываний и прини-
116
маются во внимание лишь их логические значения «истинно» и «ложно». Кроме того, не для всех логических связок существуют соответствующие союзы и союзные слова естественного языка. Различные подходы к истолкованию, уточнению смысла союзов и союзных слов естественного языка, особенно союзов èëè è åñëè…òî, явились одной из причин развития, наряду с классическими логиками, ряда классических логик. Â алгебре логики логические связки рассматривают как булевы функции, т. е. операции на множестве из двух значений («истинно» и «ложно» или 1 и 0). Константы 0 и 1 рассматриваются как нульместные логические связки. Основной одноместной логической связкой является отрицание. Существует 16 двухместных (бинарных) логических связок. Только 10 из них существенно зависят от обоих аргументов (табл. 2.4), остальные шесть равнозначны нульместным или одноместным логическим связкам.
Таблица 2.4
|
|
|
|
|
Логические связки |
|
|||
|
|
|
|
|
|
|
|
|
|
Îáî- |
Другие |
|
Таблица |
|
|
|
|||
значе- |
истинности |
|
|
||||||
обозначе- |
|
|
|||||||
íèå |
|
|
|
|
|
|
|
||
íèÿ |
x |
0 |
0 |
1 |
1 |
Название связки |
Как читать |
||
ëîãè- |
|||||||||
è ïðåä- |
|
|
|
|
|
|
|
||
ческой |
|
|
|
|
|
|
|
||
ставления |
y |
0 |
1 |
0 |
1 |
|
|
||
связки |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
x & y |
x y |
|
0 |
0 |
0 |
1 |
Конъюнкция, |
x è y |
|
|
x · y |
|
|
|
|
|
логическое |
|
|
|
xy |
|
|
|
|
|
произведение, |
|
|
|
|
|
|
|
|
|
логическое И, |
|
|
|
|
|
|
|
|
|
функция совпадения |
|
|
|
|
|
|
|
|
|
|
|
|
x y |
|
|
0 |
1 |
1 |
1 |
Дизъюнкция, |
x èëè y; ëèáî x, |
|
|
|
|
|
|
|
|
логическая сумма, |
ëèáî y, ëèáî (x è y) |
|
|
|
|
|
|
|
|
логическое ИЛИ, |
|
|
|
|
|
|
|
|
|
функция разделения |
|
|
|
|
|
|
|
|
|
|
|
|
x y |
x y |
|
1 |
1 |
0 |
1 |
Материальная |
åñëè x, òî y; |
|
|
|
|
|
|
|
|
импликация |
x влечет y; |
|
|
|
|
|
|
|
|
|
x имплицирует y |
|
|
|
|
|
|
|
|
|
|
|
x y |
x y |
|
1 |
0 |
0 |
1 |
Эквивалентность, |
x тогда и только |
|
|
x y |
|
|
|
|
|
функция |
тогда y, когда x |
|
|
|
|
|
|
|
|
равнозначности |
эквивалентен y |
|
|
|
|
|
|
|
|
|
|
|
117
Окончание табл. 2.4
Îáî- |
Другие |
|
Таблица |
|
|
|
|||
значе- |
истинности |
|
|
||||||
обозначе- |
|
|
|||||||
íèå |
|
|
|
|
|
|
|
||
íèÿ |
x |
0 |
0 |
1 |
1 |
Название связки |
Как читать |
||
ëîãè- |
|||||||||
è ïðåä- |
|
|
|
|
|
|
|
||
ческой |
|
|
|
|
|
|
|
||
ставления |
y |
0 |
1 |
0 |
1 |
|
|
||
связки |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
x + y |
x y |
|
0 |
1 |
1 |
0 |
Сумма по модулю 2, |
ëèáî x, ëèáî y; x |
|
|
(x y) |
|
|
|
|
|
разделительная |
не эквивалентен y |
|
|
(x y) |
|
|
|
|
|
дизъюнкция, |
|
|
|
|
|
|
|
|
|
отрицание |
|
|
|
|
|
|
|
|
|
эквивалентности, |
|
|
|
|
|
|
|
|
|
функция |
|
|
|
|
|
|
|
|
|
неравнозначности |
|
|
|
|
|
|
|
|
|
|
|
|
x / y |
(x & y) |
|
1 |
1 |
1 |
0 |
Штрих Шеффера, |
x è y несовместны; |
|
|
x y |
|
|
|
|
|
отрицание |
неверно, что x è y |
|
|
|
|
|
|
|
конъюнкции, |
|
||
|
x y |
|
|
|
|
|
|
||
|
|
|
|
|
|
антиконъюнкция |
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
x y |
(x y) |
|
1 |
0 |
0 |
0 |
Стрелка Пирса, |
íè x, íè y |
|
|
x y |
|
|
|
|
|
отрицание |
|
|
|
|
|
|
|
|
дизъюнкции, |
|
||
|
x y |
|
|
|
|
|
|
||
|
|
|
|
|
|
антидизъюнкция |
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
x y |
x y |
|
0 |
0 |
1 |
0 |
Отрицание |
x, íî íå y; |
|
|
(x y) |
|
|
|
|
|
материальной |
неверно, что x |
|
|
(x y) |
|
|
|
|
|
импликации, |
влечет y |
|
|
x & y |
|
|
|
|
|
материальная |
|
|
|
|
|
|
|
|
|
антиимпликация |
|
|
|
|
|
|
|
|
|
|
|
|
x y |
x y |
|
1 |
0 |
1 |
0 |
Обратная |
x, åñëè y; |
|
|
y x |
|
|
|
|
|
импликация |
åñëè y, òî x; |
|
|
y x |
|
|
|
|
|
|
y влечет x |
|
|
|
|
|
|
|
|
|
|
|
x y |
x y |
|
0 |
1 |
0 |
0 |
Отрицание обратной |
íå x, íî y; |
|
|
(y x) |
|
|
|
|
|
импликации, |
неверно, что y |
|
|
(y x) |
|
|
|
|
|
обратная |
влечет x |
|
|
x & y |
|
|
|
|
|
антиимпликация |
|
|
|
|
|
|
|
|
|
|
|
|
Логические операции в ЭВМ реализуются соответствующим набором логических элементов.
Логическими элементами ЭВМ называются технические устройства, осуществляющие элементарные логические операции над входными сигналами. Простейшими логическими элементами служат элементы, выполняющие логические операции
118
И, ИЛИ, НЕ, называемые соответственно конъюнктор, дизъюнктор è инвертор. Логический элемент имеет один выход, а количество его входов равно числу аргументов логической функции. На основе логических элементов строят более сложные логические схемы. Логическая схема — это совокупность логи- ческих элементов, реализующих какую-либо булеву функцию.
Конъюнктор (îò ëàò. conjunctio — |
|
|
|
|
|
|
|
|
|
|
связь) — это логический элемент, реа- |
À |
|
|
|
À |
B |
||||
лизующий логическую функцию конъ- |
B |
|
|
|
||||||
|
|
|
|
|
|
|
|
|||
юнкции И (рис. 2.6), или логическое |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|||
произведение. Конъюнктор выдает сиг- |
|
Ðèñ. 2.6. Элемент И |
|
|||||||
нал на выходе при наличии сигнала хо- |
|
|
||||||||
|
|
|
(конъюнктор) |
|
||||||
тя бы на одном из входов. |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
||
Дизъюнктор (îò ëàò. disjunctio — ðà- |
|
|
|
|
|
|
|
|
|
|
зобщение, обособление) — это логиче- |
|
|
|
|
|
|
|
|
|
|
ский элемент, реализующий логическую |
R |
|
|
|
|
|
|
R |
S |
|
|
|
|
|
|
|
|||||
функцию ИЛИ (рис. 2.7), или логиче- |
|
|
|
|
|
|
|
|||
S |
|
|
|
|
|
|
|
|
||
скую сумму. Дизъюнктор выдает сигнал |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|||
на выходе при одновременной подаче |
Ðèñ. 2.7. Элемент ИЛИ |
|||||||||
сигналов на все его выходы и не выдает |
||||||||||
|
|
|
(дизъюнктор) |
|
||||||
выходной сигнал, если не возбужден |
|
|
|
|
|
|
|
|
|
|
хотя бы один из его входов. |
|
|
|
|
|
|
|
|
|
|
Инвертор (от лат. inverto — повора- |
|
|
|
|
|
|
|
|
|
|
чиваю, переворачиваю) — это логиче- |
R |
|
|
|
|
|
|
|
|
|
ский элемент, реализующий логическую |
|
|
|
|
|
|
R |
S |
||
|
|
|
|
|
|
|||||
функцию НЕ (отрицание) (рис. 2.8). Раз- |
S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
личают потенциальные и импульсные |
|
|
|
|
|
|
|
|
|
|
инверторы. В потенциальном инверто- |
|
Ðèñ. 2.8. Элемент НЕ |
||||||||
ре высокий уровень входного напряже- |
|
(инвертор) |
|
|||||||
|
|
|
|
|
|
|
|
|
||
ния преобразуется в низкий и наоборот. В импульсном инверторе в момент
подачи сигнала на вход появляется сигнал противоположной полярности на его выходе.
Таким образом, логический элемент — это электронная схема, реализующая элементарную логическую функцию. На основе логических элементов строят более сложные электронные схемы: триггеры, регистры, переключатели, счетчики, сумматоры, шифраторы, дешифраторы и др.
119
Установка 0 |
|
|
|
|
Выход 0 |
Триггер (îò àíãë. trigger — çà- |
|
|
|
0 |
|
||||
|
|
|
|||||
Установка 1 |
|
|
|
|
|
Выход 1 |
щелка, спусковой механизм) — |
|
|
1 |
|
|
|||
|
|
|
|
||||
|
|
|
|
|
|
|
логическая схема, обеспечиваю- |
Ðèñ. 2.9. Триггер |
|
|
|||||
|
|
щая два устойчивых состояния |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(рис. 2.9). Переход триггера из |
одного устойчивого состояния в другое осуществляется скач- ком и только под воздействием пускового импульса, подаваемого на один из входов триггера. Так же скачком изменяется уровень напряжения на выходе электронной схемы. Каждый триггер используется для запоминания одного разряда двоич- ного числа (0 или 1). Триггер можно построить как самостоятельную электронную схему, а можно реализовать на
основе элементарных логических элементов.
Регистр (от лат. registrum — список, перечень) — совокупность элементов, предназначенная для приема, временного (оперативного) хранения и выдачи информации в виде мощного слова (здесь термин «слово» используется только для обозначения ячейки памяти ЭВМ).
Чаще всего информация в регистры вводится параллельно, т. е. все биты записываются одновременно. Парал-
лельный регистр изображен на рис. 2.10 (жирной стрелкой показано наличие нескольких информационных входов, служащих для ввода информации в регистр).
Последовательный регистр
Âõîä |
|
|
|
Выход |
может принимать и передавать |
||||
|
|
||||||||
|
|
|
|
|
|
|
|
в каждый момент времени толь- |
|
|
|
|
|
|
|
|
|
||
Сдвиг |
|
|
|
|
|
|
ко 1 бит информации. Графи- |
||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
ческое изображение последо- |
|
Ðèñ. 2.11. Последовательный |
|||||||||
вательного регистра приведено |
|||||||||
|
|
|
|
регистр |
|
|
íà ðèñ. 2.11. |
||
|
|
|
|
|
|
|
|
||
Промежуточным вариантом является последовательно-па- раллельный регистр, в котором запись и считывание информации происходят в один и тот же интервал времени. Так как
120