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

Эпистемическая логика — это разновидность модальной логики, изучающая понятия знания и веры. Как всякая логика, она направлена на анализ умозаключений о знании и вере: какие принципы, связывающие эти понятия, интуитивно приемлемы? Подобно эпистемологии, термин происходит от греческого слова ${\displaystyle \epsilon \pi \iota \sigma \tau \eta \mu \eta }$ («эпистеме», знание). В отличие от логики, эпистемология исследует природу и пределы человеческого знания — например, отвечает на вопросы «что есть знание?» или «как можно овладеть знанием?». Считается, что эпистемическая логика возникла в средние века благодаря трудам Бёрли и Оккама^[7]. Формальное же направление на базе модальной логики было открыто в 1962 году работой Яакко Хинтикки^[8]. В результате в 1960-х развернулась дискуссия о принципах для знания и веры, были сформулированы и проанализированы различные аксиомы^[9]. Среди них, например, аксиомы взаимодействия ${\displaystyle Kp\rightarrow Bp}$ и ${\displaystyle Bp\rightarrow KBp}$: если агент знает ${\displaystyle p}$, то он также верит в ${\displaystyle p}$, а если верит — то знает, что верит в ${\displaystyle p}$. В последние десятилетия философские идеи эпистемической логики были заимствованы экономистами^[10], искусственному интеллекту и теоретической информатике^[11], где вопросы рассуждения о знании — одни из центральных. В новых приложениях эпистемическая логика дополнилась новыми ракурсами и возможностями, в том числе задачами вычислимости.

Обозначим через ${\displaystyle AGTS=\{1,\ldots ,n\}}$ конечное множество агентов, а через ${\displaystyle PROP}$ — множество пропозициональных переменных.

Эпистемический язык — это расширение базового мультимодального языка модальной логики операторами общего знания ${\displaystyle C_{A}}$ и распределённого знания ${\displaystyle D_{A}}$. Формально, эпистемический язык ${\displaystyle {\mathcal {L}}_{\textsf {EL}}^{C}}$ определяется по грамматике (в БНФ): ${\displaystyle {\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 }$ где ${\displaystyle p\in PROP}$, ${\displaystyle j\in AGTS}$, ${\displaystyle A\subseteq AGTS}$. Базовый эпистемический язык ${\displaystyle {\mathcal {L}}_{EL}}$ — это язык ${\displaystyle {\mathcal {L}}_{EL}^{C}}$ без операторов общего и распределённого знания. Формула ${\displaystyle \bot }$ — сокращение для ${\displaystyle \neg p\land p}$ (для некоторого ${\displaystyle p\in PROP}$), ${\displaystyle \langle K_{j}\rangle \phi }$ — это ${\displaystyle \neg K_{j}\neg \phi }$, ${\displaystyle E_{A}\phi }$ — это ${\displaystyle \bigwedge \limits _{j\in A}K_{j}\phi }$, а ${\displaystyle C\phi }$ — это ${\displaystyle C_{AGTS}\phi }$.

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

В контексте нескольких агентов выделяют три важных эпистемических понятия: общее знание, распределённое знание и совместное знание. Понятие общего знания впервые было рассмотрено Дэвидом Льюисом применительно к конвенциям^[12]. Позднее его применяли к распределённым вычислениям^[11] и теории игр^[13], где оно позволяет выразить, что игрокам, правилам игры и числу участников эти положения известны и их знание разделяется всеми.

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

Общее знание ${\displaystyle \phi }$ означает, что каждый агент из группы ${\displaystyle AGTS}$ знает ${\displaystyle \phi }$: ${\displaystyle E\phi :={\underset {j\in {AGTS}}{\bigwedge }}K_{j}\phi .}$

Совместное знание.

Совместное знание ${\displaystyle \phi }$ означает не только, что каждый знает ${\displaystyle \phi }$, но и что каждый знает, что каждый знает ${\displaystyle \phi }$, и так далее — бесконечно. Формально: ${\displaystyle C\phi :=E\phi \land EE\phi \land EEE\phi \land \ldots }$ Поскольку бесконечные конъюнкции не допускаются, оператор совместного знания задаётся в языке как примитив.

Классическим примером различия общего и совместного знания служит задача о конвенции Льюиса. Пусть только два агента ${\displaystyle i}$ и ${\displaystyle j}$. Если оба знают p="все едут по правой полосе" (то есть ${\displaystyle Ep}$), этого недостаточно: ${\displaystyle i}$ может считать возможным, что ${\displaystyle j}$ не знает ${\displaystyle p}$ (${\displaystyle \neg K_{i}K_{j}p}$) и поэтому будет опасаться ехать вправо. Распространяя это рассуждение на любую конечную длину цепочки «знаний о знании», получаем, что только совместное знание ${\displaystyle Cp}$ гарантирует уверенность.

Распределённое знание.

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

Эпистемическая логика формализуется как модальная логика. Эпистемическая модель ${\displaystyle {\mathcal {M}}=(W,R_{1},\ldots ,R_{n},I)}$ — это крипке-модель, где ${\displaystyle W}$ — множество возможных миров, ${\displaystyle I:W\rightarrow 2^{PROP}}$ определяет, какие атомарные высказывания истинны в каждом мире, а ${\displaystyle R_{j}\subseteq W\times W}$ — бинарное отношение (достижимости) для каждого агента ${\displaystyle j\in AGTS}$, описывающее его неопределённость. ${\displaystyle (w,v)\in R_{j}}$ тогда и только тогда, когда в мире ${\displaystyle w}$ для агента ${\displaystyle j}$ возможен мир ${\displaystyle v}$.

Под указанной эпистемической моделью ${\displaystyle ({\mathcal {M}},w)}$ понимается пара: модель и актуальный мир ${\displaystyle w\in {\mathcal {M}}}$, которая отражает видение ситуации агентами.

Индуктивно определяются условия истинности ${\displaystyle {\mathcal {M}},w\models \phi }$ для ${\displaystyle \phi \in {\mathcal {L}}_{\textsf {EL}}}$ для любого ${\displaystyle w\in {\mathcal {M}}}$:

если и только если | ${\displaystyle p\in I(w)}$

если и только если | ${\displaystyle {\mathcal {M}},w\models \phi }$ и ${\displaystyle {\mathcal {M}},w\models \psi }$

если и только если | для всех ${\displaystyle v\in R_{j}(w)\colon {\mathcal {M}},v\models \phi }$

если и только если | для всех ${\displaystyle v\in \left(\bigcup _{j\in A}R_{j}\right)^{+}(w)\colon {\mathcal {M}},v\models \phi }$

если и только если | для всех ${\displaystyle v\in \bigcap _{j\in A}R_{j}(w)\colon {\mathcal {M}},v\models \phi }$

Здесь ${\displaystyle \left(\bigcup _{j\in A}R_{j}\right)^{+}}$ — транзитивное замыкание объединения ${\displaystyle R_{j}}$ по ${\displaystyle j\in A}$.

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

Игроки ${\displaystyle A}$, ${\displaystyle B}$ и ${\displaystyle C}$ (Анна, Боб и Клара) играют с тремя картами: красной, зелёной и синей. Каждый держит только одну карту и не знает карт других игроков. Пример моделируется указанной моделью ${\displaystyle ({\mathcal {M}},w)}$, где

${\displaystyle AGTS=\{A,B,C\}}$, а ${\displaystyle PROP}$ — утверждения о принадлежности карт. Стрелки, подписанные агентом, обозначают его неразличимость миров. Например, ${\displaystyle A}$ не отличает реальный мир ${\displaystyle w}$ от мира, где ${\displaystyle B}$ держит синюю, ${\displaystyle C}$ — зелёную, а у ${\displaystyle A}$ — красная.

В частности, верны следующие утверждения: ${\displaystyle {\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}})}$ — все игроки знают цвет своей карты.

Одно и то же обозначение ${\displaystyle K_{j}}$ можно использовать для знания и веры. Различие в следующем: знание подразумевает истинность (аксиома ${\displaystyle K_{j}\phi \rightarrow \phi }$), а вера — нет. Эту аксиому, называемую T (истинность), часто считают отличительной чертой знания; она была введена ещё в «Теэтете» Платона.

Различные свойства оператора знания выражаются через ограничения на отношения достижимости ${\displaystyle R_{j}}$. Разным классам этих отношений соответствуют разные аксиомы, приведённые в таблице:

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

серийность	${\displaystyle R(w)\neq \emptyset }$
D	${\displaystyle K\phi \rightarrow \langle K\rangle \phi }$
транзитивность	${\displaystyle w'\in R(w)~\wedge ~w''\in R(w')\Rightarrow w''\in R(w)}$
4	${\displaystyle K\phi \rightarrow KK\phi }$
евклидовость	${\displaystyle w'\in R(w)~\wedge ~w''\in R(w)\Rightarrow w'\in R(w'')}$
5	${\displaystyle \neg K\phi \rightarrow K\neg K\phi }$
рефлексивность	${\displaystyle w\in R(w)}$
T	${\displaystyle K\phi \rightarrow \phi }$
симметричность	${\displaystyle w'\in R(w)\Rightarrow w\in R(w')}$
B	${\displaystyle \phi \rightarrow K\neg K\neg \phi }$
конфлюэнтность	${\displaystyle w'\in R(w)\wedge w''\in R(w)\Rightarrow \exists v\cdot (v\in R(w')\wedge v\in R(w''))}$
.2	${\displaystyle \langle K\rangle K\phi \rightarrow K\langle K\rangle \phi }$
слабая связанность	${\displaystyle w',w''\in R(w)\Rightarrow w'=w''\vee w'\in R(w'')\vee w''\in R(w')}$
.3	${\displaystyle \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 )}$
полуевклидовость	${\displaystyle w''\in R(w)\wedge w\notin R(w'')\wedge w'\in R(w)\Rightarrow w''\in R(w')}$
.3.2	${\displaystyle (\langle K\rangle \phi \land \langle K\rangle K\psi )\rightarrow K(\langle K\rangle \phi \vee \psi )}$
R1	${\displaystyle w''\in R(w)\wedge w\neq w''\wedge w'\in R(w)\Rightarrow w''\in R(w')}$
.4	${\displaystyle (\phi \land \langle K\rangle K\phi )\rightarrow K\phi }$

Аксиома 4 (KK-принцип) поддерживается интерналистами (в эпистемологии), однако экстерналисты часто её критикуют^[14]. У информатиков, напротив, аксиома 4 стандартна. Аксиома 5 (евклидовость), напротив, подвергается критике, так как в реальной жизни есть знание о ложных убеждениях.

Гильбертовская аксиоматика системы K для базовой модальной логики такова (для любого ${\displaystyle j\in AGTS}$):

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

Пропозициональная логика	Все аксиомы и правила пропозициональной логики
K	${\displaystyle K_{j}(\phi \rightarrow \psi )\rightarrow (K_{j}\phi \rightarrow K_{j}\psi )}$
Nec	Если ${\displaystyle \phi }$, то ${\displaystyle K_{j}\phi }$

Строже можно задавать дополнительные системы для ${\displaystyle {\mathcal {L}}_{\textsf {EL}}}$:

Типовые доказательные системы для ${\displaystyle {\mathcal {L}}_{EL}}$

KD45

=

K+D+4+5

S4.2

=

S4+.2

S4.3.2

=

S4+.3.2

S5

=

S4+5

S4

=

K+T+4

S4.3

=

S4+.3

S4.4

=

S4+.4

Br

=

K+T+B

Пусть ${\displaystyle \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}}\}}$. Для любого ${\displaystyle {\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}}$ система ${\displaystyle {\mathcal {H}}^{\textsf {C}}}$ дополняется схемами:

Dis	${\displaystyle K_{j}\phi \rightarrow D_{A}\phi }$
Mix	${\displaystyle C_{A}\phi \rightarrow E_{A}(\phi \land C_{A}\phi )}$
Ind	Если ${\displaystyle \phi \rightarrow E_{A}(\psi \land \phi )}$, то ${\displaystyle \phi \rightarrow C_{A}\psi }$

Иерархия мощностей систем: ${\displaystyle {\textsf {S4}}\subset {\textsf {S4.2}}\subset {\textsf {S4.3}}\subset {\textsf {S4.3.2}}\subset {\textsf {S4.4}}\subset {\textsf {S5}}.}$ Многие философы считают наиболее общей логикой знания ${\displaystyle {\textsf {S4.2}}}$ или ${\displaystyle {\textsf {S4.3}}}$^[15][16]. Для логики веры в искусственном интеллекте стандартен класс ${\displaystyle {\textsf {KD45}}}$, для логики знания — ${\displaystyle {\textsf {S5}}}$.

Каждая система ${\displaystyle {\mathcal {H}}}$ и ${\displaystyle {\mathcal {H}}^{\textsf {C}}}$ является корректной и полной для своего класса моделей.

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

Сложность задачи выполнимости

Логика	${\displaystyle n=1}$	${\displaystyle n\geq 2}$	с общим знанием
K, S4	PSPACE	PSPACE	EXPTIME
KD45	NP	PSPACE	EXPTIME
S5	NP	PSPACE	EXPTIME

Задача проверки моделей для всех перечисленных логик лежит в P.

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

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

Информационное событие может быть, например, публичным объявлением формулы ${\displaystyle \psi }$; это и есть динамический компонент. Однако DEL охватывает куда более сложные события: частичные объявления, сокрытие информации, обман, блеф и т. п.