Динамическая эпистемическая логика

Динамическая эпистемическая логика (DEL) — это логическая структура, связанная с изменением знаний и информации. Обычно DEL фокусируется на ситуациях с участием нескольких агентов и изучает, как их знания изменяются при возникновении событий . Эти события могут изменять фактические свойства реального мира (они называются онтическими событиями ): например, красная карта окрашивается в синий цвет. Они также могут вызывать изменения в знаниях без изменения фактических свойств мира (их называют эпистемическими событиями ): например, публично (или конфиденциально) выясняется, что карта красная. Первоначально DEL сосредоточился на эпистемических событиях. В этой статье мы представляем только некоторые основные идеи исходной среды DEL; более подробную информацию о DEL в целом можно найти в ссылках.

Благодаря характеру объекта исследования и абстрактному подходу, DEL связан и имеет приложения к многочисленным исследовательским областям, таким как информатика ( искусственный интеллект ), философия ( формальная эпистемология ), экономика ( теория игр ) и когнитивная наука . Например, в информатике DEL во многом связан с многоагентными системами , то есть системами, в которых несколько интеллектуальных агентов взаимодействуют и обмениваются информацией.

Динамическая эпистемическая логика , представляющая собой комбинацию динамической логики и эпистемической логики , является молодой областью исследований. На самом деле все началось в 1989 году с логики публичного заявления Plaza. Независимо, Гербранди и Грюневельд предложил систему, касающуюся, кроме того, частных объявлений, и это было вдохновлено работой Вельтмана. Другая система была предложена ван Дитмаршем, главным вдохновителем которого была игра Cluedo . Но наиболее влиятельной и оригинальной была система, предложенная Балтагом, Моссом и Солецким. Эта система может иметь дело со всеми типами ситуаций, изученных в вышеизложенных работах, и ее базовая методология концептуально обоснована. В этой статье мы представим некоторые из его основных идей.

Формально DEL расширяет обычную эпистемическую логику за счет включения моделей событий для описания действий и оператора обновления продукта, который определяет, как обновляются эпистемические модели в результате выполнения действий, описанных с помощью моделей событий. Сначала вспомним эпистемическую логику. Затем в картину войдут действия и события, и мы представим структуру DEL.

Эпистемическая логика

Эпистемическая логика — это модальная логика, имеющая дело с понятиями знания и убеждения. Как логика , она занимается пониманием процесса рассуждений о знаниях и убеждениях: какие принципы, связывающие понятия знания и убеждения, интуитивно правдоподобны? Как и эпистемология, оно происходит от греческого слова $\epsilon \pi \iota \sigma \tau \eta \mu \eta$ или «эпистема», означающая знание. Тем не менее эпистемология больше занимается анализом самой природы и объема знаний, отвечая на такие вопросы, как «Каково определение знания?» или «Как приобретаются знания?». Фактически эпистемическая логика выросла из эпистемологии в средние века благодаря усилиям Берли и Оккама. Формальная работа, основанная на модальной логике, которая положила начало современным исследованиям эпистемической логики, датируется только 1962 годом и принадлежит Хинтикке . Затем в 1960-х годах это вызвало дискуссии о принципах познания и убеждений, и было предложено и обсуждено множество аксиом для этих понятий. Например, аксиомы взаимодействия $Kp\rightarrow Bp$ и $Bp\rightarrow KBp$ часто считаются интуитивными принципами: если агент знает $p$ тогда (а) он тоже верит $p$, или если агент верит $p$, тогда он знает, что он верит $p$. Совсем недавно такого рода философские теории были подхвачены исследователями в области экономики . искусственный интеллект и теоретическая информатика где рассуждения о знаниях являются центральной темой. Из-за новой обстановки, в которой использовалась эпистемическая логика, вычислимости в программу исследований эпистемической логики были добавлены новые перспективы и новые функции, такие как проблемы .

Синтаксис

В продолжении $AGTS=\{1,\ldots ,n\}$ — конечное множество, элементы которого называются агентами и $PROP$ представляет собой набор пропозициональных букв.

Эпистемический язык является расширением базового мультимодального языка модальной логики с помощью общего знания . оператора $C_{A}$ и распределенных знаний оператор $D_{A}$. Формально эпистемический язык ${\mathcal {L}}_{\textsf {EL}}^{C}$ определяется индуктивно следующей грамматикой в ​​BNF :

${\mathcal {L}}_{\textsf {EL}}^{C}:\phi ~~::=~~p~\mid ~\neg \phi ~\mid ~(\phi \land \phi )~\mid ~K_{j}\phi ~\mid ~C_{A}\phi ~\mid ~D_{A}\phi$

где $p\in PROP$, $j\in {AGTS}$ и $A\subseteq {AGTS}$. Основной эпистемический язык ${\mathcal {L}}_{EL}$ это язык ${\mathcal {L}}_{EL}^{C}$ без операторов общего знания и распределенных знаний. Формула $\bot$ это аббревиатура от $\neg p\land p$ (для заданного $p\in PROP$), $\langle K_{j}\rangle \phi$ это аббревиатура от $\neg K_{j}\neg \phi$, $E_{A}\phi$ это аббревиатура от $\bigwedge \limits _{j\in A}K_{j}\phi$ и $C\phi$ аббревиатура для $C_{AGTS}\phi$.

Групповые понятия: общие, общие и распределенные знания.

В многоагентной среде существуют три важные эпистемические концепции: общие знания, распределенные знания и общие знания. Понятие общего знания было впервые изучено Льюисом в контексте конвенций. Затем его применили к распределенным системам. и к теории игр , где это позволяет выразить, что рациональность игроков, правила игры и набор игроков общеизвестны.

Общие знания.

