МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

УТВЕРЖДАЮ

Декан ФВТ__________

«_____» ___________________ 2015 г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Б 1.1.20 Математическая логика

Направление подготовки

02.03.03 «Математическое обеспечение и администрирование информационных систем»

Профиль подготовки

«Администрирование информационных систем»

Квалификация выпускника бакалавр

Форма обучения очная

Пенза, 2015

1. Цели освоения дисциплины

Целью освоения дисциплины «Математическая логика» является изучение формальных математических систем и доказуемость математических суждений. Знания и умения, полученные при изучении курса, позволяет сформировать у студентов систему навыков, позволяющих эффективно разрабатывать программные продукты и эксплуатировать разнообразные программные комплексы.

2. Место дисциплины в структуре ОПОП

Дисциплина «Математическая логика» относится к базовому циклу дисциплин (Б 1.1). Изучение дисциплины «Математическая логика» опирается на знания и навыки, полученные студентами при изучении следующих дисциплин:

1.  «Информатика»

2.  «Вычислительная математика»

3.  «Математический анализ»

Компетенции, приобретенные в ходе изучения дисциплины, готовят студента к выполнению выпускной квалификационной работы.

3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Математическая логика»

Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВО по данному направлению:

НЕ нашли? Не то? Что вы ищете?

Коды

Компетенции

Наименование компетенции

Структурные элементы компетенции

(в результате освоения дисциплины обучающийся должен знать, уметь, владеть)

1

2

3

ОПК-7

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

Знать: формальные логические системы, их различие и границы применения.

Уметь: использовать аппарат математической логики в анализе информационных систем.

Владеть: Навыками использования программных систем, реализующих логики различных уровней.

4. Структура и содержание дисциплины «Математическая логика»

4.1. Структура дисциплины

Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.

№

п/п

Наименование

разделов и тем

дисциплины (модуля)

Семестр

Недели семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость

(в часах)

Формы текущего

контроля

успеваемости

(по неделям

семестра)

Аудиторная

Работа

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

работа

Всего

Лекция

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

занятия

Всего

Подготовка к

лабораторным

работам

Подготовка

к экзамену

Защита

лабораторной

работы

1

Раздел 1. Основные понятия, история возникновения логики как науки.

4

1-3

8

4

4

18

8

10

1.1

Тема 1.1. Введение.

4

1

1

2

1.2

Тема 1.2. Многообразие логик. Методы рассуждений (индукция и дедукция).

4

1

1

2

4

2

1.3

Тема 1.3. Логическая алгебра. Законы исключения третьего и противоречия.

4

2

1

2

4

2

1.4

Тема 1.4. Математическая логика. Аксиоматические теории.

4

3

1

4

2

Раздел 2. Логика высказываний.

4

4

20

4

16

22

14

8

2.1

Тема 2.1. Синтаксис и Семантика логики высказываний. Функциональная полнота. Выполнимые формулы и тавтологии.

4

4

1

2

2

2

2.2

Тема 2.2. Исчисление высказываний.

4

4

1

4

4

2

2.3

Тема 2.3. Нормальные формы. Правила вывода алгебры логики. Использование алгоритмов минимизации формул алгебры логики.

2

10

8

4

3

Раздел 3. Логика предикатов

4

5-6

15

3

12

20

12

8

3.1

Тема 3.1. Синтаксис и Семантика логики предикатов

4

5

1

2

4

2

3.3

Тема 3.3. Алгебра предикатов. Законы алгебры предикатов. Выполнимость и общезначимость логики предикатов. Предваренная нормальная форма. Исчисление предикатов.

4

6

1

6

4

4

3.4

Тема 3.4. Логическое программирование.

4

6

1

4

4

2

4

Раздел 4. Нечеткая логика.

4

7-8

19

5

14

30

20

10

4.1

Тема 4.1.Теоретико-множественное обоснование. Операции над нечеткими множествами.

4

8

1

2

2

2

4.2

Тема 4.2. Нечеткие переменные и нечеткие функции. Тождества функций от нечетких переменных.

4

9

1

4

6

4

4.3

Тема 4.3.Анализ логических функций от нечетких переменных.

4

9

2

4

6

2

4.4

Тема 4.4.Обзор программных систем на основе аппарата нечеткой логики.

4

9

1

4

6

2

5

Раздел 5. Теория алгоритмов.

4

10-11

10

2

8

18

6

12

5.1

Тема 5.1. Операторы: суперпозиции, примитивной рекурсии и наименьшего корня. Машина Тьюринга. Тезис Черча.

4

10

1

8

6

6

5.2

Тема 5.2. Классы задач P и NP.

4

11

1

6

Подготовка к зачету

Подготовка к экзамену

4

Общая трудоемкость, в часах

72

18

54

108

Промежут. аттестац.

Форма

Семестр

Зачет

4

Экзамен

4

4.2. Содержание дисциплины

4.2.1.Содержание лекционного курса

1.  Основные понятия, история возникновения логики как науки.

1.1  Введение.

Задачи логики. Многообразие логик. Философские и математические аспекты логики. Логические операции: определение, классификация, доказательство, опровержение. Неформальная, формальная, символическая и диалектическая логика.

1.2  Многообразие логик. Методы рассуждений (индукция и дедукция).

Многообразие логик. Процесс логического вывода на основе перехода от частного положения к общему. Частное заключение, выводимое из общего. Дилеммы. Modus ponens («правило вывода»).

1.3  Логическая алгебра. Законы исключения третьего и противоречия.

Логические операции над высказываниями. Двоичная логика. Высказывания. Операции над высказываниями. Закон исключённого третьего в математической логике. Парадокс лжеца.

1.4  Математическая логика. Аксиоматические теории.

Формальная система. Язык или сигнатура формальной теории. Полнота, независимость и разрешимость теорий. Теорема Гёделя о неполноте

2.  Логика высказываний.

2.2  Синтаксис и семантика логики высказываний. Функциональная полнота. Выполнимые формулы и тавтологии.

Синтаксические и семантические аналоги логики высказываний в естественных языках. Смысловая интерпретация предложений и формул логики высказываний. Общезначимые, выполнимые и невыполнимые формулы. Тавтологии. Функциональная полнота.

2.3  Исчисление высказываний.

Алфавит исчисления высказываний. Логические связки. Формулы исчисления высказываний. Система аксиом исчисления высказываний. Метод таблиц истинности.

2.4  Нормальные формы. Использование алгоритмов минимизации формул алгебры логики.

Правила вывода алгебры логики. СДНФ. СКНФ. Сокращенные формы. Тупиковые формы. Минимальные формы. Метод Квайна. Метод Импликантных таблиц. Диаграммы Вейча. Использование математического аппарата логики высказываний при проектировании средств вычислительной техники.

3.  Логика предикатов.

3.1  Синтаксис и Семантика логики предикатов.

Понятие ``предикат''. Язык логики предикатов. Расширение логики высказываний. Правила построения выражений. Способы приписывания выражениям некоторого формального значения. Сигнатуры. Арность. Логические операции. Кванторы. Свойства логики первого порядка. Логика предикатов как формальная модель рассуждений в математике.

3.2  Алгебра предикатов. Законы алгебры предикатов. Выполнимость и общезначимость логики предикатов. Предваренная нормальная форма. Исчисление предикатов.

Алгебра предикатов. Предваренная нормальная форма. Алгоритм приведения формулы к виду ПНФ. Сколемовская стандартная форма. Алгоритм Скомолева. Исчисление предикатов. Интерпретация формул. Правила вывода. Правила подстановки заключения. Правила введения и удаления кванторов. Правила заключения. Метод дедуктивного вывода. Принцип резолюции. Проблемы в исчислении предикатов. Метод дедуктивного вывода. Принцип резолюции. Проблемы в исчислении предикатов. Тезис Черча. Проблемы в исчислении предикатов.

3.3  Логическое программирование.

Логическое программирование. Системы искусственного интеллекта и языки программирования на основе логики предикатов. Достоинства и недостатки систем на основе языков логического программирования. Экспертные системы на основе языков логического программирования.

4.  Нечеткая логика.

4.1  Теоретико-множественное обоснование. Операции над нечеткими множествами.

Нечеткие множества. Операции над нечеткими множествами. Графическая интерпретация результатов операций над нечеткими множествами. Универсум в нечетких множествах.

4.2  Нечеткие переменные и нечеткие функции. Тождества функций от нечетких переменных.

Нечеткие переменные и функции от нечетких переменных. Логические связки в функциях от логических переменных. Тождества функций от нечетких переменных. Таблицы значений функций нечетких переменных. Связь булевой логики и нечеткой логики. Приведенные формы функций от нечетких переменных.

4.3  Анализ логических функций от нечетких переменных.

Анализ таблиц значений функций нечеткой логики. Лексикографическая процедура. Алгоритмы фазификации. Алгоритмы дефазификации Сугено и Мамдани.

4.4  Обзор программных систем на основе аппарата нечеткой логики.

Программные системы на основе нечеткой логики. Использование аппарата нечеткой логики в системах Искусственного интеллекта. Гибридные интеллектуальные системы.

5.  Теория алгоритмов.

5.1  Алгоритмическая разрешимость.

Формальное доказательство алгоритмической неразрешимости. Сравнительной оценки качества алгоритмов. ёделя о неполноте формальных систем. Понятие нормального алгоритма. Модели вычислений. Машина Тьюринга. Операторы: суперпозиции, примитивной рекурсии и наименьшего корня.

5.2  Классы задач P и NP.

Теория сложности вычислений. Оценка сложности решения отдельных задач. NP-полные задачи. Иерархия классов сложности. Вопрос о равенстве классов сложности P и NP.

4.2.2. Перечень и содержание лабораторных занятий.

№ п/п

№

раздела

Наименование лабораторных работ

Кол. часов

1

1

Доказательство формул логики высказываний.

4

2

2

Минимизация логических функций методом Квайна

10

3

2

Минимизация логических функций методом Импликантных таблиц и диаграмм Вейча.

6

4

3

Получение предваренных нормальных форм логики предикатов

12

5

4

Построение нечеткой экспертной системы в среде МАТЛАБ

14

6

5

Машина Тьюринга.

8

5. Образовательные технологии

-  Чтение трех лекций по дисциплине проводится с использованием мультимедийного компьютерного проектора с раздачей демонстрируемых слайдов комментарий.

-  При изучении материалов лабораторного практикума использовать электронные образовательные ресурсы кафедры САПР.

-  При самостоятельной работе используются материалы сайта «Интернет-Университет Информационных Технологий (www. intuit. ru).

6. Учебно-методическое обеспечение самостоятельной работы бакалавров

Оценочные средства для текущего контроля успеваемости,

промежуточной аттестации по итогам освоения дисциплины

6.1. План самостоятельной работы бакалавров

№ нед.

Тема

Вид самостоятельной работы

Задание

Рекомендуемая литература

Количество

Тема 1.2. Многообразие логик. Методы рассуждений (индукция и дедукция).

Подготовка к аудиторным и лабораторным занятиям

Изучить основные принципы построения рассуждений на основе индуктивных и дедуктивных заключений.

Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254), Основная и дополнительная литература.

18

Тема 2.2. Исчисление высказываний.

Подготовка к аудиторным и лабораторнымзанятиям

Изучить синтаксис и семантику логики выссказываний.

Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254), Основная и дополнительная литература.

22

Тема 3.3. Алгебра предикатов. Законы алгебры предикатов. Выполнимость и общезначимость логики предикатов. Предваренная нормальная форма. Исчисление предикатов.

Подготовка к аудиторным занятиям

Изучить правила получения приведенных форм языка предикатов.

Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254), Основная и дополнительная литература.

20

Тема 4.1.

Теоретико-множественное обоснование. Операции над нечеткими множествами.

Подготовка к аудиторным занятиям

Изучить операции над нечеткими множествами.

Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254), Основная и дополнительная литература.

14

Тема 4.4.

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

Подготовка к лабораторным занятиям

Проанализировать сравнительные характеристики и возможности программных систем на основе нечеткой логики.

Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254), Основная и дополнительная литература.

16

Тема 5.1. Операторы: суперпозиции, примитивной рекурсии и наименьшего корня. Машина Тьюринга. Тезис Черча.

Подготовка к лабораторным занятиям

Рассмотреть решение задач поиска алгоритма решения на основе машины Тьюринга. Самостоятельная подготовка к лекциям.

Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254), Основная и дополнительная литература.

18

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

Планируются следующие виды самостоятельной работы (внеаудиторной) относятся:

-  подготовка к лабораторным работам занятиям,

-  оформление отчётов по лабораторным работам,

-  работа с конспектом лекций и изучение рекомендованной литературы при подготовке к экзаменам.

6.3. Материалы для проведения текущего и промежуточного контроля знаний бакалавров

Контроль освоения компетенций

№ п\п

Вид контроля

Контролируемые разделы

Компетенции, компоненты которых контролируются

1

Текущий: опрос во время лекционных занятий

Промежуточный: зачет

Раздел 1. Основные понятия, история возникновения логики как науки.

ОПК-7

2

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

Промежуточный: зачет

Раздел 2. Логика высказываний.

ОПК-7

3

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

Промежуточный: зачет

Раздел 3. Логика предикатов

ОПК-7

4

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

Промежуточный: зачет

Раздел 4. Нечеткая логика.

ОПК-7

5

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

Промежуточный: зачет

Раздел 5. Теория алгоритмов.

ОПК-7

6

Промежуточный: зачет

1-6

ОПК-2,ОПК-10

Контроль освоения компетенции выполняется:

для компетенции (ОПК-8) ‑ путем оценки результатов лабораторных работ.

.

Примерный перечень вопросов к экзамену

Исторические аспекты появления логики как математической науки. Правила вывода логических формул. Препозиционные логические связки. Типы логических формул. Интерпретация результата высказываний. Доказательства через индукцию и дедукцию. Логическая алгебра. Законы исключения третьего и противоречия Интерпретация естественных языковых конструкции в логике высказываний. Синтаксис и Семантика логики высказываний. Функциональная полнота. Выполнимые общезначимые формулы и тавтологии. Исчисление высказываний. Нормальные формы. Правила вывода алгебры логики. Использование алгоритмов минимизации формул алгебры логики. Минимизация формул методом Квайна. Минимизация формул методом импликантных таблиц. Минимизация формул методом диаграмм Вейча. Понятие ``предикат''. Язык логики предикатов. Расширение логики высказываний. Правила построения выражений логики предикатов. Способы приписывания выражениям некоторого формального значения. Сигнатуры. Арность. Логические операции. Кванторы. Свойства логики первого порядка. Логика предикатов как формальная модель рассуждений в математике. Алгебра предикатов. Законы алгебры предикатов. Выполнимость и общезначимость логики предикатов. Предваренная нормальная форма. Исчисление предикатов. Алгебра предикатов. Предваренная нормальная форма. Алгоритм приведения формулы к виду ПНФ. Сколемовская стандартная форма. Алгоритм Скомолева. Исчисление предикатов. Интерпретация формул. Правила вывода. Правила подстановки заключения. . Правила введения и удаления кванторов. Правила заключения. Метод дедуктивного вывода. Принцип резолюции. Проблемы в исчислении предикатов. Метод дедуктивного вывода. Принцип резолюции. Проблемы в исчислении предикатов. Тезис Черча. Системы искусственного интеллекта и языки программирования на основе логики предикатов. Достоинства и недостатки систем на основе языков логического программирования. Операции над нечеткими множествами. Нечеткие переменные и нечеткие функции. Тождества функций от нечетких переменных. Анализ логических функций от нечетких переменных. Операторы: суперпозиции, примитивной рекурсии и наименьшего корня. Машина Тьюринга. Тезис Черча. Классы задач P и NP. Примеры.

7. Учебно-методическое и информационное обеспечение

дисциплины «Математическая логика»

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

Математическая логика и теория алгоритмов: учеб. Пособие для студ. учреждений высш. проф. образования./ , . - М.: Издательский центр «Академия» 2013.-416 с. Математическая логика и теория алгоритмов: учеб. Пособие для студентов высш. Учеб. pаведений/ 4-е издание, стер.-М.:Издательский центр «Академия», 2010.-448с. Г85 Математическая логика и теория алгоритмов для программистов: учебное пособие / , . — М. : КНОРУС, 2014. — 206 с.

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

еория возможностей. Приложения к представлению знаний в информатике. / Пер. с фр.-М.: Радио и связь. 1990г. - 287с. ведение в теорию нечетких множеств. /Пер. с фр. - М.: Радио и связь. - 1982 - 432с. , основы вычислительной техники: Учебное пособие для электротехнических спец. Вузов.- М.: Высшая школа.1988 - 311с. омбинаторные алгоритмы. Теория и практика./ Пер. с англ. - М.: Мир. 1980 - 475с. Коршунов основы кибернетики / Учебное пособие. - М.: Энерг. Атом издает. 1987 - 496с. Представление и использование знаний. / Пер с яп. - М.: Мир. 1989.- 220с. Дискретная математика./ Под ред. Яблонского. - М.:Наука.- 1974- 311с. Заде нечетких множеств. Проблемы передачи информации. . 1. 1966. – С. 37 – 44 Искусственный интеллект.– В 3–х кн. Кн.1. Системы общения и экспертные системы: Справочник /Под ред. .–М.:Радио и связь, 1990.– 464 с.

в) программное обеспечение и Интернет-ресурсы

1.  С++, ПАСКАЛЬ, Матлаб.

2.  Учебно-методические материалы и электронные учебные пособия с раздела файл-сервера кафедры САПР (диски М и Т сервер cad-filer (IP 172.16.72.254)

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

Лекционные занятия проводятся в аудитории, оснащенной компьютерным проектором, проекционным экраном, шторами, сетью электропитания 220 В.

Лабораторные занятия проводятся в классе, оснащенным ПЭВМ с операционной системой Windows XP или старше.

Рабочая программа дисциплины «Математическая логика» составлена в соответствии с требованиями ФГОС ВО с учетом рекомендаций ПрООП по направлению подготовки 02.03.03 «Математическое обеспечение и администрирование информационных систем»

Программу составила:

,

к. т.н., доцент кафедры «САПР» ___

Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.

Программа одобрена на заседании кафедры «САПР»

Протокол № от «____» _ _____ 2015 года

Зав. кафедрой САПР _________________________________ .

Программа одобрена методической комиссией факультета вычислительной техники

Протокол № ___ от «____» _ _____ 2015 года

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

Сведения о переутверждении программы на очередной учебный год и регистрации изменений

Учебный

год

Решение кафедры

(№ протокола, дата, подпись зав. кафедрой)

Внесенные изменения

Номера листов (страниц)

заменен-

ных

новых

аннулиро-ванных