Список учебно-методических разработок для студента (в)

1. Емельченков Е.П., Емельченков В.Е. Аксиоматические теории. Математическая морфология. Смоленск: Изд-во СГМА, 2000. Том 4, вып. 1. С. 35-56.

2. Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов Аксиоматические теории. Математическая морфология. Смоленск: Изд-во СГМА, 2000. Том 4, вып. 1. С. 3-34.

Информационные технологии и ресурсы (г)

1. http://www.intuit.ru – Интернет-Университет Информационных Технологий

2. http://window.edu.ru – Каталог образовательных Internet-ресурсов.

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

1. Емельченков Е. П., Емельченков В. Е. Аксиоматические теории (см. приложение 1).

2. Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов Аксиоматические теории (см. приложение 2).

Контроль над освоением студентом дисциплины

Текущий контроль

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

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

Промежуточный контроль

Вариант контрольной работы

1. Запишите на языке алгебры предикатов предложение «Через две различные точки проходит единственная прямая».

2. Найдите все следствия из посылок.

"Если сумма цифр целого числа делится на 3, то это число делится на 3 или на 9"; "Если целое число делится на 9, то оно делится на 3". Найденным следствиям придайте содержательный смысл.

3. Опишите работу счетчика голосов в комиссии из четырех человек с правом вето у председателя.

4. Исследуйте на непротиворечивость и полноту аксиоматическую теорию строгого линейного порядка.

Вопросы к экзамену

1. Дедуктивный характер математики. Предмет математической логики, ее роль в вопросах обоснования математики.

2. Булевы функции. Табличное задание булевых функций. Задание булевых функций целыми числами. Графическое представление булевых функций. Элементарные булевы функции. Формулы. Эквивалентные формулы. Полная система функций.

3. Алгебра булевых функций. Принцип двойственности.

4. Приложение алгебры высказываний к логико-математической практике. Прямая, обратная и противоположная теоремы. Принцип полной дизъюнкции. Необходимые и достаточные условия.

5. ДНФ. Теорема о разложении функций по переменным. Алгоритм приведения к СДНФ.

6. Теорема о представлении логической функции формулой. Алгоритм приведения к СКНФ.

7. Эквивалентные преобразования. Приведение к ДНФ и СДНФ. Теорема о достаточности основных соотношений булевой алгебры для эквивалентных преобразований.

8. Принцип двойственности. Функционально полные системы. Алгебра Жегалкина.

9. Нахождение следствий из посылок. Нахождение посылок для данных следствий. Тавтологии – законы логики высказываний. Законы контрапозиции, исключенного третьего, двойного отрицания, приведение к абсурду и др.

10. Применение булевых функций к анализу и синтезу дискретных устройств. Примеры (одноразрядный двоичный сумматор, автомат для продажи газированной воды).

11. Контактные схемы. Задача минимизации. Алгоритм приведения к минимальной ДНФ.

12. Методы математических доказательств. Правильные и неправильные рассуждения.

13. Применение логики высказываний в химии (проблема химического синтеза).

14. Формальные теории (как строится формальная теория). Вывод, доказательство, теорема, метатеорема. Исчисление высказываний.

15. Примеры вывода в исчислении высказываний. Теорема дедукции. Теорема о полноте исчисления высказываний относительно алгебры высказываний.

16. Свойства аксиоматических теорий: непротиворечивость, полнота, разрешимость, независимость системы аксиом. Свойства аксиоматической теории исчисления высказываний.

17. Логика предикатов. Основные определения (тождественно истинный предикат, выполнимый предикат, опровержимый предикат, множество истинности предиката, равносильные предикаты, следствие). Операции над предикатами. (Связанные и свободные переменные). Зачем нужна логика предикатов?

18. Формулы логики предикатов. Соглашения о снятии скобок. Ограниченные кванторы.

19. Основные равносильности логики предикатов.

20. Исчисление предикатов. Связь между общезначимостью и доказуемостью.

21. Предваренные нормальные формы. Алгоритм приведения к ПНФ.

22. Приложения логики предикатов к алгебре (уравнения, неравенства, системы и совокупности уравнений и неравенств).

23. Математика и язык. Имя и смысл в школьной математике.

24. Логическая структура школьного курса геометрии.

25. Приложение логики к теории баз данных.

26. Аксиоматическая теория «Исчисление предикатов» и ее свойства.

27. Интуитивное понятие алгоритма. Свойства алгоритмов. Уточнение понятия алгоритма (с помощью машины с неограниченными регистрами МНР).

28. Нумерация программ для МНР. Нумерация вычислимых функций. Универсальные программы.

29. Алгоритмически неразрешимые проблемы. s-m-n-теорема.