פתרונות נבחרים לשיעורי הבית

                                                               תרגיל מס'  7

3. הוכיחו כי:
א.	
פתרון: 
ב.	 
פתרון: . מכאן .
ג.	
פתרון: 
ד.	
פתרון: 

 .5 מה עוצמת קבוצת כל התוכניות בשפת C?
הסבר: יהי L מספר התוים על המקלדת. קבוצת התוכניות בשפת C מוכלת בקבוצת המחרוזות הסופיות שניתן ליצור מ – L תווים. קבוצת המחרוזות הסופיות שניתן ליצור מ – L התווים היא , כאשר Ai מוגדרת להיות קבוצת המחרוזות באורך i שניתן ליצור מ – L התווים במקלדת. עוצמת כל Ai היא Li ולכן עוצמת האיחוד היא לכל היותר 0א (איחוד בן מניה של קבוצות סופיות). מכאן שעוצמת קבוצת כל התוכניות בשפת C חסומה על-ידי 0א. כיון שקבוצת התוכניות ב – C היא אינסופית (כוללת את התכנית שמדפיסה את המספר i לכל ), עוצמת הקבוצה היא בדיוק 0א.

7.	חשב את עוצמת הקבוצות הבאות:
ב.A = 
הסבר: תהי  הפונקציה המתאימה לכל פונקציה  את הפונקציה שמתאימה לכל איבר x ב – R את f(x) אם x רציונלי ו – 1 אחרת. 
. הפונקציה H1 היא פונקציה שקילות (מדוע?). לכן .