1. Введение в алгебру логики Прямое произведение множеств. Соответствия и функции. Алгебры. Функции алгебры логики. Суперпозиции и формулы. Булева Алгебра. Принцип двойственности. Совершенная дизъюнктивная нормальная форма сднф
| Вид материала | Лекции |
- Лекции по математической логике тема. Введение в алгебру логики Лекция Историческая, 347.51kb.
- Функции алгебры логики, 47.25kb.
- Законы алгебры логики, 44.21kb.
- Алгебра логики и логические основы компьютера Алгебра логики (булева алгебра), 39.45kb.
- Некоммутативная геометрия, 36.84kb.
- Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.
- Разработка урока по информатике и икт «Основные понятия алгебры логики», 85.97kb.
- Лекция Логические основы компьютеров , 369.25kb.
- Реферат по теме «Зарождение современных компьютерных роботов.», 91.85kb.
- Основы математической логики. Алгебра логики (булева алгебра), 59.39kb.
математическая логика
Кафедра систем телекоммуникаций, факультет физико-математических и естественных наук.
Обязательная дисциплина, привязанная к семестру.
Трудоемкость – 3 кредита, 2 часа лекций и 2 часа лабораторных занятий в неделю.
Цель курса
Целью курса является развитие логического мышления у студентов и изучение основ математической логики. Развиваются навыки формализации и описания дискретных математических объектов.
Содержание курса
Лекции
Тема 1. Введение в алгебру логики
Прямое произведение множеств. Соответствия и функции. Алгебры. Функции алгебры логики. Суперпозиции и формулы. Булева Алгебра. Принцип двойственности. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ). Разложение булевых функций по переменным. Построение СДНФ для функции, заданной таблично.
Тема 2. Минимизация булевых функций
Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.
Тема 3. Полнота и замкнутость систем логических функций
Замкнутые классы. Класс логических функций, сохраняющий константы 0 и 1. Определение и доказательство замкнутости. Класс самодвойственных функций.
Определение и лемма о несамодвойственной функции. Класс монотонных функций. Определение и лемма о немонотонной функции. Класс линейных функций. Определение и лемма о нелинейной функции.
Тема 4. Исчисление высказываний и предикатов
Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость, логическое следствие. Метод резолюций для исчисления высказываний. Понятие предиката. Кванторы. Алфавит. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму. Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации. Метод резолюций в исчислении предикатов.
Лабораторные занятия
Тема 1. Алгебра логики
Решение примеров на прямое произведение множеств. Задача на истинность соответствия. Поиск подалгебры в алгебре. Суперпозиции и формулы. Решение задач на принцип двойственности и правило двойственности. Нахождение совершенной дизъюнктивной нормальной формы (СДНФ). Нахождение совершенной конъюнктивной нормальной формы (СКНФ). Разложение булевых функций по переменным. Построение СДНФ для функции, заданной таблично.
Тема 2. Минимизация булевых функций
Минимизация функций. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.
Тема 3. Полнота и замкнутость систем логических функций
Решение задач на доказательство замкнутости класса. Класс самодвойственных функций. Решение задач с несамодвойственными функциями. Класс монотонных функций. Решение задач с немонотонными функциями. Класс линейных функций. Решение задач с нелинейными функциями.
Тема 4. Исчисление высказываний и предикатов
Решение задач с использованием метода резолюций для исчисления высказываний. Применение кванторов. Поиск предваренной нормальной формы (ПНФ). Поиск скулемовской стандартной формы. Подстановка и унификация для ПНФ. Применение алгоритма унификации. Применение метода резолюций в исчислении предикатов.
Темы контрольных работ
Промежуточный контроль знаний
Контрольная работа № 1. Булева алгебра.
Типовые задачи
- Построение СДНФ, СКНФ, нахождение существенных и фиктивных переменных, построение полинома Жегалкина.
- Представление функции булевой формулой.
- Нахождение двойственной функции по правилу двойственности, по принципу двойственности и по таблице.
- Проверка справедливости соотношения.
Контрольная работа № 2. Минимизация булевых функций и исчисление высказываний.
Типовые задачи
- Построить минимальное представление исходной функции
с помощью алгоритма Куайна-МакКлоски и последующего выделения ядра.
- Проверить является ли высказывание логическим следствием (двумя способами: любая из двух теорем и метод резолюций).
- Найти предваренную и скулемовскую нормальные формы для формулы.
- Проверить принадлежность функции классам монотонных функций, самодвойственных функций, линейных функций.
Коллоквиум № 1. Теоретические вопросы по курсу.
Проверка знаний теоретических вопросов по темам
- Алгебра логики.
- Минимизация булевых функций.
- Полнота и замкнутость систем логических функций.
- Исчисление высказываний и предикатов.
Итоговый контроль знаний.
Контрольная работа № 3. Применение булевой алгебры к исчислению высказываний и предикатов.
Теоретические и практические вопросы и задачи по темам
- Алгебра логики.
- Минимизация булевых функций.
- Полнота и замкнутость систем логических функций.
- Исчисление высказываний и предикатов.
Литература
Обязательная
- Гаврилов Г.П., Сапоженко А.А. «Задачи и упражнения по курсу дискретной математики».// М.: "Наука", 2007.
- Иванов Б.Н. «Дискретная математика. Алгоритмы и программы». // М.: Изд-во «Лаборатория базовых знаний», 2007.
- Холл М. «Комбинаторика». // М.: "Мир", 2005.
Дополнительная
- Ю.В. Гайдамака, К.Е. Самуйлов, Л.А. Севастьянов, С.С. Спесивов «Комбинаторика. Алгоритмы на графах». Учебно-методическое пособие. // М.: Изд-во РУДН, 2002.
Программу составила
Зарипова Эльвира Ринатовна,
старший преподаватель кафедры систем телекоммуникаций,
факультет физико-математических и естественных наук.