4.3. Соответствие

Бинарное соответствие представляет собой тройку множеств:

g=(X, У, Q), Q Х У,

где Х  область отправления соответствия;

У  область прибытия соответствия;

Q  график соответствия.

Областью определения соответствия называется проекция Q на множество Х:

пр_Х={аХ/(а, у)Q}.

Областью значения соответствия называется проекция Q на множество У:

пр_у={вУ/(х, в)Q}.

Композицией двух соответствий называется последовательное применение соответствий:

g=(X,У,Q), Q Х У; p=(У,Z,P), PУ Z;

пр_уQ=пр_уP.

Соответствие γ=(X,У,Г) называется отображением и обозначается Г:ХУ, если Х=пр_ХГ.

Образом элемента аХ называют множество Г_а=Г(А)={вУ/(а,в)Г}.

Образом множества АХ называют множество Г_А=Г(А)={вУ/аА,(а,в)Г}.

Отображение ƒ: ХУ называется функцией, если

(х₁,у₁)ƒ  (х₁,у₂)ƒ у₁= у₂, то есть, если у₁= ƒ(х₂)  у₂= ƒ(х₂) у₁= у_2.

Функция ƒ называется единичной функцией, если у=ƒ(х₁) и у=ƒ(х₂), то есть х₁ =х₂.

В этом случае говорят, что функция ƒ:ХУ осуществляет взаимно однозначное соответствие между А и В.

Обратным отображением Г^-1 называется Г^-1={(х,у)/(у,х)Г}.

Бинарным отношением называется отображение, заданное на одном множестве R:Х Х. Если элемент х находится в отношении R к элементу у, то используется запись xRy.

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

- рефлексивность: xRх  истинно;

- антирефлексивность: xRх  ложно;

- симметричность: xRy уRх;

- антисимметричность: xRy  уRхх=у;

- несимметричность: xRy  истинно  уRх  ложно;

- транзитивность: xRy  уRzхRz .

Отношением эквивалентности называют отношение, обладающие следующими свойствами:

• рефлексивности xRх;

• симметричности xRy уRх;

• транзитивности xRy  уRzхRz .

Отношением нестрогого порядка называют отношение, обладающие следующими свойствами:

• рефлексивности хх (хх);

• антисимметричности ху  ухx=у (ху  ухx=у);

• транзитивности ху  уzxz (ху  уzxz).

Отношением строгого порядка называют отношение, обладающие следующими свойствами:

• антирефлексивности (х х  ложно);

• несимметричности (х у и у х  ложно);

• транзитивности (х у  у zx z).

Задачи и упражнения

1. Доказать или опровергнуть, что для любого бинарного соответствия φ и для любых множеств А и В справедливо равенство:

φ(АВ) = φ(А) φ(В).

Решение

уφ(АВ)хАВ/(х,у)φ(хА/(х,у)φ)  (хВ/(х,у) φ)уφ(А)  уφ(В) у φ(А) φ(В)  φ(АВ)  φ(А) φ(В);

уφ(А) φ(В) уφ(А)  уφ(В) (аА/(а,у)φ)   (вВ/(в,у)φ).

На этом этапе решения может представиться два случая:

а) аАВ  вАВ;

в) аАВ  вАВ.

В случае “а” уφ(АВ) φ(А) φ(В) φ(АВ), т.е. равенство выполняется.

В случае “б” ничего нельзя сказать о том, является ли у элементом множества φ(АВ) или нет. Таким образом, для любого бинарного соответствия φ справедливо утверждение: φ(АВ) = φ(А)  φ(В).

Задачи для самостоятельного решения

2. Пусть дано отображение Q:ХУ,

Х={х₁, х₂, х₃, х₄, х₅}, У={у₁, у₂, у₃, у₄};

Q={( х₁, у₂), (х₂, у₁), (х₂, у₃), (х₃, у₂), (х₄, у₁), (х₅, у₄)}.

Найти Q(А), Q^-1(В), А={ х₁, х₂, х₃}, В={ у₂, у₃, у₄}.

3. Доказать или опровергнуть, что для любого бинарного соответствия φ и для любых множеств А и В справедливо:

а) φ(АВ) = φ(А) φ(В);

б) φ(АВ) = φ(А) φ(В);

в) φ(А\В) = φ(А)\φ(В);

г) φ^-1(АВ) = φ^-1(А) φ^-1(В);

д) φ^-1(АВ) = φ^-1(А) φ^-1 (В);

е) φ^-1(А\В) = φ^-1(А)\ φ^-1(В);

ж) φ(А)= φ(А) φ(АВ);

з) φ(А_i)= φ(A_i);

и) φ(А_i)= φ(A_i);

к) φ^-1(А_i)= φ^-1(А_i);

л) φ^-1(А_i)= φ^-1(А_i).

4. Доказать, что для любой функции ƒ и для любых множеств А и В

ƒ(АВ)  ƒ(А) ƒ(В).

5. Доказать, что ƒ удовлетворяет условию ƒ(АВ)=ƒ(А) ƒ(В) для любых множеств А и В тогда и только тогда, когда ƒ есть единичная функция.

6. Доказать, что ƒ(А)\ƒ(В) ƒ(А\В) для любой функции ƒ.

7. Доказать, что если в предыдущем примере ƒ есть единичная функция, то выполняется равенство.

8. Доказать, что если АВ, то ƒ(А) ƒ(В) для любой функции ƒ.

9. Доказать, что если АВ, то ƒ^-1(А) ƒ^-1(В) для любой функции ƒ.

10. Доказать, что если А_ и В_ , где _ и _ соответственно области определения и значения функции ƒ, то:

а) А ƒ^-1(ƒ (А));

б) ƒ ( ƒ^-1 (В))=В;

в) ƒ (А)В= ƒ (А ƒ^-1(В));

г) ƒ (А) ƒ(В)=  А ƒ^-1(В)=О;

д) ƒ (А)ВА ƒ^-1(В).

11. Доказать, что для любых бинарных отношений справедливо:

а) RR=R;

б) RR=R;

в) (R^-1)^-1=R;

г) (R₁R₂)^-1= R₁^-1R₂^-1;

д) (R₁R₂)^-1= R₁^-1R₂^-1;

е)  (R₁^-1)=(R) ^–1.

12. Для каких бинарных отношений R справедливо R^-1=R.

13. Пусть А и В конечные множества, состоящие из m и n элементов соответственно. При каких m и n существует взаимно однозначное соответствие между А и В?

14. Составить алгоритм, выполняющий операцию пересечения двух множеств, заданных перечислением.

15. Составить алгоритм, выполняющий операцию объединения двух множеств, заданных перечислением.

16. Составить алгоритм, выполняющий операцию разности двух множеств, заданных перечислением.