Лекция 7. Логические основы информатики

Итоги по теме: Системы счисления.

Деление

Умножение

Вычитание

Сложение

Таблица сложения в двоичной системе предельна проста, Так как 1 + 1 = 10, то при сложении столбиком в данном разряде остается 0, а 1 переносится в следующий разряд.

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

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

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

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

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

- Шестнадцатеричная система и двоичная , по сути дела, близнецы- братья , и в отличие от десятичной системы перевод чисел из одной в другую производится чрезвычайно просто- с использованием таблицы.

- Шестнадцатеричные числа необходимо рассматривать лишь как удобный для человека вариант “сворачивания ” реально существующих в компьютере двоичных чисел.

 

«Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, что­бы облегчить сам процесс нашего мышления» (Лейбниц).

Математика является наукой, в которой все утвер­ждения доказываются с помощью умозаключений, то есть путем использования законов человеческого мыш­ления. Изучение законов человеческого мышления яв­ляется предметом логики.

Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384-322 г. до н.э.)- Он систематизировал известные до него сведения, и эта система стала впоследствии называться формаль­ной или Аристотелевой логикой. Формальная логика просуществовала без серьезных изменений более двадцати столетий. Естественно, что развитие математики выявило недостаточность Аристо­телевой логики и потребовало дальнейшего ее развития.

Простейшие закономерности выводов открывались человечеством эмпи­рическим путем в ходе общественного производства (например, простей­шие соотношения арифметики и геометрии). Открытие более сложных законов связано с результатами науки формальной логики. Первое круп­ное обобщение формальной логики принадлежит Аристотелю. В фор­мальной логике с самого начала применялись (в единичных случаях) математические методы, но развитие логики не успевало за применением таких методов по сравнению с другими областями математики. Поэтому формальная логика отстала от потребностей науки (в первую очередь от требований математики); отставание оказалось особенно очевидным в новую эру.

Главными недостатками формальной логики являлись сле­дующие.

1. Она не сумела привести законы выводов к небольшому количеству надежных логических законов; поэтому подтвердила правильность не­которых выводов на основе экспериментов, которые позже были опро­вергнуты примерами, доказывающими обратное.

2. Она была неспособна анализировать значительную часть выводов, применяемых в повседневной и научной жизни; доказать правильность или неправильность таких выводов. (Например, не могла доказать, что из правильности предложения «Каждая трапеция является четырех­угольником» вытекает правильность предложения «Кто рисует трапецию, тот рисует четырехугольник).

Впервые в истории идеи о построении логики на математической основе была высказаны немецким ма­тематиком Г. Лейбницем (1646-1716) в конце XVII века. Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам. Это позволит всякое рассуждение заменить вычислением.

Первая реализация идеи Лейбница принадлежит английскому ученому Д. Булю (1815-1864). Он создал ал­гебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний. Введение символи­ческих обозначений в логику имело для этой науки такое же решающее значение, как и введение буквенных обо­значений для математики. Именно благодаря введению символов в логику была получена основа для создания новой науки - математической логики.

Применение математики к логике позволило пред­ставить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, малодоступных человеческому мышлению, и это, ко­нечно, расширило область логических исследований. К концу XIX столетия актуальное значение для мате­матики приобрели вопросы обоснования ее основных по­нятий и идей. Эти задачи имели логическую природу и, естественно, привели к дальнейшему развитию мате­матической логики. В этом отношении показательны работы немецкого математика Г. Фреге (1848-1925) и итальянского математика Д. Пеано (1858-1932), кото­рые применили математическую логику для обоснова­ния арифметики и теории множеств.

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

В аксиоматическом построении математической тео­рии предварительно выбирается некоторая система неоп­ределяемых понятий и отношения между ними. Эти по­нятия и отношения называются основными. Далее без доказательства принимаются основные положения рас­сматриваемой теории - аксиомы. Все дальнейшее содер­жание теории выводится логически из аксиом. Впервые аксиоматическое построение математической теории бы­ло предпринято Евклидом в построении геометрии.

