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

תרגיל מס' 1

1.	בטא בצורה שקולה את:

א.	 באמצעות הקשרים  בלבד.
פתרון: 

ב.	 באמצעות הקשרים  בלבד.
פתרון:

ג.	 באמצעות הקשרים  בלבד.
פתרון:

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

א.	
פתרון: לא שקולים. אם  אז 

ב.	
פתרון: לא שקולים. אם  אז 

ג.	
פתרון: הביטויים שקולים. ניתן להראות בעזרת טבלת אמת. הסבר אחר: אם  אז צד שמאל שקול ל: . אם  אז צד שמאל שקול ל : 

3.	הקשר  מוגדר על ידי טבלת האמת הבאה:

	q	p	
F	T	T	
F	F	T	
F	T	F	
T	F	F	

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

פתרון: נראה כי ניתן לבטא על-ידי הקשר  את הקשרים   ו - .  וגם .

4.	נסמן X- הפסוק "אזכה בהגרלה"
Y - הפסוק "אקנה כרטיס הגרלה"
Z - הפסוק "יהיה לי פנאי"
הצרינו את המשפט הבא וקבעו ערכי אמת שלו עבור המקרה ש X אמיתי, Y שקרי ו-Z אמיתי. (אזכה בהגרלה) אם ורק אם (יהיה לי פנאי ולא אקנה כרטיס הגרלה).

פתרון: . בהצבה הנתונה Z והשלילה של Y הם אמת. לכן צד ימין הוא אמת. בהצבה זאת גם X אמת. לכן הפסוק הוא אמת בהצבה זאת.

5.	בהוכחה הפורמאלית שלהלן הוסיפו נימוק לכל שורה ואת הטאוטולוגיה המוכחת 
במשבצת א,9.
ודאו באמצעות טבלת אמת שזו אכן טאוטולוגיה.

		א				ב		    ג	      ד	  נימוק
1		(C<=B)<=A			הנחה	
2			B<=A		הנחה	
3				A	הנחה	
4				C<=B	MP   1,3	
5				B	MP   2,3	
6				C	MP  4,5	
7			C<=A		דדוקציה 3,6	
8		(C<=A)<=(B<=A)			דדוקציה 2,7	
9	((C<=A)<=(B<=A))<= (C<=B)<=A				דדוקציה 1,8