Hw8

‫מבוא ללוגיקה ותורת הקבוצות‬ ‫תרגיל בית ‪8‬‬ ‫מתרגל‪ :‬עדו ניסנבוים‬ ‫‪.1‬הוכח או הפרך‪ :‬אם ‪ k‬קבוצת השמות גדירה ע"י קבוצה סופית ‪ ‬אזי המשלים של ‪( k‬אוסף כל‬ ‫ההשמות שלא ב‪ )k-‬גם גדירה‬ ‫‪.2‬נניח שקבוצת האטומים היא ‪ . P1 , P2 ,...‬נאמר שהשמה היא ‪-d‬חשבונית אם קבוצת האינדקסים‬ ‫של האטומים שמקבלים ‪ 1‬היא ריקה או סידרה חשבונית עם הפרש ‪.d‬‬ ‫‪ 1 i  15,18, 21,...‬‬ ‫‪v) Pi (  ‬‬ ‫למשל‪:‬‬ ‫‪ 0 else‬‬ ‫היא השמה ‪-3‬חשבונית‪ .‬כמו כן השמת ה‪ 0-‬היא ‪ d‬חשבונית לכל ‪.d‬‬ ‫‪.1‬תהי {‪ v‬השמה ‪ 3‬חשבונית ‪ . k1  {v :‬האם ‪ k1‬גדירה?‬ ‫‪.2‬נאמר שקבוצת פסוקים היא ‪-3‬חשבונית אם קיימת השמה ‪-3‬חשבונית אם קיימת‬ ‫‪-3‬חשבונית המספקת אותה‪.‬‬ ‫השמה‬ ‫הוכח או הפרך‪-3  :‬חשבונית אמ"מ כל תת קבוצה סופית של ‪ ‬היא ‪-3‬חשבונית‪.‬‬ ‫‪.3‬נאמר שהשמה ‪ v‬היא חשבונית אם קיים ‪ d‬כך ש‪-v d-‬חשבונית‪ .‬תהי {‪ v‬חשבונית‬ ‫‪. k2  {v :‬‬ ‫האם ‪ k2‬גדירה?‬ ‫‪.3‬הוכח או הפרך‪ :‬כל קבוצת השמות מעצמה ‪ 0‬היא גדירה‪.‬‬ ‫‪.4‬הוכח או הפרך‪:‬‬ ‫‪.1‬אם ‪ k1  k2‬ו‪ k1 -‬גדירה אז ‪ k2‬גדירה‪.‬‬ ‫‪.2‬אם ‪ k1  k2‬ו‪ k2 -‬גדירה אז ‪ k1‬גדירה‪.‬‬ ‫‪.3‬אם ‪ k1 , k2‬גדירות אז ‪ k1 \ k2‬גדירה‪.‬‬ ‫‪.5‬הוכח שכל גרף ‪ G‬ניתן לכיסוי ע"י ‪ k‬קליקים אמ"מ כל תת‪-‬גרף סופי שלו ניתן לכיסוי ע"י ‪k‬‬ ‫קליקים‪.‬‬ ‫הדרכה‪ :‬הגדר קבוצת פסוקים ‪ X Gk‬כאשר ‪ X Gk‬ספיקה אמ"מ ניתן לכסות את ‪ G‬ב‪ k-‬קליקים‪.‬‬ ‫‪i‬‬ ‫‪i‬‬ ‫‪‬השתמש באטומים ‪ pv‬כאשר ‪ pv‬יקבל ‪ 1‬אמ"מ הקודקוד ‪ v‬שייך לקליק ה‪.i-‬‬ ‫‪‬הגדר ע"י פסוקים את הטענות הבאות‪:‬‬ ‫(‪)i‬אם הקשת (‪ )u,v‬אינה בגרף‪ ,‬אזי ‪ u‬ו‪ v-‬בקליקים‬ ‫שונים‬ ‫(‪)ii‬כל צומת נמצא באחד הקליקים‬

‫בהצלחה!‬ ‫להגשה עד‪ 28.6.07 :‬בשעה ‪14:00‬‬