Ложкин С.А. Лекции по основам кибернетики
Подождите немного. Документ загружается.
§3. Эквивалентные преобразования контактных схем 81
a) t
1
:
•
∼ ∅
b) t
2
:
•
x
1
x
2
1 2
∼
•
x
2
x
1
1 2
c) t
3
:
•
x
1
x
1
1 2
∼
1 2
d) t
4
:
x
2
1 2
∼
•
x
2
o
o
o
o
o
o
o
o
x
1
O
O
O
O
O
O
O
O
•
x
2
O
O
O
O
O
O
O
O
x
1
o
o
o
o
o
o
o
o
1 2
e) t
5
:
x
1
x
1
o
o
o
o
o
o
o
1 2
3
∼
x
1
x
1
O
O
O
O
O
O
O
1 2
3
f) t
(m)
6
:
•
x
1
r
r
r
r
r
r
r
r
•
x
2
L
L
L
L
L
L
L
L
L
•
x
m
,
,
,
,
,
,
,
,
1
∼
1
Рис. 3.1: основные тождества для КС
82 Глава 3. Эквивалентные п реоб разова ния
a)
b
t
4
:
x
1
1 2
∼
•
x
1
o
o
o
o
o
o
o
o
x
1
O
O
O
O
O
O
O
O
•
x
1
O
O
O
O
O
O
O
O
x
1
o
o
o
o
o
o
o
o
1 2
b)
b
t
5
:
x
1
x
1
1 2
∼
x
1
x
1
1
2
Рис. 3.2: подстановки для основных тождеств
результатом отождествления, однозначно определяется
матрицей достижимости исходной КС. На рис. 3.2a (3.2b)
показана подстановка
b
t
4
тождества t
4
(соответственно
b
t
5
тождества t
5
), связанная с переименованием БП x
2
в x
1
(соответственно полюсов 1 = 3 в 1).
Рассмотрим примеры ЭП контактных схем с
помощью системы основных тождеств. На ри с. 3.3a–
3.3e приведены тождества t
7
–t
11
, которые мы будем
называть вспомогательными. Заметим, что выводимость
{t
5
, t
(1)
6
} ⇒ t
7
доказывается применением тождества t
(1)
6
к
правой части тождества
b
t
5
(см. рис. 3.2a) для удаления из
нее «висячего» цикла длины 1. Выводимость тождеств t
8
–
t
11
из основных тождеств {t
1
−t
5
, t
(1)
6
, t
(2)
6
} показана на рис.
3.4–3.7 соответственно, где Σ
i
и
ˇ
Σ
i
— левая и правая части
тождества t
i
, i ∈ [8, 11]. Тождество t
10
называют иногда
тождеством замыкания по транзитивности, а тождество t
11
— «леммой» о звезде.
Обобщим тождества t
1
–t
11
на случай КС от БП X (n),
где n > 2. Для каждого i, i ∈ [1, 2
n
], сопоставим ЭК
вида x
σ
1
1
···x
σ
n
n
, где ν (σ
1
, . . . , σ
n
) = i − 1, моделирующую
§3. Эквивалентные преобразования контактных схем 83
a) t
7
:
x
1
1 2
∼
x
1
x
1
1 2
b) t
8
:
•
x
1
x
2
t
t
t
t
t
t
x
2
J
J
J
J
J
J
1
3
2
∼
•
x
1
t
t
t
t
t
t
x
2
•
x
1
J
J
J
J
J
J
x
2
1
2
3
c) t
9
:
•
x
1
o
o
o
o
o
o
o
o
1
∼
1
d) t
10
:
x
1
x
1
1 2
3
∼
x
1
x
1
x
1
7
7
7
7
7
7
7
7
1 2
3
e) t
11
:
x
1
O
O
O
O
O
O
O
x
1
x
1
o
o
o
o
o
o
o
x
1
o
o
o
o
o
o
o
0
1
2
3
m
∼
x
1
4
4
4
4
4
4
x
1
x
1
4
4
4
4
4
4
x
1
x
1
4
4
4
4
4
4
0
1 2
3
m
Рис. 3.3: вспомогательные тождества для КС
84 Глава 3. Эквивалентные п реоб разова ния
Σ
8
−→
t
4
•
x
1
t
t
t
t
t
t
•
x
2
J
J
J
J
J
J
J
x
2
t
t
t
t
t
t
•
x
1
J
J
J
J
J
J
x
2
t
t
t
t
t
t
t
x
2
J
J
J
J
J
J
1
2
3
⇒
t
5
•
x
1
y
y
y
y
y
y
y
x
2
•
x
2
y
y
y
y
y
y
y
x
2
E
E
E
E
E
E
E
•
x
2
x
1
E
E
E
E
E
E
E
1
2
3
−→
t
3
ˇ
Σ
8
Рис. 3.4: вывод t
8
Σ
9
−→
t
7
•
x
1
x
1
1
−−→
t
(2)
6
ˇ
Σ
9
Рис. 3.5: вывод t
9
Σ
10
−→
t
7
x
1
x
1
x
1
1 2
3
−→
t
5
ˇ
Σ
10
Рис. 3.6: вывод t
10
§3. Эквивалентные преобразования контактных схем 85
Σ
11
−→
t
7
x
1
O
O
O
O
O
O
x
1
x
1
x
1
o
o
o
o
o
o
x
1
o
o
o
o
o
o
0
1
2
3
m
−→
t
5
x
1
O
O
O
O
O
O
x
1
x
1
o
o
o
o
o
o
x
1
o
o
o
o
o
o
x
1
o
o
o
o
o
o
0
1
2
3
m
−→
t
5
−→
t
5
x
1
O
O
O
O
O
O
x
1
o
o
o
o
o
o
x
1
o
o
o
o
o
o
x
1
o
o
o
o
o
o
x
1
O
O
O
O
O
O
0
1
2
3
m
⇒
t
5
ˇ
Σ
11
Рис. 3.7: вывод t
11
ее цепочку I
(n)
i
(см. §5 главы 2), и пусть
I
(n)
i
= I
i
, i ∈ [1, 2
n
] , I = I
2
n
;
I
(n−1)
i
= I
0
i
, i ∈
1, 2
n−1
, I
0
= I
0
2
n−1
;
I
(n−2)
i
= I
00
i
, i ∈
1, 2
n−2
, I
00
= I
00
2
n−2
.
Систему тождеств τ
(n)
=
n
t
(n)
1
, . . . , t
(n)
11
o
, где t
(n)
1
= t
1
,
t
(n)
6
— соответствующее основное тождество (см. рис. 3.1f),
t
(n)
2
— система, состоящая из тождеств, показанных на
рис. 3.8a, где
e
I — произвол ьна я перестановка цепочки
I, а остальные тождества приведены на рис. 3.8b—3.8i,
будем называть системой обобщенных тождеств порядка
n. При этом система τ
n
=
n
t
1
, . . . , t
5
, t
(1)
6
, . . . , t
(n)
6
o
считается
системой основных тождеств порядка n, а система всех
основных тождеств обозначается через τ
∞
.
Лемма 3.1. При n>2 имеет место выводимость τ
n
⇒τ
(n)
.
86 Глава 3. Эквивалентные п реоб разова ния
a) t
(n)
2
:
I
1 2
∼
e
I
1 2
b) t
(n)
3
:
•
I
1
r
r
r
r
r
r
r
r
r
I
2
I
2
n
L
L
L
L
L
L
L
L
L
1 2
2
n
∼
1 2
2
n
c) t
(n)
4
:
x
n
1 2
∼
•
x
n
I
0
1
R
R
R
R
R
R
R
R
R
R
•
x
n
l
l
l
I
0
2
[
[
[
[
[
[
[
[
[
•
x
n
8
8
8
8
8
I
0
2
n−1
m
m
m
m
m
m
m
m
m
m
1 2
d) t
(n)
5
:
I
I
{
{
{
{
{
{
1 2
3
∼
I
I
C
C
C
C
C
C
1 2
3
e) t
(n)
7
:
I
1 2
∼
I
I
1 2
f) t
(n)
8
:
•
I
0
x
n
p
p
p
p
p
x
n
N
N
N
N
N
1
3
2
∼
•
I
0
p
p
p
p
p
x
n
•
I
0
N
N
N
N
N
x
n
1
2
3
g) t
(n)
9
:
•
I
g
g
g
g
g
g
1
∼
1
h) t
(n)
10
:
I
I
1 2
3
∼
I
I
I
?
?
?
?
?
?
1 2
3
i) t
(n)
11
:
I
O
O
O
O
O
O
I
I
o
o
o
o
o
o
I
o
o
o
o
o
o
0
1
2
3
m
∼
I
4
4
4
4
4
I
I
4
4
4
4
4
I
I
4
4
4
4
4
0
1 2
3
m
Рис. 3.8: обобщенные тождества порядка n для КС
§3. Эквивалентные преобразования контактных схем 87
Σ
(n)
8
→
•
I
00
•
x
n−1
x
n
x
n
9
9
9
9
9
1
2
3
−→
t
8
•
I
00
•
x
n−1
x
n
•
x
n−1
9
9
9
9
9
x
n
1
2
3
⇒
t
2
⇒
t
2
•
I
00
•
x
n
x
n−1
•
x
n
9
9
9
9
9
x
n−1
1
2
3
⇒
t
(n−1)
8
,t
2
ˇ
Σ
(n)
8
Рис. 3.9: вывод t
(n)
8
Σ
(n)
3
⇒
t
(n)
8
•
•
I
0
1
z
z
z
z
z
z
x
n
x
n
,
,
,
,
•
I
0
2
n−1
D
D
D
D
D
D
x
n
2
2
2
2
x
n
1 2
2
n
2
n
− 1
−−−−→
t
(n−1)
3
−−−−→
t
(n−1)
3
•
x
n
x
n
2
2
2
2
•
x
n
x
n
2
2
2
2
1 2
2
n
2
n
− 1
⇒
t
3
ˇ
Σ
(n)
3
Рис. 3.10: вывод t
(n)
3
88 Глава 3. Эквивалентные п реоб разова ния
Σ
(n)
4
−−−−→
t
(n−1)
4
•
x
n
v
v
v
v
v
v
I
00
1
O
O
O
O
O
O
O
O
•
x
n
H
H
H
H
H
H
I
00
2
n−2
o
o
o
o
o
o
o
o
1 2
⇒
t
4
⇒
t
4
•
x
n
•
x
n−1
I
I
I
I
I
I
I
I
I
I
00
1
U
U
U
U
U
U
U
•
x
n
x
n−1
R
R
R
R
R
R
R
R
•
x
n
/
/
/
/
/
/
/
/
•
x
n−1
u
u
u
u
u
u
u
u
u
I
00
2
n−2
i
i
i
i
i
i
i
•
x
n
?
?
?
?
?
x
n−1
e
e
e
e
e
e
e
e
⇒
t
(n−1)
8
ˇ
Σ
(n)
4
Рис. 3.11: вывод t
(n)
4
Σ
(n)
5
→
•
I
0
x
n
•
x
n
v
v
v
v
v
v
I
0
v
v
v
v
v
v
1 2
3
−→
t
5
•
I
0
x
n
•
I
0
v
v
v
v
v
v
x
n
2
2
2
2
2
1 2
3
⇒
t
2
⇒
t
2
•
I
0
x
n
•
x
n
v
v
v
v
v
v
I
0
2
2
2
2
2
1 2
3
−−−−→
t
(n−1)
5
ˇ
Σ
(n)
5
Рис. 3.12: вывод t
(n)
5
§4. Отсутствие КПСТ в классе КС 89
Доказательство. Отметим сначала следующие очевидные
выводимости:
{t
2
} ⇒ t
(n)
2
, {t
9
} ⇒ t
(n)
9
.
Выводимость τ
n
⇒ t
(n)
i
, i = 8, 3, 4, 5, докажем индукцией
по n, n > n
i
, где n
3
= n
5
= 1 и n
8
= n
4
= 2. Базис
этой индукции составляет тождество t
i
= t
(n
i
)
i
, i = 8, 3, 4, 5,
а обоснов ани е индуктивного перехода дает выводимость
правой части
ˇ
Σ
(n)
i
тождества t
(n)
i
, n > n
i
, из его левой части
Σ
(n)
i
, показанная на рис. 3.9–3.12.
Легко видеть, что выводимости
n
t
(n)
2
, t
(n)
5
o
⇒ t
(n)
7
,
n
t
(n)
7
, t
(n)
5
o
⇒
n
t
(n)
10
, t
(n)
11
o
при n > 2 доказываются аналогично тому, как это делалось
для случая n = 1 (см. рис. 3.6, 3.7).
Лемма доказана.
§4 Полнота системы основных тождеств и
отсутствие конечной полной системы
тождеств в классе контактных схем
Докажем сначала полноту системы основных тождеств
τ
∞
для ЭП КС. Для этого, как обычно, достаточно
доказать, что с помощью ЭП на основе системы τ
∞
произвольную КС из U
K
можно привести к каноническому
виду. Напомним (см. §5, ?? главы 2), что каноническая
КС
b
Σ(x
1
, . . . , x
n
; a
1
, . . . , a
m
), или, иначе, каноническая КС
порядка n, представляет собой объединение канонических
(1, 1)-КС вида
b
Σ
ij
(x
1
, . . . , x
n
; a
i
, a
j
), постр оенн ых на основе
совершенных ДНФ ФАЛ проводимости от a
i
к a
j
для всех i
и j таких, что 1 6 i < j 6 m.
90 Глава 3. Эквивалентные п реоб разова ния
Любую цепь I
(n)
i
(см. §3), где i ∈ [1, 2
n
], а также любую
цепь, которая получается из I
(n)
i
перестановкой контактов,
будем называть канонической цепью порядка n. Заметим,
что КС
b
Σ (x
1
, . . . , x
n
; a
1
, . . . , a
m
) является канонической КС
порядка n тогда и только тогда, когда она обладает
следующими свойствами:
1. любой контакт
b
Σ принадлежит некоторой
канонической цепи порядка n, являющейся подсхемой
схемы
b
Σ, причем полюсами этой подсхемы служат
только концевые вершины данной цепи;
2. любая внутренняя вершина
b
Σ является внутренней
вершиной некоторой цепи из пункта 1;
3. в КС
b
Σ отсутствуют «висячие ци клы» (см. тождество
t
(n)
6
) и «параллельные» цепи, то есть канонические
цепи порядка n из пункта 1, которые соединяют одни
и те же полюса и реализуют равные ЭК;
4. в КС
b
Σ нет существенных транзитных проводимостей,
то есть наличие цепей вида I
(n)
i
, соединяющих полюс
a
j
с полюсом a
k
и полюс a
k
с полюсом a
t
(см. рис. 4.1a),
влечет наличие цепи такого же вида, соединяющей
полюс a
j
с полюсом a
t
(см. рис. 4.1b).
Лемма 4.1. Для любой КС Σ, где Σ ∈ U
K
и Σ =
= Σ (x
1
, . . . , x
n
; a
1
, . . . , a
m
), и любой эквивалентной Σ КС
b
Σ (x
1
, . . . , x
n
; a
1
, . . . , a
m
) канонического вида существует
ЭП Σ ⇒
τ
n
b
Σ.
Доказательство. Построим ЭП вида
Σ ⇒
τ
n
Σ
1
⇒
τ
n
Σ
2
⇒
τ
n
Σ
3
⇒
τ
n
Σ
4
=
b
Σ,