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

صفحه 1:
ساقمان:های گشسبه- روانظ وابوانع ‎Discrete Structures - Relations and Functions‏ بهار 99 

صفحه 2:


صفحه 3:
* تعریف 1. یک رابطه (دودویی) از مجموعه به مجموعه , زیر مجموعه حاصل ضرب دکارتی است. اگر باشد, می نویسیم و می گوییم با رانطه دازی:جر حالعن که بانج را یک برانظه (دودوین] زوی fil ws ۶ مجموعه دامنه : ‎|(x, yp) € Rforsomey €¥}‏ 22۲ «ا ‏۶ مجموعه برد : ‏2۱ > > روك حرو رمز ح ابر رد || رای را ‏< اگر یک رابطه به صورت جدول داده شده باشد دامنه آن از عضو های ستون اول و برد آن از عضو های ستون دوم نشکیل می شود. ‎ ‎ 

صفحه 4:
* مثال 1. برای جدول زیر ‎S‏ رابطه بنویسید. X= Bill, Mary, Beth, Dave| : ‏مجموقدإناففه.‎ B Y= CompSei, Math, Art, History| > مجموعه برد : | < رابطه از جدول بالا می توان به صورت زیر نوشت : Re| Bill, CompSci,, Bill Art . Mary, Math’, Beth, History , Beth, CompSci ,|Dave, Math)) 

صفحه 5:
* مثال 2. فرض کنید : (7, 2-3456 5770 |4 ور 2۲۱2 اكر رابطه را به اين صورت تعريف كنيم كه " اگر , را بشمارد *. و ۳ > اگر رابطه به صورت جدول بنویسیم داریم : جدول 2-رابطه 

صفحه 6:
@ * مثال 3. فرض کنید رابطه ای روی باشد که به صورت " اكر ". REL 1 /1,2.03,1,4,12,2,12,3,2,4,)3,3 34,44): ates > 2 كاضيه ويه مدق يزاين سعد > یک روش مناسب برای تصویر کردن یک رابطه روی یک مجموعه , رسم گراف جهت دار آن است. 

صفحه 7:
@ ‎wags‏ * مثال 4. گراف جهت دار رابطه مثال 3 را رسم کنید. < رابطه : })4,4( )3,4 ‎R>A,1)/1,21/1,3),(1,4)12,21,/2,3),(2,41,8,3),‏ ‏< گراف جهت دار ‎C) /5 : ‏رابطه‎ ‎ 

صفحه 8:
@ ‎wags‏ * مقال ‎٩‏ گراف جوت وا :زائظه: زوی مسرت ویر اس ‎R=(\a,q\,|b,c).\c,b\,ad,a\|\ au> ‏< گراف جهت دار رابطه : ‎ 

صفحه 9:
* مثال 6. گراف جهت دار رابطه های زیر را رسم کنید. = |1,2),|2,1].13,3),(1,1),[2,2i|onX=(1,2, 3} : ‏از‎ ‎Re=\1,2)/2,3).3,4),/4,1] on X=(1,2,3,4| ‏یقت‎ ج ) رابطه : روی که به وسیله , اگر . تعریف می شود. 

صفحه 10:
* حل مثال 6 : الفنج ) رابطه : (1,2,3 121111002 - دک 2 

صفحه 11:
* حل مثال 6 : مزونه 134 1ه 122,334,411 72 

صفحه 12:
@ :6 ‏حل كان‎ © ad By جج ) رابطه : روی که به وسیله , اگر , تعریف می شود. R=|1,1)]2,2)/3,3),/4,4), 2,1),2,3,/2,4,,8, 1),3,2),(3,4),/4,1),14,2,,(4,3} 

صفحه 13:
* تعریف 2. ate 5 * تعریف 5. رابطه ودزائظه ladle رابطه روعن دانفکایسی تانت‌ناگل بزای هر ‎sail‏ زوی: متقارن: اسب اگر بزای:هر:داگر آنگاه روی , پادمتقارن است اگر برای هر , اگر و زوق #معدى أست كر يزاف هر اكز بو آنگاه باشد. آنگاه باشد. باشد. 

صفحه 14:
* مثال 7. رابطه هایی روی ارائه دهید که دارای خاصیت های زیر باشند. الف ) انعکاسی و متقارن باشند ولی متعدی نباشند. ب ) انعکاسی باشند اما متقارن و متعدی نباشند. ج ) انعکاسی و ضدمتقارن باشند , ولی متعدی نباشند. د ) انعکاسی نباشند , متقارن باشند , ضدمتقارن نباشند , متعدی باشد. 

صفحه 15:
© * حل مثال 7: الف-ج ) انعکاسی و متقارن باشند ولی متعدی نباشند. ‎R=(1,1),|2,2}./3,3),(4,4),(1,21,/2,11, 2,3), 3,2) onX=(1,2,3,4]‏ بج ) انعکاسی باشند اما متقارن و متعدی نباشند. R=\1,1)/2,21,13,3),/4,4),|1,4),(4,3) onX=(1,2,3,4] جج ) انعکاسی و ضدمتقارن باشند , ولی متعدی نباشند R=/1,1),2,2).13,3),/4,4),|2,1),(1,3) on X=|1,2,3,4] دج ) انعکاسی نباشند , متقارن باشند , ضدمتقارن نباشند , متعدی باشد. R=|1,1),/2,2),(1,2),/2,1,|2,3),(3, 21,]1,3),(3,1)| onX=(1,2,3,4} 

صفحه 16:
© تعریف 6. رابطه روی مجموعه , ترتیب جزئی است اگر انعکاسی , ضدمتقارن و متعدی باشد. * تعریف. 7. فرض کنید رابطه ای ا به باشد , معکوس که‌با نمایش داده می شود زابطة ای از به است که به ضورت زیر تعریف می شود : R'=(y,x|(x,y) ER] * مثال 8. معکوس رابطه را بنویسید. ‎R=(|2,4),(2,6],|3,3),/3,6),(4, 4]‏ ‎R*=((4,2),(6,2],(3,3],(6,3),(4,4]}‏ 

صفحه 17:
> تعریف 8. فرض کنید تزابظه‌ای از. به ور زابطه ای ان یه بانشد ركيت :و کنیا اتماینان ذاذه می:نقولارایطه الق از ببهء اشتت كه به صورت زیر تعریف می شود : ‎y,z| ER, forsome ye ¥|‏ ۵7۵ > رد2 دعر ‏#بمقال 9 مركي زائطه هاف دن نا تويسيت ‎R,=(|1,2),1,6),|2,4|,(3,4],(3,6),(3,8)}‏ ‎R,=((2,u),/4,5),/4, 4),/6,2),18, ull‏ ‎Ay=((1,u),(1,4)2,5,|2,¢),/3,5),13,41,(3, u)} ‎ 

صفحه 18:
*# تعریف 9. رابطه هایی که انعکاسی , متقارن و متعدی هستند رابطه های هم ارزی نامیده می شوند. *# مثال 10. تعبین کنید که آیا رابطه داده شده روی رابطه ای هم ارزی هستند یا خیر. R=((1,1),[2,2),8,3),(4,41,|5 Ai, '1,3),(3,1)) R=(I1,1),/2,2),/3,3),|4,4),]5,5] 31,3, ۳ Ba al Bai 3203.3 ),[4,4)} Re=((1,1),(2,21,(3,3),(4,4),15,5),|1,5], ۳ 1), 3; 3 ۳۱ 

صفحه 19:
© ماتریس , روش مناسبی برای نمایش رابطه از به است. * تعریف 10. سطر های ماتریس را با عضو های (ترتیبی دلخواه) و ستون ‎sl‏ ماتریس را با عضو های (ترتیبی دلخواه) برچسب گذاری می کنیم. ‎WT gia ly wpe 5. glean eas itt‏ مزاز.عی عم مر کاخ ( با رابطه داشته باشد) و در غیر این صورت برایر ۵ قرار می دهیم. ‏اين ماتریس , ماتریس رابطه (نسبت به ترتیب ‎skh‏ و ) ‏نامیده می شود. ‎ 

صفحه 20:
@ كس ‎<١‏ # مثال 11. ماتریس رابطه R=(1,0),|1,d1,(2,¢,,/3,¢1,|3,0),/4,a1 را نسبت به ترتیب های 1 و 2 و 3 و 4 و و و و تعیین کنید. جروج يون خر هه ی ۵ ۵ سس نج با 8 با هه هه بر بر و 

