Рабочая программа учебной дисциплины "Элементы математической логики"
рабочая программа на тему

ОДОБРЕНА

Предметной (цикловой) комиссией

Протокол №___   от _______ 2012 г.

Председатель:

Разработана на основе Федерального

государственного образовательного стандарта по специальности среднего
профессионального образования (далее –СПО) 230111 «Компьютерные сети»

Утверждаю:

Заместитель директора по учебно-методической работе:

Авторы: Мещерякова Анна Владимировна, преподаватель спец. дисциплин

Рецензенты:

1.Паспорт рабочей программы учебной дисциплины…………………........4

2.Структура и примерное содержание учебной дисциплины….……….…..5

3.Условия реализации рабочей программы учебной дисциплины.…...…..11

4.Контроль и оценка результатов освоения учебной дисциплины.……….12

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

144

Обязательная аудиторная учебная нагрузка (всего)

96

в том числе:

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

-

практические занятия

48

контрольные работы

10

Самостоятельная работа обучающегося (всего)

48

Итоговая аттестация в форме дифференцированного зачета

в этой строке часы не указываются

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

Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся

Объем

часов

Уровень

усвоения

1

2

3

4

Введение в предмет

2

Введение.

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

2

1

Раздел 1.

Теория множеств

32

Тема 1.1. Общие понятия теории множеств. Язык теории множеств.

Понятие «множество», элемент множества. Способы задания множеств: указание характеристического свойства, перечисление элементов. Пустое множество.

Изображение множеств (круги Эйлера, диаграммы Венна). Понятие «подмножества». Универсальное множество. Равные множества. Мощность множества.

2

2

Практическое занятие №1

2

Изображение множеств с помощью кругов Эйлера.

Тема 1.2. Основные операции над множествами

 Введение операций над множествами. Свойства операций над множествами.

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

Законы пересечения и объединения множеств. Прямое (декартово) произведение множеств. Основные тождества алгебры множеств.

4

2

Практическая работа №2 ,3,4

6

Законы пересечения и объединения множеств. Доказательство основных тождеств алгебры множеств

Декартово произведение множеств. Изображение декартово произведения множеств на координатной плоскости

Решение задач с использованием аппарата теории множеств.

Контрольная работа по темам 1.1, 1.2.

2

Тема 1.3. Соответствие между множествами. Отображения.

Основные понятия: соответствие между множествами, образ и прообраз элемента, множество значений, область определений, обратное соответствие.

 Задание соответствий: аналитический, табличный, графический.

Виды отображений: взаимно-однозначное, обратное отображение, равносильное, эквивалентное, равномощные. Композиция функций. Тождественное отображение.

4

2

Практическая работа №5,6

4

Составление отношений и построение графиков. Определение выполнимости свойств отношений на заданных множествах.

Установление взаимно-однозначного соответствия.

Самостоятельная работа обучающихся по разделу 1: 

1. Изучить свойства счетных множеств.
   
2. Изучить аксиомы множеств, алгоритм доказательства тождества множеств.
   
3. Доказать законы двойственности, законы поглощения
   
4. Элементы теории отображения и алгебры подстановок

8

Раздел 2.

Формулы логики

34

Тема 2.1. Логические операции. Формулы логики. Таблица истинности.

Алгебра логики.

Высказывания и высказывательные формы. Отрицание высказываний.

Конъюнкция и дизъюнкция. Союзы языка и логические операции (Язык и логика).

 Импликация, эквиваленция, сумма по модулю два.

 Таблицы истинности.

4

2

Практическая работа №7, 8, 9

6

Составление простых и составных высказываний.

Формализация высказывания.

Составление таблиц истинности логических выражений.

Тема 2.2.  Законы логики. Равносильные преобразования.

Формулы алгебры логики. Составление таблиц истинности для формул. Классификация формул алгебры логики. Равносильные преобразования. Упрощение формул.

 Закон двойственности в алгебре логики.

4

2

Практическая работа №10, 11, 12, 13

8

Составление таблиц истинности для формул логики. Выявление эквивалентных логических выражений.

Доказательство законов алгебры логики.

Тождественные преобразования формул с использованием законов алгебры логики.

Решение текстовых задач с использованием алгебры логики.

Контрольная работа по разделу 2

2

Самостоятельная работа обучающихся по разделу 2:

1. Определение понятий. Операции над понятиями. Деление понятий. Классификация понятий.

