Ложкин С.А. Лекции по основам кибернетики
Подождите немного. Документ загружается.
§5. Контактные схемы и π-схемы, оценка их чи сла 61
Лемма доказана.
Рассмотрим, в заключение, особенности
функционирования КС с несколькими входами.
Будем считать, что в каждой вершине (p, q)-КС Σ
реализуется столбец, составленный из p ФАЛ проводимости
от входов Σ к этой вершине, а сама КС Σ реализует
матрицу, которая состоит из q столбцов, реализованных на
ее выходах. Таким образом, функционировани е КС Σ =
= Σ
x
1
, . . . , x
n
; a
0
1
, . . . , a
0
p
; a
00
1
, . . . , a
00
q
представляет собой
матрицу F = F (x
1
, . . . , x
n
) с p строками, q столбцами
и элементами из P
2
(n), для которой F hi, ji — ФАЛ,
реализуемая между a
0
i
и a
00
j
, где i ∈ [1, p] и j ∈ [1, q],
то есть при любом α, α ∈ B
n
, матрица F (α) является
матрицей достижимости сети Σ|
α
(см. §?). В частности,
функционирование (1, q)-КС, как уже отмечалось выше,
представляет собой набор (строку) из q ФАЛ проводимости
от ее входа к выходам, а функционирование (p, 1)-КС —
столбец из p ФАЛ проводимости от ее входов к в ыходу.
Так, КС Σ (x
1
, x
2
, x
3
; a
1
, v; a
2
, a
3
), показанная на рисунке
5.3c реализует матрицу
h
l
3
l
3
l
3
l
3
i
от БП X(3), а на рис. 5.4b
приведено (2
n
, 1)-КД порядка n от БП X (n), которое имеет
вид D (x
1
, . . . , x
n
; a
0
, . . . , a
2
n
−1
; a) и реализует столбец из
всех ЭК множества Q
n
, упорядоченных сверху вниз по
возрастанию их номеров.
В соответствии с общими правилами из §1,
функционирование КС Σ = Σ (x
1
, . . . , x
n
; a
1
, . . . , a
m
)
с неразделенными п олюсами определяется как
функционирование КС с разделенными полюсами вида
Σ (x
1
, . . . , x
n
; a
1
, . . . , a
m
; a
1
, . . . , a
m
). В этом случае матрица
F является рефлексивной и транзитивной матрицей
(см. §?), а если, кроме того, Σ — неориентированная
сеть, то и — симметричной матрицей. Заметим также,
что функционирование (1, 1)-КС из неориентированных
62 Глава 2. Основные классы управл яющих систем
контактов по существу не отличается от функционирования
соответствующей двухполюсной КС с неразделенными
полюсами.
В частности, показанная на рис. 5.3c КС с
неразделенными полюсами a
1
, a
2
, a
3
реализует матрицу
1 l
3
l
3
l
3
1 0
l
3
0 1
, КС из тождественных вершин реализует
единичную матрицу, если каждая ее вершина является
входом и выходом с одним и тем же номером и т. д.
С другой стороны, любая симметрическая, транзитивная
и рефлексивная матрица F , F ∈ (P
2
(n))
m,m
, реализуется
КС Σ = Σ (x
1
, . . . , x
n
; a
1
, . . . , a
m
), которая представляет
собой объединение всех КС Σ
ij
= Σ
ij
(x
1
, . . . , x
n
; a
i
, a
j
),
где 1 6 i < j 6 m, а КС Σ
ij
построена по совершенной
ДНФ ФАЛ F hi, ji (см. выше) и считается канонической КС
матрицы F .
Глава 3
Эквивалентные преобразования
управляющих систем
§1 Эквивалентные преоб разования схем на
основе тождеств. Моделирование
эквивалентных преобразований формул
в классе схем из функциональных элементов
Эквивалентные преобразования (ЭП), то есть
преобразования, не изменяющие функционирования схем,
играют важную роль при решении различных задач теории
управляющих систем и, в частности, задачи синтеза схем
(см. §1 главы 4). Следуя [30], изложи м в данной главе ряд
вопросов ЭП схем из основных классов. Рассмотрим сначала
понятия, связанные с эквивалентными преобразованиями
формул над базисом Б на основе тождеств. Напомним, что
некоторые ЭП формул базиса Б
0
уже использовались для
раскрытия скобок и приведения подобных при построении
сокращенной ДНФ (см. ?? главы 1), для оптимизации
подобных формул по глубине и поднятия отрицаний (см. §2
главы 2).
Для того чтобы выделить набор x = (x
i
1
, . . . , x
i
n
),
который состоит из всех различных БП алфавита X,
встречающихся в формуле F и перечисленных в порядке
возрастания их номеров, будем записывать ее в виде F =
F (x). При этом формулу, которая получается из F в
63
64 Глава 3. Эквивалентные п реоб разова ния
результате замены каждого вхожд ени я БП x
i
j
, j = 1, . . . , n,
формулой F
j
будем считать резул ьтатом подстановки
формулы F
j
вместо БП x
i
j
, j = 1, . . . , n, в формулу
F и будем обозначать ее через F (F
1
, . . . , F
n
). Заметим,
что формула F (F
1
, . . . , F
n
) реализует ФАЛ f (f
1
, . . . , f
n
),
где ФАЛ f (ФАЛ f
j
) — ФАЛ, реал изуемая формулой F
(соответственно F
j
, j = 1, . . . , n). Отсюда следует, что
если указанную подстановку применить к обеим частям
тождества t : F
0
= F
00
, где F
0
= F
0
(x) и F
00
= F
00
(x), мы
получим тождество
b
t :
b
F
0
=
b
F
00
,
где
b
F
0
= F
0
(F
1
, . . . , F
n
) и
b
F
00
= F
00
(F
1
, . . . , F
n
), которое
называется подстановкой для тождества t.
Напомним, что формулы, полученные в процессе
индуктивного построения (см. ?? главы 1) формулы
F, называются ее подформулами. Из определений
следует, что для формул имеет место так называемый
принцип эквивалентной замены. Это означает, что если
подформулу
b
F
0
(подформулу
b
F
00
) формулы F заменить,
учитывая тождество
b
t, эквивалентной ей формулой
b
F
00
(соответственно
b
F
0
), то полученная в результате такой
замены формула
ˇ
F будет эквивалентна формуле F, то есть
будет справедливо тождество
ˇ
t : F =
ˇ
F.
Указанный переход от F к
ˇ
F (от t к
ˇ
t) будем
записывать в виде однократной выводимости вида F 7→
t
ˇ
F (соответственно t 7→
ˇ
t). Аналогичный переход от F к
e
F в результате применения одного из тождеств системы
τ (нескольких последовательных применений тождеств из
τ) будем записывать в виде однократной (соответственно
кратной) выводимости вида F 7→
τ
e
F (соответственно F ⇒|
τ
e
F).
§1. Преобразования на основе тождеств 65
При этом считается, что тождество
e
t : F =
e
F
выводится из системы тождеств τ , и этот факт
записывается в виде выводимости τ 7→
e
t или τ ⇒
|
e
t в зависимости от числа использованных переходов.
Переход вида F ⇒|
τ
e
F будем называть также эквивалентным
преобразованием формулы F в формулу
e
F на основе
системы тождеств τ. Заметим, что в силу обратимости
ЭП, из выводимости F ⇒|
τ
e
F следует обратная выводимость
e
F ⇒|
τ
F. Система тождеств τ на зывается полной для ЭП
формул над Б, если для любых двух эквивалентных формул
F
0
и F
00
над Б имеет место выводимость F
0
⇒|
τ
F
00
.
Рассмотрим, в частности, систему, которая состоит из
тождества
t
M
&
:
x
1
· x
2
= x
1
∨ x
2
,
— тождества де Моргана для конъюнкции (см.
тождества (2.6) из главы 2) и тождества
t
ПK
1,&
: x
1
(x
2
∨ x
2
) = x
1
,
— тождества подстановки константы 1 = x
2
∨ x
2
в
конъюнкцию (см. тождества (??) из главы 1). Пример ЭП
формул из U
Φ
с помощью этой системы тождеств дает
следующая цепочка выводимостей:
x
1
(x
2
x
3
∨ x
2
∨ x
3
) 7→
t
M
&
x
1
(x
2
x
3
∨ x
2
· x
3
) 7→
t
ΠK
1,&
x
1
. (1.1)
Распространим теперь введенные выше пон ятия и
обозначения на произвольный класс схем U из главы 2.
66 Глава 3. Эквивалентные п реоб разова ния
В соответствии с определениями из §1 этой главы
эквивалентность схем Σ
0
и Σ
00
из U имеет место тогда и
только тогда, когда Σ
0
и Σ
00
реализуют равные системы
(матрицы) ФАЛ. При этом, обычно, предполагается, что
соответствующие друг другу полюса (выходы, входы) в Σ
0
и Σ
00
имеют одинаковые пометки, а эквивалентность Σ
0
и Σ
00
записывается в виде тождества
t : Σ
0
∼ Σ
00
.
Для схем из U, как и д ля формул, определяется
ряд «простейших» преобразований, сохраняющих
эквивалентность схем, которые называются подстановками.
Тождество
b
t :
b
Σ
0
∼
b
Σ
00
,
которое получается в результате применения одной и той
же подстанов ки к обеим частям тождества t : Σ
0
∼
Σ
00
, называется подстановкой тождества t. Схема Σ
0
называется подсхемой схемы Σ, если
V
Σ
0
⊆ V (Σ) , E
Σ
0
⊆ E (Σ)
и любая вершина v, v ∈ V (Σ
0
), которая либо относится
к множеству входов (выходов) Σ, либо служит конечной
(соответственно начальной) вершиной некоторого ребра из
E(Σ)\E(Σ
0
), является входом (соот ветствен но выходом) Σ
0
.
Из определений следует, что для СФЭ и КС с
неразделенными полюсами, как и для формул, имеет место
принцип эквивалентной замены. При этом все введенные
выше для случая эквивал ентн ых преобразований формул
понятия (однократная и кратная выводимость, полнота
системы тождеств и др.), а также связанные с ними
обозначения переносятся на случ ай ЭП указанных классов
схем без изменений.
§1. Преобразования на основе тождеств 67
•
•
1
2
2
2
2
2
2
2
•
•
2
x
1
x
2
&
¬
z
1
∼
•
•
+
+
+
+
+
+
+
•
1
+
+
+
+
+
+
+
•
•
2
x
1
x
2
¬ ¬
∨
z
1
•
•
•
•
•
{{
yy
x
1
x
2
¬
∨
&
z
1
∼
•
z
1
x
1
a) b)
Рис. 1.1: тождества t
M
&
и t
ΠK
1,&
Рассмотрим эти вопросы на примере ЭП СФЭ. Мы
будем использовать все введенные выше общие понятия и
определения, касающиеся ЭП схем, считая подстановкой
СФЭ переименование (с возможным отождествлением)
ее входных БП и переименование (с возможным
дублированием и снятием) ее выходных БП. Напомним,
что формулы п редставляют собой частный случай СФЭ,
и для определенности будем считать, что любая формула
F из U
Φ
Б
является формулой-словом (см. ?? главы 1),
а соответствующую ей формулу-граф, т. е. квазидерево
(см. §3 главы 2), будем обозначать через F. При этом
тождеству t : F
0
= F
00
, где F
0
и F
00
—формулы из U
Φ
Б
,
будет соответствовать тождество t : F
0
∼ F
00
, где F
0
и
F
00
— соответствующие F
0
и F
00
схемы из U
C
Б
, являющееся
«схемным» аналогом тождества t. Множество СФ Э вида
F, где F ∈ F ⊆ U
Φ
Б
, будем обозначать через F, а систему
тождеств вида t, где t ∈ τ , а τ — система тождеств для U
Φ
Б
,
— через τ. Так, на рис. 1.1a и 1.1b приведены тождества t
M
&
и t
ΠK
1,&
, являющиеся схемными аналогами введенных выше
формульных тождеств t
M
&
и t
ПK
1,&
.
68 Глава 3. Эквивалентные п реоб разова ния
•
•
1
*
*
*
*
*
*
*
*
*
*
*
•
k
i
. . .
x
1
x
k
i
z
1
, z
2
ϕ
i
∼
•
•
1
$
$
$
$
$
$
$
$
$
$
$
•
•
k
i
k
i
1
:
:
:
:
:
:
:
:
:
:
:
:
:
:
x
1
x
k
i
. . .
z
1
z
2
ϕ
i
ϕ
i
a)
•
•
*
*
*
*
*
*
*
*
*
*
*
•
. . .
x
1
x
k
i
ϕ
i
∼
•
. . .
•
x
1
x
k
i
•
x
1
∼ ∅
b) c)
Рис. 1.2: тождества ветвления, снятия ФЭ и снятия входа
На рис. 1.2a и 1.2b показаны тождество ветвления t
B
E
i
и тождество снятия t
C
E
i
для функционального элемента
E
i
, i ∈ [1, b], соответственно, а на рис. 1.2c — тождество
снятия входа t
C
вх
. Заметим, что применение тождества
снятия равносильно выполнению операции удаления
висячей вершины соответствующего типа (см. §3 главы 2).
Заметим также, что тождества t
B
E
i
, t
C
E
i
, t
C
вх
не являются
аналогами формульных тождеств и положим
τ
B
Б
=
t
B
E
i
b
i=1
, τ
C
Б
=
t
C
E
i
b
i=1
∪
t
C
вх
.
Очевидно, что с помощью этих тождеств можно избавит ься
от всех висячих вершин и всех внутренних ветвлений,
имеющихся в СФЭ. Следовательно, для любой СФЭ
Σ, Σ ∈ U
C
Б
, существует ЭП вида Σ ⇒
{τ
C
,τ
B
}
F
, где F —
§1. Преобразования на основе тождеств 69
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
F
1
8
8
8
8
8
8
F
n
8
8
8
8
8
8
. . .
F
0
8
8
8
8
8
8
F
@
@
@
@
@
@
~~
~
~
~
~
~
~
−→
t
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
F
1
8
8
8
8
8
8
F
n
8
8
8
8
8
8
. . .
F
00
8
8
8
8
8
8
b
Σ
@
@
@
@
@
@
~~
~
~
~
~
~
~
Рис. 1.3: моделирование ЭП формул с помощью ЭП СФЭ
формула (система формул) из U
Φ
Б
.
Пусть, далее, F −→
t
b
F — однократное ЭП для формул из
U
Φ
Б
, где тождество t имеет вид
t : F
0
(x
1
, . . . , x
n
) = F
00
(x
1
, . . . , x
n
) ,
а формула
b
F получается из формул ы F заменой
подформулы F
0
(F
1
, . . . , F
n
) формулой F
00
(F
1
, . . . , F
n
).
Сопоставим этому ЭП «моделирующее» его однократное
ЭП СФЭ вида F −→
t
b
Σ (см. рис. 1.3). Заметим, что в т ом
случае, когда формулы F
0
и F
00
являются бесповторными
формулами, а БП x
1
, . . . , x
n
— их существенными БП,
СФЭ
b
Σ совп адает с СФЭ F
00
. В остальных случаях из
подформулы вида F
0
(F
1
, . . . , F
n
) формулы F необходимо
с помощью тождеств τ
B
Б
сформировать сначала подсхему
F
0
(F
1
, . . . , F
n
), а затем применить тождество t. При этом в
СФЭ
b
Σ могут появиться висячие вершины или внутренние
«ветвления», и тогда для перехода от
b
Σ к
b
F необходимо
провести ЭП вида
b
Σ ⇒
{τ
C
,τ
B
}
b
F. Следовательно, для любого
ЭП вида F ⇒
τ
b
F, где F,
b
F ∈ U
Φ
Б
, существует моделирующее
70 Глава 3. Эквивалентные п реоб разова ния
•
•
•
•
•
##
•
##
•
•
{{
•
##{{
x
1
x
2
x
3
z
1
&
¬ ¬
∨
∨
&
−→
t
M
&
•
•
•
•
•
•
•
•
{{
))uu
x
1
x
2
x
3
z
1
&
& &
¬
∨
−→
t
B
&
−→
t
B
&
•
•
•
•
##
•
•
{{
•
{{
x
1
x
2
x
3
z
1
&
&
¬
∨
−−→
t
ΠK
1,&
• •
•
!!
•
}}
x
1
x
2
x
3
z
1
&
⇒
τ
C
•
x
1
z
1
Рис. 1.4: пример моделирования ЭП формул с помощью ЭП
СФЭ