Общие знания $\phi$ означает, что все в группе агентов ${AGTS}$ знает это $\phi$. Формально это соответствует следующей формуле:

$E\phi :={\underset {j\in {AGTS}}{\bigwedge }}K_{j}\phi .$

Общее знание.

Общее знание $\phi$ означает, что все знают $\phi$ но также все знают, что все знают $\phi$, что все знают, что все знают, что все знают, что все знают $\phi$, и так до бесконечности . Формально это соответствует следующей формуле

$C\phi :=E\phi \land EE\phi \land EEE\phi \land \ldots$

Поскольку мы не допускаем бесконечного соединения, понятие общего знания придется ввести в нашем языке как примитивное.

Прежде чем определить язык с помощью этого нового оператора, мы собираемся привести пример, введенный Льюисом , который иллюстрирует разницу между понятиями общего знания и общеизвестного. Льюис хотел знать, какие знания необходимы для того, чтобы утверждение $p$: «Каждый водитель должен ехать справа» — таково соглашение группы агентов. Другими словами, он хотел знать, какие знания необходимы, чтобы каждый чувствовал себя безопасно при правостороннем движении. Предположим, что есть только два агента $i$ и $j$. Тогда все знают $p$ (формально $Ep$) недостаточно. Действительно, все еще возможно, что агент $i$ считает возможным, что агент $j$ не знает $p$ (формально $\neg K_{i}K_{j}p$). В этом случае агент $i$ не будет чувствовать себя в безопасности при движении справа, потому что он может подумать, что агент $j$, не зная $p$, мог ехать левосторонне. Чтобы избежать этой проблемы, мы могли бы предположить, что все знают, что все знают, что $p$ (формально $EEp$). Этого опять-таки недостаточно, чтобы гарантировать, что все будут чувствовать себя в безопасности при правостороннем движении. Действительно, все еще возможно, что агент $i$ считает возможным, что агент $j$ считает возможным, что агент $i$ не знает $p$ (формально $\neg K_{i}K_{j}K_{i}p$). В этом случае и из $i$точка зрения, $j$ считает возможным, что $i$, не зная $p$, будет левостороннее движение. Итак, от $i$точка зрения, $j$ также может двигаться слева (по тому же аргументу, что и выше). Так $i$ не будет чувствовать себя в безопасности при движении справа. Рассуждая по индукции, Льюис показал, что для любого $k\in \mathbb {N}$, $Ep\land E^{1}p\land \ldots \land E^{k}p$ недостаточно, чтобы водители чувствовали себя в безопасности при движении справа. На самом деле нам нужна бесконечная конъюнкция. Другими словами, нам нужны общие знания о $p$: $Cp$.

Распределенные знания.

Распределенные знания $\phi$ означает, что если бы агенты полностью извлекли свои знания, они бы знали, что $\phi$ держит. Другими словами, знание $\phi$ распределяется между агентами. Формула $D_{A}\phi$ читается как «распределение знаний среди множества агентов». $A$ что $\phi$ держит».

Семантика

Эпистемическая логика – это модальная логика. Итак, то, что мы называем эпистемической моделью ${\mathcal {M}}=(W,R_{1},\ldots ,R_{n},I)$ — это просто модель Крипке , определенная в модальной логике. Набор $W$ — непустое множество, элементы которого называются возможными мирами , а интерпретация $I:W\rightarrow 2^{PROP}$ — это функция, определяющая, какие пропозициональные факты (например, «У Анны красная карточка») истинны в каждом из этих миров. Отношения доступности $R_{j}\subseteq W\times W$ являются бинарными отношениями для каждого агента $j\in AGTS$; они предназначены для отражения неопределенности каждого агента (относительно реального мира и неопределенности других агентов). Интуитивно мы имеем $(w,v)\in R_{j}$ когда мир $v$ совместим с агентом $j$информация в мире $w$ или, другими словами, когда агент $j$ считает, что мир $v$ может соответствовать миру $w$ (с этой точки зрения). Мы оскорбительно пишем $w\in {\mathcal {M}}$ для $w\in W$ и $R_{j}(w)$ обозначает множество миров $\{v\in W;(w,v)\in R_{j}\}$.

Интуитивно, конкретная эпистемическая модель $({\mathcal {M}},w)$, где $w\in {\mathcal {M}}$, представляет с внешней точки зрения, как реальный мир $w$ воспринимается агентами ${AGTS}$.

Для каждой эпистемической модели ${\mathcal {M}}$, каждый $w\in {\mathcal {M}}$ и каждый $\phi \in {\mathcal {L}}_{\textsf {EL}}$, мы определяем ${\mathcal {M}},w\models \phi$ индуктивно по следующим условиям истинности :

${\mathcal {M}},w\models p$	если только	$p\in I(w)$
${\mathcal {M}},w\models \neg \phi$	если только	${\textrm {it~is~not~the~case~that~}}{\mathcal {M}},w\models \phi$
${\mathcal {M}},w\models \phi \land \psi$	если только	${\mathcal {M}},w\models \phi {\textrm {~and~}}{\mathcal {M}},w\models \psi$
${\mathcal {M}},w\models K_{j}\phi$	если только	${\textstyle {\textrm {for~all~}}v\in R_{j}(w),{\mathcal {M}},v\models \phi }$
${\mathcal {M}},w\models C_{A}\phi$	если только	${\textrm {for~all~}}v\in \left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}(w),{\mathcal {M}},v\models \phi$
${\mathcal {M}},w\models D_{A}\phi$	если только	${\textrm {for~all~}}v\in {\underset {j\in A}{\bigcap }}R_{j}(w),{\mathcal {M}},v\models \phi$

где $\left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}$ является транзитивным замыканием ${\underset {j\in A}{\bigcup }}R_{j}$: у нас это есть $v\in \left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}(w)$ тогда и только тогда, когда существуют $w_{0},\ldots ,w_{m}\in {\mathcal {M}}$ и $j_{1},\ldots ,j_{m}\in A$ такой, что $w_{0}=w,w_{m}=v$ и для всех $i\in \{1,\ldots ,m\}$, $w_{i-1}R_{j_{i}}w_{i}$.

Несмотря на то, что понятие общего убеждения должно быть введено в язык как примитивное, мы можем заметить, что определение эпистемических моделей не нужно модифицировать, чтобы придать истинностное значение операторам общего знания и распределенного знания.

Пример карты:

Игроки $A$, $B$ и $C$ (обозначает Энн, Боб и Клэр) играют в карточную игру с тремя картами: красной, зеленой и синей. У каждого из них есть одна карта, но они не знают карт других игроков. У Энн красная карточка, у Боба зеленая карточка, а у Клэр синяя карточка. Этот пример изображен в заостренной эпистемической модели. $({\mathcal {M}},w)$ представлено ниже. В этом примере $AGTS:=\{A,B,C\}$ и $PROP:=\{{\color {red}{A}},{\color {green}{B}},{\color {blue}{C}},{\color {red}{B}},{\color {green}{C}},{\color {blue}{A}},{\color {red}{C}},{\color {green}{A}},{\color {blue}{B}}\}$. Каждый мир помечен пропозициональными буквами, которые истинны в этом мире и $w$ соответствует реальному миру. Есть стрелка, проиндексированная агентом $j\in \{A,B,C\}$ из возможного мира $u$ в возможный мир $v$ когда $(u,v)\in R_{j}$. Рефлекторные стрелки опущены, а это значит, что для всех $j\in \{A,B,C\}$ и все $v\in {\mathcal {M}}$, у нас это есть $(v,v)\in R_{j}$.

Пример карты: заостренная эпистемическая модель $({\mathcal {M}},w)$

${\color {red}{A}}$ означает: " $A$ имеет красную карточку''

${\color {blue}{C}}$ стоять за: " $C$ имеет синюю карту''

${\color {green}{B}}$ означает: " $B$ имеет грин-карту''

и так далее...

Когда отношения доступности являются отношениями эквивалентности (как в этом примере), и у нас есть это $(w,v)\in R_{j}$, мы говорим, что агент $j$ не могу различить мир $w$ из мира $v$ (или мир $w$ неотличим от мира $v$ для агента $j$). Так, например, ${\textstyle A}$ не может отличить реальный мир $w$ из возможного мира, где $B$ имеет синюю карту( ${\color {blue}{B}}$), $C$ есть грин-карта( ${\color {green}{C}}$) и $A$ у него еще красная карточка( ${\color {red}{A}}$).

В частности, справедливы следующие утверждения:

${\mathcal {M}},w\models ({\color {red}{A}}\land K_{A}{\color {red}{A}})\land ({\color {blue}{C}}\land K_{C}{\color {blue}{C}})\land ({\color {green}{B}}\land K_{B}{\color {green}{B}})$

«Все агенты знают цвет своей карты».

${\mathcal {M}},w\models K_{A}({\color {blue}{B}}\vee {\color {green}{B}})\land K_{A}({\color {blue}{C}}\vee {\color {green}{C}})$

' $A$ знает это $B$ имеет либо синюю, либо зеленую карту, и это $C$ имеет либо синюю, либо зеленую карту».

${\mathcal {M}},w\models E({\color {red}{A}}\vee {\color {blue}{A}}\vee {\color {green}{A}})\land C({\color {red}{A}}\vee {\color {blue}{A}}\vee {\color {green}{A}})$

'Все это знают $A$ имеет красную, зеленую или синюю карту, и это общеизвестно даже среди всех агентов.

Знание против веры

Мы используем те же обозначения $K_{j}$ как для знания, так и для веры. Таким образом, в зависимости от контекста $K_{j}\phi$ будет либо читать «агент $j$ Знаю , что $\phi$ держит» или «агент $j$ Б полагает, что $\phi$ держит». Принципиальное отличие состоит в том, что, в отличие от знаний, убеждения могут быть ошибочными : аксиома $K_{j}\phi \rightarrow \phi$ справедливо только для знаний, но не обязательно для убеждений. Эта аксиома, называемая аксиомой Т (истина), гласит, что если агент знает предложение, то это предложение истинно. Его часто считают отличительной чертой знания, и он не подвергался каким-либо серьезным нападкам с момента его введения Платоном в Теэтете « » .

Понятие знания может соответствовать некоторым другим ограничениям (или аксиомам), таким как $K_{j}\phi \rightarrow K_{j}K_{j}\phi$: если агент $j$ что-то знает, она знает, что она это знает. Эти ограничения могут повлиять на характер отношений доступности. $R_{j}$ который затем может соответствовать некоторым дополнительным свойствам. Итак, теперь мы собираемся определить некоторые конкретные классы эпистемических моделей, которые добавляют некоторые дополнительные ограничения на отношения доступности. $R_{j}$. Этим ограничениям соответствуют определенные аксиомы оператора знаний. $K_{j}$. Под каждым свойством мы приводим аксиому, определяющую класс эпистемических фреймов, которые обладают этим свойством. ( $K\phi$ означает $K_{j}\phi$ для любого $j\in AGTS$.)

Свойства отношений доступности и соответствующие аксиомы

