Как и почему появился язык математической логики.

Приведем описание поля деятельности современной математики: «Математика изучает объекты, свойства которых точно сформулированы». Хотя само описание говорит о точных формулировках, в нем требуют уточнения, прежде всего, слова «точно сформулированы», затем «объекты» и «свойства».

Итак, какие же формулировки можно считать точными? Например, предложение «Он встретил её на поляне с цветами» имеет три различных истолкования.

Пытаясь застраховаться от такой неоднозначности, математики с самого начала стремились формулировать теоремы и доказательства на как можно более четком, хотя и бедном, диалекте естественного языка. Словарный запас этого диалекта постоянно расширяется, но основные формы предложений, связки, союзы остаются практически теми же, что были выработаны еще в античные времена. Долгое время считалось, что математический диалект состоит из строго сформулированных предложений. Но уже в средние века развитие алгебры привело к тому, что формулировки теорем часто становились всё длиннее и неудобнее. Соответственно, доказательства становились труднее.

Выход был найден, когда заметили, что часть математического языка может быть заменена несколькими условными знаками. Например, предложение «Квадрат первого, сложенный с квадратом второго и удвоенным произведением первого на второе, равен квадрату суммы первого со вторым» записывается кратко х²+2ху+у²=(х+у)². Это стало первым этапом уточнения математического языка: был создан символизм арифметических выражений, их равенств и неравенств. Однако более сложные математические утверждения все еще записывались на обычном языке с включениями формул.

Язык[1] математической логики[2], ставший символическим языком современной математики, возник в тот момент, когда неудобство математического языка для нужд математики было окончательно осознано. Новый символизм, также как и символизм алгебраических выражений, прояснил механическую природу многих преобразований и позволил дать простые алгоритмы их осуществления. Вместе с тем появилась возможность строго ответить на вопрос: «Что есть точно сформулированное высказывание?» Это высказывание, которое может быть однозначно переведено на символический язык математики.

К чему привело появление языка математической логики. Прежде всего, это привело к появлению алгебры логики[3]. Частным случаем алгебры логики является Булева алгебра[4]. В алгебре Буля область определения функции и область значений переменных ограничиваются 0 и 1. То есть любая переменная, и любая функция в булевой алгебре могут принимать только 2 значения: 0 или 1, что трактуется как «ложь» или «истина», соответственно.

Как мы знаем из истории становления и развития информатики, появлению компьютеров способствовало развитие математики (в области создания счетных машин) и физики (в области применения электромагнетизма). Алгебра Буля наилучшим образом объединила физику и математику. С одной стороны, 0 и 1 представляют алфавит двоичной системы счисления, с помощью которой можно выразить любое число и даже слово. А с другой стороны, те же 0 и 1 обозначают отсутствие или наличие тока в сети, направление магнитного поля в магнетиках, используемых в качестве материала, из которых изготавливают запоминающие устройства компьютеров и так далее.

В итоге язык математической логики определил направление развития информатики в области создания ЭВМ, а развитие физики и электротехники способствовало появлению современных компьютеров.

Так, например, американский логик Чарльз Сандерс Пирс первым осознал, что бинарная логика имеет сходство с работой электрических переключательных[5] (контактных) схем.

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

Таким образом, изучение алгебры логики и различных систем счисления является основой изучения науки информатики.

Система счисления

1.1 Классификация систем счисления

Система счисления– это способ представления чисел и совокупность приемов и привил, по которым числа записываются и читаются.

Существуют непозиционные и позиционные системы счисления.

В непозиционных системах счислениязначение цифры не зависит от её позиции в записи числа.

Примером может служить римская система: В числе X X X (тридцать) вес цифры X в любой позиции просто равен десяти.

В позиционных системах счислениявес каждой цифры изменяется в зависимости от её положения (позиции) в последовательности цифр в числе.

Например, в числе 333 (триста тридцать три) вес цифры 3 изменяется от её позиции. Если смотреть слева на право, то первая 3 стоит в позиции сотен и означает триста, вторая 3 – в позиции десятков и означает тридцать, а третья 3 находится в позиции единиц и означает просто три. Так 333 можно представить выражением:

300+30+3=3ž10²+3ž10¹+3ž10⁰

В дальнейшем мы будем работать с позиционными системами счисления.

Любая позиционная система счисления характеризуется своим основанием, т.е. количеством различных цифр, используемых для изображения чисел в данной системе счисления.

Возможно бесчисленное множество позиционных систем, т.к. за основание системы можно принять любое натуральное число - два, три, четыре, десять, шестнадцать, тридцать два, сорок и т.д. Название системы будет зависеть от основания.

Например, десятичная система счисления имеет основание десять (q=10) и для записи чисел используются десять цифр (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). Основание два (q=2) – система двоичная (0, 1), основание восемь (q=8) – система восьмеричная (0, 1, 2, 3, 4, 5, 6, 7) и т.д.

Однако, начиная с одинадцатиричной системы, где q=11 число 10 (где 1 относится уже к первому разряду, а 0 к нулевому) и цифра 10 изображаются одинаково, а имеют разный вес в системе. Для того чтобы не было путаницы, такие цифры заменяют буквами латинского алфавита по возрастанию.

Например:

а) Двенадцатеричная система – q=12

Используются цифры – 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 следовательно две последние цифры заменяем буквами, т.е. будем иметь ряд цифр и букв:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B.

Число в двенадцатеричной системе будет записываться следующим образом, например, 1A23, B12

б) Шестнадцатеричная система – q=16

Используются цифры – 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 после замены буквами будем иметь ряд цифр и букв:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Представление числа в шестнадцатеричной системе – FFA12, 1DB8

