жения
X
⊂
Y
=
Z
выражению
X
\
Z
⊂
Y
нетрудно убедиться.
Действительно:
X
⊂
Y
=
Z
⇔
(
∀
x
∈
X
)(
x
∈
Y
∨
x
∈
Z
)
и
X
\
Z
⊂
Y
⇔
(
∀
x
∈
X
&
x /
∈
Z
)(
x
∈
Y
)
.
Число сравнений элементов множеств
X, Y
и
Z
при реализации
выражения
X
⊂
Y
=
Z
равно
k
op
1
=
|
X
| ×
(
|
Y
|
+
|
Z
|
)
. Для выражения
X
\
Z
⊂
Y
при
|
X
∩
Z
|
=
∅
число операций сравнения
k
op
2
=
|
X
| ×
× |
Z
|
+ (
|
X
| − |
X
∩
Z
|
)
× |
Y
|
, отк уда
k
op
1
−
k
op
2
=
|
X
∩
Z
| × |
Y
|
.
Докажем эквивалентность выражений
X
\{
Y
∪
Z
}
выражению
X
\
Y
\
Z
. Известно, что
X
\{
Y
∪
Z
}
=
X
∩ {
Y
∪
Z
}
. По закону
де Моргана
{
Y
∪
Z
}
=
Y
∩
Z
. Тогда
X
\{
Y
∪
Z
}
=
X
∩
Y
∩
Z
,
но
X
∩
Y
=
X
\
Y
. Отсюда
X
\{
Y
∪
Z
}
=
X
\
Y
∩
Z
. С учетом
{
X
\
Y
}∩
Z
=
{
X
\
Y
}\
Z
окончательно получим
X
\{
Y
∪
Z
}
=
X
\
Y
\
Z
.
Покажем целесообразность замены выражения
X
\{
Y
∪
Z
}
на
X
\
Y
\
Z
. Число сравнений элементов множеств
X, Y
и
Z
при
Y
∩
Z
=
∅
оценивается по формуле
k
op
1
=
|
Y
| × |
Z
|
+
|
X
| ×
(
|
Y
|
+
|
Z
|
)
. Число
операций сравнения для выражения
X
\
Y
\
Z
будет максимальным в
предположении, что
X
∩
Y
=
∅
,
X
∩
Z
=
∅
и
Y
∩
Z
=
∅
−
k
op
2
=
|
X
|×
× |
Y
|
+
|
X
| × |
Z
|
. Следовательно,
k
op
1
−
k
op
2
=
|
Y
| × |
Z
|
.
Рассмотрим случай
Y
,
Z
⊂
X
. При
Y
∩
Z
=
∅
число опера-
ций для выражения
X
\{
Y
∪
Z
}
равно
k
op
1
=
k
op
1
и для выражения
X
\
Y
\
Zk
op
2
=
|
X
| × |
Y
|
+ (
|
X
| − |
Y
)
× |
Z
|
, отк уда
k
op
1
−
k
op
2
= (
|
X
|
+
+
|
Y
|
)
× |
Z
|
.
Является ли выполненный нами анализ возможных преобразова-
ний в данном случае достаточно полным и обеспечивающим тем са-
мым достижение поставленной цели — максимальное снижение вычи-
слительной сложности за счет преобразования данного вида? Вернем-
ся кзамене
X
⊆
Y
=
Z
на
{
X
\
Z
} ⊆
Y
. Ответ будет положительным,
если не существует других эквивалентных условий. Однако из теории
множеств [2] известно, что следующие условия эквивалентны:
A
⊆
B
∼
A
∩
B
=
A
∼
A
∪
B
=
B
∼
A
\
B
=
∅
∼
A
∪
B
=
U,
где
U
— универсум, под которым будем понимать все элементы дан-
ного вида, находящиеся в рассмотрении.
С учетом сказанного список эквивалентных фрагментов, которые
могут быть использованы для проверки условия в нашем алгоритме,
будет следующим:
1)
X
⊆
Y
=
Z,
2)
{
X
\
Z
} ⊆
Y,
3)
{
X
\
Z
} ∩
Y
=
{
X
\
Z
}
,
4)
{
X
\
Z
} ∪
Y
=
Y,
5)
{
X
\
Z
}\
Y
=
∅
,
6)
{
X
\
Z
} ∪
Y
=
U.
56 ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4