2. Составить конспект по теме: «Логика вопросов и ответов»

3. Составление таблиц истинности логических выражений

4. Решение задач на минимизацию логических выражений с помощью алгебры логики.

5. Решить логическую задачу.

10

Раздел 3.

Булевы функции

44

Тема 3.1. Функции алгебры логики.

Логические функции. Равенство функций. Формулы. Булевы функции одной переменной: тождественный нуль, тождественная единица, отрицание. Булевы функции двух переменных.
Способы задания булевых функций. Соглашение о написании формул.

2

1

Тема 3.2. Минимизация булевых функций

Разложение функций по переменным. Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ). Построение нормальных форм для заданной булевой функции.

Приведение формул к совершенным нормальным формам с помощью равносильных преобразований.

Упрощение формул логики до минимальной ДНФ.

Карты Карно.

4

2

Практическая работа №14, 15, 16, 17

8

Представление функций в современных нормативных формах.

Представление функций в виде СДФН и СКНФ

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

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

Контрольная работа по теме 3.2.

2

Тема 3.3. Основные классы функций. Полнота множества. Теореме Поста.

Функционально замкнутые классы. Канонический полином Жегалкина. Функциональная замкнутость класса функций алгебры логики.

Классы функций: класс функций, сохраняющих константу 0, класс функций, сохраняющих константу 1, класс самодвойственных функций, класс линейных функций, класс монотонных функций.

Функционально полные системы функций. Критерий полноты системы функций.

Теорема Поста-Яблонского.

6

2

Практические работы 18, 19, 20

6

Проверка полноты множества функций.

Использования теоремы Поста.

Выявление связи теоретико-множественных операций с логическими.

Самостоятельная работа обучающихся по разделу 3:  

1. Найти алгоритм составления карты Карно для булевых функций трех (четырех переменных).
   
2. Указать связь булевых функций с суммой по модулю два.
   
3. Составить конспект по теме: «Логические схемы».
   
4. Выполнение упражнений на составление СДНФ и СКНФ.
   
5. Выполнение упражнений на составление карты Карно для логических функций
   
6. Изучить примеры доказательства полноты системы, например {+, V, 1}, составив таблицы Поста.
   
7. Проверить, являются ли функционально замкнутыми классы:
       а) S - класс самодвойственных функций;
   

б) L - класс линейных функций;

в) М - класс монотонных функций.

16

Раздел 4.

Предикаты

10

Тема 4.1. Предикаты

Предикаты и высказывательные формы. Множество истинности  предиката. Равносильность и следование предикатов.

2

2

Практическая работа №21, 22

4

Применение аппарата алгебры высказываний для работы с предикатами.

Исчисление предикатов, выполнение операций над предикатами.

Самостоятельная работа обучающихся по разделу 4:

 1. Составление конспекта по теме: «Кванторы»

2. Умозаключения как форма мышления. Дедуктивные умозаключения и их виды.

4

Раздел 5.

Элементы теории алгоритмов

22

Тема 5.1. Элементы теории алгоритмов.

Алгоритм. Интуитивное представление об алгоритме. Основные требования к алгоритмам. Основная терминология теории алгоритмов.

  Математические модели алгоритмов. Нормальный алгоритм Маркова. Машины Тьюринга.

6

2

Контрольная работа по разделу 5.

2

Практические работы №23, 24.

4

Чтение и выполнение программ, написанных для машины Тьюринга

Построение программ для машины Тьюринга

Самостоятельная работа обучающихся по разделу 5.

1. Выписать основные теоремы теории алгоритмов
   
2. Составить конспект по теме: «Математическая модель алгоритма Чёрчя»
   
3. Выписать алгоритмически неразрешимые проблемы.
   
4. Привести примеры работы любых 3-х элементарных машин Тьюринга.
   
5. Решение задач на составление программ для машин Тьюринга.

10

Всего:

Аудиторная учебная нагрузка

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

144

96

48

Результаты обучения

(освоенные умения, усвоенные знания)

Формы и методы контроля

и оценки результатов обучения

умения:

формулировать задачи логического характера и применять средства математической логики для их решения

практические занятия, внеаудиторная самостоятельная работа

знания:

формулы алгебры высказываний;

практические занятия, внеаудиторная самостоятельная работа.

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

практические занятия, внеаудиторная самостоятельная работа, контрольная работа

основы языка и алгебры предикатов

практические занятия, внеаудиторная самостоятельная работа, контрольная работа