Ложкин С.А. Лекции по основам кибернетики
Подождите немного. Документ загружается.
§5. Регулярные сдвиговые разбиения еди нич ного куба 131
1, . . . , 2
q−m
, образует разбиение куба B
q
на m-регулярные
подмножества.
Доказательство. Покажем сначала, что ∆ — покрытие
куба B
q
. Для этого возьмем произвольный набор из B
q
вида (β, γ), где β ∈ B
m
и γ ∈ B
q−m
, а по нему на йдем в
множестве δ набор вида (β, bγ), который имеется в δ в силу
m-регулярности этого множества. Следовательно,
(β, γ) = (β, bγ) ⊕ (0, . . . , 0
| {z }
m
, bγ ⊕ γ) = (β, bγ) ⊕ α,
где ν (α) < 2
q−m
. Таким образом, система ∆ образует
покрытие куба B
m
.
С другой стороны, из m-регулярности δ следует m-ре-
гулярность любого из множеств δ
i
, i = 1, . . . , 2
q−m
, и
поэтому
2
q−m
X
i=1
|δ
i
| = 2
m
2
q−m
= 2
q
.
Следовательно, система ∆ образует разбиение куба B
q
.
Лемма доказана.
В §5–§7 мы будем выбирать параметр m так, что
m 6 q 6 n,
и будем рассматривать разбиение ∆ = (δ
1
, . . . , δ
2
q−m
) куба
B
q
от БП x
0
= (x
1
, . . . , x
q
), построенное по лемме 5.1
для некоторого m-регулярного множества наборов δ =
δ
1
. Воспользуемся, в заключение, конструкцией леммы 5.1
для построения асимптотически опти мальн ых по сложности
контактных дешифраторов.
132 Глава 4. Синтез и сложность управляющих систем
Лемма 5.2 (ср. [14]). Для системы ФАЛ Q
n
при
n = 1, 2, 3, . . . выполняется неравенство
L
К
(Q
n
) 6 2
n
+ O
2
n
n
(5.1)
Доказательство. Выберем параметры m, q и λ так, что
λ = 2
n
, q = m + λ и q 6 n, (5.2)
а затем рассмотрим m-регулярное множество наборов δ
1
куба B
q
от БП x
0
= (x
1
, . . . , x
q
), связанное с системой ФАЛ
ψ = (ψ
1
, . . . , ψ
λ
), которая состоит из ЭК вида ψ
i
(x
0
) =
x
σ
1
1
···x
σ
q
q
, где ν (σ
1
, . . . , σ
q
) = i − 1, i ∈ [1, λ]. Построим по
лемме 5.1 разбиение ∆ = (δ
1
, . . . , δ
2
q−m
) куба B
q
и заметим,
что любая ЭК K (x
0
) = x
σ
1
1
···x
σ
q
q
, где σ
0
= (σ
1
, . . . , σ
q
) ∈ δ
i
,
i ∈ [1, λ], совпадает на множестве δ
i
с буквой x
¯α
m+i
m+i
и
ν (α) = i − 1.
Пусть, далее,
1, 2
λ
-КС Σ
0
реализует столбец из
ФАЛ χ
1
, . . . , χ
2
λ
, где χ
i
(x
0
) — характеристическая ФАЛ
множества δ
i
, i ∈
1, 2
λ
и получается из (1, 2
q
)-КД
от БП x
0
в результате соответствующего отождествления
выходов (см.рис. 5.1). Заметим, что в силу указанных выше
свойств разбиения ∆ любая ЭК K = x
σ
1
1
···x
σ
n
n
, где σ
0
=
(σ
1
, . . . , σ
q
) ∈ δ
i
и 1 6 i 6 2
λ
, может быть представлена в
виде
K = χ
i
x
0
· x
¯α
m+i
m+i
· x
σ
q+1
q+1
···x
σ
n
n
. (5.3)
Искомая (1, 2
n
)-КС Σ
&
n
реализует каждую ЭК из Q
n
в
соответствии с (5.3) и имеет вид, показанный на рис. 5.1.
Полагая
m = blog (n − 3 log n)c,
получим, что
p = 2
m
6 n − 3 log n, q = m + p 6 n − 2 log n,
2
m
>
n − 3 log n
2
,
§5. Регулярные сдвиговые разбиения еди нич ного куба 133
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
•
a
КД(x
0
)
•
2
p
p
p
p
p
p
p
p
e
e
e
e
e
e
e
Y
Y
Y
Y
Y
Y
Y
N
N
N
N
N
N
N
•
1
N
N
N
N
N
N
N
Y
Y
Y
Y
Y
Y
Y
e
e
e
e
e
e
e
p
p
p
p
p
p
p
.
.
.
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
КД(x
00
)
.
.
.
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
КД(x
00
)
.
.
.
•
•
•
•
x
m+p
N
N
N
N
N
N
N
N
x
m+2
f
f
f
f
f
f
f
x
m+1
p
p
p
p
p
p
p
p
.
.
.
a
p·2
n−m
−1
•
•
•
x
m+p
N
N
N
N
N
N
N
N
x
m+2
f
f
f
f
f
f
f
x
m+1
p
p
p
p
p
p
p
p
.
.
.
•
•
•
x
m+p
N
N
N
N
N
N
N
N
x
m+2
f
f
f
f
f
f
f
x
m+1
p
p
p
p
p
p
p
p
.
.
.
•
•
•
x
m+p
N
N
N
N
N
N
N
N
x
m+2
f
f
f
f
f
f
f
x
m+1
p
p
p
p
p
p
p
p
.
.
.
•
•
•
a
0
a
1
| {z }
b
Σ
00
Рис. 5.1: к доказательству леммы 5.2
то сложность построенной (1, 2
n
)-КС Σ
(&)
n
, являющейся
контактным дешифратором порядка n, удовлетворяет
неравенствам:
L
Σ
(&)
n
6 p2
n−m
+ 2
n−m+1
+ 2
q+1
6 2
n
+ O
2
n
n
,
из которых вытекает неравенство (5.1).
Лемма доказана.
Следствие. Оценка леммы 5.2 и следствия из леммы 1.5
дают асимптотическое равенство
L
К
(Q
n
) ∼ 2
n
134 Глава 4. Синтез и сложность управляющих систем
§6 Асимптотически наилучший метод синтеза
формул в базисе {&, ∨, ¬}
Для реализации ФАЛ из P
2
(n) асимптотически
оптимальными по сложности формулами и КС выберем
параметры m и q, по-прежнему удовлетворяющие (см. §5)
неравенствам
m 6 q 6 n (6.1)
При этом для произвольной ФАЛ f (x) из P
2
(n), где x =
= (x
1
, . . . , x
n
), вместо обычного разложения f по БП набор а
x
00
= (x
q+1
, . . . , x
n
) (см. (2.4)) будем рассматривать ее
представление в виде
f (x) =
=
_
σ
00
=(σ
q+1
,...,σ
n
)
x
σ
q+1
q+1
···x
σ
n
n
2
q−m
_
i=1
i
x
0
f
σ
00
,i
x
0
=
=
2
q−m
_
i=1
i
x
0
_
σ
00
=(σ
q+1
,...,σ
n
)
x
σ
q+1
q+1
···x
σ
n
n
f
σ
00
,i
x
0
, (6.2)
где x
0
= (x
1
, . . . , x
q
),
i
(x
0
) — характеристическая ФАЛ
множества δ
i
, i = 1, . . . , 2
q−m
и f
σ
00
,i
(x
0
) — произвольная
ФАЛ, совпадающая на δ
i
с ФАЛ f
σ
00
(x
0
) = f (x
0
, σ
00
).
Теорема 6.1 (ср. [14]). Для любой ФАЛ f, f ∈ P
2
(n), в
U
Φ
существует реализующая ее формула F
f
, для которой
L (F
f
) 6
2
n
log n
1 +
log log n + O (1)
log n
. (6.3)
Доказательство. Пусть, строки таблицы, показанной на
рис. 4.1, образуют m-регулярное множество
b
δ наборов куба
B
m+λ
, которое соответствует системе ФАЛ
−→
G, связанной
§6. Асимптотически наилучший метод синтеза формул 135
с ДУМ G. При это м из свойств ДУМ G след ует, что
любая ФАЛ из P
2
(m + λ) совпадает на множестве
b
δ с
некоторой монотонной ЭД ранга p от БП x
m+1
, . . . , x
m+λ
.
Пусть, далее, q = m + λ, а ∆ = ( δ
1
, . . . , δ
2
λ
) — разбиение
куба B
q
, полученное по лемме 5.1 для описанного множества
наборов
b
δ. Из отмеченных свойств множества
b
δ,
b
δ ⊆ B
m+λ
,
следует, что любая ФАЛ из P
2
(m + λ) совпадает на любом
множестве
b
δ ⊕α, где α ∈ B
m+λ
и ν (α) < 2
λ
, с некоторой ЭД
ранга p от БП x
m+1
, . . . , x
m+λ
.
Построим сначала для ФАЛ f на основе (6.2) формулу
e
F
f
с поднятыми отрицаниями, которая имеет вид
e
F
f
=
2
λ
_
i=1
A
i
(x
0
)
b
F
n−q
x
00
, J
e
0,i
, . . . , J
e
1,i
,
где
b
F
n−q
(x
00
, y
0
, . . . , y
2
n−q
−1
) — бесповторная по
информационным БП формул а из доказательства
леммы 1.3, реализующая ФАЛ µ
n−q
, A
i
, i ∈ [1, 2
λ
], —
совершенная ДНФ ФАЛ
i
, а ЭД J
σ
00
,i
ранга p от БП
x
m+1
, . . . , x
q
задает ФАЛ f
σ
00
,i
, σ
00
∈ B
n−q
и i ∈ [1, 2
λ
].
Пусть, далее, формула
b
F
f
получается из формулы
e
F
f
оптимизацией ее ЭД по числу отрицаний (см. §2 главы 2), то
есть заменой каждой ЭД J
σ
00
,i
вида x
j
1
∨. . .∨x
j
t
∨x
j
t+1
∨. . .∨x
j
p
,
где t 6 p, формулой
b
J
σ
00
,i
вида x
j
1
∨ . . . ∨ x
j
t
∨ x
j
t+1
···x
j
p
.
Заметим, что в формуле
b
F
f
на каждую подформулу
b
J
σ
00
,i
приходится не более одного ФЭ ¬, а число остальных ФЭ ¬
равно половине числа всех остальных вхождений в нее БП.
Следовательно, в силу леммы 2.1 главы 2,
L
&,∨
b
F
f
= R
b
F
f
−1 6
q · 2
m
+ 2
n−q+1
+ 2
n−q
· p
·2
λ
136 Глава 4. Синтез и сложность управляющих систем
то есть, учитывая ФЭ ¬, приходим к неравенству
L
b
F
f
6
3q · 2
m−1
+ 4 · 2
n−q
+ 2
n−q
· p
2
λ
6
6 p · 2
n−m
+ 4 · 2
n−m
+ 3q · 2
q−1
(6.4)
Выбирая значения параметров m и s, удовлетворяющие
(4.3), так, что
m = b2 log log nc, s = blog n − log log nc − 1,
получим следующие оценки остальных параметров
p 6
2
m
s
+ 1, λ 6 p2
s
.
2
m+s
s
.
n
2
, q = m + λ .
n
2
,
для которых при больших n выполняется неравенство (6.1).
Подставляя эти значения и оценки в (6.4), получим
неравенство
L
b
F
f
6
2
n
log n − log log n
+ O
2
n
log
2
n
, (6.5)
из которого для сложности формулы
b
F
f
следует оценка
(6.3).
Теорема доказана.
Следствие. Из (6.3), с учетом нижней оценки (3.10),
вытекает, что
L
Φ
(n) ∼
2
n
log n
.
§7 Асимптотически наилучший метод синтеза
контактных схем
Заметим сначала, что асимптотически наилучший метод
синтеза СФЭ из §4 без существенных изменений переносится
§7. Асимптотически наилучший метод синтеза КС 137
на класс U
КВС
— класс контактно-вентильных схем из §4
главы 2. Действительно, для любой ФАЛ f, f ∈ P
2
(n),
реализующая ее (1, 1)-КВС
e
Σ
f
может быть получена на
основе разложения (2.4) так же, как и СФЭ Σ
f
из теоремы
4.1. Она является результатом корректной суперпозиции
(см. §4 главы 2) вида
e
Σ
f
= Σ
00
(Σ
0
), где Σ
00
— (2
n−q
, 1)-
КД от БП x
00
, а (1, 2
n−q
)-КВС Σ
0
реализует систему всех
ФАЛ вида f
σ
00
(x
0
) , σ
00
∈ B
n−q
. При этом схема Σ
0
по-
прежнему содержит в качестве подсхемы (1, λ)-КС Σ
G
,
реализующую систему ФАЛ
−→
G на основе леммы 1.2, и
реализует каждую ФАЛ g (x
0
) типа f
σ
00
(x
0
) на основе ее
представления (6.1) в виде дизъюнкции g = g
1
∨ ··· ∨ g
p
с
помощью присоединения входов вентильной звезды порядка
p к соответствующим выходам КС Σ
G
(см. рис. 7.1 a, а
также рис. 4.3c из главы 2), которое является корректной
суперпозицией. Сложность построенной КВС
e
Σ
f
при тех
же значениях параметров, что и в теореме 4.1, будет
удовлетворять неравенству (4.5).
Напомним (см. §4), что в представлении (6.1) ФАЛ
g
1
, . . . , g
p
берутся из множеств G
(1)
, . . . , G
(p)
соответственно
и что для всех i, i ∈ [1, p], g
i
= g · χ
i
= g
i
· χ
i
, где χ
i
, χ
i
∈
G
(i)
, — характеристическая ФАЛ компоненты π
i
разбиения
Π = (π
1
, . . . , π
p
) куба B
m
(см. рис. 7.2a). Учитывая
эти особенности ФАЛ g
1
, . . . , g
p
, их дизъюнкцию g можно
реализовать на основе эквивалентного (6.1) представления
g = χ
1
· g
1
∨ ··· ∨ χ
p
· g
p
(7.1)
с помощью корректной суперпозиции т.-н. итератив но-
контактных схем, показанной на рис. 7.1b, где ФАЛ
χ
1
, . . . , χ
p
управляют проводимостью соответствующих
контактов. Асимптотически наилучший метод синтеза
КС связан с «моделированием» этой суперпозиции и
представления (7.1) на компонентах подходящего m-
регулярного разбиения куба B
m+p
.
138 Глава 4. Синтез и сложность управляющих систем
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
Σ
G
•
1
•
g
p
•
g
1
.
.
.
•
&&
N
N
N
N
N
N
N
N
N
N
99
r
r
r
r
r
r
r
r
r
r
g
.
.
.
a)
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
Σ
G
•
1
•
g
p
•
g
1
.
.
.
•
χ
1
N
N
N
N
N
N
N
N
N
N
χ
p
r
r
r
r
r
r
r
r
r
r
g
.
.
.
b)
Рис. 7.1: Корректная реализация дизъюнкции ФАЛ
g
1
, . . . , g
p
в классах КВС и ИКС
Пусть
ˇ
δ — m-регулярное множество наборов куба
B
m+p
, соответствующее системе ФАЛ
−→
χ = (χ
1
, . . . , χ
p
)
(см. рис. 7.2a), а ∆ = (δ
1
, . . . , δ
2
p
) — построенное для него по
лемме 5.1 разбиение куба B
m+p
. Заметим, что любая ФАЛ
g, g ∈ P
2
(m + p), на любой компоненте этого разбиен ия
вида
ˇ
δ ⊕ α, где
α = (0, . . . , 0
| {z }
m
, α
m+1
, . . . , α
m+p
),
совпадает с ФАЛ
ˇg = x
α
m+1
m+1
· g
1
∨ . . . ∨ x
α
m+p
m+p
· g
p
, (7.2)
где g
i
= gχ
i
∈ G
(i)
, i = 1, . . . , p. При этом ФАЛ ˇg может быть
§7. Асимптотически наилучший метод синтеза КС 139
x
1
. . .
x
m−1
x
m
χ
1
χ
2
. . .
χ
p
0
0
0
0
0
1
. . .
. . .
. . .
. . .
1
1
.
.
.
1
0
0
.
.
.
0
0
0
.
.
.
0
. . .
. . .
. . .
. . .
. . .
0
0
.
.
.
0
1
1
.
.
.
1
0
0
.
.
.
0
. . .
. . . . . . . . . . . . . . .
. . .
. . .
. . .
1 1
. . .
1
0
0
.
.
.
0
0
0
.
.
.
0
1
1
.
.
.
1
. . .
π
1
π
2
π
p
ˇ
δ
a)
Σ
G
M
M
M
M
M
M
M
M
M
M
M
M
M
M
M
q
q
q
q
q
q
q
q
q
q
q
q
q
q
q
1
•
•
.
.
.
g
1
g
p
ˇg
x
α
m+1
m+1
M
M
M
M
M
M
M
M
M
x
α
m+p
m+p
q
q
q
q
q
q
q
q
q
b)
Рис. 7.2: m-регулярное множество
ˇ
δ и связанная с ним
суперпозиция КС
140 Глава 4. Синтез и сложность управляющих систем
реализована в результате операции присоединения звезды
из контактов вида x
α
m+1
m+1
, . . . , x
α
m+p
m+p
к выходам (1, λ)-КС
Σ
G
, реализующей систему ФАЛ
−→
G, так, как это показано
на рис. 7.2b . Заметим также, что указанная операция
суперпозиции является корректной на множестве наборов
ˇ
δ ⊕α в силу разделительности присоединяемой (p, 1)-КС на
этом множестве.
Теорема 7.1 (ср. [14]). Для любой ФАЛ f , f ∈ P
2
(n),
существует реализующая ее КС Σ
f
такая, что
L (Σ
f
) 6
2
n
n
1 + O
1
√
n
(7.3)
Доказательство. Пусть q = m + p, а ∆ = (δ
1
, . . . , δ
2
p
) —
описанное выше разбиен ие куба B
q
, для которого
представление (6.2) ФАЛ f имеет вид
f
x
0
, x
00
=
2
p
_
i=1
i
x
0
_
σ
00
=(σ
q+1
,...,σ
n
)
x
σ
q+1
q+1
···x
σ
n
n
ˇg
σ
00
,i
x
0
,
(7.4)
где в качестве ФАЛ f
σ
00
,i
из разложения (6.2) при всех
σ
00
,σ
00
∈ B
n−q
, и i, i ∈ [1, 2
p
], берется ФАЛ ˇg
σ
00
,i
вида
(7.2), совпадающая с ФАЛ f
σ
00
(x
0
) на компоненте δ
i
=
ˇ
δ ⊕ α. Для реализации ФАЛ f, в соответствии с (6.2),
будем использовать суперпозицию вида Σ
00
(Σ
0
), где схема Σ
0
реализует систему всех ФАЛ ˇg
σ
00
,i
, а схема Σ
00
— «внешнюю»
часть разложения (6.2).
Пусть Σ
G
— (1, λ)-КС, которая реализует систему ФАЛ
−→
G по их совершенным ДНФ на осно ве контактного дерева
(см. лемму 1.2 и оценку (1.3)). Для каждого i, i = 1, . . . , 2
p
,
построим (1, 2
n−q
)-КС Σ
0
i
(см. рис. 7.3a), которая содержит
КС Σ
G
в качестве подсхемы и реализует каждую ФАЛ ˇg
σ
00
,i
вида (7.2) с помощью корректной на множестве наборов