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