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

Прикладное значение математической логики в настоящее вре­ мя очень велико. Математическая логика применяется для следующих целей: • анализа и синтеза цифровых вычислительных машин и других дискретных автоматов, в том числе и интеллектуальных систем; • анализа и синтеза формальных и машинных языков, для ана­ лиза естественного языка; • анализа и формализации интуитивного понятия вычисли­ мости; • выяснения существования механических процедур для реше­ ния задач определенного типа; • анализа проблем сложности вычислений. Также математическая логика оказалась тесно связанной и с ря­ дом вопросов лингвистики, экономики, психологии и философии. В данном пособии излагаются основные понятия математиче­ ской логики и: теории алгоритмов. Материал, изложенный в пособии, соответствует государственному образовательному стандарту для на­ правления «Информатика и вычислительная техника» и может быть использован для студентов, обучающихся по разным специальностям этого направления. При написании пособия использовалась литература [1-31], и, конечно, — другие источники. В прилагаемый список литературы включены книги, которые желательно просмотреть любознательному и требовательному студенту. В пособии в каждой главе приведены вопросы и темы для са­ мопроверки теоретического материала и упражнения, предназначен­ ные для выработки навыков решения задач и углубления знаний по излагаемой теме, а также варианты типовых заданий и тесты для самоконтроля усвоения материала. Автор выражает благодарность профессору И. 3, Батыршину за полезные предложения и замечания, которые позволили улучшить работу, профессорам Ф. Г. Мухлисову и А. К. Шалабанову, доцентам Л. Г. Амбарцумову, А. Н. Козину, А. И. Белоусову и С. А. Ляшевой за внимание к работе и полезные замечания. Автор признателен своим студентам за помощь по набору текста.