загрузка...
загрузка...
На головну

Розбиття і покриття безлічі

ставлення еквівалентності

Бінарне відношення, що володіє властивостями рефлексивність, симетричність, транзитивність називається ставленням еквівалентності (позначається ~).

r = {(x, y) | x = y, x, y I N},

r = {(x, y) | x = y (mod m), x, y I N}.

На безлічі людей: "мати одне ім'я", "навчатися в одній студентській групі".

На безлічі множин: "A = B".

покриттям непорожньої безлічі називається сукупність підмножин таких, що:

розбиттям непорожньої безлічі називається сукупність підмножин таких, що:

клас еквівалентності для х: [x] = { yI Х | x ~ y}.

наприклад:

Відносини r і g задані на множині Х = {1, 2, 3, 4, 5, 6,}.

r = {(1,4), (2,5), (3,6), (4,1), (6,3)},

g = {(1,1), (2,3), (3,4), (4,5), (5,6), (6,6)}.

Область визначення Dr= {1, 2, 3, 4, 6}.

Область значень J r= {1, 3, 4, 5, 6}.

Зворотне відношення r-1={(4,1), (5,2), (6,3), (1,4), (3,6)}.

ставлення r- антирефлексивне, що не симетрично, не транзитивній.

Область визначення Dg= {1, 2, 3, 4, 5, 6}.

Область значень J g= {1, 3, 4, 5, 6}.

ставлення g- НЕ рефлексивно, антисиметрично, не транзитивній.

Композиція r 0 g={(1,5), (2,6), (3,6), (4,1), (6,4)}.

наприклад:

Ставлення r = {(x, y) | порівняння по модулю m, x, y I N}.

Ставлення порівняння по модулю m на безлічі натуральних чисел: x = y mod m, що означає: "x і y мають однаковий залишок при діленні на m (класи лишків за модулем m)".

Відрізок натурального ряду N4= {1,2,3,4}

Ставлення порівняння по модулю 2 на N4:

d = {(1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4) }.

Область визначення Dd = {1, 2, 3, 4}.

Область значень J d = {1, 2, 3, 4}.

Ставлення d - рефлексивно, симетрично, транзитивно.

Ставлення d - відношення еквівалентності.

Класи еквівалентності: [1] = {1,3} = [3]

[2] = {2,4} = [4].

наприклад:

Відносини j і n задані на безлічі N4.

j = {(1,2), (2,3), (1,3), (3,4), (2,4), (1,4)}

n = {(1,1), (2,2), (3,3), (4,4)}.

Область визначення Dj = {1, 2, 3}.

Область значень J j = {2, 3, 4}.

Ставлення j - антирефлексивне, антисиметрично, транзитивно.

Ставлення j - відношення строгого порядку.

Область визначення Dn = {1, 2, 3, 4}.

Область значень J n = {1, 2, 3, 4}.

Ставлення n - рефлексивно, симетрично, антисиметрично, транзитивно.

Ставлення n - відношення несуворого часткового порядку.

Ставлення n - відношення еквівалентності.

Класи еквівалентності: [1] = {1}

[2] = {2}

[3] = {3}

[4] = {4}.

Властивості бінарних відносин «-- попередня | наступна --» Комбінаторна формулювання правила твори
загрузка...
© om.net.ua