Представление некоторой графической информации в памяти ЭВМ

Среди систем кодирования графической информации можно выделить следующие системы:

Система кодирования RGB (Red–красный, Green–зеленый, Blue–синий). В этой системе для каждого из этих цветов отводится по одному байту, то есть графическая информация размещается в трех байтах. Например, 00000000 00000000 00000000 соответствует черному цвету, 11111111 00000000 00000000 соответствует красному цвету, 11111111 11111111 11111111 соответствует белому цвету.

Система кодирования CMY (Cyan–голубой, Magenta–пурпурный, Yellow–желтый). В этой системе для каждого из этих цветов также отводится по одному байту. Но здесь используются цвета, дополняющие до белого основные цвета модели RGB, то есть красный цвет поглощается голубым цветом, зеленый цвет поглощается пурпурным, синий цвет поглощается желтым. Поэтому 00000000 00000000 00000000 соответствует белому цвету, а 11111111 11111111 11111111 соответствует черному цвету. Разновидностью CMY является модель CMYK (4 байта), в которой добавлен черный цвет.

Система HSB (Hue, Saturation, Brightness) задающая оттенок, насыщенность и яркость.

Следует отметить, что модели, использующие 4 байта и 3 байта для хранения цветов, называют полноцветными. Наряду с полноцветными моделями существуют модели с уменьшенным количеством разрядов для представления цвета, в частности High Color (кодирование цветной графики двумя байтами), а также индексный метод кодирования (один байт), в котором указывается номер цвета выбираемый из палитры (таблицы цветов).

6 Контрольные вопросы

1. Что такое основание позиционной системы счисления?

2. Как перевести число из десятичной системы счисления в двоичную систему счисления и наоборот?

3. Как перевести число из двоичной системы счисления шестнадцатеричную систему счисления?

4. Как перевести число из шестнадцатеричной системы счисления в двоичную систему счисления?

5. Как перевести число из шестнадцатеричной системы счисления десятичную систему счисления?

6. Как перевести число из десятичной системы счисления в некоторую другую, например, 3–чную, 4–чную и т.д. систему счисления?

7. Как перевести число из 3–чной, 4–чной и т.д. систем счисления в десятичную систему счисления?

8. Как перевести число (содержащее дробную часть) из 2–чной в 10–чную и наоборот?

9. Как представляются отрицательные числа в форме значения со знаком (в прямом коде), в форме обратного кода, в форме дополнительного кода?

10. Переведите отрицательное число из 10–чной в 2–чную (представив в прямом, обратном, дополнительном кодах).

Часть 3. Логические основы ЭВМ

Основные понятия алгебры логики

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

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

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Примеры. Предложение «7 – нечетное число» следует считать высказыванием, так как оно истинное. Предложение «Лондон – столица Германии» тоже высказывание, так как оно ложное.

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

Предложения типа «в городе A более миллиона жителей», «у него голубые глаза» не являются высказываниями, так как для выяснения их истинности или ложности нужны дополнительные сведения: о каком конкретно городе или человеке идет речь. Такие предложения называются высказывательными формами.

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

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание «площадь поверхности Индийского океана равна 75 млн. кв. км» в одной ситуации можно посчитать ложным, а в другой – истинным. Ложным – так как указанное значение неточное и вообще не является постоянным. Истинным – если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

Примеры. Из элементарных высказываний «Петров – преподаватель», «Петров – шахматист» при помощи связки «и» можно получить составное высказывание «Петров – преподаватель и шахматист», понимаемое как «Петров – преподаватель, хорошо играющий в шахматы».

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

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена.

Пусть через А обозначено высказывание «Тимур поедет летом на море», а через В – высказывание «Тимур летом отправится в горы». Тогда составное высказывание «Тимур летом побывает и на море, и в горах» можно кратко записать как А и В. Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0».

Часто используют следующие логические связки (логические операции):

Обозначение операции	Читается	Название операции	Альтернативные обозначения
	НЕ	Отрицание (инверсия)	Черта сверху
Λ	И	Конъюнкция (логическое умножение)	∙ &
V	ИЛИ	Дизъюнкция (логическое сложение)	+
→	Если … то	Импликация
↔	Тогда и только тогда	Эквиваленция	~

 

НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком). Высказывание истинно, когда A ложно, и ложно, когда A истинно.

Пример. «Луна – спутник Земли» (А); «Луна – не спутник Земли» (A).

И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой «· » (может также обозначаться знаками Ʌ или &). Высказывание А · В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Пример. Высказывание «10 делится на 2 и 5 больше 3» истинно, а высказывания «10 делится на 2 и 5 не больше 3», «10 не делится на 2 и 5 больше 3», «10 не делится на 2 и 5 не больше 3» – ложны.

ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком V (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Пример. Высказывание «10 не делится на 2 или 5 не больше 3» ложно, а высказывания «10 делится на 2 или 5 больше 3», «10 делится на 2 или 5 не больше 3», «10 не делится на 2 или 5 больше 3» – истинны.

ЕСЛИ–ТО Операция, выражаемая связками «если..., то», «из... следует», «... влечет...», называется импликацией (лат. implico – тесно связаны) и обозначается знаком →. Высказывание ложно тогда и только тогда, когда А истинно, а В ложно.

Пример. Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: «данный четырёхугольник – квадрат» (А) и «около данного четырёхугольника можно описать окружность» (В). Рассмотрим составное высказывание A→B, понимаемое как «если данный четырёхугольник квадрат, то около него можно описать окружность». Есть три варианта, когда высказывание A→B истинно:

А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность.

А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника).

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

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

В обычной речи связка «если..., то» описывает причинно–следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться «бессмысленностью» импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: «если президент США – демократ, то в Африке водятся жирафы», «если арбуз – ягода, то в бензоколонке есть бензин».

РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно...», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~. Высказывание истинно тогда и только тогда, когда значения А и В совпадают.

Пример. Высказывания «24 делится на 6 тогда и только тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3» истинны, а высказывания «24 делится на 6 тогда и только тогда, когда 24 делится на 5», «21 делится на 6 тогда и только тогда, когда 21 делится на 3» ложны.

Высказывания А и В, образующие составное высказывание A↔B, могут быть совершенно не связаны по содержанию, например: «три больше двух» (А), «пингвины живут в Антарктиде» (В). Отрицаниями этих высказываний являются высказывания «три не больше двух» (A), «пингвины не живут в Антарктиде» (B). Образованные из высказываний А и В составные высказывания A↔B и A↔B истинны, а высказывания A↔B и A↔B – ложны.

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

Импликацию можно выразить через дизъюнкцию и отрицание:

А→В = A v В

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А↔В = (A v В) · (B v А)

Вывод: операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания.

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

Логические формулы

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

Определение логической формулы:

1. Всякая логическая переменная и символы «истина» («1») и «ложь» («0») – формулы.

2. Если А и В – формулы, то A, А · В, А v В, А→B, А↔В – формулы.

3. Никаких других формул в алгебре логики нет.

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание «если я куплю яблоки или бананы, то приготовлю фруктовый пирог». Это высказывание формализуется в виде (A v B)→C. Такая же формула соответствует высказыванию «если Алексей знает английский или китайский язык, то он получит место переводчика».

Как показывает анализ формулы (A v B)→C, при определённых сочетаниях значений переменных A, B и C она принимает значение «истина», а при некоторых других сочетаниях – значение «ложь» (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

Некоторые формулы принимают значение «истина» при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v A, соответствующая высказыванию «Этот треугольник прямоугольный или косоугольный». Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.

В качестве другого примера рассмотрим формулу А · A, которой соответствует, например, высказывание «Оксана самая высокая студентка в группе, и в группе есть студентки выше Оксаны». Очевидно, что эта формула ложна, так как либо А, либо A обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

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

Равносильность двух формул алгебры логики обозначается символом «=«или символом «≡» Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Значения, которые принимают переменные, называют интерпретациями, например формула f(a,b)=«a связка b» имеет четыре интерпретации:

a=1(ИСТИНА), b=1(ИСТИНА);

a=1(ИСТИНА), b=0(ЛОЖЬ);

a=0(ЛОЖЬ), b=1(ИСТИНА);

a=0(ЛОЖЬ), b=0(ЛОЖЬ).

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

a	b	a	a Λ b	a V b	a → b	a ↔ b

Опираясь на данные таблицы истинности можно составлять таблицы истинности для более сложных формул, например, для формулы И–НЕ, которую можно записать так: (a Λ b), или так: . Эту таблицу истинности можно сформировать последовательно (вначале (a Λ b), затем (a Λ b)).

a	b	a Λ b	(a Λ b)

Подобным образом можно составить таблицу истинности для формулы ИЛИ–НЕ, которую можно записать так: (a V b), или так: .

a	b	a V b	(a V b)

 

Примечание: И–НЕ называют также «штрих Шеффера» (обозначают |) или «антиконъюнкция»; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция».

Для связок установлены соответствующие приоритеты (старшинство связок), в частности

Связка		Λ	V	→	↔
приоритет

 

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

Таблицу истинности для более сложной формулы f1(a,b)=(a Λ b V a Λ b) также можно сформировать (учитывая приоритеты связок) следующим образом:

a	b	a	b	a Λ b	a Λ b	f1(a,b)

 

Следует отметить также операцию «исключающее ИЛИ» (XOR), которую называют также «сложение по модулю 2», или «кольцевая сумма», обозначающуюся знаком плюс в окружности. Таблица истинности ее совпадает с таблицей истинности формулы f1(a,b).

a	b	a XOR b

 

Формулы могут включать также, в частности, так называемые, отношения порядка, например, меньше (<), не меньше (≥), больше (>), не больше (≤), равно (=), не равно (≠). Например, (a<b) Λ (c>d).

Формулы можно также представлять с помощью языка логических схем. В частности, операции конъюнкции, дизъюнкции, отрицания представляют соответствующими логическими схемами (функциональными элементами):

 

конъюнктор	дизъюнктор	инвертор
a Λ b a & b	a V b a b	a a   Альтернативное обозначение   a a

 

Для данных логических схем существуют типовые технические схемы.

Используя данные функциональные элементы можно создавать вычислительные схемы, например, для формул f1(a,b)=(a Λ b V a Λ b) и f2(a,b)=(a Λ b)

Полученную схему называют сумматором (полусумматором) так как при сложении двух одноразрядных двоичных чисел формула f1(a,b) позволяет вычислять сумму в младшем разряде. То есть: 1+1=2=102 (здесь младший разряд равен нулю), 1+0=1 (младший разряд равен единице), 0+1=1 (младший разряд равен единице), 0+0=0 (младший разряд равен нулю). Формула f2(a,b) позволяет производить перенос бита в старший разряд: 1+1=2=102 (здесь старший разряд равен единице). Сравните эти данные с таблицей истинности формул f1(a,b)=(a Λ b V a Λ b) и f2(a,b)=(a Λ b).

Для схем И–НЕ, ИЛИ–НЕ функциональные элементы выглядят так:

 

И–НЕ	ИЛИ–НЕ
(a Λ b) a & b	(a V b) a b (a V b) a b

 

Комбинацию этих элементов используют для построения триггеров (элементов с двумя устойчивыми состояниями 0 и 1). На триггерах, в частности, строятся статическая память, регистры. Так как триггер используется для запоминания одного бита, то для формирования 1 байта необходимо использовать 8 триггеров.

3 Контрольные вопросы

1. Что такое высказывание (приведите пример)?

2. Что такое составное высказывание (приведите пример)?

3. Как называются и как обозначаются (в языке математики) следующие операции: ИЛИ, НЕ, И, XOR, Если … то, Тогда и только тогда?

4. Укажите приоритеты выполнения операций: ИЛИ, ЕСЛИ … ТО, НЕ, И.

5. Составьте таблицу истинности для следующих операций: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, XOR.

6. Изобразите функциональные элементы: конъюнктор, дизъюнктор, инвертор.

7. Напишите формулы для вычисления суммы в младшем разряде и переноса в старший разряд.

8. Начертите схему сумматора.

9. Изобразите схемы И–НЕ, ИЛИ–НЕ и составьте для них таблицы истинности.

10. Что такое триггер?

Часть 4. Технические средства реализации информационных процессов