Программа учебной дисциплины


Модуль 1. Математическая логика: исчисление предикатов



Скачать 278.34 Kb.
страница6/6
Дата30.07.2018
Размер278.34 Kb.
ТипПрограмма
1   2   3   4   5   6

Модуль 1. Математическая логика: исчисление предикатов


Виды учебной работы

Объем

в часах

Сроки

проведения, недели

Лекции

10

1-8

Семинары

10

1–8

Лабораторные работы







Практические занятия







Самостоятельная работа:







  • домашнее задание №1 « Исчисление предикатов»

12

1 – 8

  • рубежный контроль №1

4

8

  • проработка лекционного материала, подготовка к семинарам

8




Трудоемкость, час

36




Трудоемкость, зач.единицы

1




Контроль освоения модуля 1

Неделя проведения

контроля модуля

Формы контроля


Оценка в баллах

минимальная

максимальная

8

Домашнее задание

4

6

8

Рубежный контроль

10

14




ИТОГО

14

20

После освоения модуля 1 студент должен приобрести следующие знания, умения и владения, соответствующие компетенциям ООП.

Знания

Компетенции

  • структура теории исчисления предикатов 1-го порядка (ИП1);

  • понятия интерпретации, выполнимости, истинности и логической общезначимости;

  • теорема дедукции для ИП1;

  • непротиворечивость ИП1 и теорема Гёделя о полноте;

  • предваренная нормальная форма.




ОК-1, ОК-2, ОК-4, ОК-11, ОК-12, ОК-16
ПК-1, ПК-2, ПК-11





Умения

Компетенции

  • строить предваренную нормальную форму для формулы в ИП1;

  • строить выводы и доказательства в теории ИП1;

  • строить доказательства с применением метода резолюций.

ОК-1, ОК-2, ОК-4, ОК-11,

ОК-12
ПК-4, ПК-5,

ПК-14





Владение навыками

Компетенции

  • разработка и построение доказательств в формальной теории ИП1 в целях использования этого аппарата для решения содержательных задач.

ОК-1, ОК-2, ОК-4, ОК-11
ПК-5, ПК-12, ПК-13


Содержание модуля 1

Лекции

Определение теории ИП1 (4 ч.). Понятие терма и формулы. Понятие интерпретации. Выполнимость, истинность, логическая общезначимость. Аксиомы и правила вывода ИП1. Примеры выводов. Теорема дедукции.

Непротиворечивость и полнота ИП1 (4 ч.). Доказательство непротиворечивости ИП1. Формулировка и доказательство теоремы Гёделя о полноте. Неразрешимость теории ИП1.

Семинары

Построение выводов в ИП1 (2 ч.). Решение задач на построение выводов и доказательств в ИП1.

Предваренная нормальная форма (2 ч.). Построение предваренной нормальной формы для формул ИП1

Метод резолюций (2 ч.). Решение задач на доказательство в ИВ и в ИП1 методом резолюций.

Рубежный контроль (2 ч.).

Самостоятельная работа

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



Модуль 2. Теории первого порядка





Виды учебной работы

Объем

в часах

Сроки

проведения, недели

Лекции

8

9 –17

Семинары

8

9 –17

Лабораторные работы







Практические занятия







Самостоятельная работа:







  • рубежный контроль №2

4

17

  • проработка лекционного материала, подготовка к семинарам

17




Трудоемкость, час

36




Трудоемкость, зач.единицы

1




Контроль освоения модуля 3

Неделя проведения

Контроля модуля

Формы контроля


Оценка в баллах

Минимальная

максимальная

17

Рубежный контроль

10

14




ИТОГО

10

14

После освоения модуля 2 студент должен приобрести следующие знания, умения и владения, соответствующие компетенциям ООП.

Знания

Компетенции

  • понятие теории первого порядка, ее структура;

  • теория первого порядка с равенством;

  • формальная арифметика, аксиомы Пеано;

  • понятие рекурсивной функции;

  • нумерация Гёделя;

  • теорема Гёделя о неполноте.




ОК-1, ОК-2, ОК-4, ОК-11, ОК-12, ОК-16
ПК-1, ПК-2, ПК-11



Умения

Компетенции

  • доказывать теоремы в формальных теориях 1-го порядка;

  • строить рекурсивные функции из базисных;

  • вычислять гёделевы номера конструктивных объектов;




ОК-1, ОК-2, ОК-4, ОК-11,

ОК-12
ПК-4, ПК-5,

ПК-14





Владение навыками

Компетенции

  • использование идей и методов логики предикатов для решения прикладных задач (в частности, задач автоматизации программирования)




ОК-1, ОК-2, ОК-4, ОК-11
ПК-5, ПК-12, ПК-13


Содержание модуля 2

Лекции

