ساختمان های گسسته – فصل دوم – روابط و توابع

ساختمان های گسسته – فصل دوم – روابط و توابع

اسلاید 1: به نام خداساختمان های گسسته – روابط و توابعDiscrete Structures – Relations and Functionsبهار 991

اسلاید 2: روابط2

اسلاید 3: تعریف 1. یک رابطه (دودویی) 𝑅 از مجموعه 𝑋 به مجموعه 𝑌، زیر مجموعه حاصل ضرب دکارتی 𝑋×𝑌 است. اگر (𝑥,𝑦)∈𝑅 باشد، می نویسیم 𝒙𝑹𝒚 و می گوییم 𝑥 با 𝑦 رابطه دارد. در حالتی که 𝑋=𝑌 باشد، 𝑅 را یک رابطه (دودویی) روی 𝑋 می نامیم.3مجموعه دامنه 𝑅 : 𝑥∈𝑋 𝑥,𝑦 ∈𝑅 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑦∈𝑌}مجموعه برد 𝑅 : 𝑦∈𝑌 𝑥,𝑦 ∈𝑅 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑥∈𝑋}اگر یک رابطه به صورت جدول داده شده باشد دامنه آن از عضو های ستون اول و برد آن از عضو های ستون دوم تشکیل می شود.

اسلاید 4: مثال 1. برای جدول زیر یک رابطه 𝑅 بنویسید.4مجموعه دامنه 𝑅 (𝑆𝑡𝑢𝑑𝑒𝑛𝑡): 𝑪𝒐𝒖𝒓𝒔𝒆𝑺𝒕𝒖𝒅𝒆𝒏𝒕𝐶𝑜𝑚𝑝𝑆𝑐𝑖𝐵𝑖𝑙𝑙𝑀𝑎𝑡ℎ𝑀𝑎𝑟𝑦𝐴𝑟𝑡𝐵𝑖𝑙𝑙𝐻𝑖𝑠𝑡𝑜𝑟𝑦𝐵𝑒𝑡ℎ𝐶𝑜𝑚𝑝𝑆𝑐𝑖𝐵𝑒𝑡ℎ𝑀𝑎𝑡ℎ𝐷𝑎𝑣𝑒مجموعه برد 𝑅 (𝐶𝑜𝑢𝑟𝑠𝑒): 𝑋={𝐵𝑖𝑙𝑙, 𝑀𝑎𝑟𝑦,𝐵𝑒𝑡ℎ,𝐷𝑎𝑣𝑒}𝑌={𝐶𝑜𝑚𝑝𝑆𝑐𝑖, 𝑀𝑎𝑡ℎ,𝐴𝑟𝑡,𝐻𝑖𝑠𝑡𝑜𝑟𝑦}رابطه 𝑅 از جدول بالا می توان به صورت زیر نوشت : 𝑅={ 𝐵𝑖𝑙𝑙,𝐶𝑜𝑚𝑝𝑆𝑐𝑖 , 𝐵𝑖𝑙𝑙,𝐴𝑟𝑡 . 𝑀𝑎𝑟𝑦,𝑀𝑎𝑡ℎ , 𝐵𝑒𝑡ℎ,𝐻𝑖𝑠𝑡𝑜𝑟𝑦 , 𝐵𝑒𝑡ℎ,𝐶𝑜𝑚𝑝𝑆𝑐𝑖 ,(𝐷𝑎𝑣𝑒,𝑀𝑎𝑡ℎ)}جدول 1 – رابطه 𝑅

اسلاید 5: مثال 2. فرض کنید : 5𝐘𝑿4262336344رابطه 𝑅 : 𝑅={ 2, 4 , 2,6 . 3, 3 , 3, 6 , 4,4 }𝑋= 2,3,4 𝑎𝑛𝑑 𝑌={3,4,5,6,7} اگر رابطه 𝑅 را به این صورت تعریف کنیم که (𝑥,𝑦)∈𝑅 اگر 𝑥 ، 𝑦 را بشمارد . اگر رابطه 𝑅 به صورت جدول بنویسیم داریم : جدول 2 – رابطه 𝑅

اسلاید 6: مثال 3. فرض کنید 𝑅 رابطه ای روی 𝑋= 1,2,3,4 باشد که به صورت (𝑥,𝑦)∈𝑅 اگر 𝑥≤𝑦. 6رابطه 𝑅 : 𝑅={ 1, 1 , 1,2 . 1, 3 , 1, 4 , 2,2 , 2,3 , 2,4 , 3,3 , 3,4 ,(4,4)}دامنه و برد هر دو ، برابر 𝑋 هستند.یک روش مناسب برای تصویر کردن یک رابطه روی یک مجموعه ، رسم گراف جهت دار آن است.

اسلاید 7: مثال 4. گراف جهت دار رابطه مثال 3 را رسم کنید. 7رابطه 𝑅 : 𝑅={ 1, 1 , 1,2 . 1, 3 , 1, 4 , 2,2 , 2,3 , 2,4 , 3,3 , 3,4 ,(4,4)}3124گراف جهت دار رابطه 𝑅 :

اسلاید 8: مثال 5. گراف جهت دار رابطه 𝑅 روی 𝑋={𝑎,𝑏,𝑐,𝑑} به صورت زیر است. 8رابطه 𝑅 : 𝑅={ 𝑎, 𝑎 , 𝑏,𝑐 . 𝑐, 𝑏 , 𝑑, 𝑑 }bcگراف جهت دار رابطه 𝑅 : ad

اسلاید 9: مثال 6. گراف جهت دارِ رابطه های زیر را رسم کنید. 9الف ) رابطه 𝑅 : 𝑅= 1, 2 , 2,1 . 3, 3 , 1, 1 , 2,2 𝑜𝑛 𝑋={1,2,3}ب ) رابطه 𝑅 : 𝑅= 1, 2 , 2,3 . 3, 4 , 4, 1 𝑜𝑛 𝑋={1,2,3,4}ج ) رابطه 𝑅 : روی 𝑋={1,2,3,4} که به وسیله (𝑥,𝑦)∈𝑅، اگر 𝑥 2 ≥𝑦 ، تعریف می شود.

اسلاید 10: حل مثال 6 : 10الف-ج ) رابطه 𝑅 : 𝑅= 1, 2 , 2,1 . 3, 3 , 1, 1 , 2,2 𝑜𝑛 𝑋={1,2,3}321

اسلاید 11: 11