Лекция 4. Матрица и свойства отношений, нечёткие множества

Бинарное отношение на множестве $A$ — это подмножество декартова квадрата $A \times A$ из лекции 3. Для конечного $A$ его удобно записывать таблицей из нулей и единиц — матрицей отношения, и по ней же сразу видно, какими свойствами отношение обладает. Вторая половина занятия — разбор задачи про нечёткие множества: элемент принадлежит множеству не «да или нет», а со степенью от $0$ до $1$, и операции над множествами из лекции 1 приходится переносить на этот случай.

1. Матрица отношения

Определение 1. Бинарное отношение на множестве $A$ — любое подмножество $R \subseteq A \times A$. Вместо $(a, b) \in R$ пишут $aRb$ и говорят «$a$ находится в отношении $R$ с $b$».

Определение 2. Пусть $A = \{a_1, \dots, a_n\}$. Матрица отношения $R$ — таблица $M_R = (m_{ij})$ размера $n \times n$, где

$m_{ij} = \begin{cases} 1, & a_i R a_j, \\ 0, & \text{иначе.} \end{cases}$

Строка $i$ отвечает за то, с чем связан $a_i$, столбец $j$ — что связано с $a_j$.

Два крайних примера для $A = \{1, 2, 3\}$. Отношение равенства $\mathrm{id} = \{(1, 1), (2, 2), (3, 3)\}$ и полное отношение $A \times A$:

$M_{\mathrm{id}} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \qquad M_{A \times A} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}.$

У пустого отношения $\varnothing$ матрица целиком из нулей. Любое другое отношение на $A$ лежит между ними: единицы стоят ровно в тех клетках, пары которых входят в $R$.

Пример. Отношение делимости $a \mid b$ на $A = \{1, 2, 3\}$ состоит из пар $(1, 1), (1, 2), (1, 3), (2, 2), (3, 3)$:

$M_{\mid} = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.$

2. Свойства отношений

2.1. Четыре определения

Пусть $R$ — отношение на $A$.

Определение 3. $R$ рефлексивно, если $\forall a \in A\ \ aRa$.

Определение 4. $R$ иррефлексивно, если $\forall a \in A\ \ \neg(aRa)$.

Определение 5. $R$ симметрично, если $\forall a, b \in A\ \ (aRb \to bRa)$.

Определение 6. $R$ антисимметрично, если $\forall a, b \in A\ \ (aRb \wedge bRa \to a = b)$.

Пример рефлексивного отношения — делимость: $a \mid a$, так как $a = 1 \cdot a$. На $A = \{1, 2, 3\}$ рефлексивность означает, что в отношении есть пары $(1, 1)$, $(2, 2)$ и $(3, 3)$ — все сразу.

Делимость на $\mathbb{N}$ ещё и антисимметрична: если $a \mid b$ и $b \mid a$, то $a = b$. А на $\mathbb{Z}$ уже нет: $2 \mid -2$ и $-2 \mid 2$, но $2 \ne -2$. Свойство зависит не только от правила, но и от множества, на котором отношение задано.

2.2. Как читать свойства по матрице

Диагональ в антисимметричности не участвует: $aRa$ и $aRa$ дают $a = a$, и это не противоречие.

2.3. Примеры на трёх элементах

Все отношения ниже — на $A = \{1, 2, 3\}$.

У пустого отношения симметричность и антисимметричность выполнены по пустоте: посылки $aRb$ ложны всегда, а импликация с ложной посылкой истинна — тот же приём, что и для $\varnothing \subseteq A$ в лекции 3.

3. Нечёткие множества

3.1. Функция принадлежности

У обычного (чёткого) множества $A \subseteq U$ каждый элемент либо лежит в нём, либо нет. Это можно записать характеристической функцией: $\mu_A(x) = 1$ при $x \in A$ и $\mu_A(x) = 0$ при $x \notin A$.

Определение 7. Нечёткое множество $F$ на универсуме $U$ задаётся функцией принадлежности $\mu_F\colon U \to [0, 1]$. Число $\mu_F(x)$ — степень, с которой $x$ принадлежит $F$.

Чёткое множество — частный случай, когда $\mu$ принимает только значения $0$ и $1$. Для конечного $U$ нечёткое множество записывают списком «элемент: степень».

3.2. Условие задачи

Задача 4. На универсуме $U = \{a, b, c, d, e\}$ заданы нечёткие множества $F$ и $R$:

Для чётких множеств $x \in A \cup B \iff x \in A \vee x \in B$ и $x \in A \cap B \iff x \in A \wedge x \in B$, и верно $A \cup A = A$, $A \cap A = A$. Операции переносятся на нечёткие множества так:

$\mu_{\overline{F}}(x) = 1 - \mu_F(x), \qquad \mu_{F \cup R}(x) = \max\big(\mu_F(x), \mu_R(x)\big), \qquad \mu_{F \cap R}(x) = \min\big(\mu_F(x), \mu_R(x)\big).$

Разность — как и для чётких множеств, через пересечение с дополнением: $F \setminus R = F \cap \overline{R}$, то есть

$\mu_{F \setminus R}(x) = \min\big(\mu_F(x),\ 1 - \mu_R(x)\big).$

Пункты задачи: (1) вычислить операции и объяснить, почему такой перенос естественный; (2) проверить законы $F \cup \overline{F} = U$ и $F \cap \overline{F} = \varnothing$; (3) перенести на нечёткие множества меру Жаккара; (4) исследовать пороговые срезы.

4. Операции над нечёткими множествами

4.1. Вычисления

Всё считается поэлементно: для каждого $x$ берём два числа из таблицы условия и применяем формулу.

Разности подробно, потому что в них легче всего ошибиться:

• $F \setminus R$: $\min(0{,}4;\ 0{,}4)$, $\min(0{,}8;\ 0{,}1)$, $\min(0{,}2;\ 0{,}6)$, $\min(0{,}9;\ 0{,}9)$, $\min(0{,}7;\ 0{,}5)$.
• $R \setminus F$: $\min(0{,}6;\ 0{,}6)$, $\min(0{,}9;\ 0{,}2)$, $\min(0{,}4;\ 0{,}8)$, $\min(0{,}1;\ 0{,}1)$, $\min(0{,}5;\ 0{,}3)$.

Разность не симметрична: $F \setminus R \ne R \setminus F$, как и для чётких множеств.

4.2. Почему перенос естественный

Первая причина: на чётких множествах новые операции дают старые. Если $\mu$ принимает только значения $0$ и $1$, то $\max$ и $\min$ работают как «или» и «и», а $1 - \mu$ — как «не»:

Вторая причина: сохраняется идемпотентность. Так как $\max(x, x) = x$ и $\min(x, x) = x$, для любого нечёткого $F$ по-прежнему $F \cup F = F$ и $F \cap F = F$.

5. Законы исключённого третьего и противоречия

Пустое множество и универсум как нечёткие множества: $\mu_\varnothing \equiv 0$ и $\mu_U \equiv 1$. Для чётких множеств всегда $A \cup \overline{A} = U$ и $A \cap \overline{A} = \varnothing$. Для нечётких:

$\mu_{F \cup \overline{F}}(x) = \max\big(\mu_F(x),\ 1 - \mu_F(x)\big) = 1 \iff \mu_F(x) \in \{0, 1\},$

$\mu_{F \cap \overline{F}}(x) = \min\big(\mu_F(x),\ 1 - \mu_F(x)\big) = 0 \iff \mu_F(x) \in \{0, 1\}.$

Значит, оба закона выполняются только там, где множество фактически чёткое. В задаче ни одна степень не равна $0$ или $1$, и оба закона нарушаются в каждой точке:

6. Мера и расстояние Жаккара

6.1. Перенос формулы

Для чётких множеств мера сходства Жаккара:

$J(A, B) = \frac{|A \cap B|}{|A \cup B|}.$

Чтобы перенести её, нужна мощность нечёткого множества. Естественный выбор — сумма степеней принадлежности:

$|F| = \sum_{x \in U} \mu_F(x).$

Для чёткого множества сумма нулей и единиц — это ровно число элементов. Подставив $\mu_{F \cap R} = \min$ и $\mu_{F \cup R} = \max$, получаем

$J(F, R) = \frac{\sum_{x \in U} \min\big(\mu_F(x), \mu_R(x)\big)}{\sum_{x \in U} \max\big(\mu_F(x), \mu_R(x)\big)}.$

Расстояние Жаккара для чётких множеств:

$d_J(A, B) = 1 - J(A, B) = \frac{|A \cup B| - |A \cap B|}{|A \cup B|}.$

В числителе для нечётких множеств стоит $\sum (\max - \min)$, а разность большего и меньшего из двух чисел — модуль их разности: $\max(p, q) - \min(p, q) = |p - q|$. Поэтому

$d_J(F, R) = \frac{\sum_{x \in U} \big|\mu_F(x) - \mu_R(x)\big|}{\sum_{x \in U} \max\big(\mu_F(x), \mu_R(x)\big)}.$

Проверка. При $\mu_F(x), \mu_R(x) \in \{0, 1\}$ $\max$ и $\min$ совпадают с объединением и пересечением (таблица из раздела 4.2), так что обе формулы превращаются в исходные чёткие. Перенос согласован.

6.2. Вычисление

$J(F, R) = \frac{2{,}0}{3{,}5} = \frac{4}{7} \approx 0{,}57, \qquad d_J(F, R) = \frac{1{,}5}{3{,}5} = \frac{3}{7} \approx 0{,}43.$

Проверка: $J + d_J = 1$. Больше половины расстояния даёт элемент $d$: в $F$ он почти наверняка ($0{,}9$), в $R$ почти нет ($0{,}1$).

7. Пороговые срезы

7.1. Определение и пример

Определение 8. Пороговый срез нечёткого множества $A$ на уровне $\theta \in [0, 1]$ — чёткое множество элементов со степенью принадлежности не ниже порога:

$(A)_\theta = \{x \in U \mid \mu_A(x) \ge \theta\}.$

В литературе его называют ещё $\alpha$-срезом. Срез превращает нечёткое множество в обычное: «считаем элементом всё, что принадлежит хотя бы на $\theta$».

Для $F \cup R = \{a\colon 0{,}6,\ b\colon 0{,}9,\ c\colon 0{,}4,\ d\colon 0{,}9,\ e\colon 0{,}7\}$:

• $(F \cup R)_{0{,}25} = \{a, b, c, d, e\} = U$ — все степени не меньше $0{,}4 \ge 0{,}25$;
• $(F \cup R)_{0{,}75} = \{b, d\}$;
• $(F \cup R)_{0{,}90} = \{b, d\}$ — неравенство нестрогое, $0{,}9 \ge 0{,}9$.

7.2. С ростом порога срез только сужается

Утверждение 1. Если $\theta_1 < \theta_2$, то $(A)_{\theta_2} \subseteq (A)_{\theta_1}$.

Доказательство. От противного: пусть найдётся $c$, для которого $c \in (A)_{\theta_2}$, но $c \notin (A)_{\theta_1}$. По определению среза

$c \in (A)_{\theta_2} \iff \mu_A(c) \ge \theta_2, \qquad c \notin (A)_{\theta_1} \iff \mu_A(c) < \theta_1.$

Тогда $\theta_2 \le \mu_A(c) < \theta_1$, то есть $\theta_2 < \theta_1$ — противоречие с $\theta_1 < \theta_2$. Значит, такого $c$ нет и каждый элемент верхнего среза лежит в нижнем. $\blacksquare$

То же напрямую: если $\mu_A(x) \ge \theta_2$ и $\theta_2 > \theta_1$, то $\mu_A(x) > \theta_1$. Повышая порог, мы только выбрасываем элементы и никогда не добавляем новые.

7.3. Сколько разных срезов даёт вся шкала

Срез меняется только тогда, когда порог переходит через одно из значений $\mu$. У $F \cup R$ различные степени — $0{,}4$, $0{,}6$, $0{,}7$, $0{,}9$, и они делят $[0, 1]$ на пять участков:

Ответ: $5$ различных подмножеств. Они вложены друг в друга, как и обещает утверждение 1. В общем случае $k$ различных ненулевых степеней дают $k + 1$ срез, если наибольшая степень меньше $1$ (последним срезом будет $\varnothing$), и $k$ срезов, если она равна $1$.

Частые ошибки

• Проверять антисимметричность по диагонали. Диагональ на неё не влияет: смотрят только пары клеток $(i, j)$ и $(j, i)$ при $i \ne j$.
• Считать «иррефлексивно» синонимом «не рефлексивно», а «антисимметрично» — синонимом «не симметрично». Контрпримеры — $\{(1, 1)\}$ и отношение равенства.
• Забывать, что пустое отношение симметрично и антисимметрично — по пустоте.
• В нечёткой разности брать $\mu_F - \mu_R$. Разность — это $\min(\mu_F, 1 - \mu_R)$: из $F \setminus R$ для $a$ получится $0{,}4$, а не $-0{,}2$.
• Путать местами множества в $R \setminus F$: там дополняется $F$, то есть $\min(\mu_R, 1 - \mu_F)$.
• Переносить на нечёткие множества $F \cup \overline{F} = U$ и $F \cap \overline{F} = \varnothing$. Эти законы верны только для чётких.
• В срезе ставить строгое неравенство. Порог включается: $(A)_{0{,}9}$ содержит элементы со степенью ровно $0{,}9$.

Мини-тренажёр

1. На $A = \{1, 2, 3, 4\}$ задано отношение $aRb \iff a - b$ чётно. Запишите матрицу и определите все четыре свойства.
2. Какими свойствами обладает $R = \{(1, 1), (1, 2), (2, 1)\}$ на $A = \{1, 2, 3\}$?
3. Может ли отношение быть одновременно симметричным и антисимметричным? Опишите все такие отношения.
4. Для $G = \{a\colon 0{,}3,\ b\colon 1,\ c\colon 0,\ d\colon 0{,}5\}$ найдите $\overline{G}$, $G \cup \overline{G}$ и $G \cap \overline{G}$. В каких точках выполняются законы исключённого третьего и противоречия?
5. Найдите $J(F, \overline{F})$ для $F$ из задачи. Чему равна $J(A, \overline{A})$ для непустого чёткого $A \ne U$?
6. Найдите $(F)_{0{,}5}$ и $(F)_{0{,}8}$ для $F$ из задачи. Сколько различных срезов даёт $F$ при $\theta \in [0, 1]$?
7. Докажите, что $(A \cap B)_\theta = (A)_\theta \cap (B)_\theta$ и $(A \cup B)_\theta = (A)_\theta \cup (B)_\theta$.

Ответы

1. Связаны числа одной чётности: $M_R = \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix}.$ Рефлексивно (диагональ из единиц), не иррефлексивно, симметрично ($M_R = M_R^T$), не антисимметрично ($1R3$ и $3R1$, но $1 \ne 3$).
2. Не рефлексивно (нет $(2, 2)$ и $(3, 3)$), не иррефлексивно (есть $(1, 1)$), симметрично, не антисимметрично ($1R2$ и $2R1$).
3. Может. Если $aRb$, то по симметричности $bRa$, а по антисимметричности $a = b$. Значит, $R \subseteq \mathrm{id}$, и наоборот, любое подмножество диагонали обладает обоими свойствами: у такой матрицы единицы только на диагонали.
4. $\overline{G} = \{a\colon 0{,}7,\ b\colon 0,\ c\colon 1,\ d\colon 0{,}5\}$, $G \cup \overline{G} = \{a\colon 0{,}7,\ b\colon 1,\ c\colon 1,\ d\colon 0{,}5\}$, $G \cap \overline{G} = \{a\colon 0{,}3,\ b\colon 0,\ c\colon 0,\ d\colon 0{,}5\}$. Законы выполняются в $b$ и $c$, где степень равна $1$ или $0$.
5. $\sum \min(\mu_F, 1 - \mu_F) = 0{,}4 + 0{,}2 + 0{,}2 + 0{,}1 + 0{,}3 = 1{,}2$, $\sum \max = 0{,}6 + 0{,}8 + 0{,}8 + 0{,}9 + 0{,}7 = 3{,}8$, $J = \dfrac{1{,}2}{3{,}8} = \dfrac{6}{19} \approx 0{,}32$. Для чёткого $A \cap \overline{A} = \varnothing$, поэтому $J(A, \overline{A}) = 0$: у нечёткого множества с дополнением «общего» больше нуля.
6. $(F)_{0{,}5} = \{b, d, e\}$, $(F)_{0{,}8} = \{b, d\}$. Степени $0{,}2;\ 0{,}4;\ 0{,}7;\ 0{,}8;\ 0{,}9$ — пять различных, наибольшая меньше $1$, поэтому срезов $6$: $U$, $\{a, b, d, e\}$, $\{b, d, e\}$, $\{b, d\}$, $\{d\}$, $\varnothing$.
7. $x \in (A \cap B)_\theta \iff \min(\mu_A(x), \mu_B(x)) \ge \theta \iff \mu_A(x) \ge \theta \wedge \mu_B(x) \ge \theta \iff x \in (A)_\theta \cap (B)_\theta$: минимум не меньше порога, когда оба числа не меньше. Для объединения так же: $\max \ge \theta$, когда хотя бы одно число не меньше $\theta$.

Шпаргалка