ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 18.10.2024
Просмотров: 12
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Неклассические логики и представление знаний
Бисимуляция
Отделение прикладной математики и информатики
Высшая школа экономики
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Модальная эквивалентность
Определение (w
! w
0
)
Миры w ∈ M и w
0
∈ M
0
называются модально эквивалентными
, если их теории совпадают:
{φ | M, w |= φ} = {φ | M
0
, w
0
|= φ}
Определение (M
! M
0
)
Модели M и M
0
называются модально эквивалентными
,
если их теории совпадают:
{φ | M |= φ} = {φ | M
0
|= φ}
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение v1
v2
v3
v4
w
M
N
v1
v2
v3
v4
w
M
] N
Если N, u |= φ, то M ] N, u |= φ?
Если M ] N, u |= φ и u ∈ N, то N, u |= φ?
Да:
истинность в модели инвариантна относительно операции дизъюнктного объединения.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение v1
v2
v3
v4
w
M
N
v1
v2
v3
v4
w
M
] N
Если N, u |= φ, то M ] N, u |= φ?
Если M ] N, u |= φ и u ∈ N, то N, u |= φ?
Да:
истинность в модели инвариантна относительно операции дизъюнктного объединения.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение v1
v2
v3
v4
w
M
N
v1
v2
v3
v4
w
M
] N
Если N, u |= φ, то M ] N, u |= φ?
Если M ] N, u |= φ и u ∈ N, то N, u |= φ?
Да:
истинность в модели инвариантна относительно операции дизъюнктного объединения.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение v1
v2
v3
v4
w
M
N
v1
v2
v3
v4
w
M
] N
Если N, u |= φ, то M ] N, u |= φ?
Если M ] N, u |= φ и u ∈ N, то N, u |= φ?
Да:
истинность в модели инвариантна относительно операции дизъюнктного объединения.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение v1
v2
v3
v4
w
M
N
v1
v2
v3
v4
w
M
] N
Если N, u |= φ, то M ] N, u |= φ?
Если M ] N, u |= φ и u ∈ N, то N, u |= φ?
Да:
истинность в модели инвариантна относительно операции дизъюнктного объединения.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Модели называются непересекающимися
, если их носители не содержат общих элементов.
Определение (Базовый случай)
Дизъюнктное объединение непересекающихся моделей
M
i
= (W
i
, R
i
, V
i
)(i ∈ I ):
]
i
M
i
= (W , R, V )
W
=
S
i∈I
W
i
R
=
S
i∈I
R
i
V (p)
=
S
i∈I
V
i
(p) для всех переменных p
Дизъюнктное объединение пересекающихся моделей строится по их непересекающимся изоморфным копиям.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Модели называются непересекающимися
, если их носители не содержат общих элементов.
Определение (τ -модели)
Дизъюнктное объединение непересекающихся однотипных
τ -моделей M
i
= (W
i
, R
4i
, V
i
)
4∈τ
(i ∈ I ) :
]
i
M
i
= (W , R
4
, V )
4∈τ
W
=
S
i∈I
W
i
R
4
=
S
i∈I
R
4i
для всех 4 ∈ τ
V (p)
=
S
i∈I
V
i
(p) для всех переменных p
Дизъюнктное объединение пересекающихся моделей строится по их непересекающимся изоморфным копиям.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Определение (τ -модели)
Дизъюнктное объединение непересекающихся однотипных
τ -моделей M
i
= (W
i
, R
4i
, V
i
)
4∈τ
(i ∈ I ) :
]
i
M
i
= (W , R
4
, V )
4∈τ
W
=
S
i∈I
W
i
R
4
=
S
i∈I
R
4i
для всех 4 ∈ τ
V (p)
=
S
i∈I
V
i
(p) для всех переменных p
Дизъюнктное объединение пересекающихся моделей строится по их непересекающимся изоморфным копиям.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Утверждение (Истинность формулы инвариантна относительно дизъюнктного объединения)
Пусть τ — модальный тип сходства и M
i
— τ -модели для всех i ∈ I . Тогда для любой модальной формулы φ, любого
i ∈ I и любого элемента w из M
i
верно
M
i
, w |= φ ⇐⇒
]
j∈I
M
j
, w |= φ.
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
p
: M
i
, w |= φ ⇔ w ∈ V
i
(p) ⇔ w ∈ V (p) ⇔ M, w |= φ
⊥
: M
i
, w 6|= ⊥ и M, w 6|= ⊥
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
p
: M
i
, w |= φ ⇔ w ∈ V
i
(p) ⇔ w ∈ V (p) ⇔ M, w |= φ
⊥
: M
i
, w 6|= ⊥ и M, w 6|= ⊥
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
Пусть утверждение верно для формулы с ≤ n связками.
Покажем, что оно верно и для формулы с n + 1 связками.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
Пусть утверждение верно для формулы с ≤ n связками.
Покажем, что оно верно и для формулы с n + 1 связками.
Для ¬ψ и ψ ∨ θ доказательство тривиально.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
Пусть утверждение верно для формулы с ≤ n связками.
Покажем, что оно верно и для формулы с n + 1 связками.
Пусть M
i
, w |= ♦ψ
Есть v ∈ W
i
, такой что R
i
wv и M
i
, v |= ψ
M
, v |= ψ (по индукции)
M
, w |= ♦ψ (т.к. Rwv)
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Дизъюнктное объединение
Доказательство.
Докажем по индукции по φ для базового типа сходства.
Пусть M = (W , R, V ) =
U
j∈I
M
j
Пусть утверждение верно для формулы с ≤ n связками.
Покажем, что оно верно и для формулы с n + 1 связками.
Пусть M, w |=
♦ψ для некоторого w ∈ W
i
Есть v ∈ W , такой что Rwv и M, v |= ψ
R
i
wv (по определению R и т.к. модели непересекающиеся)
v ∈ W
i
M
i
, v |= ψ (по индукции)
M
i
, w |= ♦ψ (т.к. R
i
wv)
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Использование дизъюнктного объединения
Двойственные глобальные модальные операторы E и A:
M
, w |= E φ
⇐⇒ M, v |= φ для некоторого v ∈ M
M
, w |= Aφ
⇐⇒ M, v |= φ для всех v ∈ M
Можно ли определить E и A синтаксически в базовом модальном языке (через
♦)?
Пусть α(p) — формула базового языка, соответствующая Ap:
M
, w |= α(p) ⇐⇒ M |= p
Рассмотрим M
1
и M
2
, такие что
M
1
|= p
и
M
2
|= ¬p
w ∈ M
1
⇒
M
1
, w |= α(p)
⇒
M
1
U
M
2
, w |= α(p)
⇒
∀v ∈ M
2
: M
2
, v |= p
⇒
M
2
|= p
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Использование дизъюнктного объединения
Двойственные глобальные модальные операторы E и A:
M
, w |= E φ
⇐⇒ M, v |= φ для некоторого v ∈ M
M
, w |= Aφ
⇐⇒ M, v |= φ для всех v ∈ M
Можно ли определить E и A синтаксически в базовом модальном языке (через
♦)?
Пусть α(p) — формула базового языка, соответствующая Ap:
M
, w |= α(p) ⇐⇒ M |= p
Рассмотрим M
1
и M
2
, такие что
M
1
|= p
и
M
2
|= ¬p
w ∈ M
1
⇒
M
1
, w |= α(p)
⇒
M
1
U
M
2
, w |= α(p)
⇒
∀v ∈ M
2
: M
2
, v |= p
⇒
M
2
|= p
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Дизъюнктное объединение
Использование дизъюнктного объединения
Двойственные глобальные модальные операторы E и A:
M
, w |= E φ
⇐⇒ M, v |= φ для некоторого v ∈ M
M
, w |= Aφ
⇐⇒ M, v |= φ для всех v ∈ M
Можно ли определить E и A синтаксически в базовом модальном языке (через
♦)?
Пусть α(p) — формула базового языка, соответствующая Ap:
M
, w |= α(p) ⇐⇒ M |= p
Рассмотрим M
1
и M
2
, такие что
M
1
|= p
и
M
2
|= ¬p
w ∈ M
1
⇒
M
1
, w |= α(p)
⇒
M
1
U
M
2
, w |= α(p)
⇒
∀v ∈ M
2
: M
2
, v |= p
⇒
M
2
|= p
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Порожденные подмодели
Порожденные подмодели
-3
-2
-1 0
1 2
3
M = (Z, <)
-3
-2
-1 0
0 1
2 3
M
−
M
+
Если M
−
, u |= φ, то M, u |= φ?
Нет:
M
−
, 0 |= ⊥, но M, 0 6|= ⊥
Если M
+
, u |= φ, то M, u |= φ?
Да:
M
+
— подмодель M, замкнутая относительно отношения достижимости.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Порожденные подмодели
Порожденные подмодели
-3
-2
-1 0
1 2
3
M = (Z, <)
-3
-2
-1 0
0 1
2 3
M
−
M
+
Если M
−
, u |= φ, то M, u |= φ?
Нет:
M
−
, 0 |= ⊥, но M, 0 6|= ⊥
Если M
+
, u |= φ, то M, u |= φ?
Да:
M
+
— подмодель M, замкнутая относительно отношения достижимости.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Порожденные подмодели
Порожденные подмодели
-3
-2
-1 0
1 2
3
M = (Z, <)
-3
-2
-1 0
0 1
2 3
M
−
M
+
Если M
−
, u |= φ, то M, u |= φ?
Нет:
M
−
, 0 |= ⊥, но M, 0 6|= ⊥
Если M
+
, u |= φ, то M, u |= φ?
Да:
M
+
— подмодель M, замкнутая относительно отношения достижимости.
Неклассические логики и представление знаний
ВШЭ
Инвариантность модальных формул
Бисимуляция
Конечные модели
Упражнения
Порожденные подмодели
Порожденные подмодели
-3
-2
-1 0
1 2
3
M = (Z, <)
-3
-2
-1 0
0 1
2 3
M
−
M
+
Если M
−
, u |= φ, то M, u |= φ?
Нет:
M
−
, 0 |= ⊥, но M, 0 6|= ⊥
Если M
+
, u |= φ, то M, u |= φ?
Да:
M
+
— подмодель M, замкнутая относительно отношения достижимости.
Неклассические логики и представление знаний
ВШЭ