Тема 15. Описание систем с помощью сетей Петри. Применение сетей Петри при разработке графического языка программирования.

Сетью Петри (СП) называется двудольный ориентированный граф N = <Р, Т, * >, гдеР = {pi}, Т= {ti} — конечные непустые множества вершин, называемые соответственно позициями (места) и переходами; * — отношение между вершинами, соответствующее дугам графа. Позиции изображаются кружками, а переходы — черточками (полочки). Дуги соединяют кружки с черточками и черточки с кружками, но не однотипные вершины между собой. Маркировкой сети Петри называется функция Ф, которая каждой позиции ставит в соответствие целое неотрицательное число. Маркировка характеризуется вектором Ф = < Ф (p1),..., Ф(рп) >, где и — число позиций сети Петри. В графическом изображении маркировке Ф соответствует размещение меток (точки, маркеры, фишки) в позициях сети. При этом число меток в позицииpi равно Ф (pi).

Различные маркировки сети Петри характеризуют состояния соответствующей ей динамической системы, причем динамика изменений состояний моделируется движением меток по позициям. Маркировка сети может изменяться при срабатывании ее переходов. Если каждая из входных позиций перехода tj содержит по меньшей мере одну метку, то переходtj- может сработать (возбужден). При срабатывании перехода из каждой его позиции удаляется одна метка, а в каждую выходную позицию добавляется одна метка. Обычно в сетях Петри считается, что если при одной и той же маркировке возбуждено несколько переходов, то может сработать любой, но только один из них. Это ограничение не является принципиальным и может быть снято.

При применении сетей Петри для целей управления позициям сопоставляются операции (действия), а переходам — условия, при выполнении которых возбужденные переходы срабатывают, активизируя соответствующие операции [31]. При этом попадание меток в позицию ассоциируется с началом операции, а удаление метки — с ее окончанием. При использовании такого предположения считают, что любая операция не может быть повторно начата до ее завершения. Для описания таких процессов могут применяться только безопасные сети Петри, т. е. такие сети, в которых при любой маркировке в каждой позиции не может быть более одной метки. Так как при любом течении дискретного процесса должна быть возможность его возобновления, а любая из множества заданных операций должна быть выполнена, то сеть Петри в таких случаях должна быть живой, т. е. она не должна порождать такие маркировки, для которых другие маркировки недостижимы. Безопасные и живые сети Петри называются правильными. Поэтому в качестве модели дискретных процессов в [31] было предложено использовать правильные сети Петри. При этом отметим, что проверка сети Петри на правильность является весьма трудоемкой [146].

Основное достоинство сетей Петри состоит в возможности отображения в виде одной компоненты взаимодействия нескольких параллельно-последовательных процессов, а их недостаток заключается в том, что они не описывают в явном виде поведение — динамику смены состояний. Сети Петри в некотором смысле аналогичны мостиковым контактным схемам, для которых описание их структуры отличается от описания их поведения. Сложность анализа поведения сетей Петри состоит в том, что приходится одновременно следить за положением нескольких точек и запоминать эти ситуации. Поведение сети Петри в явном виде описывается с помощью графа достижимых маркировок, который в некотором смысле аналогичен эквивалентной параллельно-последовательной схеме (П-схема), построенной по заданной мостиковой схеме. Основное достоинство П-схем, определившее их широкое применение, состоит в том, что для каждой из них структура и поведение могут быть описаны одной и той же булевой формулой, что позволяет выполнить ее формальные преобразования с целью упрощения структуры без изменения поведения. На рис. 11.1 приведена правильная сеть Петри, а на рис. 11.2 — ГДМ, соответствующий этой сети.

При этом отметим, что ГДМ аналогичны предложенным для анализа асинхронных схем диаграммам переходов (диаграммы Маллера), которые, правда, дополнительно содержат информацию о том, какие компоненты векторов, записанные в каждой вершине, возбуждены в ней. Несмотря на то что число вершин в ГДМ в общем случае не меньше, чем в соответствующей сети Петри, читать ГДМ существенно проще, так как, во-первых, в нем в каждой вершине в явном виде указаны значения всех компонент вектора, определяющие состояние системы, а во-вторых, он в явном виде описывает динамику изменений состояний. Правильная сеть Петри называется автоматной (АСП), если все ее переходы имеют не более одной входящей и не более одной выходящей дуги, а в ее начальной маркировке имеется не более одной метки. На рис. 11.3 приведена автоматная сеть Петри, а на рис. 11.4 — соответствующий ГДМ.

Из рассмотрения этих графов следует, что они в некотором смысле изоморфны, и поэтому можно утверждать, что автоматные сети Петри не только задают структуру процесса, но и описывают его динамику. В этом смысле такие сети аналогичны П-схемам. Если переходы в сети Петри пометить условиями от входных переменных, то такая сеть называется сетью Петри с входами. В такой сети переход срабатывает, если он возбужден и выполняется условие, помечающее этот переход. В таких сетях при изменении значений входных переменных возникает переходный процесс, который завершается установлением равновесия, прежде чем произойдет следующее изменение на входе.

При использовании сетей Петри для целей управления в них должны быть помечены не только переходы, но и позиции. Сети Петри с помеченными переходами и позициями, помеченными значениями выходных переменных, называются сетями Петри с входами и выходами (СПВБ), или графами операций (ГО) [31]. Эти графы могут быть изоморфно реализованы с помощью диаграмм «Графсет» [59]. Для графов операций характерно, что позиции обычно помечаются не всеми значениями переменных, а лишь теми из них, которые изменяются в этой позиции. Это, с одной стороны, делает описания алгоритмов весьма компактными, а с другой — весьма сложными для понимания в случаях, когда значения выходных переменных связаны между собой семантически. При этом отметим, что для произвольного графа операций, выполняющего в позициях в том числе и вычисления, всегда может быть построена эквивалентная ингибиторная сеть Петри [146], содержащая кроме «прямых» входов в переходы также и «инверсные» входы, и наоборот. Несмотря на то что эти модели равномощны между собой и равномощны с машинами Тьюринга [146], применение графов операций для рассматриваемых целей предпочтительнее, так как позволяет строить компактные и наглядные модели процессов.

Выделим в классе графов операций такой важный подкласс, как автоматные графы операций, которые являются помеченными автоматными сетями Петри. Такие графы операций эквивалентны подклассу графов переходов, а именно ГП автоматов Мура с двоичным кодированием состояний. Однако так как ГП содержат вершины только одного типа и петли, позволяющие отличать устойчивые вершины от неустойчивых, а кроме того, обычно не содержат умолчаний значений выходных переменных, то рекомендуется в большинстве случаев вместо автоматных графов операций применять графы переходов. Возможность использования для описания алгоритмов разных типов ГП с различными видами кодирования делает их применение по сравнению с автоматными графами операций еще более предпочтительным.

Преимущество изобразительных возможностей неавтоматных графов операций по сравнению с графами переходов проявляется только при необходимости отобразить в одном графе синхронизацию параллельных процессов: если процессы запускаются переходом с одним входом и n выходами, то они должны завершаться переходом сn входами и одним выходом. Это имеет место, например, в версии языка «Графсет», используемой фирмой «Омрон» [236]. Необходимо отметить, что для каждого графа операций может быть построена система взаимосвязанных ГП, реализующая то же поведение (СВГП, так же как и графы операций, равномощны с машинами Тьюринга [163]). Более того, по графу операций всегда может быть построен один граф переходов, который (за счет увеличения числа вершин и дуг и параллелизма по входам и выходам) позволяет реализовать параллельные процессы. Число вершин в этом ГП равно числу состояний в ГО. Для этого по графу операций строится граф, в котором в вершинах указываются номера позиций, активизируемых при срабатывании переходов. Эти вершины помечаются соответствующими значениями выходных переменных, формируемых в этих позициях, и связываются дугами, определяемыми переходами графа операций. Получаемый граф является ГП автомата Мура, описывающим то же поведение динамической системы, что и граф операций. Эта процедура в терминах [31] выглядит следующим образом: по быстрой сети Петри, являющейся основой ГП, построить медленную сеть Петри и сопоставить ее маркировкам вершины графа переходов, а ее переходам — дуги этого графа. На рис. 11.5 приведен граф операций, а на рис. 11.6 — ГП автомата с памятью, построенный по этому графу операций в предположении о возможности срабатывания в нем более одного перехода. Необходимо отметить, что строить ГП по графу операций целесообразно лишь в том случае, когда значения выходных переменных семантически зависимы. При отсутствии зависимости между выходными переменными в параллельных процессах строить ГП нет необходимости. Непосредственно по графу операций (рис. 11.5), рассматривая каждую переменнуюр иz какR-триггер, можно записать систему булевых формул, реализующую этот граф:

В начальной позиции р1= 1;р2= р3= р4 =р5 =р6 =р7 = 0. Использование переобозначений переменных снимает проблему [31] пропуска позиций, для которых пометки входных и выходных переходов не ортогональны.

Тема 16. Динамические двоичные системы. Дифференцирование динамических двоичных функций. Производная первого порядка. Единичная остаточная функция, нулевая остаточная функция. Смешанная производная от булевой функции.

Рассмотрим метод, позволяющий проектировать логические схемы и соответствующие им суперпозиции большей сложности — метод каскадов.

Метод каскадов, основанный на разложении Шеннона

равно n!, но на каждом ярусе можно исключить не только одну и ту же переменную, но и различные переменные; далее, можно исключать на каждом шаге различное число переменных (одну, две, три и т. д.). Выбор оптимального исключения переменных перебором всех способов исключения — трудоемкий процесс.

Оптимальное исключение переменных ищут, используя эвристические критерии, один из которых основан на использовании понятия производной от булевой функции.

При переключении входного вектора 4↔З, 6↔1 и 7↔0 выходной канал fпереключается.