תרגילים פרק 4🏋️
[[4 - טבלאות אמת (סמנטיקה)]]
(החל מפרק 4 - סמנטיקה של תחשיב הפסוקים)
פרק 4:
תרגיל א:
נתון:
p,q,s = T
r, t = F
קבעו ערך אמת לכל פסוק:
- ¬p∧s שקר
| ¬p∧s |
s |
¬p |
| T |
T |
T |
| F |
F |
T |
| F |
T |
F |
| F |
F |
F |
- t→(r∨¬q) אמת
| r |
¬q |
r∨¬q |
| T |
T |
T |
| T |
F |
T |
| F |
T |
T |
| F |
F |
F |
| t |
r∨¬q |
t→(r∨¬q) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
- (p∧(q∧r))∧(s∧t) שקר
| s∧t |
q∧r |
p∧(q∧r) |
(p∧(q∧r))∧(s∧t) |
| F |
F |
F |
F |
- (¬s∧¬r)↔¬(r∨s) אמת
| (r∨s) |
¬(r∨s) |
(¬s∧¬r) |
| T |
F |
F |
| (r∨s(¬s∧¬r) |
¬(r∨s) |
(¬s∧¬r(¬s∧¬r)↔¬(r∨s) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
T |
- (p→q)↔(s∨t) אמת
| (s∨t) |
(p→q) |
(p→q)↔(s∨t) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
T |
| 6. (p∧s)→(¬t∨¬r) אמת |
|
|
| p |
s |
t |
r |
¬t |
¬r |
| T |
T |
F |
F |
T |
T |
| (¬t∨¬r) |
(p∧s) |
(p∧s)→(¬t∨¬r) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
- p→((q∧(¬r↔s))→p) אמת
| ¬r↔s |
(q∧(¬r↔s) |
((q∧(¬r↔s))→p) |
| T |
T |
T |
| p |
((q∧(¬r↔s))→p) |
p→((q∧(¬r↔s))→p) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
| 8. ((p→q)∧¬q)→(¬p∨s) אמת |
|
|
| (¬p∨s) |
(p→q) |
((p→q)∧¬q) |
| T |
T |
F |
| ((p→q)∧¬q) |
(¬p∨s) |
p→((q∧(¬r↔s))→p) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
| 9. (((¬t→s)∧(p→r))∧(¬r∨¬s)) → (¬p∨t) אמת |
|
|
| p |
s |
q |
t |
r |
¬p |
¬s |
¬t |
¬r |
| T |
T |
T |
F |
F |
F |
F |
T |
T |
| (¬p∨t) |
(¬r∨¬s) |
(p→r) |
(¬t→s) |
| F |
T |
F |
T |
| (¬r∨¬s))→(¬p∨t) |
(((¬t→s)∧(p→r)) |
| F |
F |
| (((¬t→s)∧(p→r)) |
(¬r∨¬s))→(¬p∨t) |
(((¬t→s)∧(p→r))∧(¬r∨¬s))→(¬p∨t) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
|
|
|
| 10. ((¬t∨¬s)→((p∧q)→p))↔(¬(r∨¬r)→(t∧s)) אמת |
|
|
| p |
s |
q |
t |
r |
¬s |
¬t |
¬r |
| T |
T |
T |
F |
F |
F |
T |
T |
| (t∧s) |
r∨¬r |
(¬(r∨¬r) |
(p∧q) |
((p∧q)→p)) |
(¬t∨¬s) |
| F |
T |
F |
T |
T |
T |
| ((¬t∨¬s)→((p∧q)→p)) |
(¬(r∨¬r)→(t∧s)) |
((¬t∨¬s)→((p∧q)→p))↔(¬(r∨¬r)→(t∧s)) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
T |
| > בדיקה: |
|
|
| > 1: לא בדקתי את הפונקציה רק את אחד האיברים... עשיתי את ההמשך ויצא נכון. תוקן. |
|
|
| > 9: עשיתי את הטבלה של הפונקציה הסופית לפי קשר אמת ששייך לסוגריים! כלומר לא זיהיתי נכון את הפונקציה הרחבה ביותר (מחוץ לכל הסוגריים). לשים לב לזה! אפשר לעבוד מהר, אבל לשים לב שמפרקים סוגריים נכון! |
|
|
תרגיל ב:
בנו את טבלות האמת של הפסוקים הבאים:
- ¬(¬¬¬p↔¬(p∨p))
| P |
¬p |
¬¬p |
¬¬¬p |
p∨p |
¬(p∨p) |
(¬¬¬p↔¬(p∨p)) |
¬(¬¬¬p↔¬(p∨p)) |
| T |
F |
T |
F |
T |
F |
T |
F |
| F |
T |
F |
T |
F |
T |
T |
F |
| 2. ¬p∧¬q |
|
|
|
|
|
|
|
| p |
q |
¬p |
¬q |
¬p∧¬q |
| T |
T |
F |
F |
F |
| T |
F |
F |
T |
F |
| F |
T |
T |
F |
F |
| F |
F |
T |
T |
T |
| 3. (¬p∧¬q)→p |
|
|
|
|
| p |
q |
¬p |
¬q |
(¬p∧¬q) |
(¬p∧¬q)→p |
| T |
T |
F |
F |
F |
T |
| T |
F |
F |
T |
F |
T |
| F |
T |
T |
F |
F |
T |
| F |
F |
T |
T |
T |
F |
| 4. (p∧¬q)∨(¬p∨q) |
|
|
|
|
|
| p |
q |
¬p |
¬q |
p∧¬q |
¬p∨q |
(p∧¬q)∨(¬p∨q) |
| T |
T |
F |
F |
F |
T |
T |
| T |
F |
F |
T |
T |
F |
T |
| F |
T |
T |
F |
F |
T |
T |
| F |
F |
T |
T |
F |
T |
T |
| 5. ((p∨q)→r)→(¬r∨p) |
|
|
|
|
|
|
| p |
q |
r |
¬r |
p∨q |
((p∨q)→r) |
(¬r∨p) |
((p∨q)→r)→(¬r∨p) |
| T |
T |
T |
F |
T |
T |
T |
T |
| T |
T |
F |
T |
T |
F |
T |
T |
| T |
F |
T |
F |
T |
T |
T |
T |
| T |
F |
F |
T |
T |
F |
T |
T |
| F |
T |
T |
F |
T |
T |
F |
F |
| F |
T |
F |
T |
T |
F |
T |
T |
| F |
F |
T |
F |
F |
T |
F |
F |
| F |
F |
F |
T |
F |
T |
T |
T |
| 6. ((p→r)∧(r→q))→(q∨¬p) |
|
|
|
|
|
|
|
| p |
q |
r |
¬p |
p→r |
r→q |
((p→r)∧(r→q)) |
q∨¬p |
((p→r)∧(r→q))→(q∨¬p) |
| T |
T |
T |
F |
T |
T |
T |
T |
T |
| T |
T |
F |
F |
F |
T |
F |
T |
T |
| T |
F |
T |
F |
T |
F |
F |
F |
T |
| T |
F |
F |
F |
F |
T |
F |
F |
T |
| F |
T |
T |
T |
T |
T |
T |
T |
T |
| F |
T |
F |
T |
T |
T |
T |
T |
T |
| F |
F |
T |
T |
T |
F |
F |
T |
T |
| F |
F |
F |
T |
T |
T |
T |
T |
T |
| 7. (p∨q)→(¬r∧¬p) |
|
|
|
|
|
|
|
|
| p |
q |
r |
¬p |
¬r |
p∨q |
¬r∧¬p |
(p∨q)→(¬r∧¬p) |
| T |
T |
T |
F |
F |
T |
F |
F |
| T |
T |
F |
F |
T |
T |
F |
F |
| T |
F |
T |
F |
F |
T |
F |
F |
| T |
F |
F |
F |
T |
T |
F |
F |
| F |
T |
T |
T |
F |
T |
F |
F |
| F |
T |
F |
T |
T |
T |
T |
T |
| F |
F |
T |
T |
F |
F |
F |
T |
| F |
F |
F |
T |
T |
F |
T |
T |
בדיקה:
1-4 - נכון
5 - לא נכון כי עשיתי r∨p¬ במקום r∧p¬ בפסוק הימני. עשיתי נכון ביחס לטעות - לשים לב!!!
6-7 - מעולה!
תרגיל ג:
- סתירה עצמית
- קונטינגנציה
- קונטינגנציה
- טאוטולוגיה
- קונטינגנציה
- טאוטולוגיה
- קונטינגנציה
בדיקה:
הכל נכון
תרגיל ד:
- .q→p ; p∨¬q שקול
| p |
q |
¬q |
q→p |
p∨¬q |
(q→p)↔(p∨¬q) |
| T |
T |
F |
T |
T |
T |
| T |
F |
T |
T |
T |
T |
| F |
T |
F |
F |
F |
T |
| F |
F |
T |
T |
T |
T |
| 2. .p∧¬q ; p∧(¬q∧p) שקול |
|
|
|
|
|
| p |
q |
¬q |
(¬q∧p) |
p∧¬q |
p∧(¬q∧p) |
p∧¬q ↔ p∧(¬q∧p) |
| T |
T |
F |
F |
F |
F |
T |
| T |
F |
T |
T |
T |
T |
T |
| F |
T |
F |
F |
F |
F |
T |
| F |
F |
T |
F |
F |
F |
T |
- .(¬p∧q)→r ; p→(q→¬r) לא שקול
| p |
q |
r |
¬p |
¬r |
(¬p∧q) |
(q→¬r) |
(¬p∧q)→r |
p→(q→¬r) |
(¬p∧q)→r ↔p→(q→¬r) |
| T |
T |
T |
F |
F |
F |
F |
T |
F |
F |
| T |
T |
F |
F |
T |
F |
T |
T |
T |
T |
| T |
F |
T |
F |
F |
F |
T |
T |
T |
T |
| T |
F |
F |
F |
T |
F |
T |
T |
T |
T |
| F |
T |
T |
T |
F |
T |
F |
T |
T |
T |
| F |
T |
F |
T |
T |
T |
T |
F |
T |
F |
| F |
F |
T |
T |
F |
F |
T |
T |
T |
T |
| F |
F |
F |
T |
T |
F |
T |
T |
T |
T |
| 4. p→(q→p) ; (p→q)→p לא שקול |
|
|
|
|
|
|
|
|
|
| p |
q |
q→p |
p→q |
p→(q→p) |
(p→q)→p |
p→(q→p) ↔(p→q)→p |
| T |
T |
T |
T |
T |
T |
T |
| T |
F |
T |
F |
T |
T |
T |
| F |
T |
F |
T |
T |
F |
F |
| F |
F |
T |
T |
T |
F |
F |
| > בדיקה: מושלם 💯 |
|
|
|
|
|
|
תרגיל ה:
א.
1. p→q
2. p
∴ q
תקף
| p |
q |
p→q |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
| ב. |
|
|
| 1. p∨q |
|
|
| 2. p→(p∧q) |
|
|
| 1. ¬p∨¬q |
|
|
| ∴ q |
|
|
| תקף |
|
|
| p |
q |
¬p |
¬q |
p∧q |
p∨q |
p→(p∧q) |
¬p∨¬q |
| T |
T |
F |
F |
T |
T |
T |
F |
| T |
F |
F |
T |
F |
T |
F |
T |
| F |
T |
T |
F |
F |
T |
T |
T |
| F |
F |
T |
T |
F |
F |
T |
T |
ג.
1. p→(q∧r)
2. ¬p∧¬r
∴ r∨¬q
לא תקף
| p |
q |
r |
¬p |
¬q |
¬r |
q∧r |
p→(q∧r) |
¬p∧¬r |
r∨¬q |
| T |
T |
T |
F |
F |
F |
T |
T |
F |
T |
| T |
T |
F |
F |
F |
T |
F |
F |
F |
F |
| T |
F |
T |
F |
T |
F |
F |
F |
F |
T |
| T |
F |
F |
F |
T |
T |
F |
F |
F |
T |
| F |
T |
T |
T |
F |
F |
T |
T |
F |
T |
| F |
T |
F |
T |
F |
T |
F |
T |
T |
F |
| F |
F |
T |
T |
T |
F |
F |
T |
F |
T |
| F |
F |
F |
T |
T |
T |
F |
T |
T |
T |
| > בדיקה: מושלם 💯 |
|
|
|
|
|
|
|
|
|
תרגיל ו:
- p∨¬p
- (p∧¬q)∨(¬p∧q)∨(¬p∧¬q)
- ¬p∨¬q
- (¬p∧q)∨(¬p∧¬q)
בדיקה: מושלם
תרגיל ז:
- נשתמש בקבוצה השלמה הנתונה כבר, AND + NOT.
- כדי להראות ש OR+NOT היא שלמה פונקציונלית, נראה שאפשר לבטא את AND באמצעות OR ו-NOT.
- p∧q
| p |
q |
p∧q |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
F |
| 4. p∨q |
|
|
| p |
q |
p∨q |
| T |
T |
T |
| T |
F |
T |
| F |
T |
T |
| F |
F |
F |
| 4. ¬(p∨q) |
|
|
| p |
q |
¬(p∨q) |
| T |
T |
F |
| T |
F |
F |
| F |
T |
F |
| F |
F |
T |
- ¬(¬p∨¬q)
| p |
q |
¬(p∨q) |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
F |
- גם מבחינת השפה הטבעית, זה עובד: להגיד "גם A וגם B" זה שקול ללהגיד "לא (לא-A או לא-B)".
ב. נתון קשר נוסף שהוא שלם פונקציונלית: "לא... או לא...", סימנו הוא ↑.
טבלת האמת שלו מחזירה T בכל מצב שבו לפחות אחד מהפסוקים הוא F (הופכית ל-OR).
צריך להוכיח שהיא שלמה פונקציונלית.
- נשתמש בהוכחה שביססנו, לפיה OR + NOT היא קבוצה שלמה פונקציונלית.
- ראשית, נביע את NOT באמצעות ↑
- ¬p - מחזיר אמת רק כשהפסוק שקרי
- p↑p - מחזיר אמת רק כשהפסוק שקרי
- שנית, נביע את OR באמצעות ↑
- p∨q - מחזירה אמת בכל מצב שאחד הפסוקים אמת, שקרית רק בשורה האחרונה
- (p↑q) - מחזירה אמת בכל מצב שאחד הפסוקים שקר, שקרית רק בשורה הראשונה
- ¬p↑¬q - מחזיר מה שצריך נו
בדיקה: לול, כמעט. עשיתי נכון את ההצרנה, אבל שכחתי שאין לי NOT כשאני רוצה להוכיח שקשר אחד הוא שלם פונקציונלית כשלעצמו... הייתי צריך להשתמש בהמרה שעשיתי ל-NOT ולהציב אותה בהמרה שעשיתי ל-OR.
אז בעצם שלב אחרון ורביעי: (p↑p)↑(q↑q)\
לשים לב שאם אני מוכיח שלמות של קשר יחיד - אין לי NOT בארסנל!