Методичка

3

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

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

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

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

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

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

Именно общая теория алгоритмов показала, что есть задачи неразрешимые ни при каком увеличении мощности вычислительных средств. А её бурно развивающаяся ветвь - теория сложности вычислений постепенно приводит к пониманию того, что бывают задачи разрешимые, но объективносложные, причём сложность их может оказаться в некотором смысле абсолютной, т.е. практически недоступной для современных ЭВМ.

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

5

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

В данном курсе ставились следующие задачи:

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

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

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

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

В результате освоения данного курса студент на основе ясного понимания соответствующих теоретических разделов должен уметь:

- реализовывать простейший вид логического преобразования информации при помощи логических функций;

- выделять в доказательных рассуждениях естественного языка логическую структуру, строить схемы формальных доказательств и проверять их правильность;

- знать меру сложности алгоритмов.

1.2Логические представления

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

Способы (правила) формального представления высказываний, построения новых высказываний из имеющихся с помощью логически правильных преобразований, а также способы (методы) установления истинности или ложности высказываний изучаются в математической логике. Современная математическая логика включает два основных раздела: логику высказываний и охватывающую ее логику предикатов (рис. 1.1). Для построения логики высказываний и логики предикатов существуют два подхода (метода), которые образуют два варианта моделей логики: алгебру логики и логические исчисления. Между основными понятиями этих методов формальной логики имеет место взаимно однозначное соответствие. Их изоморфизм обеспечивается в конечном итоге единством законов логики,

6

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

Формальные модели в виде исчисления высказываний и исчисления предикатов широко используются в математике и в искусственном интеллекте. Аксиоматический метод впервые был использован Евклидом при изложении геометрии. Позднее этот метод был использован Н.И. Лобачевским при создании неевклидовой геометрии.

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

Рис.1.1 Способы построения логики.

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

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

Основными объектами традиционных разделов логики являются высказывания.

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

7

Примеры высказываний: "Дважды два - четыре", "Мы живем в XXI веке", "Рубль - российская валюта", "Алеша - брат Олега", "Операции объединения, пересечения и дополнения являются операциями над множествами", "Человек смертен", "От перестановки мест слагаемых сумма не меняется", "Сегодня понедельник", "Если идет дождь, вам следует взять зонт".

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

1.3История развитая математической логики

Термин «логика» происходит от греческого слова "логос", что с одной стороны означает "слово" или "изложение", а с другой мышление. В толковом словаре Ожегова С.И. сказано: "Логика наука о законах мышления и его формах". Мышление представляет собой сложный и многогранный процесс, происходящий как на сознательном, так и подсознательном уровнях. Логика и интуиция – два неразрывно связанных между собой свойства человеческого мышления. Логическое (дедуктивное) мышление от истинных посылок всегда приводит к истинному выводу, не опираясь при этом на опыт, интуицию и другие внешние факторы. Показательны в этом отношении слова математика 20 века А. Пуанкаре: «Таким образом, логика и интуиция играют каждая свою необходимую роль. Обе они неизбежны. Логика, которая одна может дать достоверность, есть орудие доказательства; интуиция есть орудие изобретательства» [9].

Логика как наука сформировалась в 4 в. до н.э. Ее создал греческий ученый Аристотель (384-322 гг. до н.э.). Он впервые попытался разработать теорию дедукции, т.е. теорию логического вывода. Именно он формализовал логические высказывания и обратил внимание на то, что в рассуждениях мы можем из одних утверждений выводить другие, исходя не из их конкретного смысла, а из определенной взаимосвязи между их формами и структурами. В течение многих веков логика совсем не развивалась. Это свидетельствует о гениальности Аристотеля, которому удалось создать столь полную научную систему, в которой, казалось, ничего «не убавить, не прибавить».

Другой древнегреческий математик Евклид (330-275 гг. до н.э.) впервые предпринял попытку изложить основы геометрии как аксиоматической теории и впервые на практике реализовал идеи аксиоматической организации всякого научного знания. Он впервые подошел к осознанию всей математики, как совокупности аксиоматических теорий.

8

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

Только в середине 19 века ирландский математик Джордж Буль (18151864) воплотил идею Лейбница в жизнь. В работе « Математический анализ логики» (1847) он применил к логике алгебраические методы и модели. Им был создан аппарат современной математической логики. В 1854 году им была написана работа "Исследование законов мышления" (Investigation the laws of thought), которая заложила основы алгебры логики, где действуют законы, схожие с законами обычной алгебры, но буквами обозначаются не числа, а высказывания. На языке булевой алгебры можно описать рассуждения

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

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

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

Большой вклад в математическую логику внес немецкий математик и логик Г. Фреге (1848-1925). Он попытался всю математику обосновать через логику, ему удалось построить первую формальную логическую систему. Кроме того им и независимо от него Ч. Пирсом в математическую логику были введены предикаты и кванторы без которых логика не смогла бы оформиться как полноценная математическая дисциплина.

Математическая логика сама стала областью математики, поначалу казавшейся в высшей степени абстрактной и бесконечно далекой от практических приложений. Однако эта область недолго оставалась уделом "чистых" математиков. В начале 20 века (1910 г.) русский ученый Эренфест П.С. указал на возможность применения аппарата булевой алгебры в телефонной связи для описания переключательных цепей. В середине столетия была обнаружена теснейшая связь математической логики с новой наукой – кибернетикой. Эта связь открыла возможности многочисленных и разнообразных применений математической логики во многих отраслях техники и особенно в информатике и вычислительной технике. В 1938-1940 г. почти одновременно появились работы советского ученого Шестакова В. И.,

9

американского ученого Шеннона и японских ученых Накасимы и Хакадзавы о применении математической логики в цифровой технике. Первая монография, посвященная использованию математической логики при проектировании цифровой аппаратуры, была опубликована в СССР советским ученым Гавриловым М.А. в 1950 г. Чрезвычайно важна роль математической логики в развитии современной микропроцессорной техники: она используется в проектировании аппаратных средств ЭВМ, в разработке всех языков программирования и в конструировании дискретных устройств автоматики.

Большой вклад в развитие математической логики сделали ученые разных стран: профессор Казанского Университета Порецкий П.С., де-Морган, Ч.Пирс, А.Тьюринг, Колмогоров А.Н., К.Гёдель и др. Известный российский логик Порецкий П.С. очень точно отметил, что математическая логика по области исследований есть логика, а по методу исследований – математика. Широкое использование компьютеров, проникших буквально во все области человеческой деятельности, требуют развития массовой компьютерной культуры, начиная с самого раннего возраста. А это немыслимо без освоения математической логики и теории алгоритмов. В основе многочисленных языков программирования лежат математическая логика, теория формальных систем и логика предикатов. Понимание всех этих взаимосвязей неотделимо от подготовки специалистов в области программирования и программной инженерии.

1.4 Вопросы для самопроверки.

1.Сформулируйте задачи курса «математическая логика и теория алгоритмов».

2.Назовите области использования логических представлений.

3.Кто создал формальную логику?

4. Назовите имена крупных ученых в области математической логики. 5. Назовите этапы развития математической логики.

6. Назовите методы построения математической логики.

7.При изучении каких дисциплин используется математическая логика?

8.Назовите вклад русских ученых в математическую логику.

9.Назовите имена русских ученых в области математической логики.

10.Что дает изучение математической логики программисту?

10