Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Алгебра отношений.




Пусть заданы отношения R Í M x M и S Í M x M.

1. R È S = { (x, y): x, y Î M & ( (x, y) Î R v (x, y) Î S ) }

x (R È S) y => xRy v xSy

2. R Ç S = { (x, y): x, y Î M & ( (x, y) Î R & (x, y) Î S ) }

x (R Ç S) y => xRy & xSy

3. Обратное отношение: R-1 = { (y, x): x, y Î M & (x, y) Î R }

4. R · S = { (x, y): x, y Î M & $z Î M [ xRz & zSy ] }

5. Транзитивное замыкание:

6. Рефлексивное замыкание:
17. Свойства отношений. Эквивалентность и классы эквивалентности по заданному отношению.

Свойства порождаются выполнением неких абстрактных ограничений. © Красюк. Это справедливо не только для данного билета. ;)

 

1. Рефлексивность. "x Î M [ (x, x) Î R ]

2. Антирефлексивность. не$x Î M [ (x, x)ÎR ]

3. Симметричность. "x, y Î M [ (x, y) Î R => (y, x) Î R ]

4. Антисимметрич-ть. "x, y Î M [ (x, y) Î R & (y, x) Î R => x = y ]

5. Иррефлексивность. $x Î M [ (x, x) Î R ] & $y Î M [(y, y) Ï R ]

6. Транзитивность. "x, y, z Î M [ (x, y) Î R & (y, z) Î R => (x, z) Î R ]

 

– транзитивное замыкание б.о. R.

– рефлексивное замыкание б.о. R.

 

Ахтунг! Различие асимметричности и антисимметричности:

R Ç R-1 = Æ для асимметричного R

R Ç R-1 = IM для антисимметричного R

 

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

Далее символом X обозначается множество, на котором задано отношение эквивалентности R.

Каждое подмножество A из X называется классом эквивалентности, если:

1) оно состоит из эквивалентных друг другу элементов и

2) если эквивалентен хотя бы одному элементу из , то .

 

(Пример: x, yÎN (x=y)mod 7. d1: (x)mod 7=0. X1={0,7,14,...}. d2: (x)mod 7=1. X2={1,8,15,...}. X1 и X2 – классы эквивалентности, т.к. отношение (x=y)mod 7 явл. отношением эквивалентности.)

 

Система классов эквивалентности (например, система множеств X1,X2,... из предыдущего примера) называется фактор-множеством.

 

Теорема. Два класса эквивалентности либо совпадают, либо не пересекаются.

Доказательство. Пусть A и B – два класса эквивалентности из X. Допустим, что они пересекаются и c – общий элемент, то есть . Если x – произвольный элемент из A, то x~c. Поскольку , то и . Таким образом, . Аналогично доказывается, что . Итак, A = B. Теорема доказана.



Поделиться:

Дата добавления: 2015-04-05; просмотров: 90; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты