Ещё одни лекции В.А. Захарова, страница 31

Посколькузадачи решают люди, в качестве интерпретаций могутвыступать способности людей решать задачи.Но эти способности у людей со временем изменяются. Значит,интерпретации должны быть динамическими .Рассмотрим модель идеального математика (DutchMathematician), которыйможет пребывать в разных состояниях знания ипереходить из одних состояний знания в другие;в каждом состоянии знания он точно знает, какие изэлементарных задач он умеет решать, а какие нет;не утрачивает навыков в решении задач при переходе изодного состояния знания в другое.ИНТУИЦИОНИСТСКАЯ ЛОГИКАОпределение (модель Крипке)Пусть P = {P1 , P2 , .

. . , Pn , . . . } — множество атомарныхформул (названия задач).Интуиционистская интерпретация — это реляционная системаI = S, R, ξ, в которой1. S = ∅ — множество состояний (состояний знания);2. R ⊆ S × S — отношение переходов на S, которое являетсяотношением нестрогого частичного порядка:рефлексивноеR(s, s);транзитивноеR(s1 , s2 )&R(s2 , s3 ) ⇒ R(s1 , s3 );антисимметричное R(s1 , s2 )&R(s2 , s1 ) ⇒ s1 = s2 ;3. ξ : S × P → {true, false} — оценка атомарных формул,удовлетворяющая условию монотонности:R(s1 , s2 ) & ξ(P, s1 ) = true ⇒ ξ(P, s2 ) = true.ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации?ys1@@@@?s2y?s4y?s5y@?Rs@3 y @@@@@?Rs@6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации?s4y? P = falseутро ys1 Q = false@@@@@??s2Rs@y3 y @@@@@??s5Rs@y6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false@??s2 Q = falseRфирма PROGs@y3 y @@@@@???s4s5Rs@yy6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false@??s2 Q = falseRs@y3 y @@@@P = false@???s4 Q = trues5Rs@yy6 y экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false P = true @??s2 Q = false Q = false s@Rлекцияy3 y @@@@P = false@???s4 Q = trues5Rs@yy6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false P = true @??s2 Q = false Q = false s@Ry3 y @@@@P = trueP = false@???s4 Q = trues5Rys@Q = falsey6 y экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false P = true @??s2 Q = false Q = false s@Ry3 y @@@@P = true @P = falseP = true???s4 Q = trues5RyQ = true s@Q = falsey6 y экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false P = true @??s2 Q = false Q = false s@Ry3 y @@@@P = falseP = trueP = true @???s4 Q = trues5RyQ = falseQ = true s@y6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАОпределение (семантика Крипке)Пусть I = S, R, ξ — интуиционистская интерпретация.

Тогдаотношение выполнимости I , s |=I ϕ формулы ϕ в состоянии sинтерпретации I определяется так:1. если ϕ = P ∈ P, то I , s |=I ϕ ⇐⇒ ξ(s, P) = true;2. I , s |=I ϕ1 &ϕ2 ⇐⇒ I , s |=I ϕ1 и I , s |=I ϕ2 ;3. I , s |=I ϕ1 ∨ ϕ2 ⇐⇒ I , s |=I ϕ1 или I , s |=I ϕ2 ;4. I , s |=I ϕ1 → ϕ2 ⇐⇒ для любого состояния s , если(s, s ) ∈ R и I , s |=I ϕ1 , то I , s |=I ϕ2 ;5. I , s |=I ¬ϕ1 ⇐⇒ для любого состояния s , если(s, s ) ∈ R, то I , s |=I ϕ1 .Формула ϕ называется интуиционистски общезначимой(законом интуиционистской логики), если для любойинтерпретации I и для любого состояния s верно I , s |=I ϕ.ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример необщезначимой формулы|=I P ∨ ¬PдискотекаP = false?вечерys1 ¬P = false@ P ∨ ¬P = false@@@P = false P = true @?? библиотекаs2 ¬P = true ¬P = false s@Ry3 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАДругие необщезначимые формулыДокажите самостоятельно, выбрав подходящую интерпретацию(контрмодель) I ,|=I ¬¬P → P|=I ¬(P&Q) → (¬P ∨ ¬Q)|=I ¬(P ∨ Q) → (¬P&¬Q)ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример общезначимой формулы|=I P → ¬¬PОт противного.

