- •Введение
- •Занятие 1. Основные понятия математической логики. Исчисление высказываний
- •1.1. Введение
- •1.2. Исчисление высказываний
- •1.2.1. Основные логические функции исчисления высказываний
- •1.2.2. Дизъюнктивно-нормальная и конъюнктивно- нормальная формы
- •Контрольные вопросы и упражнения
- •Занятие 2. Перевод высказываний естественного языка на язык исчисления высказываний
- •Контрольные вопросы и упражнения
- •Занятие 3. Логический вывод в исчислении высказываний
- •3.1. Силлогизмы
- •3.2. Метод прямого преобразования
- •3.3. Метод семантических таблиц
- •3.4. Метод резолюций
- •Метод насыщения уровня
- •3.4.2. Стратегия вычеркивания
- •Контрольные вопросы и упражнения
- •Занятие 4. Исчисление предикатов
- •4.1. Основные понятия
- •4.2. Кванторные операции
- •4.3. Равносильности логики предикатов
- •4.4. Предваренная, сколемовская нормальная и сколемовская стандартная формы
- •Контрольные вопросы и упражнения
- •Занятие 5. Перевод высказываний естественного языка на язык логики предикатов
- •Контрольные вопросы и упражнения
- •Занятие 6. Логическое следствие в исчислении предикатов
- •6.1. Метод семантических таблиц
- •6.2. Процедура вывода Эрбрана
- •6.3. Принцип резолюции
- •6.3.1. Алгоритм унификации
- •6.3.2. Метод резолюций в исчислении предикатов
- •Контрольные вопросы и упражнения
- •Занятие 7. Теория алгоритмов
- •7.1. Вычислимые функции, частично-рекурсивные и общерекурсивные функции. Тезис Черча
- •7.2. Машинная математика. Машина Тьюринга.
- •7.3. Тезис Тьюринга (основная гипотеза теории алгоритмов)
- •7.4. Нормальные алгоритмы Маркова
- •Занятие 8. Обзор неклассических логик
- •8.1. Нечеткая логика
- •8.2. Модальные логики
- •8.3. Временные (темпоральные) логики
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
Л.В. Холопкина
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ: ПРАКТИКУМ
Учебное пособие
Воронеж 2008
ГОУВПО «Воронежский государственный
технический университет»
Л.В. Холопкина
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ: ПРАКТИКУМ
Утверждено Редакционно-издательским советом университета в качестве учебного пособия
Воронеж 2008
УДК 510.6(075.8)
Холопкина Л.В. Математическая логика и теория алгоритмов: практикум: учеб. пособие/Л.В. Холопкина. Воронеж: ГОУВПО «Воронежский государственный технический университет», 2008. 162 с.
В учебном пособии приведены теоретические сведения по основным разделам курса «Математическая логика и теория алгоритмов», даны подробные примеры решения типовых задач и представлены задания для самостоятельных и контрольных работ.
Издание соответствует требованиям Государственного образовательного стандарта высшего профессионального образования по направлению 230100 ”Информатика и вычислительная техника”, специальности 230101 “Вычислительные машины, комплексы, системы и сети”, дисциплине “Математическая логика и теория алгоритмов”. Предназначено для студентов заочной и заочной сокращенной форм обучения.
Учебное пособие подготовлено в электронном видев текстовом редакторе MS Word XP и содержится в файле Сети.rar.
Табл. 4. Ил. 5. Библиогр.: 14 назв.
Научный редактор д-р техн. наук, проф. С.Л. Подвальный
Рецензенты: кафедра естественно-научных дисциплин
Международного института компьютерных
технологий (зав. кафедрой д-р техн. наук,
проф. В.И. Митрохин);
д-р физ.-мат. наук проф. Т.М. Леденева
© Холопкина Л.В., 2008
© Оформление. ГОУВПО «Воронежский»
государственный технический универ-
ситет», 2008
Введение
Учебное пособие предназначено для студентов, обучающихся по направлению “Информатика и вычислительная техника” и смежным направлениям. Пособие является дополнением к стандартным учебникам по математической логике и теории алгоритмов для технических вузов: Л.М. Лихтарникова “Математическая логика и теория алгоритмов”, В.И. Игошина ”Математическая логика и теория алгоритмов” и В.И. Игошина “Задачи и упражнения по математической логике и теории алгоритмов”.
Данное издание позволит студентам познакомиться с основными понятиями и методами математической логики, выявить взаимосвязь математической логики с математической наукой и получить представление об областях использования математической логики: проектирование электронно-вычислительных машин, программного обеспечения к ним, системы искусственного интеллекта и различные области информатики.
Большое внимание уделено решению задач. Теоретическое изложение каждой темы завершается подробным разбором нескольких типовых задач. В пособии приведено большое количество задач для самостоятельного решения, что позволяет обеспечить индивидуальный подход к обучению каждого студента.
3
Занятие 1. Основные понятия математической логики. Исчисление высказываний
1.1. Введение
Логика – это набор правил для рассуждений и доказательств. Логика возникла тогда, когда развитие специальных наук и человеческого мышления поставило вопрос о том, как надо рассуждать, чтобы получить правильные выводы. Основателем классической логики является греческий ученый Аристотель, живший с 384 по 322 г. до н. э. Логические исследования Аристотеля изложены в двух его трудах «Первая аналитика» и «Вторая аналитика», объединенных под общим названием «Органом» (Орудие познания). Аристотель сформировал основное правило логики: является ли заключительное утверждение истинным при условии истинности приведенных фактов единственно в силу формальной структуры рассуждений, а, не исходя из смысла утверждений и фактов.
Математическая логика (теоретическая логика, символическая логика) – это раздел математики, посвященный изучению математических доказательств, иначе – это логика, развиваемая математическими методами.
Идея построения универсального языка для всей математики и формализация на базе этого языка математических доказательств выдвигалась еще в 17 веке
Г. Лейбницем (1646-1716). Г. Лейбниц впервые ввел в логику математические символы и некоторые математические правила. Это позволило заменить некоторые выводы вычислениями. Однако идеи этого ученого значительно опережали время.
4
Идеи Г. Лейбница по алгебратизации аристотелевской логики получили развитие спустя почти два столетия в работах английского математика Дж. Буля (1815-1864) и О.де Моргана (1806-1871). Очень важным этапом в развитии математической логики является изобретение в 1879 г. немецким математиком Готтлобом Фреге. (1848-1925) исчисления предикатов.
Основные принципы исчисления предикатов Г. Фреге принял на веру: он считал, что предложенная им система действительно обеспечивает формальное доказательство каждого записанного на этом языке логически верного предложения, то есть, истинного при всех возможных интерпретациях, и чтобы это доказательство систематически строилось по заданному предложению.
Обоснование теории исчисления предикатов, принятой Г. Фреге на веру, было дано в 30 годы 20 века. Это сделали независимо друг от друга французский алгебраист и логик Жак Эрбран, норвежец Торальф Скулем и австрийский математик К. Гедель. Работы этих ученых позволили создать новое направление на стыке математической логики и программирования – логическое программирование. Логическое программирование явилось теоретической основой для построения специального языка Пролог, который был создан в Марселе в 1971 году. Создателями этого языка считают европейских ученых А. Колмероэ и Р. Ковальского.
Расцвет математической логики как самостоятельной науки пришелся на 20-годы 20 века и связан с именами великих математиков: Я. Лукашевича (1878-1956),
К. Геделя (1906-1978), А. Тарского (1901-1983), А. Черча (1903-1995), С.К.Клини (1909-1994), Д. Гильберта (1862-1943), Г. Фреге (1848-1925), А. Тьюринга (1912-1980), А. Маркова (1903-1979).
5
Принципиальное (теоретическое) значение математической логики состоит в обосновании математики, то есть, в анализе ее основ.
Прикладное значение математической логики в настоящее время очень велико. Математическая логика применяется для следующих целей:
- анализа и синтеза цифровых вычислительных машин и других дискретных автоматов, в том числе и интеллектуальных систем;
- анализа и синтеза формальных и машинных языков, для анализа естественного языка;
- анализа и формализации интуитивного понятия вычислимости;
- выяснения существования механических процедур для решения задач определенного типа;
- анализа проблем сложности вычислений.
Математическая логика тесно связана с лингвистикой, экономикой, психологией и философией.