Представление символов в памяти ЭВМ

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

Для русского алфавита существует несколько кодировок (табл. 5.3).

Таблица 5.3. Кодировки букв алфавита русского языка

Кодировка	Операционная система	Количество кодируемых символов	Размер кода одного символа, байт
	MS DOS
1251 (Win-1251, CP-1251)	Windows
КОИ-8 (КОИ-8Р)	Unix
Unicode	Windows

В кодировках 866, 1251, КОИ-8 и Unicode первые 128 символов (цифры, заглавные и строчные латинские буквы, знаки препинания) со значениями кодов от 0 до 127 одни и те же и определяются стандартом ASCII (American Standard Code for Information Interchange – американский стандартный код для обмена информацией). Цифры 0, 1,..., 9 имеют соответственно коды 48, 49,..., 57; прописные латинские буквы A, B,..., Z (всего 26 букв) – коды 65, 66,..., 90; строчные латинские буквы a, b,..., z (всего 26 букв) – коды 97, 98,..., 122.

Вторые 128 символов со значениями кодов от 128 до 255 кодировок 866, 1251, КОИ-8 содержат символы псевдографики, математические операции и символы алфавитов, отличных от латинского. Причем разные символы разных алфавитов имели один и тот же код. Например, в кодировке 1251 символ русского алфавита Б имеет тот же код, что и символ Á в стандартной кодировке ASCII. Такая неоднозначность вызывала проблемы с кодировкой текста. Поэтому была предложена двухбайтовая кодировка Unicode, которая позволяет закодировать символы многих нелатинских алфавитов.

Десятичные значения кодов букв русского алфавита в кодировках 866, 1251 и Unicode приведены в табл. 5.4.

Таблица 5.4. Значения кодов букв русского алфавита

Кодировка	Коды русских букв
А-Я (без Ё)	а-я (без ё)	Ё	ё
	128-159	160-175 (а-п) 224-239(р-я)
	192-223	224-255
Unicode	1040-1071	1072-1103

В кодировке КОИ-8 (табл. 5.5) коды букв русского алфавита упорядочены не по расположению букв в алфавите, а по соответствию их буквам латинского алфавита. Например, коды латинских букв А, В, С имеют соответственно десятичные значения 65, 66, 67, а русских букв А, Б, Ц – значения 225, 226, 227.

Таблица 5.5. Значения кодов букв русского алфавита
в кодировке КОИ-8

A		К		Х		а		к		х
Б		Л		Ц		б		л		ц
В		М		Ч		в		м		ч
Г		Н		Ш		г		н		ш
Д		О		Щ		д		о		щ
Е		П		Ъ		е		п		ъ
Е		Р		Ы		ё		р		ы
Ж		С		Ь		ж		с		ь
З		Т		Э		з		т		э
И		У		Ю		и		у		ю
Й		Ф		Я		й		ф		я

 

Глава 6. ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

6.1. Алгебра высказываний.
Понятие, высказывание, умозаключение

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

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

Существуют три формы мышления:

1) понятие;

2) высказывание;

3) умозаключение.

Понятие объединяет совокупность объектов, обладающими некоторыми существенными признаками, которые отличают их от других объектов. Например, понятие «звезда» объединяет множество светящихся газовых шаров. Это понятие трудно спутать с таким понятием как, например, «автомобиль». Объекты, соответствующие одному понятию, образуют множество.

Понятие имеет две характеристики:

1) содержание;

2) объем.

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

Объем понятия «человек» определяется численностью людей, живущих в мире.

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

Истинным называется высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей, например: «Москва – столица России». Истинность высказывания кодируется единицей (1) и имеет значение «истина».

Ложным высказывание будет в том случае, когда оно не соответствует реальной действительности, например: «Париж – столица США». Ложность высказывания кодируется нулем (0) и имеет значение «ложь».

Обычно высказывания обозначаются логическими переменными – заглавными латинскими буквами с индесом или без, например, A = «Сегодня идет дождь». Логические переменные принимают только два значения 0 и 1.

Умозаключение позволяет из известных фактов (истинных высказываний) получать новые факты. Например, из факта «Все углы треугольника равны» следует истинность высказывания «Этот треугольник равносторонний».

Высказывания и логические операции над ними образуют алгебру высказываний (булеву алгебру), предложенную английским математиком Джорджем Булем.

Логические операции

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

1. Отрицание (обозначается также ØX, ~X).

Отрицание (NOT, читается «не X») – это высказывание, которое истинно, если X ложно, и ложно, если X истинно.

2. Конъюнкция XY (X&Y, XÙY).

Конъюнкция XY (AND, логическое умножение, «X и Y») – это высказывание, которое истинно только в том случае, если X истинно и Y истинно.

3. Дизъюнкция X+Y (XÚY).

Дизъюнкция X+Y (OR, логическая сумма, «X или Y или оба») – это высказывание, которое ложно только в том случае, если X ложно и Y ложно.

4. Стрелка Пирса X ¯ Y.

Стрелка Пирса X ¯ Y (NOR (NOT OR), ИЛИ-НЕ) – это высказывание, которое истинно только в том случае, если X ложно и Y ложно.

5. Штрих Шеффера X | Y.

Штрих Шеффера X | Y (NAND (NOT AND), И-НЕ) – это высказывание, которое ложно только в том случае, если X истинно и Y истинно.

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

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

X	Y		XY	X + Y	X ¯ Y	X | Y

Чтобы определить значение операции 0 + 1 в таблице истинности, необходимо на пересечении столбца X + Y (определяет операцию) и строки, где X = 0 и Y = 1 (так первый аргумент равен 0, а второй – 1), найти значение 1, которое и будет являться значением операции 0 + 1.

В алгебре высказываний существуют две нормальные формы: конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ).

КНФ – это конъюнкция конечного числа дизъюнкций нескольких переменных или их отрицаний (произведение сумм). Например, формула X(Y + Z) находится в КНФ.

ДНФ – это дизъюнкция конечного числа конъюнкций нескольких переменных или их отрицаний (сумма произведений). Например, формула X + YZ находится в ДНФ.

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

Снятие двойного отрицания (отрицание отрицания): =X. (6.1) Коммутативность: XY=YX. (6.2) X+Y=Y+X. (6.3) Ассоциативность: (XY)Z=X(YZ). (6.4) (X+Y)+Z=X+(Y+Z). (6.5) Дистрибутивность: X(Y+Z)=XY+XZ. (6.6) X+YZ=(X+Y)(X+Z). (6.7) Законы де Моргана: . (6.8) . (6.9) Идемпотентность: X+X=X. (6.10) X×X=X. (6.11) Закон противоречия: X× =0. (6.12)

Закон «исключения третьего»: X+ =1. (6.13) Свойства констант: X×1=X. (6.14) X×0=0. (6.15) X+1=1. (6.16) X+0=X. (6.17) Элементарные поглощения: X+XY=X. (6.18) X+ Y=X+Y. (6.19) X(X+Y)=X. (6.20) X( +Y)=XY. (6.21) Преобразование стрелки Пирса: X¯Y= . (6.22) Преобразование штриха Шеффера: X | Y= . (6.23)

Правило 6.1. (порядок применения формул при преобразованиях) Перечисленные формулы рекомендуется применять в следующем порядке:

1) преобразование стрелки Пирса (6.22) и штриха Шеффера (6.23);

2) законы де Моргана (6.8)-(6.9);

3) формулы дистрибутивности (6.6)-(6.7);

4) элементарные поглощения (6.18)-(6.21).

Обычно формула приводится к ДНФ, а затем отдельные слагаемые поглощаются.

Логические функции