Лекции В.А. Захарова, страница 30

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

. . , Pn , . . . } — множество атомарныхформул (названия задач).Интуиционистская интерпретация — это реляционная системаI = hS, R, ξi, в которой1. S 6= ∅ — множество состояний (состояний знания);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@?Rs@3 y @@@@@?Rs@6 y @@?s5yИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации?s4y? P = falseутро ys1 Q = false@@@@@??s2Rs@y3 y @@@@@??s5Rs@y6 y ИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? P = falseys1 Q = false@@@@P = false@??s2 Q = falseRфирма PROGys@3 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 = falseP = true@???s4 Q = trues5Rys@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 экзаменИНТУИЦИОНИСТСКАЯ ЛОГИКАПример интуиционистской интерпретации? 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 = hS, R, ξi — интуиционистская интерпретация.

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

Допустим, что I , s0 6|= P → ¬¬P. ТогдаP = true?ys0¬¬P = false¬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 = hW , R, ξi, в которой1. W 6= ∅ — множество состояний (возможные миры);2. R ⊆ S × S — отношение достижимости на W ,3.

ξ : W × P → {true, false} — оценка атомарных формул.Система hW , Ri называется шкалой Крипке (frame).Если (w , w 0 ) ∈ R, то возможный мир w 0 называетсяальтернативным миром для s.МОДАЛЬНЫЕ ЛОГИКИОтношение выполнимости для модальных формулПусть I = hW , R, ξi — модель Крипке. Тогда отношениевыполнимости 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 6|= ϕ1 или I , w |= ϕ2 ;5. I , w |= ¬ϕ1 ⇐⇒ I , w 6|= ϕ1 ;6. I , w |= ϕ ⇐⇒для любого альтернативного мира w 0если hw , w 0 i ∈ R, то I , w 0 |= ϕ;7. I , w |= ♦ϕ ⇐⇒cуществует такой альтернативный мир w 0 ,что hw , w 0 i ∈ R и I , w 0 |= ϕ.МОДАЛЬНЫЕ ЛОГИКИПримерМодель КрипкеI , w1 |= ♦pp = truew1 yI , w1 6|= pI , w1 |= ♦pI , w5 |= pI , w5 6|= ♦pw4p = false- yw2H 6 HHHI@6@@@@@@@@@@@@@@@@?R?@yyw3-p = falsep = trueHHHw5HHj yp = falseМОДАЛЬНЫЕ ЛОГИКИПростейшие свойства1.

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