Студопедия

КАТЕГОРИИ:

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



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

Читайте также:
  1. Алгебра
  2. Алгебра асинхронных процессов. Одноместные и многоместные операции.
  3. Алгебра изображений
  4. Алгебра кортежей. Голова, префикс, подпоследовательность кортежа.
  5. Алгебра логіки
  6. Алгебра множеств.
  7. Алгебра событий.
  8. Алгебра событий.
  9. Алгебра событий. Пространство элементарных событий.

Пусть заданы отношения 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; просмотров: 9; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Подпоследовательность. | Задача минимизации функций алгебры логики. Теоремы Квайна и Мак-Класски.
lektsii.com - Лекции.Ком - 2014-2019 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты