а в противном случае — процедуру
(
∀
x
i
∈
Y t
)
Р
x
i
:=
Р
x
k
.
Какпоказано в [5], в этом случае любой элемент может перейти
в любое подмножество не более чем за
1 + log
2
n
шагов. Теперь вы-
числительная сложность всех слияний будет
O
(
n
log
2
n
)
— сравните
с полученной ранее оценкой, равной
O
(
n
2
)
. Формализация данного
способа и автоматизация его применения представляются сложными,
но разрешимыми задачами.
Шестой способ — определение результата операции над характе-
ристическими множествами одноместных предикатов как характе-
ристического множества результата операции над ними
. При зада-
нии множеств коллективизирующим свойством (характеристическим
предикатом) объединение, пересечение, дополнение, симметрическую
разность их характеристических множеств целесообразно определять
как характеристические множества соответствующих логических опе-
раций над этими предикатами. Рассмотрим этот способ на примере
операции объединения.
Пусть множества
P
и
Q
заданы предикатами
P
(
X
)
и
Q
(
X
)
. Не-
обходимо определить множество
R
=
P
∪
Q
. Проанализируем два
варианта определения множества
R
.
1. Находим множества
P
и
Q
как характеристические множества
предикатов в соответствии с выражениями
P
=
{
x
i
:
P
(
x
i
) =
“и”
/x
i
∈
X
}
и
Q
=
{
x
i
:
Q
(
x
i
) =
“и”
/x
i
∈
X
}
.
Затем выполняем операцию их объединения:
R
=
P
∪
Q
.
Число операций сравнения, необходимых для определения множе-
ства
R
, равно
F
1
= (
k
1
+
k
2
)
|
X
|
+
|
P
| × |
Q
|
,
где
k
1
и
k
2
— число операций, необходимых для определения истин-
ности
P
(
x
i
)
и
Q
(
x
i
)
соответственно.
2. Определяем характеристическое множество предиката
R
(
X
) =
=
P
(
X
)
∨
Q
(
X
)
:
R
=
{
x
i
:
P
(
x
i
) =
“и”
∨
Q
(
x
i
) =
“и”
/x
i
∈
X
}
.
В этом случае число операций сравнения, необходимых для опре-
деления множества
R
, равно
F
2
= (
k
1
+
k
2
+ 1)
|
X
|
.
Очевидно, что применение данного преобразования целесообразно
при
|
P
| × |
Q
|
>
|
X
|
.
В табл. 2 приведены логические операции над предикатами, харак-
теристические множества которых равны результатам операций над
множествами, указанным в первом столбце.
ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4 61
