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

2 3 4 5 6 7 8

Основна

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-відношень використовуються спеціальні операції перестановки й ототожнення координат (стовпців), приписування фіктивної координати, а також згортки де-Моргана. Нехай rⁿ – відношення на множинах А₁, А₂, …, А_n, k=(1, 2, …, n) – набір координат (номерів) стовпців у матриці графіка rⁿ_{1, …, An}, k¢=(і₁, і₂, …, i_n) – набір, отриманий з k у результаті деякої перестановки елементів.

Визначення. Операція h_к’(rⁿ) перестановки координат породжує ставлення n-відношення gⁿ на множинах Аi₁, A_i2, …, A_in, графік якого gⁿ_{Ai, …, Ain} виходить із графіка rⁿ_1,…,An, перестановкою його стовпців відповідно до набору k¢.

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

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

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

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

Визначення. Відношення (rⁿ)^-1=h_`_k(r_n) над множинами A_n, A_n-1,…, A₂, A₁, отримане з відношення rⁿ у результаті перестановки, що відповідає набору ` k називається оберненим.

Очевидно, a=(a_n, a_n-1, …, a₂, a₁)Î(rⁿ)^-1_{An, …, A1}, тоді і тільки тоді, коли
a^-1=(a₁, a_2,,…, a_n)Îrⁿ_{1, An}

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

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

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

1. ((rⁿ)^-1)^-1=rⁿ

2. (rⁿ)^-1Í(sⁿ)^-1

3. (Çr_iⁿ)^-1=Ç(r_iⁿ)^-1

4. (Èr_iⁿ)^-1=È(r_iⁿ)^-1

5. (`rⁿ)^-1=ù((rⁿ)^-1)

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

6. (rⁿ´s^m)^-¹= (s^m)^-¹´(rⁿ)^-¹.

Нехай rⁿ – відношення на множинах А₁, …, А_n і {j₁, j₂, …, j_l} - деяка підмножина множини номерів {1, 2, …, n}.

Визначення. Операція ототожнення координат d(rⁿ) породжує відношення q ^n-l+l= d_{j1,j2., jl}(rⁿ) на множинах A₁,…, A_j2-1, A_j2+1, …, A_j3-1, A_j3+1, …, A_jl-1, A_jl+1, …, A_n, графік якого виходить із графіка rⁿ_1,…Anу результаті виділення множини векторів {a=(а₁^і, a₂ⁱ, …, a_nⁱ)| a_j1ⁱ=a_j2ⁱ=…=a_jlⁱ}Írⁿ_{1,…, An} з наступним викреслюванням у кожнім векторі a елементів a_j2ⁱ, a_j3ⁱ, …, a_jlⁱ.

Тобто у відношенні rⁿ виділяються усі вектори, в яких збігаються компоненти, розташовані в стовпцях з координатами j₁, …, j_i, з наступним виключенням стовпців-копій, що мають координати j₂, j₃, …, j_i.

Приклад. Для відношення g⁵_{А1,А2,А3,А4,А5}з попереднього приклада d₂₄(g⁵)=q ⁴, де q ⁴:

q ⁴_{А1,А2,А1,А3}= 0, a, 0, b

1, b, 1, c

1, b, 1, d

Для відношення q ⁴ d₁₃(q ⁴⁾=x³, де x³:

x³_А1,А2,А3 = 0, a, b

1, b, c

1, b, d

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

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

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

Визначення. Операція приписування фіктивної координати "(rⁿ) породжує відношення qⁿ⁺¹="(rⁿ) над множинами A, A₁, A₂,..., A_n таке, що при справедливості rⁿ(а₁^j, a₂^j,..., a_n^j) виконується
q ⁿ⁺¹(a, a₁^j, a₂^j,..., a_n^j) для будь-якого аÎA.

Операція приписування відношенню rⁿфіктивної координати по множині А полягає в утворенні відношення qⁿ⁺¹="(rⁿ) із графіком, одержуваним таким чином: для кожного вектора a=(a₁ⁱ, a₂ⁱ, …, a_nⁱ)Îrⁿ_1,…,An будуються вектори (а, а₁^і, a₂ⁱ, …, a_nⁱ)Î qⁿ⁺¹_A,A1,…,An, отримані приписуванням до вектора a ліворуч по черзі всіх елементів множини А.

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

a³_А= 1, 0, 0

0, 1, 0

0, 0, 1

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

a⁴_А= 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. Згортка де Моргана, суперпозиція

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

Нехай rⁿ – відношення на множинах А₁, А₂, …, Аn_{-1, A, a}s^m відношення на множинах A, A_n, A_n+1, …, A_n+m-2.

Визначення. Операція згортки де Моргана для відношень rⁿ і s^m породжує відношення q^n+m-2=rⁿ*s^m над множинами А₁, А₂, …, Аn_+m-2, таке, що q^n+m-2(a₁^і, a₂^і,…, a_in+m-2^j) виконується тоді і тільки тоді, коли знайдеться аÎA, для якого виконується rⁿ(a₁^і, a₂^і, …, a_n-1^і, a) і s^m(a, a_n^і, a_n+1^і, …, a_n+m-2^і).

Приклад. aⁿ_1,…,An= 1, 2, … n

2, 3, … n+1

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

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

gⁿ_{An, …, A1}= n, n-1, … 1

n+1, n, … 2

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

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

q ^2n-2_{A1,…,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 b_BC= 0, 1

b, 1 0, 2

c, 2 1, 2

2, 2

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

a, 2

b, 2

c, 2

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

1. rⁿ*s^m¹ s^m*rⁿ

2. (rⁿ*s^m)*q^k= rⁿ*(s^m*q^k)

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

3. (rⁿ*s^m)^-1=(s^m)^-¹*(rⁿ)^-¹

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

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

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

Нехай r₁^m – відношення на множинах А₁,…,А_m-1, B₁; r₂^m на множинах А₁,…,А_m-1, B₂;…;r_n-1^m – на множинах А₁,…,А_m-1, B_n-1; sⁿ – на множинах У₁,…,Вn_-1, A_m.

Визначення. Суперпозицією відношень r₁^m,r₂^m,…,r_n-1^m,sⁿ називається m-відношення q^m=sⁿ(r₁^m,r₂^m,…,r_n-1^m) на множинах А₁,A₂,…,А_m таке, що q^m(а₁^і, a₂^і,…,a_mⁱ) тоді і тільки тоді, коли знайдуться елементи b₁^jÎB₁, b₂^j ÎB₂,…,b_n-1^jÎB_n-1, для яких r_s^m(а₁^і, a₂^і,…,a_m-1ⁱ,b_s^jпри будь-якому s=1, 2,…,n-1, причому, sⁿ(b₁^j, b₂^j, b_n-1^j, a_m^і).