Информатика. Теория и практика_Острейковский В.А_2008

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

âмашине не вышли за пределы интервала (–1, +1), а также неизбежное в таких устройствах накопление абсолютной погрешности вычислений из-за перемасштабирования, при котором цифры младших разрядов (а именно в них накапливается абсолютная погрешность) передвигаются в старшие разряды, привели к тому, что в универсальных ЭВМ представление чисел

âформате с фиксированной точкой практически перестало применяться. Оно сохраняется в специализированных вычислительных системах, где диапазон изменения чисел заранее проанализирован, в некоторых микропроцессорах и микроЭВМ.

Представление чисел в формате с плавающей точкой. Плаваю-

ùåé называется такая точка, позиция которой не фиксируется форматом числа. Любое вещественное число Õ, представленное в системе счисления с основанием N, можно записать в виде

X = òN p,

ãäå m — мантисса, ð — характеристика (или порядок) числа. Если |ò| < 1, то запись числа называется нормализованной

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

а) в десятичной системе счисления:

372.95 = 0.37295 103;

25 = 0.025 103 = 0.25 102; 0.0000015 = 0.15 10–5= 0.015 10–4;

б) в двоичной системе счисления:

11010,1101 = 0,0110101101 26 = 0,110101101 25; 0,011011 = 0,11011 2–1;

0,1 = 0,1 20

(здесь порядок определяет, на сколько разрядов необходимо осуществить сдвиг относительно запятой).

101

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

Число называется нормализованным справа, если после запятой в мантиссе стоит не нуль. Например, числа 0,0007610

è0,000112, представленные соответственно в виде 0,076 10–2

è0,011 2–2, не являются нормализованными справа, а эти же числа, представленные соответственно в виде 0,76 10–3

è0,11 2–3, являются таковыми.

Âдальнейшем под нормализацией числа будем понимать нормализацию справа.

Нормализованное число одинарной точности, представленное в формате с плавающей точкой, записывается в память следующим образом: знак числа — в бите 15 первого слова (0 — для положительных и 1 — для отрицательных чисел); порядок размещается в битах 7—14 первого слова, а мантисса занимает остальные 23 бита в двух словах. Нормализованное число двойной точности записывается в четыре слова памяти и отличается от представления чисел с одинарной точностью только тем, что продолжение мантиссы размещается в следующих за первым словом трех последовательных словах памяти, а всего под мантиссу в этом случае отводится 55 бит.

Порядок числа, представленного в формате с плавающей

точкой, изменяется в диапазоне от –12810(2008) äî +12710(1778) и запоминается увеличенным на 12810(2008). Такой способ представления порядка называется смещенным.

Следует иметь в виду, что, хотя для мантиссы отведено 23 разряда для чисел одинарной точности и 55 разрядов — для чи- сел двойной точности, в операциях участвует 24 и 56 разрядов соответственно, так как старший разряд мантиссы нормализованного числа не хранится, т. е. имеет место так называемый скрытый разряд. Однако при аппаратном выполнении операций этот разряд автоматически восстанавливается и учитывается. Порядок числа также учитывает скрытый старший разряд мантиссы.

102

Также заметим, что нормализованная мантисса в двоичной системе счисления всегда представляется десятичным числом ò, лежащим в диапазоне 0,5 ò < 1.

Примеры представления чисел в формате с плавающей точкой:

1) 0,110 = 0,0 (6314)8 = 0,000 (1100)2 = 0, (1100)2 2–3;

–3 = (–3 + 200) 8 = 1758 = 011111012.

Заметим, что в этом примере мантисса представлена бесконечной периодической дробью, поэтому последний учитываемый разряд мантиссы округляется;

2) –49,510 = –61,48 = –110001,1002 = –0,11000112 26; 610 = (6 + 200)8 = 2068 = 100001102.

При выполнении арифметических операций над числами, представленными в формате с плавающей точкой, надо отдельно выполнять их для порядков и мантисс. При алгебраическом сложении чисел надо сначала уравнять порядки слагаемых. При умножении порядки надо складывать, а мантиссы — перемножать. При делении из порядка делимого вычитают порядок делителя, а над мантиссами совершают обычную операцию деления. После выполнения операций, если это необходимо, проводят нормализацию результата, что влечет изменение порядков, так как каждый сдвиг на один разряд влево соответствует уменьшению порядка на единицу, а сдвиг вправо — увели- чению его на единицу. Введение термина «плавающая точка» как раз и объясняется тем, что двоичный порядок, определяющий фактическое положение точки в изображении числа, корректируется после выполнения каждой арифметической операции, т. е. точка в изображении числа «плавает» (изменяется ее положение) по мере изменения данной величины. А в изображении чисел, представленных в формате с фиксированной точкой, она жестко зафиксирована в определенном месте.

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

103

и избавляет от накопления абсолютной погрешности при вы- числениях (хотя не избавляет от накопления относительной погрешности).

2.3.5. Представление цветной и графической информации

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

Рассмотрим наиболее часто используемую при разработке электронных (мультимедийных) и полиграфических изданий растровую графику. Основным элементом растрового изображения является точка, èëè пиксель.

Для кодирования любого изображения нужно разбить его на точки и цвет каждой точки закодировать. Например, черно-белую картинку можно закодировать, используя два бита: 11 — белый цвет, 10 — светло-серый, 01 — темно-серый и 00 — черный.

Для кодирования 256 различных цветов требуется 8 бит. Однако этого недостаточно для кодирования полноцветных изображений живой природы. Человеческий глаз может различать десятки миллионов цветовых оттенков. В современных компьютерах для кодирования цвета одной точки используется три байта.

Каждый цвет представляет собой комбинацию трех основных цветов: красного, зеленого и синего. Первый байт определяет интенсивность красной составляющей, второй — зеленой, третий — синей.

Белый цвет кодируется полными тремя байтами (255, 255, 255,

или — в двоичной системе — 111111111, 11111111, 11111111).

Черный цвет — отсутствие всех цветов (0, 0, 0). Красный цвет может быть темным (120, 0, 0) или ярко-красным (255, 0, 0). Такая система кодирования цветной графической информации называется системой RGB (Red, Green, Blue) и обеспечивает однозначное определение 16,5 млн (224) различных цветов и оттенков.

Качество графического изображения зависит от количества точек (пикселей) на единице площади. Этот параметр называется разрешением и измеряется в точках на дюйм — dpi.

104

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

Например, для цветной картинки, составленной из 256 цветов в графическом режиме монитора 640 480, требуется объем видеопамяти, равный

8 640 480 = 2 457 600 бит = 307 200 байт = 300 Кбайт.

Òåìà 2.4

АЛГЕБРА ЛОГИКИ. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ.

СЛОЖНЫЕ ВЫСКАЗЫВАНИЯ. ПОСТРОЕНИЕ ТАБЛИЦ ИСТИННОСТИ СЛОЖНЫХ ВЫСКАЗЫВАНИЙ

2.4.1. Понятие об алгебре высказываний

Великий немецкий математик Готфрид Лейбниц (1646—1716) разработал в 1666 г. (в двадцатилетнем возрасте) общий метод, позволяющий свести любую мысль к точным формальным высказываниям. Это открыло возможность перевести логику (Лейбниц называл ее законами мышления) из царства слов в царство математики, где отношения между объектами и высказываниями точны и определенны. Таким образом, Лейбниц стал основателем формальной логики. Он занимался исследованием двоичной системы счисления, наделяя ее неким мистическим смыслом: цифру 1 он ассоциировал с Богом, а 0 — с пустотой. Из этих двух цифр, по мнению Лейбница, произошло все и с их помощью можно выразить любое математическое понятие. Лейбниц первым высказал мысль о том, что двоичная система может стать универсальным логическим языком.

Что такое алгебра логики. Лейбниц мечтал о построении

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

105

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

В 1847 г. английский математик Джордж Буль (1815—1864) создал универсальный логический язык. Буль разработал ис- числение высказываний (впоследствии названное в его честь булевой алгеброй), которое представляет собой формальную логику, переведенную на строгий язык математики. Формулы булевой алгебры внешне похожи на формулы знакомой нам алгебры, причем это сходство не только внешнее, но и внутреннее. Булева алгебра — вполне равноправная алгебра, подчи- няющаяся своду принятых при ее создании законов и правил. Она является системой обозначений, применимой к любым объектам — числам, буквам и предложениям. Пользуясь этой системой, можно закодировать любые утверждения, истинность или ложность которых нужно доказать, а затем манипулировать ими, подобно обычным числам в математике.

Огромную роль в распространении булевой алгебры и ее развитии сыграл американский философ, логик, математик и естествоиспытатель Чарлз Пирс (1839—1914).

Объект рассмотрения в алгебре логики — так называемые высказывания, т. е. любые утверждения, о которых можно сказать, что они либо истинны, либо ложны. Например: «Сургут — город в России», «9 — четное число»; первое высказывание истинно, а второе — ложно.

Таким образом, высказывание — это любое утверждение, которое может быть либо истинным, либо ложным, но не может быть истинным и ложным одновременно. В математи- ческой логике понятие «высказывание» определяется как повествовательное предложение. В информатике это понятие сужается до определения: высказывание — это логическое выражение. Над высказываниями возможны определенные операции.

Итак, раздел математической логики, изучающий высказывания и операции над ними, называется булевой алгеброй. Булева алгебра — частный случай алгебры логики.

106

2.4.2. Основные логические операции

Из простых логических высказываний образовываются сложные высказывания. Для этого используются союзы: И; ИЛИ; ЕСЛИ…ТО; НЕ.

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

Рассмотрим основные логические операции.

Конъюнкция (логическое умножение, И) двух высказываний А и В представляет собой сложное высказывание, которое истинно тогда и только тогда, когда истинны оба составляющих его высказывания А и В. Обозначение конъюнкции: 1) А В (читается: А и В); 2) символ «·»; 3) между перемножаемыми высказываниями знак отсутствует: А В = А · В = АВ; 4) &.

Значение истинности логического произведения А В в зависимости от значений истинности высказываний А и В определяется следующими соотношениями:

0 0 = 0; 0 1 = 0; 1 0 = 0; 1 1 = 1.

(2.8)

Дизъюнкция (логическое сложение, ИЛИ) двух высказываний А и В является сложным высказыванием, которое истинно, когда хотя бы одно из слагаемых А и В истинно. Обозначение дизъюнкции: 1) А В (читается: А или В); 2) в виде матрицы

A B =		A		.
		B

Значение истинности логического сложения А В в зависимости от значений истинности высказываний А и В определяется следующими соотношениями:

0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 1.

(2.9)

Отрицание (НЕ). Отрицанием высказывания А является сложное высказывание А, которое ложно, когда А истинíо, и истинно, когда А ложно. Обозначение отрицания: 1) A (читается: не А); 2) А .

107

Значение истинности отрицания высказывания А определяется следующими соотношениями:

1 = 0; 0 = 1.

(2.10)

Эквивалентность (равнозначность) двух высказываний А и В

обозначается символом « » (иногда — «~»). Значение истинности эквивалентных высказываний А и В определяется в зависимости от значений истинности исходных высказываний по следующим соотношениям:

0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 1. (2.11)

Импликация двух высказываний обозначается символом «>» (если А, то В) или стрелкой: « ».

2.4.3. Построение таблиц истинности сложных высказываний

В булевой алгебре существует понятие «значение истинности высказывания». Если высказывание истинно, то его значе- нию придается символ 1, а если ложно, — символ 0.

Логические функции могут задаваться таблицами, часто называемыми таблицами истинности (òàáë. 2.3).

								Таблица 2.3
		Таблица истинности
