Лекции по "Информатике"

Page 1

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
1
УГАТУ
Кафедра
информатики
ЛЕКЦИИ ПО ИНФОРМАТИКЕ
Составители:
доценты Кафедры Информатика
Карчевская Маргарита Петровна
Рамбургер Ольга Леонардовна
Для студентов факультета АТС
групп МХ, ММ, СМ, ФМ, АТП, ТМ, ВТ
УГАТУ
Кафедра
информатики
Тема 2
Арифметические основы ЭВМ
• Системы счисления
• Представление числовой информации
Логические основы ЭВМ
• Алгебра логики
• Логические схемы
Основы построения ЭВМ
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
3
УГАТУ
Кафедра
информатики
Системы счисления
Система счисления (СС) – принятый способ наименования
и записи чисел с помощью символов, имеющих
определенные количественные значения.
В любой системе счисления выбирается алфавит,
(совокупность некоторых символов – слов или знаков), с
помощью которого можно представить любое количество
чего-либо.
Изображение любого количества называется числом, а
символы алфавита – цифрами.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
4
УГАТУ
Кафедра
информатики
В современном мире наиболее распространенной является
десятичная система счисления, происхождение которой
связано с пальцевым счетом. Она возникла в Индии и в
XIII веке была перенесена в Европу арабами. Поэтому ее
и стали называть арабской.
На Древнем Востоке довольно широко была
распространена двенадцатеричная система. Многие
предметы до сих пор считают дюжинами – столовые
предметы; в году – 12 месяцев, английская система мер –
1 фут = 12 дюймов, 1 шиллинг = 12 пенсов.
В Древнем Вавилоне существовала шестидесятиричная
система. Она сохранилась до наших дней в системе
измерения времени.
Системы счисления

---

Page 2

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
5
УГАТУ
Кафедра
информатики
Все системы счисления можно разделить на два
класса: непозиционные и позиционные.
В непозиционных системах счисления значение цифры
не зависит от места, которое он занимает в числе.
Самый известный пример непозиционной СС – римская,
в которой используется 7 знаков:
Например,
III (три), LIX (59), DLV (555)
Системы счисления
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
6
УГАТУ
Кафедра
информатики
2 3 , 4 3 1 0
число единиц
число сотых долей единицы
Системы счисления
В позиционной системе счисления количественное
значение каждой цифры зависит от ее места (позиции)
в числе.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
7
УГАТУ
Кафедра
информатики
Системы счисления
Количество используемых знаков в позиционной системе
счисления называется основанием системы счисления.
Алфавиты некоторых систем счисления
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
8
УГАТУ
Кафедра
информатики
Позиционные системы счисления
В позиционной системе счисления любое число может
быть представлено в виде суммы произведений
коэффициентов на степени основания системы
счисления.
692
10
= 6*10
2
+ 9*10
1
+ 2*10
0
1101
2
= 1*2
3
+ 1*2
2
+ 0*2
1
+ 1*2
0
112
3
= 1*3
2
+ 1*3
1
+ 2*3
0
341,5
8
= 3*8
2
+ 4*8
1
+ 1*8
0
+ 5*8
-1
A1F,4
16
= A*16
2
+ 1*16
1
+ F*16
0
+ 4*16
-1

---

