дискр

Бінарні відношення
Б. в. х є відношенням не
строгого порядку.
Якщо воно: 1 Рефлексивне;
2Транзитивне3Антисиметричне.
Мн. На якій задане таке в.
Назив.частково впорядкованим:
1 асиметричне; 2 транзетивне.
Мн. На якій задане в. строгого
Порядку назив. Лінійно впоряди.
Якщо функціональне в. є всюди
Визначеним на х то його назив.
Відображенням мн. Х, мн.у
F c x*y : x-y ; Dc(f)=x Перша
Координата будь-якої упоряд.
Пари кожного функт. В. є праобразом.
Якщо будь-який ел. З мн. У є
Образом принаймні одного ел.
Х, то кажуть що мн. Х відображу.
На мн. У. Сюр’єкція:
В графі сюр. В. з будь-якою
Вершиною з мн. Х виходить
100% одна дуга, а з вершини
У заходить не менше однієї
Дуги. Якщо для будь-яких
Двох різних ел. Х1 та х2 їх
Образи також різні, то відоб.
Назив. Ін’єкцією. Або взаємно-
Однозначне відображення. На
Графі з будь-якої вершини мн.
Х виходить точно одна дуга, а
До будь-якої мн. У заходить
Не більше однієї дуги.
Відображення яке є одночасно
Є інєктивним і сюрєктивним
Назив. Бієкцією.Якщо перша
Ф
·-я є відображення «х» до
«у», а «у» до «х».
F:x-y;q0f:x-z;q:y-z;-(q(f(x))).
Ф-я f є взаємно однозначним
Функціональним в. тоді і
Тільки тоді, коли f-1 теж
Взаємно функціональне в.
Замикальним в. f за власт.
Q назив. в. f яке має в.
Найменше в. означає, що С є
Підмножиною певного в. S для
Якого виконують умову: R c S;
S має властивості q.
Шляхом в. R від ел. А до ел. В
Назив. Послідовність ел. Для
Яких А є х1, х2, хn,, В є його ел.
Процедура пошуку транзетивн.
Замикання еквівалентна процед.
Визначення того яка пара вершин
З’єднана шляхом. Шлях мн.А до В
Існує в. R тільки тоді якщо пара АВ
Належить Rn. Алгоритми будови
Транзитивного замикання(Маршала).
1 R1=R0R;2 R2=RvR. якщо R2=R тоді R2
Шукана матриція то R2
·R-R:R2 і
Повертаємося до першого алгоритму.
Розглянемо всі поза діагональні ел.
Матриці.Якщо Zij
·0 то замінюємо
І-тий рядок дизюнцією.
15

Приложенные файлы

  • doc 15536426
    Размер файла: 29 kB Загрузок: 0

Добавить комментарий