Темы курсовых работ по дисциплине «Математическая логика и теория алгоритмов» - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Рабочая программа дисциплины Математическая логика и теория алгоритмов... 1 85.75kb.
Темы курсовых работ по дисциплине «Макроэкономика» 1 16.32kb.
Темы курсовых работ по дисциплине «бухгалтерский учет и анализ» 1 19.04kb.
Темы курсовых работ по дисциплине «Финансы организаций по отраслям» 1 20.75kb.
Темы курсовых работ по дисциплине мвко кафедры банковского дела для... 1 40.2kb.
Математическая логика 1 107.53kb.
История логики насчитывает около двух с половиной тысячелетий. 1 200.26kb.
Темы курсовых работ по истории государства и права зарубежных стран 1 37.46kb.
Параллельные вычисления 1 415.89kb.
Тематика курсовых работ по курсу «история средних веков» 1 25.25kb.
Тематика курсовых работ по дисциплине «Менеджмент» 1 9.98kb.
В работе С. С. Гончарова и Дж. Найт [1] дана классификация классов... 1 15.26kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Темы курсовых работ по дисциплине «Математическая логика и теория алгоритмов» - страница №1/1

Темы курсовых работ

по дисциплине «Математическая логика и теория алгоритмов»

(из сборника тем курсовых работ по математике / В.А. Молчанов, В.Е. Новиков, Т.М. Отрыванкина, П.Н. Пронин, В.Е. Фирстов. – Оренбург: ГОУ ОГУ, 2004. – 68 с. )

Номер варианта = номер по списку

Тема 1. Методы решения логических задач.

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



  1. Рассмотреть основные понятия алгебры высказываний и логики предикатов (/1/, с.10-35, 122-134).

  2. Изучить приложение алгебры высказываний и логики предикатов к логико-математической практике (/1/, с. 64-88, 195-221).

  3. Изучить кванторные операции над предикатами (/1/, с. 157-165).

  4. Рассмотреть решение "логических" задач на языке символов (/3/, с.60-65).

  1. Разобрать графический способ решения задач подобного рода (/2/, с.9-56).

Разобрать решения всех задач из цитированных выше разделов указанных литературных источников и решить задачи 3.58-3.61 из книги /3/. Выполнить 5 заданий из упражнений 1-91 на с. 57-60 книги /2/.

Литература, рекомендуемая для изучения темы



  1. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.

  2. Кэрролл Л. Логическая игра: Пер. с англ. Ю.А. Данилова. - М.: Наука, 1991. (М.: "Квант"; Вып. 73).

  3. Игошин В.И. Задачник-практикум по математической логике: Учеб. пособие для студентов-заочников физ.-мат. фак-в пед. ин-тов. - М.: Просвещение, 1986.

  4. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Изд-во «Академия», 2006. – 304 с.



Тема 2. Неразрешимость логики первого порядка.

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



  1. Изучить основные понятия логики первого порядка (/1/, с. 130-151).

  2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки (/1/, с. 36-54).

  3. Вывести неразрешимость логики первого порядка из неразрешимости проблемы остановки (/1/, с. 152-160).

  4. Разобрать доказательство неразрешимости логики первого порядка методом Геделя (/1/, с. 160-166).

Литература, рекомендуемая для изучения темы

  1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.

Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3 из упражнения на стр. 164-165 в книге /1/.
Тема 3. Метод диагонализации в математической логике.

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



  1. Рассмотреть понятие счетного множества и изучить метод диагонализации (/1/, с. 12-30).

  2. Рассмотреть понятие машины Тьюринга и методом диагонализации построить пример невычислимой функции (/1/, с. 36-45, 66-74).

  3. Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76).

  4. Рассмотреть понятие диагонализации выражения и доказать лемму о диагонализации и теорему Черча о неразрешимости (/1/, с. 228-235).

Разобрать решения всех примеров из цитированных разделов /1/ и решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в книге /1/.

Литература, рекомендуемая для изучения темы



  1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.


Тема 4. Машины Тьюринга и невычислимые функции

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



  1. Разобрать такие основополагающие понятия математической логики, как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.228-229, 249-255).

  2. Рассмотреть понятие продуктивности машины Тьюринга и доказать ее основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).

  3. Доказать невычислимость функции продуктивность машины Тьюринга (/1/, с. 60-64).

  4. Рассмотреть проблему остановки машины Тьюринга и доказать ее неразрешимость (/1/, с. 47-48, 53-54, 64-65).

