Математические основы теории систем

Задача 1. Элементы теории графов

Связный ориентированный граф G
(Х
, Г)
задан множеством вершин X
={
x
1
, x
2
,…,xn
}
и отображением Г
xi
={
x
|
I
±
k
|
,x
|
I
±
l
|
}
,i
=1
, 2
,…
,n
.
Здесь i
- текущий номер вершины, n- количество вершин графа. Значение индексов n
,
k
и l
возьмем из табл.1 в соответствии с номером варианта. Индексы k
и l
формируют значения индексов a
,b
, g
… переменной x
в отображении Г
xi
= {
x
a
,x
b
,x
g
,…}
. Если значения индексов a
, b
,g
… переменной x
не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Г
xi
.

Выполнить следующие действия:

а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;

в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;

г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi
и xj

i*j
при i
³
j
;

Kij
=

1/ (
p
+1)
при i
<
j
.

Найти передачу между вершинами x
1
и xn
, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;

Таблица 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 Г
xi
={
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
= {
x3
,
x
4
,
x
6
};

Г
x
6
= {
x4
,x
5
}.

Ориентированный граф графическим способом:

Неориентированный граф графическим способом:

Ориентированный граф матричным способом:

RG
- матрица смежности

x1	x2	x3	x4	x5	x6
x1	1*	1	1	0	0	0
x2	1	0	1	1	0	0
x3	1	1	0	1	1	0
x4	0	1	1	0	1	1
x5	0	0	1	1	0	1
x6	0	0	0	1	1	0

AG
- матрица инцидентности

v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	v12	v13	v14	v15	v16	v17	v18	v19
x1	1*	1	-1	0	0	0	0	0	0	0	0	1	-1	0	0	0	0	0	0
x2	0	-1	1	1	-1	0	0	0	0	0	0	0	0	1	-1	0	0	0	0
x3	0	0	0	-1	1	1	-1	0	0	0	0	-1	1	0	0	1	-1	0	0
x4	0	0	0	0	0	-1	1	1	-1	0	0	0	0	-1	1	0	0	1	-1
x5	0	0	0	0	0	0	0	-1	1	1	-1	0	0	0	0	-1	1	0	0
x6	0	0	0	0	0	0	0	0	0	-1	1	0	0	0	0	0	0	-1	1

Неориентированный граф матричным способом:

RD
- матрица смежности

x1	x2	x3	x4	x5	x6
x1	1*	2	2	0	0	0
x2	2	0	2	2	0	0
x3	2	2	0	2	2	0
x4	0	2	2	0	2	2
x5	0	0	2	2	0	2
x6	0	0	0	2	2	0

AD
- матрица инцидентности

v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	v12	v13	v14	v15	v16	v17	v18	v19
x1	1*	1	1	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0
x2	0	1	1	1	1	0	0	0	0	0	0	0	0	1	1	0	0	0	0
x3	0	0	0	1	1	1	1	0	0	0	0	1	1	0	0	1	1	0	0
x4	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	0	0	1	1
x5	0	0	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	0	0
x6	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	1	1

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:

- матрица отклонений имеет вид:

x1	x2	x3	x4	x5	x6
x1	1	1	1	2	2	3
x2	1	0	1	1	2	2
x3	1	1	0	1	1	2
x4	2	1	1	0	1	1
x5	2	2	1	1	0	1
x6	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

г) Считая, что передача между вершинами xi
и xj

i*j
при i
³
j
;

Kij
=

1/ (
p
+1)
при i
<
j
.

Сигнальный граф имеет вид

Система уравнений, соответствующая сигнальному графу имеет вид

x
1
=
x
1
+2
x
2
+3
x
3

x
2
=
x
1
+6
x
3
+8
x
4

x
3
=
x
1
+
x
2
+12
x
4
+15
x
5

x
4
=
x
2
+
x
3
+20
x
5
+24
x
6

x
5
=
x
3
+
x
4
+30
x
6

x
6
=
x
4
+
x
5

Определить передачу k
16
по правилу Мезона. Формула Мезона имеет вид

PS
-
передача пути,

DS
-
алгебраическое дополнение,

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
L9
L10
,L2
L
4
L6
,L2
L9
L10
,L6
L7
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. Задача о максимальном потоке и потоке минимальной стоимости

Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.

На каждом из ребер проставлены значения пропускной способности С
(n
) ребра n
.

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

Решение:

Максимальный поток j
max
транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:

Первый шаг.1. Находим какой-либо путь из х
1
в х
9
с положительной пропускной способностью.

Tаблица 1.

x1	x2 (1)	x3 (1)	x4 (1)	x5 ( 2)	x6 ( 3)	x7 ( 3)	x8 (2)	x9 (6)
x1	7	9-	4
x2	0	8	3	6
x3	0+	5	8-	4
x4	0	0	0	9	2
x5	0	2
x6	0+	5	3-
x7	0	0	0	7	6
x8	0	0	0	0	8
x9	0+	0	0

В результате получен путь l1
= (x1
, х3
, х6
, х9
).
Элементы этого пути Cij
помечаем знаком минус, а симметричные элементы Cji
- знаком плюс.

Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:

Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов табл.1 вычитаем C1
, а к элементам прибавляем C1
. В результате получим новую табл.2 с измененными пропускными способностями.

Tаблица 2

x1	x2 (1)	x3 (1)	x4 (1)	x5 ( 2)	x6 ( 3)	x7 ( 3)	x8 (2)	x9 (7)
x1	7	6-	4
x2	0	8	3	6
x3	3+	5	5	4-
x4	0	0	0	9	2
x5	0	2
x6	3	5	0
x7	0+	0	0	7	6-
x8	0	0	0	0	8
x9	3	0+	0

Второй шаг.1
. Помечаем столбцы табл.2, находим второй путь l2
= (x1
,x3
, х7
, х9
)
и расставляем знаки.

2. Пропускная способность пути l2

Изменим пропускные способности помеченных дуг на С2
в табл.3.

Tаблица 3

x1	x2 (1)	x3 (1)	x4 (1)	x5 ( 2)	x6 ( 3)	x7 ( 4)	x8 (2)	x9 (7)
x1	7	2	4-
x2	0	8	3	6
x3	7	5	5	0
x4	0+	0	0	9-	2
x5	0	2
x6	3	5	0
x7	4	0+	0	7	2-
x8	0	0	0	0	8
x9	3	4+	0

Третий шаг.1. Пометив столбцы, находим l3
= (x1
, х4
, х7
,x9
)
.

Величина потока по пути l3

Вычислив новые пропускные способности дуг, приходим к табл.4.

Таблица 4

x1	x2 (1)	x3 (1)	x4 (1)	x5 ( 2)	x6 ( 3)	x7 ( 4)	x8 (2)	x9 (8)
x1	7-	2	2
x2	0+	8	3	6-
x3	7	5	5	0
x4	2	0< /td>	0	7	2
x5	0	2
x6	3	5	0
x7	4	2	0	7	0
x8	0+	0	0	0	8-
x9	3	6	0+

Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l4
= (x1
, х2
, х8
, х9
)
и расставляем знаки.

2. Пропускная способность пути l
4

Изменим пропускные способности помеченных дуг на С4
в табл.5.

Таблица 5

x1	x2 (1)	x3 (1)	x4 (1)	x5 ( 2)	x6 ( 3)	x7 ( 4)	x8 (4)	x9 (8)
x1	1	2	2-
x2	6	8	3	0
x3	7	5	5	0
x4	2+	0	0	7	2-
x5	0	2
x6	3	5	0
x7	4	2	0	7	0
x8	6	0+	0	0	2-
x9	3	6	6+

Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l5
= (x1
, х4
, х8
, х9
)
и расставляем знаки.

2. Пропускная способность пути l5

Изменим пропускные способности помеченных дуг на С5
в табл.6.

Таблица 6

x1	x2 (1)	x3 (1)	x4 (1)	x5 ( 2)	x6 ( 3)	x7 ( 4)	x8 (5)	x9
x1	1	2	0
x2	6	8	3	0
x3	7	5	5	0
x4	4	0	0	7	0
x5	0	2
x6	3	5	0
x7	4	2	0	7	0
x8	6	2	0	0	0
x9	3	6	8

Шестой шаг. Просматривая строки и помечая столбцы, убеждаемся в том, больше не существует ни одного пути с положительной пропускной способностью из вершины x
1
в вершину x
9
. Подмножество R
образуют помеченные вершины х1
,х2
, х3
, х4
, х5
, х6
, х7
,х8
, а подмножество - одна непомеченная вершины х9
. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R
, а конечные - . Таким образом, разрез с минимальной пропускной способностью . Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза

Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7

Таблица 7.

x1	x2	x3	x4	x5	x6	x7	x8	x9
x1	6	7	4
x2	-6	0	0	6
x3	-7	0	3	4
x4	-4	0	0	2	2
x5	0	0
x6	-3	0	3
x7	4	2	0	0	6
x8	-6	-2	0	0	8
x9	-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
m1	0	1	0	1	1	1	1	2	2	0	1	3	0	1	1
m2	1	2	2	2	3	1	2	2	1	2	3	1	1	2	0
m3	2	3	1	0	1	1	1	3	2	1	0	1	2	3	3
m4	3	1	3	4	0	2	1	1	0	1	1	2	1	1	2
m5	1	2	5	1	2	2	3	0	3	3	2	0	3	2	1
№ рисунка	Рис.23				Рис.27				Рис.28				Рис.29

Решение:

Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p1
, p2
, p3
, p4
, p5
}
и переходы T = {t1
, t2
, t3
, t4
}
.

Начальная маркировка сети обозначается вектором μ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 (t1
) = {p5
},H (t1
) = {p1
,p2
},

F (t2
) = {p1
},H (t2
) = {p3
, p4
},

F (t3
) = {p3
, p4
}H (t3
) = {p1
},

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
- число позиций.

Элемент dij
-
матрицы D
-
равен кратности дуг, входящих в i
-й переход из j
-й позиции.

Элемент dij
+
матрицы 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
,…
, qn
}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X
=
{x
1
,x
2
,x
3
,x
4
}.
Переходы определяются законом отображения Г
вершин графа, причем каждому переходу соответствует только одна из букв множества X
. При задании графа эти буквы расставить произвольно.

Автомат позволяет вырабатывать выходные сигналы Y
=
{y
1
,y
2
,y
3
}:

y
1
- переход из состояния qi
в состояние qi
(петля);

y
2
- переход из состояния qi
в qj
при i
<
j
;

y
3
- переход из состояния qi
в qj
при 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 запишем закон отображения состояний автомата:

Г
q1
=
{q1
(x1
/y1
), q3
(x2
/y2
), q2
(x3
/y2
)},

Г
q2
=
{q4
(x3
/y2
), q1
(x4
/y3
), q3
(x1
/y2
)},

Г
q3
=
{q1
(x1
/y3
), q5
(x2
/y2
), q2
(x3
/y3
), q4
(x4
/y2
)},

Г
q4
=
{q2
(x1
/y3
), q6
(x2
/y2
), q3
(x3
/y3
), q5
(x4
/y2
)},

Г
q5
=
{q3
(x4
/y3
), q4
(x1
/y3
), q6
(x2
/y2
)},Г
q
6
=
{q
4
(x
3
/
y
3
),q
5
(x
4
/
y
3
)}.

Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл.2.

Таблица 2

X	Q	q1	q2	q3	q4	q5	q6
X1		q1 /y1	q3 /y2	q1 /y3	q2 /y3	q4 /y3	─
X2		q3 /y2	─	q5 /y2	q6 /y2	q6 /y2	─
X3		q2 /y2	q4 /y2	q2 /y3	q3 /y3	─	q4 /y3
X4		─	q1 /y3	q4 /y2	q5 /y2	q3 /y3	q5 /y3

Осуществим структурный синтез автомата, заданного табл.1. В качестве элементов памяти используем D-триггеры, в качестве элементной базы используем логические элементы И-НЕ.

Количество букв входного алфавита n
= 4

Количество входовp
≥ log2
n
= log2
4 = 2;

Количество букв выходного алфавита m
= 2

Количество выходовe
≥ log2
m
= log2
3 = 2;

Количество состояний r
= 6

Количество триггеровz
≥ log2
r
= log2
6 = 3.

Приступаем к кодированию:

x	u	u1	u2
x1		1	0	5
x2		1	1	4
x3		0	0	5
x4		0	1	5

v1	v2
y1	1	0	1
y2	0	1	9
y3	0	0	9

q	w	w1	w2	w3
q1		0	0	1	3
q2		0	1	0	3
q3		0	0	0	4
q4		1	0	0	4
q5		0	1	1	3
q6		1	1	0	2

На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.

Таблица 3

u1 u2	w1 w2 w3	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). Функции возбуждения трех триггеров обозначены через D1
, D2
, D3
, соответственно.

Таблица 4

u1	u2	w1 (t)	w2 (t)	w3 (t)	w1 ( t+1)	w2 ( t+1)	w3 ( t+1)	v1	v2	D1	D2	D3
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 и функций возбуждения триггеров D1
, D2
, и D3
, зависящих от набора переменных u1
, u2
, w1
(t), w2
(t), w3
(t). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

.

Минимизируем функции согласно картам Карно:

После минимизации имеем набор функций в базисе И-НЕ

=

.

.

.

Функциональная схема структурного автомата: