Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
x n · y n ). Легко проверяется, что от- ношение ∼ является конгруэнцией алгебры X. Фактор-алгебра X/∼ обра- зует множество действительных чисел с обычными операциями сложения и умножения. В алгебре hR; +, ·i выполняются все аксиомы поля. Нулевым элементом является класс ∼ (0); единицей — класс ∼ (1); противоположным классу ∼ (x n ) является класс −(∼ (x n )) ∼ (−x n ); обратным ненулевому классу ∼ (x n ), где (x n ) является последовательностью без нулевых элемен- тов, — класс (∼ (x n )) −1 ∼ ((x n ) −1 ). Отметим, что каждый класс ∼ (x n ) содержит единственную последова- тельность (x 0 n ), такую, что x 0 n = ±(a k 10 k + a k−1 10 k−1 + . . . + a 1 10 1 + a 0 10 0 + +a −1 10 −1 + a −2 10 −2 + . . . + a −n 10 −n ), где a i ∈ {0, 1, . . . , 9} и не существует n с условием a −i = 9 при i > n. Поэтому для обозначения действительных чисел используются следующие записи, называемые (бесконечными) десятичными дробями: ±a k a k−1 . . . a 1 a 0 .a −1 a −2 . . . a −n . . . . Каждая фундаментальная последовательность (x n ) может иметь или не иметь предел в множестве рациональных чисел. В первом случае любая последовательность из класса ∼ (x n ) сходится к одному и тому же рацио- нальному числу q, и поэтому такие классы удобно называть рациональными числами. Во втором случае, когда предела в Q не существует, класс ∼ (x n ) называется иррациональным числом. Десятичная дробь N.a 1 a 2 . . . a n . . ., где N ∈ Z, называется периодиче- ской, если существуют такие натуральные числа p, q, что a k+p = a k для всех k > q. Для обозначения периодической дроби используется запись N.a 1 a 2 . . . a q (a q+1 a q+2 . . . a q+p ), где совокупность цифр a q+1 a q+2 . . . a q+p назы- вается периодом дроби. 82 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Предложение 3.1.5. Бесконечная десятичная дробь тогда и только тогда является рациональным числом, когда она периодична. ¤ Поскольку для любого конечного алфавита A множество слов W (A) счет- но, а множество действительных чисел континуально, справедливо следую- щее предложение. Предложение 3.1.6. Не существует конечного алфавита, при помо- щи слов которого можно обозначить все действительные числа. ¤ 5. Поле комплексных чисел Множество C комплексных чисел строится из множества действительных чисел по правилу C = R 2 . Операции сложения и умножения определяются по следующим правилам: (a 1 , b 1 )+(a 2 , b 2 ) (a 1 +a 2 , b 1 +b 2 ), (a 1 , b 1 )·(a 2 , b 2 ) (a 1 a 2 − b 1 b 2 , a 1 b 2 + a 2 b 1 ). Алгебра hC; +, ·i удовлетворяет всем аксиомам поля. Естественным образом определяются мономорфизмы, позволяющие вло- жить алгебру hN; +, ·i в алгебру hZ; +, ·i, алгебру hZ; +, ·i — в алгебру hQ; +, ·i, алгебру hQ; +, ·i — в алгебру hR; +, ·i, алгебру hR; +, ·i — в алгебру hC; +, ·i. Поэтому с точностью до изоморфизма можно считать, что каж- дая из этих алгебр является подалгеброй каждой из последующих алгебр и имеют место включения N ⊂ Z ⊂ Q ⊂ R ⊂ C. Приведенные конструкции позволяют проследить процесс образования числовых систем с помощью основных теоретико-множественных операций исходя из пустого множества. § 3.2. Системы счисления 1. Позиционные системы счисления В современных компьютерах любая информация представляется в ви- де двоичных кодов, т. е. упорядоченных наборов двух различных символов, которые обычно обозначаются через 0 и 1. В связи с этим часто прихо- дится использовать системы счисления, отличные от привычной десятичной системы счисления. При этом в основном используются позиционные систе- мы счисления, которые строятся по тем же принципам, что и десятичная система. 3.2. СИСТЕМЫ СЧИСЛЕНИЯ 83 Как показано в § 3.1, запись произвольного действительного чис- ла x (x > 0) в десятичной системе представляет собой перечисление всех коэффициентов разложения числа x по степеням числа 10: a k a k−1 . . . a 1 a 0 .a −1 a −2 . . . a −n . . . . На этих же принципах основаны и другие позиционные системы счис- ления с любым целым числом P (P > 1), которое называется основанием счисления. В каждой из этих систем используется P различных символов, называемых цифрами, для обозначения некоторых различных натуральных чисел, называемых базисными. В дальнейшем в качестве базисных прини- маются целые числа от 0 до P − 1. Запись произвольного числа x в системе счисления с основанием P так- же определяется разложением этого числа x по последовательным степеням числа P : b k P k + b k−1 P k−1 + . . . + b 1 P 1 + b 0 P 0 + b −1 P −1 + b −2 P −2 + . . . , где каждый коэффициент b i является одним из базисных чисел и обознается одной цифрой. Аналогично записи в десятичной системе число x в P -ичной системе изображается последовательностью своих коэффициентов с разде- лением целой и дробной частей с помощью точки: x = b k b k−1 . . . b 0 .b −1 b −2 . . . . Для указания используемой системы счисления будем основание системы (в ее десятичной записи) приводить в качестве нижнего индекса у записи числа, например 758 16 Арифметические операции над числами в любой P -ичной системе выпол- няются по тем же правилам, что и в десятичной, поскольку все они осно- вываются на правилах выполнения операций над соответствующими много- членами. При этом используются таблицы сложения и умножения, которые имеют место в системе счисления с данным основанием. 2. Двоичная система При P = 2 для записи чисел используются всего две цифры: 0 и 1. Пример 3.2.1. 23 10 = 1 · 2 4 + 0 · 2 3 + 1 · 2 2 + 1 · 2 1 + 1 · 2 0 = 10111 2 , 29 32 = 1 · 2 −1 + 1 · 2 −2 + 1 · 2 −3 + 0 · 2 −4 + 1 · 2 −5 = 0.11101 2 . ¤ 84 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Полезно запомнить запись в двоичной системе первых шестнадцати на- туральных чисел: 0 1 2 3 4 5 6 7 0000 0001 0010 0011 0100 0101 0110 0111 8 9 10 11 12 13 14 15 1000 1001 1010 1011 1100 1101 1110 1111 При выполнении арифметических операций над числами в двоичной системе используются следующие таблицы сложения и умножения: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10; 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1. Поскольку в этой системе для изображения чисел берутся только две цифры, для построения компьютера можно использовать элементы, име- ющие лишь два различных устойчивых состояния, одно из которых соот- ветствует цифре 0, а другое — цифре 1. При этом алгебраическая система с носителем, состоящим из двоичных кодов, изоморфна соответствующей алгебраической системе, элементы которой имеют десятичную запись. 3. Восьмеричная система В восьмеричной системе счисления используются цифры 0, 1, 2, 3, 4, 5, 6, 7. Запись числа основывается на его разложении по сте- пеням числа восемь с указанными коэффициентами. Пример 3.2.2. 215 10 = 192 + 16 + 7 = 3 · 8 2 + 2 · 8 1 + 7 · 8 0 = 327 8 , 30.25 10 = 3 · 8 1 + 6 · 8 0 + 2 · 8 −1 = 36.2 8 . ¤ 4. Шестнадцатеричная система В этой системе для записи базисных чисел от нуля до пятнадцати ис- пользуются следующие символы (цифры): от 0 до 9 — те же самые арабские цифры, а для следующих чисел — от десяти до пятнадцати — символы a, b, c, d, e, f . Пример 3.2.3. ae.8 16 = 10 · 16 + 14 + 8/16 = 160 + 14 + 0.5 = 174.5 10 . ¤ 3.2. СИСТЕМЫ СЧИСЛЕНИЯ 85 5. Смешанные системы счисления В некоторых случаях числа, заданные в системе счисления с основани- ем P , приходится изображать с помощью цифр системы с основанием Q (Q < P ). Такая необходимость возникает, например, когда в память машины, способной воспринимать только двоичные цифры, нужно ввести десятичные числа для их последующей переработки. В таких случаях используют сме- шанные системы счисления, в которых каждый коэффициент разложения числа по степеням P записывается в Q-ичной системе. Такая смешанная система называется Q-P -ичной. При этом для записи каждого из упомя- нутых выше коэффициентов используется одно и то же количество Q-ичных разрядов, минимально необходимое для записи любого из допустимых коэф- фициентов. Пример 3.2.4. Представим число 8903 10 в смешанной двоично- десятичной системе. Поскольку 8 10 = 1000 2 , 9 10 = 1001 2 , 3 10 = 0011 2 , имеем 8903 10 = 1000 1001 0000 0011 2−10 . ¤ Отметим, что запись в двоично-десятичной системе отличается от за- писи данного числа в двоичной системе счисления. Например, 8903 10 = = 10001011000111 2 , что отличается от записи этого же числа в смешанной двоично-десятичной системе. Особый интерес представляет случай, когда P = Q l (l ∈ ω). При этом запись любого числа в смешанной Q-P -ичной системе совпадает с записью этого числа в Q-ичной системе. Пример 3.2.5. Если P = 8, Q = 2 (8 = 2 3 ), то 2763 8 = 010 111 110 011 2−8 = 010 111 110 011 2 . ¤ Таким образом, запись числа в P -ичной системе счисления в случае P = Q l является просто сокращенной записью изображения этого же числа в Q-ичной системе: для такой сокращенной записи Q-ичные цифры в изоб- ражении числа объединяются вправо и влево от точки в группы по l раз- рядов (дополняя, в случае необходимости, нужное количество нулей справа и слева), и каждое число, представленное в Q-ичной системе этой группой разрядов, записывается одной P -ичной цифрой. Пример 3.2.6. 1011011011.111011 2 = 0010 1101 1011.1110 1100 2 = = 0010 1101 1011.1110 1100 2−16 = 2db.ea 16 . ¤ 86 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 6. Перевод чисел из одной системы счисления в другую В связи с использованием различных систем счисления возникает необхо- димость перевода чисел из одной системы в другую. Задача перевода состоит в следующем. Пусть известна запись числа x в системе счисления с основа- нием P : x = (p n p n−1 . . . p 0 .p −1 p −2 . . . p −k ) P , где p i — цифры P -ичной систе- мы. Требуется найти запись числа x в системе счисления с основанием Q: x = (q m q m−1 . . . q 0 .q −1 q −2 . . . q −1 ) Q , где q i — цифры Q-ичной системы. При этом можно ограничиться рассмотрением положительных чисел, поскольку перевод любого числа сводится к переводу его абсолютной величины с по- следующим приписыванием соответствующего знака. Для определенности будем считать, что в процессе перевода должны ис- пользоваться только средства P -ичной арифметики. В связи с этим необхо- димо рассмотреть перевод из Q-ичной системы в P -ичную (Q → P ) и из P - ичной в Q-ичную (P → Q). Перевод Q → P . Если известна запись числа x в Q-ичной системе x = (q m q m−1 . . . q 0 .q −1 q −2 . . . q −1 ) Q , перевод в P -ичную систему сводится к вы- числению значения многочлена x = q m Q m + q m−1 Q m−1 + . . . + q 0 + q −1 Q −1 + q −2 Q −2 + . . . + q −l Q −l , что следует из правил записи числа x в Q-ичной системе. Пример 3.2.7. Переведем число x = ba.8 16 в десятичную систему сред- ствами десятичной арифметики. Здесь Q = 16, P = 10. Имеем x = 11 · 16 + 10 + 8 · 16 −1 = 186.5 10 . ¤ Перевод P → Q. Рассмотрим перевод целых чисел и правильных дробей. В общем случае перевод любого числа сводится к независимому переводу его целой и дробной частей. Перевод целых чисел. Пусть дана запись целого числа N в системе счис- ления с основанием P . Поскольку N — целое число, его запись в Q-ичной системе будет иметь вид N = (q k q k−1 . . . q 0 ) Q , где q i (0 6 q i < Q) — иско- мые цифры Q-ичной системы. Эта запись является сокращенной записью многочлена N = q k Q k + q k−1 Q k−1 + . . . + q 0 3.2. СИСТЕМЫ СЧИСЛЕНИЯ 87 Для определения q 0 разделим обе части последнего равенства на Q: N/Q = q k Q k−1 + . . . + q 1 + q 0 /Q. Приравнивая между собой целые и дробные части в левой и правой частях (учитывая, что q i < Q), получим, что q 0 есть остаток от деления N на Q. Целочисленное частное от деления N на Q обозначим через N 1 Тогда N 1 = q k Q k−1 + . . . + q 1 . Поскольку N 1 есть целое число, к нему можно применить тот же прием для определения значения q 1 , которое равно остат- ку от деления N 1 на Q. Полученное при этом частное обозначим через N 2 и т. д. Этот процесс заканчивается, когда очередное частное окажется рав- ным нулю. Для окончательной записи числа N в Q-ичной системе нужно в соответствующем порядке записать коэффициенты q i , изображая каждый из них одной Q-ичной цифрой. Пример 3.2.8. 1. Переведем десятичное число N = 23 в двоичную систему средствами десятичной арифметики (P = 10, Q = 2): 23/2 = 11 + 1/2, q 0 = 1, N 1 = 11, 11/2 = 5 + 1/2, q 1 = 1, N 2 = 5, 5/2 = 2 + 1/2, q 2 = 1, N 3 = 2, 2/2 = 1 + 0/2, q 3 = 0, N 4 = 1, 1/2 = 0 + 1/2, q 4 = 1, N 5 = 0. Поскольку числа нуль и единица в каждой из этих систем обозначаются цифрами 0 и 1, то в процессе деления сразу получены искомые двоичные цифры: N = 10111 2 2. Переведем число N = 175 10 в шестнадцатеричную систему: 175/16 = 10 + 15/16, q 0 = 15, N 1 = 10, 10/16 = 0 + 10/16, q 1 = 10, N 2 = 0. Таким образом, N = 10 · 16 1 + 15 · 16 0 . Число 10 соответствует шестнадцате- ричной цифре a, число 15 — цифре f , следовательно, N = af 16 . ¤ Перевод дробных чисел. Пусть требуется перевести в P -ичную систему правильную дробь x (0 6 x < 1), заданную в ее P -ичной записи: x = 0.p −1 p −2 . . . p −k . Запись этого числа в Q-ичной системе будет иметь вид |