Тема 68. Логика на словах
Один из основных подходов к исследованию распознаваемых языков базируется на известной теореме Ж. Бучи о характеризации регулярных языков средствами монадической логики второго порядка. В курсовой работе необходимо изучить метод исследования распознаваемых языков, основанный на монадической логике второго порядка. Рекомендуется следующий план работы.
1 Изучить основные понятия монадической логики второго порядка (/1/,
с. 328-330; /2/, с. 313-321; /3/, с. 1-2).
2 Рассмотреть приложение монадической логики второго порядка к теории языков (/2/, с. 321-324; /3/, с. 1-2).
3 Разобрать доказательство теоремы Ж.Бучи о характеризации регулярных языков средствами монадической логики второго порядка (/2/, с. 325-329; /3/, с. 1-2).
4 С помощью теоремы Ж.Бучи исследовать взаимосвязь между иерархиями языков и определяющих их формул логики первого порядка (/2/, с. 329-338; /3/, с. 8-13).
Разобрать все примеры из указанных выше литературных источников и решить задачи 2, 3, 6-8 из упражнения на с. 352 в /2/.
Литература, рекомендуемая для изучения темы
1Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
2Pin J.-E., Perrin D. Infinite words. 2001 (в печати, текст доступен на www.liafa.jussieu.fr/~jep/Resumes/InfiniteWords.html).
3Pin J.-E. Logic on Words. Report LITP 94/53, Institut Blaise Pascal, 1994 (препринт).
Тема 69. Алгебры отношений и полугруппы преобразований
Полугруппы преобразований, с одной стороны, играют фундаментальную роль в теории полугрупп и, с другой стороны, являются частным видом алгебр отношений, играющих важную роль в универсальной алгебре. Цель курсовой работы - изучить основные методы алгебр отношений и теории представления полугрупп преобразованиями. Рекомендуется следующий план работы.
- 1 АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ
- Тема 1. Алгебра бинарных отношений и отображений
- Тема 2. Отображения и фактор-множества
- Тема 10. Основная теорема алгебры
- Тема 18. Замыкания и соответствия Галуа
- Тема 19. Функция Мёбиуса и её свойства
- Тема 28. Греко-китайская теорема об остатках
- Тема 33. Силовские подгруппы
- 2 МАТЕМАТИЧЕСКАЯ ЛОГИКА
- Тема 34. Логическая игра
- Тема 35. Неразрешимость логики первого порядка
- 3 ДИСКРЕТНАЯ МАТЕМАТИКА
- Тема 47. Эйлеровы графы
- Тема 48. Гамильтоновы графы
- Тема 55. Раскраски графов
- Тема 61. Теорема Пойа и перечисление графов
- Тема 62. Графы на двумерных поверхностях
- Тема 68. Логика на словах
- Тема 75. Элементы теории конечных автоматов
- Тема 82. Модулярные и дистрибутивные решетки
- Тема 83. Булевы алгебры
- 4 РАЗЛИЧНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ
- Тема 86. Элементы линейного программирования
- Тема 95. Барицентрическое исчисление
- Приложение А