À	Â		A		À Â	À Â	À Â		À Â
0	0	1			0	0	1		1
0	1	1			0	1	0		1
1	0	0			0	1	0		0
1	1	0			1	1	1		1

Как читается данная таблица? В качестве примера прочи- таем ее верхнюю строку: «Если переменные А и В принимают значения ЛОЖЬ, то отрицание А принимает значение ИСТИНА; выражение (А и В) принимает значение ЛОЖЬ; выражение

108

(А или В) принимает значение ЛОЖЬ; выражение (А эквивалентно В) принимает значение ИСТИНА; выражение (если А, то В) принимает значение ИСТИНА».

Рассмотренные логические операции тесно связаны с повседневной жизнью. Например, конъюнкцию (логическую функцию И) можно проиллюстрировать на примере работы стереопроигрывателя. Следующее сложное высказывание о стереоэффекте истинно только при условии истинности обоих простых высказываний: «Если работают оба канала стереопроигрывателя, то стереоэффект есть».

Дизъюнкция (логическая функция ИЛИ) может быть показана на примере возможности полета двухмоторного самолета. Это сложное высказывание истинно при истинности хотя бы одного из простых высказываний: «Если работает хотя бы один из двух двигателей — левый или правый, двухмоторный самолет может лететь».

Логическая операция отрицания (НЕ) может быть представлена следующим примером: «Если фотопленка не засве- чена, то фотографировать можно, а если фотопленка засвече- на, то фотографировать нельзя». Операция НЕ — это функция только одного простого высказывания — состояния фотопленки.

Òåìà 2.5

ОСНОВНЫЕ ЗАКОНЫ ПРЕОБРАЗОВАНИЯ АЛГЕБРЫ ЛОГИКИ

2.5.1.Закономерности логических операций

Âалгебре логики имеют место несколько законов. Из них наиболее часто применяются следующие: сочетательный, переместительный, распределительный, закон двойственности (закон инверсий).

Сочетательный (синоним: ассоциативный — зависимость меж-

ду двумя высказываниями) закон для конъюнкции и дизъюнкции соответственно:

—для конъюнкции:

À (Â Ñ) = (À Â) Ñ = À Â Ñ;

(2.12)

109

— для дизъюнкции:

À (Â Ñ) = (À Â) Ñ = À Â C.

(2.13)

Переместительный (синоним: коммутативный — свойство операции не изменять значения при перестановке высказываний) закон:

— для конъюнкции:

À Â = Â À;	(2.14)
— для дизъюнкции:
À Â = Â À.	(2.15)

Правила (2.12) — (2.15) определяют конъюнкцию и дизъюнкцию в отдельности.

Распределительный (синоним: дистрибутивный) закон:

— для конъюнкции относительно дизъюнкции:

À (Â Ñ) = (À Â) (À Ñ);

(2.16)

— для дизъюнкции относительно конъюнкции:

À (Â Ñ) = (À Â) (À Ñ).

(2.17)

Правила (2.16) и (2.17) выдают связь между конъюнкцией и дизъюнкцией совместно. Функции конъюнкции и дизъюнкции обладают свойствами, аналогичными свойствам операций умножения и сложения. При этом рассмотренные законы обладают «симметрией» в том смысле, что из любого закона для дизъюнкции (конъюнкции) можно получить тот же закон путем замены знаков дизъюнкции на знаки конъюнкции (дизъюнкции) и наоборот.

Закон двойственности, èëè закон инверсий, позволяет заменять отрицание конъюнкции дизъюнкцией отрицаний и отрицание дизъюнкции — конъюнкцией отрицаний:

(À Â) = À Â ;	(2.18)
(À Â) = À Â .	(2.19)

Логическое сложение по модулю 2 (синонимы: разноименность,

отрицание равнозначности) высказываний А и В обозначается символом «+». Значение А и В определяется в зависимости от

110