Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
a 2 d 2 = a 2 c 2 + a 2 d 1 , b 2 c 1 + b 2 d 2 = b 2 c 2 + b 2 d 1 . Складывая эти четыре равенства, после приведения подобных и деления пополам получаем искомое равенство. ¤ В дальнейшем носитель алгебры N будет также обозначаться через N. Определим фактор-алгебру A = hN 2 / ∼; +, ·i. Лемма 3.1.3. Алгебра A является коммутативным ассоциативным кольцом с единицей. Доказательство. Проверка законов ассоциативности, коммутативно- сти и дистрибутивности для операций сложения и умножения осуществля- ется непосредственно. Нулевым элементом в A является класс ∼ (0, 0), еди- ничным элементом — ∼ (1, 0). Для произвольного элемента α = ∼ (a, b) про- тивоположный элемент −α равен ∼ (b, a). ¤ Множество N 2 / ∼ разобьем на три части: 1) {∼ (a, b) | a > b}, 2) {∼ (a, b) | a = b}, 3) {∼ (a, b) | a < b}. В первом случае класс ∼ (a, b) содер- жит пару (k, 0), где a = b + k. Такие классы можно интерпретировать как положительные натуральные числа k = ∼ (k, 0). Второе множество содер- жит всего один класс, который играет роль нуля в A: 0 = ∼ (0, 0). Каждый класс ∼ (a, b) из третьего множества содержит пару (0, k), где b = a + k. Эти классы интерпретируются как отрицательные числа: −k ∼ (0, k). Введен- ные обозначения позволяют рассматривать алгебру A как кольцо целых чи- сел h{. . . , −n, . . . , −2, −1, 0, 1, 2, . . . , n, . . .}; +, ·i, которое в дальнейшем будем обозначать через hZ; +, ·i или просто Z. При этом ∼-классы будем называть целыми числами. 82 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 3. Поле рациональных чисел Рассмотрим множество Z × (N \ {0}). Пару (m, n) из этого множества можно представить в виде дроби m n . Если рассматривать дроби как раци- ональные числа, то некоторые из них считаются равными, например 1 2 и 2 4 , хотя записываются они по-разному. Чтобы отождествить эти записи, определим отношение эквивалентности ∼ следующим образом: (m 1 , n 1 ) ∼ (m 2 , n 2 ) ⇔ m 1 · n 2 = m 2 · n 1 . Классы эквивалентности по отношению ∼ называются рациональными числами, а множество всех классов эквивалентности образует множество рациональных чисел Q = ¡ Z × (N \ {0}) ¢ / ∼. Рассмотрим алгебру B = hZ × (N \ {0}); +, ·i, в которой операции сложе- ния и умножения определены так: (m 1 , n 1 ) + (m 2 , n 2 ) (m 1 · n 2 + m 2 · n 1 , n 1 · n 2 ), (m 1 , n 1 ) · (m 2 , n 2 ) (m 1 · m 2 , n 1 · n 2 ) для любых (m 1 , n 1 ), (m 2 , n 2 ) ∈ Z × (N \ {0}). Эти операции можно представ- лять и виде сложения и умножения дробей. Проверим, что отношение ∼ согласовано с операциями алгебры B. Лемма 3.1.4. Отношение ∼ является конгруэнцией на алгебре B. Доказательство. Пусть (m 1 , n 1 ), (m 2 , n 2 ), (m 0 1 , n 0 1 ), (m 0 2 , n 0 2 ) — пары из Z × (N \ {0}) с условиями (m 1 , n 1 ) ∼ (m 0 1 , n 0 1 ) и (m 2 , n 2 ) ∼ (m 0 2 , n 0 2 ). (3.2) Требуется доказать, что: 1) ((m 1 , n 1 ) + (m 2 , n 2 )) ∼ ((m 0 1 , n 0 1 ) + (m 0 2 , n 0 2 )); 2) ((m 1 , n 1 ) · (m 2 , n 2 )) ∼ ((m 0 1 , n 0 1 ) · (m 0 2 , n 0 2 )). Для проверки свойства 1 имеем (m 1 , n 1 ) + (m 2 , n 2 ) = (m 1 · n 2 + m 2 · n 1 , n 1 · n 2 ), (m 0 1 , n 0 1 ) + (m 0 2 , n 0 2 ) = (m 0 1 · n 0 2 + m 0 2 · n 0 1 , n 0 1 · n 0 2 ). 3.1. БЕСКОНЕЧНЫЕ ЧИСЛОВЫЕ СИСТЕМЫ 83 Нужно установить, что (m 1 · n 2 + m 2 · n 1 ) · (n 0 1 · n 0 2 ) = (m 0 1 · n 0 2 + m 0 2 · n 0 1 ) · (n 1 · n 2 ). (3.3) Зная из (3.2), что m 1 · n 0 1 = m 0 1 · n 1 и m 2 · n 0 2 = m 0 2 · n 2 , (3.4) имеем (m 1 · n 2 + m 2 · n 1 ) · (n 0 1 · n 0 2 ) = (m 1 · n 2 ) · (n 0 1 · n 0 2 ) + (m 2 · n 1 ) · (n 0 1 · n 0 2 ) = = (m 1 · n 0 1 ) · (n 2 · n 0 2 ) + (m 2 · n 0 2 ) · (n 1 · n 0 1 ) = {в силу (3.4)} = = (m 0 1 · n 1 ) · (n 2 · n 0 2 ) + (m 0 2 · n 2 ) · (n 1 · n 0 1 ) = = (m 0 1 · n 0 2 ) · (n 1 · n 2 ) + (m 0 2 · n 0 1 ) · (n 1 · n 2 ) = ((m 0 1 · n 0 2 ) + (m 0 2 · n 0 1 )) · (n 1 · n 2 ), и тем самым равенство (3.3) установлено. Проверка свойства 2 проводится аналогично и оставляется читателю в ка- честве упражнения. ¤ Таким образом, отношение ∼ — конгруэнция, и фактор-алгебра B/ ∼ образует множество рациональных чисел Q с обычными операциями сложе- ния и умножения: B/ ∼ = hQ; +, ·i. В полученной алгебре выполняются все аксиомы поля. Нулевым рациональным числом является класс ∼ (0, 1), еди- ницей — класс ∼ (1, 1), числом, противоположным числу ∼ (m, n), является число −(∼ (m, n)) ∼ (−m, n), обратным ненулевому числу ∼ (m, n) — чис- ло (∼ (m, n)) −1 ∼ (±n, ±m), где знак плюс берется при m > 0 и минус — при m < 0. 4. Поле действительных чисел Последовательность (x n ) n∈ω рациональных чисел называется фундамен- тальной, если для любого рационального числа ε > 0 существует такое n 0 , что |x p −x q | < ε для всех p и q, больших n 0 . Фундаментальные последователь- ности (x n ) n∈ω и (y n ) n∈ω называются эквивалентными: (x n ) ∼ (y n ), если для любого рационального числа ε > 0 существует такое n 0 , что |x p − y q | < ε для всех p и q, больших n 0 . Классы эквивалентности фундаментальных после- довательностей ∼ (x n ) называются действительными или вещественными 84 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ числами. Таким образом, множество R действительных чисел является фактор-множеством X/ ∼, где X = {(x n ) | (x n ) — фундаментальная последовательность}. На множестве R определим основные арифметические операции. Для этого рассмотрим алгебру X = hX; +, ·i со следующими операциями: (x n ) + (y n ) (x n + y n ), (x n ) · (y n ) (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 назы- вается периодом дроби. 3.2. СИСТЕМЫ СЧИСЛЕНИЯ 85 Предложение 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. В связи с этим часто прихо- дится использовать системы счисления, отличные от привычной десятичной системы счисления. При этом в основном используются позиционные систе- мы счисления, которые строятся по тем же принципам, что и десятичная система. 86 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Как показано в § 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 . ¤ 3.2. СИСТЕМЫ СЧИСЛЕНИЯ 87 Полезно запомнить запись в двоичной системе первых шестнадцати на- туральных чисел: 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 |