|
Элементы математической логики
Календарно-тематический план по дисциплине "Элементы математической логики" Специальность 09.02.02 Компьютерные сети (базовая подготовка)
Структура КТП:
- № занятия
- Наименование разделов, тем
- Количество часов
- Вид занятий
- Материально- техническое обеспечение занятия, Интернет- ресурсы
- Задания для обучающихся
- Виды внеаудиторной (самостоятельной) работы
- Основная и дополнительная литература
Наименование разделов, тем
Введение.
История возникновения и предмет математической логики. Ее цели, задачи и связь с дисциплинами профессионального цикла.
Раздел 1. Теория множеств.
- Тема 1.1. Общие понятия теории множеств.
Понятие множества, элемент множества. Способы задания множеств: указание характеристического свойства, перечисление элементов. Пустое множество.
Подмножество. Количество подмножеств конечного множества. Способы задания множеств.
Изображение множеств (круги Эйлера, диаграммы Венна). Понятие «подмножества». Универсальное множество. Равные множества. Мощность множества.
Практическое занятие №1.
Решение задач на определение видов множеств, вычисление количества подмножеств конечных множеств, отыскание элементов множеств.
- Тема 1.2. Основные операции над множествами и их свойства.
Введение операций над множествами. Свойства операций над множествами.
Теоретико-множественные операции и их связь с логическими операциями: включение, объединение, пересечение, разность, дополнение множеств.
Практическое занятие №2. Операции над множествами. Изображение операций над множествами с помощью кругов Эйлера.
Законы пересечения и объединения множеств. Прямое (декартово) произведение множеств. Основные тождества алгебры множеств.
Кортежи. Декартово произведение множеств. Декартова степень множества.
Практическое занятие №3. Решение задач на выполнение теоретико-множественных операций.
- Тема 1.3. Отношения. Бинарные отношения и их свойств. Подстановки.
Основные понятия: соответствие между множествами, взаимно-однозначные соответствия, образ и прообраз элемента, множество значений, область определений, обратное соответствие.
Виды отношений. Графики отношений. Задание соответствий: аналитический, табличный, графический.
Составление отношений и построение графиков. Определение выполнимости свойств отношений на заданных множествах.
Виды отображений: взаимно-однозначное, обратное отображение, равносильное, эквивалентное, равномощные. Тождественное отображение.
Бинарные отношения и их свойства. Решение задач на составление отношений, установление свойств и графическое изображение отношений.
Подстановки. Произведение подстановок. Свойства умножения подстановок.
Натуральная степень подстановки. Порядок подстановки.
Практическое занятие №4. Решение задач на умножение, возведение в степень и определение порядка подстановок.
Раздел 2. Алгебра логики.
- Тема 2.1. Высказывания. Логические операции. Формулы логики. Таблица истинности.
Понятие высказывания. Простые и сложные высказывания.
Логические величины, операции, выражения.
Практическое занятие №5. Выполнение основных логических операций над высказываниями.
Конъюнкция и дизъюнкция.
Таблица истинности для формул алгебры логики.
Импликация и эквивалентность.
Практическое занятие №6. Построение сложных высказываний и таблиц истинности для них.
Проверка логических операций с помощью теоретико-множественных соотношений.
Таблица истинности для формул алгебры логики и методика её построения. Тождественно-истинные формулы.
Практическое занятие №7. Построение таблиц истинности логических выражений.
- Тема 2.2. Законы логики. Равносильные преобразования.
Классификация формул алгебры логики.
Равносильные преобразования.
Практическое занятие № 8. Доказательство законов алгебры логики.
Методика упрощения формул логики с помощью равносильных преобразований.
Практическое занятие №9. Тождественные преобразования формул с использованием законов алгебры логики.
Понятие минимизации формул логики.
Минимизация формул логики.
Практическое занятие №10. Упрощение формул логики с помощью равносильных преобразований.
- Тема 2.3. Дизъюнктивная и конъюнктивная нормальные формы.
Понятие нормальных форм.
Понятие дизъюнктивной нормальной формы (ДНФ).
Понятие конъюнктивной нормальной формы (КНФ).
Построение нормальных форм для заданной булевой функции.
Построение таблиц истинности для ДНФ и КНФ.
Понятие совершенных нормальных форм (СДНФ и СКНФ).
Приведение формул к совершенным нормальным формам с помощью равносильных преобразований.
Упрощение формул логики до минимальной ДНФ.
Практическое занятие № 11. Построение таблиц истинности для ДНФ и КНФ.
Упрощение формул логики с помощью равносильных преобразований.
Минимизация логических выражений с помощью алгебры логики.
- Тема 2.4. Приложения алгебры высказываний к логико-математической практике.
Прямая и обратная теоремы.
Необходимые и достаточные условия.
Раздел 3. Булевы функции
- Тема 3.1. Функции алгебры логики
Понятие булевой функции (функции алгебры логики). Способы ее задания.
Равенство функций. Формулы.
Булевы функции одной переменной: тождественный нуль, тождественная единица, отрицание. Булевы функции двух переменных.
Способы задания булевых функций. Соглашение о написании формул.
- Тема 3.2. Минимизация булевых функций.
Разложение функций по переменным.
Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ).
Построение нормальных форм для заданной булевой функции.
Приведение формул к совершенным нормальным формам с помощью равносильных преобразований.
Практическое занятие №12. Представление булевых функций в виде совершенной ДНФ, совершенной КНФ.
Упрощение формул логики до минимальной ДНФ.
Операция двоичного сложения. Многочлен Жегалкина.
Карты Карно.
- Тема 3.3. Основные классы функций. Полнота множества. Теорема Поста.
Понятие функционально замкнутого класса булевых функций. Полнота множества функций.
Замыкание множества функций. Основные замкнутые классы булевых функций. Теорема Поста.
Функционально полные системы функций. Критерий полноты системы функций.
Раздел 4. Алгебра предикатов.
- Тема 4.1. Понятие предиката. Логические операции над предикатами.
Понятие предиката. Область определения и область истинности предиката.
Понятие n- мерного предиката. Классификация предикатов.
Основы языка алгебры предикатов.
Применение аппарата алгебры высказываний для работы с предикатами.
Основные логические операции над предикатами.
- Тема 4.2.Кванторы. Кванторные операции над предикатами.
Квантор существования.
Квантор общности.
Практическое занятие 13. Выполнение кванторных операций над предикатами.
Запись математических предложений с помощью кванторов существования и общности.
- Тема 4.3. Предикатные формулы.
Понятие предикатной формулы. Свободные и связные переменные.
Решение задач на связывание переменных с помощью кванторов.
- Тема 4.4. Применение логики предикатов к логико-математической практике.
Метод математической индукции.
Применение предикатов к решению логических задач.
Практическое занятие №14. Решение логических задач с помощью алгебры предикатов.
Контактно-релейные схемы.
Раздел 5. Элементы теории алгоритмов.
- Тема 5.1. Элементы теории и практики кодирования.
Системы счисления для представления информации в ЭВМ.
Основные понятия теории кодирования.
- Тема 5.2. Элементы теории алгоритмов и формы представления алгоритма.
Алгоритм. Интуитивное представление об алгоритме.
Основные требования к алгоритмам. Основная терминология теории алгоритмов.
Математические модели алгоритмов.
Практическое занятие №15. Разработка алгоритмов для решения простейших математических задач.
Начальные понятия программирования. Основные принципы работы компьютера.
Краткая характеристика средств алгоритмического языка. Управляющая структура алгоритма.
- Тема 5.3. Машина Поста. Машина Тьюринга.
Абстрактные вычислительные машины. Машина Поста. Основные понятия алгоритмического формализма Поста.
Машина Тьюринга. Алгоритмически неразрешимые проблемы.
Разработала: Рудзина Тамара Нельевна, ГБПОУ Колледж связи № 54 имени П.М. Вострухина г. Москва
|
|
|
УМК школа