Учебно-методический комплекс дисциплины математическая логика Основная образовательная программа

РАЗДЕЛ I.Программа учебной дисциплины.

1. 
   Автор программы: Шиманский Сергей Александрович, ст. преподаватель кафедры информатики и ОТД
   

2. 
   Рецензенты: Суханова Н.Т. – канд. пед. наук, доцент кафедры информатики и ОТД
   

3. 
   Пояснительная записка:
   

4. 
   Извлечение из ГОС ВПО специальности 050202 Информатика
   

5. 
   Объем дисциплины и виды учебной работы (для всех специальностей, на которых читается данная дисциплина):
   

6. 
   Содержание дисциплины:
   
   1. 
      Разделы дисциплины и виды занятий (в часах). Примерное распределение учебного времени:
      

2. 
   Содержание разделов дисциплины.
   

3. 
   Темы для самостоятельного изучения.
   

7. 
   Методические рекомендации по организации изучения дисциплины.
   

1. 
   Тематика и планы аудиторной работы студентов по изученному материалу:
   

1. 
   Решение задач на составление таблиц истинности.
   
2. 
   Приведение высказываний к формам логических выражений.
   
3. 
   Определение истинности и ложности высказываний непосредственно и с помощью тавтологий алгебры высказываний.
   
4. 
   Определение принадлежности формулы к классам истинности.
   
5. 
   Сопоставление булевых функций логическим выражениям.
   

1. 
   Проверка истинности некоторых тождеств алгебры логики.
   
2. 
   Упрощение логических выражений с использованием основных тождеств алгебр логики.
   
3. 
   Определение истинности и ложности высказываний с помощью эквивалентных преобразований.
   
4. 
   Приведение логических выражений и булевых функций к форме с наименьшим числом литер.
   

1. 
   Разложение ФАЛ по нескольким произвольным переменным.
   
2. 
   Приведение пропозициональных формул к дизъюнктивной и конъюнктивной нормальным формам аналитическим методом.
   
3. 
   Приведение пропозициональных формул к совершенным дизъюнктивной и конъюнктивной нормальным формам аналитическим методом.
   
4. 
   Приведение пропозициональных формул к совершенным дизъюнктивной и конъюнктивной нормальным формам табличным методом.
   

1. 
   Приведение к ТДНФ, ТКНФ, МДНФ, МКНФ с помощью метода проб.
   
2. 
   Приведение к ТДНФ, ТКНФ, МДНФ, МКНФ с помощью метода Квайна.
   
3. 
   Приведение к ТДНФ, ТКНФ, МДНФ, МКНФ с помощью метода Квайна-мак Класки.
   
4. 
   Приведение к ТДНФ, ТКНФ, МДНФ, МКНФ с помощью метода Блейка-Порецкого.
   
5. 
   Приведение к ТДНФ, ТКНФ, МДНФ, МКНФ с помощью карт Карно, диаграмм Вейча.
   

1. 
   Разложение ФАЛ по нескольким произвольным переменным.
   
2. 
   Приведение пропозициональных формул к дизъюнктивной и конъюнктивной нормальным формам аналитическим методом.
   
3. 
   Приведение пропозициональных формул к совершенным дизъюнктивной и конъюнктивной нормальным формам аналитическим методом.
   
4. 
   Приведение пропозициональных формул к совершенным дизъюнктивной и конъюнктивной нормальным формам табличным методом.
   

1. 
   Приведение высказываний к формулам логики предикатов.
   
2. 
   Использование кванторов для записи ФЛП.
   
3. 
   Определение выполнимости и общезначимости ФЛП.
   

1. 
   Проверка истинности некоторых тождеств ЛП.
   
2. 
   Упрощение логических выражений с использованием основных тождеств ЛП.
   
3. 
   Определение истинности и ложности высказываний с помощью эквивалентных преобразований.
   

1. 
   Вывод предикативных утверждений.
   

1. 
   Приведение к приведённой и предварённой нормальным формам ФЛП.
   

1. 
   Доказательство формальных теорем исчисления высказываний секвенциального типа.
   
2. 
   Упрощение секвенциальных форм с использованием основных тождеств исчисления секвенций.
   
3. 
   Определение истинности и ложности секвенций с помощью эквивалентных преобразований.
   
4. 
   Доказательство формальных теорем исчисления высказываний гильбертовского типа.
   
5. 
   Упрощение форм ИВ с использованием основных тождеств ИВ.
   
6. 
   Алгоритмы проверки общезначимости и противоречивости в ИВ.
   

1. 
   Доказательство формальных теорем исчисления предикатов секвенциального типа.
   
2. 
   Доказательство формальных теорем исчисления предикатов гильбертовского типа.
   
3. 
   Описание некоторых отношений в сигнатуре заданных.
   

1. 
   Приведение к ПНФ, ПКНФ, КлНФ различных формул логики предикатов.
   
2. 
   Определение унифицируемости множеств.
   
3. 
   Нахождение резольвент пар дизъюнктов.
   
4. 
   Установление выполнимости множества предложений.
   

1. 
   Доказательство свойств формальных аксиоматических систем.
   
2. 
   Доказательство эквивалентности формул в различных сигнатурах.
   
3. 
   Нахождение интерпретаций и моделей аксиоматической теории.
   

1. 
   Разложение булевых функций в полиномы Жегалкина.
   

1. 
   Рассмотрение структур математических доказательств.
   
2. 
   Доказательство правильности различных методов доказательств.
   
3. 
   Доказательство отсутствия доказательства существования доказательства некоторых видов теорем.
   

1. 
   Логические преобразования в неклассических логиках.
   
2. 
   Структура программы в императивном и декларативном программировании.
   

1. 
   Таблицы истинности в k-значной логике.
   
2. 
   Логические функции в k-значной логике.
   
3. 
   Применение k-значной логики в программировании и конструировании ПК.
   

1. 
   Таблицы истинности в нечётких логиках.
   
2. 
   Логические функции в нечётких логиках.
   
3. 
   Конструирование высказываний в модальных логиках.
   
4. 
   Применение нечёткой логики в конструировании микропроцессоров.
   

1. 
   Учебно-методическое обеспечение дисциплины.
   
   1. 
      Рекомендуемая литература:
      
      • 
        Основная
        

1. 
   Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Изд-во Сарат. Ун-та, 1991.
   
2. 
   Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М.: МГУ, 1982.
   
3. 
   Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.
   
4. 
   Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2008.
   
5. 
   Ивлев Ю.В. Логика. – М.: «Логос», 1997.
   
6. 
   Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3 . Вычислимые функции. – 1999. 176 с.
   
7. 
   Глухов М.М. Математическая логика, – М., 1982.
   
8. 
   Ершов Ю.Л., Палютин Е.А. Математическая логика. – М., 1979.
   
9. 
   Гиндикин С.Г. Алгебра логики в задачах, – М., 1972.
   
10. 
    Лавров И.А., Максимова Л.Л., Задачи по теории множеств, математической логики и теории алгоритмов, – М., 1984.
    
11. 
    Глухов М.М., Шапошников В.А. Задачи и упражнения по математической логике, – М., 1984
    

• 
  Дополнительная.
  

12. 
    Мальцев А.И. Алгоритмы и рекурсивные функции, – М., 1965.
    
13. 
    Клини С.К. Математическая логика, – М., 1973.
    
14. 
    Гуц А.К. Математическая логика и теория алгоритмов.– Омск: Наследие. Диалог-Сибирь, 2003.
    
15. 
    Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.
    

9. 
   Материально-техническое обеспечение дисциплины
   
   1. 
      Перечень используемых технических средств. Нет.
      
   2. 
      Перечень используемых пособий. Нет.
      
   3. 
      Перечень видео- и аудиоматериалов программного обеспечения. Нет.
      

1. 
   Примерные зачетные задания.
   

1. 
   Определить, является ли данная последовательность формулой:
   
   1. 
      ;
      
   2. 
      ;
      
   3. 
      .
      
2. 
   Доказать, что результат замены некоторого вхождения формулы С в формулу А на формулу В тоже есть формула.
   
3. 
   Доказать, что для любой формулы существует эквивалентная ей «тесная формула».
   
4. 
   Построить таблицы истинности для следующих формул:
   
   1. 
      ;
      
   2. 
      ;
      
   3. 
      ;
      
   4. 
      ;
      
   5. 
      ;
      
   6. 
      .
      
5. 
   Доказать выполнимость формул:
   
   1. 
      ;
      
   2. 
      ;
      
   3. 
      .
      
6. 
   Найти СДНФ для формул:
   
   1. 
      ;
      
   2. 
      ;
      
   3. 
      ;
      
   4. 
      ;
      
   5. 
      .
      
7. 
   Найти СКНФ для формул:
   
   1. 
      ;
      
   2. 
      ;
      
   3. 
      ;
      
   4. 
      ;
      
   5. 
      .
      
8. 
   Доказать полноту систем функций:
   
   1. 
      ;
      
   2. 
      ;
      
   3. 
      ;
      
   4. 
      ;
      
   5. 
      .
      
9. 
   Доказать, что каждая тождественно истинная формула выводима в исчислении высказываний.
   
10. 
    Доказать, что бескванторная формула истинна тогда и только тогда, когда она может быть получена подстановкой из некоторой тождественно истинной формулы исчисления высказываний.
    
11. 
    Пусть предложение А истинно в любой системе, в которой истинны все аксиомы теории Т. Доказать, что А принадлежит Т.
    
12. 
    Доказать, что не существует предложения, истинного во всех конечных моделях и ложного в любой бесконечной модели.
    

1. 
   Примерный перечень вопросов к зачету (экзамену).
   

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. 
    Предикатные временнЫе логики и их приложения к программированию. Алгоритмические логики.
    

1. 
   Комплект экзаменационных билетов (утвержденный зав. кафедрой до начала сессии) – не предусмотрено.
   
2. 
   Примерная тематика рефератов.
   

1. 
   Предмет и значение логики;
   
2. 
   Исчисление высказываний;
   
3. 
   Синтаксис и семантика языка логики предикатов;
   
4. 
   Метод резолюции для логики предикатов первого порядка;
   
5. 
   Синтаксис и семантика модальной логики;
   
6. 
   Схемы модальных формул;
   
7. 
   Темпоральные логики;
   
8. 
   Нечеткая арифметика;
   
9. 
   Немонотонные рассуждения;
   
10. 
    Основные понятия нечеткой логики.
    

14. 
    Примерная тематика курсовых работ – не предусмотрено.
    
15. 
    Примерная тематика квалификационных (дипломных) работ – не предусмотрено.
    
16. 
    Методика(и) исследования (если есть) – не предусмотрено.
    
17. 
    Бально-рейтинговая система, используемая преподавателем для оценивания знаний студентов по данной дисциплине – не предусмотрено.