Математические основы теории систем (работа 3)
Задача 1. Элементы теории графов
Связный ориентированный граф G (Х, Г) задан множеством вершин X={x>1>, x>2>, …, x>n>} и отображением Гx>i>={x>|>>I>>>>k>>|>, x>|>>I>>>>l>>|>}, i =1, 2,…, n. Здесь i - текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов , , … переменной x в отображении Гx>i> = {x>>> >, x>>> >, x>>,…}. Если значения индексов , , … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гx>i>.
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;
г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами x>i> и x>j>
i*j
при i
j;
Kij =
1/ (p+1) при i<j .
Найти передачу между вершинами x>1>> >и x>n>, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;
Таблица 1
|
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
N |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
6 |
6 |
6 |
|
K |
2 |
3 |
4 |
1 |
1 |
1 |
3 |
5 |
2 |
4 |
2 |
3 |
4 |
5 |
6 |
|
L |
1 |
1 |
1 |
2 |
3 |
4 |
2 |
1 |
3 |
3 |
1 |
1 |
1 |
1 |
1 |
|
№ варианта |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
N |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
6 |
7 |
7 |
7 |
7 |
7 |
7 |
|
K |
1 |
1 |
1 |
1 |
3 |
2 |
5 |
5 |
2 |
3 |
4 |
5 |
6 |
5 |
3 |
|
L |
2 |
3 |
4 |
5 |
2 |
3 |
2 |
3 |
3 |
2 |
3 |
2 |
1 |
3 |
5 |
Решение:
Множество вершин
X = {x>1>, x>2>, x>3>, x>4>, x>5>, x>6> }, n = 6 k = 2, l = 1 Гx>i>={x>|>>I>>>>k>>|>, x>|>>I>>>>l>>|>}.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Гx>1 >= { x>1>, x>3>, x>2 >};
Гx>2 >= { x>4>, x>1>, x>3 >};
Гx>3> = { x>1>, x>5>, x>2>, x>4 >};
Гx>4 >= { x>2>, x>6>, x>3>, x>5 >};
Гx>5> = { x>3>, x>4>, x>6 >};
Гx>6> = {x>4>, x>5 >}.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
R>G>
- матрица смежности
|
x>1> |
x>2> |
x>3> |
x>4> |
x>5> |
x>6> |
|
|
x>1> |
1* |
1 |
1 |
0 |
0 |
0 |
|
x>2> |
1 |
0 |
1 |
1 |
0 |
0 |
|
x>3> |
1 |
1 |
0 |
1 |
1 |
0 |
|
x>4> |
0 |
1 |
1 |
0 |
1 |
1 |
|
x>5> |
0 |
0 |
1 |
1 |
0 |
1 |
|
x>6> |
0 |
0 |
0 |
1 |
1 |
0 |
A>G>
- матрица инцидентности
|
v>1> |
v>2> |
v>3> |
v>4> |
v>5> |
v>6> |
v>7> |
v>8> |
v>9> |
v>10> |
v>11> |
v>12> |
v>13> |
v>14> |
v>15> |
v>16> |
v>17> |
v>18> |
v>19> |
|
|
x>1> |
1* |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x>2> |
0 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
|
x>3> |
0 |
0 |
0 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
1 |
-1 |
0 |
0 |
|
x>4> |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
1 |
-1 |
|
x>5> |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
|
x>6> |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
Неориентированный граф матричным способом:
R>D> - матрица смежности
|
x>1> |
x>2> |
x>3> |
x>4> |
x>5> |
x>6> |
|
|
x>1> |
1* |
2 |
2 |
0 |
0 |
0 |
|
x>2> |
2 |
0 |
2 |
2 |
0 |
0 |
|
x>3> |
2 |
2 |
0 |
2 |
2 |
0 |
|
x>4> |
0 |
2 |
2 |
0 |
2 |
2 |
|
x>5> |
0 |
0 |
2 |
2 |
0 |
2 |
|
x>6> |
0 |
0 |
0 |
2 |
2 |
0 |
A>D> - матрица инцидентности
|
v>1> |
v>2> |
v>3> |
v>4> |
v>5> |
v>6> |
v>7> |
v>8> |
v>9> |
v>10> |
v>11> |
v>12> |
v>13> |
v>14> |
v>15> |
v>16> |
v>17> |
v>18> |
v>19> |
|
|
x>1> |
1* |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x>2> |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
x>3> |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
x>4> |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
x>5> |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
x>6> |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:
- матрица отклонений имеет вид:
|
x>1> |
x>2> |
x>3> |
x>4> |
x>5> |
x>6> |
|
|
x>1> |
1 |
1 |
1 |
2 |
2 |
3 |
|
x>2> |
1 |
0 |
1 |
1 |
2 |
2 |
|
x>3> |
1 |
1 |
0 |
1 |
1 |
2 |
|
x>4> |
2 |
1 |
1 |
0 |
1 |
1 |
|
x>5> |
2 |
2 |
1 |
1 |
0 |
1 |
|
x>6> |
3 |
2 |
2 |
1 |
1 |
0 |
- вектор отклонения
=>
х>2>, х>3>, х>4>, х>5> - центры графа с наименьшей удаленностью. Радиус ρ (G) = 2.
Периферийными вершинами являются вершины х>1>, х>6>> >с наибольшей удаленностью. Диаметр графа D (G) = 3.
в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.
Выделяем два подграфа: G>1> и G>2>
X>1> - {x>1>, x>2>}, Г>1х1> = {x>1>, x>2>}, Г>1х2> = {x>1>},
X>2> - {x>1>, x>2>,> >x>3>}, Г>2х1> = {x>2>}, Г>2х2> = {x>3>}, Г>2х3> = {x>2>}.
Объединение
,
,
,
,
.
G
Пересечение
,
,
,
.
G
Разность
,
,
,
.
G
г) Считая, что передача между вершинами x>i> и x>j>
i*j при
i
j;
Kij =
1/ (p+1) при i<j .
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x>1> = x>1> +2x>2 >+3x>3>
x>2>
=
x>1> +6 x>3>
+8 x>4>
x>3>
=
x>1> +
x>2>+12x>4
>+15x>5>
x>4>
=
x>2>
+
x>3 >+20 x>5>
+24x>6>
x>5>
=
x>3>
+
x>4 >+30x>6>
x>6>
=
x>4 >+x>5>
Определить передачу k>16> по правилу Мезона. Формула Мезона имеет вид
P>S> - передача пути,
D>S> - алгебраическое дополнение,
D - определитель.
Пути из х>1> в х>6> и передаточные функции для каждого из них имеют вид:
Контура:
;
;
;
;
;
;
;
;
;
;
;
;
;
.
;
.
Пары несоприкасающихся контуров
L>1>L>3>, L>1>L>4>, L>1>L>5>, L>1>L>6>, L>1>L>8>, L>1>L>9>, L>1>L>10>, L>1>L>13>, L>1>L>14>, L>1>L>15>, L>1>L>16>, L>1>L>17>, L>1>L>18>;
L>2>L>4>, L>2>L>5>, L>2>L>6>, L>2>L>8>, L>2>L>9>, L>2>L>10>, L>2>L>15>, L>2>L>16>, L>2>L>17>, L>2>L>18>;
L>3>L>5>, L>3>L>6>, L>3>L>10>, L>3>L>17>, L>3>L>18>;
L>4>L>6>, L>5>L>7>; L>5>L>11>, L>5>L>12>, L>6>L>7>, L>6>L>8>, L>6>L>11>, L>6>L>12>, L>6>L>13>, L>6>L>14>;
L>7>L>8>, L>7>L>10>, L>7>L>17>, L>7>L>18>;
L>8>L>9>, L>9>L>10>, L>10>L>11>, L>10>L>12>, L>11>L>17>, L>11>L>18>, L>12>L>17>, L>12>L>18>.
Независимые тройки
L>1>L>3>L>5>,> >L>1>L>3>L>6>,> >L>1>L>3>L>10>,> >L>1>L>3>L>17>,> >L>1>L>3>L>18>,> >L>1>L>4>L>6>,> >L>1>L>6>L>8>,> >L>1>L>6>L>13>,> >L>1>L>6>L>14>,> >L>1>L>8>L>9,>L>1>L>9>L>10>,> >L>2>L>4>L>6>,> >L>2>L>9>L>10>,> >L>6>L>7>L>8>>.>
Отсюда
D = 1 - (L>1 >+L>2 >+L>3 >+L>4 >+L>5 >+ L>6 >+L>7 >+ L>8 >+L>9 >+L>10 >+L>11 >+L>12> +
+L>13 >+L>14>+L>15 >+L>16>+L>17 >+L>18>)+ (L>1>L>3>+L>1>L>4>+L>1>L>5>+L>1>L>6>+L>1>L>8>+L>1>L>9>+L>1>L>10>+L>1>L>13>+L>1>L>14>+L>1>L>15>+L>1>L>16>+L>1>L>17>+L>1>L>18>+L>2>L>4>+L>2>L>5>+L>2>L>6>+L>2>L>8>+L>2>L>9>+L>2>L>10>+L>2>L>15>+L>2>L>16>+L>2>L>17>+L>2>L>18> +L>3>L>5>+L>3>L>6>+L>3>L>10>+L>3>L>17>+L>3>L>18> L>4>L>6>+L>5>L>7>+L>5>L>11>+L>5>L>12>+L>6>L>7>+L>6>L>8>+L>6>L>11>+L>6>L>12>+L>6>L>13>+L>6>L>14>+L>7>L>8>+L>7>L>10>+L>7>L>17>+L>7>L>18>+L>8>L>9>+L>9>L>10>+L>10>L>11>+L>10>L>12>+L>11>L>17>+L>11>L>18>+L>12>L>17>+L>12>L>18>) -
(L>1>L>3>L>5>+L>1>L>3>L>6>+L>1>L>3>L>10>+L>1>L>3>L>17>+L>1>L>3>L>18>+L>1>L>4>L>6>+L>1>L>6>L>8>+L>1>L>6>L>13>+L>1>L>6>L>14>+L>1>L>8>L>9>+L>1>L>9>L>10>+L>2>L>4>L>6>+L>2>L>9>L>10>+L>6>L>7>L>8>).
D>1> = 1- L>8>;
D>2> = 1;
D>3> = 1;
D>4> = 1 - L>9>;
D>5> = 1;
D>6> = 1.
.
Структура кинематической системы представлена на рисунке:
Задача 2. Задача о максимальном потоке и потоке минимальной стоимости
Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.
На каждом из ребер проставлены значения пропускной способности С () ребра .
Для заданной сети определить максимальный поток >max> транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.
Решение:
Максимальный поток >max> транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:
Первый шаг.1. Находим какой-либо путь из х>1> в х>9> с положительной пропускной способностью.
Tаблица 1.
|
x>1> |
x>2>> (1)> |
x>3 (1)> |
x>4 (1)> |
x>5>> (>>2>>)> |
x>6>> (>>3>>)> |
x>7 (>>3)> |
x>8 (2)> |
x>9 (6)> |
|
|
x>1> |
7 |
9- |
4 |
||||||
|
x>2> |
0 |
8 |
3 |
6 |
|||||
|
x>3> |
0+ |
5 |
8- |
4 |
|||||
|
x>4> |
0 |
0 |
0 |
9 |
2 |
||||
|
x>5> |
0 |
2 |
|||||||
|
x>6> |
0+ |
5 |
3- |
||||||
|
x>7> |
0 |
0 |
0 |
7 |
6 |
||||
|
x>8> |
0 |
0 |
0 |
0 |
8 |
||||
|
x>9> |
0+ |
0 |
0 |
В результате получен путь l>1> = (x>1>, х>3>, х>6>, х>9>). Элементы этого пути C>ij> помечаем знаком минус, а симметричные элементы C>ji> - знаком плюс.
Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:
Определяем остаточные
пропускные способности дуг найденного
пути и симметричных ему дуг. Для этого
из элементов
табл.1 вычитаем C>1>, а к элементам
прибавляем C>1>. В результате получим
новую табл.2 с измененными пропускными
способностями.
Tаблица 2
|
x>1> |
x>2>> (1)> |
x>3 (1)> |
x>4 (1)> |
x>5>> (>>2>>)> |
x>6>> (>>3>>)> |
x>7 (>>3)> |
x>8 (2)> |
x>9 (7)> |
|
|
x>1> |
7 |
6- |
4 |
||||||
|
x>2> |
0 |
8 |
3 |
6 |
|||||
|
x>3> |
3+ |
5 |
5 |
4- |
|||||
|
x>4> |
0 |
0 |
0 |
9 |
2 |
||||
|
x>5> |
0 |
2 |
|||||||
|
x>6> |
3 |
5 |
0 |
||||||
|
x>7> |
0+ |
0 |
0 |
7 |
6- |
||||
|
x>8> |
0 |
0 |
0 |
0 |
8 |
||||
|
x>9> |
3 |
0+ |
0 |
Второй шаг.1. Помечаем столбцы табл.2, находим второй путь l>2> = (x>1>,x>3>, х>7>, х>9>) и расставляем знаки.
2. Пропускная способность пути l>2>
Изменим пропускные способности помеченных дуг на С>2> в табл.3.
Tаблица 3
|
x>1> |
x>2>> (1)> |
x>3 (1)> |
x>4 (1)> |
x>5>> (>>2>>)> |
x>6>> (>>3>>)> |
x>7 (>>4)> |
x>8 (2)> |
x>9 (7)> |
|
|
x>1> |
7 |
2 |
4- |
||||||
|
x>2> |
0 |
8 |
3 |
6 |
|||||
|
x>3> |
7 |
5 |
5 |
0 |
|||||
|
x>4> |
0+ |
0 |
0 |
9- |
2 |
||||
|
x>5> |
0 |
2 |
|||||||
|
x>6> |
3 |
5 |
0 |
||||||
|
x>7> |
4 |
0+ |
0 |
7 |
2- |
||||
|
x>8> |
0 |
0 |
0 |
0 |
8 |
||||
|
x>9> |
3 |
4+ |
0 |
Третий шаг.1. Пометив столбцы, находим l>3> = (x>1>, х>4>, х>7>,x>9>).
Величина потока по пути l>3>
Вычислив новые пропускные способности дуг, приходим к табл.4.
Таблица 4
|
x>1> |
x>2>> (1)> |
x>3 (1)> |
x>4 (1)> |
x>5>> (>>2>>)> |
x>6>> (>>3>>)> |
x>7 (>>4)> |
x>8 (2)> |
x>9 (8)> |
|
|
x>1> |
7- |
2 |
2 |
||||||
|
x>2> |
0+ |
8 |
3 |
6- |
|||||
|
x>3> |
7 |
5 |
5 |
0 |
|||||
|
x>4> |
2 |
0 |
0 |
7 |
2 |
||||
|
x>5> |
0 |
2 |
|||||||
|
x>6> |
3 |
5 |
0 |
||||||
|
x>7> |
4 |
2 |
0 |
7 |
0 |
||||
|
x>8> |
0+ |
0 |
0 |
0 |
8- |
||||
|
x>9> |
3 |
6 |
0+ |
Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l>4> = (x>1>, х>2>, х>8>, х>9>) и расставляем знаки.
2. Пропускная способность пути l>4>
Изменим пропускные способности помеченных дуг на С>4> в табл.5.
Таблица 5
|
x>1> |
x>2>> (1)> |
x>3 (1)> |
x>4 (1)> |
x>5>> (>>2>>)> |
x>6>> (>>3>>)> |
x>7 (>>4)> |
x>8 (4)> |
x>9 (8)> |
|
|
x>1> |
1 |
2 |
2- |
||||||
|
x>2> |
6 |
8 |
3 |
0 |
|||||
|
x>3> |
7 |
5 |
5 |
0 |
|||||
|
x>4> |
2+ |
0 |
0 |
7 |
2- |
||||
|
x>5> |
0 |
2 |
|||||||
|
x>6> |
3 |
5 |
0 |
||||||
|
x>7> |
4 |
2 |
0 |
7 |
0 |
||||
|
x>8> |
6 |
0+ |
0 |
0 |
2- |
||||
|
x>9> |
3 |
6 |
6+ |
Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l>5> = (x>1>, х>4>, х>8>, х>9>) и расставляем знаки.
2. Пропускная способность пути l>5>
Изменим пропускные способности помеченных дуг на С>5> в табл.6.
Таблица 6
|
x>1> |
x>2>> (1)> |
x>3 (1)> |
x>4 (1)> |
x>5>> (>>2>>)> |
x>6>> (>>3>>)> |
x>7 (>>4)> |
x>8 (5)> |
x>9> |
|
|
x>1> |
1 |
2 |
0 |
||||||
|
x>2> |
6 |
8 |
3 |
0 |
|||||
|
x>3> |
7 |
5 |
5 |
0 |
|||||
|
x>4> |
4 |
0 |
0 |
7 |
0 |
||||
|
x>5> |
0 |
2 |
|||||||
|
x>6> |
3 |
5 |
0 |
||||||
|
x>7> |
4 |
2 |
0 |
7 |
0 |
||||
|
x>8> |
6 |
2 |
0 |
0 |
0 |
||||
|
x>9> |
3 |
6 |
8 |
Шестой шаг. Просматривая
строки и помечая столбцы, убеждаемся
в том, больше не существует ни одного
пути с положительной пропускной
способностью из вершины x>1>
в вершину x>9>.
Подмножество R образуют помеченные
вершины х>1>,> >х>2>,
х>3>, х>4>, х>5>,
х>6>, х>7>,> >х>8>,
а подмножество
- одна непомеченная вершины х>9>.
Разрез с минимальной пропускной
способностью образуют дуги, начальные
вершины которых принадлежат подмножеству
R, а конечные -
.
Таким образом, разрез с минимальной
пропускной способностью
.
Удалив дуги этого разреза, блокируем
все пути из источника в сток. Пропускная
способность разреза
Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7
Таблица 7.
|
x>1> |
x>2> |
x>3> |
x>4> |
x>5> |
x>6> |
x>7> |
x>8> |
x>9> |
|
|
x>1> |
6 |
7 |
4 |
||||||
|
x>2> |
-6 |
0 |
0 |
6 |
|||||
|
x>3> |
-7 |
0 |
3 |
4 |
|||||
|
x>4> |
-4 |
0 |
0 |
2 |
2 |
||||
|
x>5> |
0 |
0 |
|||||||
|
x>6> |
-3 |
0 |
3 |
||||||
|
x>7> |
4 |
2 |
0 |
0 |
6 |
||||
|
x>8> |
-6 |
-2 |
0 |
0 |
8 |
||||
|
x>9> |
-3 |
-6 |
-8 |
Величина максимального потока равна сумме элементов x>1>-й строки табл.7 или сумме элементов x>9>-го столбца.
Максимальный поток равен
.
Задача 3. Анализ сетей Петри
Сеть Петри задана графически (рис.23…30). В табл.1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.
Выполнить следующие действия:
Описать сеть аналитическим и матричным способами.
Проверить условия срабатывания каждого из переходов и найти новые маркировки, к которым приведет срабатывание соответствующих переходов, путем выполнения матричных преобразований.
Построить дерево достижимости заданной сети.
Проверить, является ли достижимой одна из маркировок, получаемых на четвертом шаге построения дерева, составив и решив матричные уравнения.
Таблица 1
|
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
2 |
2 |
0 |
1 |
3 |
0 |
1 |
1 |
|
2 |
1 |
2 |
2 |
2 |
3 |
1 |
2 |
2 |
1 |
2 |
3 |
1 |
1 |
2 |
0 |
|
3 |
2 |
3 |
1 |
0 |
1 |
1 |
1 |
3 |
2 |
1 |
0 |
1 |
2 |
3 |
3 |
|
4 |
3 |
1 |
3 |
4 |
0 |
2 |
1 |
1 |
0 |
1 |
1 |
2 |
1 |
1 |
2 |
|
5 |
1 |
2 |
5 |
1 |
2 |
2 |
3 |
0 |
3 |
3 |
2 |
0 |
3 |
2 |
1 |
|
№ рисунка |
Рис.23 |
Рис.27 |
Рис.28 |
Рис.29 |
Решение:
Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p>1>, p>2>, p>3>, p>4>, p>5>} и переходы T = {t>1>, t>2>, t>3 >, t>4 >}.
Начальная маркировка сети обозначается вектором μ>0> [μ>1>,μ>2>,μ>3>,μ>4>,μ>5>], μ>0> [1 3 0 1 2]. Отсюда получим:
При аналитическом способе задания сеть Петри задается как C = (P,T,F,H,μ>0>), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции.
Через F (t>j>) обозначается множество входных позиций, а через H (t>j>) - множество выходных позиций перехода t>j>; μ>0> - начальная маркировка сети.
F (t>1>) = {p>5>},H (t>1>) = {p>1>,> >p>2 >},
F (t>2>) = {p>1>},H (t>2>) = {p>3>, p>4>},
F (t>3>) = {p>3>, p>4>}H (t>3>) = {p>1 >},
F (t>4>) = {p>2>, p>3>, p>4>}H (t>4>) = {p>5 >}.
μ>0> [1 3 0 1 2]
Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = (P,T,D-,D+,μ0). Здесь D- и D+ - матрицы входных и выходных инциденций соответственно размером m × n, где m - число переходов и n - число позиций.
Элемент d>ij>- матрицы D- равен кратности дуг, входящих в i-й переход из j-й позиции.
Элемент d>ij>+ матрицы D+ равен кратности дуг, выходящих из i-ro перехода в j-ю позицию.
Для рассматриваемой сети Петри
Матрица D = D+ - D - называется матрицей инцидентности сети Петри,
2. При начальной маркировке μ>0> [1 3 0 1 2] сети Петри разрешенными являются переходы t>1> и t>2>.
Условия срабатывания для перехода t>3> и t>4 >не выполняется.
Переход t>1>
[μ>0>] ≥ [1000]*
D- =
[1000] ·
;
[1 3 0 1 2] ≥ [00001] –
условие выполняется, переход разрешен.
Новая маркировка при срабатывании перехода t>1 >равна:
.
Переход t>2>
[μ>0>] ≥ [0100]*
D- =
[0100]
·;[1
3 0 1 2] ≥ [10000] –
условие выполняется, переход разрешен.
Новая маркировка при срабатывании перехода t>2 >равна:
.
Переход t>3>
[μ>0>] ≥ [0010]*
D- =
[0010]
·;[1
3 0 1 2] ≥ [00110] - условие не
выполняется, переход запрещен.
Переход t>4>
[μ>0>] ≥ [0001]*
D- =
[0001]
·;[1
3 0 1 2] ≥ [01110] –
условие не выполняется, переход запрещен.
Построим дерево достижимости заданной сети.
Проверим, является ли достижимой одна из маркировок, полученных на пятом шаге построения дерева, составив и решив матричные уравнения.
Уравнение
принимает вид
Перенесем
в левую часть и выполним умножение,
тогда
.
Приравняем составляющие векторов
Система имеет решение x>1> = 1; x>2> = 2; x>3> = 0; x>4> = 2.
Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t>1> срабатывает один раз, переходы t>2> и t>4> - по два раза, переход t>3> не срабатывает.
Задача 4. Элементы математической логики и теории автоматов
Конечный автомат задан графом, определенным в задаче 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = {q>1>, q>2 >,…, q>n>}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x>1>, x>2>, x>3>, x>4>}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.
Автомат позволяет вырабатывать выходные сигналы Y={y>1>, y>2>, y>3>}:
y>1> - переход из состояния q>i> в состояние q>i> (петля);
y>2>> >- переход из состояния q>i>> >в q>j> при i<j;
y>3>> >- переход из состояния q>i> в q>j> при i>j.
Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл.1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.
Таблица 1
|
№ варианта |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
|
Тип элементов |
И НЕ |
И ИЛИ НЕ |
И НЕ |
ИЛИ НЕ |
И НЕ |
И ИЛИ НЕ |
И НЕ |
ИЛИ НЕ |
И ИЛИ НЕ |
И НЕ |
|
Тип триггера |
D |
JK |
T |
D |
RS |
RSD |
D |
JK |
T |
D |
Решение:
Множество вершин X = {x>1>, x>2>, x>3>, x>4>, x>5>, x>6>},
Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q>1>, q>2>, q>3>, q>4>, q>5>, q>6>}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x>1>, x>2>, x>3>, x>4>}.
Автомат позволяет вырабатывать выходные сигналы Y={y>1>, y>2>, y>3>}.
На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:
Гq>1 >= {q>1> (x>1>/y>1>), q>3> (x>2>/y>2>), q>2> (x>3>/y>2>)},
Гq>2 >= {q>4> (x>3>/y>2>), q>1> (x>4>/y>3>), q>3> (x>1>/y>2>)},
Гq>3 >= {q>1> (x>1>/y>3>), q>5> (x>2>/y>2>), q>2> (x>3>/y>3>), q>4> (x>4>/y>2>)},
Гq>4 >= {q>2> (x>1>/y>3>), q>6> (x>2>/y>2>), q>3> (x>3>/y>3>), q>5> (x>4>/y>2>)},
Гq>5 >= {q>3> (x>4>/y>3>), q>4> (x>1>/y>3>), q>6> (x>2>/y>2>)}, Гq>6>> >= {q>4> (x>3>/y>3>), q>5> (x>4>/y>3>)}.
Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл.2.
Таблица 2
|
X |
Q |
q>1> |
q>2> |
q>3> |
q>4> |
q>5> |
q>6> |
|
X>1> |
q>1>/y>1> |
q>3>/y>2> |
q>1>/y>3> |
q>2>/y>3> |
q>4>/y>3> |
─ |
|
|
X>2> |
q>3>/y>2> |
─ |
q>5>/y>2> |
q>6>/y>2> |
q>6>/y>2> |
─ |
|
|
X>3> |
q>2>/y>2> |
q>4>/y>2> |
q>2>/y>3> |
q>3>/y>3> |
─ |
q>4>/y>3> |
|
|
X>4> |
─ |
q>1>/y>3> |
q>4>/y>2> |
q>5>/y>2> |
q>3>/y>3> |
q>5>/y>3> |
Осуществим структурный синтез автомата, заданного табл.1. В качестве элементов памяти используем D-триггеры, в качестве элементной базы используем логические элементы И-НЕ.
Количество букв входного алфавита n = 4
Количество входовp ≥ log>2> n = log>2> 4 = 2;
Количество букв выходного алфавита m = 2
Количество выходовe ≥ log>2> m = log>2> 3 = 2;
Количество состояний r = 6
Количество триггеровz ≥ log>2> r = log>2> 6 = 3.
Приступаем к кодированию:
|
x |
u |
u>1> |
u>2> |
|
|
x>1> |
1 |
0 |
5 |
|
|
x>2> |
1 |
1 |
4 |
|
|
x>3> |
0 |
0 |
5 |
|
|
x>4> |
0 |
1 |
5 |
|
v>1> |
v>2> |
||
|
y>1> |
1 |
0 |
1 |
|
y>2> |
0 |
1 |
9 |
|
y>3> |
0 |
0 |
9 |
|
q |
w |
w>1> |
w>2> |
w>3> |
|
|
q>1> |
0 |
0 |
1 |
3 |
|
|
q>2> |
0 |
1 |
0 |
3 |
|
|
q>3> |
0 |
0 |
0 |
4 |
|
|
q>4> |
1 |
0 |
0 |
4 |
|
|
q>5> |
0 |
1 |
1 |
3 |
|
|
q>6> |
1 |
1 |
0 |
2 |
На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.
Таблица 3
|
u>1>u>2> |
w>1>w>2>w>3> |
001 |
010 |
000 |
100 |
011 |
110 |
|
10 |
001/10 |
000/01 |
001/00 |
010/00 |
100/00 |
─ |
|
|
11 |
000/01 |
─ |
011/01 |
110/01 |
110/01 |
─ |
|
|
00 |
010/01 |
100/01 |
010/00 |
000/00 |
─ |
100/00 |
|
|
01 |
─ |
001/00 |
100/01 |
011/01 |
000/00 |
011/00 |
Используя таблицу переходов D-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через D>1>, D>2>, D>3>, соответственно.
Таблица 4
|
u>1> |
u>2> |
w>1> (t) |
w>2> (t) |
w>3> (t) |
w>1> >(>t+1) |
w>2> >(>t+1) |
w>3> >(>t+1) |
v>1> |
v>2> |
D>1> |
D>2> |
D>3> |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
* |
* |
* |
* |
* |
* |
* |
* |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
* |
* |
* |
* |
* |
* |
* |
* |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
* |
* |
* |
* |
* |
* |
* |
* |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
* |
* |
* |
* |
* |
* |
* |
* |
|
1 |
1 |
1 |
1 |
0 |
* |
* |
* |
* |
* |
* |
* |
* |
|
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров D>1>, D>2>, и D>3>, зависящих от набора переменных u>1>, u>2>, w>1> (t), w>2> (t), w>3> (t). В результате получим систему логических функций для построения комбинационной части автомата:
.
.
.
.
.
Минимизируем функции согласно картам Карно:
После минимизации имеем набор функций в базисе И-НЕ
=
.
.
.
Функциональная схема структурного автомата:
