Редактирование: ВПнМ, примеры задач/Задача 5
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 2: | Строка 2: | ||
== Как решать эти задачи? == | == Как решать эти задачи? == | ||
Для решения этих задач '''обязательно''' знать '''[[ВПнМ/Теормин#.D0.9B.D0.BE.D0.B3.D0.B8.D0.BA.D0.B0_LTL._.D0.A1.D0.B8.D0.BD.D1.82.D0.B0.D0.BA.D1.81.D0.B8.D1.81_LTL._.D0.A1.D0.B5.D0.BC.D0.B0.D0.BD.D1.82.D0.B8.D0.BA.D0.B0_.D0.B2.D1.8B.D0.BF.D0.BE.D0.BB.D0.BD.D0.B8.D0.BC.D0.BE.D1.81.D1.82.D0.B8_.D1.84.D0.BE.D1.80.D0.BC.D1.83.D0.BB._.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.B8_.D1.81.D0.BB.D0.B0.D0.B1.D1.8B.D0.B9_until.|определения]]''', а так же следующие '''[http://patterns.projects.cis.ksu.edu/documentation/patterns/ltl.shtml шаблоны].''' | Для решения этих задач '''обязательно''' знать '''[[ВПнМ/Теормин#.D0.9B.D0.BE.D0.B3.D0.B8.D0.BA.D0.B0_LTL._.D0.A1.D0.B8.D0.BD.D1.82.D0.B0.D0.BA.D1.81.D0.B8.D1.81_LTL._.D0.A1.D0.B5.D0.BC.D0.B0.D0.BD.D1.82.D0.B8.D0.BA.D0.B0_.D0.B2.D1.8B.D0.BF.D0.BE.D0.BB.D0.BD.D0.B8.D0.BC.D0.BE.D1.81.D1.82.D0.B8_.D1.84.D0.BE.D1.80.D0.BC.D1.83.D0.BB._.D0.A1.D0.B8.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.B8_.D1.81.D0.BB.D0.B0.D0.B1.D1.8B.D0.B9_until.|определения]]''', а так же следующие '''[http://patterns.projects.cis.ksu.edu/documentation/patterns/ltl.shtml шаблоны].''' | ||
- | |||
- | Полезна также ссылка из шаблонов на то, что означают различные области[http://patterns.projects.cis.ksu.edu/documentation/patterns/scopes.shtml]. | ||
- | Обратите внимание на "между Q и R", т.е. "Between Q and R" и на "после Q до R", т.е. "After Q, until R" | ||
Задачи, по сути делятся на инвариантные к прореживанию и не обязательно инвариантные. | Задачи, по сути делятся на инвариантные к прореживанию и не обязательно инвариантные. | ||
Строка 14: | Строка 11: | ||
p W q = <>(!p) -> (p U q) | p W q = <>(!p) -> (p U q) | ||
p W q = p U (q | []p) | p W q = p U (q | []p) | ||
+ | |||
== Задачи (не инв-ные) == | == Задачи (не инв-ные) == | ||
Строка 78: | Строка 76: | ||
!a U (b && !b) // сильный или слабый Until зависит от прочтения задачи. Возможны оба варианта | !a U (b && !b) // сильный или слабый Until зависит от прочтения задачи. Возможны оба варианта | ||
- | |||
- | UPD: (b && !b) всегда false. Если наступление события означает, что условие стало верным, то ответ | ||
- | |||
- | !a W b | ||
- | |||
- | Если наступление события означает, что условие побыло истинным, а потом стало ложным, то ответ | ||
- | |||
- | !a W (b && X!b) | ||
== Задачи (инв-ные) == | == Задачи (инв-ные) == | ||
Строка 159: | Строка 149: | ||
#define d d?ack | #define d d?ack | ||
- | [](a -> ( (! | + | [](a -> ( (!d U c) U b)) |
- | []( (a & !b & <>b) -> ((! | + | []( (a & !b & <>b) -> ((!d U c) U b) ) // Добавили то, что a и b не происходят одновременно и то, что b когда-либо произойдет. |
- | []( (a & !b & <>b) -> (! | + | []( (a & !b & <>b) -> (!d U (c | b)) ) // можно и так |
=== Задача 6 === | === Задача 6 === | ||
Строка 191: | Строка 181: | ||
(!a U b) -> (!a U c) // Потомкам: доказать что эта формула верна или нет:) | (!a U b) -> (!a U c) // Потомкам: доказать что эта формула верна или нет:) | ||
- | |||
- | Teravisor: Потомки доказывают: третья не верная. Мы смотрим обе импликации(->) из начальной точки, т.е. нам подойдет | ||
- | |||
- | !a !a !a !a !a !a a | ||
- | |||
- | !b !b !b !b !b b b | ||
- | |||
- | !c c c c c c c | ||
- | |||
- | !a U c выполняется. => формула true, хотя условию не удовлетворяет. Если поставить [] перед всей формулой правильность не изменится. Кто хочет может сам доказать. | ||
=== Задача 8 === | === Задача 8 === | ||
Строка 225: | Строка 205: | ||
Потомкам: понять разницу:) | Потомкам: понять разницу:) | ||
- | |||
- | Teravisor: потомки говорят, между 2 и 3 формулами разницы нету. Объяснение: U требует выполнимости где-то второго аргумента, в данном случае "a", в случае если его нет, формула не выполняется. требование <>a-> может быть расценено лектором как избыточное, и вообщем то не хорошо. Вообще говоря вроде первая формула правильная, в отличие от последних двух, но и правильность последних можно доказать из утверждения "я так понял задание". | ||
=== Задача 10 === | === Задача 10 === | ||
Строка 239: | Строка 217: | ||
[]( (a & !b & <>b) -> ((c -> (!b U d)) U b) ) // Здесь U b можно заменить на W b (зависит от прочтения задачи) | []( (a & !b & <>b) -> ((c -> (!b U d)) U b) ) // Здесь U b можно заменить на W b (зависит от прочтения задачи) | ||
- | |||
- | Teravisor: то, же что и в задании 1. Комментарий это не можно, а нужно. И заменой U b на W b не всё исправится - надо еще <>b убрать вначале. | ||
=== Задача 11 === | === Задача 11 === | ||
Строка 383: | Строка 359: | ||
По-моему, как-то уж очень избыточно | По-моему, как-то уж очень избыточно | ||
[]((P & !S & <>S) -> (!P U S)) | []((P & !S & <>S) -> (!P U S)) | ||
- | |||
- | []((P & !S & <>S) -> (P U (!P U S))) ( поправил al-indigo: P->!P - всегда false) | ||
Авварон: | Авварон: | ||
Строка 475: | Строка 449: | ||
al-indigo: | al-indigo: | ||
[]((p_iter_begin & !p_iter_end & <>p_iter_end) -> (req -> (![]req U p_iter_end))) | []((p_iter_begin & !p_iter_end & <>p_iter_end) -> (req -> (![]req U p_iter_end))) | ||
- | |||
- | []((p_iter_begin & !p_iter_end & <>p_iter_end) -> (req -> (req U (!req U p_iter_end)))) (поправил al-indigo) | ||
Авварон: | Авварон: |