МЛиТА 6 - 7
Упражнение 5
Доказать, что если R W W – рефлексивно, то А А – тавтология относительно шкалы (W, R) для любой формулы А.
Формула (А В) (А В) является тавтологией относительно класса всех шкал Крипке. Такие формулы называют естественно истинными. Формула А А верна относительно некоторого класса шкал. Такие формулы называются условно истинными.
Содержание
- 6. Модальная и темпоральная логикИ
- 6.1. Синтаксис модальной логики
- Дополнительные логические связки
- Приоритеты операций
- Смысловые значения модальностей
- 6.2. Семантика модальной логики
- Модели Крипке
- Упражнение 1
- Упражнение 2
- Семантика темпоральной логики
- Упражнение 3
- Тавтологии
- Упражнение 4
- Условные тавтологии
- Упражнение 5
- 6.3. Алгоритмическая логика Хоара
- Пропозициональная динамическая логика
- Семантика пропозициональной динамической логики
- Аксиомы pdl
- Правила вывода
- Логика Хоара
- Корректность и полнота систем Гильберта
- Свойства шкал Крипке
- Алгоритм Салквиста
- Пример 2
- Пример 3
- Пример 6
- 6.5. Темпоральная логика
- Система Гильберта для темпоральной логики
- Линейные потоки времени
- Стандартный перевод
- Завтра и вчера
- Выбор операторов
- 7. Алгоритмы и рекурсивные функции
- 7.1. Частично рекурсивные функции
- Простейшие функции
- Пример 1
- Оператор примитивной рекурсии
- Пример 2
- Пример 4
- Пример 5
- Пример 6
- Оператор минимизации
- Пример 7
- 7.2. Машины Тьюринга
- Пример 1
- Пример 2
- Пример 3
- Упражнение
- 7.3. Вычислительная сложность
- Труднорешаемые и np-полные задачи
- 6. Модальная и темпоральная логикИ 49
- 7. Алгоритмы и рекурсивные функции 65