Логические основы ЭВМ

Тема 4. Логические основы ЭВМ.

  1. Основы математической логики; логические законы.
    1. Основные логические элементы; логические схемы.
    2. Полусумматор, сумматор.
    3. Триггер.

4.1. Основы математической логики; логические законы.

Формальная логика – наука о законах и формах мышления. Основателем формальной логики является Аристотель.

Основными формами мышления являются понятие, суждение и умозаключение.

Понятие – форма мышления, которая выделяет существенные признаки предмета или класса предметов, отличающие его от других.

Суждение – форма мышления, утверждение, в котором что-то утверждается или отрицается.

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

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

Высказывание – это повествовательное предложение, о котором всегда можно сказать, истинно оно или ложно. (Пример: «На улице идет дождь», «2 * 2 = 4»).

Высказывания делятся на общие (обо всех объектах данного класса), частные (о некоторых объектах данного класса) и единичные (об одном конкретном объекте).

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

Предикат – это утверждение о переменных. (Пример: «х + у = 10»).

Предикаты можно преобразовать в суждения двумя способами: 1) подставить конкретные числовые значения; 2) с помощью кванторов существования и всеобщности.

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

Операция

Обозначение

Правило

Инверсия (отрицание)

, , не А

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

Конъюнкция (логическое умножение)

, ,

, А и В

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

Дизъюнкция (логическое сложение)

, ,

А или В

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

Строгая дизъюнкция (исключающее или)

, А или В

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

Импликация

, , Если А, то В

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

Эквивалентность

, ,

А тогда и только тогда, когда В

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

А

В

0

0

1

0

1

0

1

1

0

1

1

0

1

1

1

0

1

0

0

0

1

1

0

0

1

1

0

1

0

0

1

1

Логическая функция – сложное логическое выражение, составленное из логических переменных, значение которого 0 или 1.

Пример. А – «Я поеду в Москву»

В – «Встречу друзей»

С – «Мы весело проведем время»

1) Я поеду в Москву, и если встречу друзей, то мы весело проведем время.

2) Я поеду в Москву, встречу друзей и мы весело проведем время.

3) Если я поеду в Москву и встречу друзей, то мы весело проведем время.

4) Я не поеду в Москву, но встречу друзей и мы весело проведем время.

5) Мы весело проведем время тогда и только тогда, когда я поеду в Москву или встречу друзей.

Таблица истинности – таблица со всеми возможными значениями входных переменных и соответствующими им значениями функции.

Количество строк – 2n; количество столбцов – n+k; где n – количество переменных, k – количество операций.

Пример. Построить таблицу истинности для функции

А

В

С

0

0

0

1

1

1

0

1

1

0

0

1

1

1

1

1

0

0

0

1

0

0

0

1

0

1

1

0

1

1

0

0

1

1

0

1

1

0

0

1

1

0

0

1

1

1

0

1

1

1

0

0

1

1

1

1

0

0

1

0

0

1

1

1

1

1

0

1

0

0

1

1

Логические законы:

1. Закон двойного отрицания: отрицание от отрицания суждения есть само суждение.

2. Закон исключения третьего: всегда истинно либо суждение, либо его отрицание.


3. Закон противоречия: не могут быть одновременно истинны суждение и его отрицание.

4. Закон коммутативности (переместительный закон):

5. Закон ассоциативности (сочетательный закон):

6. Закон дистрибутивности (распределительный закон)

7. Законы де Моргана:

8. Закон идемпотентности:

9. Действия с логическими константами:

10. Формулы замены операций:

4.2. Основные логические элементы; логические схемы.

Электронный логический элемент – это электронное устройство, реализующее одну из логических операций И, ИЛИ, НЕ. В зависимости от типа элемента на его вход подается один или несколько входных сигналов, а на выходе снимется один выходной сигнал.

Логическая схема, составленная из логических элементов, реализует логическую функцию.

Элементы, реализующие логические операции И, ИЛИ, НЕ, называются базовыми логическими элементами.

Логический элемент И (конъюнктор)

Логический элемент ИЛИ (дизъюнктор)

Логический элемент НЕ (инвентор)

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

4.3. Полусумматор, сумматор.

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

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

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

Общая схема сумматора:

Одноразрядный двоичный сумматор на два входа и два выхода называется одноразрядным полусумматором (самый правый на приведенном рисунке). В двоичной системе счисления операция сложения двух двоичных чисел в одном разряде осуществляется по правилу:

Х

Y

Перенос Р

Сумма S

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

Формулы для разряда суммы и разряда переноса: ,

Схема соединения логических элементов полусумматора:

Одноразрядный двоичный сумматор на три входа и два выхода называется полным одноразрядным сумматором.

Работа одноразрядного двоичного сумматора может быть описана следующей таблицей истинности, где X,Y – входы, через которые он воспринимает двоичные цифры; P – перенос из соседнего разряда; S – сумма в данном разряде; Q – перенос в следующий разряд:

Входы

Выходы

Х

Y

Р

S

Q

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

4.4. Триггер.

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

Самый распространенный тип триггера – это RS-триггер. Триггер имеет два симметричных входа S и R, которые используются для установки в единичное состояние и сброса, - в нулевое. Еще у него есть два симметричных выхода Q и .

За единичное состояние триггера условились принимать такое, при котором Q = 1. На каждый из входов S и R могут подаваться входные сигналы в виде кратковременных импульсов. Наличие импульса на входе считается единицей, а его отсутствие – нулем.

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

1. Пусть поданы сигналы S=1, R=0. Независимо от состояния другого входа на выходе верхнего элемента появится 0. этот нулевой сигнал подается на вход нижнего элемента, где уже есть R=0. Выход нижнего элемента станет равным 1. Эта единица возвращается на вход первого элемента. Теперь состояние другого входа (S) этого элемента роли не играет: если даже убрать входной сигнал S, состояние триггера останется без изменения. Так как Q=1, триггер перешел в единичное состояние, устойчивое, пока не придут новые внешние сигналы.

2. При S=0 и R=1 вследствие симметричности схемы все происходит аналогично, но теперь на выходе Q будет 0. То есть при подаче сигнала на вход R триггер сбрасывается в устойчивое нулевое состояние.

3. При окончании действия обоих сигналов (R=0 и S=0) триггер сохраняет на выходе Q тот сигнал, который был установлен входным импульсом S или R.

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

Один триггер хранит один бит информации.

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

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

Однако статическая память имеет более высокое быстродействие. Кэш-память имеет статическую природу, что позволяет согласовать высокое быстродействие процессора и низкую скорость работы динамической памяти.

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

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

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

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

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

сумматор – регистр АЛУ, способный производить сложение, участвует в выполнении каждой арифметической операции;

сдвиговый регистр – предназначен для выполнения операции сдвига;

счетчики – схемы, способные считать поступающие на вход импульсы;

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

регистр команд – регистр УУ для хранения кода команды на период времени, необходимый для ее выполнения. Часть его разрядов используется для хранения кода операции, остальные – для хранения кодов адресов операндов.

PAGE 7


EMBED Equation.3

A&B

B

A

&

1

A

B

A\/B

A

EMBED Equation.3

EMBED Equation.3

EMBED Equation.3

R

S

1

1

…

Pn

Sn

Y1

Pn-1

P2

S2

P1

P1

S1

Yn

Y2

Х2

Х1

Хn

S

P

Y

&

1

&

X

Q

S

P

Y

X

1

&

1

1

&

&

&

&

Логические основы ЭВМ