Множество всех символов (цифр и букв), используемых для записи чисел в данной системе счисления – называется алфавитом системы счисления.

Таблица 1.1

Алфавиты систем счисления

1.2 Понятие базиса системы счисления

Разряды числа указывают на позицию цифр в этом числе. Старшинство разрядов считается справа налево.

3 3 3

Рис. 1.1 Представление разрядов в позиции цифр числа

Значение числа складывается как сумма цифр, составляющих число, умноженное на основание q системы в степени, обозначающей номер позиции этой цифры в числе.

Запись чисел в любой из систем счисления с основанием q можно представить в следующем виде:

, (1)

где - число в q-ичной системе счисления; - цифры системы счисления; и - число целых и дробных разрядов, соответственно.

Например:

Число в двоичной системе счисления 1101,11; q=2.

Число в восьмеричной системе счисления 672,721; q=8.

Последовательность степеней основания называютбазисом системы счисления.

«Разложить число по базису системы счисления» - т.е. представить число в развернутой форме.

Например:

101,01₂ = 1 • 2² + 0 • 2¹ +1 • 2⁰ + 0 • 2^¯1+ 1 • 2^¯2;

673,2₈ = 6ž8² + 7ž8¹+3ž8⁰ + 2ž8_¯¹;

15FС₁₆ = 1ž16³+5ž16²+ Fž16¹ + Сž16⁰=

= 1ž16³+5ž16²+15ž16¹+12ž16⁰.

1.3 Перевод чисел из любой системы счисления
в десятичную систему

Представление чисел в развернутой форме одновременно является способом перевода чисел в десятичную систему из любой другой позиционной системы счисления. Достаточно подсчитать результат по правилам десятичной арифметики.

Например:

101,01₂=1ž2²+0ž2¹+1ž2⁰+0ž2_¯¹+1ž2_¯² =4 + 1 + 1/4= 5,25₁₀

673,2₈=6ž8²+7ž8¹+3ž8⁰+2ž8_¯¹= 384+56+3+2ž1/8 =443,25₁₀

15FС₁₆= 1ž16³ +5ž16² + 15ž16¹ + 12ž16⁰ = 5628₁₀

Например: Найдем сумму чисел в десятичной системе счисления

111₂ +111₈ +111₁₆.

1) 111₂ = 1 • 2² +1 • 2¹ + 1 • 2⁰ = 4 + 2 + 1 = 7₁₀;

2) 111₈ = 1 • 8² +1 • 8¹ +1 • 8⁰ = 64 + 8 +1 = 73₁₀;

3) 111₁₆ = 1ž16²+1ž16¹ +1ž16⁰ =256+16+1 = 273₁₀.

В результате получим:

111₂ +111₈ +111₁₆ = 7 + 73 + 273 = 353₁₀.

1.4 Перевод десятичных целых чисел в другие системы счисления (метод поэтапного деления)

Для перевода целого десятичного числа N в систему счисления с основанием q необходимо:

1. Разделить с остатком (“нацело”) число N на q.
Полученный остаток дает цифру, стоящую в нулевом разряде q-ичной записи числа N.

2. Полученное частное снова разделить на q и снова запомнить полученный остаток - это цифра первого разряда, и т.д.

3. Такое последовательное деление продолжается до тех пор, пока частное не станет меньше q.

4. Представлением числа N в новой системе счисления будет последовательность остатков деления, записанных в порядке, обратном порядку их получения. Если деление числа, осуществлять методом столбика, тогда цифрами искомого числа являются остатки от деления, выписанные слева направо начиная с последнего полученного остатка.

Например: 12₁₀ ® ?₂ 12₁₀ ® ?₈ 79₁₀ ® ?₁₆

т.к. 15 – это F, то

12₁₀ ® 1100₂ 12₁₀ ® 14₈ 79₁₀ ® 4F₁₆

1.5 Алгоритм разложения числа по базису новой системы счисления (метод разностей)

Для быстрого перевода десятичного числа в двоичный код (битовый, байтовый формат) можно использовать метод разностей

Таблица 1.2

Соответствие степени и разряда

1. Найти по таблице 1.2 степень новой системы, ближайшую по величине к исходному числу, но не больше исходного числа - это будет первый член суммы.

2. Найти разность между исходным числом и степенью.

3. Найти по таблице степень, ближайшую к разности, - это второй член суммы.

4. Найти разность между числом, из которого выделяли степень, и степенью.

5. Так поступать, пока разность не станет равной числу, входящему в алфавит искомой системы.

Например:

а) Переведем 45₁₀ с помощью таблицы в двоичную систему.

1) Число 45 находится в интервале 64(2⁶)>45>32(2⁵), следовательно, первый член суммы будет 32 и максимальный номер разряда будет 5, а бит числа 1.

2) Найдем разность 45-32=13, а 16(2⁴)>13>8(2³), тогда при четвертом разряде бит числа будет равен 0, а при третьем – 1.

3) Теперь 45-32-8=5, где 8(2³)>5>4(2²), следовательно, при разряде 2 бит числа будет равен 1.

4) 45-32-8-4=1, тогда при разряде 0 бит числа будет 1.

Номера разрядов
Десятичное число
							45
биты числа

Ответ: 45₁₀ = 101101₂

б)Перевести число 101₁₀ в двоичную систему счисления.

101₁₀ = 64₁₀ + 32₁₀ + 4₁₀+1₁₀ = 1100101₂

1.6 Связь между двоичной, восьмеричной и
шестнадцатеричной системами счисления