ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9324
Скачиваний: 24
31
2.3
Задачи
и
упражнения
2.1. Укажите номера всех пар, являющихся элементами от-
ношения:
a – b = 2, a
∈ A, A = {1, 2, 3, 4, 5}, b ∈ B, B = {6, 7, 8, 9, 10,
11, 12}.
1)
3,1; 2) 6,4; 3) 4,6; 4) 5,3; 5) 4,2; 6) 7,5; 7) 8,6.
2.2. Найдите элементы множества
(A
×B)⊕(B∩A), A = {a, b}, B = {b, c}.
2.3. Найдите элементы множеств А и В, если
A
×B = {<a, 3>, <a, 8>, <b, 3>, <b, 8>, <k, 3>, <k, 8>}.
2.4. Декартово произведение множеств А и В содержит 12
элементов. Известно, что А = {a, k, f} и А
∩В = ∅. Найдите число
собственных подмножеств множества В.
2.5. Укажите рефлексивные отношения:
-
точка а удалена от точки b на 4 см;
-
a
≤ b, где a и b – натуральные числа;
-
a
≠ b, где a и b – натуральные числа;
-
a похоже на b (в множестве людей);
-
Петров и Сидоров имеют одинаковый рост;
-
Смирнов и Васильев живут на третьем этаже;
-
число а не больше числа b;
-
поезд a идет быстрее поезда b.
2.6. Укажите симметричные отношения:
-
лесоруб спилил дерево;
-
число а не больше числа b, где a, b
∈{1, 2, 3,…, 9};
-
а равно b;
-
с старше, чем b;
-
Таня – сестра Пети;
-
25 + 10 = 20 + 15.
2.7. Укажите транзитивные отношения:
-
быть южнее;
-
не равно;
-
быть врагом;
-
являться матерью;
-
дружить.
2.8. Укажите отношения эквивалентности:
32
-
автомобиль а столкнулся с автомобилем b;
-
высота горы а равна высоте горы b;
-
Иванов задал вопрос Петрову;
-
a + b = 100, где a, b
∈{1, 2, 3,…, 100}.
-
прямая а перпендикулярна прямой b;
-
A и b равновеликие треугольники;
-
фраза а имеет тот же самый смысл, что и фраза b.
2.9. Привести примеры отношений:
-
не рефлексивного, но симметричного и транзитивного;
-
не симметричного, но рефлексивного и транзитивного;
-
не транзитивного, но рефлексивного и симметричного.
2.10. На множестве А
×А, где А – множество натуральных
чисел {1, 2, 3,…} определено отношение R : <x, y> R<u,v>, такое,
что х + v = y + v. Доказать, что R – отношение эквивалентности
на этом множестве.
2.11. Доказать, что если отношения R
1
и R
2
рефлексивны, то
рефлексивны отношения R
1
∪R
2
, R
1
∩R
2
.
2.12. На множестве А = {1, 2, 3, 4, 5} задано отношение R =
={<1,2>, <3,1>, <3,4>, <4,4>, <5,4>}. Построить рефлексивное,
симметричное и транзитивное замыкания.
33
3
НЕЧЕТКИЕ
МНОЖЕСТВА
Расширим понятия множества, введя свойство нечеткости.
Принадлежность элемента
х
множеству
А х
∈
А, А
⊂
М
будем
задавать с помощью характеристической функции:
μ
А
(х
), которая
принимает значения на интервале
[ 0, 1 ]
. В соответствии с этим
элемент может не принадлежать множеству
А
(в этом случае
μ
А
(х) =0
), может принадлежать множеству
А
в какой-то степени,
может быть элементом множества
А (
μ
А
(х)=1).
Нечеткие множества применяются в том случае, когда за-
труднительно использовать традиционный математический аппа-
рат, то есть когда характеристики объекта размыты. Как правило,
это качественные характеристики и они не могут быть однознач-
но интерпретированы.
Нечетким множеством
А
множества
М
назовем множест-
во пар
А={(
μ
А
(х) | x)}, где х
∈
М,
μ
А
(х)
∈
[ 0, 1].
Функция
μ
А :
хÆ [ 0, 1
] называется
функцией принадлеж-
ности
нечеткого множества
А
.
М
называется
базовым множе-
ством
. Множество элементов
Х
⊂
М
, для которых функция
принадлежности не равна нулю, называется
носителем нечетко-
го множества.
Для каждого конкретного значения
х
∈
М
величина
μ
А
(х)
принимает определенное значение из заданного интервала
[ 0, 1].
Величина
μ
А
(х)
называется
степенью принадлежности
элемен-
та
х
к множеству
А
.
Обозначим
Р = {
μ
А
(х)
}
– множество принадлежностей.
Пусть
М
– базовое множество, Р – множество принадлежно-
стей,
А
и
В
два нечетких множества.
Будем говорить, что
А
содержится в
В
, если
(
∀
х
∈
М)
(
μ
А
(х)
≤
μ
В
(х) )
,
и обозначать
А
⊂
В
, если неравенство строгое, то обознача-
ем
А
⊂
⊂
В
. Скажем, что
А
и
В
равны тогда и только тогда, когда
(
∀
х
∈
М) (
μ
А
(х) =
μ
В
(х)
), и будем обозначать
А=В
. Если найдет-
ся по крайней мере один такой элемент из
М
, что равенство
34
(
μ
А
(х) =
μ
В
(х))
не удовлетворяется, то будем говорить, что
А
и
В
не равны и обозначать
А
≠
В
.
Пример. Пусть Х множество натуральных чисел. Тогда его
нечеткое подмножество «очень малых чисел» может быть таким:
А={(1/1), (0.8/2), (0.7/3), (0.6/4), (0.5/5), (0.3/6), (0.1/7)}. Но-
сителем нечеткого множества А является множество Х={1, 2, 3,
4, 5, 6, 7}. Функция принадлежности определяется субъективно.
3.1
Операции
над
нечеткими
множествами
Пусть М – базовое множество, Р = [0,1 ] – множество при-
надлежности, А и В два нечетких подмножества. К нечетким
множествам применимы те же операции, что и к обычным мно-
жествам.
Дополнение.
А
и
В
дополняют друг друга
А = В
или
А = В
,
если
(
∀
х
∈
М) (
μ
А
(х) = 1 –
μ
В
(х) ).
Пример.
М ={1, 2,3,4,5,6,7}. А = {(0.3/1), (0.7/3), (0.9/6)}.
Тогда Ā = {(0.7/1), (1/2), (0.3/3) (1/4), (1/5), (0.1/6), (1/7)}.
Пересечение
. Пересечение
А ∩ В
определяют как наиболь-
шее нечеткое подмножество, содержащееся одновременно в
А
и
В
.
(
∀
х
∈
М) (
μ
А∩В
(х) = min (
μ
А
(х),
μ
В
(х) ).
Объединение
. Определим объединение
А
∪
В
как нечеткое
множество, которое содержит как
А
, так и
В
.
(
∀
х
∈
М) (
μ
А
∪В
(х) = max (
μ
А
(х),
μ
В
(х) ).
Введенные операции дополнения, объединения, пересечения
удовлетворяют законам:
Коммутативности объединения и пересечения:
А
∩В = В∩А, А∪В = ВА.
Закон ассоциативности:
А
∪ (В∪С) = (А∪В) ∪ С;
А
∩(В∩С) = (А∩В) ∩С.
Закон дистрибутивности пересечения относительно объеди-
нения и объединения относительно пересечения:
А
∩ (В∪С) = А∩ В∪А∩С;
35
А
∪ (В∩С) = (А∪В) ∩ (А∪С).
Закон идемпотентности:
А
∪ А = А; А ∩ А = А.
Законы де Моргана:
Закон двойного дополнения:
Действия с универсальным и пустым множествами:
А
∪ ∅ = А, А ∩ ∅ = ∅, А ∪1 = 1, А ∩1 = А.
∅ – пустое множество. ∅ ↔ (∀ х ∈А) (μ
∅
(х) = 0 ).
1 – универсальное множество 1
↔ (∀ х ∈А) (μ
1
(х) = 1 ).
Необходимо заметить, что соотношения А
∩ Ā = ∅, А ∪ Ā =
= 1 с нечеткими множествами не выполняются. Рассмотрим при-
мер. Пусть М = {1, 2, 3, 4, 5, 6}. A = {(0.3/1), (0.4/2), (0.5/3),
(0.8/4), (0.9/5),(1/6)}.
Тогда Ā = {(0.7/1), (0.6/2), (0.5/3), (0.2/4), (0.1/5), (0/6)}.
А
∩ Ā = {(0.3/1), (0.4/2), (0.5/3), (0.2/4), (0.1/5), (0/6)}.
А
∪ Ā = {(0.7/1), (0.6/2), (0.5/3), (0.8/4), (0.9/5), (1/6)}.
В силу несправедливости выше приведенных соотношений
не выполняются законы склеивания:
В
∩А∪В∩Ā ≠ В, В ∪А∩В∪Ā ≠ В.
Так же не выполняются законы Порецкого:
А
∪В∩Ā ≠ В∪А, А∩(В∪Ā) ≠ А∩В.
Ряд задач информационной математики сводятся к опреде-
лению «близости» нечеткого подмножества к подмножеству, вы-
полняющему роль эталона. При решении этих задач используется
понятие метрического пространства.
Метрическим пространством
называется множество (M,
D), состоящее из элементов множества
М
(точек) и определенно-
го в нем расстояния
d(m
i
, m
j
)
∈
D
между любыми двумя точками
m
i
, m
j
, удовлетворяющего условиям:
Неотрицательности:
⎩
⎨
⎧
≠
=
j
i
j
i
j
i
m
m
если
,
1
m
m
если
,
0
)
m
,
m
(
d
;
B
A
B
A
,
B
A
B
A
∩
=
∪
∪
=
∩
;
A
A
=