Теории 1-го порядка (2 ч.). Структура теории 1-го порядка. Нелогические (собственные) аксиомы. Понятие модели теории. Теория 1-го порядка с равенством.

Формальная арифметика и теорема Гёделя о неполноте (6 ч.). Система натуральных чисел. Аксиомы Пеано. Арифметические операции. Рекурсивные функции. Нумерация рекурсивных функций. Гёделева нумерация. Теорема Гёделя о неполноте.

Семинары

Теории 1-го порядка (2 ч.). Построение доказательств в теориях 1-порядка (теория частичного порядка, теория групп).

Рекурсивные функции (2 ч.). Анализ рекурсивных функций и построение их из базисных.

Гёделева нумерация (2 ч.). Вычисление номеров рекурсивных функций и конструктивных объектов (слов и выводов).

Рубежный контроль (2 ч.).

Самостоятельная работа

В модуле 2 предусмотрено самостоятельная проработка материала лекций и семинаров и подготовка к итоговой аттестации (рубежному контролю). Рубежный контроль проводится в форме письменной работы на семинарском занятии.




Раздел 4. Методическое обеспечение дисциплины

Литература


Основная литература

  1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В.С. Зарубина и А.П. Крищенко. – 4-е изд. - М. Изд-во МГТУ им. Н.Э. Баумана, 2006, – 743 с.

  2. Яблонский С.В. Введение в дискретную математику. – 3-е изд.. – М: Высшая школа, 2001. – 384 с.

  3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – 2-е изд. – М: Наука, 1992, – 368 с.

  4. Дж. Андерсон. Дискретная математика и комбинаторика. – М., СПб, Киев: Изд. Дом. «Вильямс», 2003. – 960 с.

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

  6. Б.А. Кушнер. Лекции по конструктивному математическому анализу. – М.: Наука, 1973. – 448 с.

  7. А.А. Марков, Н.М. Нагорный. Теория алгорифмов. – М.: Наука, 1984. – 432 с.

  8. А.Н. Колмогоров, А.Г. Драгалин. Математическая логика.- 3-е изд. – М.: КомКнига, 2006. – 240 с.


Дополнительная литература

  1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2 т. – М.: Мир, 1978.

  2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

  3. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е изд.. – М.: Издательский дом «Вильямс», 2002. – 528 с.

  4. Евстигнеев В.А. Применение теории графов в программировании. – М.: Наука, 1985. – 352 с.

  5. Блюменфельд В.К., Котов В.Е. Теория схем программ. – М.: Наука, 1991. – 248 с.

  6. Зыков А.А. Основы теории графов. – М.: «Вузовская книга», 2004. – 664 с.

  7. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – М: Наука, 1990. – 383 с.

  8. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М: Наука, 1975, – 240 с.

  9. Шапорев С.Д. Дискретная математика: курс лекций и практических занятий. – СПб, БХВ-Петербург, 2006. – 400 с.

  10. Математическая логика в программировании: Сб. статей: Пер. с англ. – М.: Мир, 1991. – 408 с.

  11. Н.К. Верещагин, А. Шень. Языки и исчисления. – М.: МЦНМО, 2000. – 291 с.

  12. Н. Катленд. Вычислимость: введение в теорию рекурсивных функций. – М.: Мир, 1983. – 256 с.

  13. Ч. Чень, Р. Ли. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983. – 360 с.


Кафедральные издания и методические материалы

  1. Белоусов А.И., Власов П.А. Элементы комбинаторики: метод. указания к выполнению домашнего задания. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2012. – 53 с.

  2. Ахметова Ф.Х., Власов П.А. Дискретная математика – М.: Изд-во МГТУ им. Н.Э. Баумана, 2008. – 53 с.

Раздел 5. Материально-техническое обеспечение дисциплины


Методические материалы

1. Программа дисциплины.

2. Календарный план дисциплины.

3. Комплекты контрольно-оценочных средств (варианты домашних заданий, билеты рубежных контролей и вопросы для подготовки к ним).

4. Раздаточный материал по лекционному курсу.

Используемое оборудование: — не предусмотрено
Программа составлена в соответствии с требованиями ОС ВПО МГТУ им. Н.Э. Баумана


Обсуждено на заседании кафедры ФН-12

« » 2014 г.

Протокол №
Зав. кафедрой ФН-12

А.П. Крищенко


Автор программы:
доцент каф. ФН-12
Белоусов А.И.


Рецензент
________________ «____» ____________ 201_ г.

Председатель методической комиссии


факультета ФН Еркович О.С. ________________ «____» ____________ 201_ г.

Декан факультета ФН


Гладышев В.О. ________________ «____» ____________ 201_ г.

СОГЛАСОВАНО:

Начальник управления


образовательных стандартов и программ
Строганов Д.В. ________________ «____» ____________ 201_ г.




Поделитесь с Вашими друзьями:
1   2   3   4   5   6


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница