МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВЛАДИВОСТОКСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ЭКОНОМИКИ И СЕРВИСА
ИНСТИТУТ ИНФОРМАТИКИ, ИННОВАЦИЙ И БИЗНЕС-СИСТЕМ
КАФЕДРА МАТЕМАТИКИ И МОДЕЛИРОВАНИЯ
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Рабочая программа учебной дисциплины
Основная образовательная программа
230700Прикладная информатика
230400Информационные системы и технологии
Владивосток
Издательство ВГУЭС
2014
ББК ***
Рабочая программа учебной дисциплины «Математическая логика и теория алгоритмов» составлена в соответствии с требованиями ООП для студентов направлений 23070Прикладная информатика, 230400Информационные системы и технологии, на базе ФГОС ВПО.
Составитель: профессор, канд. физ.-мат. наук, кафедры математики и моделирования
Утверждена на заседании кафедры математики и моделирования от 7.02.2011 г., протокол № 7, редакция 2014г.
Рекомендована к изданию учебно-методической комиссией Института информатики, инноваций и бизнес – систем.
© Издательство Владивостокский
государственный университет
экономики и сервиса, 2014
ВВЕДЕНИЕ
Дисциплина «Математическая логика и теория алгоритмов» является важным звеном математического образования. Этот раздел математики наиболее интенсивно стал развиваться в середине прошлого века в связи с внедрением ЭВМ. В современной науке и технике знание математической логики и теории алгоритмов играют все большую роль. Это обусловлено совершенствованием вычислительной техники, благодаря которой существенно расширяется возможность успешного применения математики при решении конкретных задач. Причины введения дисциплины «Математическая логика и теория алгоритмов» заключаются в необходимости подготовки студентов к изучению последующих математических и специальных дисциплин, многие из которых связаны с основными понятиями математической логики и теории алгоритмов.
Дисциплина «Математическая логика и теория алгоритмов» включает в себя такие разделы, как алгебра высказываний, исчисление высказываний, логика предикатов, исчисление предикатов, элементы теории алгоритмов.
Данная программа построена в соответствии с требованиями ФГОС ВПО к дисциплине «Математическая логика и теория алгоритмов». Рабочая учебная программа разработана на основе учебных планов направлений «Прикладная информатика», 230400.62 «Информационные системы и технологии».
1. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ
1.1. Цели освоения учебной дисциплины
Целями освоения учебной дисциплины являются сформировать представление об основах математической логики и развить способность применять полученные теоретические знания к решению актуальных практических задач. Задачи курса сводятся к изучению алгебры высказываний, исчисления высказываний, логики предикатов и исчисления предикатов, к формированию логического мышления, развитию абстрактного мышления, освоение аппарата математической логики. Изучая математическую логику, студенты, по сути, знакомятся с современным математическим языком, являющимся, как известно, языком любой науки.
1.2. Место учебной дисциплины в структуре ООП (связь с другими дисциплинами)
Дисциплина «Математическая логика и теория алгоритмов» относится к вариативной части математического и естественнонаучного цикла для направлений «Прикладная информатика», «Информационные системы и технологии».
Дисциплина «Математическая логика и теория алгоритмов» базируется на следующих дисциплинах ООП: «Дискретная математика», «Линейная алгебра».
1.3. Компетенции обучающегося, формируемые в результате освоения учебной дисциплины
Таблица 1. Формируемые компетенции
Название ООП (сокращенное название ООП) | Блок | Компетенции | Знания/ умения/ владения (ЗУВ) | |
230700.62 Прикладная информатика | Б.2 | ПК-17- способен применять методы анализа прикладной области на концептуальном, логическом, математическом и алгоритмическом уровнях | Знания: | методов математической логики, теории алгоритмов |
Умения: | применять методы теории множеств, математической логики, алгебры высказываний, теории графов, теории автоматов, теории алгоритмов при решении профессиональных задач повышенной сложности | |||
Владение: | навыками моделирования прикладных задач | |||
230400.62 Информационные системы и технологи | Б.2 | ОК-10- готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования | Знания: | основных понятий и методов математической логики |
Умения: | решать типовые задачи по основным разделам курса | |||
Владение: | методами построения математической модели профессиональных задач и содержательной интерпретации полученных результатов |
1.4. Основные виды занятий и особенности их проведения
Объем и сроки изучения дисциплины.
Курс читается для бакалавров второго курса в осеннем семестре для направлений
«Прикладная информатика», «Информационные системы и технологии» в объеме 144 учебных часов (4 зачетные единицы) из них аудиторных 51 час. На самостоятельное изучение дисциплины выделяется 47 часов.
Промежуточный контроль по дисциплине — экзамен.
Удельный вес занятий, проводимых в интерактивных формах, для направлений составляет 20 процентов аудиторных занятий.
1.5. Виды контроля и отчетности по дисциплине
Контроль успеваемости осуществляется в соответствии с рейтинговой системой оценки знаний студентов.
Текущий контроль предполагает:
- проверку уровня самостоятельной подготовки студента при выполнении индивидуального задания;
- опросы по основным моментам изучаемой темы;
- проведение контрольных работ по блокам изученного материала;
- тестирование остаточных знаний (предварительные аттестации).
Промежуточный контроль знаний осуществляется при проведении экзамена.
2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
2.1 Темы лекций
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)» (2 час.).
Формулы АВ. Эквивалентность формул АВ. Понятия дизъюнктивной нормальной формы (ДНФ), конъюнктивной нормальной формы (КНФ), СДНФ, СКНФ.
Тема 2. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ» (2 час.).
Понятие исчисления. Язык ИВ. Определение формулы ИВ. Аксиомы и правила вывода ИВ. Доказуемые и выводимые формулы ИВ. Примеры доказуемых и выводимых формул ИВ.
Тема 3. «Теорема о дедукции в ИВ» (2 час.).
Формулировка и доказательство теоремы о дедукции. Следствия из данной теоремы.
Тема 4. «Эквивалентные формулы ИВ» (3 час.).
Понятие эквивалентных формул ИВ. Формулировка и доказательство основных законов ИВ: законы идемпотентности, коммутативности, ассоциативности, дистрибутивности, де Моргана, двойного отрицания.
Тема 5. «Дизъюнктивная и конъюнктивная нормальные формы (ДНФ и КНФ)»
(2 час.).
Определения элементарной конъюнкции, элементарной дизъюнкции, ДНФ, КНФ. Теорема о существовании для любой формулы ИВ эквивалентной ей ДНФ (КНФ).
Тема 6. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы» (3 час.). Понятия сигнатуры, алгебраической системы данной сигнатуры, подсистемы, подсистемы, порожденной множеством. Примеры. Понятия терма данной сигнатуры, значение терма на кортеже в алгебраической системе. Теорема о подсистеме, порожденной множеством.
Тема 7. «Формулы ЛП. Истинность формул ЛП в алгебраической системе. Эквивалентные формулы ЛП» (3 час.).
Понятие формулы данной сигнатуры. Определение истинности формулы ЛП на кортеже элементов в алгебраической системе. Примеры.
Тема 8. «Пренексная нормальная форма (ПНФ) для формул ЛП» (2 час.).
Понятия ДНФ и ПНФ для формул ЛП. Теорема о существовании для любой формулы ЛП эквивалентной ей ПНФ.
Тема 9. «Исчисление предикатов (ИП). Доказуемые формулы ИП» (2 час.).
Язык ИП. Определение формулы ИП. Аксиомы и правила вывода ИП. Доказуемые и выводимые формулы ИП. Примеры доказуемых и выводимых формул ИП. Тавтологии. Связь между тавтологией и доказуемой формулой.
Тема 10. «Теорема о дедукции в ИП» (2 час.).
Формулировка и доказательство теоремы о дедукции. Следствия из данной теоремы.
Тема 11. «Эквивалентные формулы ИП» (3 час.).
Понятия эквивалентных формул ИП, пропозиционально эквивалентных формул ИП. Связь между этими понятиями. Формулировка и доказательство основных эквивалентностей ИП.
Тема 12. «Пренексная нормальная форма для формул ИП» (2 час.).
Понятия ДНФ и ПНФ для формул ИП. Теорема о существовании для любой формулы ИП эквивалентной ей ПНФ.
Тема 13. «Машины Тьюринга» (2 час.).
Определение машины Тьюринга. Понятие функций, вычислимых по Тьюрингу. Примеры таких функций.
Тема 14. «Примитивно рекурсивные функции» (2 час.).
Понятия базисных функций, операторов суперпозиции, примитивной рекурсии, примитивно рекурсивных функций. Примеры.
Тема 15. «Частично рекурсивные функции» (2 час.).
Понятия оператора минимизации, частично рекурсивных функций. Примеры. Эквивалентность классов функций, вычислимых по Тьюрингу с классом частично рекурсивных функций.
2.2 Перечень тем практических/лабораторных занятий
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)» (1 час.).
Построение ДНФ, КНФ, СДНФ, СКНФ, эквивалентных данным формулам алгебры высказываний.
Тема 2. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ» (2 часа, «снежный ком»).
Построение выводов и доказательств формул ИВ.
Тема 3. «Эквивалентные формулы ИВ» (2 часа, «снежный ком»).
Доказательство эквивалентности формул ИВ.
Тема 4. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы» (1 час.). Построение подсистем, порожденных множеством.
Тема 5. «Формулы ЛП. Истинность формул ЛП в алгебраической системе» (2 часа, метод «мозгового штурма»).
Построение формул ЛП, истинных на кортеже элементов в алгебраической системе.
Тема 6. «Пренексная нормальная форма (ПНФ) для формул ЛП» (2 час.).
Построение ПНФ для формул ЛП.
Тема 7. «Исчисление предикатов (ИП). Доказуемые формулы ИП» (2 часа, «снежный ком»).
Построение выводов и доказательств формул ИП.
Тема 8. «Эквивалентные формулы ИП» (2 часа, метод «мозгового штурма»).
Доказательство эквивалентности формул ИП.
Тема 9. «Машины Тьюринга» (1 час.).
Построение машин Тьюринга для вычислимых функций.
Тема 10. «Примитивно рекурсивные функции» (1 час.).
Доказательство примитивной рекурсивности функций.
Тема 11. «Частично рекурсивные функции» (1 час.).
Доказательство рекурсивности для вычислимых функций.
3. ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ
Программой дисциплины предусмотрено чтение лекций, проведение практических занятий. В течение изучения дисциплины студентов изучают на лекционных занятиях теоретический материал. На практических занятиях под руководством преподавателя, решают практические задачи.
При проведении практических занятиях применяются следующие интерактивные методы обучения:
- метод «мозгового штурма»: метод представляет собой разновидность групповой дискуссии, которая характеризуется сбором всех вариантов решений, гипотез и предложений, рожденных в процессе осмысления какой-либо проблемы, их последующим анализом с точки зрения перспективы дальнейшего использования или реализации на практике;
-«снежный ком»: цель наработка и согласование мнений всех членов группы. При использовании этой техники в активное обсуждение включаются практически все студенты.
Для студентов в качестве самостоятельной работы предполагается выполнения домашних заданий, изучение дополнительных тем.
4. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ КУРСА
4.1 . Перечень и тематика самостоятельных работ студентов по дисциплине
Тема 1. «Логическое следствие в алгебре высказываний». Понятия логического следствия. Связь между понятиями логического следствия, противоречивого множества формул, тождественно ложной формулы и тождественно истинной формулы.
Тема 2. «Логическое следствие в ЛП». Понятия логического следствия, противоречивого множества формул ЛП, тождественно истинной формулы ЛП. Связь между этими понятиями. Определение эквивалентных формул ЛП. Основные эквивалентности в ЛП.
Тема 3. «Нормальные алгорифмы». Понятия нормального алгорифма. Примеры. Эквивалентность классов нормально вычислимых функций с классом частично рекурсивных функций.
4.2 Контрольные вопросы для самостоятельной оценки качества освоения учебной дисциплины.
1. Дать определение дизъюнктивной и конъюнктивной нормальных форм в алгебре высказываний. Привести примеры формул, находящихся в ДНФ и КНФ; в ДНФ, но не в КНФ; в КНФ, но не в ДНФ.
2. Что такое тождественно истинная формула алгебры высказываний? Тождественно ложная формула алгебры высказываний? Противоречивое множество формул алгебры высказываний? Привести примеры.
3. Сформулировать определение логического следствия в АВ. Дать эквивалентные формулировки логического следствия. Доказать эквивалентность. Привести примеры.
4. Что такое формула исчисления высказываний? Дать определение доказуемой и выводимой из множества формул формулы исчисления высказываний Показать доказуемость формулы F®F.
5. Сформулировать и доказать теорему о дедукции, а также следствия из этой теоремы. Продемонстрировать применение этой теоремы на примерах.
6. Какие формулы исчисления высказываний называются эквивалентными? Доказать законы идемпотентности в исчислении высказываний.
7. Доказать законы коммутативности в исчислении высказываний.
8. Доказать законы ассоциативности в исчислении высказываний.
9. Доказать законы дистрибутивности в исчислении высказываний.
10. Доказать законы двойного отрицания в исчислении высказываний.
11. Доказать законы де Моргана в исчислении высказываний.
12. Дать определение элементарной конъюнкции, элементарной дизъюнкции, дизъюнктивной и конъюнктивной нормальных форм в исчислении высказываний. Доказать теорему о существовании формулы, находящейся в ДНФ (КНФ) и эквивалентной данной формуле исчисления высказываний.
13. Что такое сигнатура? Алгебраическая система данной сигнатуры? Подсистема алгебраической системы? Привести примеры.
14. Дать определение подсистемы алгебраической системы, порожденной множеством. Как строятся термы данной сигнатуры? Как, применяя понятие терма, можно построить подсистему, порожденную множеством, для данной системы?
15. Что такое формула логики предикатов? Подформула логики предикатов? Свободная и связанная переменная формулы логики предикатов? Привести примеры формул. Указать все свободные и связанные переменные этих формул.
16. Дать определение истинности формулы логики предикатов в алгебраической системе на кортеже элементов из носителя системы. Привести примеры.
17. Что такое логическое следствие в логике предикатов. Дать определение тождественно истинной и тождественно ложной формулы логики предикатов. Определить понятие противоречивого множества формул логики предикатов. Сформулировать и доказать утверждения, эквивалентные понятию логического следствия. Привести примеры.
18. Что такое формула исчисления предикатов? Дать определение доказуемой и выводимой из множества формул формулы исчисления предикатов, тавтологии исчисления предикатов.. Привести примеры тавтологий исчисления предикатов.
19. Сформулировать и доказать теорему о дедукции в исчислении предикатов, а также следствия из этой теоремы. Продемонстрировать применение этой теоремы на примерах.
20. Какие формулы исчисления предикатов называются пропозиционально эквивалентными? Эквивалентными? Доказать основные эквивалентности исчисления предикатов.
21. Что такое пренексная нормальная форма для формул исчисления предикатов? Доказать теорему существования формулы, эквивалентной данной, находящейся в пренексной нормальной форме.
22. Сформулировать связь между понятиями алгоритма, машины Тьюринга и рекурсивными функциями. Дать определения машины Тьюринга, примитивно рекурсивной функцией, частично рекурсивной функцией.
23. Доказать, что простейшие арифметические операции вычислимы по Тьюрингу.
24. Доказать, что простейшие арифметические операции являются примитивно рекурсивными функциями.
4.3 Методические рекомендации по организации СРС
При решении индивидуальных домашних заданий необходимо использовать теоретический материал, делать ссылки на соответствующие теоремы, свойства, формулы и пр. Решение ИДЗ излагается подробно и содержит необходимые пояснительные ссылки.
4.4 Рекомендации по работе с литературой
В процессе изучения дисциплины «Математическая логика и теория алгоритмов» помимо теоретического материала, предоставленного преподавателем во время лекционных занятий, может возникнуть необходимость в использовании учебной литературы.
Наиболее подробно и просто темы «Исчисление высказываний» и «Исчисление предикатов» изложены в книге «Элементы математической логики». Темы «Логика предикатов» и «Теория алгоритмов» более доступно изложены в книге , «Математическая логика».
В качестве учебника для формирования практических навыков решения задач по математической логике и теории алгоритмов наилучшим образом подходит «Задачи по теории множеств, математической логике и теории алгоритмов» ,
Остальные учебники, указанные в списке рекомендованной литературы, характеризуются либо сложностью изложения, либо подробным освещением некоторых тем.
5. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
5.1 Основная литература
1. Лавров логика: учебное пособие для студ. вузов / ; под ред. . - М.: Академия, 2006.
2. Игошин В И. Математическая логика: учеб. пособие для студентов вузов / . - М.: ИНФРА-М, 2012.
3. Игошин и упражнения по математической логике и теории алгоритмов: учебное пособие для студ. вузов / . - 3-е изд., стереотип. - М.: Академия, 2007.
4. , , Математическая логика и теория алгоритмов для программистов. - М.: КНОРУС, 2013.
5. , , Математическая логика и теория алгоритмов. - М.: Научный мир, 2008.
5.2 Дополнительная литература
1. , Овчинникова логика и теория алгоритмов. М.: Инфра-М, 2004.
1. Введение в математическую логику. – М.: Наука,1976.
2. , Сукачева логика. С. П.:Лань,1998.
3. Введение в математическую логику. – М.: Наука. 1960.
4. Новиков математической логики. – М.: Наука,1973.
5. , Палютин логика. – М.: Наука, 1987.
5.3 Полнотекстовые базы данных - нет
6. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Для качественного проведения лекционных занятий по данной дисциплине используются аудитории, оснащенные мультимедийным оборудованием.
7. СЛОВАРЬ ОСНОВНЫХ ТЕРМИНОВ
Вывод формулы φ исчисления высказываний из формул φ1,…,φm исчисления высказываний – это последовательность формул ψ1,…,ψk,φ, в которой любая формула либо является аксиомой, либо принадлежит множеству формул {φ1,…,φm}, либо получается из предыдущих по правилу вывода.
Эквивалентные формулы исчисления высказываний – это формулы φ и ψ исчисления высказываний такие, что формулы φ→ψ и ψ→φ выводимы из пустого множества формул.
Алгебраической системой сигнатуры Σ называется пара 
=
где А – непустое множество и каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция) на А.
Эквивалентные формулы сигнатуры 
– это формулы φ и ψ сигнатуры исчисления высказываний такие, что формулы φ→ψ и ψ→φ истины в любой алгебраической системе сигнатуры на любом кортеже элементов их носителя этой системы.