صفحه 21:
@ ‎ves‏ # مثال 12. ماتریس رابطه ‎R=(1,0),|1,d1,(2,¢,,/3,¢1,|3,0),/4,a1 ‏را نسبت به ترتیب های 2 و 3 و 4 و 1 و و و و تعیین کنید. ‎0 ‎1 ‎1 ‎0 ‎0 ‏دحم دن جرهم ی 2 ۵۱ محر ليحت ات بن حت ص هه هه هه دشرا ‎ 

صفحه 22:
@ ‎wad by‏ * مثال 13.,ماتزیش رانطه که آگن : نز شعاود وال به عریت لنندهاست را نسبت به ترتیب های 2 و 3 و 4 , 5 و 6 و 7 و 8 تعیین کنید. ‎GO DO‏ حير اسن © © © ده دمر ير ى داي هي © هه با و بر ‎ 

صفحه 23:
@ مركاة ‎guile‏ رازویمجموعه [یعنت:به ) راابنویسیم از همان ترتیب سطر‌ها برای ستون:ها استفاده: میا * مثال 14. ماتریس رابطه ‏ ر ‎al}‏ و أطرعاء 6 رظاء |0 ,0 ا 6 رع اراطرظا,|4 ,4 احا روى نسبت به ترتيب و و و راتعيين كنيد. هاه كيه صصص هت 2ت 2 ع كرك 0 همه شر ير ان ريه هه هته اه دم 

صفحه 24:
فرض کنید ماتریس رابطه باشد. * تعریف 11. رابطه انعکاسی است اگر و فقط اگر تمام درایه های قطر اصلی 1 باشد. # تعریف 12. رابطه متقارن است اگر و فقط اگر تمام درایه های نسبت به قطر اصلی متقارن باشند. # تعریف 13. رابطه متعدی است اگر و فقط اگر درایه در مخالف صفر باشد و درایه در نیز مخالف صفر باشد. 

صفحه 25:
* مثال 15. ماتریس رابطه ۱ روی نسبت به ترتیب و و و عبارت است از : abcd aj1000 ‏يمر‎ #80 1 10 60 110 010 0 0 1 : ‏آن عبارت است از‎ مریع آن عبار از ‎ried‏ ملاحظه کنید که درایه در مخالف صفر است و درایه 0 0 0 411 در نیز مخالف صفر است بنابراین متعدی است. 220 ‎Abo‏ ‏20 2 610 1 0 010 

صفحه 26:
بانک اطلاعاتی رابطه ای 

صفحه 27:
” تعریف 14. " دو " در رابطه ی دوتايي ( دودویی ) به اين واقعیت اشاره مى ‎US‏ ‏که هر گاه را به صورت جدول بنویسیم , دارای دو ستون است. اغلب مفید است جدول با تعداد دلخواه ستون داشته باشیم. اگر جدولی , ستون داشته باشد بعترانمله: متاظر با آن رانطه عایین :من ‎ans‏ 

صفحه 28:
* مثال 16. جدول زیر یک رابطه تایی را نشان می دهد. اين جدول ارتباط بین شماره شناسایی , نام , موقعیت و سن را بیان می 25 

صفحه 29:
* تعریف 15. بانک اطلاعاتی ( پایگاه داده ها ) , گردایه ای از رکورد هاست که به وسیله کامپیوتر مورد پردازش قرار می گیرد. مدل بانک اطلاعاتی رابطه ای , وابسته به مفهوم رابطه تایی است. * تعریف 16. ستون های یک رابطه تایی را خصیصه می نامند. © تعریف 17. دامنه یک خضیضه : مجموعه ای از تمام عضو هایی است که ‎ol‏ ‎wees‏ را دارند. *# تعریف 18. اگر مقادیر خصیصه ها به صورت منحصر به فردی یک تایی را تعریف کنند , یک خصیصه یا ترکیبی از خصیصه های یک رابطه , کلید نامیده می شود. 

