Транзитивность матрицы: 2.3. Транзитивность и транзитивное замыкание бинарного отношения

Содержание

2.3. Транзитивность и транзитивное замыкание бинарного отношения

Определение 2.6. Бинарное отношение называюттранзитивным бинарным отношением, если для любых ,ииз того, чтои, вытекает, что.

Символически определение 2.6 записано формулой (2.7).

.

(2.7)

Другими словами, отношение транзитивно, если оно покрывает все опосредованные связи между элементами. Отсюда вытекает, чтоусловием транзитивности отношения является выполнение условия

(2.8)

Используя матрицы отношений, условие (2.8) можно переписать так:

.

(2.9)

Пример.

На множестве ={a,b,c} задано отношение :

.

Покажем, что не является транзитивным отношением.

,

инесравнимы между собой, следовательно, не транзитивно.

Найдем более высокие степени отношения , т.е. матрицы отношений,,,…,:

,

,

,

.

Легко проверить, что …=.

Определение 2.7. Транзитивным замыканием бинарного отношения называют объединение степеней этого бинарного отношения:

.

(2. 10)

Транзитивное замыкание отношения в рассмотренном примере имеет вид.

Пусть на множестве отношениезадано графом (рис.2.4). Запишем матрицуэтого отношения и найдем его транзитивное замыкание.

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

Для нахождения транзитивного замыкания будем умножать матрицу на себя, получая,,…,, до тех пор, пока не выполнится равенство. Дальнейшее умножение не будет приводить к изменению матриц.

==.

Любой элемент матрицы не превосходит соответствующий элемент матрицы, т.е.. Это означает, чтовключает все опосредованные связи между элементами, следовательно,является транзитивным бинарным отношением. Покажем, что его транзитивное замыкание совпадает с самим.

==.

Умножение нуль-матрицы на любую другую матрицу есть нуль-матрица. Поэтому для любых.

Транзитивное замыкание отношения найдем, используя формулу (2. 10) и матрицыи:

.

Как и следовало ожидать, поскольку отношение является транзитивным отношением, оно совпадает со своим транзитивным замыканием.

Справедливы следующие утверждения.

Утверждение 1. Транзитивное бинарное отношение совпадает со своим транзитивным замыканием.

Утверждение 2. Транзитивное замыкание бинарного отношения есть наименьшее по числу элементов транзитивное отношение, содержащее данное бинарное отношение.

Утверждение 3. Транзитивное замыкание есть ближайшее к транзитивное отношение.

Использование термина «ближайшее отношение» предполагает, что между отношениями определено расстояние. Для определения

расстояния между множествами используют формулу линейного расстояния (формула 2.11), или формулу евклидова расстояния (формула 2.12).

,

(2. 11)

,

(2.12)

где – расстояние между подмножествамииуниверсального множества,ихарактеристические функции этих подмножеств. Суммирование выполняется по всем элементам универсального множества.

Для бинарного отношения, заданного на множестве , универсальным множеством является множество. Если, тоназывают

полным отношением. Очевидно, что все элементы матрицы полного отношения есть единицы: , где- число элементов множества. Формулы (2.11) и (2.12) для бинарных отношений имеют следующий вид:

,

(2.13)

,

(2.14)

где – число элементов универсального множества,,.

Не следует думать, что последовательность степеней матрицы отношения всегда имеет предел, т. е., начиная с некоторого шага , выполняется равенство. Приведем простой пример, показывающий, что это не так.

Пусть матрица отношения на множествеимеет вид.

Тогда

, ,,….,,

для любого .

Тем не менее .

Решение задач по высшей математике, линейной алгебре, математическому анализу, теории вероятностей, статистике, эконометрике

Математика — это язык, на котором написана книга природы.
РЕШЕНИЕ ЗАДАЧ, КОНТРОЛЬНЫХ РАБОТ ПО ВЫСШЕЙ МАТЕМАТИКЕ
&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp &nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Галилео Галилей

Главная

Оплата

Примеры

Учебники

Условия:

Даны два конечных множества: А={a,b,c}, B={1,2,3,4}; бинарные отношения PÍ A´ B, PÍ B2. Изобразить P1, P2 графически. Найти P = (P2◦P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P= {(b,1),(b,4),(a,3),(a,4),(c,4),(c,2)}; P= {(1,1),(2,4),(2,3),(2,2),(3,3),(3,4),(4,2),(4,4)}.

 

Решение:

 

Произведением  отношений  и  называется отношение .

Запишем  в виде пар.

.

.

.

.

.

.

.

.

.

.

.

.

Убрав одинаковые пары, получим

.

Обратное отношение

.

 

Областью определения отношения  называется множество

.

 

Областью значений называется множество:

 .

. .       

.   .

. .

 

Матрица отношения :

 .

Бинарное отношение  на называется рефлексивным, если

.

 

На главной диагонали матрицы такого отношения стоят единицы.

Отношение  рефлексивно.

 

Отношение называется симметричным, если

, т. е.  или .

 

Матрица симметричного отношения симметрична.

Отношение  не симметрично.

 

Отношение называется антисимметричным, если

, т. е. в матрице  

 

вне главной диагонали все элементы равны нулю.

Отношение  не является антисимметричным.

 

Отношение называется транзитивным, если

, т. е. .


Отношение  транзитивно.

 

Copyright © 2008 email: [email protected]

матриц — Как проверить, является ли отношение транзитивным от матричного представления?

Это ответ на ваш второй вопрос об отношении $R=\{\langle 1,2\rangle,\langle 2,2\rangle,\langle 3,2\rangle\}$. Мы можем проверить транзитивность несколькими способами.

(1) Список всех связанных пар:

$$\begin{align*} &\langle 1,2\rangle\land\langle 2,2\rangle\tag{1}\\ &\langle 2,2\rangle\land\langle 2,2\rangle\tag{2}\\ &\langle 3,2\rangle\land\langle 2,2\rangle\tag{3} \end{выравнивание*}$$

Если $R$ должен быть транзитивным, $(1)$ требует, чтобы $\langle 1,2\rangle$ было в $R$, $(2)$ требует, чтобы $\langle 2,2\rangle$ было в $R$, а $(3)$ требует, чтобы $\langle 3,2\rangle$ находилось в $R$. А поскольку все эти требуемые пары равны в $R$, $R$ действительно транзитивно.

(2) Проверить все возможные пары конечных точек. Например, чтобы увидеть, требуется ли $\langle 1,3\rangle$ для того, чтобы $R$ был транзитивным, посмотрите, существует ли «ступенька» от $1$ к $3$: существует ли $a$ такие, что $\langle 1,a\rangle$ и $\langle a,3\rangle$ принадлежат $R$? Если это так, транзитивность потребует, чтобы $\langle 1,3\rangle$ также лежало в $R$. Как оказалось, такого $a$ не существует, поэтому транзитивность $R$ не требует, чтобы $\langle 1,3\rangle$ было в $R$. Выполните эту проверку для каждой из девяти упорядоченных пар в $\{1,2,3\}\times\{1,2,3\}$. 92=\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix}\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix}=\begin{bmatrix}0&1&0\\0&1&0\\0&1&0\ end{bmatrix}$$

подсчитывает количество путей с шагом $2$ между элементами $\{1,2,3\}$. Запись в строке $i$, столбце $j$ — это количество путей из $i$ в $j$, состоящих из $2$ шагов. (Под двухшаговым путем я имею в виду что-то вроде $\langle 3,2\rangle\land\langle 2,2\rangle$: первая пара ведет от $3$ до $2$, вторая — от $2$ до $2$. $2$, а вместе вы получите от $3$ до $2$.) 92=\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}\begin{bmatrix}1&0&1\\0&1&0\\1&0&1\end{bmatrix}=\begin{bmatrix}2&0&2\\0&1&0\\2&0&2\ end{bmatrix}\;.$$

$2$ указывают на то, что существует два $2$-шаговых пути из $1$ в $1$, из $1$ в $3$, из $3$ в $1$ и из $3 $ до $3$; существует только один $2$-шаговый путь из $2$ в $2$. Например, от $1$ до $1$ у вас есть как $\langle 1,1\rangle\land\langle 1,1\rangle$, так и $\langle 1,3\rangle\land\langle 3,1\rangle$ . 2$ показывает хотя бы один двухшаговый путь, $M_R$ показывает, что одношаговый путь уже существует, и поэтому $R$ транзитивен. 92$. Если $M_R$ уже имеет $1$ в каждой из этих позиций, $R$ является транзитивным; если нет, то нет.

