ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 28
Скачиваний: 4
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МАШИННАЯ АРИФМЕТИКА И
ЦИФРОВАЯ ЛОГИКА
Учебно-методический комплекс
(направление подготовки
09.03.04 Программная инженерия)
А. Н. Мадонов
7 сентября 2022 г
ЦИФРОВАЯ ЛОГИКА
Учебно-методический комплекс
(направление подготовки
09.03.04 Программная инженерия)
А. Н. Мадонов
7 сентября 2022 г
Оглавление Лекционный курс 1 Системы счисления 1.1 Общее представление о системах счисления . . . . . . . . . .
7 1.2 Римская система счисления . . . . . . . . . . . . . . . . . . .
10 1.3 Позиционные системы счисления . . . . . . . . . . . . . . . .
13 1.3.1 Перевод целых чисел из одной системы счисления в другую . . . . . . . . . . . . . . . . . . . . . . . . . . Перевод целых чисел через промежуточную унарную систему счисления . . . . . . . . . . . . . . Перевод целых чисел через промежуточную десятичную систему счисления . . . . . . . . . . . .
15 2 Представление числовой информации 2.1 Формат с фиксированной запятой . . . . . . . . . . . . . . .
23 3 Основы алгебры логики 3.1 Понятие функции алгебры логики . . . . . . . . . . . . . . .
25 3.2 Элементарные функции алгебры логики . . . . . . . . . . . .
28 3.3 Аналитическое представление булевых функций . . . . . . .
28 4 Основы цифровой схемотехники 4.1 Синтез и анализ комбинационных схем . . . . . . . . . . . .
29
II Контрольные работы 1 Системы счисления 1.1 Перевод десятичных чисел в римскую систему счисления . .
35 1.2 Перевод чисел из римской системы счисления . . . . . . . Предметный указатель
7 1.2 Римская система счисления . . . . . . . . . . . . . . . . . . .
10 1.3 Позиционные системы счисления . . . . . . . . . . . . . . . .
13 1.3.1 Перевод целых чисел из одной системы счисления в другую . . . . . . . . . . . . . . . . . . . . . . . . . . Перевод целых чисел через промежуточную унарную систему счисления . . . . . . . . . . . . . . Перевод целых чисел через промежуточную десятичную систему счисления . . . . . . . . . . . .
15 2 Представление числовой информации 2.1 Формат с фиксированной запятой . . . . . . . . . . . . . . .
23 3 Основы алгебры логики 3.1 Понятие функции алгебры логики . . . . . . . . . . . . . . .
25 3.2 Элементарные функции алгебры логики . . . . . . . . . . . .
28 3.3 Аналитическое представление булевых функций . . . . . . .
28 4 Основы цифровой схемотехники 4.1 Синтез и анализ комбинационных схем . . . . . . . . . . . .
29
II Контрольные работы 1 Системы счисления 1.1 Перевод десятичных чисел в римскую систему счисления . .
35 1.2 Перевод чисел из римской системы счисления . . . . . . . Предметный указатель
ОГЛАВЛЕНИЕ
Часть ЛЕКЦИОННЫЙ КУРС
Раздел Системы счисления Общее представление о системах счисления
Любое число имеет значение (содержание) и обозначение (форму представления. Значение числа задајт его отношение к значениям других чисел, в результате чего их можно сравнивать. Иными словами, значения чисел задают последовательность их расположения на числовой оси. Форма представления определяет правило записи числа с помощью предназначенных для этого знаков. При этом значение числа является инвариантом,
т. е. оно не зависит от формы представления. Это означает, что число с одними тем же значением может быть записано по-разному, те. отсутствует взаимно однозначное соответствие между формой представления числа и его значением.
В связи с этим возникают вопросы о формах представления чисел,
а также о возможности и способах перехода от одной формы представления к другой. Форма представления числа определяется системой счисления.
О пределен и е 1.1 Системой счисления называется правило записи чисел с помощью заданного набора специальных знаков,
называемых цифрами. Количество различных цифр, с помощью которых выполняется запись чисел в заданной системе счисления, называется еј
основанием, асами цифры образуют алфавит системы счисления.
В разное время люди использовали в процессе своей деятельности различные системы счисления, которые можно разделить натри группы унарную, непозиционные и позиционные системы.
В унарной системе счисления для записи чисел используется всего одна цифра | (вертикальная черта. Следующее число образуется из предыдущего добавлением ещј одной черты. Таким образом, количество чјрточек и будет определять значение числа. Унарная система счисления очень важна в теоретическом отношении, поскольку число в этой системе
Любое число имеет значение (содержание) и обозначение (форму представления. Значение числа задајт его отношение к значениям других чисел, в результате чего их можно сравнивать. Иными словами, значения чисел задают последовательность их расположения на числовой оси. Форма представления определяет правило записи числа с помощью предназначенных для этого знаков. При этом значение числа является инвариантом,
т. е. оно не зависит от формы представления. Это означает, что число с одними тем же значением может быть записано по-разному, те. отсутствует взаимно однозначное соответствие между формой представления числа и его значением.
В связи с этим возникают вопросы о формах представления чисел,
а также о возможности и способах перехода от одной формы представления к другой. Форма представления числа определяется системой счисления.
О пределен и е 1.1 Системой счисления называется правило записи чисел с помощью заданного набора специальных знаков,
называемых цифрами. Количество различных цифр, с помощью которых выполняется запись чисел в заданной системе счисления, называется еј
основанием, асами цифры образуют алфавит системы счисления.
В разное время люди использовали в процессе своей деятельности различные системы счисления, которые можно разделить натри группы унарную, непозиционные и позиционные системы.
В унарной системе счисления для записи чисел используется всего одна цифра | (вертикальная черта. Следующее число образуется из предыдущего добавлением ещј одной черты. Таким образом, количество чјрточек и будет определять значение числа. Унарная система счисления очень важна в теоретическом отношении, поскольку число в этой системе
РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
представляется наиболее простым способом и все операции над числами выполняются тоже просто. Кроме того, именно унарная система определяет значение целого числа количеством содержащихся в нм единиц,
которое, как уже было сказано, не зависит от формы представления.
В непозиционных системах счисления значение любого числа зависит лишь от значений составляющих его цифр и не зависит от месторасположения (позиций) этих цифр в числе. По этой причине унарную систему счисления при желании можно отнести к непозиционным системам. Наиболее известным примером непозиционной системы счисления является римская система, которая рассматривается в разд. В настоящее время используются, в основном, позиционные системы счисления, в которых значение числа определяется не только значениями каждой его цифры, но и позициями, которые эти цифры занимают в числе.
Наиболее распространјнной и привычной является десятичная система счисления, в которой для записи чисел используются десять арабских цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Причиной широкого распространения именно десятичной системы счисления стало е происхождение от унарной системы, в которой в качестве чјрточек использовались пальцы рук. Однако в истории человечества имеются свидетельства использования и других систем счисления пятеричной, шестеричной, двенадцатеричной, двадцатеричной и даже шестидесятеричной.
Любое число в десятичной системе счисления может быть представлено в виде многочлена, в который входят степени основания системы счисления. Для разложения десятичного числа по степеням основания нужно предварительно пронумеровать разряды этого числа, как показано наследующем примере.
П р им ер Разложим число 575, 15 по степеням основания 10:
2 1 0
-1-2 575, 15 10 5 10 2
7 10 1
5 10 0
1 10
1
5 В данном числе цифра 5 встречается трижды, однако е значения во всех трјх случаях различны (500, 5 и 0,05 соответственно) и определяются позициями, которые занимает цифра 5 в числе Главной особенностью позиционных систем счисления является то,
что в них с помощью конечного набора знаков (цифр, разделителя целой и дробной частей, а также символа, обозначающего знак числа) можно записать неограниченное количество различных чисел. Кроме того, в позиционных системах счисления гораздо легче, чем в непозиционных, выполняются операции умножения и деления. Именно эти обстоятельства и
1.1. ОБЩЕЕ ПРЕДСТАВЛЕНИЕ О СИСТЕМАХ СЧИСЛЕНИЯ
9
определили доминирование позиционных систем счисления при обработке числовой информации как человеком, таки компьютером.
В соответствии с принципом, заложенным в основу десятичной системы, можно построить позиционные системы счисления и с другими основаниями.
Обозначим через p основание системы счисления. Тогда любое целое число Z
p
, удовлетворяющее условию Z
p
$ p k
, где k целое положительное число, может быть представлено в виде следующего многочлена a
k
1
p k
1
a k
2
p k
2
. . . a
1
p
1
a
0
p
0
k
1
=
j 0
a j
p Формулу (1.1) можно записать в сокращјнном виде, указав лишь последовательность коэффициентов a j
:
Z
p a
k
1
a k
2
. . . a
1
a
0
Здесь индекс p числа Z
p указывает на то, что оно записано в системе счисления с основанием p. Общее количество k цифр в числе Z
p указывает на то, что наибольшая степень основания p в разложении (1.1) равна Наконец, все коэффициенты a являются целыми числами, удовлетворяющими условию 0 ( a j
( p Естественным образом возникает вопрос о том, каково наименьшее значение основания p. Очевидно, что значение p 1 невозможно, поскольку в этом случае все коэффициенты a должны быть равны нулю, и выражение) теряет всякий смысл. Поэтому наименьшим для позиционных систем счисления основанием является значение p Система счисления с основанием p 2 называется двоичной. Запись всех чисел в двоичной системе счисления выполняется с помощью цифр и 1, а многочлен в формуле (1.1) строится по степеням числа Интерес именно к двоичной системе счисления вызван тем, что любая информация в компьютере представляется с помощью двух противоположных состояний, которые легко реализуются технически. Наряду с двоичной системой, которая является основной, в компьютерах также используются восьмеричная, десятичная и шестнадцатеричная системы счисления,
а также смешанная двоично-десятичная система
1.2. РИМСКАЯ СИСТЕМА СЧИСЛЕНИЯ 2. Заменить базовые числа 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, и 1 эквивалентными римскими цифрами или комбинациями римских цифр.
П р им ер Записать десятичное число 1648 в римской системе счисле- ния.
Р е ш е ни е Представим число 1648 в виде суммы базовых чисел 1000
500 100 40 5 1 Заменим каждое слагаемое в сумме эквивалентной римской цифрой или комбинацией цифр 500 100 40 5 1 3 M D C XL V III Ответ Очевидно, что приведјнные выше правила записи чисел в римской системе счисления ограничивают диапазон представления чисел. Наибольшим десятичным числом, которое можно записать в римской системе счисления, является число 3999 10
:
3999 10 3 1000
900 90 9 Для записи в римской системе счисления значений, больших 3999 используют следующее правило над разрядами тысяч, десятков тысячи сотен тысяч ставят черту, а над разрядами миллионов, десятков миллионов и сотен миллионов две черты.
П р им ер Записать в римской системе счисления число 615 880 547 Решение 6
500 100 3 50 10 3 10 3
500 40 5 1 2
DCXV DCCCLXXX Ответ Для перевода числа из римской системы счисления в десятичную нужно выполнить следующие действия. Разбить римское число на неделимые составляющие I, IV, V, IX, X, XL,
L, XC, C, CD, D, CM и M. При этом комбинации из двух римских цифр имеют приоритет перед одиночными цифрами. Например, число Правильность перевода десятичного числа в римскую систему счисления всегда можно проверить,
воспользовавшись программой Microsoft Office Excel. В этой программе перевод из десятичной системы счисления в римскую выполняется с помощью функции РИМСКОЕ, единственным аргументом которой является исходное десятичное число
представляется наиболее простым способом и все операции над числами выполняются тоже просто. Кроме того, именно унарная система определяет значение целого числа количеством содержащихся в нм единиц,
которое, как уже было сказано, не зависит от формы представления.
В непозиционных системах счисления значение любого числа зависит лишь от значений составляющих его цифр и не зависит от месторасположения (позиций) этих цифр в числе. По этой причине унарную систему счисления при желании можно отнести к непозиционным системам. Наиболее известным примером непозиционной системы счисления является римская система, которая рассматривается в разд. В настоящее время используются, в основном, позиционные системы счисления, в которых значение числа определяется не только значениями каждой его цифры, но и позициями, которые эти цифры занимают в числе.
Наиболее распространјнной и привычной является десятичная система счисления, в которой для записи чисел используются десять арабских цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Причиной широкого распространения именно десятичной системы счисления стало е происхождение от унарной системы, в которой в качестве чјрточек использовались пальцы рук. Однако в истории человечества имеются свидетельства использования и других систем счисления пятеричной, шестеричной, двенадцатеричной, двадцатеричной и даже шестидесятеричной.
Любое число в десятичной системе счисления может быть представлено в виде многочлена, в который входят степени основания системы счисления. Для разложения десятичного числа по степеням основания нужно предварительно пронумеровать разряды этого числа, как показано наследующем примере.
П р им ер Разложим число 575, 15 по степеням основания 10:
2 1 0
-1-2 575, 15 10 5 10 2
7 10 1
5 10 0
1 10
1
5 В данном числе цифра 5 встречается трижды, однако е значения во всех трјх случаях различны (500, 5 и 0,05 соответственно) и определяются позициями, которые занимает цифра 5 в числе Главной особенностью позиционных систем счисления является то,
что в них с помощью конечного набора знаков (цифр, разделителя целой и дробной частей, а также символа, обозначающего знак числа) можно записать неограниченное количество различных чисел. Кроме того, в позиционных системах счисления гораздо легче, чем в непозиционных, выполняются операции умножения и деления. Именно эти обстоятельства и
1.1. ОБЩЕЕ ПРЕДСТАВЛЕНИЕ О СИСТЕМАХ СЧИСЛЕНИЯ
9
определили доминирование позиционных систем счисления при обработке числовой информации как человеком, таки компьютером.
В соответствии с принципом, заложенным в основу десятичной системы, можно построить позиционные системы счисления и с другими основаниями.
Обозначим через p основание системы счисления. Тогда любое целое число Z
p
, удовлетворяющее условию Z
p
$ p k
, где k целое положительное число, может быть представлено в виде следующего многочлена a
k
1
p k
1
a k
2
p k
2
. . . a
1
p
1
a
0
p
0
k
1
=
j 0
a j
p Формулу (1.1) можно записать в сокращјнном виде, указав лишь последовательность коэффициентов a j
:
Z
p a
k
1
a k
2
. . . a
1
a
0
Здесь индекс p числа Z
p указывает на то, что оно записано в системе счисления с основанием p. Общее количество k цифр в числе Z
p указывает на то, что наибольшая степень основания p в разложении (1.1) равна Наконец, все коэффициенты a являются целыми числами, удовлетворяющими условию 0 ( a j
( p Естественным образом возникает вопрос о том, каково наименьшее значение основания p. Очевидно, что значение p 1 невозможно, поскольку в этом случае все коэффициенты a должны быть равны нулю, и выражение) теряет всякий смысл. Поэтому наименьшим для позиционных систем счисления основанием является значение p Система счисления с основанием p 2 называется двоичной. Запись всех чисел в двоичной системе счисления выполняется с помощью цифр и 1, а многочлен в формуле (1.1) строится по степеням числа Интерес именно к двоичной системе счисления вызван тем, что любая информация в компьютере представляется с помощью двух противоположных состояний, которые легко реализуются технически. Наряду с двоичной системой, которая является основной, в компьютерах также используются восьмеричная, десятичная и шестнадцатеричная системы счисления,
а также смешанная двоично-десятичная система
РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ Римская система счисления
Наиболее известным примером непозиционной системы счисления является римская система, которая использовалась древними римлянами для записи натуральных чисел.
Алфавит римской системы счисления составляют семь римских цифр, которые обозначаются прописными буквами латинского алфавита. Таким образом,
десятичные числа 1, 5, 10, 50, 100, 500 и 1000 можно считать базовыми для представления в римской системе счисления.
Все остальные числа записываются в виде комбинациий базовых в соответствии со следующими правилами меньшая цифра должна находиться справа от большей цифры I, X, C и M могут использоваться при записи числа по нескольку разно подряд могут следовать не более трјх одинаковых цифр цифры V, L и D могут встречаться в записи числа не более одного раза каждая в виде исключения меньшая цифра может предшествовать большей,
но лишь в комбинациях IV, IX, XL, XC, CD и CM;
€ если меньшая цифра находится справа от большей, то их значения складываются если же слева то из значения большей цифры вычитается значение меньшей из этого следует, что комбинации IV, IX,
XL, XC, CD и CM римских цифр эквивалентны десятичным числами соответственно эти числа также будут являться базовыми, наряду с числами 1, 5, 10, 50, 100, 500 и Для записи целого десятичного числа в римской системе счисления нужно выполнить следующие действия. Представить число в виде суммы базовых чисел. При этом большее число имеет более высокий приоритет, те. недопустимо использовать в качестве слагаемого меньшее число, минуя большее. Например, число следует представить в виде суммы 900 50 10 10 а не в виде 500 400 40 10 10 5 5 1. В последнем случае будут нарушаться правила записи чисел в римской системе счисления. В частности, по два раза будут использоваться цифры D и Как обычно, сложение одинаковых чисел можно заменить умножением. Тогда, например, разложение числа 971 можно представить в виде 971 10 900
50 10 2 1.
Наиболее известным примером непозиционной системы счисления является римская система, которая использовалась древними римлянами для записи натуральных чисел.
Алфавит римской системы счисления составляют семь римских цифр, которые обозначаются прописными буквами латинского алфавита. Таким образом,
десятичные числа 1, 5, 10, 50, 100, 500 и 1000 можно считать базовыми для представления в римской системе счисления.
Все остальные числа записываются в виде комбинациий базовых в соответствии со следующими правилами меньшая цифра должна находиться справа от большей цифры I, X, C и M могут использоваться при записи числа по нескольку разно подряд могут следовать не более трјх одинаковых цифр цифры V, L и D могут встречаться в записи числа не более одного раза каждая в виде исключения меньшая цифра может предшествовать большей,
но лишь в комбинациях IV, IX, XL, XC, CD и CM;
€ если меньшая цифра находится справа от большей, то их значения складываются если же слева то из значения большей цифры вычитается значение меньшей из этого следует, что комбинации IV, IX,
XL, XC, CD и CM римских цифр эквивалентны десятичным числами соответственно эти числа также будут являться базовыми, наряду с числами 1, 5, 10, 50, 100, 500 и Для записи целого десятичного числа в римской системе счисления нужно выполнить следующие действия. Представить число в виде суммы базовых чисел. При этом большее число имеет более высокий приоритет, те. недопустимо использовать в качестве слагаемого меньшее число, минуя большее. Например, число следует представить в виде суммы 900 50 10 10 а не в виде 500 400 40 10 10 5 5 1. В последнем случае будут нарушаться правила записи чисел в римской системе счисления. В частности, по два раза будут использоваться цифры D и Как обычно, сложение одинаковых чисел можно заменить умножением. Тогда, например, разложение числа 971 можно представить в виде 971 10 900
50 10 2 1.
1.2. РИМСКАЯ СИСТЕМА СЧИСЛЕНИЯ 2. Заменить базовые числа 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, и 1 эквивалентными римскими цифрами или комбинациями римских цифр.
П р им ер Записать десятичное число 1648 в римской системе счисле- ния.
Р е ш е ни е Представим число 1648 в виде суммы базовых чисел 1000
500 100 40 5 1 Заменим каждое слагаемое в сумме эквивалентной римской цифрой или комбинацией цифр 500 100 40 5 1 3 M D C XL V III Ответ Очевидно, что приведјнные выше правила записи чисел в римской системе счисления ограничивают диапазон представления чисел. Наибольшим десятичным числом, которое можно записать в римской системе счисления, является число 3999 10
:
3999 10 3 1000
900 90 9 Для записи в римской системе счисления значений, больших 3999 используют следующее правило над разрядами тысяч, десятков тысячи сотен тысяч ставят черту, а над разрядами миллионов, десятков миллионов и сотен миллионов две черты.
П р им ер Записать в римской системе счисления число 615 880 547 Решение 6
500 100 3 50 10 3 10 3
500 40 5 1 2
DCXV DCCCLXXX Ответ Для перевода числа из римской системы счисления в десятичную нужно выполнить следующие действия. Разбить римское число на неделимые составляющие I, IV, V, IX, X, XL,
L, XC, C, CD, D, CM и M. При этом комбинации из двух римских цифр имеют приоритет перед одиночными цифрами. Например, число Правильность перевода десятичного числа в римскую систему счисления всегда можно проверить,
воспользовавшись программой Microsoft Office Excel. В этой программе перевод из десятичной системы счисления в римскую выполняется с помощью функции РИМСКОЕ, единственным аргументом которой является исходное десятичное число
РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
следует представлять в виде D XL V I I, а не в виде D X L V I Одинаковые римские цифры, которые расположены в числе непосредственно одна за другой, можно объединять в одну группу. Например,
приведјнное выше число можно представить в виде D XL V II.
2. Заменить каждую римскую цифру или группу цифр эквивалентным десятичным числом. Выполнить сложение полученных чисел. Вычисленная сумма и будет являться эквивалентным представлением римского числа в десятичной системе счисления.
П р им ер Записать римское число MMCXIX в десятичной системе счисле- ния.
Р е ш е ни е Выполним разбиение исходного римского числа C X Заменим каждую группу римских цифр эквивалентным десятичным числом и выполним сложение полученных чисел C X IX
1000 2
100 10 9 2119 Ответ Пример Записать римское число DCCCXXI CDXLVIII CMXLII в десятичной системе счисления.
Р е ш е ни е Проведјм его по аналогии с примером 1.4, выполняя процедуру разбиения по отдельности для миллионов, тысячи единиц римского числа CDXLVIII CMXLII
D CCC XX I CD XL V III CM XL II
500
100 3 10 2 1 10 6
400 40 5 1 3 10 3
900 40 1 2
821 10 6
448 10 3
942 821 448 942 Ответ Запись чисел в римской системе счисления оказывается громоздкой и неудобной, но ещј более неудобным является выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел, больших 1000, не позволяет записать с помощью римских цифр любое целое положительное число. По указанным причинам в настоящее время римская система счисления используется лишь при нумерации каких-либо объектов. Такими же недостатками обладают и все другие непозиционные системы счисления, которые в настоящее время и вовсе не находят практического применения
1.3. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ 1.3 Позиционные системы счисления
Очевидно, что значение целого числа, те. общее количество входящих в него единиц, не зависит от способа представления числа и остајтся одинаковым во всех системах счисления. Различаются только формы представления одного итого же количественного содержания числа, например 101 2
12 3
5 10 Поскольку одно и тоже число может быть записано в различных системах счисления, возникает вопрос о переводе чисел из одной системы счисления в другую Перевод целых чисел из одной системы счисления в другую Обозначим преобразование числа Z, представленного в системе счисления с основанием p, в систему счисления с основанием q в виде формулы. Теоретически это преобразование можно выполнить при любых основаниях p и q. Однако подобное непосредственное преобразование будет затруднено тем, что придјтся выполнять арифметические операции по правилам недесятичных систем счисления, поскольку в общем случае p
j 10 и q j По этой причине более удобными с практической точки зрения оказываются варианты преобразования Z
p
Z
r
Z
q через промежуточную систему счисления с основанием r, для которого арифметические операции будут выполняться легко. Такими удобными основаниями являются значения r 1 и r 10, те. перевод удобно осуществлять через промежуточную унарную или десятичную систему счисления.
Перевод целых чисел через промежуточную унарную систему счисления
Алгоритм перевода Z
p
Z
1
Z
q через промежуточную унарную систему счисления имеет следующий вид. Положим начальное значение Z
q
0 2. Из числа Z
p вычтем единицу по правилам вычитания в системе счисления с основанием p, те. К числу Z
q прибавим единицу по правилам сложения в системе счисления с основанием q, те РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
Будем повторять шаги 2, 3 алгоритма до тех пор, пока значение Z
p не станет равным нулю.
Правила сложения с единицей (инкремента) и вычитания единицы (декремента) могут быть записаны так, как представлено в табл. Таблица 1.1: Правила инкремента и декремента
Для Для Z
q p
1 1 p 2 0
1 1
p
2 1 p 3 1
1 2 1
1 0
q
2 1 q 1 0
1 ? p 1
q
1 1 Примечание. Здесь символ ? означает перенос единицы в следующий разряд в случае инкремента или заимствование из следующего разряда в случае декремента.
П р им ер Выполнить перевод числа 10000 в пятеричную систему счисления через промежуточную унарную систему.
Р е ш е ни е Обозначим исходное двоичное число через Z
2
, а искомое пятеричное число через Присвоим искомому пятеричному числу начальное значение, равное нулю,
т. е. Z
5 0
. Затем на каждой итерации будем уменьшать значение двоичного числа на единицу, одновременно увеличивая на единицу значение пятеричного числа Z
5
. Итерационный процесс будем продолжать до тех пор, пока значение не станет равным нулю 10000 2
1 1111 2
,
Z
5 0
5
1 1 5
,
Z
2 1111 2
1 1110 2
,
Z
5 1
5
1 2 5
,
Z
2 1110 2
1 1101 2
,
Z
5 2
5
1 3 5
,
Z
2 1101 2
1 1100 2
,
Z
5 3
5
1 4 5
,
Z
2 1100 2
1 1011 2
,
Z
5 4
5
1 10 5
,
Z
2 1011 2
1 1010 2
,
Z
5 10 5
1 11 5
,
Z
2 1010 2
1 1001 2
,
Z
5 11 5
1 12 5
,
Z
2 1001 2
1 1000 2
,
Z
5 12 5
1 13 5
,
Z
2 1000 2
1 111 2
,
Z
5 13 5
1 14 5
,
Z
2 111 2
1 110 2
,
Z
5 14 5
1 20 5
,
Z
2 110 2
1 101 2
,
Z
5 20 5
1 21 5
,
Z
2 101 2
1 100 2
,
Z
5 21 5
1 22 5
,
Z
2 100 2
1 11 2
,
Z
5 22 5
1 23 5
,
Z
2 11 2
1 10 2
,
Z
5 23 5
1 24 5
,
Z
2 10 2
1 1 2
,
Z
5 24 5
1 30 5
,
Z
2 1
2
1 0 2
,
Z
5 30 5
1 31 Таким образом, 10000 2
31 Ответ. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
15
Переход к промежуточной унарной системе счисления в данном случае осуществляется неявно используется упоминавшееся ранее свойство независимости числа от формы его представления.
Перевод целых чисел через промежуточную десятичную систему счисления
Очевидно, что первая и вторая части преобразования Z
p
Z
10
Z
q никак не связаны одна с другой. Поэтому есть основание рассматривать их по отдельности.
Алгоритм преобразования Z
10
Z
q вытекает из следующих соображений. Рассмотрим многочлен (1.1) для числа Z
q
:
Z
q m
1
=
j 0
b j
q j
b m
1
q m
1
b m
2
q m
2
. . . b
3
q
3
b
2
q
2
b
1
q
где m количество разрядов в записи числа Z
q
;
b j
значения разрядов (цифры) числа Z
q
, j 0, 1, . . . , m Выполним в равенстве 1.2 следующие преобразования m
1
q m
2
b m
2
q m
3
b m
3
q m
4
. . . b
3
q
2
b
2
q
b
1
q b
0
b m
1
q m
3
b m
2
q m
4
b m
3
q m
5
. . . b
3
q
b
2
q b
1
q b
0
b m
1
q m
4
b m
2
q m
5
b m
3
q m
6
. . . b
3
q b
2
q b
1
q b
0
. . . b m
1
q
b m
2
q b m
3
q . . . b
1
q b
0
Разобьјм разряды числа Z
q на две части по разряду с номером i, который может принимать любые значения от 0 до m 1. Часть числа,
содержащую m i разрядов с го пой, обозначим через Другую часть, содержащую i разрядов с нулевого пой через ?
i
:
Z
q b
m
1
b m
2
. . . b i
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i b
i
1
. . . b
1
b
0
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i
(1.3)
или
Z
q
?
i
МТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТРТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТО
. . . b m
1
q
b m
2
q . . . b i
1
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i
1
q
b i
q . . . b
1
q b
0
(1.4)
1.3. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
19
а с учјтом того, что m 1 целое число, получаем m
1 log q
Z
10
Второй способ перевода чисел из десятичной системы счисления реализуется в соответствии со следующим алгоритмом. Определить значение m 1 по формуле (1.8).
2. Разделить исходное число на число q и определить частное и остаток отделения. Частное отделения будет являться старшей цифрой числа Z
q
3. Остаток отделения, вычисленный на втором шаге, разделить на число и снова определить частное и остаток отделения. Частное отделения будет являться второй цифрой числа Z
q
4. Процесс деления продолжать до тех пор, пока показатель степени числа не станет равным нулю. Вычисленные частные отделения и остаток отделения, который был получен на последней итерации алгоритма, записанные в порядке их вычисления, и образуют число Пример Решим задачу из примера 1.7, используя второй способ.
Р е ш е ни е Сначала определим число m 1 по формуле (1.8):
m
1 log
6 5025
Вычисление логарифма, находящегося в правой части равенства, представляет сложность даже при наличии электронных вычислительных средств, поскольку возможность вычисления логарифма по основанию 6 вряд ли реализована хотя бы водном калькуляторе.
Но практически в любом калькуляторе реализована возможность вычисления натурального и десятичного логарифмов. Поэтому перейдјт от логарифма по основанию к любому из них (например, к десятичному логарифму 1 log
6 5025
lg 5025
lg 6
Теперь оба логарифма мы можем вычислить, но лишь приближјнно. Применительно к нашим данным мы получаем следующие результаты вычисления на калькуляторе. Выполним оценки сверху и снизу для вычисленных значений, 701
( lg 5025 ( 3, 702;
0, 778
( lg 6 ( 0, Тогда, 7
(
3, 701 0, 779 (
log
10 5025
log
10 6
(
3, 702 0, 778 (
4, 8
следует представлять в виде D XL V I I, а не в виде D X L V I Одинаковые римские цифры, которые расположены в числе непосредственно одна за другой, можно объединять в одну группу. Например,
приведјнное выше число можно представить в виде D XL V II.
2. Заменить каждую римскую цифру или группу цифр эквивалентным десятичным числом. Выполнить сложение полученных чисел. Вычисленная сумма и будет являться эквивалентным представлением римского числа в десятичной системе счисления.
П р им ер Записать римское число MMCXIX в десятичной системе счисле- ния.
Р е ш е ни е Выполним разбиение исходного римского числа C X Заменим каждую группу римских цифр эквивалентным десятичным числом и выполним сложение полученных чисел C X IX
1000 2
100 10 9 2119 Ответ Пример Записать римское число DCCCXXI CDXLVIII CMXLII в десятичной системе счисления.
Р е ш е ни е Проведјм его по аналогии с примером 1.4, выполняя процедуру разбиения по отдельности для миллионов, тысячи единиц римского числа CDXLVIII CMXLII
D CCC XX I CD XL V III CM XL II
500
100 3 10 2 1 10 6
400 40 5 1 3 10 3
900 40 1 2
821 10 6
448 10 3
942 821 448 942 Ответ Запись чисел в римской системе счисления оказывается громоздкой и неудобной, но ещј более неудобным является выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел, больших 1000, не позволяет записать с помощью римских цифр любое целое положительное число. По указанным причинам в настоящее время римская система счисления используется лишь при нумерации каких-либо объектов. Такими же недостатками обладают и все другие непозиционные системы счисления, которые в настоящее время и вовсе не находят практического применения
1.3. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ 1.3 Позиционные системы счисления
Очевидно, что значение целого числа, те. общее количество входящих в него единиц, не зависит от способа представления числа и остајтся одинаковым во всех системах счисления. Различаются только формы представления одного итого же количественного содержания числа, например 101 2
12 3
5 10 Поскольку одно и тоже число может быть записано в различных системах счисления, возникает вопрос о переводе чисел из одной системы счисления в другую Перевод целых чисел из одной системы счисления в другую Обозначим преобразование числа Z, представленного в системе счисления с основанием p, в систему счисления с основанием q в виде формулы. Теоретически это преобразование можно выполнить при любых основаниях p и q. Однако подобное непосредственное преобразование будет затруднено тем, что придјтся выполнять арифметические операции по правилам недесятичных систем счисления, поскольку в общем случае p
j 10 и q j По этой причине более удобными с практической точки зрения оказываются варианты преобразования Z
p
Z
r
Z
q через промежуточную систему счисления с основанием r, для которого арифметические операции будут выполняться легко. Такими удобными основаниями являются значения r 1 и r 10, те. перевод удобно осуществлять через промежуточную унарную или десятичную систему счисления.
Перевод целых чисел через промежуточную унарную систему счисления
Алгоритм перевода Z
p
Z
1
Z
q через промежуточную унарную систему счисления имеет следующий вид. Положим начальное значение Z
q
0 2. Из числа Z
p вычтем единицу по правилам вычитания в системе счисления с основанием p, те. К числу Z
q прибавим единицу по правилам сложения в системе счисления с основанием q, те РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
Будем повторять шаги 2, 3 алгоритма до тех пор, пока значение Z
p не станет равным нулю.
Правила сложения с единицей (инкремента) и вычитания единицы (декремента) могут быть записаны так, как представлено в табл. Таблица 1.1: Правила инкремента и декремента
Для Для Z
q p
1 1 p 2 0
1 1
p
2 1 p 3 1
1 2 1
1 0
q
2 1 q 1 0
1 ? p 1
q
1 1 Примечание. Здесь символ ? означает перенос единицы в следующий разряд в случае инкремента или заимствование из следующего разряда в случае декремента.
П р им ер Выполнить перевод числа 10000 в пятеричную систему счисления через промежуточную унарную систему.
Р е ш е ни е Обозначим исходное двоичное число через Z
2
, а искомое пятеричное число через Присвоим искомому пятеричному числу начальное значение, равное нулю,
т. е. Z
5 0
. Затем на каждой итерации будем уменьшать значение двоичного числа на единицу, одновременно увеличивая на единицу значение пятеричного числа Z
5
. Итерационный процесс будем продолжать до тех пор, пока значение не станет равным нулю 10000 2
1 1111 2
,
Z
5 0
5
1 1 5
,
Z
2 1111 2
1 1110 2
,
Z
5 1
5
1 2 5
,
Z
2 1110 2
1 1101 2
,
Z
5 2
5
1 3 5
,
Z
2 1101 2
1 1100 2
,
Z
5 3
5
1 4 5
,
Z
2 1100 2
1 1011 2
,
Z
5 4
5
1 10 5
,
Z
2 1011 2
1 1010 2
,
Z
5 10 5
1 11 5
,
Z
2 1010 2
1 1001 2
,
Z
5 11 5
1 12 5
,
Z
2 1001 2
1 1000 2
,
Z
5 12 5
1 13 5
,
Z
2 1000 2
1 111 2
,
Z
5 13 5
1 14 5
,
Z
2 111 2
1 110 2
,
Z
5 14 5
1 20 5
,
Z
2 110 2
1 101 2
,
Z
5 20 5
1 21 5
,
Z
2 101 2
1 100 2
,
Z
5 21 5
1 22 5
,
Z
2 100 2
1 11 2
,
Z
5 22 5
1 23 5
,
Z
2 11 2
1 10 2
,
Z
5 23 5
1 24 5
,
Z
2 10 2
1 1 2
,
Z
5 24 5
1 30 5
,
Z
2 1
2
1 0 2
,
Z
5 30 5
1 31 Таким образом, 10000 2
31 Ответ. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
15
Переход к промежуточной унарной системе счисления в данном случае осуществляется неявно используется упоминавшееся ранее свойство независимости числа от формы его представления.
Перевод целых чисел через промежуточную десятичную систему счисления
Очевидно, что первая и вторая части преобразования Z
p
Z
10
Z
q никак не связаны одна с другой. Поэтому есть основание рассматривать их по отдельности.
Алгоритм преобразования Z
10
Z
q вытекает из следующих соображений. Рассмотрим многочлен (1.1) для числа Z
q
:
Z
q m
1
=
j 0
b j
q j
b m
1
q m
1
b m
2
q m
2
. . . b
3
q
3
b
2
q
2
b
1
q
где m количество разрядов в записи числа Z
q
;
b j
значения разрядов (цифры) числа Z
q
, j 0, 1, . . . , m Выполним в равенстве 1.2 следующие преобразования m
1
q m
2
b m
2
q m
3
b m
3
q m
4
. . . b
3
q
2
b
2
q
b
1
q b
0
b m
1
q m
3
b m
2
q m
4
b m
3
q m
5
. . . b
3
q
b
2
q b
1
q b
0
b m
1
q m
4
b m
2
q m
5
b m
3
q m
6
. . . b
3
q b
2
q b
1
q b
0
. . . b m
1
q
b m
2
q b m
3
q . . . b
1
q b
0
Разобьјм разряды числа Z
q на две части по разряду с номером i, который может принимать любые значения от 0 до m 1. Часть числа,
содержащую m i разрядов с го пой, обозначим через Другую часть, содержащую i разрядов с нулевого пой через ?
i
:
Z
q b
m
1
b m
2
. . . b i
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i b
i
1
. . . b
1
b
0
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i
(1.3)
или
Z
q
?
i
МТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТРТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТО
. . . b m
1
q
b m
2
q . . . b i
1
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i
1
q
b i
q . . . b
1
q b
0
(1.4)
РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
Из формулы (1.3) следует, что и ?
m
1
b m
1
, а из формулы) вытекает рекуррентное соотношение ?
i
?
i
1
q
b i
Введјм обозначения div для частного и mod для остатка, которые получаются в результате деления одного целого числа на другое. Например 4 3,
13
mod 4 Тогда будут справедливы следующие соотношения div q,
b i
?
i mod Из соотношений (1.5) непосредственно следует первый способ перевода целых чисел из десятичной системы счисления в систему счисления с произвольным основанием Младшая цифра числа Z
q определяется по второй из формул (1.5):
b
0
?
0
mod q Z
10
mod те. она вычисляется как остаток отделения исходного числа на основание новой системы счисления.
Параллельно с этим по первой из формул (1.5) определяется частное отделения исходного числа на основание q:
?
1
?
0
div q Z
10
div которое будет использоваться наследующей итерации алгоритма.
Следующая цифра числа Z
q также определяется по второй из формул) как остаток отделения частного, полученного на предыдущей итерации, на основание q новой системы счисления q и вместе с ней по первой из формул (1.5) вычисляется частное отделения величины на основание q:
?
2
?
1
div Далее поэтому алгоритму определяются цифры b
2
, b
3
, . . . , b m
2
. Старшая же цифра b равна ?
m
1
, те. она совпадает с последним частным отделения величины на основание Поскольку величина является цифрой числа Z
q
, она должна быть меньше основания q новой системы счисления. Следовательно, получение частного отделения, которое окажется меньше делителя, и будет являться условием прекращения итерационного процесса.
Таким образом, первый способ предполагает следующий алгоритм перевода. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ 1. Разделить исходное число на основание q новой системы счисления и определить остаток отделения, который будет являться цифрой нулевого разряда числа Z
q
2. Частное отделения, полученное на предыдущем шаге, снова разделить на число q с выделением остатка, который будет являться цифрой первого разряда числа Z
q
3. Процесс деления продолжать до тех пор, пока частное отделения не окажется меньше числа q.
4. Вычисленные остатки отделения и частное отделения, которое было получено на последней итерации алгоритма, записанные в порядке,
обратном порядку их вычисления, и образуют число Пример Перевести число 5025 в шестеричную систему счисления.
Р е ш е ни е Процесс перевода будет иметь следующий вид 6
5022 837 6
3 834 139 6
3 138 23 6
1 18 Остатки 3, 3, 1, 5 отделения и частное 3, полученное на последней итерации, образуют обратный порядок цифр числа в шестеричной системе счисления. Следовательно 10 35133 Ответ С другой стороны, из формулы (1.3) следует, что и, а из формулы (1.2) то, что b
m
1
q m
1
b m
2
q m
2
. . .
?
i
1
МТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТРТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТО
b i
q i
b i
1
q i
1
b
1
q
1
b
0
q
0
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i
(1.6)
Из формулы (1.6) вытекает рекуррентное соотношение ?
i
1
?
i
b i
q из которого, в свою очередь, следуют выражения b
i
?
i
1
div q i
,
?
i
?
i
1
mod q Полученное шестеричное число нельзя читать как тридцать пять тысяч сто тридцать триї, поскольку единицы, десятки, сотни, тысячи и другие подобные наименования относятся только к десятичной системе счисления. В данном же случае прочитывать число следует путјм простого перечисления его цифр с указанием системы счисления, те. три, пять, один, три, три в шестеричной системе счисленияї.
Из формулы (1.3) следует, что и ?
m
1
b m
1
, а из формулы) вытекает рекуррентное соотношение ?
i
?
i
1
q
b i
Введјм обозначения div для частного и mod для остатка, которые получаются в результате деления одного целого числа на другое. Например 4 3,
13
mod 4 Тогда будут справедливы следующие соотношения div q,
b i
?
i mod Из соотношений (1.5) непосредственно следует первый способ перевода целых чисел из десятичной системы счисления в систему счисления с произвольным основанием Младшая цифра числа Z
q определяется по второй из формул (1.5):
b
0
?
0
mod q Z
10
mod те. она вычисляется как остаток отделения исходного числа на основание новой системы счисления.
Параллельно с этим по первой из формул (1.5) определяется частное отделения исходного числа на основание q:
?
1
?
0
div q Z
10
div которое будет использоваться наследующей итерации алгоритма.
Следующая цифра числа Z
q также определяется по второй из формул) как остаток отделения частного, полученного на предыдущей итерации, на основание q новой системы счисления q и вместе с ней по первой из формул (1.5) вычисляется частное отделения величины на основание q:
?
2
?
1
div Далее поэтому алгоритму определяются цифры b
2
, b
3
, . . . , b m
2
. Старшая же цифра b равна ?
m
1
, те. она совпадает с последним частным отделения величины на основание Поскольку величина является цифрой числа Z
q
, она должна быть меньше основания q новой системы счисления. Следовательно, получение частного отделения, которое окажется меньше делителя, и будет являться условием прекращения итерационного процесса.
Таким образом, первый способ предполагает следующий алгоритм перевода. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ 1. Разделить исходное число на основание q новой системы счисления и определить остаток отделения, который будет являться цифрой нулевого разряда числа Z
q
2. Частное отделения, полученное на предыдущем шаге, снова разделить на число q с выделением остатка, который будет являться цифрой первого разряда числа Z
q
3. Процесс деления продолжать до тех пор, пока частное отделения не окажется меньше числа q.
4. Вычисленные остатки отделения и частное отделения, которое было получено на последней итерации алгоритма, записанные в порядке,
обратном порядку их вычисления, и образуют число Пример Перевести число 5025 в шестеричную систему счисления.
Р е ш е ни е Процесс перевода будет иметь следующий вид 6
5022 837 6
3 834 139 6
3 138 23 6
1 18 Остатки 3, 3, 1, 5 отделения и частное 3, полученное на последней итерации, образуют обратный порядок цифр числа в шестеричной системе счисления. Следовательно 10 35133 Ответ С другой стороны, из формулы (1.3) следует, что и, а из формулы (1.2) то, что b
m
1
q m
1
b m
2
q m
2
. . .
?
i
1
МТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТРТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТО
b i
q i
b i
1
q i
1
b
1
q
1
b
0
q
0
НТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТСТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТТП
?
i
(1.6)
Из формулы (1.6) вытекает рекуррентное соотношение ?
i
1
?
i
b i
q из которого, в свою очередь, следуют выражения b
i
?
i
1
div q i
,
?
i
?
i
1
mod q Полученное шестеричное число нельзя читать как тридцать пять тысяч сто тридцать триї, поскольку единицы, десятки, сотни, тысячи и другие подобные наименования относятся только к десятичной системе счисления. В данном же случае прочитывать число следует путјм простого перечисления его цифр с указанием системы счисления, те. три, пять, один, три, три в шестеричной системе счисленияї.
РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
Из соотношения (1.7) непосредственно следует второй способ перевода целых чисел из десятичной системы счисления в систему счисления с произвольным основанием Старшая цифра b числа Z
q определяется по первой из формул (1.7):
b m
1
?
m div q m
1
Z
10
div q те. она вычисляется как частное отделения исходного числа на основание новой системы счисления, возведјнное в степень m 1, где m количество цифр в числе Параллельно с этим по второй из формул (1.7) определяется остаток отделения исходного числа на основание q, возведјнное в степень m1:
?
m
1
?
m mod q m
1
Z
10
mod q которое будет использоваться наследующей итерации алгоритма.
Следующая цифра b числа Z
q также определяется по первой из формул (1.7) как частное отделения остатка, полученного на предыдущей итерации, на основание q новой системы счисления, возведјнное в степень m 2:
b m
2
?
m
1
div q и вместе с ней по второй из формул (1.7) вычисляется остаток отделения величины на основание q, возведјнное в степень m 2:
?
m
2
?
m
1
mod q Далее поэтому алгоритму определяются цифры b m
3
, b m
4
, . . . , Младшая же цифра равна ?
1
, те. она совпадает с последним остатком отделения величины на основание В рассмотренном алгоритме остајтся невыясненным один момент. Нам заранее неизвестно количество цифр в числе Z
q
, те. нам неизвестно число, а не зная его, мы не сможем выполнить даже самую первую итерацию алгоритма.
Однако число m 1 можно легко определить из следующих соображений. Из формулы 1.6 следует, что m 1 наибольшая из степеней основания q, которая не превосходит значение Z
q
, а последнее, в свою очередь, совпадает со значением Z
10
. Иными словами m
1
( и q
m
% Из последних двух неравенств следует, что m
1 ( log и m
% log q
Z
10
,
Из соотношения (1.7) непосредственно следует второй способ перевода целых чисел из десятичной системы счисления в систему счисления с произвольным основанием Старшая цифра b числа Z
q определяется по первой из формул (1.7):
b m
1
?
m div q m
1
Z
10
div q те. она вычисляется как частное отделения исходного числа на основание новой системы счисления, возведјнное в степень m 1, где m количество цифр в числе Параллельно с этим по второй из формул (1.7) определяется остаток отделения исходного числа на основание q, возведјнное в степень m1:
?
m
1
?
m mod q m
1
Z
10
mod q которое будет использоваться наследующей итерации алгоритма.
Следующая цифра b числа Z
q также определяется по первой из формул (1.7) как частное отделения остатка, полученного на предыдущей итерации, на основание q новой системы счисления, возведјнное в степень m 2:
b m
2
?
m
1
div q и вместе с ней по второй из формул (1.7) вычисляется остаток отделения величины на основание q, возведјнное в степень m 2:
?
m
2
?
m
1
mod q Далее поэтому алгоритму определяются цифры b m
3
, b m
4
, . . . , Младшая же цифра равна ?
1
, те. она совпадает с последним остатком отделения величины на основание В рассмотренном алгоритме остајтся невыясненным один момент. Нам заранее неизвестно количество цифр в числе Z
q
, те. нам неизвестно число, а не зная его, мы не сможем выполнить даже самую первую итерацию алгоритма.
Однако число m 1 можно легко определить из следующих соображений. Из формулы 1.6 следует, что m 1 наибольшая из степеней основания q, которая не превосходит значение Z
q
, а последнее, в свою очередь, совпадает со значением Z
10
. Иными словами m
1
( и q
m
% Из последних двух неравенств следует, что m
1 ( log и m
% log q
Z
10
,
1.3. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
19
а с учјтом того, что m 1 целое число, получаем m
1 log q
Z
10
Второй способ перевода чисел из десятичной системы счисления реализуется в соответствии со следующим алгоритмом. Определить значение m 1 по формуле (1.8).
2. Разделить исходное число на число q и определить частное и остаток отделения. Частное отделения будет являться старшей цифрой числа Z
q
3. Остаток отделения, вычисленный на втором шаге, разделить на число и снова определить частное и остаток отделения. Частное отделения будет являться второй цифрой числа Z
q
4. Процесс деления продолжать до тех пор, пока показатель степени числа не станет равным нулю. Вычисленные частные отделения и остаток отделения, который был получен на последней итерации алгоритма, записанные в порядке их вычисления, и образуют число Пример Решим задачу из примера 1.7, используя второй способ.
Р е ш е ни е Сначала определим число m 1 по формуле (1.8):
m
1 log
6 5025
Вычисление логарифма, находящегося в правой части равенства, представляет сложность даже при наличии электронных вычислительных средств, поскольку возможность вычисления логарифма по основанию 6 вряд ли реализована хотя бы водном калькуляторе.
Но практически в любом калькуляторе реализована возможность вычисления натурального и десятичного логарифмов. Поэтому перейдјт от логарифма по основанию к любому из них (например, к десятичному логарифму 1 log
6 5025
lg 5025
lg 6
Теперь оба логарифма мы можем вычислить, но лишь приближјнно. Применительно к нашим данным мы получаем следующие результаты вычисления на калькуляторе. Выполним оценки сверху и снизу для вычисленных значений, 701
( lg 5025 ( 3, 702;
0, 778
( lg 6 ( 0, Тогда, 7
(
3, 701 0, 779 (
log
10 5025
log
10 6
(
3, 702 0, 778 (
4, 8
РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
и
4
4, 7 (
log
10 5025
log
10 6
( 4, 8 Из полученных неравенств следует, что m
1
log
10 5025
log
10 6
Дальнейший процесс перевода исходного числа в шестеричную систему счисления можно представить следующим образом 1296 3888 3
1137 216 1080 5
57 36 36 1
21 6
18 Частные 3, 5, 1, 3 отделения и остаток 3, полученный на последней итерации, образуют прямой порядок цифр числа в шестеричной системе счисления. Следовательно 10 35133 6
. Сравнивая этот результат с результатом, полученным при выполнении примера 1.7, убеждаемся в том, что они совпадают.
О т в е т 5025 10 35133 Алгоритм перевода явно следует из выражения (1.1), т. е.
необходимо значение Z
p представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.
П р им ер Перевести число 35133 6
, полученное в результате выполнения примеров 1.7 и 1.8, обратно в десятичную систему счисления.
Р е ш е ни е Представим исходное значение в виде многочлена в соответствии с формулой (1.1):
4 3 2 1 0 35133 6
3 6 4
5 6 3
1 6 2
3 6 1
3 6 0
3 1296
5 216 1 36 3 6 3 1 3888
1080 36 18 3 5025 Ответ 10
Ещј раз отметим, что приведјнные алгоритмы удобно использовать при переводе числа из десятичной системы счисления в какую-либо другую или наоборот. Эти алгоритмы остаются работоспособными при преобразованиях между любыми системами счисления, в том числе ив случаях,
когда и исходная, и конечная системы счисления отличны от десятичной системы. Однако в этих случаях преобразование будет затруднено тем
1.3. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
21
что все арифметические операции необходимо выполнять по правилам исходной (в двух первых алгоритмах) или конечной (в последнем алгоритме)
системы счисления.
По этой причине преобразование Z
p
Z
q
, где p j 10 и q j 10, проще осуществить через промежуточное преобразование к десятичной системе счисления, те. Пример Перевести число 6199 в семеричную систему счисления.
Р е ш е ни е Сначала выполним перевод из тринадцатеричной системы счисления в десятичную 2 1 0 6199 13 6 13 3
1 13 2
9 13 1
9 13 0
6 2197
1 169 9 13 9 1 13182
169 117 9 13477 Теперь переведјм полученное десятичное число в семеричную систему счисления 7
13475 1925 7
2 1925 275 7 0 273 39 7 2 35 5 Таким образом, 6199 13 13477 10 54202 Ответ РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
и
4
4, 7 (
log
10 5025
log
10 6
( 4, 8 Из полученных неравенств следует, что m
1
log
10 5025
log
10 6
Дальнейший процесс перевода исходного числа в шестеричную систему счисления можно представить следующим образом 1296 3888 3
1137 216 1080 5
57 36 36 1
21 6
18 Частные 3, 5, 1, 3 отделения и остаток 3, полученный на последней итерации, образуют прямой порядок цифр числа в шестеричной системе счисления. Следовательно 10 35133 6
. Сравнивая этот результат с результатом, полученным при выполнении примера 1.7, убеждаемся в том, что они совпадают.
О т в е т 5025 10 35133 Алгоритм перевода явно следует из выражения (1.1), т. е.
необходимо значение Z
p представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.
П р им ер Перевести число 35133 6
, полученное в результате выполнения примеров 1.7 и 1.8, обратно в десятичную систему счисления.
Р е ш е ни е Представим исходное значение в виде многочлена в соответствии с формулой (1.1):
4 3 2 1 0 35133 6
3 6 4
5 6 3
1 6 2
3 6 1
3 6 0
3 1296
5 216 1 36 3 6 3 1 3888
1080 36 18 3 5025 Ответ 10
Ещј раз отметим, что приведјнные алгоритмы удобно использовать при переводе числа из десятичной системы счисления в какую-либо другую или наоборот. Эти алгоритмы остаются работоспособными при преобразованиях между любыми системами счисления, в том числе ив случаях,
когда и исходная, и конечная системы счисления отличны от десятичной системы. Однако в этих случаях преобразование будет затруднено тем
1.3. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ
21
что все арифметические операции необходимо выполнять по правилам исходной (в двух первых алгоритмах) или конечной (в последнем алгоритме)
системы счисления.
По этой причине преобразование Z
p
Z
q
, где p j 10 и q j 10, проще осуществить через промежуточное преобразование к десятичной системе счисления, те. Пример Перевести число 6199 в семеричную систему счисления.
Р е ш е ни е Сначала выполним перевод из тринадцатеричной системы счисления в десятичную 2 1 0 6199 13 6 13 3
1 13 2
9 13 1
9 13 0
6 2197
1 169 9 13 9 1 13182
169 117 9 13477 Теперь переведјм полученное десятичное число в семеричную систему счисления 7
13475 1925 7
2 1925 275 7 0 273 39 7 2 35 5 Таким образом, 6199 13 13477 10 54202 Ответ РАЗДЕЛ 1. СИСТЕМЫ СЧИСЛЕНИЯ
Раздел Представление числовой информации Представление чисел в формате с фиксированной запятой
РАЗДЕЛ 2. ПРЕДСТАВЛЕНИЕ ЧИСЛОВОЙ ИНФОРМАЦИИ
Раздел Основы алгебры логики
Теоретической базой цифровой вычислительной техники является алгебра логики, или булева алгебра, названная по имение основоположника английского математика и логика Джорджа Буля.
В алгебре логики любая из переменных может принимать одно из двух значений true (истина) или false (ложь. Эти значения в цифровой технике принято рассматривать как логическую единицу (true) и логический нуль (false) или как двоичные цифры 1 и 0, а физически представлять в виде наличия или отсутствия некоторого сигнала.
Как правило, компьютеры оперируют наборами логических переменных длиной в машинное слово (см. разд. 2.1). Такие слова обрабатываются с помощью команд, реализующих логические операции, которые рассматриваются в разд. 3.2. При этом все разряды машинного слова обрабатываются одинаково, но независимо друг от друга, те. никаких переносов между разрядами не происходит Понятие функции алгебры логики
О пределен и е 3.1 Функция f x
1
, x
2
, . . . , x n
, зависящая от n переменных, называется функцией алгебры логики (булевой функцией, логической функцией, переключательной функцией),
если сама функция и любой из е аргументов могут принимать значения только из множества r0, Определение Совокупность значений аргументов булевой функции называется набором и обозначается x
1
, x
2
, . . . , x Поскольку любой набор имеет длину, равную n, и может содержать лишь два значения (0 и 1), которые могут повторяться, то число всех возможных наборов равно числу размещений из двух элементов пос повторениями, те РАЗДЕЛ 3. ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
Для описания функции алгебры логики используется один из следующих способов вербальный табличный числовой аналитический координатный графический (геометрический).
При вербальном способе все случаи, когда функция алгебры логики принимает значение 0 и/или 1, описываются словесно. Например, функцию
ИЛИ с произвольным числом аргументов можно описать следующим образом функция принимает значение 1, если хотя бы один из е аргументов равен 1, в противном случае значение функции равно 0 или функция принимает значение 0, если все е аргументы равны 0, в противном случае значение функции равно При табличном способе функция алгебры логики задајтся в виде таблицы истинности. В левой части таблицы истинности перечисляются всевозможные наборы аргументов, а в правой значения функции на этих наборах (табл. 3.1, а. Таблица истинности содержит 2
n строк
(число всех возможных наборов аргументов) и n 1 столбец (n значений аргументов и одно значение функции).
Таблица 3.1: Представления таблицы истинности Номер набора f
0 0
0 0 0
0 0
0 1 1 1
1 0
1 0 1 2
1 0
1 1 1 3
1 1
0 0 1 4
1 1
0 1 1 5
1 1
1 0 1 6
1 1
1 1 1 а б
Иногда вместо двоичных наборов аргументов в таблице истинности указывают их десятичные эквиваленты (табл. 3.1, б При числовом способе функция алгебры логики задајтся в виде последовательности десятичных эквивалентов тех наборов аргументов, на ко
3.1. ПОНЯТИЕ ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
27
торых функция принимает значение 0 или 1. Например, двоичным наборам аргументов r0, 1, 0x и r1, 0, 1x соответствуют десятичные числа 2 и При таком подходе логическая функция ИЛИ трјх переменных, представленная в табл. 3.1, может быть записана в виде f 1, 2, 3, 4, 5, 6, 7 1 или f 0
Аналитический способ предполагает описание функции алгебры логики в виде алгебраического выражения, которое получается путјм применения к аргументам функции операций алгебры логики. Способ получения такого описания функции алгебры логики будет рассмотрен в разд.
3.3.
При координатном способе задания таблица истинности заменяется координатной картой состояний, называемой картой Карно. Такая карта содержит 2
n клеток, соответствующих числу всех возможных наборов из n переменных. Аргументы функции алгебры логики разбиваются на две группы таким образом, что одна группа определяет координаты столбца, а другая координаты строки. Иными словами, каждой строке таблицы истинности (те. каждому набору аргументов, соответствует единственная клетка карты Карно, внутри которой указывается значение функции. В табл. 3.2 представлена карта Карно, соответствующая таблице истинности для функции ИЛИ, зависящей от трјх переменных
(ср. с табл. Таблица 3.2: Карта Карно x
1
x
2 00 01 11 10
x
3 0 0 1
1 1
1 1 1
1 При графическом (геометрическом) способе функция алгебры логики f x
1
, x
2
, . . . , x n
задајтся с помощью мерного куба, поскольку в геометрическом смысле каждый двоичный набор x
1
, x
2
, . . . , x n
есть мерный вектор, определяющий точку в мерном векторном пространстве. По этой причине любой набор аргументов при графическом способе представления функции алгебры логики принято называть вектором,
а его компоненты координатами. Количество переменных определяет размерность куба (одномерный, двумерный, трјхмерный, . . . , n-мерный).
Множество наборов, на которых определена функция n переменных,
представляются вершинами мерного куба. Отметив прозрачными точками вершины куба, соответствующие наборам, на которых функция принимает нулевое значение, и непрозрачными точками вершины, соответствующие наборам, на которых функция принимает единичное значение, мы
Теоретической базой цифровой вычислительной техники является алгебра логики, или булева алгебра, названная по имение основоположника английского математика и логика Джорджа Буля.
В алгебре логики любая из переменных может принимать одно из двух значений true (истина) или false (ложь. Эти значения в цифровой технике принято рассматривать как логическую единицу (true) и логический нуль (false) или как двоичные цифры 1 и 0, а физически представлять в виде наличия или отсутствия некоторого сигнала.
Как правило, компьютеры оперируют наборами логических переменных длиной в машинное слово (см. разд. 2.1). Такие слова обрабатываются с помощью команд, реализующих логические операции, которые рассматриваются в разд. 3.2. При этом все разряды машинного слова обрабатываются одинаково, но независимо друг от друга, те. никаких переносов между разрядами не происходит Понятие функции алгебры логики
О пределен и е 3.1 Функция f x
1
, x
2
, . . . , x n
, зависящая от n переменных, называется функцией алгебры логики (булевой функцией, логической функцией, переключательной функцией),
если сама функция и любой из е аргументов могут принимать значения только из множества r0, Определение Совокупность значений аргументов булевой функции называется набором и обозначается x
1
, x
2
, . . . , x Поскольку любой набор имеет длину, равную n, и может содержать лишь два значения (0 и 1), которые могут повторяться, то число всех возможных наборов равно числу размещений из двух элементов пос повторениями, те РАЗДЕЛ 3. ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
Для описания функции алгебры логики используется один из следующих способов вербальный табличный числовой аналитический координатный графический (геометрический).
При вербальном способе все случаи, когда функция алгебры логики принимает значение 0 и/или 1, описываются словесно. Например, функцию
ИЛИ с произвольным числом аргументов можно описать следующим образом функция принимает значение 1, если хотя бы один из е аргументов равен 1, в противном случае значение функции равно 0 или функция принимает значение 0, если все е аргументы равны 0, в противном случае значение функции равно При табличном способе функция алгебры логики задајтся в виде таблицы истинности. В левой части таблицы истинности перечисляются всевозможные наборы аргументов, а в правой значения функции на этих наборах (табл. 3.1, а. Таблица истинности содержит 2
n строк
(число всех возможных наборов аргументов) и n 1 столбец (n значений аргументов и одно значение функции).
Таблица 3.1: Представления таблицы истинности Номер набора f
0 0
0 0 0
0 0
0 1 1 1
1 0
1 0 1 2
1 0
1 1 1 3
1 1
0 0 1 4
1 1
0 1 1 5
1 1
1 0 1 6
1 1
1 1 1 а б
Иногда вместо двоичных наборов аргументов в таблице истинности указывают их десятичные эквиваленты (табл. 3.1, б При числовом способе функция алгебры логики задајтся в виде последовательности десятичных эквивалентов тех наборов аргументов, на ко
3.1. ПОНЯТИЕ ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
27
торых функция принимает значение 0 или 1. Например, двоичным наборам аргументов r0, 1, 0x и r1, 0, 1x соответствуют десятичные числа 2 и При таком подходе логическая функция ИЛИ трјх переменных, представленная в табл. 3.1, может быть записана в виде f 1, 2, 3, 4, 5, 6, 7 1 или f 0
Аналитический способ предполагает описание функции алгебры логики в виде алгебраического выражения, которое получается путјм применения к аргументам функции операций алгебры логики. Способ получения такого описания функции алгебры логики будет рассмотрен в разд.
3.3.
При координатном способе задания таблица истинности заменяется координатной картой состояний, называемой картой Карно. Такая карта содержит 2
n клеток, соответствующих числу всех возможных наборов из n переменных. Аргументы функции алгебры логики разбиваются на две группы таким образом, что одна группа определяет координаты столбца, а другая координаты строки. Иными словами, каждой строке таблицы истинности (те. каждому набору аргументов, соответствует единственная клетка карты Карно, внутри которой указывается значение функции. В табл. 3.2 представлена карта Карно, соответствующая таблице истинности для функции ИЛИ, зависящей от трјх переменных
(ср. с табл. Таблица 3.2: Карта Карно x
1
x
2 00 01 11 10
x
3 0 0 1
1 1
1 1 1
1 При графическом (геометрическом) способе функция алгебры логики f x
1
, x
2
, . . . , x n
задајтся с помощью мерного куба, поскольку в геометрическом смысле каждый двоичный набор x
1
, x
2
, . . . , x n
есть мерный вектор, определяющий точку в мерном векторном пространстве. По этой причине любой набор аргументов при графическом способе представления функции алгебры логики принято называть вектором,
а его компоненты координатами. Количество переменных определяет размерность куба (одномерный, двумерный, трјхмерный, . . . , n-мерный).
Множество наборов, на которых определена функция n переменных,
представляются вершинами мерного куба. Отметив прозрачными точками вершины куба, соответствующие наборам, на которых функция принимает нулевое значение, и непрозрачными точками вершины, соответствующие наборам, на которых функция принимает единичное значение, мы
РАЗДЕЛ 3. ОСНОВЫ АЛГЕБРЫ ЛОГИКИ
получим геометрическое представление функции алгебры логики. В этом случае функция ИЛИ трјх переменных, представленная таблицей истинности, может быть изображена в виде трјхмерного куба (рис. Рис. 3.1: Геометрическое представление функции ИЛИ
Кроме перечисленных форм, иногда используются менее распространјнные способы описания функций алгебры логики с помощью комбинационных схем, которые составлены из логических элементов (см. разд. с помощью диаграмм двоичного решения, диаграмм Венна и т. д.
О пределен и е 3.3 Булева функция, которая определена на всех возможных наборах переменных, называется полностью определјнной. Если же функция алгебры логики определена лишь на некоторых наборах переменных, то она называется частично определјнной.
Примером полностью определјнной функции алгебры логики является функция ИЛИ, способы описания которой были рассмотрены выше
(см. табл. 3.1, 3.2 ирис. Частично определјнные функции описываются теми же способами,
что и полностью определјнные. Отличие состоит лишь в том, что наборы,
на которых значения функции алгебры логики не определены, помечаются каким-либо символом, отличным от нуля и единицы (например, звјздоч- кой) (табл. Таблица 3.3: Частично определјнная функция x
1
x
2
x
3
f
0 0
0 0
0 0
1 1
0 1
0 “
0 1
1 0
1 0
0 1
1 0
1 “
1 1
0 0
1 1
1 “
3.2 Элементарные функции алгебры логики Аналитическое представление булевых функций
получим геометрическое представление функции алгебры логики. В этом случае функция ИЛИ трјх переменных, представленная таблицей истинности, может быть изображена в виде трјхмерного куба (рис. Рис. 3.1: Геометрическое представление функции ИЛИ
Кроме перечисленных форм, иногда используются менее распространјнные способы описания функций алгебры логики с помощью комбинационных схем, которые составлены из логических элементов (см. разд. с помощью диаграмм двоичного решения, диаграмм Венна и т. д.
О пределен и е 3.3 Булева функция, которая определена на всех возможных наборах переменных, называется полностью определјнной. Если же функция алгебры логики определена лишь на некоторых наборах переменных, то она называется частично определјнной.
Примером полностью определјнной функции алгебры логики является функция ИЛИ, способы описания которой были рассмотрены выше
(см. табл. 3.1, 3.2 ирис. Частично определјнные функции описываются теми же способами,
что и полностью определјнные. Отличие состоит лишь в том, что наборы,
на которых значения функции алгебры логики не определены, помечаются каким-либо символом, отличным от нуля и единицы (например, звјздоч- кой) (табл. Таблица 3.3: Частично определјнная функция x
1
x
2
x
3
f
0 0
0 0
0 0
1 1
0 1
0 “
0 1
1 0
1 0
0 1
1 0
1 “
1 1
0 0
1 1
1 “
3.2 Элементарные функции алгебры логики Аналитическое представление булевых функций
Раздел Основы цифровой схемотехники Синтез и анализ комбинационных схем
РАЗДЕЛ 4. ОСНОВЫ ЦИФРОВОЙ СХЕМОТЕХНИКИ
Часть КОНТРОЛЬНЫЕ РАБОТЫ
Самостоятельная работа представляет собой вид деятельности, которую осуществляют студенты вне аудиторий, те. в свободное от занятий время и посвящена выполнению практических заданий в рамках дисципли- ны.
Все контрольные работы, которые предлагаются студентам для самостоятельного выполнения, сгруппированы по тематике лекционных и практических занятий, на которых изучаются соответствующие теоретические положения и приобретаются практические навыки. Например, контрольная работа 1 включает в себя задания, связанные с использованием различных систем счисления и переводами чисел из одной системы счисления в другую.
Контрольные работы выполняются с целью закрепления теоретических знаний, которые были получены на лекционных и практических занятиях, и приобретения навыков применения этих знаний при решении практических задач. Для оформления выполненных контрольных работ необходимо завести две листовые тетради в клетку, первую из которых нужно подписать следующим образом:
Т Е Т РАД Ь
для контрольных работ по дисциплинеѕМашинная арифметика и цифровая логикаї
(раздел Машинная арифметикаї)
студента 104(105) группы факультета математики и информационных технологий
Иванова Ивана Ивановича
(Ивановой Марии Ивановны)
Вариант Вторая тетрадь должна быть подписана аналогично первой, но вместо надписи (раздел Машинная арифметикаї) следует указать (раздел
ѕЦифровая логикаї)
1
Примеры оформления контрольных работ приведены в последующих разделах непосредственно после формулировок заданий.
Контрольная работа может состоять из нескольких заданий. Например, контрольная работа 1 состоит из тринадцати заданий. Каждое задание преподаватель оценивает определјнным количеством баллов, которое выражается целым числом и зависит от степени трудојмкости задания. Это значение указывается для каждого задания непосредственно по-
1
Эти два раздела дисциплины будут изучаться параллельно, поэтому оформлять выполненные задания по машинной арифметике и цифровой логике лучше в разных тетрадях
34
сле самой формулировки задания, заключается в скобки и выделяется подчјркиванием.
В следующей таблице приведены наименования контрольных работ и содержащихся в них заданий, которые предлагаются студентам для самостоятельного выполнения.
ќ
Наименование работы
Перечень заданий
Макс.
п/п кол-во баллов
1
Системы счисления
Перевод десятичных чисел в римскую систему счисления
3
Перевод чисел из римской системы счисления в десятичную
3
Итого
6
Все контрольные работы, которые предлагаются студентам для самостоятельного выполнения, сгруппированы по тематике лекционных и практических занятий, на которых изучаются соответствующие теоретические положения и приобретаются практические навыки. Например, контрольная работа 1 включает в себя задания, связанные с использованием различных систем счисления и переводами чисел из одной системы счисления в другую.
Контрольные работы выполняются с целью закрепления теоретических знаний, которые были получены на лекционных и практических занятиях, и приобретения навыков применения этих знаний при решении практических задач. Для оформления выполненных контрольных работ необходимо завести две листовые тетради в клетку, первую из которых нужно подписать следующим образом:
Т Е Т РАД Ь
для контрольных работ по дисциплинеѕМашинная арифметика и цифровая логикаї
(раздел Машинная арифметикаї)
студента 104(105) группы факультета математики и информационных технологий
Иванова Ивана Ивановича
(Ивановой Марии Ивановны)
Вариант Вторая тетрадь должна быть подписана аналогично первой, но вместо надписи (раздел Машинная арифметикаї) следует указать (раздел
ѕЦифровая логикаї)
1
Примеры оформления контрольных работ приведены в последующих разделах непосредственно после формулировок заданий.
Контрольная работа может состоять из нескольких заданий. Например, контрольная работа 1 состоит из тринадцати заданий. Каждое задание преподаватель оценивает определјнным количеством баллов, которое выражается целым числом и зависит от степени трудојмкости задания. Это значение указывается для каждого задания непосредственно по-
1
Эти два раздела дисциплины будут изучаться параллельно, поэтому оформлять выполненные задания по машинной арифметике и цифровой логике лучше в разных тетрадях
34
сле самой формулировки задания, заключается в скобки и выделяется подчјркиванием.
В следующей таблице приведены наименования контрольных работ и содержащихся в них заданий, которые предлагаются студентам для самостоятельного выполнения.
ќ
Наименование работы
Перечень заданий
Макс.
п/п кол-во баллов
1
Системы счисления
Перевод десятичных чисел в римскую систему счисления
3
Перевод чисел из римской системы счисления в десятичную
3
Итого
6
Контрольная работа Системы счисления Перевод десятичных чисел в римскую систему счисления
Для данных из табл. 1.1 выполнить перевод целого десятичного числа в римскую систему счисления (3 балла).
Таблица Вариант Десятичное число Вариант Десятичное число Z
10 1
134 598 952 26 757 402 395 2
455 266 803 27 197 210 659 3
657 018 380 28 817 624 253 4
577 443 628 29 352 665 071 5
870 726 347 30 911 527 499 6
712 091 604 31 999 754 625 7
249 800 155 32 784 802 195 8
348 809 221 33 587 851 476 9
498 501 042 34 715 393 458 10 226 539 112 35 816 550 627 11 580 566 420 36 140 228 774 12 179 465 928 37 121 297 878 13 563 788 045 38 281 728 607 14 188 452 875 39 158 017 392 15 985 309 647 40 524 209 418 16 856 318 743 41 329 983 471 17 557 980 805 42 111 254 588 18 894 533 328 43 397 781 116 19 943 462 614 44 549 791 403 20 450 185 818 45 976 290 648 21 292 068 303 46 454 242 810 22 432 700 675 47 159 595 038 23 423 351 762 48 235 716 853 24 603 076 484 49 270 108 419 25 153 446 962 50 189 265 440
Для данных из табл. 1.1 выполнить перевод целого десятичного числа в римскую систему счисления (3 балла).
Таблица Вариант Десятичное число Вариант Десятичное число Z
10 1
134 598 952 26 757 402 395 2
455 266 803 27 197 210 659 3
657 018 380 28 817 624 253 4
577 443 628 29 352 665 071 5
870 726 347 30 911 527 499 6
712 091 604 31 999 754 625 7
249 800 155 32 784 802 195 8
348 809 221 33 587 851 476 9
498 501 042 34 715 393 458 10 226 539 112 35 816 550 627 11 580 566 420 36 140 228 774 12 179 465 928 37 121 297 878 13 563 788 045 38 281 728 607 14 188 452 875 39 158 017 392 15 985 309 647 40 524 209 418 16 856 318 743 41 329 983 471 17 557 980 805 42 111 254 588 18 894 533 328 43 397 781 116 19 943 462 614 44 549 791 403 20 450 185 818 45 976 290 648 21 292 068 303 46 454 242 810 22 432 700 675 47 159 595 038 23 423 351 762 48 235 716 853 24 603 076 484 49 270 108 419 25 153 446 962 50 189 265 440
КОНТРОЛЬНАЯ РАБОТА 1. СИСТЕМЫ СЧИСЛЕНИЯ
П р им ер выполнения задания КОНТРОЛЬНАЯ РАБОТА ќ СИСТЕМЫ СЧИСЛЕНИЯ
Задание 1.1. Выполнить перевод целого числа 738 620 105 из десятичной системы счисления в римскую.
Решение. Выполним разложение каждой из составляющих исходного десятичного числа на сумму чисел, которые используются в римской системе счисления в качестве базовых 620 105 10 738 10 6
620 10 3
105 500
100 210 351 3 10 6
500 100 10 2 10 3
100 Заменим каждое базовое число эквивалентной римской цифрой и запишем исходное число в римской системе счисления 620 105 10
DCCXXXVIII DCXX Ответ. 738 620 105 10
DCCXXXVIII DCXX CV
1.2 Перевод чисел из римской системы счисления в десятичную
Для данных из табл. 1.2 выполнить перевод числа, представленного в римской системе счисления, в десятичную систему (3 балла).
Таблица 1.2:
Вариант
Римское число DLXX XCIII
2
DCCCLVIII CCXXII DCCXC
3
VIII CDXLVII DCLIII
4
CCXLI CLXXXVII CCCXXXIV
5
CCCXLVI LV CCCLXX
6
DCII DCCLXXXIII CMLXXVII
7
DCCCLXXXIX DLXXIII CXCVIII
8
DCCCLXIII DCLXXXV окончание наследующей странице
1.2. ПЕРЕВОД ЧИСЕЛ ИЗ РИМСКОЙ СИСТЕМЫ СЧИСЛЕНИЯ
37
окончание табл. 1.2
Вариант
Римское число CDXXXVI DCCLXXVIII
10
DCCCLXIV XXXIX CMLXXXI
11
CCCLXV CDLIX XXII
12
LXV DCCCLVII CCXVI
13
CCCLXXXV LXVII DCCCXXXI
14
DCCCXLVII DCXXX CCXLIV
15
CDLXXX DIV DCXLII
16
CCCLX CXXIV CDXLIX
17
CCXXIII XXXV DCCLXVII
18
X CCCXLIII DCCXXXIV
19
DCLV CCXL DCCCXCI
20
C CCCXLIV DCCXXV
21
CDXC CCXLV DLXXVIII
22
L CDXVII DCCCXCV
23
CMXXX DCCCXV CXLIX
24
CCCXII CMLVIII CLXXXIV
25
DCXXII CCCXXXVII DCCLXVIII
26
CCCXXV CLXXI CMXVIII
27
CDXXII CXXXVI CCCXIX
28
CCXX DCLXIII CDLXXXIX
29
CMVII CDLXXXI DCCLIX
30
LXXXVII CLX DCCII
31
III CDLXXXVI DXL
32
DCCLXX DLXXXV XXXVI
33
CMLXIV DXLVI XXIII
34
CLIV DCCXLV DCXCI
35
CMLXX CCXCIII DCLVI
36
CCCLVI CCXIV DCCCLXXI
37
CMLXXVIII CXLIV CCLXXXVI
38
CCXXXIV CMII CCCXXVII
39
CMLXXXIX CXLVII CDLXVIII
40
CCCLXXXII CMX CCLI
41
CCXXXI CXVII LXXIX
42
CCXXXVII CLXIX CMLXXXVIII
43
DCCCLXXXII CMXXXIII окончание наследующей странице
П р им ер выполнения задания КОНТРОЛЬНАЯ РАБОТА ќ СИСТЕМЫ СЧИСЛЕНИЯ
Задание 1.1. Выполнить перевод целого числа 738 620 105 из десятичной системы счисления в римскую.
Решение. Выполним разложение каждой из составляющих исходного десятичного числа на сумму чисел, которые используются в римской системе счисления в качестве базовых 620 105 10 738 10 6
620 10 3
105 500
100 210 351 3 10 6
500 100 10 2 10 3
100 Заменим каждое базовое число эквивалентной римской цифрой и запишем исходное число в римской системе счисления 620 105 10
DCCXXXVIII DCXX Ответ. 738 620 105 10
DCCXXXVIII DCXX CV
1.2 Перевод чисел из римской системы счисления в десятичную
Для данных из табл. 1.2 выполнить перевод числа, представленного в римской системе счисления, в десятичную систему (3 балла).
Таблица 1.2:
Вариант
Римское число DLXX XCIII
2
DCCCLVIII CCXXII DCCXC
3
VIII CDXLVII DCLIII
4
CCXLI CLXXXVII CCCXXXIV
5
CCCXLVI LV CCCLXX
6
DCII DCCLXXXIII CMLXXVII
7
DCCCLXXXIX DLXXIII CXCVIII
8
DCCCLXIII DCLXXXV окончание наследующей странице
1.2. ПЕРЕВОД ЧИСЕЛ ИЗ РИМСКОЙ СИСТЕМЫ СЧИСЛЕНИЯ
37
окончание табл. 1.2
Вариант
Римское число CDXXXVI DCCLXXVIII
10
DCCCLXIV XXXIX CMLXXXI
11
CCCLXV CDLIX XXII
12
LXV DCCCLVII CCXVI
13
CCCLXXXV LXVII DCCCXXXI
14
DCCCXLVII DCXXX CCXLIV
15
CDLXXX DIV DCXLII
16
CCCLX CXXIV CDXLIX
17
CCXXIII XXXV DCCLXVII
18
X CCCXLIII DCCXXXIV
19
DCLV CCXL DCCCXCI
20
C CCCXLIV DCCXXV
21
CDXC CCXLV DLXXVIII
22
L CDXVII DCCCXCV
23
CMXXX DCCCXV CXLIX
24
CCCXII CMLVIII CLXXXIV
25
DCXXII CCCXXXVII DCCLXVIII
26
CCCXXV CLXXI CMXVIII
27
CDXXII CXXXVI CCCXIX
28
CCXX DCLXIII CDLXXXIX
29
CMVII CDLXXXI DCCLIX
30
LXXXVII CLX DCCII
31
III CDLXXXVI DXL
32
DCCLXX DLXXXV XXXVI
33
CMLXIV DXLVI XXIII
34
CLIV DCCXLV DCXCI
35
CMLXX CCXCIII DCLVI
36
CCCLVI CCXIV DCCCLXXI
37
CMLXXVIII CXLIV CCLXXXVI
38
CCXXXIV CMII CCCXXVII
39
CMLXXXIX CXLVII CDLXVIII
40
CCCLXXXII CMX CCLI
41
CCXXXI CXVII LXXIX
42
CCXXXVII CLXIX CMLXXXVIII
43
DCCCLXXXII CMXXXIII окончание наследующей странице
КОНТРОЛЬНАЯ РАБОТА 1. СИСТЕМЫ СЧИСЛЕНИЯ
окончание табл. 1.2
Вариант
Римское число CXCVI LXXVIII
45
CCLXXXV CMIX DXXXVI
46
CCXVII CLXXV DCIX
47
CMXCIII DCCCXII DCXXVI
48
DCCCLXIX XXV CCLVI
49
CCCLXVIII DCCCXX XCV
50
DCCCXXII CMVIII Пример выполнения задания Задание 1.2. Выполнить перевод числа DCCXCIX представленного в римской системе счисления, в десятичную систему.
Решение. Разобьјм каждую составляющую исходного числа на одиночные римские цифры, на группы повторяющихся римских цифр и на неделимые комбинации римских цифр DCCXCIX CMLXVII
D CCC L XX III D CC XC IX CM L X V Заменим все римские цифры и их комбинации эквивалентными десятичными числами и вычислим значение десятичного числа, равного заданному Ответ. DCCCLXXIII DCCXCIX CMLXVII 873 799 967 10
окончание табл. 1.2
Вариант
Римское число CXCVI LXXVIII
45
CCLXXXV CMIX DXXXVI
46
CCXVII CLXXV DCIX
47
CMXCIII DCCCXII DCXXVI
48
DCCCLXIX XXV CCLVI
49
CCCLXVIII DCCCXX XCV
50
DCCCXXII CMVIII Пример выполнения задания Задание 1.2. Выполнить перевод числа DCCXCIX представленного в римской системе счисления, в десятичную систему.
Решение. Разобьјм каждую составляющую исходного числа на одиночные римские цифры, на группы повторяющихся римских цифр и на неделимые комбинации римских цифр DCCXCIX CMLXVII
D CCC L XX III D CC XC IX CM L X V Заменим все римские цифры и их комбинации эквивалентными десятичными числами и вычислим значение десятичного числа, равного заданному Ответ. DCCCLXXIII DCCXCIX CMLXVII 873 799 967 10
Предметный указатель
Алгебра булева, см. Алгебра логики логики, Алфавит системы счисления, Вектор, Единица логическая, Координата, Набор, Нуль логический, Основание системы счисления, Система счисления, двоичная, десятичная, 8
непозиционная, позиционная, римская, унарная, Способ описания функции алгебры логики аналитический, вербальный, геометрический, см. Способ описания функции алгебры логики графический графический, координатный, табличный, числовой, Таблица истинности, Функция алгебры логики, полностью определјнная, частично определјнная, булева, см. Функция алгебры логики логическая, см. Функция алгебры логики переключательная, см. Функция алгебры логики
Цифра, арабская, римская, 10 39
Алгебра булева, см. Алгебра логики логики, Алфавит системы счисления, Вектор, Единица логическая, Координата, Набор, Нуль логический, Основание системы счисления, Система счисления, двоичная, десятичная, 8
непозиционная, позиционная, римская, унарная, Способ описания функции алгебры логики аналитический, вербальный, геометрический, см. Способ описания функции алгебры логики графический графический, координатный, табличный, числовой, Таблица истинности, Функция алгебры логики, полностью определјнная, частично определјнная, булева, см. Функция алгебры логики логическая, см. Функция алгебры логики переключательная, см. Функция алгебры логики
Цифра, арабская, римская, 10 39