Математическая логика

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

Фундаментом науки о вычислительных машинах является конструктивная математика, в основе которой лежит математическая логика и теория алгоритмов с их однозначностью в оценке суждений и процедур вывода. Для описания элементов и узлов ЭВМ с самого начала использовалась математическая логика, а для описания компьютерных программ - теория алгоритмов.

Математическая логика - это дисциплина, изучающая технику математических доказательств. Отличие математических суждений от обычных разговорных высказываний состоит в том, что математические суждения всегда предполагают однозначную интерпретацию, в то время как наши обычные высказывания зачастую допускают многозначную трактовку.

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

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

Существуют следующие системы счисления информации:

Двоичная система счисления. В этой системе всего две цифры - 0 и 1. Особую роль здесь играет число 2 и его степени: 2, 4, 8 и т.д. Самая правая цифра числа показывает число единиц, следующая цифра - число двоек, следующая - число четверок и т.д. Двоичная система счисления позволяет закодировать любое натуральное число - представить его в виде последовательности нулей и единиц. В двоичном виде можно представлять не только числа, но и любую другую информацию: тексты, картинки, фильмы и аудиозаписи.

Десятичная система счисления. В этой системе 10 цифр: от 0 до 9, но информацию несет не только цифра, но и место, на котором цифра стоит. В десятичной системе счисления особую роль играют число 10 и его степени: 10, 100, 1000 и т.д. Самая правая цифра числа показывает число единиц, вторая справа - число десятков, следующая - число сотен и т.д.

Восьмеричная система счисления. В этой системе счисления 8 цифр: от 0 до 7. Цифра 1, указанная в самом младшем разряде, означает - как и в десятичном числе - просто единицу. Та же цифра 1 в следующем разряде означает 8, в следующем 64 и т.д. Число 100 (восьмеричное) есть не что иное, как 64 (десятичное).

Шестнадцатеричная система счисления. Запись числа в восьмеричной системе счисления достаточно компактна, но еще компактнее она получается в шестнадцатеричной системе. В качестве первых 10 из 16 шестнадцатеричных цифр взяты привычные цифры от 0 до 9, а вот в качестве остальных 6 цифр используют первые буквы латинского алфавита: A, B, C, D, E, F. Цифра 1, записанная в самом младшем разряде, означат просто единицу. Та же цифра 1 в следующем - 16 (десятичное), в следующем - 256 (десятичное) и т.д. Цифра F, указанная в самом младшем разряде, означает 15 (десятичное).

Существуют позиционные и непозиционные системы счисления. В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа.

Любая позиционная система счисления характеризуется своим основанием.

Основание позиционной системы счисления - это количество различных знаков или символов, используемых для изображения цифр в данной системе. За основание системы можно принять любое натуральное число – 2, 3, 4 и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д.

В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д.

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

Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления. Эта система имеет преимущества перед другими системами: двоичная арифметика намного проще десятичной; возможно применение аппарата булевой алгебры для выполнения логических преобразований информации.

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

Закон в логике понимается как требование или принцип, которому необходимо следовать, чтобы мышление было правильным. Из многих возможных требований были выделены те, которые наиболее тесно связаны с такими свойствами мышления, как последовательность, определенность, непротиворечивость и обоснованность: закон тождества, закон непротиворечия, закон исключенного третьего, закон достаточного основания. Рассмотрим каждый из них более подробно.

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

А = А                            – закон тождества

2. Закон непротиворечия. Два противоположных суждения не могут быть одновременно истинны: по крайней мере одно из них ложно.

А & = 0              – закон непротиворечия

3. Закон исключенного третьего. Истинно либо суждение, либо его отрицание ("третьего не дано").

A  = 1              – закон исключенного третьего

4. Закон достаточных оснований. Для истинности всякой мысли должно быть достаточно оснований, т.е. умозаключение необходимо обосновать исходя из суждений, истинность которых уже доказана.

= А              – закон достаточных оснований

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

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

1. Логическое умножение (логическое произведение, конъюнкция) в формулах используется: ^, &, и.

А и В = А^B - высказывание истинно только тогда, когда А и В оба истинны и ложно - во всех остальных случаях.

2. Логическое сложение (дизъюнкция) в формулах используется: v + ИЛИ. А и В (А v В) - высказывание ложно тогда и только тогда, когда составляющие его высказывания - ложные, и истинные во всех остальных случаях.

3. Логическое отрицание (инверсия).

(не А) - означает высказывание, которое истинно, когда А - ложно и ложно, - когда истинно: =1 =0.

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

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

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

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

Прямой код складывается из знакового разряда (старшего) и собственно числа. Знаковый разряд имеет значение

0 – для положительных чисел;

1 – для отрицательных чисел.

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

Дополнительный код образуется из обратного кода добавлением 1 к младшему разряду.

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

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

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

Логическое следование (импликация) - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)– следствием из этого условия. Результатом импликации является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом  "следовательно"  и  выражается словами ЕСЛИ … , ТО …