Информационные основы вычислительной техники

Информационные основы вычислительной техники

2-е издание, исправленное

Гуров В.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Информационные основы вычислительной техники/ В.В. Гуров - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

В пособии приводятся основные понятия алгебры логики. Особое внимание уделяется тем
элементарным логическим функциям, которые находят наибольшее распространение в ЭВМ:
конъюнкция, дизъюнкция, штрих Шеффера, стрелка Пирса, сумма по модулю два и их основным
эквивалентностям.
Рассматриваются различные подходы к одному из важнейших для вычислительной техники вопросов
математической логики – минимизации логических функций. Рассмотрены вопросы минимизации
функций алгебры логики на основе теоремы Квайна, минимизирующих карт (диаграмм Вейча),
метода Квайна – МакКласки, а также минимизации не полностью определённых логических
функций. Дано схемотехническое представление элементов, выполняющих основные операции
функций алгебры логики, а также некоторых других основных элементов ЭВМ, знание
функционирования которых позволит лучше понять выполнение арифметических операций в
компьютере, а также функционирование компьютера в целом. Учебное пособие предназначено для
студентов-бакалавров, по направлениям «Информатика и вычислительная техника», «Программная
инженерия», «Информационная безопасность», студентов, обучающихся по специальности
«Применение и эксплуатация автоматизированных систем специального назначения» и схожим
направлениям и специальностям на начальном периоде обучения.

(c) ООО “ИНТУИТ.РУ”, 2018-2016
(c) Гуров В.В., 2018-2016

3

Основные понятия алгебры логики. Функции алгебры логики.
Основные логические эквивалентности

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

Предисловие

Учебное пособие предназначено для студентов-бакалавров, по направлениям
“Информатика и вычислительная техника”, “Программная инженерия”,
“Информационная безопасность”, студентов, обучающихся по специальности
“Применение и эксплуатация автоматизированных систем специального назначения” и
схожим направлениям и специальностям на начальном периоде обучения.

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

Для изучения данного учебного пособия, с одной стороны, не требуется каких-либо
специальных знаний, но, с другой стороны, пособие призвано показать, как
традиционные понятия и алгоритмы, преломляются при проектировании реальных
вычислительных устройств в зависимости от тех целей, которые перед этим
устройством ставятся: минимизация оборудования или используемой элементной базы,
минимизация времени выполнения какой-либо команды или упрощения используемого
устройства управления, АЛУ и других критериев.

В пособии приводятся основные понятия алгебры логики. Особое внимание уделяется
тем элементарным логическим функциям, которые находят наибольшее
распространение в ЭВМ: конъюнкция, дизъюнкция, штрих Шеффера, стрелка Пирса,
сумма по модулю два и их основным эквивалентностям.

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

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

4

При рассмотрении арифметических основ ЭВМ даны понятия системы счисления,
определены правила перевода смешанных чисел между различными системами
счисления. Особое внимание уделено часто встречающемуся в вычислительной
технике механизму быстрого перевода чисел между системами счисления с
основаниями, связанными между собой соотношениями p = q±2, например, 16=24.
Представлены диапазоны, погрешности и, соответственно, области применения чисел с
фиксированной запятой, фиксированной точкой, плавающей запятой.

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

Весь материал проиллюстрирован большим количеством примеров, которые позволят
на практике закрепить изложенные в пособии теоретические положения.

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

Основные определения математической логики

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

Высказывания бывают простыми и сложными. Простые отдельные высказывания – это
логические переменные, их принято обозначать буквами латинского алфавита.
Логическая (булева) переменная –эта такая величина x, которая может принимать
только два значения: “Истина” или “Ложь”. Например, если простое высказывание x
истинно, то x = true, если же ложно, то x = false.

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

x = 1, если высказывание истинно, и

x = 0, если высказывание ложно.

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

Функция ƒ(x1, x2, …, xn) называется логической (переключательной), или булевой,
если она, так же как и ее аргументы xi, может принимать только два значения: “истина”
или “ложь”.

Логические функции могут быть описаны различными способами:

5

в виде таблицы истинности;
совершенными нормальными формами;
в виде формулы.

Рассмотрим эти формы представления функции алгебры логики (ФАЛ).

Чаще всего встречаются табличная форма представления логической функции (в виде
таблицы истинности) и ее аналитическое представление (например, в виде
дизъюнктивных или конънктивных форм). Рассмотрим некоторые формы
представления ФАЛ.

Представление логической функции в виде таблицы истинности

Прежде всего, определимся с понятием “элементарная логическая функция”. Чаще
всего,это понятие в литературе никак не расшифровывается. В дальнейшем мы будем
понимать под “элементарной логической функцией” ФАЛ от аргументов, каждый из
которых, в свою очередь, не является логической функцией и которые имеют своё
собственное обозначение.

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

Все возможные элементарные логические функции от одной переменной представлены
в Табл. 1.1:

Таблица 1.1. Логические функции одной переменной

Функция
x
Наименование функции Обозначение функции
x=0 x=1

ƒ0
0
0
Константа “ноль”
ƒ(x)=0

ƒ1
0
1
Тождественная функция ƒ(x)=x

ƒ2
1
0
Отрицание

