Рабочая программа по учебной дисциплине Элементы математической логики
Федеральное государственное автономное образовательное учреждение
высшего образования
«Нижегородский государственный университет им. Н.И. Лобачевского»
Арзамасский филиал
отделение среднего профессионального образования
(Арзамасский политехнический колледж им. В.А. Новикова)
РАБОЧАЯ ПРОГРАММА
учебной дисциплины ЕН.02 Элементы математической логики
специальность 09.02.03 Программирование в компьютерных системах
Арзамас 2015
Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта по специальности среднего профессионального образования 09.02.03 Программирование в компьютерных системах
РАССМОТРЕНО И ОДОБРЕНО
Утверждаю
на заседании методической комиссии________________________
________________________________________________________________________________________________.
Директор
Арзамасского филиала ННГУ
«___» _________________ 20____г.
«___» _________________ 20____г.
Председатель методической комиссии__________/____________/
(ф.и.о.)
_________________/С.Н. Пяткин /
Разработчики: Копьёва С.В.
СОДЕРЖАНИЕ
Паспорт программы учебной дисциплины ЕН.02 Элементы математической логики.
стр.
4
Результаты усвоения программы.
5
Структура и содержание программы учебной дисциплины ЕН.02 Элементы математической логики.
6-26
Условия реализации программы учебной дисциплины ЕН.02 Элементы математической логики.
27-28
Контроль и оценка результатов усвоения программы учебной дисциплины ЕН.02 Элементы математической логики.
29-33
1. ПАСПОРТ ПРОГРАММЫ
учебной дисциплины ЕН.02 Элементы математической логики
Область применения.
Программа учебной дисциплины ЕН.02 Элементы математической логики является элементом основной образовательной программы специальности 09.02.03 Программирование в компьютерных системах цикла ЕН.00.
Цели и задачи программы, требования к результатам усвоения:
уметь:
формулировать задачи логического характера и применять средства математической логики для их решения;
знать:
основные принципы математической логики, теории множеств и теории алгоритмов;
формулы алгебры высказываний;
методы минимизации алгебраических преобразований;
основы языка и алгебры предикатов.
Рекомендуемое количество часов на освоение программы учебной дисциплины Элементы математической логики:
максимальной учебной нагрузки обучающегося –144 час.;
обязательной аудиторной учебной нагрузки обучающегося – 96, в том числе:
практические занятия - 24 часа;
самостоятельной работы обучающегося – 48часа;
итоговая аттестация - зачёт.
2.Результаты усвоения программы
ЕН.02 Элементы математической логики
Результатом усвоения программы ЕН.02 Элементы математической логики являются общие (ОК) и профессиональные (ПК) компетенции.
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК.2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК.3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
ОК.4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
ОК.5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК.6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
ОК.7. Брать на себя ответственность за работу членов команды (подчинённых), результат выполнения заданий.
ОК.8. Самостоятельно определять задачи профессионального личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ОК.9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
ПК 1.1. Выполнять разработку спецификаций отдельных компонент.
ПК 1.2. Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля.
ПК 2.4. Реализовывать методы и технологии защиты информации в базах данных.
ПК 3.4. Осуществлять разработку тестовых наборов и тестовых сценариев.
3. СТРУКТУРА и ПРИМЕРНОЕ содержание учебной дисциплины
ЕН.02 Элементы математической логики
3.1. Объем учебной дисциплины и виды учебной работы
Вид учебной работы
Количество часов
Максимальная учебная нагрузка (всего)
144
Обязательная аудиторная учебная нагрузка (всего)
96
в том числе:
практические занятия
24
Самостоятельная работа обучающегося (всего)
48
в том числе:
тематика внеаудиторной самостоятельной работы
48
Итоговая аттестация в форме зачета
3.2. Тематический план учебной дисциплины
ЕН.02 Элементы математической логики
Коды общих и профессиональ-ных компетенций
Наименования разделов и тем рабочей программы учебной дисциплины Элементы математической логики
Всего часов
(макс. учебная нагрузка и практики)
Количество часов, отведенное на освоение учебной дисциплины
Обязательная аудиторная учебная нагрузка обучающегося
Самостоятельная работа обучаю-щегося
Всего,
часов
в т.ч. практические занятия,
часов
Всего,
часов
1
2
3
4
5
6
Раздел 1. Формулы логики
27
18
6
9
ОК.3, ПК.1.2
Тема 1.1. Логические операции.
3
2
1
ОК.5, ПК.3.4
Тема 1.2. Формулы логики.
6
4
2
2
ОК.7, ПК.2.4
Тема 1.3. Таблицы истинности.
6
4
2
2
ОК.2, ПК.1.1
Тема 1.4. ДНФ, КНФ.
3
2
1
ОК.8, ПК.1.2
Тема 1.5. Законы логики.
3
2
1
ОК.6, ПК.3.4
Тема 1.6. Равносильные преобразования.
6
4
2
2
Раздел 2. Булевы функции.
30
20
8
10
Тема 2.1. Понятие булевой функции. Проблема представления в виде формулы логики.
12
8
4
4
ОК.4, ПК.2.4
Тема 2.1.1. СДНФ. Методика представления.
6
2
2
ОК.9, ПК.1.2
Тема 2.1.2. СКНФ. Методика представления.
6
6
4
2
ОК.8, ПК.1.1
Тема 2.2. Операция двоичного сложения. Многочлен Жегалкина.
6
4
2
2
ОК.6, ПК.3.4
Тема 2.3. Полнота множества функций. Важнейшие замкнутые классы.
6
4
2
2
ОК.2, ПК.2.4
Тема 2.4. Теорема Поста.
6
4
2
Раздел 3. Основы теории множеств.
18
12
4
5
ОК.9, ПК.1.1
Тема 3.1. Основные понятия. Теоретико-множественные диаграммы.
3
2
2
1
ОК.3, ПК.2.4
Тема 3.2. Операции над множествами и их свойства.
6
4
2
2
ОК.7, ПК.3.4
Тема 3.3. Соответствие между теоретико-множественными и логическими операциями.
6
4
2
Раздел 4. Логика предикатов.
15
10
4
5
ОК.4, ПК.1.2
Тема 4.1. Основные понятия. Обычные логические операции над предикатами.
6
4
2
2
ОК.1. ПК.1.1
Тема 4.2. Кванторные операции над предикатами.
6
4
2
2
ОК.5, ПК.3.4
Тема 4.3. Бинарные отношения.
3
2
1
Раздел 5. Теория отображений и алгебра подстановок.
6
4
2
ОК.9, ПК.1.2
Тема 5.1. Отображения. Основные понятия.
3
2
1
ОК.3, ПК.1.1
Тема 5.2. Подстановки. Основные понятия.
3
2
1
Раздел 6. Алгоритмическое перечисление (генерирование) комбинаторных объектов.
18
12
6
ОК.7, ПК.1.2
Тема 6.1. Генерирование двоичных слов заданной длины.
3
2
1
ОК.5, ПК.2.4
Тема 6.2. Генерирование элементов декартова произведения множеств.
3
2
1
ОК.2, ПК.1.1
Тема 6.3. Генерирование перестановок заданной длины.
3
2
1
ОК.6, ПК.2.4
Тема 6.4. Генерирование К-элементных подмножеств данного множества.
3
2
1
ОК.9, ПК.3.5
Тема 6.5. Генерирование всех подмножеств данного множества.
6
4
2
Раздел 7. Основы алгебры вычетов.
6
4
2
ОК.4, ПК.1.1
Тема 7.1. Сравнения и их свойства.
3
2
1
ОК.3, ПК.3.4.
Тема 7.2. Вычеты.
3
2
1
Раздел 8. Простейшие криптографические шифры.
9
6
3
ОК.2, ПК.1.2
Тема 8.1. Шифры замены.
4
2
2
ОК.3, ПК.2.4
Тема 8.2. Коды Хемминга.
6
4
2
Раздел 9. Основы теории алгоритмов.
15
10
2
4
ОК.9, ПК.3.4
Тема 9.1. Вводные понятия.
3
2
1
ОК.7, ПК.2.4
Тема 9.2. Машина Тьюринга.
6
4
2
ОК.4, ПК.1.2
Тема 9.3. Сочетания машин Тьюринга.
3
2
1
ОК.8, ПК.1.1
Тема 9.4. Тьюрингов подход к понятию «алгоритм»
3
2
1
ИТОГО:
144
96
24
48
3.3. Содержание обучения по учебной дисциплине ЕН.02 Элементы математической логики
Наименование разделов и тем
Содержание обучения по дисциплине
Количест-во часов
Уровень усвоения
Знать, уметь
Структурное содержание учебного материала, лабораторные занятия и практические занятия, самостоятельная работа обучающихся, курсовая работа (проект) (если предусмотрены)
1
2
3
4
5
Раздел 1. Формулы логики
27
Тема 1.1.Введение. Логические операции.
Студент должен:
иметь представление:
о роли и месте знаний по дисциплине в процессе освоения профессиональной образовательной программы по специальности.
знать:
основные логические операции;
уметь:
обозначать логические операции.
Предмет математической логики, его основные задачи и области применения. Понятие высказывания. Основные логические операции.
2
2
Самостоятельная работа: Выполнение упражнений записи и оценки основных логических операций.
1
3
Тема 1.2. Формулы логики.
Студент должен:
знать:
понятие формулы логики;
понятие тождественно-истинной формулы;
уметь:
упрощать запись формулы.
Понятие формулы логики. Равносильные формулы. Тождественно-истинные формулы.
4
2
Практическое занятие 1: Упрощение формул логики.
2
Самостоятельная работа: Выполнение упражнений по упрощению записи формул.
2
3
Тема 1.3. Таблицы истинности.
Студент должен:
знать:
понятие таблицы истинности и методику её построения;
уметь:
строить таблицы истинности формул логики.
Таблицы истинности и методика её построения.
4
2
Практическое занятие 2: Составление таблиц истинности.
2
Самостоятельная работа: Выполнение упражнений по оценке формул логики с помощью таблиц истинности.
2
3
Тема 1.4. ДНФ, КНФ.
Студент должен:
знать:
понятие ДНФ (дизъюнктивной нормальной формы);
понятие КНФ(конъюнктивной нормальной формы);
уметь:
строить таблицы истинности для ДНФ упрощённым методом.
Понятие элементарного произведения; понятие ДНФ. Методика построения таблицы истинности для ДНФ упрощённым методом. Понятие элементарной дизъюнкции, понятие КНФ.
2
2
Самостоятельная работа: Выполнение упражнений в представлении формул логики в виде ДНФ, КНФ.
1
3
Тема 1.5. Законы логики.
Студент должен:
знать:
понятие равносильности формул логики;
законы логики;
уметь:
применять законы логики для упрощения формул
Равносильные формулы. Законы логики.
2
2
Самостоятельная работа: Выполнение упражнений по применению законов логики.
1
3
Тема 1.6. Равносильные преобразования.
Студент должен:
знать:
методику упрощения формул логики с помощью равносильных преобразований;
уметь:
упрощать формулы логики с помощью равносильных преобразований.
Методика упрощения формул логики с помощью равносильных преобразований.
4
2
Практическое занятие 3: Упрощение формул логики с помощью равносильных преобразований.
2
3
Самостоятельная работа: Выполнение равносильных преобразований формул логики.
2
3
Раздел 2. Булевы функции.
30
Тема 2.1. Понятие булевой функции. Проблема представления в виде формулы логики.
12
Тема 2.1.1. СДНФ. Методика представления.
Студент должен:
знать:
понятие булевой функции и способы её заданий;
понятие СДНФ совершенной дизъюнктивной нормальной формы);
методику представления булевой функции в виде СДНФ;
уметь:
представлять булеву функцию в виде СДНФ.
Понятие булевой функции. Способы задания булевой функции. Понятие совершенной ДНФ. Методика представления булевой функции в виде СДНФ.
2
2
Самостоятельная работа: Выполнение упражнений в составлении СДНФ.
2
3
Тема 2.1.2. СКНФ. Методика представления.
Студент должен:
знать:
понятие совершенной КНФ;
методику представления булевой функции в виде СКНФ (совершенной конъюнктивной нормальной формы);
понятие ДНФ;
методику представления булевой функции (N
· 3) в виде минимальной ДНФ;
уметь:
представлять булеву функцию в виде совершенной КНФ;
представлять булеву функцию (N
· 3) в виде минимальной ДНФ.
Понятие совершенной КНФ. Методика представления булевой функции в виде совершенной КНФ. Понятие минимальной ДНФ. Методика представления булевой функции (N
· 3) в виде минимальной ДНФ графическим методом.
6
2
Практическое занятие 4: Представление булевой функции в виде СКНФ, СДНФ.
4
3
Самостоятельная работа: Выполнение упражнений в представлении булевой функции в виде СКНФ, СДНФ.
2
3
Тема 2.2. Операция двоичного сложения. Многочлен Жегалкина.
Студент должен:
знать:
операцию двоичного сложения и её свойства;
методику представления булевой функции в виде многочлена Жегалкина;
уметь:
представлять булеву функцию в виде многочлена Жегалкина.
Операция двоичного сложения и её свойства. Многочлен Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина.
4
2
Практическое занятие 5: Представление булевой функции в виде многочлена Жегалкина.
2
3
Самостоятельная работа: Выполнение упражнений в представлении булевой функции в виде многочлена Жегалкина.
2
3
Тема 2.3. Полнота множества функций. Важнейшие замкнутые классы.
Студент должен:
знать:
понятие выражения одних булевых функций через другие;
понятие полноты множества функций;
понятие замкнутого класса, важнейшие замкнутые классы;
уметь:
проверять булеву функцию на принадлежность Т0, Т1, S, L, M.
Проблема возможности выражения одних булевых функций через другие. Полнота множества функций. Понятие замкнутого класса функций. Важнейшие замкнутые классы: Т0, Т1, S, L, M.
4
2
Практическое занятие 6: Проверка булевых функций на принадлежность к классам: Т0, Т1, S, L, M..
2
3
Самостоятельная работа: Выполнение упражнений по проверке булевых функций на принадлежность к важнейшим замкнутым классам.
2
3
Тема 2.4. Теорема Поста.
Студент должен:
знать:
знать теорему Поста;
методику проверки множества булевых функций на полноту;
уметь:
проверять множество булевых функций на полноту;
проверять, является ли функция шефферовской.
Теорема Поста. Шефферовские функции. Функция Шеффера и функция Пирса как простейшие шефферовские функции.
4
2
Самостоятельная работа: Проверка множества булевых функций на полноту.
2
3
Раздел 3. Основы теории множеств.
18
Тема 3.1. Основные понятия. Теоретико-множественные диаграммы.
Студент должен:
знать:
понятие множества;
понятие подмножества; формулу количества подмножеств конечного множества;
уметь:
применять теоретико-множественные диаграммы.
Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество; количество подмножеств конечного множества.
Теоретико-множественные диаграммы.
4
2
Самостоятельная работа: Решение задач с помощью теоретико-множественных диаграмм.
2
3
Тема 3.2. Операции над множествами и их свойства.
Студент должен:
знать:
операции над множествами и их свойства;
формулу количества элементов в объединении нескольких конечных множеств.
уметь:
выполнять операции над множествами;
решать задачи на подсчёт количества элементов с использованием формул.
Операции над множествами и их свойства. Формула количества элементов в объединении конечных множеств. Декартово произведение множеств. Декартова степень множества.
4
2
Практическое занятие 7: Операции над множествами.
2
Самостоятельная работа: Выполнение упражнений на теоретико-множественные операции.
2
3
Тема 3.3. Соответствие между теоретико-множественными и логическими операциями.
Студент должен:
знать:
соответствие между теоретико-множественными и логическими операциями;
методику проверки теоретико-множественных соотношений с помощью формул логики;
уметь:
проверять теоретико-множественные соотношения с помощью формул логики.
Соответствие между теоретико-множественными и логическими операциями. Методика проверки теоретико-множественных соотношений с помощью формул логики.
4
2
Практическое занятие 8: Решение задач с помощью кругов Эйлера.
2
Самостоятельная работа: Выполнение упражнений по проверке теоретико-множественных соотношений с помощью формул логики.
2
3
Раздел 4. Логика предикатов.
15
Тема 4.1. Основные понятия. Обычные логические операции над предикатами.
Студент должен:
знать:
понятие предиката, понятия области определения и области истинности предиката;
логические операции над предикатами;
уметь:
записывать область истинности предиката;
выполнять логические операции над предикатами.
Понятие предиката. Область определения и область истинности предиката. Обычные логические операции над предикатами.
4
2
Практическое занятие 9: Логические операции над предикатами.
2
Самостоятельная работа: Выполнение упражнений по записи области истинности предикатов.
2
3
Тема 4.2. Кванторные операции над предикатами.
Студент должен:
знать:
кванторные операции над предикатами;
понятие предикатной формулы;
методику построения отрицаний к предикатам, содержащим кванторные операции;
уметь:
определять логическое значение формулы алгебра предикатов;
строить отрицания к предикатам, содержащим кванторные операции;
формализовывать предложения с помощью логики предикатов.
Кванторные операции над предикатами. Предикатная формула. Построение отрицаний к предикатам, содержащим кванторные операции. Формализация предложений с помощью логики предикатов.
4
2
Практическое занятие 10: Определение логического значения формул алгебры предикатов. Формализация предложений с помощью логики предикатов.
2
3
Самостоятельная работа: Построение отрицаний к предикатам, содержащим кванторные операции.
2
3
Тема 4.3. Бинарные отношения.
Студент должен:
знать:
понятие бинарного отношений;
понятие рефлексивного, симметричного, транзитивного бинарного отношения;
понятие отношения эквивалентности;
уметь:
строить диаграмму бинарного отношения;
исследовать бинарные отношения на рефлексивность, симметричность, транзитивность;
выделять классы эквивалентности.
Понятие бинарного отношения. Диаграммы бинарного отношения. Рефлексивные, симметричные, транзитивные бинарные отношения. Отношение эквивалентности; теорема о разбиении множества на классы эквивалентности.
2
·