صفحه 30:
* تعریف 19. پرس و جو , به معنای درخواست اطلاعات از بانک اطلاعاتی است. 5-52 تعریف 20. جبر رابطه ای » یک زبان پرس و جو است که عملیات را بر روی ‎SL‏ اطلاعاتی ( پایگاه داده ) به صورت فرمولی بیان می کند. > عملگر های جپر رابطه ای توسط تماد هایی نمایش داده می شوند. > عملگر های جبر رابطه ای عبارتند از : Selection:[] Set Intersection: N Prajection: [] Division: + CartesianProduct:X Natural Join: ‏مه‎ Set Union: UV Set Difference: - 707707720 [] 

صفحه 31:
تعريف 21: عملگر +یک:غملگز بگنایی است گه.:سطر هانن از یگ رابطه را ۱ انتخاب می کند. قرم کلی : خروچی عملگر رابطه ای است که شامل سطر هایی از رابطه می شود که شرط مورد بوده است. شرط می تواند توسط علائم یی ساخته شود. کاردیتالیتی جدول حاصل کمتر یا مساوی جدول اولیه است اما درجه آنها تفاوتی ندارد. نظر در آنها برقرار 

صفحه 32:
* تعریف 22. عملگر ‎Sloe Sie‏ یکتایی است که ستون هایی از یک رابطه را ‎aS wa laa‏ 7 فرم کلی : > مجموعه اسامی خصیصه ها است که از رابطه انتخاب می شوند. ۶ خروجی عملگر کلیه تاپل های رابطه است که محدود به خصیصه های مشخص شده است. > اگر در جدول سطر هایی شییه هم باشند با هم ترکیب می شوند و سطر های تکراری حذف می شوند. > کاردینالیتی حفظ می شود ( معمولا یک کلید کاندید انتخاب می کنیم ) اما درجه آنها کمتر یا مساوی جدول اولیه می باشد. 

صفحه 33:
* ثعریف 23. عملگر , یک عملگری است که روی دو جدول کار می کند و جدول جدیدی را می دهد که یک رکورد برای هر جفت رکورد ممکن از هر دو جدول دارد. + قرم کلی : ۲ در جدول حاصل احتمال تکراری شدن ستون ها وجود دارد. ۶ کاردینالیتی جدول حاصل برابر حاصل ضرب کاردینالیتی دو جدول است و درجه جدول برابر با مجموع درجات دو جدول می باشد. 

صفحه 34:
* تثعریف 24. عملگر » یک عملگر دوتایی است که همانند اجتماع در تثوری مجموعه ها کار می کند. + قرم کلی : ۱ اجتماع دو رابطه و جدولی است که شامل کلیه تاپل های و می شود > دو رابطه ای که بر روی آنها عمل اجتماع انجام می شود باید همساز باشند , یعنی دارای خصیصه های یکسان باشند. کاردینالیتی جدول حاصل برایر مجموع کاردینالیتی دو جدول منهای سطر های مشترک است و درجه جدول حفظ می شود. 

صفحه 35:
* ثعریف 25 عملگر ؛ یک عملگز دوتاین است که همانند اشتراک در تثوری مجموعه ها کار می کند. 2 قرم كلى: > اشتراك دو رابطه و جدولى اسث كه شامل کلیه تاپل هایی می شود که در هر دو جدول وجود دارند. > دو رابطه ای که بر روی آنها عمل اشتراک انجام می شود باید همساز باشند ؛ یعنی دارای خصیصه های یکسان باشند. > کاردینالیتی جدول حاصل برابر سطر های مشترک دو جدول است و درجه جدول حفظ می شود. 

صفحه 36:
*# تعریف 26. عملگر » یک عملگر دوتایی است که همانند تفاضل در تثوری مجموعه ها کار می کند. + قرم کلی : > تفاضل دو رایطه و جدولی است که شامل کلیه تاپل هایی می شود که در جدول رابطه است ولی در جدول رایطه نیست. دو رابطه اى كه بن روی آنها عمل تفاضل انجام می شود باید همساز باشند , یعنی دارای خصیصه های یکسان باشند. > کاردینالیتی حاصل جدول برایر کاردینالتی جدول رابطه منهای سطر های مشترک است و درجه جدول حفظ می شود. 

صفحه 37:
تعریف 27. عملگر » یک عملگر یکتایی است که برای تغییر نام تخصیصه های ‎Wally, Jose‏ عودرجدول رانظهزهورد اتشفاذه :رآ هی گیر, فرم کلی : خروجی عملگر روی رابطه همان رابطه است با نام جدید , به عبارت دیگر رابطه به تغییر نام می دهد. 

