שינויים

קפיצה אל: ניווט, חיפוש

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 0

נוספו 2,131 בתים, 15:25, 11 בינואר 2023
הייתה טעות בדוגמה של CNF בC_2. התייחסות ל1 כמו שהוא ו0 כשלילה, כשזה צריך להיות הפוך.
[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]
 
סיכום הנושא המלא נמצא בדף [[88-101 חשיבה מתמטית]].
אזהרה: דף זה נועד להכיר ללומד המתחיל את החשיבה הלוגיקית הקשיחה. כיוון שמדובר בלומד המתחיל ואיננו רוצים להבריח אותו, הדוגמאות וההסברים לעיתים "מעגלים פינות" (מבחינת דיוק קשיח ופורמלי) לטובת הסבר ברור ומסביר פנים. ==פסוקים וקַשָּרִים, פרדיקטים וכַּמָּתִים, הצרנה וטבלאות אמת==
=== אטומים, פסוקים וקשרים===
אם הביטוי <math>A \leftrightarrow B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)
====תרגיל: ====הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד
פתרון:
ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>
====תכונות הקשרים====
כעת נוכל לנסח את הטענה בצורה מדויקת, תכונות הקשרים: לכל שלוש פסוקים <math>A,B,C</math> מתקיים כי:
* קיבוציות <math>(A\land B) \land C \equiv A\land (B \land C), (A\lor B) \lor C \equiv A\lor (B \lor C) </math>
פיתרון: לא. בא' יש פעמיים את אותו דבר, בגלל השקילות <math>p\to q\equiv \lnot q\to \lnot p</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>
===טענת גרירה===
ניתן להסיק: אם אני מנגן בפסנתר אני לא מנגן בתופים.
פתרון: נכון, זה לא תלוי במי זה "אני" (במילים אחרות הפסוק "(מסקנה)<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>\forall x P(x)</math> אנחנו צריכים לדעת איזה x ים "חוקיים" (בהנחה שאנחנו יודעים את P) ומכאן שנעבור להגדרות הבאות.
===הגדרות הקשורות לקבוצותתרגיל===ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים".בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל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 הינו אוסף האיברים השייכים גם לA וגם לB (מסומן <math>A\cap B</math>).
*'''איחוד''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן <math>A\cup B</math>).
*A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B).
*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\Delta B</math>).
'''תרגיל:'''
*הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB
פתרון <math>a\in A \or a\in B</math>
*הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB====תרגיל====*הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB*הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וBנגדיר פרדיקט <math>R(x,z,y)</math> המביע כי <math>x<z<y</math>.
הגדרה: קבוצה 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>. אם המשתנים מגיעים מהרציונאלים הפסוק אמת (תכונה זאת נקראת צפיפות הרציונאלים). מסקנה: צריך לדעת מאיפה מגיעים משתני הפרדיקט.
*הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וBמה לא חשוב? לא חשוב שמות המשתנים. למשל <math>\forall x\forall y \exists z : (x<y)\to R(x,z,y)</math> זה פסוק זהה לפסוק <math>\forall m\forall n \exists k : (m<n)\to R(m,k,n)</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>
שזה בעצם מהצורה (לכל כלב) * <math>\ (p \rightarrow q) \iff ((\neg q) \rightarrow (\neg p))</math>.
* באופן דומה ניתן לעשות אם הטענה: מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר
==שלילת פסוקים==
הערה: סדר הכמתים הוא חשוב (כמו בעברית) - לדוגמא: יש הבדל בין "לכל סיר קיים מכסה" לבין "קיים מכסה שמתאים לכל סיר".דוגמא: הצרן את המשפט "לכל מספר טבעי יש מספר טבעי הגדול ממנו" פתרון: <math>\forall n\in\mathbb{N}\,\exists m\in\mathbb{N}:n<m</math> לעומת זאת <math>\exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n<m</math> פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.
 
===תרגיל (בהרצאה)===
.3 נתונים 4 קלפים שבצד א יש מספר )בין 1 ל 10( ובצד ב יש צבע )ירוק או אדום(. אני טוען: "כל קלף שבצד א יש מספר זוגי הצד השני שלו ירוק".הצרינו את הפסוק בעזרת הפרדיקטים P(x) המביע "צד א של קלף x הוא זוגי" ו Q(x) המביע "צד ב של קלף x הוא ירוק". מה השלילה של הפסוק?בהיתן שרואים 2,3 ירוק ואדום. אילו קלפים הכרחי ומספיק להפוך כדי לוודא את נכונות הטענה.
====תרגיל====
הוכיחו או הפריכו:
דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה
==צורות נורמליות: CNF ,DNF(אם רלוונטי לקורס שאתם לוקחים. אם לא שמעתם על הדברים האלה - תדלגו)== 
ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.
באופן דומה נייצר <math>C_2,C_3,C_4,C_5</math> עבור שורות 2 , 5, 7 ו-8:
<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>
<math> C_4=x_1 \lor \lnot x_2 \lor \lnot x_3, C_5= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3</math>
1153426601
עריכה אחד
מקור: https://math-wiki.com/index.php?title=מיוחד:השוואה_ניידת/81657...89579