Литература: Игошин В. И. Математическая логика и теория алгоритмов: учеб пособие для студ высш учеб заведений. М: Изд центр "Академия", 2008, 448с

Вид материала

Содержание

12. Машины Тьюринга и невычислимые функции ЗАНЯТО
13. Вычислимость на абаке и рекурсивные функции
16. Логика второго порядка и определимость в арифметике ЗАНЯТО
17. Логика второго порядка и определимость в арифметике (вариант-2)
18. Метод ультрапроизведений в теории моделей (вариант-1)
19. Метод ультрапроизведений в теории моделей (вариант-2)

Подобный материал:

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

Применение булевых функций к релейно-контактным схемам, в том числе к проектированию цифровых устройств в ЭВМ (шифраторы, дешифраторы, преобразователи кодов). ЗАНЯТО
Изучить принцип работы релейно-контактной схемы.
Рассмотреть математическую модель представления релейно-контактных схем с помощью булевых функций.
Изучить цифровые устройств в ЭВМ, работающие по принципу релейно-контактных схем, (шифраторы, дешифраторы, преобразователи кодов)
Решить задачи 7.3, 7.7, 7.8 (через СДН форму), 7.11 из [3].

Литература:

Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2008, 448с
Калабеков Б.А. Цифровые устройства и микропроцессорные схемы: Учебник для техникумов связи. –Горячая линия- Телеком, 2003, 336 с.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2007, 304с

2. Применение булевых функций к релейно-контактным схемам, в том числе к проектированию цифровых устройств в ЭВМ (сумматоры). ЗАНЯТО

Изучить принцип работы релейно-контактной схемы.
Рассмотреть математическую модель представления релейно-контактных схем с помощью булевых функций.
Изучить цифровые устройств в ЭВМ, работающие по принципу релейно-контактных схем, (сумматоры)
Решить задачи 7.4, 7.6, 7.8 (через СКН форму), 7.21 из [3].

Литература:

Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2008, 448с
Калабеков Б.А. Цифровые устройства и микропроцессорные схемы: Учебник для техникумов связи. –Горячая линия- Телеком, 2003, 336 с.
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2007, 304с

Применение булевых функций в теории распознавания образов ЗАНЯТО

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

Литература:

Горелик А.Л., Скрипкин. В.А. Методы распознавания. – М.: Высшая школа, 1977.

Приложение логики высказываний к логико-математической практике.ЗАНЯТО

Изучить применение логики высказываний в формулировках и доказательствах математических теорем.
Рассмотреть дедуктивные и индуктивные умозаключения.
Изучить применение логики высказываний в логических задачах.
Решить задачи 3.10, 3.12, 3.13, 3.20, 3.23, 3.42, 3.45, 3.55 из [2]

Литература:

Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2008, 448с
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2007, 304с

Формализованное исчисление предикатов.

Изучить первоначальные понятия формального исчисления предикатов (ИП), системы аксиом, правила вывода.
Разобрать теоремы о связи выводимости в ИП и истинности формул. (задачи 1-3, §5)[3]
Решить задачи 11.1-11.11 из [2]

Литература:

Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2008, 448с
Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений. - М: Изд. центр "Академия", 2007, 304с
Лавров И.А, Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.- М.: Физматлит-2004.

Аксиоматическая теория множеств ЗАНЯТО

Изложить систему аксиом
Изучить порядковые числа, равномощность, конечные и счетные множества.
Разобрать теорему Харгоса.
Рассмотреть аксиому выбора и аксиому ограничения.
Выполнить все упражнения из §1 Главы IV.

Литература:

Мендельсон Э. Введение в математическую логику. - Изд-во "Наука", гл. редакция физ.-мат. лит., - 1971.

Логическая игра (1 вариант) ЗАНЯТО

Рассмотреть основные понятия алгебры высказываний и логики предикатов.
Изучить приложение алгебры высказываний и логики предикатов к логико-математической практике.
Изучить кванторные операции над предикатами.
Рассмотреть решение «логических» задач на языке символов.
Разобрать графический способ решения задач подобного рода
_{Выполнить 30 заданий из упражнений 1-41 на с. 57-60 книги [2].}

Литература:

_{1. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд-во Сарат. ун-та, 1991.}

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

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

Логическая игра (2 вариант) ЗАНЯТО

Рассмотреть основные понятия алгебры высказываний и логики предикатов.
Изучить приложение алгебры высказываний и логики предикатов к логико-математической практике.
Изучить кванторные операции над предикатами.
Рассмотреть решение «логических» задач на языке символов.
Разобрать графический способ решения задач подобного рода
_{Выполнить 30 заданий из упражнений 42-91 на с. 57-60 книги [2].}

Неразрешимость логики первого порядка ЗАНЯТО

1. Изучить основные понятия логики первого порядка.

2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки.

3. Вывести неразрешимость логики первого порядка из неразрешимости проблемы остановки.

4. Разобрать доказательство неразрешимости логики 1 порядка методом Геделя.

5. Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3 из упражнения на стр. 164-165 в [1].

Литература:

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

_{Нестандартные модели арифметики}

_{1. Рассмотреть язык логики узкого исчисления предикатов арифметики и его стандартную интерпретацию в алгебре натуральных чисел.}

_{2. Доказать теорему о существовании нестандартных моделей элементарной теории арифметики.}

_{3. Изучить метод построения моделей элементарной теории арифметики с помощью принципов нестандартного анализа.}

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

_{Литература}

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

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

_{Метод диагонализации в математической логике ЗАНЯТО}

_{1. Рассмотреть понятие счетного множества и изучить метод диагонализации.}

_{2. Рассмотреть понятие машины Тьюринга и методом диагонализации построить пример невычислимой функции.}

_{3. Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость.}

_{4. Рассмотреть понятие диагонализации выражения и доказать лемму о диагонализации и теорему Черча о неразрешимости.}

5. Решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в [1].

Литература

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

12. Машины Тьюринга и невычислимые функции ЗАНЯТО

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

2. Рассмотреть понятие продуктивности машины Тьюринга и доказать ее основные свойства.

3. Доказать невычислимость функции продуктивность машины Тьюринга.

4. Рассмотреть проблему остановки машины Тьюринга и доказать ее неразрешимость.

5. Решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге [1].

Литература

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

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

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

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

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

3. Доказать, что рекурсивные функции вычислимы на абаках.

4. Доказать, что вычислимые функции рекурсивны.

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

Литература

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

_{14. Представимость рекурсивных функций и отрицательные результаты математической логики}

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

_{1.Разобрать такие основополагающие понятия математической логики, как язык арифметики и рекурсивная функция.}

_{2.Рассмотреть понятие представимости функций в теории и доказать представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики.}

_{3. Рассмотреть понятие геделевой нумерации и доказать главные отрицательные результаты математической логики.}

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

_{Литература}

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

_{15. Разрешимость арифметики сложения ЗАНЯТО}

_{1. Разобрать такие основополагающие понятия математической логики, как геделева нумерация и разрешимое множество.}

_{2. Доказать неразрешимость арифметики со сложением и умножением.}

_{3. Доказать разрешимость арифметики со сложением, без умножения.}

4. Решить задачи 1-3 из упражнения на стр. 152 в книге [2].

Литература

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

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

16. Логика второго порядка и определимость в арифметике ЗАНЯТО

1. Изучить основные понятия логики второго порядка и проанализировать ее главные отличия от логики первого порядка.

2. Рассмотреть понятие определимого в теории множества и исследовать проблему определимости множеств предложений первого порядка, истинных в стандартной модели арифметики.

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

4. Решить задачи 18.3,18.4 из упражнения на стр. 272-273 и задачи 20.1-20.5 из упражнения на стр. 289 в книге [1].

Литература

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

17. Логика второго порядка и определимость в арифметике (вариант-2)

1. Изучить основные понятия логики второго порядка и проанализировать ее главные отличия от логики первого порядка.

2. Рассмотреть понятие определимого в теории множества и исследовать проблему определимости множеств предложений первого порядка, истинных в стандартной модели арифметики.

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

4. Решить задачи 18.1,18.2 из упражнения на стр. 272-273 и задачи 20.6-20.10 из упражнения на стр. 289 в книге [1].

Литература

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

18. Метод ультрапроизведений в теории моделей (вариант-1)

1. Изучить такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, разобрать примеры теорий.

2. Рассмотреть понятие фильтра над множеством и доказать основные свойства фильтров.

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

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

5. Рассмотреть приложения теоремы Силова и примеры силовских подгрупп.

6. Решить задачи 1.4.1, 1.4.2, 1.4.9, 1.4.16 на стр.62, 4.1.1-4.1.6 на стр.207 в [1].

Литература

1. Кейслер Г., Чен Ч.Ч. Теория моделей. – М.: Мир, 1977.

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

19. Метод ультрапроизведений в теории моделей (вариант-2)

1. Изучить такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, разобрать примеры теорий.

2. Рассмотреть понятие фильтра над множеством и доказать основные свойства фильтров.

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

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

5. Рассмотреть приложения теоремы Силова и примеры силовских подгрупп.

6. Решить задачи 4.1.12-4.1.14 на стр.207 в [1], а также задачи 1-4 на стр. 125-126 в [2].

Литература

1. Кейслер Г., Чен Ч.Ч. Теория моделей. – М.: Мир, 1977.

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

_{20. Теорема Геделя о неполноте формальной арифметики}

_{1. Изучить постановку задачи о неполноте формальной арифметики.}

_{2. Рассмотреть начальные понятия теории алгоритмов и примеры их применения.}

3. Доказать простейшие критерии неполноты.

_{4. Изучить основы формальной арифметики и доказать семантическую формулировку теоремы Геделя о ее неполноте.}

5. Разобрать все примеры и восстановить все пропущенные доказательства в [1].

_{Литература:}

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

_{21. Разрешимые и неразрешимые аксиоматические теории}

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

_{2. Изучить методы доказательства разрешимости и неразрешимости теорий.}

_{3. Рассмотреть известные примеры доказательства разрешимости и неразрешимости аксиоматических теорий.}

_{4. Разобрать решения всех примеров из литературных источников [1],[2].}

_{Литература}

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

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

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

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

_{22. Интерполяционная лемма Крейга и ее приложения}

1. Разобрать доказательство интерполяционной леммы Крейга.

2. Доказать теорему Робинсона о непротиворечивости объединения теорий.

_{3. Доказать теорему Бета об определимости понятий теории.}

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

_{Литература}

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

Blog

Литература: Игошин В. И. Математическая логика и теория алгоритмов: учеб пособие для студ высш учеб заведений. М: Изд центр "Академия", 2008, 448с

Содержание