Логика булевых функций

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МГАПИ

УТВЕРЖДАЮ

Проректор по УР
____________ Соколов В.В.
«___» ___________ 2002 г.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению контрольных заданий и лабораторных работ
по дисциплине

«Математическая логика и теория алгоритмов»

Рекомендуется для направления подготовки

дипломированного специалиста
654600 – «Информатика и вычислительная техника»
специальности – 22.02.00.

Автоматизированные системы обработки

информации и управления.

Москва 2002

АННОТАЦИЯ
Методические указания соответствуют программе курса “Математическая логика и теория алгоритмов” для студентов специальности 22.02.03. Приведены краткие сведения по основам логики высказываний, логики предикатов, формальных аксиоматических теорий и теории алгоритмов. Контрольные задания включают упражнения по всем разделам. Приводятся указания к проведению лабораторных работ.

Авторы: Казаков С.А., Правоторова Н.А.

Научный редактор: проф. Петров О.М.
Рецензент:
Рассмотрено и одобрено на заседании кафедры ИТ-7
"__"____________2002 г. Зав. кафедрой __________О.М. Петров
Ответственный от кафедры за выпуск учебно-методических материалов
доц. Правоторова Н.А.

СОДЕРЖАНИЕ

Введение
Тема 1. Логика высказываний
1.1. Определение высказывания
1.2. Операции над высказываниями. Алгебра высказываний
1.3. Формулы логики высказываний. Равносильность формул
1.4. Запись сложного высказывания в виде формулы логики высказываний
1.5. Нормальные формы
1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости
1.7.Формализация рассуждений. Правильные рассуждения
Тема 2. Логика предикатов
2.1. Определение предиката. Кванторы
2.2. Формулы логики предикатов. Равносильность формул
2.3. Приведенные и нормальные формулы
2.4. Выражение суждения в виде формулы логики предикатов
2.5. Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость
Тема 3. Формальные аксиоматические теории (исчисления)
3.1. Принципы построения формальных теорий
3.2. Исчисление высказываний
3.3. Исчисление предикатов
3.4. Автоматическое доказательство теорем. Метод резолюций.
Тема 4. Нечеткая логика
4.1. Нечеткие множества
4.2. Нечеткие высказывания
4.3. Нечеткие предикаты
Тема 5 Алгоритмы
5.1. Определение алгоритма
5.2. Машина Тьюринга
5.3. Вычислимые по Тьюрингу функции
Указания к выполнению лабораторных работ
Контрольные задания по курсу “Математическая логика и теория алгоритмов”
Вопросы к экзамену
Список литературы
Краткие сведения о математиках