Системы счисления Системы счисления - это способы записи чисел в виде, удобном для прочтения и выполнения арифметических операций Рассматривая археологические находки эпохи палеолита, можно заметить, что люди стремились группировать точки, полосы, насечки по 3, 4, 5 или по 7. Такая группировка облегчала счет. В древности чаще всего считали на пальцах, и поэтому предметы стали группировать по 5 или по 10 Пальцевый счет сохранился кое-где и поныне. Историк и математик Л.Карпинский в книге "История арифметики" сообщает, что на крупнейшей мировой хлебной бирже в Чикаго предложения и запросы, как и цены, объявлялись маклерами на пальцах без единого слова

В дальнейшем десяток десятков получил свое название (сотня), десяток сотен свое и т.д. Если при пересчете оказывалось 2 сотни, 7 десятков и еще 4 предмета, то дважды повторяли знак для сотни, семь раз для десятка и 4 - знак для единицы. Знаки для единиц, десятков, сотен были непохожи друг на друга. При такой записи знаки можно было располагать в любой порядке, и значение записанного числа при этом не менялось. Подобные системы счисления стали называться непозиционными. Непозиционные системы счисления были более или менее пригодны для выполнения операций сложения или вычитания, но совсем не удобны для умножения и деления. Чтобы облегчить работу, применялись счетные доски абаки Непозиционными были системы счисления у древних египтян, греков, римлян и славян. Долгое время бытовала алфавитная форма записи. А ней каждый значок означал определенное число, при записи эти числа суммировались.

На Руси пользовались десятлличной алфавитной нумерацией, а чтобы не путать буквы с цифрами, над числами ставился особый значок - титло

1 000 тысяча тьма 10 e12 легион 10 e24 леодр 10 e48 ворон 10e 49 колода Для обозначения тысяч употреблялся другой знак, который ставился слева. Так можно было записывать числа от единицы до миллиона, а для больших чисел имелись свои обозначения. В русских арифметиках XVII века встречаются две системы их записи - "великого числа" и " малого числа ", в которой те же названия имеют совсем другие величины: тьма легион леодр

Римская пятерично-десятичная система использовала шесть букв алфавита, как числа-цифры, кратные пяти и еще одну - для обозначения единицы. Нуля в ней нет I V X L C D M Знаки в числе располагали по убыванию, от больших к меньшим и складывали. Меньшее число, стоящее перед большим из него вычитали. Для очень больших цифр значок М использовали как индекс, показывающий, сколько тысяч записано CLXVII M DXXXIV = ?

CLXVII M DXXXIV = Поступали и по иному: горизонтальная черта над цифрой показывала ее увеличение в тысячу раз _ X = двумя вертикальными боковыми чертами вместе с горизонтальной - в сто тысяч раз _ IVI = По свидетельству древнеримского историка Плиния-старшего, на главной римской площади Форуме была воздвигнута гигантская фигура двуликого бога Януса. Пальцами правой руки он изображал число 300, пальцами левой Вместе это составляло число дней в году в римском календаре

У древних вавилонян система счисления вначале была непозиционной, но в последствии они перешли к использованию записи, использующую порядок записи. При этом в отличии от используемой нами системы счисления, в которой значение цифры меняется в 10 раз при перемещении на одно место (такую систему называют десятлличной) у вавилонян при перемещении знака происходило изменение значение в 60 раз). Долгое время у вавилонян не было нуля, т.е. знака для пропущенного разряда. Следы вавилонской системы счисления сохранились до наших дней. (1 час - 60 мин, 1 мин с).

Индийские математики использовали десятичную систему. Сочетав с ней вавилонский метод обозначения чисел, индийцы создали в 6 веке способ записи использующий лишь 9 цифр. Вместо нуля оставляли пустое, а позднее стали ставить точку или маленький кружок. В 9 веке появился особый знак для нуля. Были выработаны правила выполнения арифметических операций, не требующих применения абака, и этот способ распространился по всему миру XII в

Такая система возникала около полутора тысяч лет назад, а в Европу пришла через мавров - арабов, завоевавших в средние века Пиренеи и юг Франции. Поэтому и сами цифры называются арабскими. Древнейшая известная рукопись с такими цифрами хранится в одном из монастырей на севере Испании и датируется 976 годом Мысль - выражать все числа немногими знаками, придавая им, кроме значения по форме, еще значение по месту, - настолько проста, что именно из-за ее простоты трудно оценить насколько она удивительна. Как нелегко прийти к этому, мы видим ясно на примере величайших гениев греческой учености - Архимеда и Аполония от которых эта мыль оказалась скрытой - писал выдающийся французский математик и астроном Лаплас

За основание системы счисления можно принять любое число p, большее 1. Для записи чисел в p - лличной системе счисления нужно p цифр. Число записанное цифрами a k, a k-1,, a 0 в p-лличной системе равно Например:

Если число записано в десятлличной системе, а его надо перевести в p-ичную систему, то делят это число на p с остатком. Потом делят на p с остатком неполное частное и т.д., пока не получится неполное частное равное нулю. Выписывая подряд все остатки, начиная с последнего, получим искомую запись нашего числа 327:2 = 163 остаток :16 = :2 = :16 = (E) 81:2 = :16 = 1 11 (B) 40:2 = :16 = :2 = :2 = 5 0 5:2 = 2 1 2:2 = 1 0 1:2 = = = 1BE7 16

Перевод дробной части производится следующим образом: x 2 = = x 2 = 0.5 = x 2 = = = x 16 = 3.48 = x 16 = 7.68 = x 16 = = 10 (A) x 16 = = 14 (E) x 16 = 1.28 = x 16 = 4.48 = = 0.37AE14 16

Операции над натуральными числами в p-лличной системе счисления выполняются в обычном порядке, с той лишь разницей, что для каждой системы счисления надо брать свои таблицы сложения и умножения. Особенно простой вид эти таблицы имеют для дволличной системы счисления 0+0 = 0 0x0=0 0+1 = 1 0x1=0 1+1 =10 1x1=1 Еще в 17 в. Немецкий математик Г.В.Лейбниц предложил перейти на двоичную систему счисления, но этому помешало то, что запись в дволличной форме очень длина При подготовке задач в дволличной системе для сокращения записи нередко пользуются восьмерлличной и шестнадцатерлличной системами счисления

Переход от этих систем к дволличной и обратно осуществляется очень просто каждый разряд восьмерлличной системы преобразуется в некоторое трехзначное двоичное число каждый разряд 16-ой системы преобразуется в 4-значное число = = Для перехода от дволличной записи к восьмерлличной нужно разбить двоичную запись на группы по три цифры справа налево и каждую группу заменить восьмеричным числом. Для перехода от дволличной к шестнадцатерлличной на группы по = = = = Простота указанных преобразований объясняется тем, что числа 8 и 16 являются целыми степенями двойки.

В ряде как теоретических, так и практических задач некоторые системы счисления, отличные от десятлличной, представляют известные преимущества. Двоичная система счисления для изображения одного и того же диапазона чисел требует меньшего числа элементов машины для их записи, чем десятичная Действительно количество чисел, имеющих n разрядов, в системе счисления с основание c равно n M = c Необходимое для представления этих чисел число элементов пропорционально N c = c*n Зафиксируем число M и найдем то c для которого N c достигает минимума Из первого равенства находим, что n = ln(M)/ ln(c)

Подставив это значение в выражение для N c, находим N c = c*ln(M)/ln(c) Легко найти, что минимум этого выражения достигается при c=e=2, С рассматриваемой точки зрения самой выгодной системой счисления является троичная. 6 Для изображения всех чисел от 1 до 10 в десятлличной системе требуется 60 элементов (6 позиций по 10 знаков), в дволличной 40, в тролличной 38. Однако увеличение числа элементов для записи чисел в дволличной системе по сравнению с тролличной невелико. Если число элементов, необходимое для записи в дволличной системе, обозначить N 2, а для записи в тролличной N 3, то N 2 /N 3 = 2*ln(3)/(3*ln(2))= = 2*lg 10 (3)/(3*lg 10 (2)) ~ 1,056

Троичная система не получила широкого применения в цифровых машинах в связи с трудностями конструирования достаточно надежных быстродействующих элементов с тремя устойчивыми состояниями В Советском Союзе была создана и несколько лет успешно работала троичная машина. Речь идет об ЭВМ «Сетунь», разработка которой завершилась в 1959 году в стенах МГУ. Ее главный конструктор Николай Петрович Брусенцов

Логические операции Применение дволличной системы счисления дает возможность использовать аппарат математической логики, в частности исчисление высказываний. В математической логике под высказыванием понимается любое предложение, относительно которого имеет смысл говорить об его истинности или ложности. Предложения которые могут быть одновременно истинными и ложными или частично истинными, в математической логике не рассматриваются. При оценке высказываний мы будем принимать во внимание лишь их истинность или ложность, никак не учитывая их конкретного содержания Высказывания будем обозначать заглавными буквами латинского алфавита. Если A истинно, то будем писать A=1, если ложно A=0

Математическая логика изучает вопросы представления и преобразования двоичных функций от двоичных аргументов посредством некоторых логических операций, называемыми логическими связями Из простых выражений посредством логических связей могут быть составлены сложные высказывания, принимающие значения истинно (1) или ложно (0) в зависимости от значения составляющих простых высказываний Так как высказывания можно рассматривать как двоичные переменные, то логические связи между высказываниями можно представить как операции над двоичными переменными величинами Определим основные логические операции

1. Отрицание (унарная) _ А - читается не A результат Отрицание высказывания А является высказывание, которое ложно, когда А истинно, и истинно, когда А ложно

2. Логическое умножение А B - читается A и B результат 0 0 = = = = 1 Операция логического умножения называется конъюнкцией, или логическим И. Конъюнкция двух высказываний представляет собой сложное высказывание, которое истинно тогда и только тогда, когда истинны оба составляющих его высказывания.

3. Логическое сложение А B - читается A и B результат 0 0 = = = = 1 Операция логического сложения называется дизъюнкцией, или логическим ИЛИ. Дизъюнкция двух высказываний представляет собой сложное высказывание, которое ложно, тогда и только тогда, когда оба слагаемых ложно

4. Равнозначность А B - читается A равнозначно B результат 0 0 = = = = 1 Равнозначность двух высказываний представляет собой сложное высказывание, которое истинно, когда оба его составляющих имеют одинаковой значение истинности и ложна в противоположном случае

5. Сложение по модулю 2 А B - читается A равнозначно B результат 0 0 = = = = 0 Операция сложения по модулю 2 выражается через операции равнозначности и отрицания по формуле _____ A B = A B

Проверить следующие формулы (вместо звездочки произвольная операция). Проверка осуществляется подстановкой переменных значений 0 или 1 в различных комбинациях и применением таблиц, определяющих эти операции A * B = B *A Коммутативность (A * B) * C = A *(B*C) Ассоциативность A (B C) = ( A B ) (A C) В исчислении высказываний доказывается, что любое сложное высказывание может быть построено из простых при помощи операций отрицания, логического умножения и логического сложения