Программа дисциплины по кафедре Прикладная математика и информатика математическая логика и теория алгоритмов

Тихоокеанский государственный университет

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Прекдседатель УМК _________________ _________200_ г ________________

Директор института _________________ _________200_ г ________________

(декан факультета)

• 
  обучить студентов классической логике высказываний и предикатов, теории рекурсивных функций;
  
• 
  на примерах этих моделей математической логики ознакомить студентов с предназначением и устройством аксиоматических систем, с характерными задачами логического вывода и методами их решения; с применением логических систем в качестве формальных языков представления знаний, с методами дедуктивного извлечения знаний, с принципами устройства автоматических систем, логического доказательства теорем; с разнообразием моделей вычислений, положенными в основу современных и перспективных систем программирования, их вычислительными возможностями и принципиальными ограничениями; с понятиями универсального алгоритма, с явлением алгоритмической неразрешимости и эффективной сводимости массовых проблем, с основами теории сложности алгоритмов.
  
• 
  привести естественное содержательное истолкование изучаемых понятий и результатов в терминах современного программирования;
  
• 
  выработать у студентов навыки свободного обращения с такими объектами как логические формулы, логико-алгебраические модели, системы формального вывода, модели вычислений, рекурсивные множества и функции;
  
• 
  дать студентам представление о потенциальных возможностях и ограничениях формальных логических теорий и алгоритмов;
  
• 
  развить у студентов аналитическое мышление и общую математическую культуру;
  
• 
  привить студентам умение самостоятельно изучать учебную и научную литературу в области математики.
  

Разделы дисциплины и виды занятий и работ

Практические занятия и их взаимосвязь с содержанием лекционного курса

1. Входной контроль знаний студентов

2. Текущий контроль знаний студентов

1. 
   Понятие «элементарное высказывание». Логические операции над элементарными высказываниями. Формулы алгебры высказываний. Подформулы.
   
2. 
   Тавтология и противоречие. Равносильные формулы. Связь между равносильностью и эквивалентностью. Равносильные преобразования формул: теорема подстановки и теорема замены.
   
3. 
   Двойственные формулы. Принцип двойственности. Основные равносильности алгебры высказываний.
   
4. 
   Определение логической функции. Логические функции одной и двух переменных.
   
5. 
   Конъюктивные и дизъюнктивные нормальные формы. Совершенные конъюктивные и дизъюнктивные нормальные формы. Теорема Шеннона.
   
6. 
   Классы Поста. Полная система. Критерий Поста. Базис. Основные базисы пространства бинарных логических функций.
   
7. 
   Одноместный предикат. - местный предикат. Область определения и область истинности предиката. Тождественно истинный и тождественно ложный предикат.
   
8. 
   Логические операции над одноместными предикатами. Кванторы всеобщности и существования.
   
9. 
   Формулы логики предикатов. Равносильные формулы. Равносильности логики предикатов.
   
10. 
    Нормальная форма формулы логики предикатов и предваренная нормальная форма. Теорема о предваренной нормальной форме.
    
11. 
    Понятие «чистое исчисление предикатов». Алфавит, формулы, аксиомы и основные правила вывода исчисления предикатов.
    
12. 
    Алфавит, формулы, аксиомы и основные правила вывода прикладных исчислений предикатов.
    
13. 
    Алфавит, формулы, аксиомы и основные правила вывода исчисления высказываний.
    
14. 
    Доказуемая формула. Правило одновременной подстановки. Правило сложного заключения.
    
15. 
    Формула, выводимая из совокупности формул. Теорема дедукции.
    
16. 
    Эквивалентные формулы. Теорема эквивалентности.
    
17. 
    Проблемы аксиоматического исчисления высказываний.
    
18. 
    Понятие «алгоритм». Основные требования, предъявляемые к алгоритмам. Блок-схемы алгоритмов.
    
19. 
    Машина Тьюринга. Определение и описания. Конфигурация машины Тьюринга. Стандартная начальная и стандартная заключительная конфигурация.
    
20. 
    Эквивалентные машины Тьюринга. Теорема о машине Тьюринга, не содержащей направления «» (или «на месте»). Композиция машин Тьюринга. Функции, правильно вычислимые на машине Тьюринга.
    
21. 
    Нуль-функция, функция следования и функция проекции. Операторы суперпозиции, примитивной рекурсии и минимизации. Примитивно рекурсивные, частично рекурсивные функции.
    
22. 
    Нормальные алгоритмы Маркова.
    
23. 
    Алгоритмическая разрешимость. Меры сложности алгоритмов. Верхние и нижние оценки сложности алгоритмов.
    

Учебно-методическое обеспечение дисциплины

1. 
   Верещагин. Лекции по математической логике и теории алгоритмов.
   
2. 
   Гетманова А.Д. Учебник по логике. – М.: ЧеРо, 1997.
   
3. 
   Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987.
   
4. 
   Ивлев Ю.В. Логика: учебник для вузов.- М.: Логос, 1997.
   
5. 
   Игошин В.И. Математическая и теория алгоритмов. – Саратов: изд. СГУ, 1991.
   
6. 
   Клини С. Математическая логика.– М.: Мир, 1973.
   
7. 
   Ковальский Р. Логика в решении проблем. – М.: Наука, 1990.
   
8. 
   Лавров С.С. Лекции по теории программирования. – СПб.: изд. НЕСТОР, 1999.
   
9. 
   Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – Москва: "Лань", 1999.
   
10. 
    Мальцев А.И. Алгоритмы и рекурсивные функции.
    
11. 
    Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.
    
12. 
    Непейвода Н.Н. Прикладная логика. – Новосибирск: изд НГУ, 2000.
    
13. 
    Новиков П.С. Элементы математической логики. – М.: Наука, 1973.
    

1. 
   Гилберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. – М.: Наука, 1979.
   
2. 
   Яблонский С.В. Введение в дискретную математику. – М.: Высш. шк., 2001.
   
3. 
   Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Издательство МГТУ им. Н.Э. Баумана, 2001.
   
4. 
   Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.
   
5. 
   Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
   
6. 
   Клини С.К. Математическая логика. – М.: Мир, 1973.
   
7. 
   Гилберт Д., Бернайс П. Основания математики. Теория доказательств. – М.: Наука, 1982.
   
8. 
   Гудстейн Р.Л. Математическая логика. – М.: ИЛ, 1961.
   
9. 
   Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1972.
   
10. 
    Марков А.А., Нагорный Н.М. Теория алгорифмов. – М.: Наука, 1984.
    
11. 
    Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.–М.: Наука, 1977.
    

1. 
   отдельные темы могут быть отнесены на самостоятельное изучение;
   
2. 
   на лекциях предлагается значительное количество контрольных вопросов и упражнений, служащих для проверки усвоения теории;
   
3. 
   на практических занятиях регулярно задаются домашние задания, которые проверяют усвоение методов и приемов решения разбираемых на практических занятиях задач, закрепляют алгоритмические умения и навыки.