Властивості бінарних відношень

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

Рефлексивність. Бінарне відношення R називається рефлексивним, якщо справедливо . Очевидно, що в цьому разі також . Таким чином, рефлексивне відношення виконується для однакових елементів, тобто Введемо предикат від бінарного відношення, який істинний тоді і лише тоді, коли R – рефлексивне.

Антирефлексивність. Ця властивість є протилежною до рефлексивності. Відношення R називається антирефлексивним, якщо жодний елемент не знаходиться в цьому відношенні сам із собою, тобто . Через операцію перетину це можна записати як , а через включення – як Також подібно до попередньої властивості введемо предикат антирефлексивності .

Симетричність. Відношення R є симетричним, якщо разом із кожною впорядкованою парою, що належить відношенню, воно містить і пару із переставленими компонентами, тобто . Інакше це можна виразити як . Відповідний предикат будемо позначати . Легко показати, що .

Асиметричність. Для асиметричного відношення R виконується , тобто щонайбільше одна пара з та належить такому відношенню. Через операцію перетину це можна записати як . Предикат асиметричності позначатимемо .

Антисиметричність. Відношення R називається антисиметричним, якщо , тобто такому відношенню належать щонайбільше одна пара із різними компонентами з та , та, можливо, пари однакових елементів. За допомогою операцій над відношеннями це можна записати як . Предикат антисиметричності отримує позначення .

Відношення називається симетричною частиною вихідного відношення R, якщо . Це симетричне відношення .

Відношення називається асиметричною частиною вихідного відношення R, якщо . Можна легко показати, що , тобто

.
Відмітимо, що це означає, що та . в загальному випадку асиметричне відношення.

Транзитивність. Відношення R буде транзитивним, якщо кожний направлений шлях довжиною 2 в його графі замикається дугою, тобто . Можна легко показати, що в графі транзитивного відношення дугою замикається направлений шлях будь-якої довжини, тобто

.

Для транзитивного відношення виконується

,
тобто нижній переріз кожного елементу множини є максимальним за включенням серед нижніх перерізів елементів, яких він містить. Через операцію включення властивість транзитивності можна записати як . Предикат транзитивності – це .

Лема 1.2. Для того, щоб R було транзитивним відношенням (щоб виконувалось ) необхідно і достатньо справедливості .

Доведення. ⇒ Доведемо за індукцією включення .

База: n = 2. виконується за .

Припущення: виконується для деякого .

Перехід: , і включення доведено .

За означенням транзитивного замикання

,
тобто . Але зворотне включення також тривіально виконується, тобто і необхідність доведена.

⇐ З означення транзитивного замикання очевидно . Оскільки , то , тобто – достатність доведена.

Доведено.

Від’ємна транзитивність. Відношення R називається від’ємно транзитивним, якщо транзитивним є його доповнення , тобто якщо . Для від’ємної транзитивності введемо предикат .

Лема 1.3. Для необхідно і достатньо справедливості твердження

.

Доведення. ⇒ Нехай , тобто при виконується та . Але з . Отримали протиріччя, яке доводить необхідність.

⇐ Нехай , тобто при та виконується . Але, поклавши в , маємо . Кожний з цих варіантів протирічить вихідному припущенню, і таким чином достатність твердження для від’ємної транзитивності також доведена.

Доведено.

Зв’язність. Відношення R називається зв’язним, якщо виконується . Предикат, введений для властивості зв’язності, позначається . Інша назва цієї властивості – лінійність. Зрозуміло, що зв’язне відношення обов’язково має бути рефлексивним. Граф зв’язного відношення містить єдину компоненту зв’язності та петлі у кожній вершині.

Слабка зв’язність. Будемо називати бінарне відношення R слабкозв’язним (відповідний предикат - ), якщо . Граф такого відношення, подібно до зв’язного, містить єдину компоненту зв’язності. Слабкозв’язне відношення не обов’язково має бути рефлексивним, тобто його граф може мати вершини, у яких відсутні петлі.

Не будь-який зв’язний граф відповідає слабкозв’язному відношенню, прикладом чому може слугувати дерево.

Теорема 1.1 (про взаємозв’язок властивостей бінарних відношень).

Мають місце наступні залежності між властивостями деякого бінарного відношення :

1) ; 2) ; 3) ;

4) ; 5) ; 6) .

Доведення.

1) Нехай , тоді . Припустимо, що , тобто , тоді

2) Нехай . Якщо при цьому , то , тобто граф відношення R містить цикл довжини 2. Якщо ж виконується лише коли , то граф відношення містить петлю. Обидва ці випадки протирічать .

3) Нехай для деяких . За для виконується . За , тобто можливий лише випадок . Отримали , звідки .

4) Нехай , але всупереч для деяких . Через те, що , та . Тобто , , що протирічить .

5) Нехай , але , тобто . За , що неможливо через .

6) Нехай знову , але всупереч

,

тоді за , чого не може бути згідно з .

Доведено.

Для теореми 1.1 можна навести ряд наслідків, наприклад:

· ;

· .

Відомості про взаємозв’язок властивостей бінарних відношень зручно представляти в табличному вигляді, рядок якої відповідає одному такому твердженню, стовпчик – окремій властивості. У комірці таблиці ставляться символи: ×, якщо антецедент твердження вимагає виконання відповідної властивості, та , який відмічає консеквент твердження. Викладені вище відомості зведені у табл. 1.1.

Таблиця 1.1. –Відомості про взаємозв’язок властивостей бінарних відношень
№
	⇒	×
		⇒				×
		×	⇒	×
				⇒	×	×
	×	⇒	×
	×		×			⇒
Н1	×		×	⇒	×
Н2			⇒		×	×

Розглянемо питання про інваріантність деяких властивостей бінарних відношень відносно операцій над ними. Наведемо відповідну теорему.

Теорема 1.2 (про інваріантність властивостей відношень відносно операцій між ними).

Для заданих бінарних відношень , та будь-якого справедливі наступні твердження:

1) якщо , то , , , , ;

2) якщо , то , , ;

3) якщо , то , , , ;

4) якщо , то , ;

5) якщо , то та ;

6) якщо , то , , .

Доведення.

1) , . З властивостей включення множин

,

.
З тривіальним чином випливає . Доведемо . З означення композиції відношень . В якості z також можна взяти елемент x. Тепер, беручи до уваги те, що , вже доведене , та поклавши маємо

.

2) Оскільки , то за властивістю операції включення та . Далі, з випливає . За лемою 1.1 отримаємо

.

3) , . Тоді за

,

.

Подібним чином з інволютивності обернення . З

.

За індукцією . Знову використавши отримаємо

.

4) Відомо, що . . За лемою 1.1 маємо . Також тобто

.

Тепер нехай для деяких . Це зокрема означає, що . Оскільки , має місце

.

Візьмемо , використавши правило де Моргана отримаємо

.

Звідси .

5) , . Тоді

,

отже Подібним чином

,

і .

6) Нехай справедливі співвідношення та для деяких . Тоді також вірні , , , . За отримаємо , ідоведено. Якщо справджується та для деяких , то за визначенням оберненого відношення маємо та . За отримаємо що доводить . Далі, за лемою 1.2. Тоді , звідки .

Доведено.

Дата добавления: 2013-12-14