2. Model Checking. Вериф. парал. и распределенных программных систем. Карпов (2010) (1185529), страница 62
Текст из файла (страница 62)
Еу пустое множество йГ: Унарная операция: В дополнение множества Д С Я г Бинарные оцерацин: 13 пересечение нишежтв РшЯ: ХР 0=ХР'ОХ0 цию, з Хл юич- Еу объединение ыножеств Рига: Хн„р У р оХ ' Еу разность ыивкеств Р Ъ О: 2 рту ХР л Хд Таким образом, ВСВ операции над множествами можно выразить через булевы операции над характеристическими булевыми функцнямн. Если хвракгеристические булевы функции множеств представлены в форме ВЕУЕГ, то буле. вы операции над ниии будут выпслнятьса достаточно эффективно. ВЕЗЕЗ нюл- .оди- вами г хаво,а ~и Р Представление отношений с помощью характеристических булевых функций Вр йхб Пусть о =(ас,...,а г) — множество нз л элементов. Пусть для определенности л = 4. Дяя джишного кодирования элементов из Я нуишы два двоичных разрялв, обозначим нк х1 и хз.
Выберем кодирование элеыентов Я такг ас с; 00, а, со 01, ... Оэ се !1. Любое подмножество Я можно представить булевой функцией от двух переменных. Бинарное отношение на Я вЂ” это подмножество пар элементов Я, напринер, Я ((аз,аз),(ос,а1),(апа),(аз,а~),(аз,аз),(аэ,а1)). Такое бннаРное отношение можно рассматривать как представление направленного графа, вершииаин которого валяются элементы из Я, а направленные ребра соединяют соответствуюшне вершины. Пример такого графа представлен на рис. 9.24,ш Первый элемент каждой пары отношения Я вЂ” зто вершина, нз которой идет ребро, второй элемент кюкдой пары бинарного отношения — вершине, в ко- Разря значи бина! напр» коди! а, оз Опе ю х,',' -.00 ' бт ' »а .21 0 СШЛ и опр В В эп» ции, » делен 'юрую направлено ребро.
Бинарное отшипеиие мшкно право»влить матрицсй ннциленций, такая матрица для отношения Я показана на рнс. 9.24, б. Рнг. 9,24, а) Бинарное опюшснае и; б) матрииа бинарного отношения и; в) таблица истинности функции ул, представленная магри»ей; г) результат операции Ршмап) 1шайс над йл., д) результат олерапин ВасЬ»мц !шаве наа у л Введмн йл — хара«тернстическую булеву функцию бинарного отношения Я. Эта булеаа функция для нашего примера опрацелена нв четырех дмзнчных переменных: она равна ! на кодировках пар нз л, т.е. на шести двоичных наборах й = !101 1, 000 1, 010 1, 1001, 1010, 11 0 11, сйстастствующнх шести направленным ребрам зрвфеь х» !х Эту г катр» реме» метр» зта м: Итак, раста резан форм мтрк Онер гнфи» Пуст» л=( рех б ьтнче Разряды кала первого элемшпв каждой нары бииарвого отиошвиия Я еби. значим «, иапример, (хг,хг).
Разряды кода второго злемеита каждой пары бинарного отиошеиия обозначим»' — штриховаилыми переменными из «, например, (х,',хг'). Характеристическую функцию Хя отношения Я при кодировке (», «') маццо записать в СДИФ так: Хя(».»)=(хг кгх~'хг')«( х| «г ~~'~')«( «гхг т~'хг')« (х~ мг-Ф~ хг )«(хз»«гх тг )«(х~т~ т~ хг ).
Эту булеву фуишшю можно задать, иапример, таблицей истинности в виде матрицы, в которой строки помечены юдами лсштрлхоаалвых двоичвых пвремеииых, а столбцы — кодами штриховаииых двоичных переменных. Такая матрица лдя примера отиошеиия Я представлеиа иа рис. 9.24, е. Заметим, что эта матрица совпажмт с матрицей иициделций отношения Я. Итик, бинарное апюшеиие иа конечных множествах может быть щааио жрактеристической булевой функцией, которая может быть предагашмпа в различных формах: логической формулой, таблицей истинности или жа в форме ВОО, которую удабиа представлять с одним и тем же порядком ив. штриховаииых и штриховаииых перемеииых. гсиия воич- шес- Операции над отношениями Оверапии ивавтвфвкации ве перемеиивй.
Существует две операции кваитификвции: "Э-квалификация" и "у -квмпификашш". Пусть миажество А, зле велты которого закодированы так: А =(1011, 0001, 0101, 1001, 1010,1110), предстаелеио функцией Ух от четырех булевых переменных (хихг,х~',хг'). Эга фулкция является характеристической функцией отношения Я примера 9.10. ОпеРациа кваигификациЯ фУнкции Ух по пеРемеивой хг эаписывастгл такг (З*г) У„(хп, хг,~ ) и определяет следующее мважестео кодиршилс „.. В =(111, 001, 101, 110)(х,,х,хг') . В этих кодировках разряд, по которому выполияется опервщш кввндифрягм ции, просто выброшеи.
Кааитификэция булежзй функции может быть определена через операшио дизъюикции: (Зх) у(х.у) у(О,у) «у(1,у) . 10нипифнкация по нескольким переменным аычисляеюа последовательно в любом порядке. Например, операция (Зх<,хз) <тл(х<,хз,х<',.гз') =(лт<)(Зтз)<тл(х<,хз,х<',хз') определяет следукицсе множество коднроеок: (11,01, 10)(х<,хз'). Легко видеть, что это кодировки тех вершин, в котсрьв сходит хоп бы одно ребро отношения Л примера 9.10, Выполним теперь операцию 3-каа<пифиюипш по переменным .т<', хз'. Операция (ох< ° хз ) хл(х< хз "< хз ) оп1мдсджт ш<елуюлзес миозмстао кодпроас<с (10,00,01, П)(х,,х,). Легко виден., что это кодировки тех вершин, нз которых выходит хоп бы одно ребро отношения Я примера 9.10.
Таким образом, с помощью операций кеантификации молпю по характеристической булевой функции, предстаялякнцей отношение, получить хлракпристические функции как множества всех вторых, так и мнохмстаа асах первых компонент бинарного отношения. Операция "<г -кеапифнкацни" опрелсввтся симметрично операции "3-кеантнфикацин": (тГх) У(х, у) = У(0 у) «У(1,у) . Эзн оперяцна таске палвзна Пусть с помощью бинарного отношения задан направленный граф. Если операцию "ж-кеанти(ипации" применить ко всем переменным, кодирующим первые компоненты бинарного отношениа, мы получим кодировки вершин графа, е которые направлены ребра нз асех вершин. Применив операции "<Г-квзяггификацнн" ко веем переменным, кодирующим вторые элементы бинарного отношения, получим кодировки тех вершин, из которых ребра направлены ао есе вершины.
Пример 0.11 Ляя харакпристической фунюнн Гл, предстаелжощей отношешю Л примера 9.10(см. рис. 9.24): (тЪ ) ул(х<,т,х,', ') = ну а<. (тз что мс прями Прям< стичсс множе котора усгва т. е. эт ны. иг Р вр жсстез иые и:. 1юабе иар. 3< ректор чается мн пет стичес персия ценны Обрат ческая бы одн (Образ стичео тифиш ребра < рации < этих ж Фаьти ношен< ВасЬт< рлмм в пьно в л одно Оерн- раьтек пе(ь задан г, мы ! Вер «одни тех >име- что можно интерпретнровшь так: из.всяк вершин грм(м вшь ребро в лернш ну а!.
(ттх! ~ ) тл( ! лз х! ° з ) ч,бг(ш что можно иитерпретиромпь таю в графе нет вершин, нз которых ребра на правлеиы во все вершины. Прямей образ бниариеге отиешеиии (регнмгб Пнабе). Пусть хврвктерн. стическая булеза функция хл(г,т') опредсшмт бинарное отношение м нв множестве Я. Харакшристическая функшш мшхкества тех элементов иэ 8, в которые направлено хотя бы одно ребро отношения Я, звдвеюя операцией тоги аЫ 1табе (Прямой образ) отношения Я.
Оиа определяется как операсшя квантифнкации на характеристической функции отношения й: (Згдл)(г'), т. е. это операция кввнтификации по всем переменным, кодирующим вершины, вэ кошорых выходвт ребра отношения. Для нашего примера отношения д в результате этой операции получим характеристическую функцию множества (а!,аэ,аэ) — в эти элементы множсспш Я входят ребра, направленные нз каких-то элементов этого множества. Фактически, операция Рогмшб йпвбе просто выбрасывает нз бинарного отношения все первые компоненты пар.
Заметим, что в результате операции Раптшб !пабе, примененной к характеристической фунщнн бинарного отношения с кодировкой (г,г'), получается харвктеристичежвя функция множества с кодировкой штрихованнммн переменными г' (см. Рис. 9.24, г). Если необходимо получить харжггеристнческую функцию с нешгрнхованными перемеинымн, мояэо выполнив переименование переменных: (Иг') — подсшновка нештрихованных переменных иэ г вместо штрнхованнмх переменных нз г'. Обратный образ бииариоге отношения (Васймап)1шябе). Харакгернстнческш функция миоямства тех элементов нэ Я, иэ которых направлено хотя бы одно ребро бинарного опюшеинл Я, звдаегся операцией Васйиеги'1аабе (Обрамлый образ) отношения и.
Эта операция определяется над характеристической функцией отношения д твк: (Эг'))(л(г'), т. е. зто операция квантнфикации по всем переменным, кодирующим вершины, е коморые входят ребра отношения. Дяя нашего примера отношения й в результате этой опе. Рации получим характеристнческУю фУнкцню множества (ае.аг,ат,аэ) — из этих элементов Я есть переходы в какие-нибудь элементы множества Я. Фактически, операция Вас(ггтагб )пмбе просто выбрасывает нэ бинарного отношения все вторые компоне!пм пар. Заметим, что в результате операции Вас)гпагб )ямбе, примененной к характернстичеаюй функции бинарного от- Глава В пщнения с кодированием (юг'), пояучается характернсгичеокая функшм множества с кодированием т (см, рис.
9,24, д). Если характернстичсскав булеза функция бинарного отношения представлы нв в форме ВРР, то операции каантификацин могут быть вьпзолнены до. вольно легко. Они включены во все библиощхи, работающие с бинарнымп решжощими диаграммами. Оз раннчеиня втвщиеннв вв повмшавестви Пусть Я вЂ” бинарное отношение на В, и А — подмножество Ю. Обнначнм Хя(т,т') н Хя(т) — характеристические функции отношения Я и множества А прн соответствующих зшднровках. Конъюнкция «„(т) Я Хя(жт') определяет бинарное отношение А) Я вЂ” такое ограничение отношения Я на множсозве А, что асс первые компоненты этого отношения принадлежат А.
)5оньюнкция ХА (т) м Хя(в,т) определяет бинарное отношение Я ~ А — такое ограничениее отношения Я на множества А, чго все вторые компоненпя этого опюшепия принадлехат А. Прнмвр 9.12 Пуща бинарное отношение Я~ В х В задано направленным графом рис. 9.25, а. Нв рис. 9.25, б вмделено мшхкеотво А ~ 8. Бинарное отношение А ! Я вЂ” такое ограничение отношения Я на множестве А, что первые компоненты этого отношение принадлежат А, представлено на рис.9.25,е. Бинарное отношение Я ~ А — тшюе ограничение отношенив Я на множсст- ее А, что вторые компоненты этого отношения принадлсиат А, предсгаалено нв рис. 9.25, и Пусть зашло конечное мнолмство В и Я вЂ” бинврное отношение на 5, Ящбхб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