Изложение этой теории в «Началах» Евклида не без­упречно. Евклид здесь пытается дать определение исход­ных понятий (точки, прямой, плоскости). В доказатель­стве теорем используются нигде явно не сформулирован­ные положения, которые считаются очевидными. Таким образом, в этом построении отсутствует необходимая логическая строгость, хотя истинность всех положений теории не вызывает сомнений.

Отметим, что такой подход к аксиоматическому пос­троению теории оставался единственным до XIX века. Большую роль в изменении такого подхода сыграли ра­боты Н. И. Лобачевского (1792-1856).

Лобачевский впервые в явном виде высказал убежде­ние в невозможности доказательства пятого постулата Ев­клида и подкрепил это убеждение созданием новой геомет­рии. Позже немецкий математик Ф. Клейн (1849-1925) доказал непротиворечивость геометрии Лобачевского, чем фактически была доказана и невозможность доказатель­ства пятого постулата Евклида.

Так возникли и были решены в работах Н. И. Лоба­чевского и Ф. Клейна впервые в истории математики про­блемы невозможности доказательства и непротиворечи­вости в аксиоматической теории.

Непротиворечивость аксиоматической теории явля­ется одним из основных требований, предъявляемых к системе аксиом данной теории. Она означает, что из дан­ной системы аксиом нельзя логическим путем вывести два противоречащих друг другу утверждения.

Доказательство непротиворечивости аксиоматических теорий можно осуществить различными методами. Одним из них является метод моделирования или интерпретаций. Здесь в качестве основных понятий и отношений выбира­ются элементы некоторого множества и отношения между ними, а затем проверяется, будут ли выполняться для выб­ранных понятий и отношений аксиомы данной теории, то есть строится модель для данной теории. Так, аналитичес­кая геометрия является арифметической интерпретацией геометрии Евклида. Ясно, что метод моделирования сво­дит вопрос о непротиворечивости одной теории к проблеме непротиворечивости другой теории.

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

Однако в конце XIX века в теории множеств были обнаружены противоречия (парадоксы теории мно­жеств). Ярким примером такого парадокса является парадокс Б. Рассела. Разобьем все мыслимые множества на два класса. Назовем множество «нормальным», если оно не содержит себя в качестве своего элемента и «не­нормальным» в противном случае. Например, множе­ство всех книг - «нормальное» множество, а множе­ство всех мыслимых вещей - «ненормальное» множе­ство.

Основным (неопределяемым) понятием математичес­кой логики является понятие «простого высказывания».

Под высказыванием обычно понимают всякое повество­вательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логически­ми значениями высказываний являются «истина» и «ложь».

Приведем примеры высказываний.

1) Новгород стоит на Волхове.

2) Париж - столица Англии.

3) Карась не рыба.

4) Число 6 делится на 2 и на 3.

5) Если юноша окончил среднюю школу, то он полу­чает аттестат зрелости.

Высказывания 1), 4), 5) истинны, а высказывания 2) и 3) ложны.

Очевидно, предложение «Да здравствуют наши спорт­смены!» не является высказыванием.

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

Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если ..., то ...», «тогда и только тогда», принято называть слож­ными или составными. Так, высказывание 3) получается из простого высказывания «Карась — рыба» с помощью отрицания «не», высказывание 4) образовано из элемен­тарных высказываний «Число 6 делится на 2», «Число 6 делится на 3», соединенных союзом «и». Высказывание 5) получается из простых высказываний «Юноша окончил среднюю школу», «Юноша получает аттестат зрелости» с помощью грамматической связки «если ., то ...». Ана­логично сложные высказывания могут быть получены из простых высказываний с помощью грамматических свя­зок «или», «тогда и только тогда».

В алгебре логики все высказывания рассматривают­ся только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истин­ным и ложным.

В дальнейшем будем элементарные высказывания обозначать малыми буквами латинского алфавита: х, у, z, .,., а, Ь, с, ...; истинное значение высказывания - бук­вой и или цифрой 1, а ложное значение - буквой л или цифрой 0.

Если высказывание а истинно, то будем писать а = 1, а если а ложно, то а = 0.