صفحه 38:
* تعریف 28. عملگر , یک عملگر دوتایی > فرم کلی > حاصل عملگر رایطه بر رابطه رابطه ای است که شامل تايل هایی از می شود که دارای مقادیر خصیصه های مشترک که در رابطه نیز است می شود و در جدول حاصل خصیصه ای از جدول اضافه می شود که در جدول رابطه نیست. 

صفحه 39:
> فرم کلی < حاصل عملگر رابطه بر رابطه رابطه ای است که شامل تاپل هایی از و می شود که خصیصه های مشترک آنها برایر است. > دو رایطه ای که در الحاق شرکت می کنند باید دارای خصیصه های مشترک باشند. 

صفحه 40:
* مثال 17. رابطه های زیر را در نظر بگیرید : ‎CUSLOMET |‏ ی ‎name? ‎ame dMOUNt| account, ‎SOT nurber OAM number ‎branch( branch customer' customer, sti account| account yy branch, balance} ‎branch ,, assets) ‎depositor(¢ ‎borrower| ‎name? ‎ 

صفحه 41:
* مثال 17. الف) شماره وام هایی که مقدارشان از 200 دلار بیشتر است را بيابيد. 27101112) ‏و۳۵76‎ 271011011 yy, ASSCLS) ‏ريرري 61/5/0111 0171271أكلا6‎ CUSLOMET yyy, CUSLOMET py} ACCOUNE| ACCOUNE pumyor branch... _ balance} Loan LOAN pumpers OTANCE pymes AMOUNE) ae ite (customer, account, eposito. "name? number borrower | CUStOMET ame. LOAN, number: T1622 panne, Lamount>200|L0a72)) 

صفحه 42:
‎Shee‏ 7 .با نام یانی كه يك وام , یک حساب یا هر دو را دارند پیدا کنید. ‎ ‎27101112) ‏و۳۵76‎ 271011011 yy, ASSCLS) ۱ 6060107 ‏م6660‎ branch... _ balance} Loan LOAN pumpers OTANCE pymes AMOUNE) depositor (CUStOMET yume, account, ‎7 1 number. OTTOWET | CUSLOMET james LOAN number ‎TTeystomer,,., borrower) UIT, (depositor) ‎CUSLOMET sane ‎ 

صفحه 43:
* هثال 17.ج) نام مشتریانی که‌تیک وام در شعبه مرکزق دارند را پیدا ‎in‏ 27101112) ‏و۳۵76‎ 271011011 yy, ASSCLS) ۱ 6060107 ‏م6660‎ branch... _ balance} Loan LOAN pumpers OTANCE pymes AMOUNE) depositor (CUStOMET yume, account, b 1 number. OTTOWET | CUSLOMET names !OAN number ‎loan) (‏ 207791067 ) مكى حبري لمرلا أي ‎Teystomer‏ ‎ 

صفحه 44:
* مثال 17. د) نام مشتریانی که یا وام گرفته اند یا حساب دارند ( ولی نه هر دو ) ogi lag customer... Laccountx,=nllor loan, =nui DOrTOWer & depositor) branch | Branch jane, DTANCH yy, ASSCLS) CUSLOMEP CUSLOMET app, CUSLOMET yyy, CUSLOMET py} ACCOUNE| ACCOUNE pumyor branch... _ balance} Loan LOAN pumpers OTANCE pymes AMOUNE) ae ite (customer, account, eposito. "name? number borrower | CUStOMET ame. LOAN, number: II, 

صفحه 45:
ها * مثال 17.ح) نام مشتریانی که هیچ شعبه ندارند را پیدا کنید. ‎de positor ۱‏ سس ‎Dr “ihe ‘borrowers loan - ‏وأم:در شتعبه مرکزق دارند ولی هیچ حسایی در ‎27101112) ‏ري 27171011 و۳۵76‎ ASSCLS) ‎CUSLOMET| CUSLOMET pomp; CUSLOMET yoo) 1 ‏ا‎ ‎ACCOUNE| ACCOUNE ‏رم‎ , branch, _ balance} Loan lodNumpers PANIC pamer' ‘amount) depositor(é CUSLOME james ‏سل‎ = borrower | CUStOMET james LOAN number ‎00 ‏اسر ‎