сериал	$R(w)\neq \emptyset$
Д	$K\phi \rightarrow \langle K\rangle \phi$
переходный	${\textrm {If}}~w'\in R(w)~{\textrm {and}}~w''\in R(w'),~{\textrm {then}}~w''\in R(w)$
4	$K\phi \rightarrow KK\phi$
Евклидичность	${\textrm {If}}~w'\in R(w)~{\textrm {and}}~w''\in R(w),~{\textrm {then}}~w'\in R(w'')$
5	$\neg K\phi \rightarrow K\neg K\phi$
рефлексивный	$w\in R(w)$
Т	$K\phi \rightarrow \phi$
симметричный	${\textrm {If}}~w'\in R(w),~{\textrm {then}}~w\in R(w')$
Б	$\phi \rightarrow K\neg K\neg \phi$
сливающийся	${\textrm {If}}~w'\in R(w){\textrm {~and~}}w''\in R(w),{\textrm {then~there~is~}}v{\textrm {~such~that}}~v\in R(w'){\textrm {~and~}}v\in R(w'')$
.2	$\langle K\rangle K\phi \rightarrow K\langle K\rangle \phi$
слабо связан	${\textrm {If}}~w'\in R(w){\textrm {~and~}}w''\in R(w),{\textrm {~then~}}w'=w''{\textrm {~or~}}w'\in R(w''){\textrm {~or~}}w''\in R(w')$
.3	$\langle K\rangle \phi \land \langle K\rangle \psi \rightarrow \langle K\rangle (\phi \land \psi )\vee \langle K\rangle (\psi \land \langle K\rangle \phi )\vee \langle K\rangle (\phi \land \langle K\rangle \psi )$
полуевклидов	${\textrm {If~}}w''\in R(w){\textrm {~and~}}w\notin R(w''){\textrm {~and~}}w'\in R(w),{\textrm {~then~}}w''\in R(w')$
.3.2	$(\langle K\rangle \phi \land \langle K\rangle K\psi )\rightarrow K(\langle K\rangle \phi \vee \psi )$
Р1	${\textrm {If~}}w''\in R(w){\textrm {~and~}}w\neq w''{\textrm {~and~}}w'\in R(w),{\textrm {~then~}}w''\in R(w')$
.4	$(\phi \land \langle K\rangle K\phi )\rightarrow K\phi$

Об аксиомах мы говорили выше. Аксиома 4 гласит, что если агент знает предложение, то он знает, что знает его (эта аксиома также известна как «принцип КК» или «тезис КК»). В эпистемологии аксиому 4 обычно принимают интерналисты , но не экстерналисты . Аксиома 4, тем не менее, широко принята учёными-компьютерщиками (а также многими философами, включая Платона , Аристотеля , Святого Августина , Спинозу и Шопенгауэра , как Хинтикка вспоминает ). Более спорной аксиомой логики познания является аксиома 5 евклидичности: эта аксиома гласит, что если агент не знает предложения, то он знает, что он его не знает. Большинство философов (включая Хинтикку) подвергли критике эту аксиому, поскольку многочисленные примеры из повседневной жизни, похоже, опровергают ее. В общем, аксиома 5 становится недействительной, когда у агента есть ошибочные убеждения, которые могут быть вызваны, например, неправильным восприятием, ложью или другими формами обмана. Аксиома B утверждает, что не может быть такого случая, когда агент считает возможным, что он знает ложное суждение (т. е. $\neg (\neg \phi \land \neg K\neg K\phi )$). Если мы предположим, что аксиомы T и 4 верны, то аксиома B станет жертвой той же атаки, что и аксиома 5, поскольку эта аксиома выводима. Аксиома D утверждает, что убеждения агента последовательны. В сочетании с аксиомой K (где оператор знания заменяется оператором убеждения) аксиома D фактически эквивалентна более простой аксиоме D', которая передает, возможно, более явно, тот факт, что убеждения агента не могут быть противоречивыми: $\neg B\bot$. Другие сложные аксиомы .2, .3, .3.2 и .4 были введены эпистемическими логиками, такими как Ленцен и Катчера, в 1970-х годах. и представлены для некоторых из них как ключевые аксиомы эпистемической логики. Их можно охарактеризовать с точки зрения аксиом интуитивного взаимодействия, касающихся знаний и убеждений.

Аксиоматизация

Гильберта Система доказательства K для базовой модальной логики определяется следующими аксиомами и правилами вывода : для всех $j\in AGTS$,

Система доказательств ${\textsf {K}}$ для ${\mathcal {L}}_{EL}$

Опора	Все аксиомы и правила вывода логики высказываний.
К	$K_{j}(\phi \rightarrow \psi )\rightarrow (K_{j}\phi \rightarrow K_{j}\psi )$
Ни	Если $\phi$ затем $K_{j}\phi$

Аксиомы эпистемической логики очевидно отражают способ рассуждения агентов. Например, аксиома K вместе с правилом вывода Nec влечет за собой, что если я знаю $\phi$ ( $K\phi$) и я это знаю $\phi$ подразумевает $\psi$ ( $K(\phi \rightarrow \psi ))$ тогда я это знаю $\psi$ ( $K\psi$). Могут быть добавлены более строгие ограничения. Следующие системы доказательств для ${\mathcal {L}}_{\textsf {EL}}$ часто используются в литературе.

Общие системы доказательств для ${\mathcal {L}}_{EL}$

КД45

=

К+Д+4+5

С4.2

=

S4+.2

С4.3.2

=

С4+.3.2

С5

=

С4+5

С4

=

К+Т+4

С4.3

=

S4+.3

С4.4

=

С4+.4

Бр

=

К+Т+Б

Определим множество систем доказательств $\mathbb {L} _{\textsf {EL}}:=\{{\textsf {K}},{\textsf {KD45}},{\textsf {S4}},{\textsf {S4.2}},{\textsf {S4.3}},{\textsf {S4.3.2}},{\textsf {S4.4}},{\textsf {S5}}\}$.

Более того, для всех ${\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}$, мы определяем систему доказательств ${\mathcal {H}}^{\textsf {C}}$ добавив следующие схемы аксиом и правила вывода к схемам из ${\mathcal {H}}$. Для всех $A\subseteq AGTS$,

Дис	$K_{j}\phi \rightarrow D_{A}\phi$
Смешивание	$C_{A}\phi \rightarrow E_{A}(\phi \land C_{A}\phi )$
В	${\textrm {if~}}\phi \rightarrow E_{A}(\psi \land \phi ){\textrm {~then~}}\phi \rightarrow C_{A}\psi$

Относительная сила систем доказательства знаний такова:

${\textsf {S4}}\subset {\textsf {S4.2}}\subset {\textsf {S4.3}}\subset {\textsf {S4.3.2}}\subset {\textsf {S4.4}}\subset {\textsf {S5}}.$

, все теоремы Итак ${\textsf {S4.2}}$ также являются теоремами ${\textsf {S4.3}},{\textsf {S4.3.2}},{\textsf {S4.4}}$ и ${\textsf {S5}}$. Многие философы утверждают, что в наиболее общих случаях логика познания ${\textsf {S4.2}}$ или ${\textsf {S4.3}}$. Обычно в информатике и во многих теориях, разработанных в области искусственного интеллекта, логика убеждения ( доксастическая логика) принимается как ${\textsf {KD45}}$ а логика познания ( эпистемическая логика) принимается как ${\textsf {S5}}$, даже если ${\textsf {S5}}$ подходит только для ситуаций, когда у агентов нет ошибочных убеждений. ${\textsf {Br}}$ была предложена Флориди как логика понятия «информированность», которая главным образом отличается от логики знания отсутствием самоанализа у агентов.

Для всех ${\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}$, класс ${\mathcal {H}}$–модели или ${\mathcal {H}}^{\textsf {C}}$–модели – это класс эпистемических моделей, отношения доступности которых удовлетворяют перечисленным выше свойствам, определяемым аксиомами ${\mathcal {H}}$ или ${\mathcal {H}}^{\textsf {C}}$. Тогда для всех ${\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}$, ${\mathcal {H}}$ является надежным и полностью полным для ${\mathcal {L}}_{\textsf {EL}}$ относительно класса ${\mathcal {H}}$– модели и ${\mathcal {H}}^{\textsf {C}}$ является надежным и полностью полным для ${\mathcal {L}}_{\textsf {EL}}^{\textsf {C}}$ относительно класса ${\mathcal {H}}^{\textsf {C}}$–модели.

Разрешимость и сложность

Проблема выполнимости всех введенных логик разрешима . Ниже мы перечислим вычислительную сложность задачи о выполнимости каждого из них. Обратите внимание, что оно становится линейным во времени, если в языке имеется лишь конечное число пропозициональных букв. Для $n\geq 2$, если ограничиться конечным вложением, то проблема выполнимости будет NP-полной для всех рассматриваемых модальных логик. Если затем мы ограничим язык лишь конечным числом примитивных предложений, сложность во всех случаях снизится до линейной по времени.

Сложность проблемы выполнимости

Логика	$n=1$	$n\geq 2$	с общим знанием
К, С4	PSPACE	PSPACE	ВРЕМЯ ЭКСПРЕСС
КД45	НАПРИМЕР	PSPACE	ВРЕМЯ ЭКСПРЕСС
С5	НАПРИМЕР	PSPACE	ВРЕМЯ ЭКСПРЕСС

Вычислительная сложность задачи проверки модели находится в P. во всех случаях

Добавление динамики

Динамическая эпистемическая логика (DEL) — это логическая основа для моделирования эпистемических ситуаций с участием нескольких агентов и изменений, которые происходят в этих ситуациях в результате поступающей информации или, в более общем плане, входящих действий. Методология DEL такова, что она разделяет задачу представления убеждений и знаний агентов на три части:

1. Один представляет свои убеждения об исходной ситуации благодаря эпистемической модели ;
2. Один представляет свои убеждения о событии, происходящем в этой ситуации, благодаря модели события ;
3. Один представляет собой способ, которым агенты обновляют свои представления о ситуации после (или во время) возникновения события благодаря обновлению продукта .

Обычно информативное событие может представлять собой публичное объявление для всех участников формулы. $\psi$: это публичное объявление и соответствующее обновление составляют динамическую часть. Однако эпистемические события могут быть гораздо более сложными, чем простое публичное объявление, включая сокрытие информации для некоторых агентов, мошенничество, ложь, блеф и т. д. Эта сложность рассматривается, когда мы вводим понятие модели событий. Сначала мы сосредоточимся на публичных заявлениях, чтобы получить представление об основных идеях DEL.

Публичные мероприятия

В этом разделе мы предполагаем, что все события являются публичными. Мы начнем с конкретного примера использования DEL, чтобы лучше понять, что происходит. Этот пример называется « головоломка для грязных детей» . Затем мы представим формализацию этой головоломки в логике, называемой «Логика публичных объявлений» (PAL). Головоломка «грязные дети» — одна из самых известных головоломок, сыгравшая роль в развитии DEL. Другие важные головоломки включают головоломку о сумме и произведении , дилемму Монти Холла , проблему русских карт , проблему двух конвертов , парадокс Мура , парадокс палача и т. д .

Пример грязных детей:

У нас двое детей, А и Б, оба грязные. А может видеть Б, но не себя, а Б может видеть А, но не себя. Позволять $p$ быть предложением, утверждающим, что A грязно, и $q$ быть предложением, утверждающим, что B грязен.

1. Мы представляем исходную ситуацию указанной эпистемической моделью. $({\mathcal {N}},s)$ представлено ниже, где отношения между мирами являются отношениями эквивалентности. Штаты $s,t,u,v$ интуитивно представляют возможные миры, суждение (например, $p$) выполнимое в одном из этих миров интуитивно означает, что в соответствующем возможном мире интуитивная интерпретация $p$ (А грязный) верно. Связи между мирами, обозначенными агентами (A или B), интуитивно выражают идею неотличимости для агента, поставленного на карту, двух возможных миров. Например, связь между $s$ и $t$ обозначение A интуитивно означает, что A не может различить возможный мир $s$ от $t$ и наоборот. Действительно, А не может видеть себя, поэтому он не может отличить мир, в котором он грязный, от мира, в котором он не грязный. Однако он может различать миры, в которых B грязный или нет, потому что он может видеть B. Благодаря этой интуитивной интерпретации мы вынуждены предположить, что наши отношения между мирами являются отношениями эквивалентности.

   

   Исходная ситуация: точечная эпистемическая модель $({\mathcal {N}},s)$

2. Теперь предположим, что их отец приходит и объявляет, что хотя бы один грязный (формально $p\vee q$). Затем мы обновляем модель, и это дает конкретную эпистемическую модель, представленную ниже. Что мы на самом деле делаем, так это подавляем миры, где содержание объявления не выполняется. В нашем случае это мир, где $\neg p$ и $\neg q$ верны. Это подавление и есть то, что мы называем обновлением. Затем мы получаем модель, изображенную ниже. В результате объявления и A, и B знают, что по крайней мере один из них грязный. Мы можем прочитать это из эпистемической модели.

   

   Обновленная эпистемическая модель после первого анонса $p\vee q$

3. Теперь предположим, что существует второе (и последнее) объявление, в котором говорится, что ни один из них не знает, что они грязные (объявление может выражать факты о ситуации, а также эпистемические факты о знаниях, которыми обладают агенты). Затем мы аналогичным образом обновляем модель, подавляя миры, которые не удовлетворяют содержанию объявления, или, что то же самое, сохраняя миры, которые удовлетворяют объявлению. Таким образом, этот процесс обновления дает конкретную эпистемическую модель, представленную ниже. Интерпретируя эту модель, мы получаем, что A и B оба знают, что они грязные, что, по-видимому, противоречит содержанию объявления. Однако если мы предположим, что A и B оба являются прекрасными мыслителями и что это общеизвестно среди них, тогда этот вывод имеет смысл.

Обновленная эпистемическая модель после второго анонса

Логика публичного объявления (PAL):

Мы представляем синтаксис и семантику логики публичных объявлений (PAL), которая сочетает в себе черты эпистемической логики и пропозициональной динамической логики .

Мы определяем язык ${{\mathcal {L}}_{PAL}}$ индуктивно с помощью следующей грамматики в BNF :

${{\mathcal {L}}_{PAL}}:\phi ~~::=~~p~\mid ~\neg \phi ~\mid ~(\phi \land \phi )~\mid ~K_{j}\phi ~\mid ~[\phi !]\phi$

где $j\in AGTS$.

Язык ${{\mathcal {L}}_{PAL}}$ интерпретируется на основе эпистемических моделей. Условия истинности связок эпистемического языка такие же, как и в эпистемической логике (см. выше). Условие истинности для новой модальности динамического действия $[\psi !]\phi$ определяется следующим образом:

${\mathcal {M}},w\models [\psi !]\phi$

если только

${\mbox{if }}{\mathcal {M}},w\models \psi {\mbox{ then }}{\mathcal {M}}^{\psi },w\models \phi$

где ${\mathcal {M}}^{\psi }:=(W^{\psi },R_{1}^{\psi },\ldots ,R_{n}^{\psi },I^{\psi })$ с

$W^{\psi }:=\{w\in W;{\mathcal {M}},w\models \psi \}$,

$R_{j}^{\psi }:=R_{j}\cap (W^{\psi }\times W^{\psi })$ для всех $j\in \{1,\ldots ,n\}$ и

$I^{\psi }(w):=I(w){\textrm {~for~all~}}w\in W^{\psi }$.

Формула $[\psi !]\phi$ интуитивно означает, что после правдивого объявления $\psi$, $\phi$ держит. Публичное объявление о предложении $\psi$ меняет текущую эпистемическую модель, как показано на рисунке ниже.

Уничтожьте все миры, которые на данный момент не удовлетворяют $\psi$

Система доказательств ${\mathcal {H}}_{PAL}$ определенное ниже, является обоснованным и полностью полным для ${{\mathcal {L}}_{PAL}}$ относительно класса всех указанных эпистемических моделей.

${\textsf {K}}$		Аксиомы и правила вывода системы доказательств. ${\textsf {K}}$(см. выше)
Красный 1		$[\psi !]p\leftrightarrow (\psi \rightarrow p)$
Красный 2		$[\psi !]\neg \phi \leftrightarrow (\psi \rightarrow \neg [\psi !]\phi )$
Красный 3		$[\psi !](\phi \land \chi )\leftrightarrow ([\psi !]\phi \land [\psi !]\chi )$
Красный 4		$[\psi !]K_{i}\phi \leftrightarrow \left(\psi \rightarrow K_{i}(\psi \rightarrow [\psi !]\phi )\right)$

Аксиомы Red 1 – Red 4 называются аксиомами редукции , поскольку они позволяют свести любую формулу ${{\mathcal {L}}_{PAL}}$ к доказуемо эквивалентной формуле ${\mathcal {L}}_{EL}$ в ${\mathcal {H}}_{PAL}$. Формула $[q!]Kq$ является теоремой , доказуемой в ${\mathcal {H}}_{PAL}$. В нем говорится, что после публичного объявления $q$, агент знает это $q$ держит.

PAL разрешима , его проблема проверки модели разрешима за полиномиальное время , а его проблема выполнимости является PSPACE-полной .

Головоломка для мутных детей, формализованная с помощью PAL:

Вот некоторые из утверждений, которые содержатся в головоломке для детей, формализованной в PAL.

${\mathcal {N}},s\models p\land q$

«В исходной ситуации А грязен, а Б грязен».

${\mathcal {N}},s\models (\neg K_{A}p\land \neg K_{A}\neg p)\land (\neg K_{B}q\land \neg K_{B}\neg q)$

«В исходной ситуации А не знает, грязен ли он, и Б тоже».

${\mathcal {N}},s\models [p\vee q!](K_{A}(p\vee q)\land K_{B}(p\vee q))$

«После публичного объявления о том, что по крайней мере один из детей А и Б грязный, они оба знают, что по крайней мере один из них грязный». Однако:

${\mathcal {N}},s\models [p\vee q!]((\neg K_{A}p\land \neg K_{A}\neg p)\land (\neg K_{B}q\land \neg K_{B}\neg q))$

«После публичного объявления о том, что по крайней мере один из детей А и Б грязный, они все еще не знают, что они грязные». Более того:

${\mathcal {N}},s\models [p\vee q!][(\neg K_{A}p\land \neg K_{A}\neg p)\land (\neg K_{B}q\land \neg K_{B}\neg q)!](K_{A}p\land K_{B}q)$

«После последовательных публичных заявлений о том, что по крайней мере один из детей А и Б грязный и что они все еще не знают, грязные ли они, А и Б оба знают, что они грязные».

В этом последнем утверждении мы видим интересную особенность процесса обновления: формула не обязательно верна после ее объявления. Это то, что мы технически называем «самосохраняемостью», и эта проблема возникает для эпистемических формул (в отличие от пропозициональных формул). Не следует путать объявление и обновление, вызванное этим объявлением, которое может отменить некоторую информацию, закодированную в объявлении.

Произвольные события

В этом разделе мы предполагаем, что события не обязательно являются публичными, и фокусируемся на пунктах 2 и 3 выше, а именно на том, как представлять события и на том, как обновлять эпистемическую модель с таким представлением событий посредством обновления продукта.

Модель событий

Эпистемические модели используются для моделирования того, как агенты воспринимают реальный мир. Их восприятие также можно описать с точки зрения знаний и убеждений о мире и убеждениях других агентов. Суть подхода DEL заключается в том, что можно описать, как событие воспринимается агентами очень похожим образом. Действительно, восприятие события агентами также можно описать с точки зрения знаний и убеждений. Например, частное объявление $A$ к $B$ то, что ее карта красная, также можно описать с точки зрения знаний и убеждений: в то время как $A$ рассказывает $B$ что ее карта красная (событие $e$) $C$ считает , что ничего не происходит (событие $f$). Это приводит к определению понятия модели событий, определение которого очень похоже на определение эпистемической модели.

Заостренная модель событий $({\mathcal {E}},e)$ представляет собой то, как фактическое событие, представленное $e$ воспринимается агентами. Интуитивно, $f\in R_{j}(e)$ означает, что хотя возможное событие, представленное $e$ происходит, агент $j$ считает возможным, что возможное событие, представленное $f$ происходит на самом деле.

Модель событий — это кортеж ${\mathcal {E}}=(W^{\alpha },R_{1}^{\alpha },\ldots ,R_{m}^{\alpha },I^{\alpha })$ где:

• $W^{\alpha }$ непустое множество возможных событий ,
• $R_{j}^{\alpha }\subseteq W^{\alpha }\times W^{\alpha }$ — это бинарное отношение, называемое отношением доступности на $W^{\alpha }$, для каждого $j\in AGTS$,
• $I^{\alpha }:W^{\alpha }\rightarrow {\mathcal {L}}_{\textsf {EL}}$ — это функция, называемая функцией предусловия, присваивающая каждому возможному событию формулу ${\mathcal {L}}_{\textsf {EL}}$.

$R_{j}^{\alpha }(e)$ обозначает множество $\{f\in W^{\alpha };(e,f)\in R_{j}^{\alpha }\}$ .Мы пишем $e\in {\mathcal {E}}$ для $e\in W^{\alpha }$, и $({\mathcal {E}},e)$ называется точечной моделью событий ( $e$ часто представляет собой реальное событие).

Пример карты:

Давайте вернемся к примеру с картами и предположим, что игроки $A$ и $B$ показать свою карточку друг другу. Как оказалось, $C$ заметил это $A$ показала свою визитку $B$ но не заметил этого $B$ сделал это, чтобы $A$. Игроки $A$ и $B$ знай это. Это событие представлено ниже в модели событий. $({\mathcal {E}},e)$.

Возможное событие $e$ соответствует реальному событию 'игроки $A$ и $B$ показать свои карты и карты соответственно друг другу» (с предусловием ${\color {red}{A}}\land {\color {green}{B}}$), $f$ обозначает событие «игрок $A$ показывает свою грин-карту» (с предварительным условием ${\color {green}{A}}$) и $g$ означает атомное событие 'игрок $A$ показывает свою красную карточку' (с предусловием ${\color {red}{A}}$). Игроки $A$ и $B$ показать свои карты друг другу, игроки $A$ и $B$ знать это и считать это возможным, пока игрок $C$ считает возможным, что игрок $A$ показывает свою красную карточку и также считает возможным, что игрок $A$ показывает свою грин-карту, так как он не знает ее карты. Собственно, это все, что есть у игрока $C$ считает возможным, потому что она не заметила, что $B$ показала свою визитку.

