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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Примечания

Ссылки

• Юрий Устиновский. (неопр.) . Элементы (30 июля 2012).