double arrow

Список літератури. 1. Новиков Ф.А. Дискретная математика для программистов


Основна

1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.33-38.

2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. с.35-46.

3. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. – К.:Наук. думка, 1989. - С.35-50.

4. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.97-115.

Додаткова

5. Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. - С.62, 63.

6. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. - С.39-42.

Для практичних занять

7. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.13-14.


Лекція 6. Спеціальні операції над відношеннями

Вступ

Лекція має за мету висвітлити поняття спеціальних операцій для n-арних відношень. Розглянуті операції перестановки і ототожнення координат, приписування фіктивної координати, згортки де Моргана і суперпозиції. Звернено повагу на спеціальні часткові випадки перестановки – цикл, транспозицію, зворотну перестановку, поняття діагоналі, властивості згортки де Моргана, узагальнення між операціями композиції, згортки де Моргана і суперпозиції, що часто використовуються.

У лекції присутні два підрозділи:

6.1. Перестановка, ототожнення, приписування фіктивної координати

6.2. Згортка де Моргана, суперпозиція

6.1. Перестановка, ототожнення, приписування фіктивної координати

Крім множинних операцій, у теорії n-відношень використовуються спеціальні операції перестановки й ототожнення координат (стовпців), приписування фіктивної координати, а також згортки де-Моргана. Нехай rn – відношення на множинах А1, А2, … , Аn, k=(1, 2, …, n) – набір координат (номерів) стовпців у матриці графіка rn1, … , An, k¢=(і1, і2, … , in) – набір, отриманий з k у результаті деякої перестановки елементів.

Визначення. Операція hк’(rn) перестановки координат породжує ставлення n-відношення gn на множинах Аi1, Ai2, …, Ain, графік якого gnAi, … , Ain виходить із графіка rn1,…,An, перестановкою його стовпців відповідно до набору k¢.

Визначення. Нехай k0=(2, 3, …, n, 1). Перестановка hk0(rn) називається циклом і позначається x(rn).

Визначення. Нехай k1=(2, 1, 3, … , n). Перестановка hk1(rn) називається транспозицією і позначається t(rn).

За допомогою циклу n транспозиції можна виразити будь-яку перестановку h(rn).

Нехай`k=(n, n-1, …, 2, 1).

Визначення. Відношення (rn)-1=h`k(rn) над множинами An, An-1,…, A2, A1, отримане з відношення rn у результаті перестановки, що відповідає набору`k називається оберненим.

Очевидно, a=(an, an-1, …, a2, a1)Î(rn)-1An, …, A1, тоді і тільки тоді, коли
a-1=(a1, a2,,…, an)Îrn1, An

Приклад. Для бінарних відношень <, >, £, ³ справедливо
<---1=>, >--1=<, £--1=³,³--1=£ (Операція перестановки).

Операція перестановки для бінарних відношень є інверсією.

Для обернання n-відношень виконуються рівності (при rnÍsn):

1. ((rn)-1)-1=rn

2. (rn)-1Í(sn)-1

3. (Çrin)-1=Ç(rin)-1

4. (Èrin)-1=È(rin)-1

5. (`rn)-1=ù((rn)-1)

З рівностей випливає, що для Ф-1(r1n, r2n,..., rkn)=F((r1n)-1, (r2n)-1,..., (rkn)-1),
де Ф – формула, побудована з відношень r1n, ..., rkn за допомогою операцій È, Ç, ù. Крім того, справедлива рівність

6. (rn´sm)-1 = (sm)-1´(rn)-1.

Нехай rn – відношення на множинах А1, …, Аn і {j1, j2, …, jl} - деяка підмножина множини номерів {1, 2, …, n}.

Визначення. Операція ототожнення координат d(rn) породжує відношення q n-l+l= dj1,j2 . , jl(rn) на множинах A1,…, Aj2-1, Aj2+1, …, Aj3-1, Aj3+1, …, Ajl-1, Ajl+1, …, An, графік якого виходить із графіка rn1,…An
у результаті виділення множини векторів {a=(а1і, a2i, …, ani)| aj1i=aj2i=…=ajl i}Írn1,…, An з наступним викреслюванням у кожнім векторі a елементів aj2i, aj3i, …, ajl i.

Тобто у відношенні rn виділяються усі вектори, в яких збігаються компоненти, розташовані в стовпцях з координатами j1, …, ji, з наступним виключенням стовпців-копій, що мають координати j2, j3, …, ji.

Приклад. Для відношення g5А1,А2,А3,А4,А5 з попереднього приклада d24(g5)=q 4, де q 4:

q 4А1,А2,А1,А3= 0, a, 0, b

1, b, 1, c

1, b, 1, d

Для відношення q 4 d13(q 4)=x3, де x3:

x3А1,А2,А3 = 0, a, b

1, b, c

1, b, d

Якщо l=2, j1=1, j2=2, то ототожнення d12(rn) позначається d(rn). За допомогою d(rn) і перестановки координат можна зробити будь-яке ототожнення координат.

Визначення. Відношення dn на множині А називається діагоналлю, якщо для будь-якого аÎA виконується (a, …, a)Îdn.

Приклад. Бінарне відношення рівності на множині N - діагональ. Якщо d1,2,…n(rn)- відношення на множини А, то d1,2,…n(rn)Ídn. Крім того, для будь-якого відношення rnÍdn виконується (rn)—1=rn.

Визначення. Операція приписування фіктивної координати "(rn) породжує відношення qn+1="(rn) над множинами A, A1, A2, ..., An таке, що при справедливості rn1 j, a2 j, ..., an j) виконується
q n+1(a, a1 j, a2 j, ..., an j) для будь-якого аÎA.

Операція приписування відношенню rn фіктивної координати по множині А полягає в утворенні відношення qn+1="(rn) із графіком, одержуваним таким чином: для кожного вектора a=(a1i, a2i, …, ani)Îrn1,…,An будуються вектори (а, а1і, a2i, …, ani)Î qn+1A,A1,…,An, отримані приписуванням до вектора a ліворуч по черзі всіх елементів множини А.

Приклад. Для a3 на множини А={0,1} із графіком

a3А= 1, 0, 0

0, 1, 0

0, 0, 1

у результаті приписування фіктивної (на множині А) координати

a4А= 0, 1, 0, 0

0, 0, 1, 0

0, 0, 0, 1

1, 1, 0, 0

1, 0, 1, 0

1, 0, 0, 1

Операція ", зокрема, вирівнює арності у відношеннях.

6.2. Згортка де Моргана, суперпозиція

Одна з важливих операцій над відношеннями – згортка де Моргана.

Нехай rn – відношення на множинах А1, А2, … , Аn-1, A, a sm відношення на множинах A, An, An+1, … , An+m-2.

Визначення. Операція згортки де Моргана для відношень rn і sm породжує відношення qn+m-2=rn*sm над множинами А1, А2, …, Аn+m-2, таке, що qn+m-2(a1і, a2і,…, ain+m-2j) виконується тоді і тільки тоді, коли знайдеться аÎA, для якого виконується rn(a1і, a2і, …, an-1і, a) і sm(a, anі, an+1і, …, an+m-2і).

Приклад. an1,…,An= 1, 2, … n

2, 3, … n+1

…............................................................

k-2n+2 k-2n+3 … k-n+1

gnAn, …, A1= n, n-1, … 1

n+1, n, … 2

….............................................................

k-n+1, k-n, … k-2n+2

q 2n-2A1,…,An-1,An+1,…A1=1, 2, … n-1, n-1 … 2, 1

2, 3, … n, n … 3 2

…........................................................................

k-2n+2, k-2n+3, … k-n, k-n, … k-2n+3, k-2n+2

Приклад. Графік згортки a*b бінарних відношень a і b на множинах А={a, b, c} і B={0, 1, 2}=C із графіками

aАВ= а, 0 bBC= 0, 1

b, 1 0, 2

c, 2 1, 2

2, 2

має вигляд (a*b)= a, 1

a, 2

b, 2

c, 2

Операція згортки не комутативна, але асоціативна.

1. rn*sm¹ sm*rn

2. (rn*sm)*q k= rn*(sm*q k)

Справедлива рівність

3. (rn*sm)-1=(sm)-1*(rn)-1

Нехай r - бінарне відношення на множинах А, В, s - бінарне відношення на множинах В, С. Згортка бінарних відношень r і s називається їхньою композицією.

Операція композиції бінарних відношень допускає й інші узагальнення на n-арний випадок.

Приклад. Нехай L1, L2, L3 – алгоритмічні мови, а p і p’ - відношення перекладу відповідно з L1 на L2 і з L2 на L3. Тоді композиція p²=p*p¢ відношень p і p’ також є відношенням перекладу з мови L1 на L3.

Нехай r1m – відношення на множинах А1,…,Аm-1, B1; r2m на множинах А1,…,Аm-1, B2;…;rn-1m – на множинах А1,…,Аm-1, Bn-1; sn – на множинах У1,…,Вn-1, Am.

Визначення. Суперпозицією відношень r1m,r2m,…,rn-1m,sn називається m-відношення qm=sn(r1m,r2m,…,rn-1m) на множинах А1,A2,…,Аm таке, що qm1і, a2і,…,ami) тоді і тільки тоді, коли знайдуться елементи b1jÎB1, b2j ÎB2,…,bn-1jÎBn-1, для яких rsm1і, a2і,…,am-1i,bsj при будь-якому s=1, 2,…,n-1, причому, sn(b1j, b2j, bn-1j, amі).

Приклад. r13 = 0, 1, 1 r23 = 0, 0, 0 r33 = 0, 0, 1 s 4= 0, 0, 0, 0

1, 0, 0 0, 1, 0 0, 1, 1 1, 0, 1, 1

1, 1, 1 1, 1, 1 1, 1, 0 1, 1, 0, 0

1, 1, 1 1, 1, 1, 1

q 3=s4(r13,r23,r33)= 0, 1, 1

1, 1, 0

1, 1, 1

Окремним випадком суперпозиції для двох відношень є згортка де-Моргана.

Контрольні запитання

1. Що є перестановкою для n-арних відношень і які окремі випадки перестановок існують?

2. Які властивості мають обернення n-арного відношення?

3. Як виконується ототожнення координат n-арного відношення?

4. Що є діагоналлю відношення і для яких відношень діагональ має існувати?

5. Яка операція дозволяє вирівнювати арність у відношеннях?

6. Для яких відношень можна застосувати згортку де Моргана?

7. Які властивості має згортка де Моргана?

8. Що є суперпозицією відношень і у чому полягає різниця між суперпозицією і згорткою де Моргана?


Сейчас читают про: