שינויים

אזהרה: דף זה נועד להכיר ללומד המתחיל את החשיבה הלוגיקית הקשיחה. כיוון שמדובר בלומד המתחיל ואיננו רוצים להבריח אותו, הדוגמאות וההסברים לעיתים "מעגלים פינות" (מבחינת דיוק קשיח ופורמלי) לטובת הסבר ברור ומסביר פנים. ==פסוקים וקַשָּרִים, פרדיקטים וכַּמָּתִים, הצרנה וטבלאות אמת==

<math>A\iff leftrightarrow B := </math> שטבלת האמת שלו זהה לטבלת האמת של <math>(A\Rightarrow to B)\and(B\Rightarrow to A)</math>

* מספר (טבעי) מסוים n ניתן להצגה בעזרת 2 ספרות (בבסיס עשרוני) <math>\iff</math> המספר n קטן מ 100. הפסוק יקבל ערך T רק אם שני התנאים יתקיימו ביחד. במילים אחרות, אם אחד מתקיים גם השני. במילים אחרות, אם אחד לא מתקיים והשני אז השני גם לא מתקיים.

 תכונות הקשרים:* קיבוציות <math>(A\land B) \land C =A\land (B \land C), (A\lor B) \lor C =A\lor (B \lor C) </math>== פסוקים מורכבים ====* חילופיות פסוקים יכולים להיות מורכבים יותר מאשר האטומים או חיבור של אטומים ע"י קשרים. המורכבות נוצרת ע"י הפעלה חוזרת של קשרים. במילים אחרות, נתייחס לכל אחד מהבאים כפסוק: א. אטומים ב. אם <math>A\land B =B\land Ap, A\lor B = B\lor Aq</math> * פילוג פסוקים אזי <math>A\lor (B\land C)= (A\lor Bp)\land (A\lor Cq), A\land (Bp)\lor C(q)= , (A\land Bp)\lor to (A\land Cq)</math> * כללי דה מורגן פסוקים. ג. אם <math>p</math> פסוק אזי <math>\neg lnot (A \lor Bp) = \neg A \land \neg B, \neg (A \land B) = \neg A \lor \neg B</math>פסוק. תוכיחו אחד מהם בתרגיל הבית

אם הביטוי <math>A \iff leftrightarrow B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

====תרגיל: ====הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד

הוכח ====תכונות הקשרים====כעת נוכל לנסח את הבאיםהטענה בצורה מדויקת, תכונות הקשרים: לכל שלוש פסוקים <math>A,B,C</math> מתקיים כי:* קיבוציות <math>(A\ land B) \negland C \equiv A\land (B \land C), (A \or lor B) \lor C \equiv A\neg lor (B \lor C) </math>* חילופיות <math>A \and land B\neg equiv B\land A, A\lor B \equiv B\lor A</math>* פילוג <math>A\ lor (B\land C)\equiv (A\lor B)\land (A\lor C), A\or land (B \and lor C ) \equiv (A \or land B ) \and lor (A \or land C)</math>* כללי דה מורגן <math>\ neg (A\rightarrow lor B) \equiv ((\neg A) \vee land \neg B, \neg (A \land B)\equiv \neg A \lor \neg B</math>.תוכיחו אחד מהם בתרגיל הבית ועוד כמה תרגילים למי שיש זמן - הוכח* <math>\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B))</math>.

====תרגיל====האם המשפטים הבאים שקולים: א. אם אייל שמח אז ענת גבוהה, ואם ענת לא גבוהה אז אייל לא שמח. ב. אייל שמח אם ורק אם ענת גבוהה. פיתרון: לא. בא' יש פעמיים את אותו דבר, בגלל השקילות <math>p\to q\equiv \lnot q\to \lnot p</math>. עבור: אייל לא שמח וענת גבוהה, נקבל בא' אמת ובב' שקר. ===טענת גרירה==="טענות גרירה" הם טענות נפוצות במתמטיקה. טענות אלו פשוט טוענות שמתקיים כי: אם (משהו) אז (משהו). בשביל לרמוז על נכונות הטענה מסמנים <math>A\Rightarrow B</math> להדגיש כי הפסוק <math>A\rightarrow B</math> הינו אמת. במידה ולא מגלים לכם אם טענה הגרירה נכונה או לא (או שאתם לא מאמינים למרצה) אזי עומדות בפניכם שתי אופציות: 1. אם הטענה נכונה אזי כדאי להוכיח אותה ע"י כך שתראו שאם A נכון אז גם B נכון. או בצורה פרקטית יותר: נניח שA נכון ונוכיח שגם B נכון. 2. אם הטענה אינה נכונה אזי כדאי למצוא דוגמא שתפריך אותה. דוגמא מפריכה היא דוגמא עבורה A נכון וB לא נכון. ====תרגיל====האם משני הנתונים: א. אם אני מנגן בחצוצרה אז אני לא מנגן בתופים ובפסנתר יחד. ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר. ניתן להסיק: אני לא מנגן בפסנתר אז אני מנגן בתופים. פתרון: לא, זה תלוי מי זה "אני": במידה ו"אני" לא מנגן על אף כלי (מתאים לשורה F,F,F בטבלת האמת שאטומיה הן: "מנגן בחצוצרה", "מנגן בתופים", "מנגן בפנתר") נקבל כי הנתונים (א+ב) מקבלים ערך <math>T</math> והמסקנה <math>F</math>. ולכן הפסוק "(מסקנה)<math>\to</math>(נתונים)" אינו נכון. ====תרגיל====האם משני הנתונים: א. אם אני מנגן בחצוצרה אז אני לא מנגן בתופים ובפסנתר יחד. ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר. ניתן להסיק: אם אני מנגן בפסנתר אני לא מנגן בתופים. פתרון: נכון, זה לא תלוי במי זה "אני" (במילים אחרות הפסוק "(מסקנה)<math>\to</math>(נתונים)" הוא טאוטולוגיה ולא מושפע מערכי האמת של האטומים שלו). בהינתן א+ב אנו רוצים להוכיח את המסקנה, שהיא בעצמה טענת גרירה. לכן: נניח שמנגן בפסנתר, לכן לפי ב מנגן בחצוצרה. ואז לפי א יוצא שלא מנגן בתופים או לא מנגן בפסנתר (דה-מורגן). כיון שנתון שמנגן בפסנתר מתחייב שלא בתופים. ===הכרחי ומספיק ===הערה (טרמינולוגיה): *כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא שהפסוק <math>A \to B</math> נכון. לעיתים, לצורך הדגשה מסמנים <math>A \Rightarrow B</math>*כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא שהפסוק <math>B \to A</math> נכון. לעיתים, לצורך הדגשה מסמנים <math>B \Rightarrow A</math>*כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא שהפסוק <math>B \rightarrow A</math> נכון. לעיתים, לצורך הדגשה מסמנים <math>A \iff B</math>====תרגיל====השלם את המשפט הבא: כדי שירד גשם _____ שיהיו עננים בשמים. לכן אם נסמן ע"י "יש עננים בשמים = A", "יורד גשם = B" נקבל "A____B". פיתרון: הכרחי, <math>\Leftarrow </math> ====תרגיל====השלם את המשפט הבא: כניסת המורה לכיתה הוא תנאי _____ שיהיה שקט בכיתה. לכן אם נסמן ע"י "כניסת המורה= A", "שקט בכיתה = B" נקבל "A____B". פיתרון: מספיק, <math>\Rightarrow </math> ===תרגיל===(a) כדי שלזכות בלוטו _____ למלא כרטיס לוטו. (b) כדי שהיה שקט בכיתה _____ ללחוץ mute all (c) לקבל ציון עם 3ספרות בקורס _____ לקבל 100 בקורס.

===דרכי הוכחה===הוכח שהפסוקים הבאים הינם טאוטולוגיות:*<math>(A\rightarrow B) \iff equiv (\neg B \rightarrow \neg A)\equiv ((\neg A) \vee B)</math>*(הנחה בשלילה) <math>A \iffequiv (\neg A \rightarrow F)</math>*<math>(A\lor B) \iffequiv (\neg A \rightarrow B)</math>

===פרדיקטים וכמתים===בניגוד לאטומים שהם ללא משתנים ה'''פרדיקטים''' הינם פונקציות התלויות במשתנים. לדוגמא ניתן להגדיר את הפרדיקט <math>S(x)</math> להיות פרדיקט שמביע כי x הינו סטודנט באוניברסיטה("מביע" פירושו שאם x הוא סטודנט אזי <math>S(x)</math> הוא T ואם x אינו סטודנט <math>S(x)</math> הוא F).

כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט <math>S(x,y)=</math>שמביע כי <math>x<y</math> יהיה נכון במקרה ש <math>S(2,3)</math> ולא נכון במקרה ש <math>S(3,2)</math>. כלומר לכל הצבה במשתני הפרדיקטים נקבל פסוק. הערה: משמשים בקשרים גם בפרדיקטים למשל <math>S(x,y)</math> הפרדיקט המוגדר <math>(x>0 ) \land (x<y)</math>

* <math>P(x)</math> הוא הפרדיקט המביע כי"x" הוא ראשוני".* <math>Q(x)</math> הוא הפרדיקט המביע <math>\forall a,b : p|ab \Rightarrow (p|a \lor p|b)</math>

===הגדרות הקשורות לקבוצותתרגיל===ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים".בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות (קבוצות נוהגים לסמן בין 2 סוגריים מסולסלות): הצרינו את הפסוקים

<math>\{1(a) "כל שתי נקודות שונות קובעות ישר" באמצעות הפרדיקט הדו-מקומי P(x,\mathrm{horse},3\}</math>, <math>\{1,2,3\}</math> l) - x נמצא ב l כאשר המשתנה x הוא נקודה ו<math>\{1,\{2,3\},\{\}\}</math>l הוא ישר.

איבר ה'''שייך''' לקבוצה אנו מסמנים בסימן <math>\in</math>. למשל <math>1\in\{1,2,3\}</math>, ואילו <math>4\notin\{1,2,3\}</math>. שימו לב שגם <math>1\notin\{\{1,2,3\}\}</math> שכן האיבר היחיד בקבוצה זו הינה הקבוצה <math>\{1,2,3\}</math>.*אומרים שקבוצה A '''מוכלת''' בקבוצה B (מסומן <math>A \subseteq B</math>b) אם "כל האיברים בA הם גם איברים בB. שתי נקודות שונות קובעות ישר אחד ויחיד"

הגדרה: קבוצה A מוכלת בקבוצה B אם בB נמצאים כל האיברים מA (למשל הטבעיים מוכלים בשלמים האם הפסוק <math>\mathbb{N}forall x\subseteqforall y \mathbb{Z}exists z : (x</math>, והשלמים מוכלים בממשיים <math>y)\mathbb{Z}\subseteq\mathbb{to R}(x,z,y)</math>).*הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וBאמיתי?

פתרון: <math>\forall c [c\in C \rightarrow אם המשתנים מגיעים מהשלמים הפסוק שקרי (c\in A \and c \in Bשהרי לא קיים z עבור x=1,y=2)]</math>. אם המשתנים מגיעים מהרציונאלים הפסוק אמת (תכונה זאת נקראת צפיפות הרציונאלים). מסקנה: צריך לדעת מאיפה מגיעים משתני הפרדיקט.

דוגמאות מילוליותחשוב גם הסדר, והכוונה לשני דברים:*"כלב נובח אינו נושך" אם"ם "כלב נושך אינו נובח"סדר הופעת הכמתים, למשל הפסוק <math>\forall x\exists z \forall y : (x<y)\to R(x,z,y)</math> הוא שקרי גם כשהמשתנים מגיעים מהרציונאלים (שהרי אפשר למצוא y שבין x לz)*סדר המשתנים בתוך הפרדיקט, למשל הפסוק <math>\forall x\forall y \exists z : (x<y)\to R(x,y,z)</math> נכון גם כשהמשתנים מגיעים מהשלמים.

הסבר ==== תרגיל ====הוכח או הפרך (משתני הפרדיקט נלקחים מהטבעיים): א. <math>(\forall n (P(n) \lor Q(n))) \Rightarrow ((\forall n P(n)) \lor (\forall n Q(n)))</math> ב. <math>(\forall n (P(n) \lor Q(n))) \Leftarrow ((\forall n P(n)) \lor (\forall n Q(n)))</math> פיתרון: א. הפרכה. ניקח את <math>P(n)</math> להיות <math>1</math> על הזוגיים ו-<math>0</math> על אי-זוגיים, ו-<math>Q(n)</math> להפך. אכן כל מספר טבעי הוא זוגי או אי-זוגי, אך זה לא נכון שכל מספר הוא זוגי או שכל מספר הוא אי-זוגי. ב. הוכחה: יהי <math>n</math>. אם מתקיים <math>P(n)</math> אז בפרט מתקיים <math>P(n) \lor Q(n)</math> כדרוש. אחרת, לפי השקילות <math>a\lor b \equiv \lnot a \rightarrow b</math>, מתקיים שלכל מס' טבעי, ובפרט עבור <math>n</math>, מתקיים <math>Q(n)</math>, ולכן מתקיים <math>P(n) \lor Q(n)</math> כדרוש. ==== תרגיל ====הטענה: "כלב נובח אינו נושך" אם"ם "כלב נושך אינו נובח" צריכה להיות מנוסחת בצורה פורמלית יותר כ: "עבור כל כלב מתקיים כי: (כלב נובח אינו נושך) אם"ם (כלב נושך אינו נובח)" נוכיח את הטענה: נסמן ב- D את קבוצת כל הכלבים ב -A את הנובחים וב- B את הנושכים אז הדוגמא היא בעצם <math>\forall x\in D :((x\in A\to x\notin B)\iff (x\in B \to x\notin A)) </math>

* באופן דומה ניתן לעשות אם הטענה: מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר

*===תרגיל(בהרצאה)===.3 נתונים 4 קלפים שבצד א יש מספר )בין 1 ל 10( ובצד ב יש צבע )ירוק או אדום(. אני טוען: "כל קלף שבצד א יש מספר זוגי הצד השני שלו ירוק".הצרינו את הפסוק בעזרת הפרדיקטים P(x) המביע "צד א של קלף x הוא זוגי" ו Q(x) המביע "צד ב של קלף x הוא ירוק". מה השלילה של הפסוק?בהיתן שרואים 2,3 ירוק ואדום. אילו קלפים הכרחי ומספיק להפוך כדי לוודא את נכונות הטענה. ====תרגיל====הוכיחו או הפריכו: <math>\lnot (\forall a\in \mathbb{N} \exists b\in \mathbb{N} (a|b\rightarrow (a\leq b\land a+b<a\cdot b)))</math> פיתרון: ראשית נראה מה הטענה בעצם אומרת: <math>\exists a\in \mathbb{N} \forall b\in \mathbb{N} (a|b \land (a>b \lor a+b\geq a\cdot b))</math> שימו לב שנעזרו בשקילות <math>\ (A\rightarrow B) \equiv ((\neg A) \lor B)</math> ובחוקי דה-מורגן. כעת נשים לב שאם <math>a|b</math> אז <math>a\leq b</math> ולכן כדי שזה יהיה נכון צריך שיתקיים <math>a+b\geq a\cdot b</math> וזה אכן קורה עבור <math>a=1</math>. ====תרגיל====הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו"

==צורות נורמליות: CNF ,DNF(אם רלוונטי לקורס שאתם לוקחים. אם לא שמעתם על הדברים האלה - תדלגו)== 

<math>C_2= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3, C_3=\lnot x_1\lor \lnot x_2 \lor x_3</math>