Допустим, что I , s0 |= P → ¬¬P. ТогдаP = true?¬¬P = falseys0¬P = trueP = falseP = true?ys1?ys2Полученное противоречие свидетельствует о невозможностипостроения контрмодели для формулы P → ¬¬P.ИНТУИЦИОНИСТСКАЯ ЛОГИКАДругие общезначимые формулыДокажите самостоятельно интуиционистскую общезначимостьследующих формул|=I ¬¬¬P → ¬P|=I (¬P ∨ ¬Q) → ¬(P&Q)|=I ¬P ∨ ¬¬PИНТУИЦИОНИСТСКАЯ ЛОГИКАНекоторые особенности интуиционистской логикиТеорема 1|=I ϕ =⇒ |=C ϕТеорема 2 (дизъюнктивное свойство)|=I ϕ ∨ ψ ⇐⇒ |=I ϕ или |=I ψТеорема 3 (экзистенциальное свойство)|=I ∀x1 . .

. ∀x1 ∃y ϕ(x1 , . . . , xn , y )⇐⇒существует такой терм t(x1 , . . . , xn ), что|=I ϕ(x1 , . . . , xn , t(x1 , . . . , xn ))t(x1 , . . . , xn ) — это программа решения задачи ϕ.Это называется «изоморфизмом Карри–Ховарда».МОДАЛЬНЫЕ ЛОГИКИЗимой идет снегЗимой всегда идет снегЗимой иногда идет снегЭто разные высказывания. И поэтому они должны бытьзаписаны разными формулами.Эти высказывания по смыслу связаны друг с другом.

И этодолжно быть отражено в формулах. Поскольку высказыванияотличаются лишь словами всегда, иногда (модальностивремени ), нужно ввести какие-то логические конструкции длявыражения этих модальностей.Может быть для этой цели пригодны кванторы?МОДАЛЬНЫЕ ЛОГИКИСтуденты посещают лекцииСтуденты обязаны посещать лекцииСтуденты имеют право посещать лекцииобязан, имею право — деонтические модальности .А будут ли пригодны кванторы в этом случае для выражениямодальностей?МОДАЛЬНЫЕ ЛОГИКИЗадача имеет решениеИзвестно, что задача имеет решениеМожно допустить, что задача имеет решениезнаю, предполагаю — эпистемические модальности.А как быть здесь?МОДАЛЬНЫЕ ЛОГИКИМодальности (в естественном языке они, как правило,представлены наречиями или служебными глаголами)выражают различные оттенки истинности (уверенность,необходимость, доказуемость, осведомленность и др.).Эти оттенки можно классифицировать:Модальности необходимогонеобходимообязательновсегдадолжназнаюдоказуемоМодальности возможноговозможноне исключеноиногдаимею правопредполагаюнепротиворечиво♦МОДАЛЬНЫЕ ЛОГИКИСинтаксис модальных формулРасширим синтаксис классической логики предикатов, введядва логических оператора (модальность необходимого) и♦ (модальность возможного),при помощи которых разрешается строить формулыследующего вида:(ϕ)«необходимо ϕ»,(♦ϕ)«возможно ϕ».Во избежание большого количества скобок, будем считать, чтомодальные операторы имеют такой же приоритет, что икванторы.МОДАЛЬНЫЕ ЛОГИКИСемантика модальных формул многообразна и непроста.РассмотримПримерВерно ли, что формула ϕ → ϕ — это закон модальнойлогики?Если — модальность времени, «всегда», то ϕ → ϕ — этозакон модальной логики.Если студенты всегда ходят на лекции, то они ходят на лекции.А вот если — деонтическая модальность, «должны», тоформула ϕ → ϕ уже не может претендовать на статуслогического закона.Если студенты должны ходить на лекции, то они ходят на лекции.Это неправда, а законы логики не зависят от прихоти студентов.МОДАЛЬНЫЕ ЛОГИКИСемантика Крипке модальных формулОпределим самое общее отношение выполнимости длямодальных формул.Пусть P = {P1 , P2 , .

. . , Pn , . . . } — множество атомарныхформул (элементарные высказывания).Модальная интерпретация или модель Крипке — этореляционная система I = W , R, ξ, в которой1. W = ∅ — множество состояний (возможные миры);2. R ⊆ S × S — отношение достижимости на W ,3. ξ : W × P → {true, false} — оценка атомарных формул.Система W , R называется шкалой Крипке (frame).Если (w , w ) ∈ R, то возможный мир w называетсяальтернативным миром для s.МОДАЛЬНЫЕ ЛОГИКИОтношение выполнимости для модальных формулПусть I = W , R, ξ — модель Крипке.

Тогда отношениевыполнимости I , s |= ϕ формулы ϕ в мире s модели Iопределяется так:1. если ϕ = P ∈ P, то I , s |= ϕ ⇐⇒ ξ(w , P) = true;2. I , w |= ϕ1 &ϕ2 ⇐⇒ I , w |= ϕ1 и I , w |= ϕ2 ;3. I , w |= ϕ1 ∨ ϕ2 ⇐⇒ I , w |= ϕ1 или I , w |= ϕ2 ;4. I , w |= ϕ1 → ϕ2 ⇐⇒ I , w |= ϕ1 или I , w |= ϕ2 ;5. I , w |= ¬ϕ1 ⇐⇒ I , w |= ϕ1 ;6.

I , w |= ϕ ⇐⇒для любого альтернативного мира w если w , w ∈ R, то I , w |= ϕ;7. I , w |= ♦ϕ ⇐⇒cуществует такой альтернативный мир w ,что w , w ∈ R и I , w |= ϕ.МОДАЛЬНЫЕ ЛОГИКИПримерМодель КрипкеI , w1 |= ♦pp = truew1 yI , w1 |= pI , w1 |= ♦pI , w5 |= pI , w5 |= ♦pw4p = false- yw2HH6HHHHHH w5j yHI@6@@@@@@@@@@@@@@@@?R?@yyw3p = falsep = truep = falseМОДАЛЬНЫЕ ЛОГИКИПростейшие свойства1. |= ♦ϕ ≡ ¬¬ϕ;2.

|= (ϕ1 → ϕ2 ) → (ϕ1 → ϕ2 );3. |= ϕ =⇒ |= ϕ (правило необходимости).В разных приложениях модальность необходимого можетпониматься по разному. Отсюда большое разнообразиемодальных логик. В разных модальных логиках отношениевыполнимости определяется на разных классах шкал. Каждаяразновидность шкал (отношения достижимости R)характеризуется определенным законом (формулой) модальнойлогики.МОДАЛЬНЫЕ ЛОГИКИХарактеристические формулы1.

ϕ → ϕрефлексивные шкалы∀w R(w , w );2. ϕ → ϕтранзитивные шкалы∀w1 ∀w2 ∀w3 (R(w1 , w2 )&R(w2 , w3 ) → R(w1 , w3 ));3. ♦ϕ → ϕсимметричные шкалы∀w1 ∀w2 (R(w1 , w2 ) → R(w2 , w1 )).Рассмотрим некоторые разновидности модальных логик,которые используются информатике.МОДАЛЬНЫЕ ЛОГИКИЭпистемические логики и мультагентные системыЭпистемические логики — это разновидности модальных логик,изучающие модальности знания и мнения (веры)идеализированных агентов. Интерес представляют вопросы отом, какими знаниям располагает субъект, насколько оносознает свои знания (и незнания), и какиепричинно-следственные связи возникают междуутверждениями, касающимися вопросов знания и веры.В эпистемической логике модальный оператор ϕ следуетпрочитывать «Я знаю, что ϕ», а ♦ϕ — «Я допускаю, что ϕ».МОДАЛЬНЫЕ ЛОГИКИЭпистемические логики и мультагентные системыОсновные законы (аксимы) эпистемической логики:1.

Аксиома адекватности знания:«Мои знания верны».ϕ → ϕ2. Аксиома позитивной интроспекции: ϕ → ϕ«Я вполне представляю все, что мне известно».3. Аксиома негативной интроспекции: ♦ϕ → ϕ«Я вполне сознаю, что именно мне неизвестно».Но чаще всего возникают задачи, когда коллектив субъектов(мультиагентная система) пытается совместными усилиямиили в конкурентной борьбе достичь какой-то цели. В такомслучае каждый агент должен принимать в расчет не толькознания о предметной области, но и представления о том,какими знаниями располагают другие агенты.МОДАЛЬНЫЕ ЛОГИКИЗадача.Три мудреца спорили о том, кто из них мудрее. Прохожийвзялся разрешить их спор. Он сказал: «У меня в мешке пятьшапок: 3 черных и 2 белых.

Я завяжу вам глаза, наденукаждому на голову одну из шапок, а потом развяжу глаза. Тотиз вас, кто первым догадается, какого цвета шапка у него наголове, будет признан мудрейшмим». Мудрецы согласились, ипрохожий исполнил все то, о чем он говорил. После того, как сглаз мудрецов были сняты повязки, некоторое время никто непроизнес ни слова. И после этого один из мудрецов заявил:«На моей голове черная шапка». Он оказался прав, и былпризнан мудрейшим.Вопрос: Докажите, что мудрейший из мудрых слеп.МОДАЛЬНЫЕ ЛОГИКИЭпистемические логики и мультагентные системыВ мультиагентных системах нужно ввести более специальныемодальные операторы.Пусть A = {a1 , a2 , . . . an } — множество агентов.