Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Следует особо отметить большое значение для становления и развития ма­ тематической логики одного из самых блестящих достижений в истории чело­ вечества, а именно, превращение геометрии в точную дедуктивную систему в работе Евклида (330 - 275 г. до н. э.) - «Начала». Именно этот дедуктивный подход с ясным осознанием целей и методов был положен в основу развития философской и математической мысли последующих столетий. Также большое значение для становления и развития логики сыграли дос­ тижения в алгебре (алгебра Буля) и в других математических дисциплинах, в том числе и вновь в геометрии (создание неевклидовой геометрии - геометрии Лобачевского - Гаусса - Бойаи). Краткий обзор становления математической логики можно найти в [7]. В формировании и становлении математической логики участвовали мно­ гие и многие ученые как древних времен, так средневековья и последующих времен. Принципиальное и прикладное значение математической логики Принципиальное значение математической логики - обоснование матема­ тики (анализ основ математики). Прикладное значение математической логики в настоящее время очень ве­ лико. Математическая логика применяется для следующих целей: • анализа и синтеза цифровых вычислительных машин и других дискрет­ ных автоматов, в том числе и интеллектуальных систем; • анализа и синтеза формальных и машинных языков, для анализа естест­ венного языка; • проверки правильности программ и электронных схем; • анализа и формализации интуитивного понятия вычислимости; • выяснения существования механических процедур для решения задач определённого типа; • анализа проблем сложности вычислений; • создания экспертных систем для решения сложных проблем. Также математическая логика оказалась тесно связанной и с рядом во­ просов лингвистики, экономики, психологии и философии. в данном пособии излагаются основные понятия математической логики и теории алгоритмов, являющихся теоретической базой для компьютерных наук. При написании пособия использовалась литература [1-39], и, конечно, другие источники. В пособии в каждой главе приведены упражнения, предназначенные для выработки навыков решения задач и углубления знаний по излагаемой теме, кроме того, приведены варианты типовых заданий и тесты для самоконтроля усвоения материала. 4