Модальная глубина

редактировать
Термин модальной логики

В модальной логике модальная глубина формулы является самой глубокой вложенностью из модальные операторы (обычно ◻ {\ displaystyle \ Box}\ Box и ◊ {\ displaystyle \ Diamond}\ Diamond ). Модальные формулы без модальных операторов имеют модальную глубину, равную нулю.

Содержание

  • 1 Определение
  • 2 Пример
  • 3 Модальная глубина и семантика
  • 4 Ссылки

Определение

Модальная глубина может быть определена следующим образом. Пусть MD (ϕ) {\ displaystyle MD (\ phi)}{\ displaystyle MD (\ phi)} будет функцией, которая вычисляет модальную глубину для модальной формулы ϕ {\ displaystyle \ phi }\ phi :

MD (p) = 0 {\ displaystyle MD (p) = 0}{\ displaystyle MD (p) = 0} , где p {\ displaystyle p}p - атомарная формула.
MD (⊤) = 0 {\ displaystyle MD (\ top) = 0}{\ displaystyle MD (\ top) = 0}
MD (⊥) = 0 {\ displaystyle MD (\ bot) = 0}{\ displaystyle MD (\ bot) = 0}
MD (¬ φ) = MD (φ) {\ Displaystyle MD (\ neg \ varphi) = MD (\ varphi)}{\ displaystyle MD (\ neg \ varphi) = MD (\ varphi)}
MD (φ ∧ ψ) = макс (MD (φ), MD (ψ)) {\ displaystyle MD (\ varphi \ клин \ psi) = макс (MD (\ varphi), MD (\ psi))}{\ displaystyle MD (\ varphi \ wedge \ psi) = max (MD (\ varphi), MD (\ psi))}
MD (φ ∨ ψ) = max (MD (φ), MD (ψ)) {\ displaystyle MD (\ varphi \ vee \ psi) = макс (MD (\ varphi), MD (\ psi))}{\ Displaystyle MD (\ varphi \ vee \ psi) = max (MD (\ varphi), MD (\ psi))}
MD (φ → ψ) = max (MD (φ), MD (ψ)) {\ displaystyle MD (\ varphi \ rightarrow \ psi) = max (MD (\ varphi), MD (\ psi))}{\ displaystyle MD (\ varphi \ rightarrow \ psi) = max (MD (\ varphi), MD (\ psi))}
MD (◻ φ) = 1 + MD (φ) {\ displaystyle MD (\ Box \ varphi) = 1 + MD ( \ varphi)}{\ displaystyle MD (\ Box \ varphi) = 1 + MD (\ varphi)}
MD (◊ φ) = 1 + MD (φ) {\ displaystyle MD (\ Diamond \ varphi) = 1 + MD (\ varphi)}{\ displaystyle MD (\ Diamond \ varphi) = 1 + MD (\ varphi)}

Пример

Th е следующее вычисление дает модальную глубину ◻ (◻ p → p) {\ displaystyle \ Box (\ Box p \ rightarrow p)}{\ displaystyle \ Box (\ Box p \ rightarrow p)} :

MD (◻ (◻ p → p)) = {\ displaystyle MD (\ Box (\ Box p \ rightarrow p)) =}{\ displaystyle MD (\ Box (\ Box p \ rightarrow p)) = }
1 + MD (◻ p → p) = {\ displaystyle 1 + MD (\ Box p \ rightarrow p) =}{\ displaystyle 1 + MD (\ Box p \ rightarrow p) =}
1 + max ( MD (◻ p), MD (p)) = {\ displaystyle 1 + max (MD (\ Box p), MD (p)) =}{\ displaystyle 1 + max (MD (\ Box p), MD (p)) =}
1 + max (1 + MD (p), 0) = {\ displaystyle 1 + max (1 + MD (p), 0) =}{\ displaystyle 1 + max (1 + MD (p), 0) =}
1 + max (1 + 0, 0) = {\ displaystyle 1 + max (1 + 0,0) =}{\ displaystyle 1 + max (1 + 0,0) =}
1 + 1 =: 2 {\ displaystyle 1 + 1 =: 2}{\ displaystyle 1 + 1 =: 2 }

Модальная глубина и семантика

Модальная глубина формулы указывает, «как далеко» нужно смотреть в Крипке модель при проверке действительности формулы. Для каждого модального оператора необходимо перейти от мира в модели к миру, доступному через отношение доступности. Модальная глубина указывает на самую длинную «цепочку» переходов от одного мира к другому, которая необходима для проверки правильности формулы.

Например, чтобы проверить, M, w ⊨ ◊ ◊ φ {\ displaystyle M, w \ models \ Diamond \ Diamond \ varphi}{\ displaystyle M, w \ models \ Diamond \ Diamond \ varphi} , нужно проверить, есть ли существует доступный мир v {\ displaystyle v}v, для которого M, v ⊨ ◊ φ {\ displaystyle M, v \ models \ Diamond \ varphi}{\ displaystyle M, v \ models \ Diamond \ varphi} . Если это так, нужно проверить, существует ли еще такой мир u {\ displaystyle u}u , такой что M, u ⊨ φ {\ displaystyle M, u \ models \ varphi}{\ displaystyle M, u \ models \ varphi} и u {\ displaystyle u}u доступны из v {\ displaystyle v}v. Мы сделали два шага от мира w {\ displaystyle w}w (от w {\ displaystyle w}w до v {\ displaystyle v}vи от v {\ displaystyle v}vдо u {\ displaystyle u}u ) в модели, чтобы определить, верна ли формула; это, по определению, модальная глубина этой формулы.

Модальная глубина - это верхняя граница (включительно) количества переходов, как и для блоков, модальная формула также верна, когда в мире нет доступных миров (т. Е. ◻ φ {\ displaystyle \ Поле \ varphi}\ Box \ varphi сохраняется для всех φ {\ displaystyle \ varphi}\ varphi в мире w {\ displaystyle w}w при ∀ v ∈ W (w, v) ∉ R {\ displaystyle \ forall v \ in W \ (w, v) \ not \ in R}{\ displaystyle \ forall v \ in W \ (w, v) \ not \ in R} , где W {\ displaystyle W}W - это набор миров, а R {\ displaystyle R}R - отношение доступности). Чтобы проверить, соответствует ли M, w ⊨ ◻ ◻ φ {\ displaystyle M, w \ models \ Box \ Box \ varphi}{\ displaystyle M, w \ models \ Box \ Box \ varphi} , может потребоваться выполнить два шага в модели, но это может быть меньше, в зависимости от структуры модели. Предположим, что в w {\ displaystyle w}w нет доступных миров; формула теперь тривиально выполняется в силу предыдущего наблюдения о действительности формул с прямоугольником в качестве внешнего оператора.

Ссылки

Последняя правка сделана 2021-05-30 04:21:04
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте