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

Эпистемическая логика создана для изучения понятия знания и является направлением в модальной логике. Начнём с примера, который иллюстрирует понятие знания.

Задача о грязных детях

В песочнице играют $n\,\!$ детей $(n\geq 1)\,\!$. Мама предупреждает их: "Если кто-нибудь из вас запачкается, у него будут большие проблемы". Предположим, что $k\,\!$ детей $(k\leq n)\,\!$ запачкали свои лбы (и, следовательно, не знают, чистые они или нет). Чтобы как-то помочь детям, папа заявляет им: "Кое-кто из вас уже запачкался". Поскольку мама слышит всё, что произносится детьми и отцом (но не видит, так как, скажем, читает газету), то отцу не так просто намекнуть детям, кто из них запачкал лоб. Предположим, что отец -- математик или философ. Решение отца таково: задавать один и тот же вопрос:

"Знает ли каждый из вас, грязен он или нет?"

ровно столько раз, сколько грязных детей, т.е. $k\,\!$ раз. (Он не смущается это делать, поскольку жена и без того считает его несколько сумасшедшим). Если предположить, что дети честны, гениальны (т.е. способны вывести все следствия из их знаний), видят других и слышат отца, то решение отца пройдёт! (Важно также, что дети отвечают хором, т.е. одновременно). Оказывается, что:

1) На первые $k-1\,\!$ вопросов все дети ответят "Нет". 2) На $k\,\!$-й вопрос все грязные ответят "Да", а все чистые по-прежнему "Нет"!

Например, если $k=2\,\!$, то картина такая:

-- чистый

-- грязный

В этом случае, ответ на первый вопрос будет "Нет" для каждого ребёнка, поскольку каждый из них видит хотя бы одного грязного (ребёнок может ответить "Да" уже на первом шагу, только если видит перед собой всех чистыми). На втором шаге каждый из грязных рассуждает так: "я вижу только одного грязного, но он на предыдущем шаге ответил "Нет" и, значит, он видел перед собой хотя бы одного грязного, т.е. это грязный я!". Следовательно, на шаге $k=2\,\!$ все грязные отвечают "Да". Чистые на втором шаге по-прежнему ответят "Нет" (проверьте!). Проверьте это для $k=1,2,3,4,5\,\!$.

Обозначим утверждение отца "кое-кто из вас уже запачкался" через $p\,\!$. Через $Ep\,\!$ обозначим тот факт, что все дети знают $p\,\!$. Аналогично

$E^{k}p\equiv {\underset {k}{\underbrace {E\ldots E} }}p\,\!$

т.е. все знают, что все знают, что все знают, и т.д. $k-1\,\!$ раз, что все знают $p\,\!$.

Пусть $k\geq 2\,\!$. Тогда и без утверждения отца каждый ребёнок видит перед собой хотя бы одного грязного. Т.е. все знали $p\,\!$ и без утверждения отца. Так что же нового дало публичное заявление отцом факта $p\,\!$ детям? Оно дало не только $Ep\,\!$, но и $EEp,EEEp,\ldots ,E^{k}p\,\!$, для любого $k-1\,\!$! Т.е. отец сделал $p\,\!$ общим знанием детей (common knowledge). Проверьте, что до утверждения отца имело место $E^{k-1}p\,\!$, но не $E^{k}p\,\!$! (возьмите $k=2,3,4,5\,\!$) $E^{k-1}p\,\!$ не достаточно для того, чтобы дети определили на $k\,\!$-ом шаге, кто из них грязный, а $E^{k}p\,\!$ уже достаточно! (Отец, конечно, сообщил им гораздо больше.)

Кроме того, чтобы решение отца было решением, необходимо дополнительно предположить:

$E^{k-1}\,\!$"все дети честны, гениальны, чувствительны и т.д."

Например, если $k=2\,\!$, то после первого вопроса грязный не был бы уверен, что второй грязный, ответив "Нет" на первый вопрос, сказал правду.

Вопрос: может ли отец сделать $p\,\!$ общим знанием детей не заявляя $p\,\!$ им публично?

Носители знания в эпистемологии называются агентами. Агентами могут быть дети, роботы, программы (в этом случае знанием программы может быть память к которой у неё есть доступ) и т.д.

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

Описание языка

Синтаксис

Мир, в котором находятся агенты, описывается свойствами (например, "снег белый" - свойство нашего мира). Для обозначения различных свойств различных миров используются пропозициональные буквы:

$p_{1},p_{2},\ldots ,p_{k},\ldots \,\!$

Для каждого агента (предположим, что их конечное число, n штук) с номером $i\,\!$ вводится знак $K_{i}\,\!$. Интуитивно, если $\varphi \,\!$ - некоторое свойство, то $K_{i}\varphi \,\!$ означает "$i\,\!$-й агент знает $\varphi \,\!$". Отождествим агентов с их номерами $\{1,\ldots ,n\}\,\!$. Пусть $G\subseteq \{1,\ldots ,n\}\,\!$ множество агентов. Для каждого такого G вводятся символы $E_{G},C_{G},D_{G}\,\!$. Интуитивно:

$E_{G}\varphi \equiv \,\!$ "Все агенты из $G\,\!$ знают $\varphi \,\!$"

$C_{G}\varphi \equiv \,\!$ "$\varphi \,\!$ - общее знание агентов из $G\,\!$" $\equiv E_{G}\varphi ,E_{G}E_{G}\varphi ,\ldots ,E_{G}^{k}\varphi ,\ldots \,\!$

$D_{G}\varphi \equiv \,\!$ "$\varphi \,\!$ - дистрибутивное зание агентов из $G\,\!$" $\equiv \,\!$ "$\varphi \,\!$ это такое знание, которое может быть получено в результате опроса агентов из $G\,\!$ (при этом каждый агент в отдельности может не знать $\varphi \,\!$"

Логические связки: $\wedge \,\!$ ("и"), $\neg \,\!$ ("не"), $\vee \,\!$ ("или") ...

 \mathfrak{M} \models \varphi\,\!</math> и ${\mathfrak {M}}\models \psi \,\!$

1. ${\mathfrak {M}},s\models \neg \varphi \Leftrightarrow {\mathfrak {M}},s\not \models \varphi \,\!$
2. ${\mathfrak {M}},s\models K_{i}\varphi \Leftrightarrow \forall t\in S{\big (}(s,t)\in K_{i}\Rightarrow {\mathfrak {M}},t\models \varphi {\big )}\,\!$
3. ${\mathfrak {M}},s\models E_{G}\varphi \Leftrightarrow \forall i\in G:{\mathfrak {M}},s\models K_{i}\varphi \,\!$
4. ${\mathfrak {M}},s\models C_{G}\varphi \Leftrightarrow \forall k\geq 1:{\mathfrak {M}},s\models E_{G}^{k}\varphi \,\!$
5. ${\mathfrak {M}},s\models D_{G}\varphi \Leftrightarrow \forall t\in S{\big (}(s,t)\in {\underset {i\in G}{\cap }}K_{i}\Rightarrow {\mathfrak {M}},t\models \varphi {\big )}\,\!$

Итак, согласно пункту 4, агент, находясь в некотором состоянии $s\in S\,\!$ знает $\varphi \,\!$, если $\varphi \,\!$ истинно во всех для него состояниях.

Пусть ${\mathfrak {M}}\,\!$ - структура Крипке для трёх детей (см. выше). Проверьте, что:

${\mathfrak {M}},011\models K_{2}p_{3};\,\,\,{\mathfrak {M}},111\models \neg K_{2}p_{2};\,\,\,{\mathfrak {M}},010\models E_{\{2,3\}}\neg p_{1};\,\,\,{\mathfrak {M}},110\models C_{\{2,3\}}p_{1}\,\!$

Определения

${\mathfrak {M}}\models \varphi \equiv \forall s\in S:{\mathfrak {M}},s\models \varphi \,\!$

$\models \varphi \,\!$ ($\varphi \,\!$ - универсально истинна) $\equiv \forall {\mathfrak {M}}:{\mathfrak {M}}\models \varphi \,\!$

$\varphi \,\!$ - выполнима $\equiv \exists {\mathfrak {M}}\,\exists s\in S:{\mathfrak {M}},s\models \varphi \,\!$

Проверьте, что следующие формулы универсально истинны для любого $i\,\!$:

$K_{i}(\varphi \to \psi )\to (K_{i}\varphi \to K_{i}\psi )\,\!$ (дистрибутивность)

$K_{i}\varphi \to \varphi \,\!$ (аксиома знания)

$K_{i}\varphi \to K_{i}K_{i}\varphi \,\!$ (позитивная интроспекция)

$\neg K_{i}\varphi \to K_{i}\neg K_{i}\varphi \,\!$ (негативная интроспекция)

Проверьте, что если ${\mathfrak {M}}\models \varphi \,\!$, то ${\mathfrak {M}}\models K_{i}\varphi \,\!$.