Page 3

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
9
УГАТУ
Кафедра
информатики
Позиционные системы счисления
В общем виде в позиционной СС с основанием p любое число
,
...
...
2
2
1
1
0
1
1
1
4
4
4
4
4
3
4
4
4
4
4
2
1
4
4
4
4
4
3
4
4
4
4
4
2
1
числа
часть
дробная
числа
часть
целая
m
m
n
n
n
n
p
p
a
p
a
p
a
a
p
a
p
a
p
a
A
−
−
−
−
−
−
−
−
+
+
+
+
+
+
+
+
=
здесь n+1 – число разрядов, необходимое для записи целой части числа,
m – число разрядов, необходимое для записи дробной части числа Z,
a
i
– веса разрядов.
43
42
1
43
42
1
K
числа
часть
дробная
числа
часть
целая
m
n
n
p
a
a
a
a
a
a
A
−
−
−
−
=
...
,
2
1
0
1
может быть представлено в развернутой форме:
На этой формуле основан способ перевода чисел из любой системы
счисления в десятичную СС. Для этого достаточно выполнить
указанные операции в десятичной системе счисления.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
10
УГАТУ
Кафедра
информатики
Правило перевода чисел
из любой СС в десятичную СС
Перевод в десятичную систему числа A, записанного
в р-ичной системе счисления
,
...
...
2
2
1
1
0
1
1
1
4
4
4
4
4
3
4
4
4
4
4
2
1
4
4
4
4
4
3
4
4
4
4
4
2
1
числа
часть
дробная
числа
часть
целая
m
m
n
n
n
n
p
p
a
p
a
p
a
a
p
a
p
a
p
a
A
−
−
−
−
−
−
−
−
+
+
+
+
+
+
+
+
=
43
42
1
43
42
1
K
числа
часть
дробная
числа
часть
целая
m
n
n
p
a
a
a
a
a
a
A
−
−
−
−
=
...
,
2
1
0
1
сводится к вычислению значения многочлена
средствами десятичной арифметики.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
11
УГАТУ
Кафедра
информатики
Правило перевода целой части числа
из десятичной СС в любую СС
Чтобы перевести целую часть числа из десятичной
системы в систему с основанием p, необходимо
разделить ее на основание p.
Остаток даст младший разряд числа.
Полученное при этом частное необходимо вновь
разделить на p – остаток даст следующий разряд числа
и т.д. пока частное от деления не станет равным 0.
200 : 8 = 25
(0),
25 : 8 = 3
(1),
3 : 8 = 0
(3)
Ответ: 200
10
=310
8
Пример
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
12
УГАТУ
Кафедра
информатики
Правило перевода целой части числа
из десятичной СС в любую СС
Полученные остатки от делений при переводе в p-ричную
СС необходимо на каждом шаге привести в соответствие
с алфавитом новой СС.
2638 : 16 = 164 (14),
164 : 16 = 10
(4),
10
: 16 = 0
(10)
Ответ: 2638
10
= A4E
16
(число 14 заменили шестнадцатеричной цифрой E,
10 – цифрой A)
Пример

---

Page 4

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
13
УГАТУ
Кафедра
информатики
Правило перевода дробной части числа
из десятичной СС в любую СС
Для перевода дробной части ее необходимо умножить на основание
системы p.
Целая часть, полученного произведения будет первым (после запятой,
отделяющей целую часть от дробной) знаком.
Дробную часть произведения необходимо вновь умножить на p. Целая
часть полученного числа будет следующим знаком и т.д. пока дробная
часть не станет равной 0 или, пока не будет достигнута нужная
точность, т.к.конечная дробь вполне может оказаться бесконечной
(периодической).
Полученные целые части произведений необходимо на каждом шаге
привести в соответствие с алфавитом новой СС.
0,65 * 16 = 10,40 (целая часть 10)
0,40 * 16 = 6,40 (целая часть 6)
0,40 * 16 = 6,40 (целая часть 6) и т.д.
0,65
10
= 0,A6(6)
16
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
14
УГАТУ
Кафедра
информатики
Соответствие чисел в различных СС
1111
17
F
15
1110
16
E
14
1101
15
D
13
1100
14
C
12
1011
13
B
11
1010
12
A
10
1001
11
9
9
1000
10
8
8
111
7
7
7
110
6
6
6
101
5
5
5
100
4
4
4
11
3
3
3
10
2
2
2
1
1
1
1
0
0
0
0
Двоичная
Восьмеричная
Шестнадцатеричная
Десятичная
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
15
УГАТУ
Кафедра
информатики
Арифметические операции с двоичными
числами
Таблицы сложения, умножения и вычитания в
двоичной СС
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
16
УГАТУ
Кафедра
информатики
Арифметические операции
с двоичными числами
При двоичном сложении 1 + 1 возникает перенос 1 в
старший разряд, как и в десятичной арифметике.
Например,

---

Page 5

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
17
УГАТУ
Кафедра
информатики
Арифметические операции
с двоичными числами
При двоичном вычитании необходимо помнить, что занятая в
ближайшем разряде 1, дает две единицы младшего разряда.
Если в соседних старших разрядах стоят нули, то 1 занимается
через несколько разрядов. При этом единица, занятая в
ближайшем значащем старшем разряде, дает две единицы
младшего разряда и единицы во всех нулевых разрядах,
стоящих между младшим и тем старшим разрядом, у
которого бралась единица.
2
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
18
УГАТУ
Кафедра
информатики
11011001 = 011 011 001 = 331
(8)
1100011011001 = 0001 1000 1101 1001 = 18D9
(16)
Для перевода целого двоичного числа в восьмеричное
(шестнадцатеричное) необходимо:
- разбить это число справа налево на группы по 3 (4) цифры –
двоичные триады (тетрады). При этом самая левая группа
может содержать менее трех (четырех) двоичных цифр.
- каждой группе поставить в соответствие ее восьмеричный
(шестнадцатеричный) эквивалент.
Правило перевода целой части двоичного числа в
восьмеричную (шестнадцатеричную) СС
011 = 2 + 1 = 3
1101 = 8 + 4 + 1 = 13
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
19
УГАТУ
Кафедра
информатики
0,1100011101
(2)
= 0,110 001 110 100 = 0,6164
(8)
0,1100011101
(2)
= 0,1100 0111 0100 = С74
(16)
Правило перевода дробной части двоичного числа
в восьмеричную (шестнадцатеричную) СС
Для перевода дробных частей двоичных чисел в
восьмеричную или шестнадцатеричную системы
аналогичное разбиение на триады или тетрады
производится от запятой вправо (с дополнением
недостающих последних цифр нулями)
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
20
УГАТУ
Кафедра
информатики
А1F
(16)
= 1010 0001 1111
(2)
127
(8)
= 001 010 111
(2)
Правило перевода восьмеричных (шестнадцатиричных)
чисел в двоичную СС
А
1
F
1
2
7
Перевод восьмеричных (шестнадцатеричных) чисел в
двоичные производится обратным путем –
сопоставлением каждому знаку числа
соответствующей тройки (четверки) двоичных цифр.

---

Page 6

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
21
УГАТУ
Кафедра
информатики
Представление числовой информации
Информация в памяти ЭВМ записывается в форме
цифрового двоичного кода.
Для этого в компьютере содержится большое количество
ячеек памяти и регистров (от лат. regestum – внесенное,
записанное).
Ячейки памяти и регистры состоят из элементов памяти. Каждый
из таких электрических элементов может находиться в одном
из двух устойчивых состояний: конденсатор заряжен или
разряжен, транзистор находится в проводящем или
непроводящем состоянии и т.п.
Одно из таких физических состояний создает высокий уровень
выходного напряжения элемента памяти, а другое – низкий.
Обычно это электрическое напряжение порядка 4-5В, его
принимают за двоичную единицу, и 0В – его принимают за
двоичный ноль.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
22
УГАТУ
Кафедра
информатики
Представление числовой информации
Большинство из ячеек памяти имеет одинаковую длину n,
т.е. они используются для хранения n бит двоичной
информации (бит – один двоичный разряд).
Информация, хранимая в такой ячейке, называется словом.
В большинстве случаев, словом называют группу из
четырех соседних байт, группу из двух соседних байт –
полусловом, группу из восьми соседних байт – двойным
словом.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
23
УГАТУ
Кафедра
информатики
Представление числовой информации
Память ЭВМ состоит из конечной последовательности
слов, а слова – из конечной последовательности битов,
поэтому объем представляемой в ЭВМ информации
ограничен емкостью памяти, а числовая
информация может быть представлена только с
определенной степенью точности.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
24
УГАТУ
Кафедра
информатики
Представление числовой информации
В вычислительных машинах применяются две формы
представления двоичных чисел:
- естественная форма, или форма с фиксированной
запятой (точкой);
- нормальная форма, или форма с плавающей запятой
(точкой).
В формате с фиксированной запятой все числа
изображаются в виде последовательности цифр с
постоянным положением запятой, отделяющей целую
часть от дробной.
Режим с фиксированной точкой в современных компьютерах
фактически применяется только для целых чисел и условно
запятая как бы зафиксирована после младшего разряда.

---

Page 7

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
25
УГАТУ
Кафедра
информатики
Представление числовой информации
В формате с плавающей запятой число представляется в виде двух
групп цифр, называемых мантиссой и порядком.
Для однозначности представления чисел с плавающей запятой
используется нормализованная (нормальная) форма, при которой:
• абсолютная величина мантиссы должна быть меньше 1, и первая ее
цифра после запятой не равна нулю,
•
порядок должен быть целым числом положительным или
отрицательным.
р
S
M
N
±
±
=
где
M
– мантисса,
0.1 <= |
M
| < 1
(
Целая часть мантиссы = 0, первая цифра
после точки не равна нулю)
р
– порядок числа;
S
– основание системы счисления
В общем виде число в нормальной форме (в любой СС)
записывается в виде:
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
26
УГАТУ
Кафедра
информатики
Представление числовой информации
Примеры представления двоичных чисел в
нормализованном виде
:
Первая цифра двоичной мантиссы после точки всегда 1
Внутреннее представление вещественных чисел в
компьютере всегда нормализовано
Примеры представления десятичных чисел в
нормализованном виде:
0,123*10
-02
0,567*10
5
0,1*10
-5
0,1*10
8
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
27
УГАТУ
Кафедра
информатики
Представление целых чисел без знака
Целые числа без знака могут занимать в памяти компьютера 1, 2, 4
байта, при этом самый младший двоичный разряд записывается в
крайний правый бит разрядной сетки. Все разряды должны быть
обязательно заполнены, даже если в этом разряде будет храниться
«незначащий ноль».
Например, десятичное число 19
10
=10011
2
в 1-байтовом формате
запишется так:
При такой форме представления целых чисел без знака
диапазон их возможных значений находится в
пределах от 0 до 2
n
-1, где n – количество разрядов,
отведенных для числа.
Номера разрядов
Биты числа
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
28
УГАТУ
Кафедра
информатики
Представление целых чисел без знака
В таблице приведены максимальные значения десятичных
чисел без знака и соответствующее им число
разрядов:

---

Page 8

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
29
УГАТУ
Кафедра
информатики
Представление целых чисел со знаком
Для представления целых чисел со знаком один разряд, как правило,
старший отводится под знак числа. Знак положительного числа
кодируется нулем, а знак отрицательного – единицей в этом
разряде:
Максимальное значение целого числа со знаком, которое можно
представить в n-разрядном регистре, равно 2
n-1
-1
,
а
минимальное равно -2
n-1
, т.е. отрицательных чисел можно
закодировать на одно больше, чем положительных.
Код числа -2
15
(-32768) в 16-разрядном регистре имеет вид:
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
30
УГАТУ
Кафедра
информатики
Представление целых чисел со знаком
Форма представления целых чисел со знаком, когда
крайний левый бит разрядной сетки отводится под
знак, а остальные биты – под цифры числа,
называется прямым кодом.
Форма представления двоичных чисел в виде прямого
кода используется в компьютере для хранения
только целых положительных чисел
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
31
УГАТУ
Кафедра
информатики
Правило формирования дополнительного кода:
- отрицательное двоичное число записывается в прямом
коде (в старшем бите – 1);
Представление целых чисел со знаком
- все разряды прямого кода, кроме знакового
(старшего бита) инвертируются – получается
обратный код;
- к младшему разряду обратного кода прибавляется
единица по правилам сложения двоичных чисел –
получается дополнительный код.
Отрицательные числа хранятся в дополнительном коде.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
32
УГАТУ
Кафедра
информатики
Представление целых чисел со знаком

---

Page 9

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
33
УГАТУ
Кафедра
информатики
Представление целых чисел со знаком
1 111 0100
1 111 0011
1 000 1100
-12
0 000 1100
0 000 1100
0 000 1100
12
Дополнительный
код
Обратный код
Прямой код
Десятичное
число
Примеры представления однобайтовых целых чисел со
знаком
1 000 0111
1 000 0110
1 111 1001
-121
0 111 1001
0 111 1001
0 111 1001
121
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
34
УГАТУ
Кафедра
информатики
Представление целых чисел со знаком
Дополнительный код используется для замены операции
вычитания простым сложением.
При возникновении переноса из знакового разряда
единица переноса отбрасывается, т.к. она вышла за
пределы разрядной сетки. В результате получается
алгебраическая сумма в прямом коде, если она
положительна (в знаковом разряде оказался 0), или в
дополнительном коде, если эта сумма получилась
отрицательной (в знаковом разряде оказалась 1).
При этом операция сложения выполняется над всеми
разрядами полученного дополнительного кода, т.е.
распространяется и на разряды знаков,
рассматриваемых в данном случае как разряды
числа.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
35
УГАТУ
Кафедра
информатики
Представление числовой информации
При записи вещественного числа в память компьютера выделяются разряды для
хранения знака мантиссы, порядка и мантиссы, например, для 4-х байтового
формата под мантиссу отводится 23 разряда, под порядок – 8 разрядов:
Смещенный (машинный) порядок числа P
м
находится по формуле:
P
м
= p + (2
k-1
-1)
где p – порядок числа, k - количество разрядов, отведенное для порядка.
Мантисса запоминается без первой единицы. Она считается скрытым
разрядом, но при выполнении арифметических операций, естественно,
учитывается.
смещение
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
36
УГАТУ
Кафедра
информатики
Алгебра логики
Алгебра логики – раздел математики, изучающий
высказывания, рассматриваемые со стороны их
логических значений (истинности или ложности) и
логических операций над ними.
Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем
как попытка изучения логики мышления человека математическими
методами.
Высказывание в алгебре логики – это повествовательное
предложение, в котором что-либо утверждается или
отрицается. По поводу любого высказывания можно
однозначно сказать истинно оно или ложно.
Примеры высказываний: «Трава зеленая»; «2≠5»; «Я – студент УГАТУ»; «10<5».
«Коля дома и смотрит телевизор»; «Мама на работе или уже дома».

---

Page 10

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
37
УГАТУ
Кафедра
информатики
Алгебра логики
Логические величины – понятия, выражаемые
словами ИСТИНА, ЛОЖЬ.
Логические константы – ИСТИНА (1) или ЛОЖЬ (0).
Логическая переменная – символически
обозначенная логическая величина, которая
может принимать значения ИСТИНА или ЛОЖЬ.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
38
УГАТУ
Кафедра
информатики
Алгебра логики
Простое высказывание – это повествовательное
предложение или некоторое математическое
соотношение, в котором что-либо утверждается или
отрицается и в отношении которого можно сразу
однозначно сказать, истинно оно или ложно. Простые
высказывания в математике строятся с помощью знаков
отношений (<, >, =, ≠ , ≥ , ≤).
Сложное высказывание образуется из простых
высказываний с помощью логических операций.
Простому высказыванию ставят в соответствие логическую
переменную, а сложному – логическую (булеву) функцию
Y = F(X1,X2,…,Xn), где X1, X2,…,Xn – логические переменные,
соответствующие простым высказываниям.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
39
УГАТУ
Кафедра
информатики
Основные логические операции.
Отрицание
Отрицание – логическая операция, которая исходному высказыванию ставит
в соответствие новое, значение которого противоположно исходному.
Описывается таблицей:
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
40
УГАТУ
Кафедра
информатики
Основные логические операции.
Конъюнкция
Описывается
таблицей:
Результатом операции будет:
- ЛОЖЬ, если хотя бы значение
одного из операндов будет ложно;
- ИСТИНА тогда и только тогда, когда
оба высказывания истинны.

---

Page 11

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
41
УГАТУ
Кафедра
информатики
Основные логические операции.
Дизъюнкция
Описывается
таблицей:
Результатом операции будет:
- ИСТИНА, если хотя бы одно из
высказываний истинно.
- ЛОЖЬ, тогда и только тогда,
когда оба высказывания ложны;
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
42
УГАТУ
Кафедра
информатики
Основные логические операции.
Строгая дизъюнкция
Описывается
таблицей:
Результатом операции будет:
- ИСТИНА, если хотя бы одно из
высказываний истинно.
- ЛОЖЬ, тогда, когда оба
высказывания ложны или оба
истинны;
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
43
УГАТУ
Кафедра
информатики
Основные логические операции.
Импликация
Описывается
таблицей:
Результатом операции будет
ЛОЖЬ, тогда, когда значение
первого операнда истинно, а
второго – ложно.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
44
УГАТУ
Кафедра
информатики
Основные логические операции.
Импликация. Пример
Ясно, что этот студент окажется лжецом только в одном случае: если он
завалит информатику (A – ИСТИНА), а отдыхать все-таки поедет (B – ЛОЖЬ).
Если же он информатику сдаст, но отдыхать не поедет, то во лжи его обвинить
нельзя, т.к. обещание нигде не отдыхать он давал лишь при условии, что не
сдаст информатику.
A
B
A
B
Пример. Высказывание:
«Если я завалю информатику, то летом никуда не поеду отдыхать».
В математических теоремах импликации формулируются в виде
доказательства только необходимого или только достаточного условия, при
этом условие теоремы и заключение всегда связаны по содержанию.

---

Page 12

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
45
УГАТУ
Кафедра
информатики
Основные логические операции.
Эквиваленция
Описывается
таблицей:
Высказывание является
истинным тогда и только
тогда, когда оба
высказывания
одновременно истинны
или одновременно
ложны.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
46
УГАТУ
Кафедра
информатики
Пример. Преподаватель информатики утверждает, что он
«Допустит студента до экзамена тогда и только тогда, когда он
защитит все лабораторные работы».
Основные логические операции.
Эквиваленция. Пример
Все возможные
значения такого
высказывания:
A
B
A
B
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
47
УГАТУ
Кафедра
информатики
Основные логические операции
С помощью логических переменных и символов,
обозначающих логические операции любое
высказывание можно формализовать, т.е. заменить
логической формулой.
Приоритеты выполнения логических операций в
логических выражениях:
-
отрицание;
-
логическое произведение;
-
логическое сложение, исключающее или;
-
импликация, эквиваленция.
Скобки меняют порядок выполнения операций.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
48
УГАТУ
Кафедра
информатики
Основные логические операции
Сводная таблица истинности основных логических операций
Для удобства и наглядности отражения сути логических
операций производимых над логическими переменными
принято использовать таблицы истинности.
В таблицах истинности записываются все возможные
сочетания значений логических переменных и
соответствующие им значения логической функции.

---

