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

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

 

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

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

Как самостоятельная  наука логика оформилась в трудах греческого философа Аристотеля (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.

Логические операции над высказываниями.

1. Отрицание.

Отрицанием  высказывания х называется новое высказывание, которое является истинный, если высказывание х ложно, и ложным, если высказывание x истинно. Отрицание высказывания х обозначается   и читается «не х» или «неверно, что х».

Логические значения высказывания х можно описать с помощью таблицы:

x
0	1
1	0

Таблицы такого вида принято называть таблицами истинности.

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

2. Конъюнкция (логическое умножение).

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

Конъюнкция  высказываний х, у обозначается символом х&у или (х у), читается «x и у». Высказывания х, у называются членами конъюнкции.

Логические значения конъюнкции описываются  следующей таблицей истинности:

x	y	х&у
0	0	0
1	0	0
0	1	0
1	1	1

 

Например, для высказываний «6 делится  на 2», «б делится на 3» их конъюнкцией будет высказывание «б делится на 2 и 6 делится на 3», которое, очевидно, истинно.

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

Из определения операции конъюнкции и отрицания ясно, что высказывание x& всегда ложно.

3. Дизъюнкция (логическое сложение).

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

Дизъюнкция высказываний х, у обозначается символом x y, читается «x или у». Высказывания х, у называются членами дизъюнкции.

Логические значения дизъюнкции описываются  следующей таблицей истинности:

х		y
1	1			1
1	0			1
0	1			1
0	0			0