- •Пермский Государственный Технический Университет
- •Тема 1. Логика высказываний
- •1.1. Понятие высказывания
- •1.2. Логические операции
- •1. Отрицание или инверсия ( – не)
- •4. Импликация () “если а, то b”
- •6. Сумма по модулю два
- •7. Штрих Шеффера ( , обратная конъюнкция и – не)
- •8. Стрелка Пирса (, обратная дизъюнкция или – не )
- •1.3. Булевы функции
- •1.3.1. Некоторые определения из теории множеств
- •1.3.2. Булевы функции
- •1.4. Формулы
- •1.5. Равносильные формулы
- •1.6. Подстановка и замена
- •1.7. Формы представления высказываний
- •1.8. Минимизация сложных высказываний методом Квайна
- •1.9. Полные системы функций
- •1.9.1. Система функций {}
- •1.9.2. Замкнутые классы
- •1.9.3. Функциональная полнота
- •Тема 2. Логические исчисления
- •2.1. Интерпретация формул
- •2.2. Примеры тождественно истинных формул высказываний
- •2.3. Формальные теории
- •2.5. Интерпретация формальных теорий
- •2.6. Исчисление высказываний.
- •2.7. Производные правила вывода
- •2.8. Дедукция
- •2.9. Некоторые теоремы теории £
- •Тема 3. Логика и исчисление предикатов
- •3.1. Предикаты
- •3.2. Исчисление предикатов
- •3.3. Интерпретация
- •3.4. Основные равносильности для предикатов
- •3.5. Приведенная форма представления предикатов
- •Тема 4. Автоматическое доказательство теорем
- •4.1. Постановка задачи
- •4.2. Доказательство от противного
- •4.3.Правило резолюции для исчисления высказываний
- •4.4. Правило резолюции для исчисления предикатов
- •4.5. Основные положения мр (выводы)
- •4.6. Логическое программирование
- •Тема 5. Теория алгоритмов
- •5.1. Интуитивное понятие алгоритма
- •5.2. Конкретизация понятия алгоритма
- •5.2.1. Машины Тьюринга
- •5.2.3. Рекурсивные функции
- •5.2.3. Нормальные алгорифмы Маркова
- •5.3. Алгоритмически неразрешимые проблемы
- •5.3.1. Проблема самоприменимости
- •5.3.1.1. Нумерация мт
- •5.3.1.2. Самоприменимость мт
- •5.3.2. Проблема останова
- •5.3.3. Разрешимые и неразрешимые задачи математики
- •5.4. Характеристики сложности вычислений
- •5.5. Классы сложности задач
- •5.5.1. Р задачи
- •5.5.2. NPзадачи
4.6. Логическое программирование
Приведенный метод резолюций служит основой языков логического программирования. Главное отличие языков логического программирования от процедурных языков заключается в том, что программа не указывает как что-то сделать, а описывает некоторые элементы и связи между ними (модель) и ставит цель, т. е. задает вопрос об этой системе. На формальном языке это означает проверить истинность предложения на данной системе. При этом компьютер самостоятельно выбирает стратегию для решения поставленных вопросов.
Логическая программа представляет собой конечный набор выражений следующих видов:
факты: , (1)
правила: , (2)
где ,- атомарные формулы.
Правило читается как: «если истинны , то истинно». Формуланазывается заголовком правила.
Правила позволяют выводить новые факты из уже существующих. Факты определяют отношения между объектами.
Для выполнения программы необходимо обратиться к целевому запросу (цели), которая представляет собой последовательность атомарных формул вида:
.(3)
Выполнение программы состоит в попытке решить задачу, т .е. доказать целевое утверждение, используя факты и правила.
Каждому факту (1) поставим в соответствие предложение:
А:, где- все переменные, входящие в формулу.
Каждому правилу (2) поставим в соответствие предложение:
В:, где- все переменные, входящие в формулы
Запросу (3) поставим в соответствие формулу:
С:,
где кванторы связывают все переменные.
Нужно доказать
Для доказательства используется метод резолюций.
Тема 5. Теория алгоритмов
5.1. Интуитивное понятие алгоритма
Для решения ряда однотипных задач можно использовать чисто механические вычислительные процессы. С их помощью искомые величины вычисляются последовательно из данных величин по определенным правилам. Описание таких процессов принято называть алгоритмами.
Алгоритм – это строгое предписание, определяющее вычислительный процесс как последовательность шагов, которая приводит от изменяемых начальных данных к конечному результату. Это фундаментальное и неопределяемое понятие.
Свойства алгоритмов
Массовость: алгоритм должен решать не одну конкретную задачу, а целый класс подобных задач.
Элементарность шагов: алгоритм разбивается на этапы, каждый из которых должен быть простым и локальным.
Детерминированность: после выполнения очередного этапа однозначно определено, что делать дальше.
Результативность: алгоритм должен приводить к решению задачи за конечное число шагов.
Примеры алгоритмов:
Нахождение наибольшего общего делителя.
Вычисление ранга целочисленной матрицы.
Построение ДНФ и КНФ в логике высказываний.
Интуитивное понятие алгоритма позволяет определить является ли данный процесс алгоритмом. Но существуют и алгоритмически неразрешимые задачи, т .е. задачи для которых построить алгоритм в принципе невозможно.
Теория алгоритмов занимается проблемой алгоритмической разрешимости, т. е. определением того, возможно ли вообще построить алгоритм для задач данного типа.
Но для того, чтобы доказать, что алгоритм не существует, надо точно знать, что такое алгоритм.
Начиная с 30-х годов XX века, было предложено несколько уточнений понятия алгоритма. К ним относятся:
Рекурсивные функции.
Машина Тьюринга.
Нормальные алгорифмы Маркова.