Page 13

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
49
УГАТУ
Кафедра
информатики
Построение таблицы истинности
для заданной логической функции
Для каждой логической функции Y = F(X1,X2,…,Xn)
можно построить таблицу истинности.
Количество строк в этой таблице будет равно числу
возможных комбинаций значений логических
переменных, т.е. 2
N
, где N – число логических
переменных, входящих в логическое выражение
.
Количество столбцов в таблице истинности равно сумме
количества логических переменных и количества
логических операций в логическом выражении, т.е. N+M,
где M – число логических операций.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
50
УГАТУ
Кафедра
информатики
Построение таблицы истинности
для заданной логической функции
Пример. Составить таблицу истинности для логической функции
A
and
C
or
B
C
B
A
F
)
(
)
,
,
(
=
Последняя колонка полученной таблицы является ответом на
поставленную задачу.
Количество строк, в таблице равно 8 (2
3
), количество столбцов 3 + 3=6.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
51
УГАТУ
Кафедра
информатики
Таблицы истинности логических функций
Логические выражения называются тождественно
истинными, если они имеют в таблице истинности
значения 1 для всех наборов значений входных
переменных.
Логические выражения называются тождественно
ложными, если они имеют в таблице истинности
значения 0 для всех наборов значений входных
переменных.
Логические выражения называются равносильными или
эквивалентными, если они имеют одинаковые значения
в таблице истинности для всех наборов значений
входных переменных.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
52
УГАТУ
Кафедра
информатики
Преобразование логических функций
Логические операции инверсии, конъюнкции и
дизъюнкции называют базовыми. Любую функцию с
помощью тождественных преобразований можно
представить таким образом, чтобы она содержала
только базовые логические операции.
Тождества, заменяющие операции «исключающее ИЛИ»,
«импликации» и «эквиваленции» базовыми функциями:

---

Page 14

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
53
УГАТУ
Кафедра
информатики
Основные законы алгебры логики
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
54
УГАТУ
Кафедра
информатики
Основные законы алгебры логики
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
55
УГАТУ
Кафедра
информатики
КНФ и ДНФ
Форма представления логических функций, содержащая только три
основные логические операции: логическое отрицание, логическое
сложение и логическое умножение называется нормальной.
Инверсия в нормальной форме представления должна быть только над
переменными (не над выражениями!)
Выделяют две специальные нормальные формы представления логических
функций:
1. Конъюнктивно-нормальная форма (КНФ) – представление в виде
произведений суммы элементарных высказываний и их отрицаний
(дизъюнкции конъюнкций).
2. Дизъюнктивно-нормальная форма (ДНФ) – представление в виде суммы
произведений элементарных высказываний и их отрицаний (конъюнкции
дизъюнкций).
)
(
)
(
)
(
)
,
,
(
A
C
B
B
A
B
A
C
B
A
F
+
+
⋅
+
⋅
+
=
A
C
B
A
C
B
A
C
B
A
F
⋅
+
⋅
+
⋅
⋅
=
)
,
,
(
Например:
Например:
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
56
УГАТУ
Кафедра
информатики
КНФ и ДНФ
Любая логическая функция приводится к КНФ
или ДНФ с помощью следующего алгоритма:
1. избавляются от импликации и эвиваленции;
2. избавляются от отрицаний над сложными
высказываниями;
3. раскрывают скобки, применяя
распределительный закон логики.

---

Page 15

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
57
УГАТУ
Кафедра
информатики
КНФ и ДНФ
(
)
(
)
C
B
C
A
↔
→
and
к ДНФ
1. Избавимся от импликации и эвиваленции:
)
(
)
(
)
(
and
)
(
C
B
C
B
C
A
C
B
C
A
⋅
+
⋅
⋅
+
=
↔
→
2. Раскрываем скобки:
C
B
C
C
B
A
B
C
C
B
A
C
B
C
B
C
A
⋅
⋅
+
⋅
⋅
+
⋅
+
⋅
⋅
=
⋅
+
⋅
⋅
+
)
(
)
(
3. Преобразуем и получаем дизъюнктивную нормальную форму:
ПРИМЕР. Привести логическое высказывание
РЕШЕНИЕ
=0
=1
C
B
A
C
B
C
B
A
A
C
B
C
B
A
B
C
C
B
A
⋅
⋅
+
⋅
=
⋅
⋅
+
+
⋅
⋅
=
⋅
⋅
+
⋅
+
⋅
⋅
)1
(
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
58
УГАТУ
Кафедра
информатики
Построение логической функции
по заданной таблице истинности
1. Для каждой строки таблицы истинности с единичным
значением функции строится минтерм. Переменные,
имеющие нулевые значения в строке, входят в минтерм
с отрицанием, а переменные со значением 1 – без
отрицания.
2. Все полученные минтермы объединяются операцией
дизъюнкция
Логическую функцию по заданной таблице истинности
можно построить по следующему алгоритму:
Минтермом называется терм-произведение, в котором каждая
переменная встречается только один раз – либо с отрицанием, либо
без него. Например,
C
B
A
⋅
⋅
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
59
УГАТУ
Кафедра
информатики
Построение логической функции
по заданной таблице истинности
1. В таблице истинности находим строки, в которых F = 1.
Вторую строку описывает минтерм: not X1 and not X2 and X3.
Третью строку описывает минтерм: not X1 and X2 and not X3.
Шестую строку описывает минтерм: X1 and not X2 and X3.
2. Термы объединяем операцией дизъюнкция, получается логическое выражение
3
2
1
3
2
1
3
2
1
3
2
1
X
X
X
X
X
X
X
X
X
)
X,
X,
X
(F
⋅
⋅
+
⋅
⋅
+
⋅
⋅
=
Решение:
ПРИМЕР. Восстановить
логическую функцию
трех переменных по
заданной таблице
истинности
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
60
УГАТУ
Кафедра
информатики
Построение логического выражения по
условиям, заданным в виде текста
С помощью логических переменных и символов, обозначающих
логические операции любое высказывание можно формализовать,
т.е. заменить логической формулой.

---

Page 16

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
61
УГАТУ
Кафедра
информатики
Построение логического выражения по
условиям, заданным в виде текста
)1
(
)1
(
=
=
y
and
x
)1
(
)1
(
≤
≤
y
and
x
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
62
УГАТУ
Кафедра
информатики
Переключательные схемы
В компьютерах и других автоматических устройствах
применяются электрические схемы, содержащие тысячи
переключательных элементов: реле. выключателей и т.п.
Переключательная схема – это схематическое изображение
некоторого устройства, состоящего из переключателей и
соединяющих их проводников, а также входов и выходов, на
которые подается и снимается сигнал.
Каждый переключатель имеет только два состояния: замкнутое и
разомкнутое.
Переключателю Х ставится в соответствие логическая
переменная х, которая принимает значение 1 в том и только в
том случае, когда переключатель Х замкнут и схема проводит
ток; если переключатель разомкнут, то х равна 0.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
63
УГАТУ
Кафедра
информатики
Переключательные схемы
Функции проводимости F некоторых переключательных схем
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
64
УГАТУ
Кафедра
информатики
Переключательные схемы
Пример

---

Page 17

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
65
УГАТУ
Кафедра
информатики
Переключательные схемы
Две схемы называются равносильными, если через
одну из них проходит ток тогда и только тогда,
когда он проходит через другую (при одном и том
же входном сигнале).
Из двух равносильных схем более простой
считается та схема, функция проводимости
которой содержит меньшее число логических
операций или переключателей.
При рассмотрении переключательных схем
возникают две основные задачи: синтез и анализ
схемы.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
66
УГАТУ
Кафедра
информатики
Переключательные схемы
Синтез схемы по заданным условиям ее работы
сводится к следующим этапам:
• составлению функции проводимости;
• упрощению этой функции;
• построению соответствующей схемы.
Анализ схемы сводится к следующим этапам:
• определению значения функции проводимости
схемы при всех возможных наборах входящих в эту
функцию переменных;
• получению упрощенной формулы.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
67
УГАТУ
Кафедра
информатики
Переключательные схемы
Пример
Здесь второе логическое
слагаемое является
отрицанием первого, а
дизъюнкция переменной с ее
инверсией равна 1.
Упрощенная схема
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
68
УГАТУ
Кафедра
информатики
Логические схемы
Логическая схема – графическое представление
логической функции.
Схема строится из логических элементов и отрезков
прямых.
Логический элемент – это прямоугольник, в котором
ставится символ логической операции.
Указанные операции производятся над логическими
переменными на входе в прямоугольник (слева), а
результат операции передается на выход (справа).
Логическую схему можно интерпретировать как
электрическую цепь с преобразователями сигналов в
виде логических элементов. Соответствующие схемы
называются функциональными.

---

Page 18

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
69
УГАТУ
Кафедра
информатики
Логические элементы
Наиболее популярные изображения базовых логических
элементов
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
70
УГАТУ
Кафедра
информатики
Логические элементы
Изображения основных логических элементов
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
71
УГАТУ
Кафедра
информатики
Логические элементы
Изображения основных логических элементов
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
72
УГАТУ
Кафедра
информатики
Логические элементы
Любой логической функции можно поставить в соответствие
некоторую функциональную схему и наоборот.
Построение логических схем по заданной логической функции
(синтез) является задачей проектирования функциональных
схем.
Задача проектирования функциональных схем возникает,
например, при проектировании отдельных узлов
компьютера, если имеется лишь описание алгоритма его
работы.
Построение логической функции по заданной логической схеме
(анализ) является задачей анализа функциональных схем.
Анализ функциональных схем дает возможность понять, как
работает логическое устройство, т.е. дать ответ на вопрос:
какую функцию оно выполняет.

---

Page 19

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
73
УГАТУ
Кафедра
информатики
Построение логических схем
по заданной логической функции
Рекомендуется следующая последовательность действий:
-
формируется таблица истинности, которую должна
будет реализовать проектируемая функциональная
схема;
-
по таблице истинности составляется логическая
функция, состоящая только из базовых логических
операций;
-
полученная логическая функция упрощается;
-
по упрощенной логической функции строится
функциональная логическая схема.
При решении задачи проектирования функциональных схем
нужно стремиться к уменьшению числа используемых
базовых логических элементов, реализующих требуемую
логическую функцию.
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
74
УГАТУ
Кафедра
информатики
Построение логических схем
по заданной логической функции
B
A⋅
B
A⋅
Пример. Построить функциональную схему для функции
)
(
B
A
B
A
+
⋅
⋅
B
A+
)
(
B
A
B
A
+
⋅
⋅
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
75
УГАТУ
Кафедра
информатики
Построение логических схем
по заданной таблице истинности
Пример. Построить функциональную схему по таблице
истинности:
C
B
A
C
B
A
⋅
⋅
+
⋅
⋅
Функциональная схема будет
иметь вид:
Решение.
Составим логическую функцию
по данной таблице истинности:
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
76
УГАТУ
Кафедра
информатики
Построение логической функции
по заданной логической схеме
Пример. Построить и проанализировать логическую функцию по заданной
схеме.
Решение. Запишем логические
выражения поэлементно слева
направо и сверху вниз, упрощая
их на каждом шаге:
(применили закон де Моргана)
B
A
B
A
⋅
=
+
1.
2.
;B
A⋅
3.
;1
=
⋅
⋅
⋅
B
A
B
A
4.
;1
=
+
+
=
+
⋅
B
B
A
B
B
A
5.
0
1
1 =
⋅
Получается, что данная логическая схема дает на выходе ложные значения при любых
комбинациях A и B, т.е. данная схема реализует функцию
.
)
,
(
False
B
A
F
=

---

Page 20

Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
77
УГАТУ
Кафедра
информатики
Логическая схема одноразрядного
двоичного сумматора
Построение логической схемы одноразрядного
двоичного сумматора, имеющего два входа (х
1
и х
2
) и
два выхода (S и P).
1. Составим таблицу истинности сумматора
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
78
УГАТУ
Кафедра
информатики
Логическая схема одноразрядного
двоичного сумматора
2. По таблице истинности представим выходные
функции S и P в виде ДНФ
(
)
(
)
2
1
2
1
2
2
1
2
1
2
1
1
x
x
x,
x
f
P
,
x
x
x
x
x,
x
f
S
=
=
+
=
=
3. По логическим функциям построим схему
Информатика
ФАТС – 2, 3 курс 1, заочники
семестр 1, 2010 г.
79
УГАТУ
Кафедра
информатики