Таблица 2
Соответствие операций над множествами операциям над предикатами
Операции над множествами
Логические операции над предикатами
P
∪
Q
P
(
X
)
∨
Q
(
X
)
P
∩
Q
P
(
X
)&
Q
(
X
)
P
\
Q
P
(
X
)&
Q
(
X
)
P
Δ
Q
P
(
X
)Δ
Q
(
X
) = (
P
(
X
)
∨
Q
(
X
))& (
P
(
X
)&
Q
(
X
))
Пример использования такого преобразования в алгоритме струк-
турного синтеза.
Решается задача декомпозиции структуры систе-
мы на две подсистемы с равным числом компонентов. Моделью
структуры системы является гиперграф, представленный в форме
H
(
X, U,
Γ
X,
Γ
U
)
,
|
X
|
=
n
,
|
U
|
=
m
. В результате работы алгоритма
разрезания гиперграфа на два куска
H
к
1
(
X
1
, U
1
)
и
H
к
2
(
X
2
, U
2
)
полу-
чены множества
X
1
и
X
2
(
|
X
1
|
=
|
X
2
|
=
n/
2
). Рассмотрим только
определение множества связей между подсистемами. Напомним, что
по определению куска графа
U
1
=
{
U
1
,
1
, U
1
,
2
}
, U
2
=
{
U
2
,
2
, U
2
,
1
}
,
U
1
,
1
∩
U
1
,
2
=
∅
, U
2
,
2
∩
U
2
,
1
=
∅
, U
1
,
2
=
U
2
,
1
=
U
1
∩
U
2
,
где
U
1
,
1
и
U
2
,
2
— внутренние ребра кусков
H
к
1
и
H
к
2
;
U
1
,
2
и
U
2
,
1
—
внешние ребра этих кусков.
Свойство, определяющее принадлежность ребра
u
j
множеству
U
1
(
U
2
), можно сформулировать, например, так: “хотя бы одна верши-
на множества
X
1
(
X
2
)
и ребро
u
j
инцидентны”. При представлении
множеств
X, U,
Γ
X
,
Γ
U
перечислением предикаты
P
1
(
U
)
и
P
2
(
U
)
, ха-
рактеристическими множествами которых являются
U
1
и
U
2
соответ-
ственно, запишем как
P
1
(
u
) =
“
Γ
u
∩
X
1
=
∅
” и
P
2
(
u
) = “Γ
u
∩
X
2
=
∅
”
.
Рассмотрим 1-й и 2-й варианты определения множеств
U
1
,
U
2
и
U
1
,
2
:
U
1
=
{
u
j
: Γ
u
j
∩
X
1
=
∅
/u
j
∈
U,
Γ
u
j
∈
Γ
U
}
;
U
2
=
{
u
j
: Γ
u
j
∩
X
2
=
∅
/u
j
∈
U,
Γ
u
j
∈
Γ
U
}
, U
1
,
2
=
U
1
∩
U
2
.
Число операций сравнения, необходимых для определения множе-
ства
U
1
,
2
, равно
F
1
= (
k
1
+
k
2
)
|
U
|
+
|
U
1
|×|
U
2
|
,
где
k
1
=
|
Γ
u
j
|×|
X
1
|
и
k
2
=
|
Γ
u
j
|×|
X
2
|
.
Для разрезания на куски справедливо:
|
U
1
,
1
|
+
|
U
2
,
2
|
+
|
U
1
,
2
|
=
|
U
|
,
|
U
1
|
=
|
U
1
,
1
|
+
|
U
1
,
2
|
и
|
U
2
|
=
|
U
2
,
2
|
+
|
U
2
,
1
|
. На основании закона Рента
имеем
|
U
1
,
2
|
=
|
Γ
x
|×|
X
1
|
0
,
5
. Принимая
|
Γ
u
|
=
A
,
|
Γ
x
|
=
ρ
и
|
U
1
|
=
|
U
2
|
,
62 ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4
