1_Введение (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004)

Введение.

1. Назначение курса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1.1

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

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

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

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

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

Логика как наука сформировалась в 4 в. до н.э. Ее создал гречес­кий ученый Аристотель.

Слово «логика» происходит от греческого "логос", что с одной стороны означает "слово" или "изложение", а с другой мышление. В толковом словаре Ожегова С.И. сказано: "Логика наука о законах мышления и его формах". В 17 в. немецкий ученый Лейбниц задумал создать новую науку, ко­торая была бы «искусством исчисления истины» . В этой логике, по мысли Лейбница, каждому высказыванию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила распространения и развития и осталась гениальной догадкой.

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

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

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

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

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

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

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

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

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

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