2. Model Checking. Вериф. парал. и распределенных программных систем. Карпов (2010) (1185529), страница 20
Текст из файла (страница 20)
Хоп Нзч~ Кри| хан 3.3. Формальная семантика СТ~ щхх оыз ст н фср а ко О знр,'ч рз игнр,чг~ р ГЕ З! АХри(Уяоз-ьзг) з~)=<р о г~=ЕХдги(Зю|.з-ьз1) гг(=р О 4=АСЗг (У(зе-езг-ьяз-ь...)г(я=ге))(УГ)з;! р ьг зЬЕСри(Л(за- з,-+з -+...):( =ае))(УГ)з,~ гр О гидр% (ч(ге-+з~-+зз-+ .,):(з=а))(ЕГ)з,! Чг а з!=Ерр (Л(юо-+зг- ~-+...):(з=зо)) (Э/)ю/3 ф О зМ Д(яырз) и (У(зе + а| -+ зз -+ - ):(з зе)) (зг'хб) (зу 1=юрз о(Уд:Онд < г)зь ~р~) Пусть М вЂ” структура Кринке (8,4г.
-+, АР,ь) (стрелкой "-+" здесь обозначено отношение перехода в М: если нз состояния з, в состояние ю, идет дуга,то (зозг)е-+, нлн, чтото:«е, (з, -+г;)К Утверждение "формула р истинна в состоянии з отрукгуры Крнпке М" записывается так: М, гьи. Если структура Кринке М, о шпорой идет речь, очевидна, М может опусИстииность формуяы р логики СТЕ в состоянии з структуры М определяется по нндукпнп по структуре формулы йи О зидиде~(з) О з~ <риз~но «леев 3 дл«ср и вюпы ' Вял бтк выпол— это и в те- яедукь .ь сбой ндпг ф иск!=Ф опус- г1 К(«р~РФ2)п(З(яа +я! ья2 +"')'(я яе)) (Зг'лб)(« ~= р Х(згй:Од«<2) «~«р,) ' Хотя эти определенна выпилят довольно сявкно, они соверщенно понятым.
Начнем с первого. Если формула есть престо атомарный предикат р, то в состоянии з структуры Кринке М эта формула истинна «выполняется«тогда и только тогда, когда «г входит в число атомарных предивное, помечмощнх состояние г . Второе правило говорит о том, что в соспинии г структуры Крипке М формула ф не истинна тогда и только тогда, когда в «зта формула не выполнается. Рассиотрим семантическое правило дяя формулы АХр.
Смысл формулы прост: она истинна в состоянии «, если во всех состояниях, непосредственно следующих за г, формула Е выполняетсж Правило формально устанавливает именно зто: оно говорит о том, что в состоянии г структуры Кринке М формула АХ«р истинна тогда и только тогда, когда для любого состояния яы в которое есть переход из «, эта формула выполивстся.
Формула ЕРр более сяолпнс из текущего соспиния существует путь, на ко. тором когда-нибудь в будущем и аыпслнится. Рассмотрим ее формаеьное определение: г«=-КР«З и (3(«е в«« -+«2-ь...):(« =за)) (З«)5«) р; Эта формула истинна в состоянии «тогда и только тогда, когда сущесг вует такое вычисление нз г (последовательное«ь соспмннй «с,гп..., в каждое из которых есть перехол нэ предыдущего состояния), начальное состояние ге которого совладает с г, гго в каком-нибудь состоянии этого вычисления (вкпючая и начальное) формула ф выполняется. Здесь (Эх:Я(х))Д(х) — это ограниченный предикат, который нужно понимать квк (Зх)(л(П)*Д(х)). Анвлогнчнмй ограниченный преднкат с квантором всеобщности (тх: л(к)) Д(х) нужно полипа«ь квк (згх)(й(х) ~Д(х)). семенина остальных формул трактуется так я«в просто. глава 3 3.4.
Проверка Формул СТ1 на развертке структуры Крилке Рассмотрим, как мошно вычислить истинность нли лшкность СП формул на структуре Кринка. На рис. 33 показана структура Крнпкс Мн сс,развсртка — начало бссконвчного дсрсвв возмакных вычислений М, начнимошихся в начальном состоянии М. 1зко Конг фс(н Рви У Е Струшура Крыма н сс раззсрпш Формула твмпоральной логики выполнвстся на М, если она вйпавняется в начальном состоямии М. Для нашего примера на рис.
ЗЗ: О Формула р хо аыполнясгся на М (т. с. Мгх р хр~, ш(скольку зта логичсская формула истинна в начальном состоянии М: в нсм истинны оба атомарных прсдиката, р и р. В Формула ЕС(гчр) выполнясшяна М (т.с. МАКС(гчр)),поскольку нз начального состояния структуры Кринка М сушсствуст путь, в кшкаом состоянии которого ияи истинно г, илм истинно р. 0 Формула ЕХ ЕС г выполнястся на М (т. с. М Р ЕХ ЕС г Е поскольку из начального сосгшшиа структуры Кринка М сущссгвуст путь, такой, что ллмзнек лмги( Сщ СЛ из следующего его соспжннв существует пуп„пв юмором все армен б„. дст выполняться г . 0 Формула АСЕР( р л у) вьнюлнаетса на М (т.
е. А(~ =АСЕР( рл-чу)), поскольку дла всех пушй из начального состояния из всех состоаний этих пугей существует путь, такой, что в будущем на мом пути не встретится нн р, ни р. Такой неформальный анализ молвю провести лишь дла небольших структур Крипке. Нашей задачей явлветса рассмотрение алгоритма пюре! сйесЫад, который макет быть использован для прогпвольной структуры Кринке и формулы СТ1. любой сложности. ул на аерг- щнх- 3.5. Базисы СТЕ Две формулы и и ж темпоральной логики назывшотса семантически эквивалентными (обоэначаеюа Еи ж ), если они принимают одинаковые испгнностиые значении на квлшой возможной ннтерпрешини (структуре Крнпкей Испол ьэул следующие очевидные шхпношеннаг Ач Е р рр т ир Сеч-~Р ф -Хпи Х-,р ша в юги- оба льку ~у нз по А(р~((рз) и луиз л- Е(-зрЗЩ ~рг л-юрз)) можно вырампь одни комбинации — "квамюр пуугь тампорвльный оператор", через другиа. Например„дла СП. справедливы следуювше аналоги законов Де Моргана: АХр и - ЖХ-р АСф и ЕР-зр Аур и ЕС-ер Минимавьиое множество операторов, с помощью которых можно вырезнп любой оператор СП., как обычно, нвзмвастса базисом.
Используя приведенные выше соопюшениа, мшкно шютроить несколько базисов СП.. Рассмотрим, как строить базисы СТЕ. На рис. 3.4 представлены асс возможные парные комбинации СПл ЕХ, АХ, ЕС, АС, ЕР, АР, ЕС и А((. Стрелками показаны все перечисленные Гласа 3 вмше воэможности выражения одних юнбииацнй СП. через другие. А именно, комбинации ЕХ и АХ, ЕС н АР, ЕР и АС можно вырезнть друг через друга.
Далее, поскольку Рн Тгиебр, можно выразить ЕР через Е6 и АР через А6 (но не наоборот). Наконел, в соответствии с формулой: А(<р~бйз)иАВрз л Е( Езб(-яр~ к рэ)) А6 можно выразить парой комбинаций АР и Е6. рог, кз зРЗ ЕЕ лц — т ((~~' йеп апч~еГ~ с,— -((В рнс.3.4. Зависимости меяшу комбннаторамн СП. 05 Для того чтобы построить базис, нужно выбршь минимальное число таких комбинаций "квантор, темпоральный оператор", из которых можно получить все остальные. Например, выберем три пары: (ЕХ, АР, Е6) (они выделены на рис.
3,4). Это множество комбинаций — базис, поскольку по стрелкам зависимостей на рис. 3.4 видно, что оставшиеся пать комбинаций можно выразить через зти трн: АХри ЕХ р ЕСэрм АР р А(~ребра) нАРрз л-Е( рз6(-яй л-ярз)) ЕРР и Е(Тгтмбр) АСярн ЕР ~р Основывакь на зависимостях рис. 3.4, мшкио построить всего шесть базисов СТЕ из трех комбинаций "квантор, темпоральный оператор"; из этого рисун. ка виано, что вместо пары АР можно выбриь пару А6 нлн ЕС, и кюкдаа нэ этих трех возможностей может быль либо с парой ЕХ, либо с парой АХ . Все базисы СТ1„которые можно построить, исходя из перечисленных выше зависимостей, таковы: (ЕХ, АР, Е6),(ЕХ, А6, Е6),(ЕХ, ЕС, Е6) (АХ, Ай', Е6), (АХ, А6,Е6), (АХ, ЕС, Е6) л вввм( ' а сп ~лм~ э Посеяны вопрос: существуют ли в логике СТ(.
другие. бюивь кроме пере. численных шестн2 Формула, в которой комбинация АУ вырывается через комбинации АР и Е(), наводит на мысль, по существует н симметричное соотношение, вырм лающее Е() через ЕР и А() . Наличие такою соотношения могло бы позволить построить и другие базисы СТ(,. Как пишет Ргапсом (лговзз(ве в (5Ц, многие думают, что зго аозмоюю. То, что зто не тмь Р)лговззш(е называет совершенно удивительным". Приведем, следуя [5Ц, доказательство этого результата, которое является весьма простым.
Зто докюательство показывает кухню" исследований в этой области. ззугие. разить через улой: ТЕОРЕМА 3.! Е() не может быть вырюкенос помощью ЕР и АУ. таких учить иены зм за- выра- зисов нсунпшая АХ. ° мше Ло лаз кгельстве Предпалозким противное, т. е. что это возмвкно. Тогда из дошнанных амин соотношений (см. рис. Зд) следует, что мнвкеспю комбинаций (ЕХ, ЕР, АЩ тоже является базисом СТ(,. Покюкем, что это ие так, т.
е. что ° зык формул СТ(. строго более выразительный, чем язык бя, в котором позволены (допустимы) талька три комбинации: ЕХ, ЕР и АП. Как следствие, мы получим доказательство утверждения теаремм. Язык формул Е„, пастроеннмй нз комбинаций (ЕХ, ЕР, АУ), опрадвал(йз(л слелующей грамматикой: апжр(-яр(рчр~ЕХр(ЕРр(А(р()р). Для доказательства теоремы 33 покажем, Что Лля произвоаьией фвРмулм у, построенной ю конструкций язмка з,я, мвкно построить такую структуру Кринке, на которой дея двух выбранных состояний этой структурм формула и будет одновременно истинной или одновременно ложной, а некоторая формула логики СТЕ (фактически, формула Е() ) для одного из этих состояний будет истинной, а для другого состояния — ложной.
Тем самым мы покажем, что язык Ех слабее язмка логики СП.; в азыке Ая нельзя выразись некоторые свойства, которые вырюнмм в логике СТ) Рвсмотрим сгру«туру Кринке на рис. 3.5. Покажем, что для любого у кй. любая формула р языяа А„глубиной (,г(=я не болыией, чем У (т.е. скаку),будетодноаременноистиннаилнлажнавсоапжниах я- и г этой глава з структуры Кринке~ т. ш аг фмг;~тг.
Докаэяшльство ушерзшения проведем по индукции. Рис. ЗЛ. Структура Кркпке к локазшальстау теоремы ЗЛ ту з = Ошн лм Е ° паф При Е. О зто соотношеняе очевидно. Формула тг глубиной Π— это атомарнме предшаты. Их истинностные значения совпадают на всех состояниях зз и.г~ при ОяЛх/. Мразь теперь л я'+!, н по индуктивной гипотезе вредположнм, чго любые формулы языка Ел, глубиной я' илн меньшей. одновременно истиним или жвкны в состояннзх з н г~ структуры Кринке парис. 3.5 при Оял'пу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
