Для перехода кмоделям задач структурного синтеза прирав-
няем множество
Z
кмножеству
X
. Множества
X
и
U
опреде-
лим как вершины и ребра графа соответственно. Тогда композиция
предикатов
Γ
1
(
X, U
)
и
Γ
2
(
U, X
)
— это предикат смежности графа
F
1
(
X, X
) = Γ
1
(
X, U
)
•
Γ
2
(
U, X
)
.
Переходя кобразам элементов множества
X
и
U
относительно пре-
дикатов
Γ
1
(
X, U
)
и
Γ
2
(
U, X
)
соответственно, получаем, что смежность
вершины
x
i
определяется как
F
1
x
i
=
{
x
k
:
∃
u
j
(
u
j
∈
Γ
1
x
i
&
x
k
∈
Γ
2
u
j
)
/u
j
∈
U, x
k
∈
X
}
.
Логически эквивалентным выражению
∃
u
j
(
u
j
∈
Γ
1
x
i
&
x
k
∈
Γ
2
u
j
)
будет
Γ
1
x
i
∩
Γ
−
1
2
x
k
=
∅
.
Теперь
F
1
x
i
(
X
) =
{
x
k
: Γ
1
x
i
∩
Γ
−
1
2
x
k
=
∅
/x
k
∈
X
}
.
Оценим число операций сравнения, необходимых для определения
образа вершины
x
i
относительно предиката смежности двумя спосо-
бами — как объединение подмножеств вершин, инцидентных ребрам
u
j
∈
Γ
1
x
i
, и как характеристическое множество предиката
F
1
x
i
(
X
)
.
В первом случае образ определяется по формуле
F
1
x
i
=
∪
u
j
∈
Γ
1
x
i
Γ
2
u
j
,
Число операций сравнения элементов множеств
Γ
2
u
j
будет равно
K
1
=
|
Γ
2
u
j
|
2
|
Γ
1
x
i
|
i
=2
[1 +
c
(
i
−
2)]
,
где
0
≤
c <
1
— коэффициент, учитывающий возможность того, что
у подмножеств
Γ
2
u
j
и
Γ
2
u
r
, принадлежащих
Γ
1
x
i
, могут быть общие
вершины. При
|
Γ
1
x
i
|
=
ρ
и
|
Γ
2
u
j
|
=
A
число операций сравнения
K
1
=
f
(
A
2
ρ
2
)
. Для определения
Γ
2
u
j
и
Γ
1
x
i
потребуется менее, чем
(
n
+
m
)
операций проверки
Γ
2
u
j
(
x
i
) =
“и
”
и
Γ
1
x
i
(
u
j
) =
“и". Тогда
K
1Σ
<
(
n
+
m
+
f
(
A
2
ρ
2
))
.
Если
|
Γ
1
x
i
|
и
|
Γ
2
u
j
|
ограничены
m
и
n
соответственно, то асим-
птотическая оценка будет
O
1
(
m
2
n
2
)
.
Определение
F
1
x
i
, как характеристического множества предиката
F
1
x
i
(
X
)
, потребует
K
2
=
|
Γ
1
x
i
| × |
Γ
−
1
2
x
k
|
n
операций сравнения. При
|
Γ
1
x
i
|
=
|
Γ
−
1
2
x
k
|
=
ρ
число операций сравнения
K
2
=
ρ
2
n
. Если
|
Γ
1
x
i
|
ограничена
m
, то асимптотическая оценка будет
O
2
(
m
2
n
)
.
Восьмой способ — использование свойств логических операций над
предикатами
. Рассмотрим использование свойства коммутативности
при определении характеристических множеств. Пусть необходимо
определить характеристические множества предикатов
T
1
(
X
) =
P
(
X
)&
Q
(
X
)
, T
2
(
X
) =
P
(
X
)
\
Q
(
X
) =
P
(
X
)&
Q
(
X
)
64 ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4