Разобрать решения всех примеров из литературных источников /1/,/2/ и решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.

Литература, рекомендуемая для изучения темы



  1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.

  2. Мендельсон Э. Введение в математическую логику. - М.: Наука, 1971.


Тема 5. Вычислимость и рекурсивные функции.

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



  1. Разобрать такие основополагающие понятия математической логики, как машина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).

  2. Рассмотреть понятие «обычного» компьютера, введенное Иоахимом Ламбеком и названное им абаком, доказать, что вычислимость функции абаком сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95).

  3. Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100­122).

  4. Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/.
Тема 6. Отрицательные результаты математической логики.

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



  1. Разобрать такие основополагающие понятия математической логики, как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145).

  2. Рассмотреть понятие представимости функций в теории и доказать представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики (/1/, с. 212-226).

  3. Рассмотреть понятие геделевой нумерации и доказать главные отрицательные результаты математической логики (/1/, с. 228-240).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.

Литература, рекомендуемая для изучения темы



  1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.


Тема 7. Разрешимость арифметики сложения.

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



  1. Разобрать такие основополагающие понятия математической логики, как геделева нумерация и разрешимое множество (/1/, с. 228-233, /2/, с. 151­152).

  2. Доказать неразрешимость арифметики со сложением и умножением (/1/, с. 234-236).

  3. Доказать разрешимость арифметики со сложением, без умножения (/1/, с. 290-299).

Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.
Тема 8. Логика второго порядка.

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



  1. Изучить основные понятия логики второго порядка и проанализировать ее главные отличия от логики первого порядка (/1/, с. 261­273).

  2. Рассмотреть понятие определимого в теории множества и исследовать проблему определимости множеств предложений первого порядка, истинных в стандартной модели арифметики (/1/, с. 273, 274-280).

  3. Рассмотреть введенный П. Коэном метод вынуждения и доказать с его помощью теорему Дж. Аддисона о неопределимости в арифметике класса множеств, определимых в арифметике (/1/, с. 281-289).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 18.1-18.4 из упражнения на стр. 272-273 и задачи 20.1-20.10 из упражнения на стр. 289 в книге /1/.

Литература, рекомендуемая для изучения темы



    1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.


Тема 9. Неполнота формальной арифметики.

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



  1. Изучить постановку задачи о неполноте формальной арифметики (/1/,с. 7-11).

  2. Рассмотреть начальные понятия теории алгоритмов и примеры их применения (/1/, с. 12-21).

  3. Доказать простейшие критерии неполноты (/1/, с. 21-25).

  4. Изучить основы формальной арифметики и доказать семантическую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42).

Разобрать примеры./1/.

Литература, рекомендуемая для изучения темы

1. Успенский В.А. Теорема Геделя о неполноте. - М.: Наука, 1982.

2. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.


Тема 10. Разрешимые и неразрешимые аксиоматические теории.

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



  1. Разобрать такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, рассмотреть известные конструкции над алгебраическими системами (/1/, с. 103-118; /2/, с. 12-25).

  2. Изучить методы доказательства разрешимости и неразрешимости теорий (/2/, с. 265-275).

  3. Рассмотреть известные примеры доказательства разрешимости и неразрешимости аксиоматических теорий (/2/, с. 275-292; /3/).

Разобрать решения всех примеров из литературных источников /1/, /2/.

Литература, рекомендуемая для изучения темы

1 Ершов Ю.Л., Палютин Е.А. Математическая логика. - М.: Наука,1979.

2 Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. -М.: Наука, 1980.



  1. Рабин М.О. Разрешимые теории. В кн.: Справочная книга по математической логике, ч.3. Теория рекурсии. - М.: Наука, 1982. - с. 77-111.

  2. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А. Элементарные теории // УМН, 1965, 20, № 4, с. 37-108.

  3. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.


Тема 11. Решение задач логики узкого исчисления предикатов.

Интерполяционная лемма Крейга дает положительное решение следующей важной задачи логики узкого исчисления предикатов (УИП): если из предложения A следует предложение C, то существует предложение B, которое следует из A, из которого следует C и которое содержит лишь нелогические символы, входящие как в A, так и в C. В курсовой работе необходимо изучить доказательство интерполяционной леммы Крейга и рассмотреть ее приложения к задаче о непротиворечивости объединения теорий и к задаче об определимости понятий теории. Рекомендуется следующий план работы.

1 Разобрать доказательство интерполяционной леммы Крейга (/1/, с.308-318).


  1. Доказать теорему Робинсона о непротиворечивости объединения теорий (/1/, с. 319-322).

  2. Доказать теорему Бета об определимости понятий теории (/1/, с. 25­-32).

Выполнить упражнение на с. 327 в книге /1/.

Литература, рекомендуемая для изучения темы

1 Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.
Тема 12 Машины Тьюринга.


  1. Дать определение машины Тьюринга.

  2. Рассмотреть применения машины Тьюринга к словам. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции.

  3. Разобрать примеры.

Литература, рекомендуемая для изучения темы

  1. Игошин В.И. Математическая логика и теория алгоритмов. – М.: Изд-во «Академия», 2004. – 448 с.

  2. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. - М.: Изд-во «Академия», 2006. – 304 с.



Тема 13. Существование и единственность модели формализации теории.


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

1 Рассмотреть язык логики узкого исчисления предикатов арифметики и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131).

2 Доказать теорему о существовании нестандартных моделей элементарной теории арифметики (/1/, с. 252-260).

3 Изучить метод построения моделей элементарной теории арифметики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57-79).

Разобрать все примеры из указанных выше литературных источников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 на стр.131 в книге /2/.

Литература, рекомендуемая для изучения темы

1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

2 Мендельсон Э. Введение в математическую логику. – М.: Наука, 1971.




Тема 14. Булевы алгебры.


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

1 Изучить характеристические свойства булевых алгебр и проанализировать их взаимосвязь с булевыми кольцами (/1/, глава 1, § 2, /2/, глава 1, § 1.1).

2 Рассмотреть основные свойства булевых алгебр и теорему о представлении конечной булевой алгебры алгеброй множеств (/1/, глава 1, § 2, /2/, глава 1, § 1.1).

Разобрать все примеры из указанных выше литературных источников и решить задачи 2, 3, 4, 5 на стр. 42 в /1/.

Литература, рекомендуемая для изучения темы

1 Лидл Р., Пильц Г., Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.

2 Богомолов А.В., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука, 1997.

Тема 15. Минимизация булевых многочленов.


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

1 Рассмотреть понятия булевой алгебры и булева кольца, доказать еих основные свойства (/1/, с. 31-43).

2 Рассмотреть понятия булева многочлена и булевой полиномиальной функции, доказать их основные свойства (/1/, с. 43-47, 53-56).

3 Изучить алгоритмы построения дизъюнктивной нормальной формы и конъюнктивной нормальной формы булева многочлена (/1/, с. 47-53).

4 Рассмотреть проблему минимизации булевых многочленов и изучить метод минимизации таких многочленов, разработанный Куайном-Мак-Класки (/1/, с. 60-70).

Разобрать решения всех примеров из указанного выше литературного источника и решить задачи 5-8, 15 из упражнения на стр. 59-60 и задачи 1-5 из упражнения на стр. 70 в /1/.

Литература, рекомендуемая для изучения темы

1 Лидл Р., Пильц Г., Прикладная абстрактная алгебра, Екатеринбург: Изд-во УрГУ, 1996.

2 Богомолов А.В., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука, 1997.

Тема 16. Приложения булевых алгебр к переключательным схемам.


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

1 Рассмотреть понятия булевой алгебры и булева многочлена, доказать их основные свойства (/1/, с. 31-53).

2. Изучить основные понятия алгебры переключательных схем и разобрать способ представления переключательных функций с помощью диаграмм Карно (/1/, с. 74-86, 111-122).

3. Разобрать типичные примеры приложений переключательных схем (/1/, с. 89-104).

4. Разобрать приложение переключательных схем к сложению двоичных чисел с помощью полусумматоров и сумматоров (/1/, с. 105-111).

Разобрать решения всех примеров из указанного выше литературного источника /1/ и решить задачи 1-4, 9-11, 15, 19, 21 из упражнения на стр. 124-130 в /1/.



Литература, рекомендуемая для изучения темы

1 Лидл Р., Пильц Г., Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.


izumzum.ru