Презентация 18 (1131946), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. .ϕUψ? . . .ϕUψ? . . .Задача model checking для LTL......ϕRψ?......;Вспомним закон неподвижной точки:ϕUψ ≈ ψ ∨ ϕ & X(ϕUψ)......Задача model checking для LTL......ϕRψ?......;Вспомним законы неподвижной точки:ϕUψ ≈ ψ ∨ ϕ & X(ϕUψ)ϕRψ ≈ ψ &(ϕ ∨ X(ϕRψ))......Задача model checking для LTL...ϕRψ?......ψ, ϕ?;X(ϕRψ)?Вспомним законы неподвижной точки:ϕUψ ≈ ψ ∨ ϕ & X(ϕUψ)ϕRψ ≈ ψ &(ϕ ∨ X(ϕRψ))ϕRψ? .

. .ϕRψ? . . .ϕRψ? . . .Задача model checking для LTL............;......Вспомним законы неподвижной точки:ϕUψ ≈ ψ ∨ ϕ & X(ϕUψ)ϕRψ ≈ ψ &(ϕ ∨ X(ϕRψ))При попытке применить индуктивный способ проверкисоотношения M |= ϕ существенными становятся и некоторыеформулы, не являющиеся подформулами ϕЗадача model checking для LTL............;......Вспомним законы неподвижной точки:ϕUψ ≈ ψ ∨ ϕ & X(ϕUψ)ϕRψ ≈ ψ &(ϕ ∨ X(ϕRψ))При попытке применить индуктивный способ проверкисоотношения M |= ϕ существенными становятся и некоторыеформулы, не являющиеся подформулами ϕА насколько много новых формул возникает в таком решении?Замыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноЗамыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:Замыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:Iϕ ∈ [ϕ]FLЗамыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:IIϕ ∈ [ϕ]FLесли p ∈ [ϕ]FL , то ¬p ∈ [ϕ]FL(p ∈ P)Замыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:IIIϕ ∈ [ϕ]FLесли p ∈ [ϕ]FL , то ¬p ∈ [ϕ]FL(p ∈ P)если ψ & χ ∈ [ϕ]FL или ψ ∨ χ ∈ [ϕ]FL , то {ψ, χ} ⊆ [ϕ]FLЗамыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:IIIIϕ ∈ [ϕ]FLесли p ∈ [ϕ]FL , то ¬p ∈ [ϕ]FL(p ∈ P)если ψ & χ ∈ [ϕ]FL или ψ ∨ χ ∈ [ϕ]FL , то {ψ, χ} ⊆ [ϕ]FLесли ¬ψ ∈ [ϕ]FL или Xψ ∈ [ϕ]FL , то ψ ∈ [ϕ]FLЗамыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:IIIIIϕ ∈ [ϕ]FLесли p ∈ [ϕ]FL , то ¬p ∈ [ϕ]FL(p ∈ P)если ψ & χ ∈ [ϕ]FL или ψ ∨ χ ∈ [ϕ]FL , то {ψ, χ} ⊆ [ϕ]FLесли ¬ψ ∈ [ϕ]FL или Xψ ∈ [ϕ]FL , то ψ ∈ [ϕ]FLесли ψUχ ∈ [ϕ]FL , то {ψ, χ, X(ψUχ)} ⊆ [ϕ]FLЗамыкание Фишера-ЛаднераПусть ϕ — позитивная формаЗамыкание Фишера-Ладнера [ϕ]FL формулы ϕ — этоI (неформально) все формулы, которые только могутвозникнуть при попытке решить задачу индуктивноI (формально) наименьшее множество формул, такое что:IIIIIIϕ ∈ [ϕ]FLесли p ∈ [ϕ]FL , то ¬p ∈ [ϕ]FL(p ∈ P)если ψ & χ ∈ [ϕ]FL или ψ ∨ χ ∈ [ϕ]FL , то {ψ, χ} ⊆ [ϕ]FLесли ¬ψ ∈ [ϕ]FL или Xψ ∈ [ϕ]FL , то ψ ∈ [ϕ]FLесли ψUχ ∈ [ϕ]FL , то {ψ, χ, X(ψUχ)} ⊆ [ϕ]FLесли ψRχ ∈ [ϕ]FL , то {ψ, χ, X(ψRχ)} ⊆ [ϕ]FLЗамыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))[ϕ]FL =Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ[ϕ]FL =Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ[ϕ]FL =Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ,¬free, X¬busy , X(true U(pr1 ∨ pr2 ))[ϕ]FL =Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ,¬free, X¬busy , X(true U(pr1 ∨ pr2 )),[ϕ]FL =free, ¬busy , true U(pr1 ∨ pr2 )Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ,¬free, X¬busy , X(true U(pr1 ∨ pr2 )),[ϕ]FL =free, ¬busy , true U(pr1 ∨ pr2 ),busy , true, pr1 ∨ pr2Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ,¬free, X¬busy , X(true U(pr1 ∨ pr2 )),[ϕ]FL =free, ¬busy , true U(pr1 ∨ pr2 ),busy , true, pr1 ∨ pr2 ,pr1 , pr2 , ¬pr1 , ¬pr2Замыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ,¬free, X¬busy , X(true U(pr1 ∨ pr2 )),[ϕ]FL =free, ¬busy , true U(pr1 ∨ pr2 ),busy , true, pr1 ∨ pr2 ,pr1 , pr2 , ¬pr1 , ¬pr2УтверждениеЕсли позитивная форма ψ содержит n операций, то|[ϕ]FL | ≤ 3nЗамыкание Фишера-ЛаднераПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))ϕ,false, ¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )), Xϕ,¬free, X¬busy , X(true U(pr1 ∨ pr2 )),[ϕ]FL =free, ¬busy , true U(pr1 ∨ pr2 ),busy , true, pr1 ∨ pr2 ,pr1 , pr2 , ¬pr1 , ¬pr2УтверждениеЕсли позитивная форма ψ содержит n операций, то|[ϕ]FL | ≤ 3nДоказательство.ОчевидноЗамыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχЗамыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииЗамыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:Замыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PЗамыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PI [ϕ]X — формулы множества [ϕ]FL вида XψЗамыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PI [ϕ]X — формулы множества [ϕ]FL вида XψI [ϕ]UR — формулы множества [ϕ]FL вида ψUχ и ψRχЗамыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PI [ϕ]X — формулы множества [ϕ]FL вида XψI [ϕ]UR — формулы множества [ϕ]FL вида ψUχ и ψRχПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))Замыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PI [ϕ]X — формулы множества [ϕ]FL вида XψI [ϕ]UR — формулы множества [ϕ]FL вида ψUχ и ψRχПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))[ϕ]P = {free, busy , pr1 , pr2 }Замыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PI [ϕ]X — формулы множества [ϕ]FL вида XψI [ϕ]UR — формулы множества [ϕ]FL вида ψUχ и ψRχПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))[ϕ]P = {free, busy , pr1 , pr2 }[ϕ]X = {Xϕ, X¬busy , X(true U(pr1 ∨ pr2 ))}Замыкание Фишера-ЛаднераОсобую роль при проверке соотношения M |= ϕ будут игратьформулы вида Xψ, ψUχ, ψRχБаза индуктивного решения — это выяснение того, какиеатомарные события выполняются в заданном состоянииДля удобства рассуждений будем использовать такиеобозначения:I [ϕ]P = [ϕ]FL ∩ PI [ϕ]X — формулы множества [ϕ]FL вида XψI [ϕ]UR — формулы множества [ϕ]FL вида ψUχ и ψRχПримерϕ: false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))[ϕ]P = {free, busy , pr1 , pr2 }[ϕ]X = {Xϕ, X¬busy , X(true U(pr1 ∨ pr2 ))}[ϕ]UR = {ϕ, true U(pr1 ∨ pr2 )}Замыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSЗамыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLЗамыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеЗамыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЗамыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:Замыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:I false ∈/HЗамыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:I false ∈/HI формулы p и ¬p не входят в H одновременно(p ∈ P)Замыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:I false ∈/HI формулы p и ¬p не входят в H одновременно(p ∈ P)I ψ ∨ χ ∈ H ⇔ {ψ, χ} ∩ H 6= ∅(ψ ∨ χ ∈ [ϕ]FL )Замыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:I false ∈/HI формулы p и ¬p не входят в H одновременно(p ∈ P)I ψ ∨ χ ∈ H ⇔ {ψ, χ} ∩ H 6= ∅(ψ ∨ χ ∈ [ϕ]FL )I ψ & χ ∈ H ⇔ {ψ, χ} ⊆ H(ψ & χ ∈ [ϕ]FL )Замыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:I false ∈/HI формулы p и ¬p не входят в H одновременно(p ∈ P)I ψ ∨ χ ∈ H ⇔ {ψ, χ} ∩ H 6= ∅(ψ ∨ χ ∈ [ϕ]FL )I ψ & χ ∈ H ⇔ {ψ, χ} ⊆ H(ψ & χ ∈ [ϕ]FL )I ψUχ ∈ H ⇔ χ ∈ H или {ψ, X(ψUχ)} ⊆ H(ψUχ ∈ [ϕ]FL )Замыкание Фишера-ЛаднераПо аналогии с методом семантических таблиц будем выдвигатьпредположения о выполнимости формул в состояниях LTSПредположение (в контексте LTL-формулы ϕ) — это любоеподмножество множества [ϕ]FLФормула предполагается верной ⇔ она входит в предположениеТак как требуется найти нужную трассу LTS, будем пытатьсяизбегать противоречий, выдвигая предположенияЯвных противоречий можно избежать, используя толькосогласованные предположения H:I false ∈/HI формулы p и ¬p не входят в H одновременно(p ∈ P)I ψ ∨ χ ∈ H ⇔ {ψ, χ} ∩ H 6= ∅(ψ ∨ χ ∈ [ϕ]FL )I ψ & χ ∈ H ⇔ {ψ, χ} ⊆ H(ψ & χ ∈ [ϕ]FL )I ψUχ ∈ H ⇔ χ ∈ H или {ψ, X(ψUχ)} ⊆ H(ψUχ ∈ [ϕ]FL )I ψRχ ∈ H ⇔ χ ∈ H и либо ψ ∈ H, либо X(ψRχ) ∈ H(ψRχ ∈ [ϕ]FL )Замыкание Фишера-ЛаднераПримерϕ : false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))[ϕ]FLfree, busy , pr1 , pr2 , ¬free, ¬busy , ¬pr1 , ¬pr2 ,pr1 ∨ pr2 ,true U(pr1 ∨ pr2 ),=X¬busy , X(true U(pr1 ∨ pr2 )),¬free∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )),ϕ, XϕЗамыкание Фишера-ЛаднераПримерϕ : false R(¬free ∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )))[ϕ]FLfree, busy , pr1 , pr2 , ¬free, ¬busy , ¬pr1 , ¬pr2 ,pr1 ∨ pr2 ,true U(pr1 ∨ pr2 ),=X¬busy , X(true U(pr1 ∨ pr2 )),¬free∨ X¬busy ∨ X(true U(pr1 ∨ pr2 )),ϕ, XϕТакое множество H является согласованным предположением:H=true, pr1 , ¬pr2 , ¬free, busy , X¬busy ,true U(pr1 ∨ pr2 ), X(true U(pr1 ∨ pr2 )), ϕ}Замыкание Фишера-ЛаднераПозволяет ли согласованность предположения избежать всехпротиворечий?Замыкание Фишера-ЛаднераПозволяет ли согласованность предположения избежать всехпротиворечий?Нет!Замыкание Фишера-ЛаднераПозволяет ли согласованность предположения избежать всехпротиворечий?Нет!Например, такие две формулы:Xp: “я завтра брошу пить”,X¬p: “завтра всё как обычно” —образуют неявное противоречиеЗамыкание Фишера-ЛаднераПозволяет ли согласованность предположения избежать всехпротиворечий?Нет!Например, такие две формулы:Xp: “я завтра брошу пить”,X¬p: “завтра всё как обычно” —образуют неявное противоречие:I мой образ жизни сегодня никак ими не затрагиваетсяЗамыкание Фишера-ЛаднераПозволяет ли согласованность предположения избежать всехпротиворечий?Нет!Например, такие две формулы:Xp: “я завтра брошу пить”,X¬p: “завтра всё как обычно” —образуют неявное противоречие:I мой образ жизни сегодня никак ими не затрагиваетсяI завтра я никак не смогу сдержать оба обещанияЗамыкание Фишера-ЛаднераПозволяет ли согласованность предположения избежать всехпротиворечий?Нет!Например, такие две формулы:Xp: “я завтра брошу пить”,X¬p: “завтра всё как обычно” —образуют неявное противоречие:I мой образ жизни сегодня никак ими не затрагиваетсяI завтра я никак не смогу сдержать оба обещанияI формулы Xp, X¬p могут одновременно входить всогласованное предположениеЗамыкание Фишера-ЛаднераА обязано ли непротиворечивое предположение бытьсогласованным?Замыкание Фишера-ЛаднераА обязано ли непротиворечивое предположение бытьсогласованным?УтверждениеПусть I — темпоральная интерпретацияи ϕ — позитивная формаТогда для любого момента времени n множество{ψ | ψ ∈ [ϕ]FL и I, n |= ψ}является согласованным предположениемЗамыкание Фишера-ЛаднераА обязано ли непротиворечивое предположение бытьсогласованным?УтверждениеПусть I — темпоральная интерпретацияи ϕ — позитивная формаТогда для любого момента времени n множество{ψ | ψ ∈ [ϕ]FL и I, n |= ψ}является согласованным предположениемДоказательство.

Характеристики

Список файлов лекций