[ Рабочая программа дисциплины
"Дискретная математика и математическая логика, часть 2 "
Предназначена для студентов _4_ курса,
по специальности: 01.01.00 -математика
АВТОР: Арсланов М.М.
1. Требования к уровню подготовки студента, завершившего изучение дисциплины
"Дискретная математика и математическая логика, часть 2"
Студенты, завершившие изучение данной дисциплины должны:
- понимать основные идеи и методы, лежащие в основе математической логики, их роль и место в современной математике и других науках, их практическое применение и возможности;
- обладать теоретическими знаниями об основных логических исчислениях, уметь строить выводы из логических аксиом, понимать суть аксиоматического подхода в математике, обладать знаниями об основных достижениях математической логики: о теоремах Геделя о неполноте, совместности аксиом выбора и континуума с аксиомами теории множеств, Коэна о независимости этих аксиом от аксиом теории множеств, о неразрешимых и разрешимых теориях, об алгоритмически неразрешимых математических проблемах.
- ориентироваться в литературе по математической логике;
- приобрести навыки решения типовых задач математической логики, уметь строить формальные доказательства логических суждений и исследовать вопросы непротиворечивости и полноты логических исчислений.
2. Объем дисциплины и виды учебной работы (в часах).
Форма обучения очная Количество семестров _1_ Форма контроля:
8 семестр - зачет Количество часов № Виды учебных занятий п/ п семестр 1. Всего часов по дисциплине 2. Самостоятельная работа 3. Аудиторных занятий в том числе лекций практических занятий
СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
Название темы и ее содержание № Количество часов п/п лекции практ.занятия Тема. Исчисление высказываеий. 6 1. Алгебра логики. Логические операции, их истинностные значения.
2. Исчисление высказываний (ИВ). Аксиомы, правило вывода.
Доказуемые формулы. Примеры.
3. Теорема дедукции.
4. Правила введения и удаления логических символов.
5. Доказуемость формул “закон исключенного третьего”, “закон противоречия”.
6. Эквивалентные формулы ИВ.
7. Теорема о замене.
8. Непротиворечивость ИВ.
9. Полнота ИВ.
10.Дизъюнктивная нормальная форма формул ИВ.
2 Тема. Исчисление предикатов. 10 1. Исчисление предикатов (ИП). Аксиомы, правила вывода.
Доказуемые формулы.
Правила введения и удаления кванторов.
2.
Эквивалентные формулы ИП.
3.
Теорема о замене.
4.
Пренексная нормальная форма формул ИП.
5.
Непротиворечивость ИП.
6.
Теорема о существовании модели.
7.
Полнота ИП.
8.
Алгебраические системы. Сигнатура, тип сигнатуры.
Декартовы произведения. Примеры.
Фильтры, ультрафильтры. Примеры.
Фильтрованные произведения алгебраических систем.
Теорема компактности (локальная теорема Мальцева) 1. Аксиомы теории множеств. Первые следствия из аксиом.
2. Натуральные числа, множество натуральных чисел. Ординалы.
3. Трансфинитная индукция. Примеры доказательства трансфинитной индукции.
4. Класс всех ординалов не является множеством.
5. Аксиома выбора. Эквивалентные формулировки. Лемма Цорна, аксиома полного упорядочения.
6. Равномощные множества. Мощность континуума. Мощность множества всех подмножеств больше мощности самого 7. Для каждого множества существует равномощный с ним
ЛИТЕРАТУРА
1. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987.2. Арсланов М.М., Калимуллин И.Ш. Элементы математической логики.
Казань, из-во КГУ, 3. Клини С.К. Математическая логика М.: Наука, 1988.
4. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. Поведение и синтез. М.: Наука, 1970.
БИЛЕТЫ К ЭКЗАМЕНАМ
1. Графы: основные определения и понятия, типы графов, примеры. Лемма о рукопожатиях.2. Теорема о функциональной полноте.
1. Связные графы, компоненты связности. Два определения связности графа, их эквивалентность.
2. Теорема Майхилла-Нероуда о распознаваемости языка конечным автоматом.
1. Верхняя и нижняя оценки числа ребер простого графа с n вершинами и k компонентами связности.
2. Замкнутость пяти классов Поста.
1. Эйлеровы и полуэйлеровы графы. Теорема Эйлера.
2. Примеры полных систем. Представление функций алгебры логики полиномами Жегалкина.
1. Гамильтоновы и полугамильтоновы графы. Теорема Дирака.
2. Функции алгебры логики от n переменных, их количество. Существенные и несущественные переменные.
1. Основные свойства деревьев.
2. Конечные автоматы и распознаваемые языки. Пример языка, нераспознаваемого никаким конечным автоматом.
1. Алгоритм Краскала нахождения остовного дерева наименьшего веса и его обоснование.
2. Класс линейных функций. Лемма о нелинейной функции.
1. Паросочетания, трансверсали. Теорема Холла.
2. Регулярные языки, их распознаваемость конечными автоматами.
1. Орграфы, компоненты сильной связности, конденсация.
2. Замкнутость множества языков, распознаваемых источниками, относительно операций: сумма, отражение, проекция, цилиндр, конкатенация, итерация.
1. Основание орграфа. Критерий существования сильно связного орграфа с заданным основанием.
2. Источники и распознаваемые ими языки. Эквивалентность источников.
Двухполюсные источники.
1. Теорема Форда-Фалкерсона о максимальном потоке.
2. Класс монотонных функций. Лемма о немонотонной функции.
1. Алгоритм нахождения максимального потока и его обоснование.
2. Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
1. Укладка графов в трехмерном пространстве. Укладка планарного графа на поверхности сферы.
2. Принцип двойственности. Лемма о несамодвойственной функции.
1. Непланарность графов K5 и K3,3. Отношение гомеоморфности, Теорема Понтрягина-Куратовского (без доказательства).
2. Теорема о детерминизации источника.
1. Формула Эйлера для плоских графов.
2. Теорема Клини о регулярности языков, распознаваемых конечными автоматами.
1. Замкнутость множества языков, распознаваемых конечными автоматами относительно операций: отрицание, сумма, пересечение, Y-цилиндр.
2. Предполные классы функций алгебры логики.
ВАРИАНТ КОНТРОЛЬНОЙ РАБОТЫ
1. Проверить полноту системы функций: {x y yz, x y}.2. Пусть Gn - простой регулярный связный граф с n вершинами. Доказать, что если 3 n 7, то граф Gn гамильтонов.
3. Построить конечный автомат, распознающий язык L = {x1... x k | k 2, x1 x k } в алфавите X={0,1}.
«