Общее знание (KQpyy [uguny)

Общее знание (англ. common knowledge) имеет место в ситуации, когда каждому индивиду из некоторой группы известно о наступлении некого события, о наличии этого знания у других представителей группы, о наличии знания о наличии знания и так далее ad infinitum. Концепция общего знания впервые возникла в философской литературе у Дэвида Келлогга Льюиса (1969). Определение общего знания было дано тогда же социологом Моррисом Фриделлом. Математическая (теоретико-множественная) интерпретация осуществлена в 1976 году Робертом Ауманном, который занимался построением эпистемической теории игр. С 1980-х годов концепцией заинтересовались исследователи в области информатики. Общее знание лежит в основе многих логических головоломок, изучением который, в частности, занимался Джон Хортон Конвей.

Общее знание связано с более слабой концепцией взаимного знания. В отличие от общего, взаимное предполагает осведомлённость о наступлении события, но никакие другие условия на знания участников не налагаются. Таким образом, общее знание всегда является взаимным (обратное неверно).

Формализация

Модальная логика (синтаксическая характеристика)

Общее знание можно определить для мультимодальных логических систем, где модальные операторы интерпретируются эпистемически. Мультимодальные системы являются расширением логики высказываний с добавлением группы агентов G и модальных операторов K_i (with i = 1, ..., n). ВыражениеK_iφ означает «агент i знает, что φ». Далее необходимо определить оператор E_G, который будет соответствовать ситуации «все в группе G знают, что»:

$E_{G}\varphi \Leftrightarrow \bigwedge _{i\in G}K_{i}\varphi ,$

Обозначив выражение $E_{G}E_{G}^{n-1}\varphi$ как$E_{G}^{n}\varphi$ при $E_{G}^{0}\varphi =\varphi$, получаем аксиому общего знания

$C\varphi \Leftrightarrow \bigwedge _{i=0}^{\infty }E^{i}\varphi$

Здесь возникает осложнение. Язык эпистемической логики оперирует конечным числом объектов, в то время как аксиому общего знания содержит конъюнкцию бесконечного числа формул. Следовательно, в языке эпистемической логики формула не является правильно построенной. Проблема решается определением термина через неподвижную точку. Общее знание является неподвижной точкой выражения $C_{G}\varphi =\varphi \wedge E_{G}(C_{G}\varphi )$. Тогда можно найти формулу $\psi$, предполагающую $E_{G}(\varphi \wedge C_{G}\varphi )$, что в пределе даст общее знание $\varphi$.

Данная синтаксическая характеристика наделяется семантикой с помощью модели Крипке. Модель задаётся (i) множеством состояний S, (ii) n отношениями перехода $R_{1},\dots ,R_{n}$, определёнными на $S\times S$, (iii) функцией пометок $\pi$. Чтобы построить семантику, необходимо сначала указать, что $K_{i}\varphi$ верно в состоянии s тогда и только тогда, когда $\varphi$ верно для всех состояний t таких, что $(s,t)\in R_{i}$. Семантика оператора общего знания создаётся рефлексивным и транзитивным замыканием $R_{i}$ для всех агентов i в G (получаемое отношение обозначается как $R_{G}$) при условии, что $C_{G}\varphi$ верно в состоянии s тогда и только тогда, когда $\varphi$ верно во всех состояниях t таких, что $(s,t)\in R_{G}$.

Теория множеств (семантическая характеристика)

Альтернативная, но эквивалентная формализация общего знания дана Робертом Ауманном в терминах теории множеств. Имеется множество состояний S. Его подмножества называются событиями. Для каждого индивида i определяется разбиение S — P_i. Разбиение служит для характеристики знания индивида в некотором состоянии. В состоянии s индивид i знает, что возникло какое-либо (но не какое именно) из состояний, входящих во множество P_i(s), которое является элементом разбиения P_i, содержащим s. В данной модели возможность ошибочного знания исключается.

Функция знания определяется так:

$K_{i}(e)=\{s\in S\mid P_{i}(s)\subset e\}$

То есть K_i(e) является множеством состояний, в которых индивид знает о наступлении события e. K_i(e) есть подмножество e.

Тогда оператор «все знают о наступлении e» определяется как

$E(e)=\bigcap _{i}K_{i}(e)$

Как и в случае модальной логики, функция E применяется итеративно, $E^{1}(e)=E(e)$ и $E^{n+1}(e)=E(E^{n}(e))$. Функция общего знания выглядит следующим образом:

$C(e)=\bigcap _{n=1}^{\infty }E^{n}(e).$

Эквивалентность подходов легко продемонстрировать. Если задана модель Ауманна, тогда можно определить соответствующую ей модель Крипке. Для этого необходимо (i) задать то же множество состояний S, (ii) задать отношения перехода $R_{i}$, определяющие классы эквивалентности, соответствующие разбиениям $P_{i}$, (iii) задать функцию пометок, присваивающую значение «верно» высказыванию p тогда и только тогда, когда состояния s такие, что $s\in E^{p}$, где $E^{p}$ есть событие из модели Ауманна, соответствующее высказыванию p. Нетрудно увидеть, что функция $R_{G}$, определённая в прошлом разделе, соответствует наилучшему общему огрублению разбиений $P_{i}$ для всех $i\in G$, что есть конечная характеристика общего знания (также дана Ауманном в 1976 году).

Примеры

Основные статьи: Задача о чумазых детях и Задача двух генералов

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

В какой-то момент на остров прибывает иностранец, собирает жителей острова и делает публичное объявление, говоря: «Как минимум один из вас имеет голубые глаза». Всем известно, что этот иностранец всегда говорит правду, и информация о том, что как минимум один островитянин имеет голубые глаза, становится общим знанием. Вопрос таков: если считать, что все жители острова логичны и это также является общим знанием, чем закончится дело?

Ответ таков: на k-ый рассвет после объявления все голубоглазые люди покинут остров. Решение может быть проведено по индукции. Если k=1, то есть на острове ровно один голубоглазый человек, то этот человек сразу осознает, что он один имеет голубые глаза, так как вокруг только зеленоглазые, и покинет остров с первым же рассветом. Если k = 2, то никто с первым рассветом остров не покинет, но эти двое, видя вокруг только по одному голубоглазому человеку и зная, что никто остров с первым рассветом не покинул (и поэтому k>1), покинут остров на второй рассвет. Легко доказать по индукции, что никто не покинет остров после первых k-1 рассветов в том и только том случае, если на острове не менее k голубоглазых людей, и что все голубоглазые люди покинут остров на k-й рассвет, если их ровно k.

В этом сценарии наибольший интерес представляет то, что при k>1 иностранец сообщает островитянам только то, что они знают и так: что среди них есть голубоглазые. Важно же то, что до того, как этот факт был озвучен, он не был общим знанием.

Примером задачи иллюстрирующем невозможность достичь общее знание в случае надёжного канала связи является задача двух генералов. Есть две армии, каждая руководимая своим генералом, готовятся к штурму города. Лагеря этих армий располагаются на двух холмах, разделённых долиной. Единственным способом связи между генералами является отправка посыльных с сообщениями через долину. Но долина занята противником и любой из посыльных может быть перехвачен. Проблема заключается в том, что, генералы заранее (пока была связь) приняли принципиальное решение о штурме, но не согласовали точное время штурма. Сложность задачи заключается в невозможности разработать алгоритм гарантированного обмена сообщениями.

Ссылки

• Юрий Устиновский. О мудрецах и неверных жёнах  (неопр.). Элементы (30 июля 2012).