"Алгебра логики"
Методическое пособие
Автор: Сафонова Ольга Александровна, преподаватель высшей категории, Железнодорожный техникум Нижегородский филиал МИИТ, г.Нижний Новгород
В раздел среднее профессиональное образование
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО
ТРАНСПОРТА
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
"МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ
СООБЩЕНИЯ» (МГУПС (МИИТ))
НИЖЕГОРОДСКИЙ ФИЛИАЛ МИИТ
МЕТОДИЧЕСКОЕ ПОСОБИЕ
по теме
: Алгебра логики
по дисциплине
: Прикладная математика
для специальности: 220415 «Автоматика и телемеханика на транспорте (на железнодорожном транспорте)» Работу составила: преподаватель высшей квалификационной категории Сафонова О.А. Нижний Новгород 2014 г.
ОДОБРЕНО Цикловой комиссией Общеобразовательных дисциплин Протокол № 5 От «12 » января 2014 г. Председатель комиссии Захарова Н.А. Составлено в соответствии с Государственными требованиями к минимуму содержания и уровню подготовки выпускника по дисциплине «Прикладная математика» специальности 220415 «Автоматика и телемеханика на транспорте (на железнодорожном транспорте)» Методическое пособие. Нижегородский Филиал МИИТ Н.Новгород, 2014 г. - 36 стр. Составитель: преподаватель Сафонова О.А. Предлагаемое учебное пособие по курсу «Прикладная математика» представляет собой учебный материал по разделу «Алгебра логики» в виде конспекта лекций и практикума с методикой решения типовых задач. Методическое пособие рассчитано на студентов, обучающихся по специальности «Автоматика и телемеханика на транспорте (на железнодорожном транспорте)». Материалы пособия могут быть использованы преподавателями при проведении занятий по отдельным темам.
1. Системы счисления в алгебре логике
1. Системой счисления
называется совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (их называют цифрами), а остальные числа получаются в результате каких-либо операций над цифрами данной системы счисления. Система называется
позиционной
, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Примером позиционной формы записи чисел является та, которой мы пользуемся (так называемая арабская форма чисел). Так, в числах 123 и 321 значения цифры 3, например, определяются ее положением в числе: в первом случае она обозначает три единицы (т.е. просто три), а во втором – три сотни (т.е. триста). Римские числа являются примером полупозиционной системы образования числа: так, в числах IX и XI знак I обозначает в обоих случаях единицу (признак непозиционной системы), но, будучи расположенным слева от знака X (обозначающего десять), вычитается из десяти, а при расположении справа – прибавляется к десяти. В первом случае полное значение числа равно 9, во втором – 11. Рассмотрим позиционные системы счисления. Число единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления. Если количество таких цифр равно р, то система счисления называется р- ичной. Основание системы счисления совпадает с количеством цифр, используемых для записи чисел в этой системе счисления. Запись произвольного числа 1 2 1 0 1 ... , ... n n m X a a a a a a в р-ичной позиционной системе счисления основывается на представлении этого числа в виде многочлена: 1 2 1 0 1 1 2 1 0 1 ... ... n n m n n m X a p a p a p a p a p a p .
2. Примеры позиционной системы счисления - десятичная, восьмеричная,
шестнадцатеричная, двоичная системы счисления и т. д.
1.
Десятичная
система
счисления
используется для кодирования дискретного сигнала, потребителем которого является так называемый конечный пользователь – неспециалист в области информатики (очевидно, что и любой человек может выступать в роли такого потребителя). Используемые знаки для представления числа – цифры от 0 до 9. Основание системы 10 p . 2 1 0 1 2 10 125,57 1 10 2 10 5 10 5 10 7 10 2.
Двоичная система счисления
используется для кодирования дискретного сигнала, потребителем которого является вычислительная техника. Такое
положение дел сложилось исторически, поскольку двоичный сигнал проще представлять на аппаратном уровне. В этой системе счисления для представления числа применяются два знака – 0 и 1. 3.
Шестнадцатеричная система счисления
используется для кодирования дискретного сигнала, потребителем которого является хорошо подготовленный пользователь – специалист в области информатики. В частности, шестнадцатеричная система счисления применяется в низкоуровневом программировании (например, в языке Assembler) для более краткого представления двоичных чисел. Используемые знаки для представления числа – десятичные цифры от 0 до 9 и буквы латинского алфавита – A, B, C, D, E, F. A соответствует десятичному числу 10, В – 11, С – 12, D – 13, E – 14, F – 15. 3 2 1 0 16 10 1 4 1 16 10 16 4 16 15 16 6735 AF 4.
Восьмеричная
система
счисления
наряду с двоичной и шестнадцатеричной используется в цифровой электронике и компьютерной технике, однако в настоящее время применяется редко (ранее использовалась в низкоуровневом программировании, вытеснена шестнадцатеричной). В восьмеричной системе счисления используется восемь знаков-цифр (от 0 до 7). Соответствие между первыми несколькими натуральными числами всех четырех систем счисления представлено в таблице перевода: Десятичная система Двоичная система Восьмеричная система Шестнадцатеричная система 0 0 0 0 1 1 1 1 2 10 2 2 3 11 3 3 4 100 4 4 5 101 5 5 6 110 6 6 7 111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F 16 10000 20 10
5.
В
двоично–десятичной
системе
число записывается сначала с помощью десятичной системы, а затем каждая из входящих цифр представляется в двоичной системе. 10 2 2593 0010 0101 1001 0011 10010110010011
2. Перевод чисел из одной системы счисления в другую
При переводе чисел из десятичной системы счисления в систему с основанием 1 p обычно используют следующий алгоритм: 1) если переводится целая часть числа, то она делится на p , после чего запоминается остаток от деления. Полученное частное вновь делится на p , остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на p выписываются в порядке, обратном их получению; 2) если переводится дробная часть числа, то она умножается на p , после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на p и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая дробь в системе счисления с основанием p . Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием p . Для перевода числа из двоичной системы счисления в систему счисления с основанием, являющимся степенью двойки: 2 m a , достаточно объединить цифры двоичного числа в группы размера m (значение степени двойки в представлении основания a ) и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8 = 2 3 ). В целой части будем производить группировку справа налево, в дробной — слева направо. Если в последней группе недостает цифр, дописываем нули: в целой части — слева, в дробной — справа. Затем каждая группа заменяется соответствующей цифрой новой системы. При переводе чисел из системы счисления с основанием p в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер -1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления. Перевод чисел из одной системы счисления в другую составляет важную часть машинной арифметики.
Рассмотрим основные правила перевода.
1. Для перевода
двоичного числа в десятичное
необходимо записать его в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 2, и вычислить по правилам десятичной арифметики: 1 2 1 0 1 2 1 2 1 0 1 2 2 ... 2 2 2 ... 2 n n m n n m X a a a a a a При переводе удобно пользоваться таблицей степеней двойки: Степени числа 2 n (степень) 0 1 2 3 4 5 6 7 8 9 10 1 2 4 8 16 32 64 128 256 512 1024 Пример. Число 2 101,11 перевести в десятичную систему счисления 2 0 1 2 2 10 101,11 1 2 1 2 1 2 1 2 5,75 2. Для перевода
восьмеричного числа в десятичное
необходимо записать его в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 8, и вычислить по правилам десятичной арифметики: 1 2 1 0 1 8 1 2 1 0 1 8 8 ... 8 8 8 ... 8 n n m n n m X a a a a a a При переводе удобно пользоваться таблицей степеней восьмерки: Степени числа 8 n (степень) 0 1 2 3 4 5 6 1 8 64 512 4096 32768 262144 Пример. Число 8 1025,6 перевести в десятичную систему счисления. 3 1 0 1 8 10 1025,6 1 8 2 8 5 8 6 8 533,75
3. Для перевода
шестнадцатеричного числа в десятичное
необходимо записать его в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 16, и вычислить по правилам десятичной арифметики: 1 2 1 0 1 16 1 2 1 0 1 16 16 ... 16 16 16 ... 16 n n m n n m X a a a a a a При переводе удобно пользоваться таблицей степеней числа 16: Степени числа 16 n (степень) 0 1 2 3 4 5 6 1 16 256 4096 65536 1048576 16777216 Пример
.
Число 16 14AF перевести в десятичную систему счисления. 3 2 1 0 16 10 1 4 1 16 10 16 4 16 15 16 6735 AF
4.
Для перевода
целого
десятичного
числа
в
двоичную
систему
его необходимо последовательно делить на 2 до тех пор, пока не останется остаток, меньший или равный 1. Число в двоичной системе записывается как последовательность последнего результата деления и остатков от деления в обратном порядке. Пример
.
Число 10 22 перевести в двоичную систему счисления. 22| 2 22 11| 2
0
10 5| 2
1
4 2| 2
1
2
1
0
10 2 22 10110
5.
Для перевода
правильной
десятичной
дроби
в
двоичную
систему
необходимо произвести последовательное умножение этой дроби и получающихся дробных частей произведения на 2. Результатом перевода является прямая последовательность целых чисел. Пример. Число 10 0,65625 перевести в двоичную систему счисления 0,65625 2 1 31250 2 1 2500 2 0 5000 2 1 0000 10 2 0,65625 0,10101
6.
Если задана неправильная дробь, то следует отдельно перевести в новую систему счисления отдельно целую и дробные части.
7.
Для перевода
десятичного
числа
в
восьмеричную
систему
его необходимо последовательно делить на 8 до тех пор, пока не останется остаток, меньший или равный 7. Число в восьмеричной системе записывается как последовательность цифр последнего результата деления и остатков от деления в обратном порядке. Пример. Число 10 571 перевести в восьмеричную систему счисления. _571| 8 56 _71| 8 _11 64 _8| 8 8
7
8
1
3 0
10 8 571 1073
8.
Для перевода
десятичного числа в шестнадцатеричную систему
его необходимо последовательно делить на 16 до тех пор, пока не останется остаток, меньший или равный 15. Число в шестнадцатеричной системе записывается как последовательность цифр последнего результата деления и остатков от деления в обратном порядке. Пример. Число 10 7467 перевести в шестнадцатеричную систему счисления. _7467| 16 7456 _466| 16
11
464 _29| 16
2
16
1
13
10 16 7467 1 2 DB
9.
Чтобы перевести число из
двоичной системы в восьмеричную
, его нужно разбить на триады (тройки цифр), начиная с младшего разряда, в случае необходимости дополнив старшую триаду нулями, и каждую триаду заменить соответствующей восьмеричной цифрой. При переводе удобно пользоваться таблицей триад: Триады цифра 0 1 2 3 4 5 6 7 триада 000 001 010 011 100 101 110 111 Пример
.
Число 2 1001011 перевести в восьмеричную систему счисления. 28 001 001 011 113
10.
Чтобы перевести число из
двоичной системы в шестнадцатеричную
, его нужно разбить на тетрады (четверки цифр), начиная с младшего разряда, в случае необходимости дополнив старшую тетраду нулями, и каждую тетраду заменить соответствующей восьмеричной цифрой.
При переводе удобно пользоваться таблицей тетрад: Тетрады 0 1 2 3 4 5 6 7 8 9 A B C D E F 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Пример. Число 2 1011100011 перевести в шестнадцатеричную систему счисления. 2 10 1011100011 2 3 E
11.
Для перевода
восьмеричного
числа
в
двоичное
необходимо каждую цифру заменить эквивалентной ей двоичной триадой. Пример. Число 8 531 перевести в двоичную систему счисления. 82 531 101011001
12.
Для перевода
шестнадцатеричного
числа
в
двоичное
необходимо каждую цифру заменить эквивалентной ей двоичной тетрадой. Пример. Число 16 8 EE перевести в двоичную систему счисления. 16 2 8 111011101000 EE
13.
При переходе из
восьмеричной
системы
счисления
в
шестнадцатеричную
и обратно, необходим промежуточный перевод чисел в двоичную систему. Пример 1. Число 16 FEA перевести в восьмеричную систему счисления. 16 2 2 8 111111101010 111 111 101 010 7752 FEA Пример 2. Число 8 6635 перевести в шестнадцатеричную систему счисления. 8 2 2 16 6635 110110011101 1101 1001 1101 9 DD
Упражнения
1. Переведите числа из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную системы счисления.
1.
949;
2.
763;
3.
994,125;
4.
523,25;
5.
203,82;
6.
563;
7.
264;
8.
234,25;
9.
53,125;
10.
286,16;
11.
279;
12.
281;
13.
841,375;
14.
800,3125;
15.
208,92. 2. Переведите числа в десятичную систему счисления.
1.
2 111000111
2.
2 100011011
3.
2 1100101,101
4.
2 1001001,011
5.
8 335,7
6.
8 665,42
7.
16 14C,A
8.
16 246,18
9.
2 1100010010
10.
2 10011011
11.
2 1111000001,01
12.
2 10110111,012
13.
8 416,1
14.
8 203,3
15.
16 287,D
16.
16 EF,A
17.
2 1100111001
18.
2 10011101
19.
2 1111011,001
20.
2 110000101,01
21.
8 1601,56
22.
8 125,02
23.
16 16E,B4
24.
16 13B,4 3. Переведите числа в восьмеричную и шестнадцатеричную системы счисления.
1.
2 111000111
2.
2 100011011
3.
2 1100101,101
4.
2 1001001,011
5.
2 1100010010
6.
2 10011011
7.
2 1111000001,01
8.
2 10110111,012
9.
2 1100111001
10.
2 10011101
11.
2 1111011,001
12.
2 110000101,01 4. Переведите числа из шестнадцатеричной системы счисления в восьмеричную: А54; 21E,7F; 0,FD 5. Переведите числа из восьмеричной системы счисления в шестнадцатеричную: 344; 0,7612; 333,222
2. Двоичная арифметика
1. Арифметические операции одноразрядных двоичных чисел
1.
Правила сложения в двоичной системе счисления 0 0 0 0 1 1 1 0 1 1 1 10
2.
Правила вычитания в двоичной системе счисления 0 0 0 1 0 1 1 1 0 1 0 1 1
3.
Правила умножения в двоичной системе счисления 0 0 0 1 0 0 0 1 0 1 1 1
2. Арифметические операции многоразрядных двоичных чисел
1.
Сложение
многоразрядных двоичных чисел происходит в соответствии с вышеприведенной таблицей сложения с учетом возможных переносов из младших разрядов в старшие . Пример 1. 1 1 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 Пример 2. Иногда возможен перенос не только в следующий, но и более старший разряд. 1 11 1 1 1 1 1 11 1 1 1 1 1 0 0 1
Проверим правильность вычислений сложением в десятичной системе счисления. Переведем двоичные числа в десятичную систему счисления и затем их сложим: 4 2 1 2 10 3 2 0 2 10 4 2 0 2 10 10110 1 2 1 2 1 2 22 1101 1 2 1 2 1 2 13 10101 1 2 1 2 1 2 21 10 10 10 10 22 13 21 56 Теперь переведем результат двоичного сложения в десятичное число: 5 4 3 2 10 111000 1 2 1 2 1 2 56 Сравним результаты - сложение выполнено правильно.
2.
Вычитание
многоразрядных двоичных чисел происходит в соответствии с вышеприведенной таблицей вычитания с учетом возможных заемов из старших разрядов. Пример. 10 1 10 1 10 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1
3.
Умножение
многоразрядных двоичных чисел происходит в соответствии с вышеприведенной таблицей умножения по обычной схеме, применяемой в десятичной системе счисления с последовательным умножением множимого на цифры множителя . Пример. 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1
4.
Операция деления
выполняется по алгоритму, подобному алгоритму выполнения операции деления в десятичной системе счисления.
Пример. 1001 1 0 1 0 0 1 1 0 1 100101 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1
Упражнения
1. Выполните сложение чисел. 22 22 22 1)1110101010 +10111001 2)10111010 +10010100 3)111101110,1011 +1111011110,1 22 22 22 4)10111111 +110010000 5)110010100 +1011100001 6)00000101,0101 +1010000110,01 22 22 22 7)1000100001 +1011100110 8)1101110011 +111000101 9)1011011,01 +1000101110,1001 4. Выполните вычитание чисел. 22 22 22 1)1000000100 -101010001 2) 1010111101 -111000010 3) 1101000000,01 -1001011010,011 22 22 22 4)1000001001 -111110100 5) 1111000101 -1100110101 6) 1100110101,1 -1011100011,01 22 22 22 7) 11110010 -10101001 8) 1110100001 -1011001001 9) 1101001010,1 -1011101001,11011 5. Выполните умножение чисел. 22 22 22 1) 1001011 1010110 2) 111101 1010111 3) 1001001 100010 6. Выполните деление чисел 22 22 22 4) 10010,11 10011,01 5) 101,101 1011,111 6) 110100,1 101010 22 22 22 1) 1001011 101 2) 111101 1010111 3) 1001001 10001 22 22 22 4) 10010 10011 5) 101101 101 6) 1101001 10101 7. Вычислите значения выражений:
8 2 8 10 16 6 2 2 8 2 16 2 8 2 2 8 2 8 1)256 10110,1 (60 12 ) 1 2)1 100101100 1010 217 3)1010 (106 11011101 ) 12 4)1011 1100 14 (100000 40 ) F AD 8. В какой системе счисления справедливо следующее: 1) 20 + 25 = 100; 2) 22 + 44 = 110?
Контрольные вопросы:
1. Что называется системой счисления? 2. На какие два типа можно разделить все системы счисления? 3. Какие системы счисления называются непозиционными? Почему? Приведите пример такой системы счисления и записи чисел в ней? 4. Какие системы счисления называются позиционными? 5. Что называется основанием системы счисления? 6. Как можно представить целое положительное число в позиционной системе счисления? 7. Приведите пример позиционной системы счисления. 8. Охарактеризуйте двоичную систему счисления: алфавит, основание системы счисления, запись числа. 9. Почему двоичная система счисления используется в информатике? 10. Сформулируйте правила перевода чисел из системы счисления с основанием р в десятичную систему счисления и обратного перевода: из десятичной системы счисления в систему счисления с основанием S. 11. Как выполнить перевод чисел из двоичной СС в восьмеричную и обратный перевод? Из двоичной СС в шестнадцатеричную и обратно? 12. По каким правилам выполняется перевод из восьмеричной в шестнадцатеричную СС и наоборот?
3.Структура и форматы двоичных чисел
1. Формы представления чисел
Машинным изображением числа называют его представление в разрядной сетке ЭВМ. В вычислительных машинах применяются две формы представления чисел:
1.
естественная форма или форма с фиксированной запятой (точкой);
2.
нормальная форма или форма с плавающей запятой (точкой); Пример: (естественная форма) 3 5 3 425,34 42534 10 0,0042534 10 0,42534 10 (нормальная форма) Всякое десятичное число, прежде чем оно попадает в память компьютера, преобразуется по схеме: 10 2 2 10 p X X M После этого осуществляется ещё одна важная процедура:
1.
мантисса с её знаком заменяется кодом мантиссы с её знаком;
2.
порядок числа с его знаком заменяется кодом порядка с его знаком. Указанные коды двоичных чисел - это образы чисел, которые и воспринимают вычислительные устройства. Каждому двоичному числу можно поставить в соответствие несколько видов кодов. Существуют следующие коды двоичных чисел: Прямой код; Обратный код; Дополнительный код. Последние две формы применяются особенно широко, так как позволяют упростить конструкцию арифметико-логического устройства компьютера путем замены разнообразных арифметических операций операцией сложения.
1. Прямой код
Представление числа в привычной форме "знак"-"величина", при которой старший разряд ячейки отводится под знак, а остальные - под запись числа в двоичной системе, называется
прямым кодом
двоичного числа. Например, прямой код двоичных чисел 1001 и -1001 для 8-разрядной ячейки равен 00001001 и 10001001 соответственно. Положительные числа в ЭВМ всегда представляются с помощью прямого кода. Прямой код числа полностью совпадает с записью самого числа в ячейке машины. Вообще, положительные числа в прямом, обратном и дополнительном кодах изображаются одинаково — двоичными кодами с цифрой 0 в знаковом разряде.
Пример: 10 2 23 23 10111 00010111 пр x x знак числа Прямой код отрицательного числа отличается от прямого кода соответствующего положительного числа лишь содержимым знакового разряда. Пример: 10 2 31 31 11111 10011111 пр x x знак числа
2. Обратный код
Обратный код
положительного двоичного числа совпадает с прямым кодом. Для отрицательного числа все цифры числа заменяются на противоположные (1 на 0, 0 на 1), а в знаковый разряд заносится единица. Пример: 1) 23 00010111 обр x x 2) 31 10011111 11100000 пр обр x x x
3. Дополнительный код
Дополнительный код положительного числа
равен прямому коду этого числа. Пример: 23 00010111 00010111 обр доп x x x
Дополнительный
код
отрицательного
числа
m равен
2
k
- |m|, где k - количество разрядов в ячейке. Также дополнительный код отрицательного числа образуется путём прибавления 1 к обратному коду.
Алгоритм получения дополнительного кода отрицательного числа:
1. модуль отрицательного числа представить прямым кодом в k двоичных разрядах; 2. значение всех бит инвертировать: все нули заменить на единицы, а единицы на нули (таким образом, получается k-разрядный обратный код исходного числа);
3. к полученному обратному коду прибавить единицу. Пример: 31 10011111 11100000 1 11100001 пр обр доп x x x x Дополнительный код используется для упрощения выполнения арифметических операций. Если бы вычислительная машина работала с прямыми кодами положительных и отрицательных чисел, то при выполнении арифметических операций следовало бы выполнять ряд дополнительных действий. Например, при сложении нужно было бы проверять знаки обоих операндов и определять знак результата. Если знаки одинаковые, то вычисляется сумма операндов и ей присваивается тот же знак. Если знаки разные, то из большего по абсолютной величине числа вычитается меньшее и результату присваивается знак большего числа. То есть при таком представлении чисел (в виде только прямого кода) операция сложения реализуется через достаточно сложный алгоритм. Если же отрицательные числа представлять в виде дополнительного кода, то операция сложения, в том числе и разного знака, сводится к их поразрядному сложению. Для компьютерного представления целых чисел обычно используется один, два или четыре байта, то есть ячейка памяти будет состоять из восьми, шестнадцати или тридцати двух разрядов соответственно. При изучении видов двоичных кодов нужно четко понимать отличие двоичной системы счисления от двоичных кодов. Двоичная система счисления является разделом математики и соответственно работает с двоичными числами. Например, для записи двоичного числа кроме символов '0' и '1' применяются символы '+', '–', двоичная запятая. Может применяться пробел для отбрасывания незначащих цифр. Количество разрядов при записи двоичного числа неограниченно. В двоичном коде набор символов ограничен нулем и единицей, поэтому для записи символов '+' и '–' в двоичном коде отводится определенный разряд. Двоичная запятая обычно подразумевается между определенными разрядами двоичного кода. Количество разрядов в двоичном коде тоже строго ограничено. Поэтому незначащие разряды двоичного числа в двоичном коде заполняются нулями, либо повторением знака числа в зависимости от вида двоичного кода.
4. Сложение чисел с использованием кодов
Введение дополнительных и обратных кодов позволяет заменить операцию вычитания операцией сложения.
Рассмотрим выполнение операции сложения с использованием кодов на
примерах.
Предположим, что технические возможности вычислительной системы позволяют оперировать только восьмиразрядными двоичными числами. Если старший разряд двоичного числа отведен под знак, тогда оставшиеся семь разрядов не позволяют оперировать числами, большими 127. Если результат какой - либо операции превысит значение 127, то такое событие называется переполнением разрядной сетки.
Пример
1. Выполнить
сложение
двоичных
эквивалентов
десятичных
чисел
54 x
и
68 y
.
Так как числа х и у положительные, то прямые, обратные и дополнительные коды этих чисел будут одинаковыми, а знаковый разряд равен нулю: 2 10 0011011 0 0100010 0 0011011 0 0100010 0 0111101 0 12 2 5 4 6 8 12 2 пр обр доп пр обр доп x x x y y y В знаковом разряде результата стоит ноль, то есть результат положительный. Переведя полученный результат в десятичный эквивалент, получим х + у = 122.
Пример 2. Выполнить операцию сложения чисел х = 77 и у = –36
. Рассмотрим выполнение операции сложения положительного и отрицательного чисел с использованием обратного и дополнительного кодов. 1. Первоначально получим обратный и дополнительный код чисел х и у: 0100110 1 1010010 0 1101101 1 1101110 0 п р обр до п п р обр до п x x x y y y 2. Выполним операцию сложения с использованием обратного кода:
01001101 11011011 100101000 1 00101001 В обратном коде единица переполнения разрядной сетки прибавляется к младшему разряду. 3.Выполним операцию сложения с использованием дополнительного кода: 01001101 11011100 100101000 00101001 отбрасываем В дополнительном коде единица переполнения отбрасывается. В знаковом разряде результата стоит ноль, следовательно, результат операции сложения – положительный. Переведя полученный результат в десятичный эквивалент, получим х + у = 41.
Пример 3. Выполнить операцию сложения чисел х = –77 и у = 36.
1. Получим прямые, обратные и дополнительные коды слагаемых: 00100100 11001101 10110010 10110011 пр обр доп пр обр доп y y y x x x 2. Выполним операцию сложения с использованием обратного кода:
10110010 00100100 11010110 При выполнении операции переполнения разрядной сетки не произошло, поэтому не требуется прибавления единицы к младшему разряду. Так как в результате сложения двух обратных кодов двоичных чисел будет получен обратный код результата, а в знаковом разряде результата стоит единица, что указывает на отрицательное число, полученный результат необходимо преобразовать в прямой код: 11010110 10101001 обр пр x y x y 3. Выполним операцию сложения с использованием дополнительного кода: 10110011 00100100 11010111 В результате выполнения операции получено отрицательное число, поэтому произведем преобразование дополнительного кода результата в прямой: 11010111 11010110 10101001 доп обр пр x y x y x y В знаковом разряде результата стоит единица, следовательно, результат операции сложения число отрицательное. Переведя полученный результат в десятичный эквивалент, получим х + у = –41 .
Пример 4. Выполнить операцию сложения чисел х = –77 и у = -21.
1. Получим прямые, обратные и дополнительные коды слагаемых: 11001101 10010101 10110010 11101010 10110011 11101011 пр пр обр обр доп доп xy xy xy
2. Выполним операцию сложения с использованием обратного кода: 10110010 11101010 110011100 1 10011101 В обратном коде единица переполнения разрядной сетки прибавляется к младшему разряду. Так как в результате сложения двух обратных кодов двоичных чисел будет получен обратный код результата, а в знаковом разряде результата стоит единица, что указывает на отрицательное число, полученный результат необходимо преобразовать в прямой код: 10011101 11100010 обр пр x y x y 3. Выполним операцию сложения с использованием дополнительного кода: 10110011 11101011 110011110 10011110 отбрасываем В дополнительном коде единица переполнения отбрасывается. В результате выполнения операции получено отрицательное число, поэтому произведем преобразование дополнительного кода результата в прямой: 10011110 10011101 11100010 доп обр пр x y x y x y В знаковом разряде результата стоит единица, следовательно, результат операции сложения число отрицательное. Переведя полученный результат в десятичный эквивалент, получим х + у = –98 .
5. Форма с фиксированной запятой
В форме с фиксированной запятой
в разрядной сетке выделяется строго определенное число разрядов для целой и для дробной частей числа. Левый
(старший) разряд хранит признак знака (0 – "+", 1 – "-") и для записи числа не используется. Сама запятая никак не изображается, но ее место строго фиксировано и учитывается при выполнении всех операций с числами. Независимо от положения запятой в машину можно вводить любые числа, т.к. A = [A] · K А , где А – произвольное число, [A] – машинное изображение числа в разрядной сетке, K А - масштабный коэффициент. С фиксированной запятой числа изображаются в виде последовательности цифр с постоянным для всех чисел положением запятой, отделяющей целую часть от дробной (например, 32,54; 0,0036; –108,2). Форма представления чисел с фиксированной запятой упрощает аппаратную реализацию ЭВМ, уменьшает время выполнения машинных операций, однако при решении задач на машине необходимо постоянно следить за тем, чтобы все исходные данные, промежуточные и окончательные результаты находились в допустимом диапазоне представления. Если этого не соблюдать, то возможно переполнение разрядной сетки, и результат вычислений будет неверным. От этих недостатков в значительной степени свободны ЭВМ, использующие форму представления чисел с плавающей точкой, или нормальную форму. В современных компьютерах форма представления чисел с фиксированной запятой используется только для целых чисел.
6. Форма с плавающей запятой
С плавающей запятой
(ПЛЗ) числа изображаются в виде: r X M p , где M - мантисса числа (правильная дробь в пределах 0,1 ≤ M < 1), r - порядок числа (целое), р - основание системы счисления. Например, приведенные выше числа с фиксированной запятой можно преобразовать в числа с плавающей запятой так: 0,3254×10 2 , 0,36×10 -2 , –0,1082×10 3 . Нормальная форма представления имеет огромный диапазон чисел и является основной в современных ЭВМ. При представлении чисел с плавающей запятой часть разрядов ячейки отводится для записи порядка числа, остальные разряды - для записи мантиссы. По одному разряду в каждой группе отводится для изображения
знака порядка и знака мантиссы. Для того, чтобы не хранить знак порядка, используется так называемый смещённый порядок, который рассчитывается по формуле 2 (a-1) + ИП, где a - количество разрядов, отводимых под порядок, ИП - истинный порядок. В конкретной ЭВМ диапазон представления чисел с плавающей запятой зависит от основания системы и числа разрядов для представления порядка. При этом у одинаковых по длине форматов чисел с плавающей запятой с увеличением основания системы счисления существенно расширяется диапазон представляемых чисел. Точность вычислений при использовании формата с плавающей запятой определяется числом разрядов мантиссы. Она увеличивается с увеличением числа разрядов.
Упражнения
1. Запишите следующие числа в прямом, обратном и дополнительном кодах. 1) 1101011; 2) -101011; 3) -101101; 4) -1100111. 2. Запишите числа в прямом коде (формат 1 байт): 1) 31; 2) -63; 3) 65; 4) -128.
3.
Запишите числа в обратном и дополнительном кодах (формат 1 байт): 1) -9; 2) -15; 3) -127; 4) -128.
3.
Найдите десятичные представления чисел, записанных в дополнительном коде: 1) 1 1111000; 2) 1 0011011; 3) 1 1101001; 4) 1 0000000.
4.
Найдите десятичные представления чисел, записанных в обратном коде: 1) 1 1101000; 2) 1 0011111; 3) 1 0101011; 4) 1 0000000.
5.
Выполните вычитания чисел путем сложения их обратных (дополнительных) кодов в формате 1 байт. Укажите, в каких случаях имеет место переполнение разрядной сетки: 1) 9 - 2; 4) -20 - 10; 7) -120 - 15; 2) 2 - 9; 5) 50 - 25; 8) -126 - 1; 3) -5 - 7; 6) 127 - 1; 9) -127 - 1.
Контрольные вопросы
1. Что понимают под прямым кодом числа ? 2. Как образуется обратный код целого положительного числа? 3. Как образуется обратный код целого отрицательного числа? 4. Каков алгоритм сложения чисел в прямом коде? 5. Каков алгоритм сложения чисел в обратном коде?
5. Основные понятия алгебры логики
1.Булевы функции
Функцией алгебры логики
называется функция 1 ( ,... ) n f x x , принимающая одно из двух значений 0 или 1, от n переменных, каждая из которых принимает одно из двух значений 0 или 1. Функции алгебры логики также называются
булевыми функциями
. n P - множество булевых функций n переменных 2 2 n n P
Элементарные функции от одной переменной
Элементарные функции двух переменных
x y 0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 -
дизъюнкция
(логическое сложение); -
конъюнкция
(логическое умножение); -
сумма по модулю 2
; -
импликация
(логическое следование) -
эквивалентность
; | xy -
штрих Шеффера
(антиконъюнкция); -
стрелка Пирса
(антидизъюнкция). Таблицы, в которых представлены значения булевых функций, называются
таблицами истинности (таблицами соответствия)
. х х x 0 1 0 1 0 1 1 0 0 0 1 1
Пример. Построить таблицу истинности функции: ( , , ) 1 f x y z x y y z z x y z x y xy yz 1 yz 1 x y y z z ( , , ) f x y z 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0
2. Основные законы алгебры логики
1.
Законы коммутативности
2.
Законы ассоциативности
3.
Законы дистрибутивности
4.
Закон двойного отрицания
xx =
5.
Законы де Моргана
̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅
6.
Законы поглощения
x x y x x x y x
7.
Выражение эквивалентности через другие операции
̅ ̅ ̅
8.
Выражение суммы по модулю 2 через другие операции
̅ ̅
9.
Выражение импликации через другие операции
̅ В справедливости этих формул можно убедиться, построив таблицы истинности. Пример. Доказать закон дистрибутивности: с помощью таблицы истинности x y z 0 0 0 0
0
0 0
0
0 0 1 1
0
0 0
0
0 1 0 1
0
0 0
0
0 1 1 0
0
0 0
0
1 0 0 0
0
0 0
0
1 0 1 1
1
0 1
1
1 1 0 1
1
1 0
1
1 1 1 0
0
1 1
0
С помощью законов алгебры логики можно упрощать исходные формулы и получать новые. Если в выражении не скобок, то используется следующий приоритет операций: отрицание, конъюнкция, дизъюнкция, сумма по модулю 2, сумма по модулю 2, эквивалентность, импликация. Пример. Упростить выражение: x y z x y . x y z x y x y z x y x y x y x y
4.
Канонические формы представления функций
1.
Совершенная дизъюнктивная нормальная форма
Простой конъюнкцией называется конъюнкция одной или нескольких перем енных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание). Например, xy z является простой конъюнкцией. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций Например, выражение xz y z является ДНФ.
Совершенной дизъюнктивной нормальной формой
(СДНФ) называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные (либо сами, либо их отрицания). Например, выражение x yz является ДНФ, но не СДНФ. Выражение xyz x yz xyz x yz xyz является СДНФ.
Всякая
булева
функция,
кроме
константы
0,
имеет
единственную
СДНФ.
Рассмотрим способы построения СДНФ.
1. Табличный способ Пример. Построить СДНФ функции, заданной таблицей истинности (ТИ). x y z ( , , ) f x y z 0 0 0 0
0
0
1
1
0
1
0
1
0 1 1 0 1 0 0 0
1
0
1
1
1
1
0
1
1 1 1 0
Алгоритм построения СДНФ по ТИ
1. Отметит те строки, в последнем столбце которых стоит 1. 2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то
в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: x yz — для 2-й строки; xy z — для 3-й строки, x yz — для 6-й строки, xy z — для 7-й строки. 3. Все полученные конъюнкции связать в дизъюнкцию: x yz xyz x yz xyz 2. Аналитический способ построения СДНФ 1. Привести формулу с помощью равносильных преобразований к ДНФ. 2. Удалить члены дизъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся); 3. Из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного; 4. Из одинаковых членов каждой конъюнкции (если такие окажутся) удалить все, кроме одного; 5. Если в какой-нибудь конъюнкции не содержится переменной i x из числа переменных, входящих в исходную формулу, добавить к этой конъюнкции член ii xx и применить закон дистрибутивности конъюнкции относительно дизъюнкции; 6. Если в полученной дизъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3. Полученная формула и является СДНФ данной формулы Пример. Построить СДНФ функции f x y z ( ) ( ) f f x y z xz yz x y y z x x yz xyz x yz xyz xyz xyz x yz xyz СДНФ 2.
Совершенная конъюнктивная нормальная форма
Простой дизъюнкцией называется дизъюнкция одной или нескольких переме нных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Например, выражение x y z , – простая дизъюнкция. Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций Например, выражение x z y z является КНФ.
Совершенной
конъюнктивной
нормальной
формой
(СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания). Например, выражение x y z x y z x y z является СКНФ.
Всякая
булева
функция,
кроме
константы
1,
имеет
единственную
СКНФ.
Рассмотрим способы построения СКНФ.
1.Табличный способ Пример. Построить СКНФ функции, заданной таблицей истинности (ТИ). x y z ( , , ) f x y z
0
0
0
0
0 0 1 1 0 1 0 1
0
1
1
0
1
0
0
0
1 0 1 1 1 1 0 1
1
1
1
0
Алгоритм построения СКНФ по ТИ
1. Отметит те строки, в последнем столбце которых стоит 0. 2.Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание: x y z — для 1-й строки; x y z — для 4-й строки, x y z — для 5-й строки, x y z — для 8-й строки. 3. Все полученные дизъюнкции связать в конъюнкцию: x y z x y z x y z x y z f СКНФ x y z x y z x y z x y z 3. Аналитический способ построения СКНФ 1. Привести формулу с помощью равносильных преобразований к КНФ. 2. Удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся); 3. Из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;
4. Из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного; 5. Если в какой-нибудь дизъюнкции не содержится переменной i x из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член ii xx и применить закон дистрибутивности дизъюнкции относительно конъюнкции; 6. Если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3. Полученная формула и является СКНФ данной формулы. Пример. Построить СКНФ функции f f x y z x y y z z x x y z x y z x y z x y z x y z x y z x y z x y z x y z x y z x y z x y z СКНФ 4. Аналитический способ построения СКНФ из СДНФ Чтобы построить СКНФ для некоторой функции, надо построить отрицание функции f в СДНФ, то есть взять дизъюнкцию элементарных конъюнкций, дающих значение 0 и взять отрицание от f . Пример. Построить СКНФ функции. x y z ( , , ) f x y z 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 f f СКНФ СДНФ x y z xyz x y z xyz x y z x y z x y z x y z
5.
Функциональная полнота системы булевых функций
Система функций 1 ,..., n ff называется
полной
(функционально полной), если любая булева функция может быть записана в виде формул через функции этой системы. К наиболее распространенным в практике построения цифровых автоматов, функционально полным системам, следует отнести: , , , , , , ,1 , | , , 2 | где конъюнкция дизъюнкция отрицание сумма по модулю штрих Шеффера стрелка Пирса
Упражнения
1. Постойте таблицы истинности следующих функций: 1) f (x,y,z,) = (x y z) (y z) x y z 2) z y x z y y x z y x f | ) 1 ( ) , , , ( 3) f (x,y,z) = (x y) ((x y) ( x ~ y z)) 4) z z y y x z y x f 1 ) , , ( 5) y z z y x z y x f ) , , ( 6) z x y y y x z y x z y x f | ) , , ( 2. Опираясь на законы, проверьте справедливость следующих соотношений: 1) y x y x z y x ; 2) y x y x y x y x y x ~ ; 3) z x y x z y x ~ ~ ; 4) z x y x z y x ~ ~ ; 5) z x y x z y x ; 6) x z x y x z y x ~ ~ ~ ; 7) z x y x z y x ~ ~ .
3. Для следующих функций постройте СДНФ и СКНФ: 1) f = x y z; 6) y z x z y x f ; 2) f = (x y) z; 7) ) ~ ( ) | ( yz x y x y x f ; 3) f = x x y y z; 8) f = x ~ ((x y) z); 4) z y x z y x f ; 9) f = (x y) (z x). 5) f = (x y) (x | y z); 4. Постройте из заданной д.н.ф. функции её СДНФ. 1) f = x y z; 3) f = x y z y z. 2) f = x y y z x z; 5. Постройте из заданной к.н.ф. функции её СКНФ. 1) z y x f ; 3) z y z x y x f . 2) z z x y x f ;
Контрольные вопросы
1. Выберите правильный вариант ответа 1 – 4 для следующих вопросов: а) Сколько существует различных булевых функций n переменных? б) Сколько существует различных наборов переменных для булевой функции n переменных? Варианты ответа: 1) 2 n ; 2) 2 2 n ; 3) n 2 ; 4) n!. 2. Какое из следующих утверждений верно: а) Переменные булевой функции и сама булева функция принимают значения 0 или 1; б) Переменные булевой функции принимают значения 0 или 1, а значения самой булевой функции совпадают с множеством действительных чисел; в) Значения переменных булевой функции совпадают с множеством действительных чисел, а сама булева функция принимает значения 0 или 1; г) Значения переменных булевой функции и значения самой функции совпадают с множеством действительных чисел; 3. Выберите правильный вариант ответа 1 – 4 для следующих вопросов: а) Сколько может быть различных ДНФ у булевой функции? б) Сколько может быть различных СДНФ у булевой функции? в) Сколько может быть различных КНФ у булевой функции? г) Сколько может быть различных СКНФ у булевой функции? Варианты ответа: 1 – ноль или одна; 2 – ноль или бесконечно много; 3 – ноль или одна; 4 – одна; 5 – одна или бесконечно много. 4. В какой из нормальных форм (ДНФ, СДНФ, КНФ, СКНФ) находится данная формула булевой функции трех переменных ):
а) ; б) z; в) ̅ ; г) ; д) ̅ ̅ ; е) ̅ ; ж) xz. 5. Какая релейно-контактная схема соответствует функции проводимости ̅ ?
Литература
1. Кузнецов А.А. Информатика. Тестовые задания. / А.А. Кузнецов, В.И. Пугач, Т.В. Добудько, Н.В. Матвеева. – М.: БИНОМ. Лаборатория знаний, 2003. – 232 с. 2. Андреева Е.В., Фалина И.Н. Системы счисления и компьютерная арифметика. – М.: ЛБЗ, 2009. – 248 с. 3. Белоусова Л.И. Сборник задач по курсу информатики / под ред. Л.И. Белоусовой. – М.: Издательство «Экзамен», 2006. – 253 с. 4. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 1986. —384 с. 5. Нефедов В.Н., Осипова В.А. Курс дискретной математики — М.: Издательство МАИ, 1992. —264с. 6. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1984. —319с. 7. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. — М.: Наука, 1992. —408с.
В раздел среднее профессиональное образование