ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9327
Скачиваний: 24
36
Симметричности:
d(m
i
, m
j
) = d(m
j
, m
i
).
Транзитивности:
d(m
i
, m
j
) + d(m
j
, m
k
) = d(m
i
, m
k
).
Расстоянием Хемминга d
h
(A,B)
между подмножествами
А,
В
(обыкновенные детерминированные подмножества, в этом слу-
чае
μ
А
(х) принимает значения из {0,1}) называется число, равное
∑
=
μ
−
μ
n
1
i
i
B
i
A
|
)
x
(
)
x
(
|
,
где n
− размерность пространства.
Относительным расстоянием Хемминга d
hо
(A,B)
между
подмножествами А и В называется число, равное
n
–1
•
d
h
(A,B).
Рассмотрим пример. Пусть А ={10110}, B={01101}.
Расстояние Хемминга d
h
(A,B) = 4. Относительное расстоя-
ние Хемминга d
hо
(A,B) = 5
–1
•4 = 0.8.
Обобщенное расстояние Хемминга
(линейное расстояние)
d
л
(А, В
) между нечеткими подмножествами А, В определяется
значением
∑
=
μ
−
μ
n
1
i
i
B
i
A
|
)
x
(
)
x
(
|
,
где n
− размерность пространства.
Здесь
μ
А
(х) принимает значения на интервале [0, 1].
Пример.
А={(0.2/1), (0.8/2), (1.0/3), (0.0/4), (0.7/5), (0.8/6)},
B={(0.3/1), (0.9/2), (0.8/3), (0.6/4), (1.0/5), (0.0/6)}.
d
л
(А, В) =|0.2–0.3| + |0.8–0.9| +|1.0–0.8| +|0.0–0.6| +
+|0.7–1.0|+|0.8–0.0|=2.1.
Относительное линейное расстояние
d
ол
(А, В
) определяется как
d
ол
(А, В) = n
–1
•
d
ол
(A,B).
Евклидовым (квадратным) расстоянием
d
e
(А,В)
между не-
четкими подмножествами А и В называется число
где n – размерность пространства. Очевидно, что относительное
евклидово расстояние
d
eo
(А, В
) определяется как
(
)
,
)
x
(
)
x
(
n
1
i
2
i
B
i
A
∑
=
μ
−
μ
,
n
)
B
,
A
(
d
0
e
≤
≤
37
в этом случае 0 ≤ d
eo
≤ 1.
Рассмотрим еще два определения «расстояние»: – линейный
индекс нечеткости
λ (А'), вычисляемый через относительное ли-
нейное расстояние d
oл
(А', А), и квадратичный индекс нечеткости
Χ (А'), определяемый посредством относительного евклидова
расстояния d
eo
(А', А),
(
)
( )
(
)
;
)
x
(
)
x
(
n
2
)
'
A
(
X
;
)
x
(
)
x
(
)
n
(
2
)
A
(
n
1
i
2
i
A
i
'
A
1
n
1
i
i
A
i
A
1
'
∑
∑
=
−
=
−
μ
−
μ
⋅
⋅
=
μ
−
μ
⋅
⋅
=
λ
где n – размерность пространства,
2 – коэффициент, обеспечивающий соотношения
0
≤ λ(А') ≤ 1, 0 ≤ Х(А') ≤ 1.
3.2
Задачи
и
упражнения
1. Доказать закон де Моргана для нечетких множеств.
2.Доказать закон поглощения для нечетких множеств.
А
∪А∩В = А; А ∩ (А∪В) = А.
3.
Задано два нечетких подмножества A и B множества M =
={1,2,3,4,5,6,7};
A={(0.3|2), (0.7|4), (0.9|6)};
B={(0.2|1), (0.4|3), (0.1|4), (0.9|6), (0.2|5), (0.5|7)}.
Найти: Ā; А
∪В; А∪ ; А∩В; Ā ∩В; Ā ∩ .
4. Задано нечеткое подмножество А. Найти Ā.
M
μ(A)
А
( )
).
B
,
A
(
d
n
)
B
,
A
(
d
e
1
eo
−
=
;
B
A
B
A
,
B
A
B
A
∩
=
∪
∪
=
∩
B
B
,
38
5. Заданы два нечетких множества А и В.
Отобразить А
∩В; А∪ Ā ∩В.
6. Заданы нечеткие подмножества А, В,С множества
М = {1, 2, 3, 4, 5, 6 }; А={(0.1|3), (0.6|4), (0.7|5)}; B={(0.3|2),
(0.4|6), (0.1|1)}; C={(0.2|2), (0.3|4), (0.7|1), (0.1|5)}.
Найти дополнение их пересечения и объединения.
7. Даны два подмножества А и В множества М. М={1, 2, 3,
4, 5, 6, 7}, A={3, 6,2,1,7}, B={1, 2, 4, 6, 5}. Найти расстояние по
Хеммингу, относительное расстояние по Хеммингу.
8. Заданы два нечетких подмножества А и В множества М =
={1, 2, 3, 4, 5, 6}. A={(0.1|1), (0.3|2), (0.4|3), (0.4|4), (0.3|5),
(0.2|6)}, B={(0.2|1), (0.4|2), (0.8|3), (0.9|4), (0.1|5), (0.9|6)}. Найти
расстояние по Хеммингу, относительное расстояние по Хеммин-
гу между нечеткими подмножествами А и В.
M
В
M
А
39
4 K-
ЗНАЧНАЯ
ЛОГИКА
4.1
Элементарные
функции
k-
значных
логик
и
соотношение
между
ними
Всюду в этой главе число
k
предполагается натуральным
большим 2. Через
E
k
обозначается множество
{0, 1, …, k–1}
.
Функция
f(x
1
, x
2
, …, x
n
)
называется функцией
k-значной логики
,
если на всяком наборе
)
a
,...,
a
,
a
(
a
~
n
2
1
=
значений переменных
x
1
,
x
2
, …, x
n
, где
a
i
∈
E
k
,
значение
f(a
1
, a
2
, …, a
n
)
∈
E
k
. Совокупность
всех функций
k-
значной логики обозначается через
P
k
.
Очевидно, что функция
f(x
1
, x
2
, …, x
n
)
полностью определе-
на, если задана ее таблица (см. табл.ХХХ). В этой таблице набо-
ры суть разложения в
k
-ичной системе счисления чисел
0, 1, …,
k
n
−
1
. Символ
f
здесь будет интерпретироваться как символ, обо-
значающий отображение, характеризуемое таблицей, а символы
x
1
, x
2
, …, x
n
– как названия столбцов.
x
1
x
2
x
i
x
n–1
x
n
f(x
1
, x
2
, …, x
n
)
0
0
…
0
…
0
0
f(0, 0, …, 0, 0)
0
0
…
0
…
0
1
f(0, 0, …, 0, 1)
…
…
0
0
…
0
…
0
k–1
f(0, 0, …, 0, k–1)
0
0
…
0
…
1
0
f(0, 0, …,1, 0)
…
…
k–1 k–1
…
k–1
…
k–1 k–2
f(k–1, k–1, …, k–1, k–2)
k–1 k–1
…
k–1
…
k–1 k–1
f(k–1, k–1, …, k–1, k–1)
Теорема. Число всех функций из
P
k
,
зависящих от
n
пере-
менных
x
1
, x
2
, …, x
n
,
равно
n
k
k .
Из сказанного вытекает, что в
P
k
при
k
≥
3
в значительной
степени возрастают трудности по сравнению с
P
2
как в возмож-
ности эффективного использования табличного задания функций,
так и в возможности просмотра всех функций от
n
переменных.
Уже в
P
3
число функций от двух переменных равно 3
9
=19683, т.е.
это множество практически необозримо. В
P
k
часто употребляют
вместо табличного задания функций задание при помощи алго-
ритма вычислимости функций. Например,
max(x
1
, x
2
, …, x
n
)
40
можно рассматривать как алгоритм, который для любого набора
(a
1
, a
2
, …, a
n
)
значений переменных выдает их максимум. Этот
алгоритм определяет в
P
k
единственную функцию, которую бу-
дем обозначать тем же символом.
Понятия фиктивной и существенной переменных, равных
функций, формулы над множеством функций (и связок), опера-
ций суперпозиции и замыкания, замкнутого класса, базиса и дру-
гие в
k-
значных логиках определяются так же, как существую-
щие понятия в алгебре логики.
Следующие функции k-значной логики считаются элемен-
тарными:
Константы
0, 1, …, k–1;
эти функции будут рассматриваться
как функции, зависящие от произвольного конечного числа пе-
ременных (включая и нуль переменных).
Отрицание Поста
:
)
k
(mod
1
x
x
+
=
. Здесь
x
представля-
ет обобщение отрицания в смысле «циклического» сдвига значе-
ний.
Отрицание Лукасевича
:
x
1
k
x
~
Nx
−
−
=
=
. Здесь
~x
является
обобщением отрицания в смысле «зеркального» отображения
значений.
Характеристическая функция первого рода
числа i:
j
i
(x)
(i=0, 1, …, k–1)
⎩
⎨
⎧
≠
=
=
.
i
x
если
,
0
,
i
x
если
,
1
)
x
(
j
i
Характеристическая функция второго рода
числа i:
J
i
(x)
(i=0, 1, …, k–1)
⎩
⎨
⎧
≠
=
−
=
.
i
x
если
,
0
,
i
x
если
,
1
k
)
x
(
J
i
Минимум
x
1
и
x
2
:
min (x
1
, x
2
)
– обобщение конъюнкции.
Максимум x
1
и
x
2
:
max (x
1
, x
2
)
– обобщение дизъюнкции.
Сумма по модулю
k
:
x
1
+x
2
(mod k)
, читается «
x
1
плюс
x
2
по
модулю
k
».
Произведение по модулю k
:
x
1
⋅
x
2
(mod k),
читается «про-
изведение
x
1
на
x
2
по модулю
k
».
Усеченная разность
: