יחידה 2: לוגיקה ופסוקים

מבוא לקורס

מטרת הקורס

מטרת הקורס היא להכשיר כלים מתמטיים של מדעי המחשב:

• שפה מתמטית מדויקת
• הוכחות מתמטיות
• מושגים בסיסיים (קבוצות, יחסים, פונקציות וכו')

נושאי הקורס

1. קבוצות, יחסים והעתקות (כולל אינדוקציה)
2. מושג המספר ואלגברה בסיסית
3. שיטות מנייה והסתברות
4. קומבינטוריקה ואלגוריתמים

היגדים ולוגיקה

מוטיבציה

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

פסוק (היגד)

דוגמאות לפסוקים

הערה חשובה: כשכותבים "$x$ הוא מספר גדול מ-5", זהו משפט פתוח (או נוסחה פתוחה) -- ערך האמת שלו תלוי ב-$x$. רק כשנקבע ערך ספציפי ל-$x$, הופך המשפט לפסוק.

קשרים לוגיים (קונקטורים)

קשרים לוגיים (או קונקטורים) הם פעולות שמאפשרות לבנות פסוקים מורכבים מפסוקים פשוטים יותר.

שלילה (NOT)

הגדרה: אם $P$ הוא פסוק, אז $\neg P$ ("לא $P$") הוא פסוק ששולל את $P$.

סימון: $\neg P$ או $\lnot P$ או $\overline{P}$

וגם (AND) -- קוניונקציה

הגדרה: אם $P$ ו-$Q$ הם פסוקים, אז $P \land Q$ ("$P$ וגם $Q$") הוא פסוק שאמיתי רק אם שני הפסוקים אמיתיים.

סימון: $P \land Q$ או $P \cdot Q$ או $P \& Q$

או (OR) -- דיסיונקציה

הגדרה: אם $P$ ו-$Q$ הם פסוקים, אז $P \lor Q$ ("$P$ או $Q$") הוא פסוק שאמיתי אם לפחות אחד מהפסוקים אמיתי.

סימון: $P \lor Q$ או $P + Q$

שימו לב: זהו "או" לא מוציא (inclusive OR) -- גם אם שניהם אמיתיים, התוצאה אמת.

או מוציא (XOR)

הגדרה: $P \oplus Q$ ("$P$ או $Q$ אך לא שניהם") הוא פסוק שאמיתי אם בדיוק אחד מהפסוקים אמיתי.

סימון: $P \oplus Q$ או $P \veebar Q$

גרירה (אימפליקציה)

הגדרה: אם $P$ ו-$Q$ הם פסוקים, אז $P \rightarrow Q$ ("$P$ גורר $Q$" או "אם $P$ אז $Q$") הוא פסוק.

סימון: $P \rightarrow Q$ או $P \Rightarrow Q$ או $P \supset Q$

פירוש: "אם $P$ אמת, אז $Q$ חייב להיות אמת"

שקילות (אם ורק אם)

הגדרה: $P \leftrightarrow Q$ ("$P$ אם ורק אם $Q$") הוא פסוק שאמיתי כאשר ל-$P$ ול-$Q$ יש אותו ערך אמת.

סימון: $P \leftrightarrow Q$ או $P \Leftrightarrow Q$ או $P \equiv Q$

שקול ל: $(P \rightarrow Q) \land (Q \rightarrow P)$

טבלאות אמת

הגדרה: טבלת אמת היא טבלה המציגה את ערך האמת של פסוק מורכב עבור כל השילובים האפשריים של ערכי האמת של הפסוקים המרכיבים אותו.

בניית טבלת אמת: אם יש $n$ פסוקים אטומיים, יש $2^n$ שורות בטבלת האמת (כל השילובים האפשריים של $T$ ו-$F$).

סיווג פסוקים

• טאוטולוגיה: פסוק שתמיד אמת, לכל השמה של ערכי אמת למשתנים.

  • דוגמה: $P \lor \neg P$ (חוק השלישי הנמנע)

• סתירה: (או קונטרדיקציה) פסוק שתמיד שקר, לכל השמה.

  • דוגמה: $P \land \neg P$

• פסוק ספיק: (או מתקיים, contingent) פסוק שאינו טאוטולוגיה ואינו סתירה -- יש השמות שבהן הוא אמת ויש השמות שבהן הוא שקר.

  • דוגמה: $P \rightarrow Q$

שקילות לוגית

הגדרה: שני פסוקים $P$ ו-$Q$ הם שקולים לוגית (ונסמן $P \equiv Q$) אם יש להם אותם ערכי אמת בכל טבלת האמת.

שקול לכך: $P \leftrightarrow Q$ היא טאוטולוגיה.

שקילויות חשובות

חוקי דה-מורגן

$\neg(P \land Q) \equiv \neg P \lor \neg Q$

$\neg(P \lor Q) \equiv \neg P \land \neg Q$

חוקי הכפלה והפיצול

$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$

$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

שקילויות נוספות

$P \rightarrow Q \equiv \neg P \lor Q$

$P \rightarrow Q \equiv \neg Q \rightarrow \neg P \quad \text{(קונטרפוזיציה)}$

$P \leftrightarrow Q \equiv (P \rightarrow Q) \land (Q \rightarrow P)$

$\neg(\neg P) \equiv P \quad \text{(שלילה כפולה)}$

חוקי החילוף (קומוטטיביות)

$P \land Q \equiv Q \land P$

$P \lor Q \equiv Q \lor P$

חוקי הקיבוץ (אסוציאטיביות)

$(P \land Q) \land R \equiv P \land (Q \land R)$

$(P \lor Q) \lor R \equiv P \lor (Q \lor R)$

חוקי הזהות

$P \land T \equiv P$

$P \lor F \equiv P$

$P \land F \equiv F$

$P \lor T \equiv T$

חוקי האידמפוטנטיות

$P \land P \equiv P$

$P \lor P \equiv P$

חוקי הבליעה

$P \land (P \lor Q) \equiv P$

$P \lor (P \land Q) \equiv P$

סיכום: טבלת הקשרים הלוגיים