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

תרגיל מס' 3

1.	הוכח כי לכל זוג קבוצות A ו – B מתקיים ש: B=A  אם ורק אם  (רמז: הוכחה בדרך השלילה).  
פתרון: 
	נניח B=A. אזי .
	נניח . נניח בשלילה . אזי או ש – A לא מוכל ב – B, או ש – B לא 	מוכל ב – A (אם A היה מוכל ב – B ו – B היה מוכל ב -A, אז הקבוצות A ו – B היו 	שוות). אם B לא מוכל ב – A, אז קיים איבר x המקיים . לכן הקבוצה 	 אינה ריקה ולכן גם הקבוצה  אינה ריקה. זוהי 	סתירה. באופן דומה נגיע לסתירה אם נניח ש – A לא מוכל ב – B.

	הערות:
	א. כדי להוכיח בשלילה את הטענה  מסתמכים על כך ש- P נכון, ומניחים בשלילה ש-	Q לא נכון. מהמצב הזה מגיעים לסתירה לנכונות P ומזה נובע ש- Q נכון. למעשה מוכיחים את 	הטענה הבאה ששקולה למקורית: .
	ב. כשמוכיחים ללא הגבלת הכלליות צריך להסביר מדוע ניתן לעשות זאת. הסברים מהסוג "קל 	לראות", "ניתן לראות בבירור" וכו' לא יתקבלו. לדוגמא, בשאלה הנוכחית ניתן להניח ב.ה.כ. 	שאם אז קיים X ב-A שלא נמצא ב-B, אבל צריך להסביר שאם המצב הוא הפוך אפשר 	להגיע לתוצאה זהה בהוכחה.

2.	הוכח או הפרך:
ג.	
		פתרון: פסוק זה נכון. דוגמא: . במקרה זה: 			  , 					ואכן .

ד.	
		פתרון: פסוק זה אינו נכון. דוגמא נגדית: . במקרה 		זה , אולם 			.

ה.	
		פתרון:

ו.	
		פתרון: נעזר בסעיף ה':

ז.	
		פתרון:   

הערה (לשאלה 2):
 כדאי להוכיח ע"י שימוש בזהויות, ולא ע"י טבלאות אמת (למרות שההוכחה תקינה). המטרה היא להכיר זהויות ולדעת להשתמש בהן, ולא לכתוב טבלאות אמת ענקיות – דבר שלוקח הרבה זמן ומועד לטעויות.

3.	. חשב את  הקבוצה .
	פתרון: . במקום לחשב 	את P(P(A)), נבדוק אילו איברים מאברי P(A) אינם שייכים ל - P(P(A)). על פי ההגדרה, אלו 	הם אותם איברים שאינם מוכלים ב – P(A). כלומר: 	.

	הערה (לשאלה 3):	
	הגדרה: . מזה לא נובע  אלא . כי A מוכלת 	בעצמה. P(A) היא קבוצה שאיבריה הם אך ורק קבוצות. זה תקף גם לגבי, 	שמוגדרת להיות . ולכן,  ולא 	. ובוודאי שלא בהכרח מתקיים: 	
	חשוב להדגיש שהקשר היחיד שתמיד מתקיים בין הוא: . יכולה להיות 	הכלה, אבל היא לא תמיד מתקיימת. במקרה הזה היא לא. 

4.	
א.	  

ב.	 A,B זרות, לכן ההפרש הסימטרי הוא בעצם איחודן.

ג.	

5.
	א. 

		איברי הסדרה הראשונים:

הוכחת נכונות:
נוכיח באינדוקציה כי וכי לכל   מתקיים .
הערה: בקורס זה אנחנו לא רשאים להניח כי לכל קבוצה  מתקיים . על כן נוסף התנאי השני של הנחת האינדוקציה שיאפר לנו להראות ש .
עבור 0,1 זה נובע מההגדרה. נניח שזה נכון עבור K ונוכיח עבור K+1.
מהנחת האינדוקציה נובע ש  (כי ב  יש k אברים ובכל אבר שלה (שהוא בעצמו קבוצה) יש פחות מ k אברים). כמו כן מההגדרה נובע ש.לכן היות שהקבוצהאינה אבר בקבוצה, מתקיים . כמו כן אם  אזי מההגדרה של יתקיים ש  או ש . במקרה הראשון על פי הנחה האינדוקציה  תהיה קבוצה בת לכל היותר k-1 אברים, ובמקרה השני  תהיה הקבוצה  ששוב לפי הנחת האינדוקציה בת k (<k+1) אברים.

6.	הוכח או הפרך:

א.	
   פתרון: לא נכון. למשל 

ב.	
		פתרון: לא נכון. דוגמא נגדית: . ,    				. , ולכן 				 .

7.	הוכח או הפרך על-ידי דוגמא נגדית:
א.	
	    הוכחה:. אגף 		ימין של  השקילות נכון משום שאכן  וכן  ו- . לכן 			   וגם . לכן  - .

ב.	    
  		הטענה שקרית:   לפי כלל ,  		אם ורק אם     (הצבנו את 0 במקום המופע החופשי היחיד שיש ל- בנוסחה ). שוב לפי  כלל , זה נכון אם ורק אם . הפסוק  הוא שקרי, שכן השלילה שלו:  היא אמת. הוכחה: .

8.	
א. לא נכון. למשל 
			
ב. לא נכון. אותן קבוצות כמו ב-א'.