تويت
علاقه ثناييه
Binary relation - Relation binaire
العلاقة الثنائية
المجموعة set، يعد مفهوم المجموعة من المفاهيم الأساسية في علم الرياضيات. وحيث إن كلمة مجموعة هي كلمة أولية في هذا العلم، وهي ببساطة جماعة من الأشياء، كل شيء من هذه الأشياء يدعى عنصراً، ووجوده فيها يوصف بالانتماء لها. لذا فليس للمجموعة تعريف، وإنما تُعرَف بعناصرها. فإذا كان a عنصراً في مجموعةA، قيل إن a ينتمي إلى A، ورمز لذلك بـ aÎA، وإذا لم يكن b عنصراً في المجموعة A، قيل إن b لا ينتمي إلى A، ورمز لذلك بـ bÏA. مثلاً مجموعة أيام الأسبوع هي {الجمعة، السبت، الأحد، الاثنين، الثلاثاء، الأربعاء، الخميس} ومجموعة أشهر السنة الهجرية هي {محرم، صفر، ربيع أول، ربيع ثاني، جمادى أولى، جمادى أخرى، رجب، شعبان، رمضان، شوال، ذو القعدة، ذو الحجة}.
مثال (1): إن مجموعة الأعداد الطبيعية هيN={1,2,3,…} فالعدد 17ÎN بينما العدد -2ÏN. ومجموعة الأعداد الصحيحة هي Z=[…,-3,-2,-1,0,1,2,3..} وكل من العددين ينتمي إلى هذه المجموعة، أي 17ÎZ, -2ÎZ.
وكذلك بفرض A={xÎN: x³9} فإن 5ÏA بينما11ÎA.
العلاقة الثنائية Binary Relation
تعريف: العلاقة الثنائية من مجموعة إلى أخرى، غير خاليتين، هي ثلاثية مرتبة (A, B, R)، حيث A هي مجموعة المنطلق (Domain)، نB هي مجموعة المستقر Co-domain))، تR هي قاعدة الربط (Relationship) بين عناصر A وB.
وإذا كانت A = B قيل إن العلاقة على A، وكتبت ثنائية مرتبة (A, R).
مثال (2): لتكن العلاقة الثنائية (A, B, R)، حيث المنطلق A={2,3,5,11} والمستقر B={2,7,12,15,17,20}، وقاعدة الربط بينها R هي «يقسم»، فإن قاعدة الربط R تعين الارتباط بين العناصر بما يإتي:
2 يقسم 2، 2 يقسم 12، 2 يقسم 20، 3 يقسم 12، 3 يقسم 15، 5 يقسم 15، 5 يقسم 20.
ويمكن تمثيل ذلك بالرسم المبين في الشكل (1).
كما يمكن كتابة ذلك على شكل مجموعة L={(2,2),(2,12),(2,20),(3,12),(3,15),(5,15),(5,20) }.
أي أن الزوج المرتب (الثنائية) (x, y) ÎL إذا وفقط إذا كانت x R y.
إن L تدعى بيان العلاقة Graph.
بيان العلاقة الثنائية (R,B,A) هو مجموعة كل الأزواج المرتبة (x,y)ÎA.B حيث x R y. أي هو مجموعة جزئية {(x,y)Î A.B :x R y} Ê A´ B
فإذا رمزنا للبيان بـ R فإن x R y Û(x, y)Î A.
وهذا يقودنا إلى التعريف المكافئ الآتي:
تعريف العلاقة الثنائية R من مجموعة A إلى مجموعة B هي مجموعة جزئية من الجداء الديكارتي
A´B = {(x,y):xÎA,yÎB} بحيث x R y Û (x,y)ÎR
مثال (3): لتكن المجموعتان B = {2,7,12,15,17,20} وA = {2,3,5,11}
إن المجموعة T = {(2,2),(12,2),(20,2),(12,3),(15,3),(15,5),(20,5)}
تعين علاقة ثنائية T من المجموعة B إلى المجموعة A.
التطبيق (التابع، الدالة) Mapping (Function)
تعريف التطبيق هو علاقة ثنائية تحقق الشرطين الآتيين:
1) كل عنصر من المنطلق له صورة في المستقر.
2) هذه الصورة وحيدة.
إن كل تطبيق هو علاقة، لكن العكس غير صحيح.
مثلاً إن العلاقة R في المثال (2) ليست تطبيقاً، ذلك لأن العنصر 11 من المنطلق ليس له صورة في المستقر.
كذلك فالعلاقة T في المثال (3) ليست تطبيقاً ذلك لأن العنصر 12 من المنطلق له أكثر من صورة في المستقر.
نظير علاقة ثنائية inverse relation
إن نظير العلاقة R من مجموعة A إلى مجموعة B، (ونرمز لها R-1)، هي علاقة من المجموعة B إلى المجموعة A،
بحيث y R-1 x Û x R y : xÎA, yÎB
مثال (4): إن العلاقة T في المثال (3) هي نظير العلاقة R في المثال (2)، أي أن T = R-1وكذلك فإن R هي نظير T، أي R = T-1.
تساوي علاقتين Equality of two relations
تتساوى علاقتان ثنائيتان T وR من مجموعةA إلى مجموعة B إذا تساوى بياناهما. أما تساوي العلاقتين (A, B, R), (C, D, T)
فيعني أن A = C , B = D, R = T.
العلاقة الكلية (الشاملة) Total (universal)relation
إذا كانت B ≠ Φ ≠ A فإن R= A ´ B تدعى العلاقة الكلية من A إلى B.
العلاقة الخالية (المستحيلة) Emptyrelation
إذا كانت R مجموعة خالية (R=Φ) فإن Rتدعى علاقة خالية أو مستحيلة.
مثال (5): لتكن مجموعة الأشخاص {أحمد، غسان، وليد، ماهر، سعيد} = A ولتكن مجموعة السنوات
B={200,201,…,300}، وقاعدة الربط R بينها هي «عُمرُه»، فإن R=Φ (علاقة خالية).
الاحتواء Conclusion
إذا كانت R وT علاقتين من مجموعة A إلى مجموعة B، فإن T محتواة في Rت، (TÍR)، أو Tتقضي R ت، (TÞR)، إذا كان بيان T محتوى في بيان R.
تقاطع علاقتين Intersection of tworelations
إذا كانت R وT علاقتين من مجموعة A إلى مجموعة B، فإن S=RÇT (تقرأ R تقاطع T) هو علاقة من المجموعة A إلى المجموعة B
بحيث x S y Û x R y Ù x, x T y, Î A, y Î B، أي أن بيان العلاقة S هو تقاطع بيانَي العلاقتين R وT.
اجتماع (اتحاد) علاقتين Union of tworelations
إذا كانت R وT علاقتين من مجموعة A إلى مجموعة B، فإن S=R È T هو علاقة من المجموعةA إلى المجموعة B بحيث x S y Ûx R y Úx T y; x ÎA, y ÎB.
تركيب (جداء) علاقتين Composition (product) of two relations
إذا كانت A وB وC ثلاث مجموعات، وكانت Tعلاقة من المجموعة A إلى المجموعة B، R علاقة من المجموعة B إلى المجموعة C، فإن S=R o T(وتقرأ R بعد T) هو علاقة من المجموعة A إلى المجموعة C
بحيث x S y Þ $ z Î B; x T z Ù z R y; x Î A, y ÎC.
الخاصة التجميعية Associative law
إذا كانت A وB وC وD أربع مجموعات، Tعلاقة من المجموعة A إلى المجموعة B، R علاقة من المجموعة B إلى المجموعة C،S علاقة من المجموعة C إلى المجموعة D، فإن S o (R o T) = (S o R) o T، أي أن تركيب العلاقات يتمتع بالخاصة التجميعية.
مثال (6): إذا كانت العلاقات المعرفة على المجموعة A={1,2,3,4,5} هي
R={(1,2),(3,5),(4,1)},S={(2,4),(5,2)},T={(2,5),(4, 3),(1,5)}
فإن To(SoR)={(1,3),(3,5)}
(T o S) o R = {(1,3),(3,5)} = T o (S o R)
تصنيف العلاقات الثنائية على مجموعةClassification of relations
إن علاقة R على مجموعة A تدعى:
1) انعكاسية reflexive إذا تحقق الشرط " x ÎA x R x
أي " x ÎA (x,x) xÎR أي {(x ,x) :x ÎA} ÍR
2) تناظرية symmetric إذا تحقق الشرط(x,y) Î R Þ (y,x) Î R أي R-1 = R
3) متعدية transitive إذا تحقق الشرط (x,y) ÎR Ù (y,z) Î R Þ (x,z) Î R أي R o R Í R
4) تخالفية anti-symmetric إذا تحقق الشرط(x,y) Î R Ù (y,x)ÎR Þ x = y أي R o R-1 Í {(x,x) :x Î A}
5) كلية total إذا تحقق الشرط x,y Î A; x¹y Þ(x,y) Î R Ú (y,x) Î R
أي أن أي عنصرين مختلفين ينتميان إلى A، يرتبطان فيما بينهما بالعلاقة R.
6) دائرية circular إذا تحقق الشرط (x,y) Î RÙ (y,z) Î R Þ (z, x)Î R
يجب الانتباه إلى أن كلمتي «تناظرية» و«تخالفية» ليستا صفتين متعاكستين، فمثلاً إن العلاقة «أكبر تماماً من» المعرفة على مجموعة من الأشخاص، هي علاقة غير تناظرية ، لأنه إذا كان س < ع فلا يمكن أن تكون ع <س، ولكنها علاقة تخالفية.
بينما العلاقة «أخت» المعرفة على أبناء عائلة مكونة من مجموعة من الصبيان والبنات، فهي علاقة غير تناظرية وغير تخالفية معاً.
لأنه لو كان «خالد وليلى وسلمى» من أبناء هذه العائلة، فإن ليلى «أخت» خالد، لكن العكس غير صحيح؛ فالعلاقة ليست تناظرية.
ثم إن ليلى «أخت» سلمى، وكذلك سلمى «أخت» ليلى، لكن ليلى غير سلمى فالعلاقة ليست تخالفية.
مثال (7): إن العلاقة «يقسم» على مجموعة الأعداد الطبيعية N هي: انعكاسية وتخالفية ومتعدية.
حيث إن xÎN «يقسم» yÎN، (وتُرمَّز (x½y)يعني يوجد عدد طبيعي zÎN بحيث y=z x
1) مهما يكن العدد الطبيعي x Î N فإن x=1. xأي أن x يقسم x
2) إن x Î N يقسم y Î N يعني يوجد عدد طبيعي z Î N بحيث y=z x
وإن y Î N يقسم x Î N يعني يوجد عدد طبيعي u Î N بحيث x=u y
إذن x = y Ü u = z =1 Ü zu =1 Ü y=z(uy)=(zu)y
3) إن x Î N يقسم y Î N يعني يوجد عدد طبيعي t Î N بحيث y=t x
وإن y Î N يقسم z Î N يعني يوجد عدد طبيعي u Î N بحيث z = u y
إذن z = u (tx) = (ut) x أي أن x يقسم z
مثال (8): إن العلاقة «أصغر أو يساوي» المعرّفة على مجموعة الأعداد الصحيحة Z هي علاقة: انعكاسية وتخالفية ومتعدية وكلية.
بينما العلاقة «أصغر تماماً»، هي علاقة تخالفية ومتعدية وكلية.
علاقة التكافؤ equivalence relation
تعريف: علاقة التكافؤ على مجموعة A هي علاقة ثنائية انعكاسية وتناظرية ومتعدية.
مثال (9): إذا كان n عدداً طبيعياً (n Î N)فالعلاقة R المعرفة على مجموعة الأعداد الصحيحة Z بالشكل:
X R y Û $ k Î Z: x-y = kn
أي أن باقي قسمة x على n يساوي باقي قسمة y على n وتُرمَّز (x mod (n)=y mod (n))، هي علاقة تكافؤ على A. حيث إن:
1) x Î Z يقضي أن x-x = 0 = 0n وبالتالي " x ÎZ (x, x) Î R
2) إن x R y يقضي بوجود عدد صحيح kبحيث x-y = k. n وبالتالي y- x = (-k). n أي أن y R x.
3) إن x R y وy R z يقضي بوجود عددين صحيحين k وt بحيث x- y = k. n وy- z = t. nوبالجمع نجد
x- z = (k+ t) n = r. n (حيث k+ n = r Î R) أي أنx R z.
صفوف التكافؤ equivalence classes
لتكن A مجموعة غير خالية.
تعريف: إذا كانت R علاقة تكافؤ معرفة على المجموعة A، وكان a عنصراً من A، فإن المجموعة الجزئية
{x Î A: (x, a) Î R} تدعى صف تكافؤ العنصر a، ونرمز له Ra.
إن x, y Î Ra Þ (x, y) Î R Ù (y, x) Î R ذلك لأن Rعلاقة تناظرية ومتعدية.
إن صف التكافؤ Ra = {x Î A: (x, a)Î R} = {x Î A; (a, x) Î R} ذلك لأن R علاقة تناظرية ومتعدية.
إن عناصر صف التكافؤ Ra تدعى العناصر المكافئة equivalent للعنصر a.
إذا كان C صف تكافؤ، فكل عنصر فيه يدعى ممثلاً representative لهذا الصف.
أي أن a, b Î C يقضي أن C=Ra=Rb.
إن أي صف تكافؤ هو مجموعة غير خالية. (إن R a ¹ Φ لأن a Î Ra).
إن تقاطع أي صفي تكافؤ مختلفين هو مجموعة خالية (a,bÎA;a¹bÞRaÇRb=Φ) إن اجتماع كل صفوف التكافؤ يساوي المجموعة A.
التجزئة partition
لتكن A مجموعة غير خالية.
إن تجزئة المجموعة A هو تقسيمها إلى جماعة من المجموعات الجزئية {Ai :iÎ I}بحيث:
1) كل واحدة منها غير خالية.
2) تقاطع أي مجموعتين جزئيتين مختلفتين هو مجموعة خالية.
3) اجتماع كل هذه المجموعات الجزئية يساوي A.
إن أي علاقة تكافؤ R على مجموعة R تحدد تجزئة {Ai : iÎ I} للمجموعة A.
إن أي تجزئة {Ai :iÎ I} لمجموعة غير خالية Aتحدد علاقة تكافؤ R على المجموعة A تكون {Ai :iÎI} مجموعة كل صفوف التكافؤ للعلاقة R.
مثال (10): إن علاقة التكافؤ في المثال (9) تعين تجزئة لمجموعة الأعداد الصحيحة Z
وعدد صفوف التكافؤ هو n. فمثلاً إذا كانتn=4 فإن صفوف التكافؤ هي:
R0={…,-12,-8,-4,0,4,8,12,…} وR1={…,-11,-7,-3,1,5,9,13,…}
R2={…,-10,-6,-2,2,6,10,14,…} وR3={…,-9,-5,-1,3,7,11,15,…}
واضح أن:
1) كل صف تكافؤ هو مجموعة جزئية غير خالية.
2) إن تقاطع أي صفي تكافؤ مختلفين هو مجموعة خالية.
3) إن اجتماع كل صفوف التكافؤ يساوي المجموعة Z.
علاقة الترتيب order relation
إذا عُرِّفت علاقة على مجموعة غير خالية نظمت عناصرها وفق ترتيب معين،
تدعى هذه العلاقة علاقة ترتيب.
تعريف: علاقة الترتيب على مجموعة غير خالية A هي علاقة ثنائية تخالفية، متعدية.
تعريف: علاقة الترتيب الكلي على مجموعة غير خالية A هي علاقة ثنائية تخالفية ومتعدية وكلية.
مثال (11): إن علاقة "يقسم" المعرفة على مجموعة الأعداد الطبيعية N في المثال (7) هي علاقة ترتيب.
بينما العلاقة "أصغر تماماً" المعرفة على مجموعةو الأعداد الصحيحة Z فهيى علاقة ترتيب كلي.
أنور اللحام
Binary relation - Relation binaire
العلاقة الثنائية
المجموعة set، يعد مفهوم المجموعة من المفاهيم الأساسية في علم الرياضيات. وحيث إن كلمة مجموعة هي كلمة أولية في هذا العلم، وهي ببساطة جماعة من الأشياء، كل شيء من هذه الأشياء يدعى عنصراً، ووجوده فيها يوصف بالانتماء لها. لذا فليس للمجموعة تعريف، وإنما تُعرَف بعناصرها. فإذا كان a عنصراً في مجموعةA، قيل إن a ينتمي إلى A، ورمز لذلك بـ aÎA، وإذا لم يكن b عنصراً في المجموعة A، قيل إن b لا ينتمي إلى A، ورمز لذلك بـ bÏA. مثلاً مجموعة أيام الأسبوع هي {الجمعة، السبت، الأحد، الاثنين، الثلاثاء، الأربعاء، الخميس} ومجموعة أشهر السنة الهجرية هي {محرم، صفر، ربيع أول، ربيع ثاني، جمادى أولى، جمادى أخرى، رجب، شعبان، رمضان، شوال، ذو القعدة، ذو الحجة}.
مثال (1): إن مجموعة الأعداد الطبيعية هيN={1,2,3,…} فالعدد 17ÎN بينما العدد -2ÏN. ومجموعة الأعداد الصحيحة هي Z=[…,-3,-2,-1,0,1,2,3..} وكل من العددين ينتمي إلى هذه المجموعة، أي 17ÎZ, -2ÎZ.
وكذلك بفرض A={xÎN: x³9} فإن 5ÏA بينما11ÎA.
العلاقة الثنائية Binary Relation
تعريف: العلاقة الثنائية من مجموعة إلى أخرى، غير خاليتين، هي ثلاثية مرتبة (A, B, R)، حيث A هي مجموعة المنطلق (Domain)، نB هي مجموعة المستقر Co-domain))، تR هي قاعدة الربط (Relationship) بين عناصر A وB.
وإذا كانت A = B قيل إن العلاقة على A، وكتبت ثنائية مرتبة (A, R).
مثال (2): لتكن العلاقة الثنائية (A, B, R)، حيث المنطلق A={2,3,5,11} والمستقر B={2,7,12,15,17,20}، وقاعدة الربط بينها R هي «يقسم»، فإن قاعدة الربط R تعين الارتباط بين العناصر بما يإتي:
2 يقسم 2، 2 يقسم 12، 2 يقسم 20، 3 يقسم 12، 3 يقسم 15، 5 يقسم 15، 5 يقسم 20.
ويمكن تمثيل ذلك بالرسم المبين في الشكل (1).
 الشكل (1) |
أي أن الزوج المرتب (الثنائية) (x, y) ÎL إذا وفقط إذا كانت x R y.
إن L تدعى بيان العلاقة Graph.
بيان العلاقة الثنائية (R,B,A) هو مجموعة كل الأزواج المرتبة (x,y)ÎA.B حيث x R y. أي هو مجموعة جزئية {(x,y)Î A.B :x R y} Ê A´ B
فإذا رمزنا للبيان بـ R فإن x R y Û(x, y)Î A.
وهذا يقودنا إلى التعريف المكافئ الآتي:
تعريف العلاقة الثنائية R من مجموعة A إلى مجموعة B هي مجموعة جزئية من الجداء الديكارتي
A´B = {(x,y):xÎA,yÎB} بحيث x R y Û (x,y)ÎR
مثال (3): لتكن المجموعتان B = {2,7,12,15,17,20} وA = {2,3,5,11}
إن المجموعة T = {(2,2),(12,2),(20,2),(12,3),(15,3),(15,5),(20,5)}
تعين علاقة ثنائية T من المجموعة B إلى المجموعة A.
التطبيق (التابع، الدالة) Mapping (Function)
تعريف التطبيق هو علاقة ثنائية تحقق الشرطين الآتيين:
1) كل عنصر من المنطلق له صورة في المستقر.
2) هذه الصورة وحيدة.
إن كل تطبيق هو علاقة، لكن العكس غير صحيح.
مثلاً إن العلاقة R في المثال (2) ليست تطبيقاً، ذلك لأن العنصر 11 من المنطلق ليس له صورة في المستقر.
كذلك فالعلاقة T في المثال (3) ليست تطبيقاً ذلك لأن العنصر 12 من المنطلق له أكثر من صورة في المستقر.
نظير علاقة ثنائية inverse relation
إن نظير العلاقة R من مجموعة A إلى مجموعة B، (ونرمز لها R-1)، هي علاقة من المجموعة B إلى المجموعة A،
بحيث y R-1 x Û x R y : xÎA, yÎB
مثال (4): إن العلاقة T في المثال (3) هي نظير العلاقة R في المثال (2)، أي أن T = R-1وكذلك فإن R هي نظير T، أي R = T-1.
تساوي علاقتين Equality of two relations
تتساوى علاقتان ثنائيتان T وR من مجموعةA إلى مجموعة B إذا تساوى بياناهما. أما تساوي العلاقتين (A, B, R), (C, D, T)
فيعني أن A = C , B = D, R = T.
العلاقة الكلية (الشاملة) Total (universal)relation
إذا كانت B ≠ Φ ≠ A فإن R= A ´ B تدعى العلاقة الكلية من A إلى B.
العلاقة الخالية (المستحيلة) Emptyrelation
إذا كانت R مجموعة خالية (R=Φ) فإن Rتدعى علاقة خالية أو مستحيلة.
مثال (5): لتكن مجموعة الأشخاص {أحمد، غسان، وليد، ماهر، سعيد} = A ولتكن مجموعة السنوات
B={200,201,…,300}، وقاعدة الربط R بينها هي «عُمرُه»، فإن R=Φ (علاقة خالية).
الاحتواء Conclusion
إذا كانت R وT علاقتين من مجموعة A إلى مجموعة B، فإن T محتواة في Rت، (TÍR)، أو Tتقضي R ت، (TÞR)، إذا كان بيان T محتوى في بيان R.
تقاطع علاقتين Intersection of tworelations
إذا كانت R وT علاقتين من مجموعة A إلى مجموعة B، فإن S=RÇT (تقرأ R تقاطع T) هو علاقة من المجموعة A إلى المجموعة B
بحيث x S y Û x R y Ù x, x T y, Î A, y Î B، أي أن بيان العلاقة S هو تقاطع بيانَي العلاقتين R وT.
اجتماع (اتحاد) علاقتين Union of tworelations
إذا كانت R وT علاقتين من مجموعة A إلى مجموعة B، فإن S=R È T هو علاقة من المجموعةA إلى المجموعة B بحيث x S y Ûx R y Úx T y; x ÎA, y ÎB.
تركيب (جداء) علاقتين Composition (product) of two relations
إذا كانت A وB وC ثلاث مجموعات، وكانت Tعلاقة من المجموعة A إلى المجموعة B، R علاقة من المجموعة B إلى المجموعة C، فإن S=R o T(وتقرأ R بعد T) هو علاقة من المجموعة A إلى المجموعة C
بحيث x S y Þ $ z Î B; x T z Ù z R y; x Î A, y ÎC.
الخاصة التجميعية Associative law
إذا كانت A وB وC وD أربع مجموعات، Tعلاقة من المجموعة A إلى المجموعة B، R علاقة من المجموعة B إلى المجموعة C،S علاقة من المجموعة C إلى المجموعة D، فإن S o (R o T) = (S o R) o T، أي أن تركيب العلاقات يتمتع بالخاصة التجميعية.
مثال (6): إذا كانت العلاقات المعرفة على المجموعة A={1,2,3,4,5} هي
R={(1,2),(3,5),(4,1)},S={(2,4),(5,2)},T={(2,5),(4, 3),(1,5)}
فإن To(SoR)={(1,3),(3,5)}
(T o S) o R = {(1,3),(3,5)} = T o (S o R)
تصنيف العلاقات الثنائية على مجموعةClassification of relations
إن علاقة R على مجموعة A تدعى:
1) انعكاسية reflexive إذا تحقق الشرط " x ÎA x R x
أي " x ÎA (x,x) xÎR أي {(x ,x) :x ÎA} ÍR
2) تناظرية symmetric إذا تحقق الشرط(x,y) Î R Þ (y,x) Î R أي R-1 = R
3) متعدية transitive إذا تحقق الشرط (x,y) ÎR Ù (y,z) Î R Þ (x,z) Î R أي R o R Í R
4) تخالفية anti-symmetric إذا تحقق الشرط(x,y) Î R Ù (y,x)ÎR Þ x = y أي R o R-1 Í {(x,x) :x Î A}
5) كلية total إذا تحقق الشرط x,y Î A; x¹y Þ(x,y) Î R Ú (y,x) Î R
أي أن أي عنصرين مختلفين ينتميان إلى A، يرتبطان فيما بينهما بالعلاقة R.
6) دائرية circular إذا تحقق الشرط (x,y) Î RÙ (y,z) Î R Þ (z, x)Î R
يجب الانتباه إلى أن كلمتي «تناظرية» و«تخالفية» ليستا صفتين متعاكستين، فمثلاً إن العلاقة «أكبر تماماً من» المعرفة على مجموعة من الأشخاص، هي علاقة غير تناظرية ، لأنه إذا كان س < ع فلا يمكن أن تكون ع <س، ولكنها علاقة تخالفية.
بينما العلاقة «أخت» المعرفة على أبناء عائلة مكونة من مجموعة من الصبيان والبنات، فهي علاقة غير تناظرية وغير تخالفية معاً.
لأنه لو كان «خالد وليلى وسلمى» من أبناء هذه العائلة، فإن ليلى «أخت» خالد، لكن العكس غير صحيح؛ فالعلاقة ليست تناظرية.
ثم إن ليلى «أخت» سلمى، وكذلك سلمى «أخت» ليلى، لكن ليلى غير سلمى فالعلاقة ليست تخالفية.
مثال (7): إن العلاقة «يقسم» على مجموعة الأعداد الطبيعية N هي: انعكاسية وتخالفية ومتعدية.
حيث إن xÎN «يقسم» yÎN، (وتُرمَّز (x½y)يعني يوجد عدد طبيعي zÎN بحيث y=z x
1) مهما يكن العدد الطبيعي x Î N فإن x=1. xأي أن x يقسم x
2) إن x Î N يقسم y Î N يعني يوجد عدد طبيعي z Î N بحيث y=z x
وإن y Î N يقسم x Î N يعني يوجد عدد طبيعي u Î N بحيث x=u y
إذن x = y Ü u = z =1 Ü zu =1 Ü y=z(uy)=(zu)y
3) إن x Î N يقسم y Î N يعني يوجد عدد طبيعي t Î N بحيث y=t x
وإن y Î N يقسم z Î N يعني يوجد عدد طبيعي u Î N بحيث z = u y
إذن z = u (tx) = (ut) x أي أن x يقسم z
مثال (8): إن العلاقة «أصغر أو يساوي» المعرّفة على مجموعة الأعداد الصحيحة Z هي علاقة: انعكاسية وتخالفية ومتعدية وكلية.
بينما العلاقة «أصغر تماماً»، هي علاقة تخالفية ومتعدية وكلية.
علاقة التكافؤ equivalence relation
تعريف: علاقة التكافؤ على مجموعة A هي علاقة ثنائية انعكاسية وتناظرية ومتعدية.
مثال (9): إذا كان n عدداً طبيعياً (n Î N)فالعلاقة R المعرفة على مجموعة الأعداد الصحيحة Z بالشكل:
X R y Û $ k Î Z: x-y = kn
أي أن باقي قسمة x على n يساوي باقي قسمة y على n وتُرمَّز (x mod (n)=y mod (n))، هي علاقة تكافؤ على A. حيث إن:
1) x Î Z يقضي أن x-x = 0 = 0n وبالتالي " x ÎZ (x, x) Î R
2) إن x R y يقضي بوجود عدد صحيح kبحيث x-y = k. n وبالتالي y- x = (-k). n أي أن y R x.
3) إن x R y وy R z يقضي بوجود عددين صحيحين k وt بحيث x- y = k. n وy- z = t. nوبالجمع نجد
x- z = (k+ t) n = r. n (حيث k+ n = r Î R) أي أنx R z.
صفوف التكافؤ equivalence classes
لتكن A مجموعة غير خالية.
تعريف: إذا كانت R علاقة تكافؤ معرفة على المجموعة A، وكان a عنصراً من A، فإن المجموعة الجزئية
{x Î A: (x, a) Î R} تدعى صف تكافؤ العنصر a، ونرمز له Ra.
إن x, y Î Ra Þ (x, y) Î R Ù (y, x) Î R ذلك لأن Rعلاقة تناظرية ومتعدية.
إن صف التكافؤ Ra = {x Î A: (x, a)Î R} = {x Î A; (a, x) Î R} ذلك لأن R علاقة تناظرية ومتعدية.
إن عناصر صف التكافؤ Ra تدعى العناصر المكافئة equivalent للعنصر a.
إذا كان C صف تكافؤ، فكل عنصر فيه يدعى ممثلاً representative لهذا الصف.
أي أن a, b Î C يقضي أن C=Ra=Rb.
إن أي صف تكافؤ هو مجموعة غير خالية. (إن R a ¹ Φ لأن a Î Ra).
إن تقاطع أي صفي تكافؤ مختلفين هو مجموعة خالية (a,bÎA;a¹bÞRaÇRb=Φ) إن اجتماع كل صفوف التكافؤ يساوي المجموعة A.
التجزئة partition
لتكن A مجموعة غير خالية.
إن تجزئة المجموعة A هو تقسيمها إلى جماعة من المجموعات الجزئية {Ai :iÎ I}بحيث:
1) كل واحدة منها غير خالية.
2) تقاطع أي مجموعتين جزئيتين مختلفتين هو مجموعة خالية.
3) اجتماع كل هذه المجموعات الجزئية يساوي A.
إن أي علاقة تكافؤ R على مجموعة R تحدد تجزئة {Ai : iÎ I} للمجموعة A.
إن أي تجزئة {Ai :iÎ I} لمجموعة غير خالية Aتحدد علاقة تكافؤ R على المجموعة A تكون {Ai :iÎI} مجموعة كل صفوف التكافؤ للعلاقة R.
مثال (10): إن علاقة التكافؤ في المثال (9) تعين تجزئة لمجموعة الأعداد الصحيحة Z
وعدد صفوف التكافؤ هو n. فمثلاً إذا كانتn=4 فإن صفوف التكافؤ هي:
R0={…,-12,-8,-4,0,4,8,12,…} وR1={…,-11,-7,-3,1,5,9,13,…}
R2={…,-10,-6,-2,2,6,10,14,…} وR3={…,-9,-5,-1,3,7,11,15,…}
واضح أن:
1) كل صف تكافؤ هو مجموعة جزئية غير خالية.
2) إن تقاطع أي صفي تكافؤ مختلفين هو مجموعة خالية.
3) إن اجتماع كل صفوف التكافؤ يساوي المجموعة Z.
علاقة الترتيب order relation
إذا عُرِّفت علاقة على مجموعة غير خالية نظمت عناصرها وفق ترتيب معين،
تدعى هذه العلاقة علاقة ترتيب.
تعريف: علاقة الترتيب على مجموعة غير خالية A هي علاقة ثنائية تخالفية، متعدية.
تعريف: علاقة الترتيب الكلي على مجموعة غير خالية A هي علاقة ثنائية تخالفية ومتعدية وكلية.
مثال (11): إن علاقة "يقسم" المعرفة على مجموعة الأعداد الطبيعية N في المثال (7) هي علاقة ترتيب.
بينما العلاقة "أصغر تماماً" المعرفة على مجموعةو الأعداد الصحيحة Z فهيى علاقة ترتيب كلي.
أنور اللحام