Сходимость степеней нечеткой транзитивной матрицы

  • title={Сходимость степеней нечеткой транзитивной матрицы}, автор={Хироши Хашимото}, journal={Нечеткие множества и системы}, год = {1983}, громкость = {9}, страницы = {153-160} }
    • H. hashimoto
    • Опубликовано 1983
    • Компьютерная наука
    • Нечеткие наборы и системы

    View Via Publisher

    Конвергенция продуктов Fuzzy Matrices

    • S. Guu, HSING-HSING-HSIA, CHIN-TZONG
      • S. GUU, HSING-HSING-HSIA, CHINGONG
      • S. Guu, HSING-HSIN Информатика, Математика

        Сист. нечетких множеств.

      • 2001

      Период степеней нечеткой матрицы

      • Х. Имаи, Юичи Окахара, М. Миякоши
      • Информатика

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

      • 2000

      Сходимость макс-средних арифметических степеней нечеткой матрицы

      • Юнг-Йих Лур, Ян-Куэн Ву, С. Гуу
      • Информатика

        3

        3 Информатика.

      • 2007

      О транзитивности обобщенных нечетких матриц

      • И-цзя Тан
      • Математика, информатика

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

      • 2013

      Сходимость степеней s-транзитивных нечетких матриц

      • W. Kołodziejczyk
      • Computer Science

      • 1988

      On Infinite Products of Fuzzy Matrices

      • S. Guu, Yung-Yih Lur, Chin-Tzong Pang
      • Mathematics, Computer Science

        SIAM Дж. Матричный анал. заявл.

      • 2001

      Показано, что слабая сходимость бесконечных произведений конечного числа нечетких матриц эквивалентна слабым сходимостям бесконечных произведений конечного числа ассоциированных булевых матриц.

      Периодичность степеней нечетких матриц (конечные нечеткие отношения)

      • Ли Цзянь-Синь
      • Информатика

      • 1992

      средние операции

      • Yung-Yih Lur, Yan-Kuen Wu, S. Guu
      • Информатика

        Инф. науч.

      • 2009

      Мультипликативный функционал на верхнетреугольных нечетких матрицах

      • Лю Пин
      • Информатика, Математика

      • 2015

      Доказано, что существуют мультипликативный функционал F и функционал G из нечеткой алгебры в нечеткую геометрию такие, что образ нечеткой верхней матрицы треугольный под f может быть представлен как произведение всех образов его элементов главной диагонали под F и других элементов под G.0061

      • В. Колодзейчик
      • Информатика

      • 1990

      Показано, что существуют решения с различными известными типами нечеткой транзитивности, а максимальное решение имеет особый новый тип так называемой α- показано транзитивность и интересное свойство сходимости натуральных степеней максимального решения.

      ПОКАЗАНЫ 1-10 ИЗ 11 ССЫЛОК

      СОРТИРОВАТЬ ПОРелевантности Наиболее влиятельные документыНедавность

      Сходимость степеней нечеткой матрицы

      • M. Thomason
      • Computer Science

      • 1977

      STRUCTURE OF FUZZY BINARY RELATIONS

      • S. Ovchinnikov
      • Computer Science

      • 1981

      Similarity relations and fuzzy orderings

      • L Заде
      • Информатика

        Инф. науч.

      • 1971

      Классификация образов на основе нечетких отношений

      Описан метод классификации образов с использованием нечетких отношений, в котором сходство между любыми двумя образами вычисляется путем использования композиции нечеткого отношения для индуцирования отношения эквивалентности.

      Графы и сети

      привлекательно, использование алгебры путей. Здесь матрица инцидентности графа состоит из элементов из подходящей алгебры, а система уравнений решается методами, аналогичными используемым в линейных…

      Нечеткая модель поисковых систем документов

      Введение в теорию нечетких подмножеств.

      • C. Proctor, A. Kaufman, D. Swanson
      • Информатика

      • 1977

      Применение графов и булевых матриц в компьютерном программировании

      • Р. Маримон
      • Информатика

      • 1960

      Рассмотрены элементарные свойства ориентированных графов и булевых матриц, показано, как их использование в других областях может быть связано с программированием, а также некоторые проблемы которые должны быть решены, прежде чем компьютерное программирование может быть полностью механизировано.

      О графиках и асимптотиках матриц конечных булевых отношений и стохастических матриц

      • D. Rosenblatt
      • Математика

      • 1957

      на графах конечных идаптотентов. Характеристика идемпотентных матриц булевых отношений конечного порядка и формальные результаты приведены на примере исследования асимптотических форм рекурсивной модели информационной системы, которая обеспечивает совместное представление процессов передачи и получения информации.

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *