Линейные потоки времени
Чтобы ограничить виды потоков времени, к системе Kt добавляются аксиомы. Аксиомы <F>1 и <P>1 означают отсутствие наименьшего и наибольшего t W.
Истинность аксиомы [F][F]A [F]A равносильна свойству плотности отношения доступности:
tu (t < u v(t < v <u)).
Например, Q и R – плотные линейно упорядоченные множества, а Z – нет.
Для того чтобы потоки времени были линейно упорядочены, т.е. удовлетворяли условию:
tu (t < u t = u u < t),
добавляется аксиома
<F>A&<F>B <F>(A&B)<F>(A&<F>B)(B&<F>A)
(или её зеркальное отображение).
В случае шкалы (Z, <) добавляются аксиомы:
[F]([F]A A) (<F>[F]A [F]A),
[P]([P]A A) (<P>[P]A [P]A).
Для шкалы (N, <) добавляются аксиомы:
[F]([F]A A) (<F>[F]A [F]A),
[P]([P]A A) [P]A.
Для (R, <) добавляются аксиомы, обеспечивающие плотность отношения порядка и отсутствие максимального и минимального элементов. Добавляется аксиома Прайера:
<F>[F] <F>A <F>)[F]A& <P>[F]A).
- 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