19.Поняття композиції відношень

Композицією відношень R і S називається відношення, що складається з упорядкованих пар (x,z)<x·z (xX, zZ), для яких існує елемент yY, такий, що виконуються умови (х,у) R, (y,z) S. Композиція відношень R і S позначається SR. Операція композицій відношень дозволяє ввести поняття степеня бінарного відношення, що задане на одній множині.

20.Властивості композиції відношень

Композиція відношень має наступні властивості: 1) не є комутативною: А₀ВВ₀А; 2)асоціативна: А₀(В₀С)=(А₀В)₀С=А₀В₀С; 3) (В₀А)^-1=А^-1₀В^-1; 4) підняття відношень у степінь. Матриця композиції відношення С=В₀А утворюється, як добуток матриць відношень В і А з подальшою заміною відмінних від 0 на 1. Щоб побудувати граф, потрібно до графа відношення А побудувати граф відношення В і вилучити вершини, що відповідають елементам множини У. При вилученні вершини у кожен шлях, що проходить через неї від вершин множини Х до вершин множини Z замінюється однією дугою з тим самим напрямком.

21.Властивості відношень

Кожне бінарне відношення на множині Х може мати одну або кілька властивостей. Ці властивості визначають вид матриці і граф відношення. Відношення антирефлексивне, якщо ЕА Ǿ; симетричне, якщо А=А^-1; транзитивне, якщо А₀АА; асиметричне, якщо АА^-1= Ǿ; антисиметричне, якщо АА^-1=Е. Відношення рефлексивне, якщо ЕА, Е – тотожне відношення.

22.Особливості матриць відношень, які мають різні властивості (рефлективність, симетричність, транзитивність, антирефлексивність).

Рефлективність- на головній діагоналі всі 1; Симетричність-Матриця симетрична по-відношенню головної діагоналі; Антирефлексивність-на головній діагоналі нулі; Анти симетричність-Не має симетрично розташованих-одиниць; Транзитивність- якщо в матриці є елемент x(i,j) та x(j,k), то має бути й x(i,k).

Cv

23.Особливості графів відношень, які мають різні властивості (рефлективність, симетричність, транзитивність, антирефлексивність).

Рефлективність- Містить петлів усіх вершинах; Симетричність-Для кожної дуги, що з’єднує дві вершини є також дуга, що з’єднує ці вершини в зворотньому напрямку; Антирефлексивність-Не має жодної петлі; Анти симетричність- всі вершини пов’язані дугами, можуть бути петлі; Транзитивність-Якщо вершина a прямує до b, пов’язані дугою, де c прямує до b , то існує дуга, де a прямує до с.

24.Поняття функціонального відношення

Відношення F XxY є функціональним, якщо всі його елементи (упорядковані пари) мають різні перші координати: кожному xX або відповідає тільки один елемент yY, такий, що хRy, або такого елемента у взагалі не існує. Матриця функціональног відношення, щл задане на скінченних множинах Х і У, містить не більше однієї одиниці в кожному рядку. Якщо функціональне відношення задано у вигляді графа, то з кожної вершини, що зображує першу координату, виходить не більше однієї дуги.

25.Багатомістним відношенням (N-містним) є відношення {(x1,x2,x3…xn)/( x1,x2,x3…xn)  x1·x2·…·xn}, яке назив. кортежем, або впрорядкованною n-кою

26.Поняття функції та відображень.

В будь-якому функціональному відношенні перша координата є унікальною для кожної пари. Перша координата – прообраз, аргумент, змінна. Друга координата – значення, образ. Якщо функціональне відношення f  XxY є всюди визначеним на х, то воно називається відображенням множини Х в множину Y Х→Y. При відображені один елемент Х має 1 і тільки 1 образ.