- •Учебное пособие
- •Тема. Введение в алгебру логики
- •1. Историческая справка. Прямое произведение множеств. Соответствия и функции. Алгебры.
- •2. Функции алгебры логики. Примеры логических функций
- •Таблица 2.1
- •4. Принцип двойственности. Совершенная дизъюнктивная нормальная форма (СДНФ). Разложение булевых функций по переменным.
- •5. Построение СДНФ для функции, заданной таблицей. Представление логических функций булевыми формулами. Совершенная конъюнктивная нормальная форма (СКНФ). Основные эквивалентные преобразования.
- •Тема. Минимизация булевых функций.
- •6. Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски.
- •Тема. Полнота и замкнутость систем логических функций.
- •8. Основные определения. Основные замкнутые классы.
- •Действительно, пусть
- •Поэтому
- •Тема. Исчисление высказываний.
- •9. Общие принципы построения формальной теории.Интерпретация, общезначимость, противоречивость, логическое следствие.
- •Тема. Исчисление предикатов.
- •11. Понятие предиката. Кванторы. Алфавит. Формулы. Интерпретация формул.
- •12. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму.
- •13. Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации.
- •Учебно-методический комплекс
- •1. Выписка из ГОС ВПО (если дисциплина в ГОС имеется);
- •2. Календарный план учебных занятий по дисциплине;
- •3. Описание курса (дисциплины):
- •1. Информация о преподавателе (ссылка на страницу)
- •2. Цель курса
- •3. Содержание курса
- •5. Условия и критерии выставления оценок
- •6. Балльно-рейтинговая система оценки знаний, шкала оценок
- •7. Темы лекций, семинарских занятий, лабораторных работ
- •5. Методические указания и рекомендации по выполнению лабораторных работ, практических или семинарских занятий, курсовых работ (проектов)
- •6. Правила выполнения письменных работ (контрольных тестовых работ)
- •7. Комплект индивидуальных заданий (рефератов) по дисциплине, тематика курсовых работ (проектов)
- •8. Образцы студенческой продукции: конспекты лекций, отчеты по лабораторным работам, практическим занятиям, образцы курсовых проектов или работ, индивидуальных заданий, рефератов и т.п.
- •9. Содержание практик; проведения экскурсий, лекций и их примерное содержание и сроки; индивидуальные задания студентов с указанием сроков выполнения; структура и содержание отчета о практике, порядок и сроки их защиты студентами.
- •10. Контролирующие материалы (тесты, билеты, задачи и т.п.) по обеспечению:
- •1. текущего, рубежного (промежуточного) контролей
- •2. итоговых семестровых испытаний
- •Учебное пособие
Э.Р. Зарипова, М.Г. Кокотчикова, Л.А. Севастьянов
Л Е К Ц И И ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Учебное пособие
Математическая логика
Москва Российский университет дружбы народов
2011
1
Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А.
Лекции по дискретной математике: Учеб. пособие. Математическая логика. – М.: Изд-во РУДН, 2011. – 79 с.
В пособии излагаются основные положения логики – булева алгебра, исчисление высказываний, исчисление предикатов.
Подготовлено на кафедре систем телекоммуникаций и предназначено для студентов I, II курсов математических специальностей университетов.
© Э.Р. Зарипова, М.Г. Кокотчикова, Л.А. Севастьянов, 2011 г.
2
ОГЛАВЛЕНИЕ Тема. Введение в алгебру логики_____________________5
1. Историческая справка. Прямое произведение множеств. Соответствия и функции. Алгебры________________5
2.Функции алгебры логики. Примеры логических функций__5
3.Суперпозиции и формулы. Булева Алгебра____________12
4.Принцип двойственности. Совершенная дизъюнктивная нормальная форма (СДНФ).Разложение булевых функций по переменным_____________________________________________15
5.Построение СДНФ для функции, заданной таблицей. Представление логических функций булевыми формулами. Совершенная конъюнктивная нормальная форма (СКНФ). Основные эквивалентные преобразования___________________20
Тема. Минимизация булевых функций_______________24
6.Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски_______________24
7.Таблицы простых импликантов_____________________28
Тема. Полнота и замкнутость систем логических
функций_______________________________________________33
8. Основные определения. Основные замкнутые классы___33
Тема. Исчисление высказываний____________________41
9. Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость,
логическое следствие_____________________________________41 10. Метод резолюций для исчисления высказываний______44
3
Тема. Исчисление предикатов_______________________48
11.Понятие предиката. Кванторы. Алфавит.
Формулы. Интерпретация формул_________________________48
12.Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму____52
13.Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации_________________________55
14.Метод резолюций в исчислении предикатов__________59
Учебно-методический комплекс по дисциплине
«Математическая логика»_______________________________63
4