МЛиТА 6 - 7
Семантика темпоральной логики
Понятие модели Крипке (W, R, h) такое же, как для модальной логики. Определяется истинность формул [F]А и [P]А, вместо А.
Если tRu, то говорят, что t – прошлое для u, а u – будущее для t. (Напомним, что tRu означает (t, u) R.)
Обычно отношение R предполагается транзитивным в том смысле, что из tRu и uRv следует: tRv (исключением являются шкалы с циклическим временем). Утверждения для интерпретации А заменяются на следующие:
-
M, t |= [F]А, если и только если M, u |= А для всех u W таких, что tRu.
-
M, t |= [P]А, если и только если M, u |= А для всех u W таких, что uRt.
Содержание
- 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