ƒ3
1
1
Константа “единица”
ƒ(x)=1

Здесь интерес представляет лишь одна функция – отрицание. Опишем ее основные
свойства:

Последнее свойств можно описать как “отрицание отрицания есть утверждение”.

Все возможные логические функции от двух переменных представлены в Табл. 1.2:

Таблица 1.2. Логические функции двух переменных

Значение функции на наборах
Наименование функции Обозначение

6

№

функции

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

x=0

y=0

x=1

y=0

x=0

y=1

x=1

y=1

ƒ0

0
0
0
0
Константа “ноль”
ƒ(x,y)=0

ƒ1

0
0
0
1
Конъюнкция

ƒ(x,y)=x&y

ƒ(x,y)=xy

ƒ2

0
0
1
0
Запрет по y
xΔy

ƒ3

0
0
1
1
x
ƒ(x,y)=x

ƒ4

0
1
0
0
Запрет по x
yΔx

ƒ5

0
1
0
1
y
ƒ(x,y)=y

ƒ6

0
1
1
0
Сумма по
mod2(неравнозначность)

ƒ7

0
1
1
1
Дизъюнкция

ƒ(x,y)=x v y

ƒ(x,y)=x+y

ƒ8

1
0
0
0
Стрелка Пирса (Вебба)

ƒ(x,y)=x↓y

ƒ(x,y)=xОy

ƒ9

1
0
0
1
Равнозначность

ƒ(x,y)=x≡y

ƒ(x,y)=x∞y

ƒ10

1
0
1
0
Инверсия y

ƒ(x,y)=^y

7

ƒ11

1
0
1
1
Импликация от y к x
ƒ(x,y)=y→x

ƒ12

1
1
0
0
Инверсия x

ƒ(x,y)=^x

ƒ13

1
1
0
1
Импликация от х к y
ƒ(x,y)=x→y

ƒ14

1
1
1
0
Штрих Шеффера
ƒ(x,y)=x/y

ƒ15

1
1
1
1
Константа “единица”
ƒ(x,y)=1

Общее количество функций от n переменных равно: 

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

В первом случае переменную называют фиктивной, а во втором – существенной.

Так, например, для функции ƒ12(x,y) логическая переменная x является существенной,
а логическая переменная y – фиктивной.

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

Эквивалентность ФАЛ.

Логические функции являются эквивалентными, если их значения совпадают для всех
допустимых наборов аргументов. Так как аргументами ФАЛ являются логические
переменные, которые могут принимать только два значения (“Истина” либо “Ложь”,
которые, как было сказано выше, обычно обозначаются “1” и “0”), то доказательство
эквивалентности логических функций сводится к сравнению их таблиц истинности.

Конъюнкция

Таблица

истинности
х y x&y

8

0 0
0 1 0
1 0 0
1 1 1

Основные свойства:

0 & 0 = 0

0 & 1 = 0

1 & 1 = 1

0 & x = 0

1 & x = x

x & x &…& x = x

x & y = y & x

x & y & z = (x & y) & z = x & (y & z)

Для более легкого запоминания этой функции следует придерживаться правила:
функция конъюнкции ложна, если ложен хотя бы один из ее операндов. Это правило
действует для функции, содержащей произвольное число операндов. Если обозначать
значение “истина” как “1”, а значение “ложь” как “0”, то эта функция будет похожа на
математическую функцию умножения. Поэтому ее зачастую называют функцией
логического умножения.

Отметим, что для конъюнкции, так же как и для следующей рассматриваемой функции
– дизъюнкции – действуют ассоциативный (сочетательный) и коммуникативный
(переместительный) законы.

В то же время для некоторых других логических функций тот или иной закон не
действует. Некоторые из примеров таких функций мы рассмотрим ниже.

Покажем, например, что 
.

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

Но в данном случае можно поступить проще. Так как функция зависит только от одной
логической переменной, которая может принимать только значения “0” или “1” и, то в
рассматриваемом выражении один из операндов всегда будет равен “0” (при x =0 
“1”, а при x = 1 
).Учитывая, что 0 & x = 0, получаем, что рассматриваемые

функции эквивалентны.

9

Дизъюнкция

Таблица

истинности
х y x v y
0 0 0
0 1 1
1 0 1
1 1 1

Основные свойства:

0 v 0 = 0

0 v 1 = 1

1 v 1 = 1

0 v x = x

1 v x = 1

x v x = x

x v x v…v x = x

x v y = y v x

x v y v z = (x v y) v z = x v (y v z)

Для более легкого запоминания этой функции следует придерживаться правила:
функция дизъюнкции истинна, если истенен хотя бы один из ее операндов. Это
правило действует для функции, содержащей произвольное число операндов. Если
обозначать значение “истина” как “1”, а значение “ложь” как “0”, то эта функция для
двух операндов будет похожа на математическую функцию поразрядного сложения.
Поэтому ее зачастую называют функцией логическогосложения. Хотя здесь следует
иметь в виду, что в логическом сложении сигнал переноса в более старший разряд не
вырабатывается.

Штрих Шеффера (И-НЕ)

Штрих Шеффера (И-НЕ)1)

Таблица

истинности

10