Модель точечных событий $({\mathcal {E}},e)$: Игроки A и B показывают свои карты друг другу перед игроком C.

Еще один пример событийной модели приведен ниже. Этот второй пример соответствует событию, когда Player $A$ публично показывает всем свою красную карточку. Игрок $A$ показывает свою красную карточку, игроки $A$, $B$ и $C$ «знайте» это, игроки $A$, $B$ и $C$ «знать», что каждый из них «знает» это и т. д. существует общее знание Другими словами, среди игроков $A$, $B$ и $C$ этот игрок $A$ показывает ей красную карточку.

Модель точечных событий $({\mathcal {F}},e)$

Обновление продукта

Обновление продукта DEL описано ниже. Это обновление дает новую точечную эпистемическую модель. $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)$ представляя, как новая ситуация, которая ранее была представлена $({\mathcal {M}},w)$ воспринимается агентами после наступления события, представленного $({\mathcal {E}},e)$.

Позволять ${\mathcal {M}}=(W,R_{1},\ldots ,R_{n},I)$ быть эпистемической моделью и пусть ${\mathcal {E}}=(W^{\alpha },R_{1}^{\alpha },\ldots ,R_{n}^{\alpha },I^{\alpha })$ быть моделью событий. Обновление продукта ​ ${\mathcal {M}}$ и ${\mathcal {E}}$ это эпистемическая модель ${\mathcal {M}}\otimes {\mathcal {\mathcal {E}}}=(W^{\otimes },R_{1}^{\otimes },\ldots ,R_{n}^{\otimes },I^{\otimes })$ определяется следующим образом: для всех $v\in W$ и все $f\in W^{\alpha }$,

$W^{\otimes }$	=	$\{(v,f)\in W\times W^{\alpha };{\mathcal {M}},v\models I^{\alpha }(f)\}$
$R_{j}^{\otimes }(v,f)$	=	$\{(u,g)\in W^{\otimes };u\in R_{j}(v){\textrm {~and~}}g\in R_{j}^{\alpha }(f)\}$
$I^{\otimes }(v,f)$	=	$I(v)$

Если $w\in W$ и $e\in W^{\alpha }$ таковы, что ${\mathcal {M}},w\models I^{\alpha }(e)$ затем $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)$ обозначает указанную эпистемическую модель $({\mathcal {M}}\otimes {\mathcal {E}},(w,e))$. Такое определение обновления продукта концептуально обосновано.

Пример карты:

В результате первого события, описанного выше (Игроки $A$ и $B$ показать свои карты друг другу перед игроком $C$), агенты обновляют свои убеждения. Мы получаем ситуацию, представленную в указанной эпистемической модели. $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)$ ниже. В этой четкой эпистемической модели справедливо следующее утверждение: $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)\models ({\color {green}{B}}\land K_{A}{\color {green}{B}})\land K_{C}\neg K_{A}{\color {green}{B}}.$ Там указано, что игрок $A$ знает этого игрока $B$ есть карта, но игрок $C$ «считает», что это не так.

Обновленная точечная эпистемическая модель $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)$

Результат второго события представлен ниже. В этой четкой эпистемической модели справедливо следующее утверждение: $({\mathcal {M}},w)\otimes ({\mathcal {F}},e)\models C_{\{B,C\}}({\color {red}{A}}\land {\color {green}{B}}\land {\color {blue}{C}})\land \neg K_{A}({\color {green}{B}}\land {\color {blue}{C}})$. В нем говорится, что среди $B$ и $C$ что они знают истинное состояние мира (а именно $A$ имеет красную карточку, $B$ имеет грин-карту и $C$ имеет синюю карту), но $A$ не знает этого.

Обновленная точечная эпистемическая модель $({\mathcal {M}},w)\otimes ({\mathcal {F}},e)$

Основываясь на этих трех компонентах (эпистемическая модель, модель событий и обновление продукта), Балтаг, Мосс и Солецки определили общий логический язык, вдохновленный логическим языком пропозициональной динамической логики. рассуждать об изменении информации и знаний.

См. также

• Эпистемическая логика
• Эпистемология
• Логика в информатике
• Модальная логика

Ссылки

• ван Бентем, Йохан (2011). Логическая динамика информации и взаимодействия . Издательство Кембриджского университета. ISBN  978-0521873970 .
• Ганс, ван Дитмарш; Халперн, Джозеф; ван дер Хук, Вибе; Коой, Бартелд (2015). Справочник по эпистемической логике . Лондон: издание колледжа. ISBN  978-1848901582 .
• ван Дитмарш, Ганс, ван дер Хук, Вибе и Коой, Бартелд (2007). Динамическая эпистемическая логика . Итака: том 337 библиотеки Synthese. Спрингер. ISBN  978-1-4020-5839-4 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Феджин, Рональд; Халперн, Джозеф; Моисей, Йорам; Варди, Моше (2003). Рассуждения о Знании . Кембридж: MIT Press . ISBN  978-0-262-56200-3 . Классическая ссылка.
• Хинтикка, Яакко (1962). Знание и убеждение. Введение в логику двух понятий . Итака: Издательство Корнельского университета . ISBN  978-1-904987-08-6 . .

Внешние ссылки

• Балтаг, Александру; Ренн, Брайан. «Динамическая эпистемическая логика» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• ван Дитмарш, Ганс; ван дер Хук, Вибе; Кейдж, Бартелд. «Динамическая эпистемическая логика» . Интернет-энциклопедия философии .
• Хендрикс, Винсент; Саймонс, Джон. «Эпистемическая логика» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Гарсон, Джеймс. «Модальная логика» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .