Методические указания к выполнению контрольных заданий и лабораторных работ по дисциплине «Математическая логика и теория алгоритмов»
СодержаниеТема 1. логика высказываний
1.2. Операции над высказываниями. Алгебра высказываний
А ложно. Чтобы составить отрицание А
1.3. Формулы логики высказываний. Равносильность формул
F называется двойственной
1.4. Запись сложного высказывания в виде формулы логики высказываний
A = "Будет холодное лето". B
B (прямая теорема); B
A = ”Политик обещает невыполнимое”. B
1.5. Нормальные формы
Алгоритм приведения формул логики высказываний к ДНФ (КНФ).
X&Y&Z – СДНФ и КНФ; b) X
Алгоритм приведения формулы булевой функции к СДНФ
Шаг 2. Если в элементарную конъюнкцию K
Алгоритм представления логической функции, заданной таблицей, формулой в СДНФ.
Алгоритм представления логической функции, заданной таблицей, формулой в СКНФ
1.6. Тождественно-истинные и тождественно-ложные формулы. Проблема
1.7.Формализация рассуждений. Правильные рассуждения
B = “Книга интересная”. Схема рассуждения имеет вид: А
А = “Будет хорошая погода”; B
Контрольные вопросы к теме 2
Тема 2. логика предикатов
Квантор общности.
Квантор существования.
2.2. Формулы логики предикатов. Равносильность формул
A – формула, содержащая свободную переменную x
2.3. Приведенные и нормальные формулы
2.4. Выражение суждения в виде формулы логики предикатов
Простым суждением
Andrew Wiles
2.5. Интерпретация формулы логики предикатов в виде суждения.
Контрольные вопросы к теме 2
Тема 3. формальные аксиоматические теории
Правила вывода.
3.2. Исчисление высказываний
B заменить формулой A
A = “Иван умнее Петра”. B
3.3. Исчисление предикатов
Термы: а) предметные переменные x
B не содержит переменной x
A можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в A
M – множество натуральных чисел. Введем предикаты: A
3.4. Автоматическое доказательство теорем. Метод резолюций.
Шаг 4. Процесс продолжаем. Если он заканчивается пустым дизъюнктом, то вывод обоснован. Изложенный алгоритм назывется резолютивн
B не выводима из множества формул A
B выводима из множества формул A
A = ”студент хорошо учится”. B
4.1. Нечеткие множества
Для обычного четкого множества A можно положить
4.3. Нечеткие предикаты
Тема 5. алгоритмы
5.2. Машина Тьюринга
W, управляющее устройство находится в состоянии q
K – команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп); q
K = влево), или сдвиг головки вправо (K
5.3. Вычислимые по Тьюрингу функции
1. Раздел «Логика высказываний»
Варианты индивидуальных заданий
Варианты индивидуальных заданий
Раздел «Теория алгоритмов»
Варианты индивидуальных заданий
Вопросы к экзамену по курсу “Математическая логика” (2 курс)
