אנחנו נחכה כמה דקות, שיקנסו, לדבר היום על משמעות סמנטיקס בתחשיב הפסוקים. תודה. תודה.
שוב בוקר טוב לכולם, תודה רבה שבאתם. מה שאנחנו נעשה היום, כאמור, נדבר על Semantics and Propositional Logics, כלומר על משמעות בתחשיב הפסוקים. אמרנו שיש שבעצם אנחנו הולכים ללמוד בקורס שתי לוגיקות עיקריות, אחת תחשיב הפסוקים והשנייה תחשיב היחסים, ובכל אחת משתי הלוגיקות האלה אנחנו מתכוונים לדבר על תחביר ועל משמעות.
אוקיי? אז התחלנו לדבר על תחביר, כלומר על איך... על מה זה פסוק מוגדר היטב, מה בעצם הם המשפטים שאותם אנחנו, לא המשפטים, הפסוקים, הטענות שבהן אנחנו נתעסק, הנוסחאות, זה התחלה של התחביר, הוא משמש.
כבסיס גם לתכביר וגם למשמעות. כשאנחנו אומרים תכביר, בדרך כלל אנחנו מדברים על מערכת ההוכחה של התכביר. מדברים על משמעות, על מערכת ההוכחה של המשמעות.
כשהמערכת ההוכחה אנחנו אמרנו בדיוק מה זה. זה כאשר, זה מתי מסיקים הסקנות. אז היום אנחנו נסביר בדיוק מתי מסיקים את המסקנות בתחשיב הפסוקים.
השיעורים יתחילו תמיד במין חזרה על מה שהיה בשיעור הקודם, זה כמובן הזדמנות לשאלות, אבל כמובן גם לא צריך לחכות לזה שאני אחזור על זה ואז לשאול, אלא אפשר לשאול במהלך ההמצאה. טוב. שוב אני מזכיר, אם מישהו שכח, אנחנו לא מרימים יד פה, לא משתמשים בצ'אט, אלא פותחים מיקרופון ומדברים.
בבקשה. טוב, זה לא שייך לסמסטר הזה, והנה אנחנו מתחילים בקצת תזכורות. אז דיברנו על קבוצות ופעולות על קבוצות, אז פעולת החיתוך. איבר שייך לחיתוך של זוג קבוצות, אם ורק אם הוא נמצא גם בקבוצה הראשונה וגם בשנייה, איחוד אם הוא נמצא או בראשונה או בשנייה, או במקרה בשתיהן, אפרש, איבר נמצא באפרש אם הוא נמצא בקבוצה הראשונה ולא נמצא בשנייה, כן?
כלומר, אם הוא במקרה בחיתוך, אז הוא לא באפרש, אוקיי? ומשלים, על מנת לדבר על משלים חייבים שתהיה איזושהי קבוצת עולם והמשלים הוא פשוט כל העברים שנמצאים בעולם אבל לא בקבוצה שלנו X שייך ל-A משלים, אם ורק אם X שייך לעולם פחות A הראינו דוגמה של הוכחה הוכחה שה... חיתוך של A עם B ייחוד C הוא כמו הייחוד של A חיתוך B עם A חיתוך C.
מה שאני רוצה לעשות פה זה שתיק את כולם, כולם עכשיו שקטים אבל יכולים לפתוח מיקרופון כמו שאמרתי. אז איך מוכיחים את זה? בשביל להוכיח שוויון של קבוצות, יש להוכיח אוכחה, אכלה דו-כיוונית.
איך מוכיחים אכלה? אנחנו בוחרים איבר שרירותי מהקבוצה השמאלית, ומראים שהוא שייך לקבוצה הימנית. בגלל שבחרנו איבר שרירותי, זה אומר שכל איבר בקבוצה השמאלית שייך לאיבר הימנית. שרירותי זה עבר כלשהו. אוקיי, במדעי המחשב דרך אגב, מאוד מאוד חשובה הקפדה על המילה שרירותי לעומת המילה רנדומי שיש לה משמעות באנגלית ארביטררי לעומת רנדום.
אוקיי, אז אנחנו מדברים על איבר X, האיבר X אנחנו יודעים שהוא שייך לחיתוך של A עם בייחוד C, אנחנו רוצים שהוא שייך, רוצים להראות שהוא שייך לביטוי מימין, אז אנחנו מסתכלים על הגדרה של החיתוך, על פי הגדרה של החיתוך הוא חייב להיות שייך ל-A, וחייב להיות שייך לאיחוד של B עם C, אז X שייך ל-A, וגם X שייך לאיחוד של B עם C, אז זה כאלה הגדרה של האיחוד. הגדרה של האיחוד אומרת או שהוא שייך ל-B או שהוא שייך ל-C. אם הוא שייך ל-B, סימן שהוא גם שייך ל-A וגם ל-B, כלומר הוא שייך לחיתוך של A עם B.
אם הוא שייך ל-C, סימן שהוא שייך גם ל-A וגם ל-C, כלומר הוא שייך לחיתוך של A עם C. כיוון שאו אחד או שתיים בהכרח מתקיימים, אז X בהכרח שייך או לחיתוך של A עם B או לחיתוך של A עם C. ולכן הוא שייך לאיחוד של החיתוכים כמו שרצינו.
אוקיי? אז זה כיוון אחד. הכיוון ההפוך, אני מניח שגם שבוע שעבר אמרתי את זה, כיוון ההפוך דומה ואפשר לעבור עליו פה.
שנה הבאה אני אנסה לעבור על כיוון שונה. אוקיי, אז איך מוכיחים מה שאנחנו... קוראים לפעמים קייס אנליסיס, כן?
נניח ש-A נכון וגם B נכון, אבל אנחנו לא יודעים איזה מהם, אנחנו רוצים לראות את גמא, אז אנחנו אומרים שמי אלפא, A ו-B אמרתי, אלפא ובטא, כן? אנחנו אומרים שמי אלפא אנחנו יכולים, שאלפא אומרת את גמא, או כן, שאם אלפא אז גמא, וגם שאם בטא אז גמא. ואז אנחנו מסיקים את גמא. אם במקרה גם אלפא וגם פטא נפונות, אז לא נורא, הוכחנו פעמיים, כל מעולה. אוקיי, אז קצת לגבי ההוכחות שעשינו, הבוקר, ועשינו בשבוע שעבר, אז זו צורה שכותבים את זה בלוגיקה, כן?
הצורה היא, אם מ-A אנחנו הראינו את B, או אם מ-A נובעת B, אז אנחנו מסיקים, כמו קו שבר הזה אומר שאנחנו מסיקים שהראינו את הטענה, אם A אז B. אוקיי? שוב, אלה חוקים לא פורמליים, אנחנו, כל החוקים האלה נעשה פורמליים במהלך הסימנסטר, אלה חוקים לא פורמליים שהשתמשנו בהם הבוקר, השתמשנו בשבוע שעבר, והשתמשתם בהם כולכם במהלך כל הלימודים שלכם באוניברסיטה וגם הרבה לפני, אוקיי?
שוב. מ-A אפשר להסיק את B, כלומר אפשר להסיק את אם A אז B. זה דומה למה שאנחנו נקרא יותר מאוחר, כיוון אחד של משפט הדדוקציה. אם נכון ש-AX, אם נכון ש-AX, אם נכון ש-AX, אם נכון ש-AX, ש-ax, אז נכון ש-ax לכל x, אוקיי? אלה הדברים שהשתמשנו, עוד דברים שהשתמשנו, מה שהרגע הראינו, אם הצלחנו להראות את a והצלחנו להראות את b, אז הצלחנו להראות את a וגם b, אוקיי?
והדבר העיקרי, קייס אנליסיס, חלוקה למקרים, הצלחנו להראות את A או B, והצלחנו להראות את אם A אז C וגם אם B אז C, אז בעצם הצלחנו להראות את C. עוד פעם, הצלחנו להראות את A או B, והצלחנו להראות את שתי הטענות, אם A אז C וגם אם B אז C. אז הצלחנו לראות את C.
אוקיי, אז אלה החוקים בצורה לא פורמלית, ואנחנו נסה לפרמל אותם במהלך הסמסטר. אוקיי, אני מזכיר משהו שכנראה עשיתם בבדידה, כיוון שזה היה מזמן, אז אני חוזר על זה. קבוצות בנויות אינדוקטיבית. מה זה קבוצה בנויה אינדוקטיבית? קבוצה בנויה אינדוקטיבית, אם יש לנו בסיס לקבוצה, כלומר, איזשהו עבר אחד לפחות, או, כן, אחד לפחות שנמצא בקבוצה, ויש לנו איזשהו כלל גזירה, כלל יצירה, induction rules.
ונתן איזשהו עבר בקבוצה, איך אנחנו בונים עבר אחר. כלל גזירה יכול להיות כמובן יחיד, ויכולים להיות רבים. לדוגמה, וכמובן יש את ההנחה האימפליסית פה, ההנחה המובלעת, שאין עוד עברים בקבוצה.
רק העברים שאפשר ליצור אותם בעזרת או שנמצאים בבסיס, או שאפשר ליצור אותם מעבר כל מה שנמצא בבסיס, ואיזושהי סדרה של ליצור עברים אחרים עד שמגיעים אליהם. אולי דוגמה פשוטה, איך יוצרים את קבוצת הטבעיים, מי שרוצה לתת הגדרה אינדוקטיבית לקבוצת הטבעיים. הבסיס הוא אפץ וכל פעם מוסף ים אחד.
נהדר. בסיס הוא 0 שייך לקבוצה הטבעיים, וכלל הגזירה הוא אם איבר שייך לקבוצה הטבעיים, אז אם נוסיף לו 1 נקבל איבר בקבוצה הטבעיים. מעולה. סימונים, אנחנו מסמנים ב-IAP את הקבוצה שהיא נגזרת, את הקבוצה האינדוקטיבית, שה-A זה קבוצת האטומים שלה. ו-P זה קבוצת הכללים שלו.
אוקיי. הנה דוגמה לזה, הנה דוגמה לקבוצה המוגדרת אינדוקטיבית, הקבוצה היא קבוצה של מכרוזות, אוקיי? מה זה מכרוזת?
מכרוזת זה אוסף אותיות מסודר, אז כל אוסף כזה הוא עבר בקבוצה. ה-A'ב'שלנו הוא א'ב'שיש בו רק M, I ו-U, אלה שלושת האותיות היחידות, התווים היחידים שניתנים לשימוש, אוקיי? ובשביל להגדיר את הקבוצה אנחנו נצטרך להגדיר מה נמצא, איזה מכרוזות נמצאות בסיס, ואיזה מכרוזות נמצאות, ואיזה כללי יצירה יש.
אז בבסיס שלנו יש את המכרוזת MI בלבד, ויש לנו כללי יצירה, יש לנו ארבעה כללי יצירה. מהם כללי יצירה? מותר להוסיף u, u זה אחת מהשלושת האותיות שיש, מותר להוסיף u בסוף המילה, או בסוף המחוזת, בתנאי שהיא נגמרת, המילה באות i.
כלומר, אם יש לנו x i, אנחנו יכולים לגזור את המילה x i u. זה מילה חדשה, אם המילה x i הייתה, המילה x i u היא מילה חדשה. מה זה x?
X זה מחרוזת כלשהי, לא חשוב מה, לא חשוב כמה אותיות יש בה. יכול להיות 0 אותיות, 0 זה גם מחרוזת, מחרוזת בת 0 אותיות. יכול להיות אות אחת, שתי אותיות, שלוש אותיות או מחרוזת ארוכה כרצוננו.
כל ה-X נשארת כמו שהיא וגם ה-I נשאר, רק אנחנו מוסיפים את ה-U בסוף. זה כתוב ככה, כיוון שאנחנו חייבים שיהיה I בסוף בשביל שאפשר להוסיף את ה-U. אז זה הכלל הראשון.
רק לעל השני, אם במקרה המכרוזת מתחילה באות M, אז מותר להכפיל את כל המכרוזת חוץ מה-M. M ו-X אחריה, מותר להכפיל את כל המכרוזת. שוב, X זה מכרוזת כלשהי. אם במקרה היא ריקה, אז לא עשינו כלום פה, כי הכפלה שהיא מכרוזת ריקה זה עדיין ריק.
אבל אם היא ארוכה כמה שהיא תהיה ארוכה, היא בדיוק מוכפלת. אז זה הכלל השני, כלל השלישי, להחליף שלושה איים רצופים, אם יש לנו מקרה שלושה איים רצופים, אפשר להחליף אותם באות U, אז X לושה איים, Y חץ, X, U, Y, שוב, X ו-U מכוזות כלשהן, לא אומרים לנו, אין לנו שום בקשה מהן, וכלל האחרון, אם יש לנו פעמיים U רצוף, מותר לבחוק אותם. אלה ארבעת הכללים. איזה מכרוזות יש בקבוצה?
אז בואו תעזרו לי לכתוב מכרוזות בקבוצה. אני כותב את הראשונה, את המכרוזת הראשונה שיש בקבוצה. זה קל מאוד, אני מסתכל על הבסיס ואני רואה שהם. אה, איזה מכרוזת. איזה עוד מכרוזות יש?
שוב, אה, אולי לא אמרתי, אני אדגיש. מותר לנו לבחור כל כלל שאנחנו רוצים. כמה פעמים שאנחנו רוצים ולהפעיל. כל פעם אנחנו בוחרים איזה כלל שנרצה ונפעיל.
אז מי רוצה לבחור איזשהו כלל ולהפעיל וליצור מכרוזות נוספות. אורן, תוכל להסביר עוד פעם מהמקרה בסיס? כאילו באיזה מכרוז אנחנו יכולים להתחיל? כן, המקרה בסיס זה מה שמוגדר ב-A פה, זה הבסיס, זה האטומים. במקרה שלנו זה אך ורק המכרוזת MI.
במקרה בסיס שדיברנו לפני שנייה, היה לנו את הטבעיים, אז הבסיס היה, המספר 0 הוא מספר טבעי. אז כרגע אם אנחנו רוצים להפעיל את הכללים האלה, אנחנו יכולים להפעיל רק על המכרוזת MI. ברגע שנפעיל פעם ראשונה, כבר היינו שתי מכרוזות, ואז צריך לבחור על איזה מכרוזת אנחנו רוצים. מה שאנחנו רוצים כל אחת מהשתיים, ולפעיל כל אחת מהארבע שיכול להתאים.
ואחרי שיהיו לנו 34 מילים, אז על כל אחת מ-34 נוכל לבחור כל אחת מארבעה כללים. בסדר? אז כרגע מחוזתי רק עם I. זה M-I-U, גם יכול להיות. אחלה, מי אומר את זה?
עידו. עידו, מאיפה אתה יודע ש-M-I-U יכולה להיות? לפי הכלל הראשון אם זה נגמר בהי אז אפשר להוסיף יו בסוף יפה מאוד יפה מאוד. מה שעידו עשה, הוא הסתכל על הכלל הראשון ואמר שאם הכרוזת נגמרת בעי, מותר להוסיף U בסוף, אז אם MI היא מכרוזת, סימן שגם MIU היא מכרוזת. מעולה.
עוד מכרוזות? MIU, IU. MIU, IU. תודה, נתלי.
למה את חושבת שזו מכרוזת חוקית? לפי הכלל השני. לפי הכלל השני, על איזה מכרוזת הפעלת אותה? על IU. על המכרוזת M-I-U.
אוקיי? נתנית לקחה את המכרוזת M-I-U, היא כבר מכרוזת שהיא נמצאת בקבוצה אנחנו יודעים, ומותר להפעיל את הכלל השני, למשל, כי היא מתחילה ב-M. אז M-I-U M-I-U. יופי. עוד מכרוזת?
M-I-U. כן, שדן? M-I-I מהכלל השני.
M-I-I מהכלל השני, כלל שני על איזה מכרוזת הפעלת? המכרוזת הראשונה, כלו I. אוקיי, אז בחרת את המכרוזת M-I, והפעלת את הכלל השני עליה בשביל להגיע ל-M-I-I. מעולה, עוד רעיון.
עוד, קדימה, מחוזת אחרונה עכשיו נכתוב, לא בצ'אטים, צ'אטים לא יודעים, רק לפתוח מיקרופון. אפשר להכפיל עוד פעם את העיים. גיא, אני מתקשה לשמוע אותך עוד פעם. אפשר להכפיל עוד פעם את העיים, נגיד ב-M עם השני עיים להפוך את זה ל-M עם ארבע עיים. אוקיי, אפשר לקחת למשל את המילה האחרונה שיצרנו, את M-I-I, ולהפוך אותה בעזרת הכלל השני ל-M-I-I-I-I, יופי.
ואפשר עכשיו, עכשיו אני אפעיל, אני יכול לקחת את המילה הזו, את המילה האחרונה שיצרנו, M ו-4-I, ולהפעיל את ה... כלל השלישי, שימו לב, עכשיו כשאני מפעיל את הכלל השלישי, אני יכול להפעיל אותו בשתי צורות, כשיש לי פה ארבעה עם רצופים ולא שלושה. אני יכול לגזור גם את M, I, U, אבל זה כבר גזרתי קודם, זה לא מעניין. אבל אני יכול גם לגזור את M, U, I, אוקיי?
כי יש לנו גם פה שלושה וגם פה שלושה, יש לנו שתי שלושות רצופות. ברביעי הרצופה, בסדר? אבל פה אנחנו נפסיק לעשות את זה ביחד, ועכשיו כל אחד לוקח דף ועת ועושה את זה לבד.
מה אנחנו עושים? מה שאנחנו עושים זה אנחנו שואלים שאלה. השאלה היא, האם המכרוזת MU שייכת לשפה שהרגע הגדרנו?
בואו נכתוב שוב את השפה, הנה השפה. השפה זה הבסיס שלה ואלה הכללים. האם אפשר לגזור את המכרוזת MU? אז ניתן לכולם שתי דקות עם דף ועד, כל אחד מנסה ומי שיש לו תשובה מתפרץ. מי שיש לו תשובה אומר שיש לו.
אוקיי? בהצלחה. אוקיי, יש התקדמות?
מישהו הצליח לגזור? מ-U? מישהו... אפשר לנוסות? כן, בטח.
לקחתי, הפעלתי פעמיים על המחוז את A, את הכלל השני, שבחרתי רק את I, ואז קיבלתי M עם שלושה I אחריו. לא הבנתי. רגע, רגע, לא הבנתי. בחרתי את הכלל השני של הכפלה.
כן. ובחרתי X להיות איי. אם עושים פעמיים הכפלה מ-1, אני מגיע ל-4, איך אתה מגיע ל... לא, בחרתי רק את איי. מה זאת אומרת בחרת רק את איי?
בחרתי X להיות איי, שהוא לא יהיה כאילו... לא, לא, לא, אנחנו לא בוחרים X, אנחנו מסתכלים, אוקיי, אז בואו נשים לב עוד פעם מה הכללים, אוקיי? הכלל הראשון, אנחנו, אם החוזת נגמרת ב-איי, אנחנו יכולים להוסיף U. הכלל השני, אם החוזת מתחילה ב-M, אנחנו יכולים להכפיל את כל המכרוזת, חוץ מתאים.
אוקיי? חייב לחפול את כל ה... הבנתי.
חייב לחפול, זה הכלל, כן. בסדר? אוקיי. אז, אז, אז זו בעיה קשה. הבעיה הזאת, קוראים לשפה הזאת שפת המו, והסיבה שהיא שבעיה קשה היא בגלל שבעזרת הכללים של המערכת פה, בעזרת כללי היצירה בלבד, אנחנו לא יכולים להראות שבעצם אי אפשר ליצור את MU.
או במילים אחרות, הכללים פה יאפשרו לנו אך ורק ליצור איברים, הם לא יאפשרו לנו לראות שאיזשהו איבר אי אפשר ליצור. על מנת להוכיח שאיבר אי אפשר ליצור, אנחנו חייבים לצאת שנייה מהמערכת ולהסיק מסקנה על המערכת, לדבר על המערכת מבחוץ. אז זה מה שאנחנו נעשה, אנחנו ננסה למצוא...
אין וריאנטה, שמורה, שמתקיימת עבור כל המילים שאפשר לגזור מהמערכת, היא חייבת להתקיים, אבל היא לא מתקיימת למילה שאנחנו רוצים להוכיח, למילה מו. אם נצליח למצוא כזה דבר, אז הצלחנו להוכיח שהמילה לא קיימת. אוקיי? וזה תמיד המקרה, זה תמיד המקרה בקבוצות מותרות אינדוקטיבית, זה תמיד המקרה, ומה שאנחנו עושים, אנחנו עושים אינדוקט קצת מבנה, אנחנו מראים שהשמורה מתקיימת עבור הבסיס, ומראים שכל אחת מהגזירות, כל אחד מכללי הגזירה, שומר על השמורה, כלומר, אם מתקיימה הכלל, אם מתקיימה השמורה לפני, היא תתקיים אחרי. שוב, שמורה זה אין וריאנט, אז כל מה שצריך זה למצוא את השמורה הנכונה.
ובמקרה הזה, השמורה הנכונה תהיה, בואו נסתכל מה מספר העיים בכל מכרוזת. אוקיי, אז מה מספר העיים בכל מכרוזת? במכרוזת הבסיס, מספר העיים הוא אחד, אוקיי?
המכרוזת הראשונה לא משנה את מספר העיים, היה לנו איזשהו מספר כלשהו והוא נשאר. המכרוז, סליחה, לא מכרוזת, הכלל הראשון. הכלל השני, אם מספר, אוקיי, לא משנה מה מספר העיים היה קודם, אנחנו מכפילים אותו.
הכלל השלישי, אנחנו מורידים שלוש ממספר 2. הכלל הרביעי שוב לא משנה. אז יש לנו בהתחלה אחד, אנחנו יכולים להכפיל אותו או להוריד ממנו שלוש. נכון? אוקיי?
זו האפשרות היחידה של להשתנות, שמספר 2 משתנה. אז הוא או אחד, או מכפילים אותו, אז הוא שתיים, או ארבע, או שמונה, או... וכולי, 16 וכולי, ו...
יש לנו עוד אפשרות להוריד שלושה, אז אם היה לנו 16 עיים, אז אפשר להגיע ל-13, אוקיי? ואחר כך ל-12, בסדר? אוקיי.
מה אופייני לכל המספרים האלה שאמרתי, וגם לא אופייני ל-MU, בקשר למספר עיים? כלומר... מה המספר 2 ב-MU? הוא 0. אז מה אופייני ל-0 ולא אופייני למספרים שאמרתי?
מתחלק ב-2 אולי? אז מתחלק ב-2, 0 מתחלק ב-2, ואמרנו שאפשר להכפיל אותו, אז אם הוא 1, אז נכפיל. אם הוא מחפיל אותו, אז הוא יהיה 2, אז הוא כן מתחלק ב-2.
אבל את, שירה, מאוד מאוד חמה, זהירות לא לקבל קביעה. היא פשוט לא מעצורה של 2N-3K. זה נכון, זאת אומרת, צורה ב-2N-3K, אבל זה... זאת אומרת, זה נכון לגמרי, אבל אמרתי לשירה שהייתה מאוד מאוד חמה, אז תן לשירה לזה, ל...
לתת את ה... לא, התכוונתי כאילו שאפשר להגיע ככה ל-0. נכון, אפשר להגיע ככה ל-0, אבל למה? אתה צולק, אי אפשר להגיע ככה ל-0.
אבל השאלה היא למה אי אפשר להגיע ל-0? אז שירה הרנו שהוא יכול להתחלק ב-2, אבל במה הוא... במה הוא לא יכול...
הוא לא מתחלק ב-3. תודה רבה. זו לא הייתה שירה, נכון? מי זו הייתה?
מי דיברה? יעל. יעל, תודה יעל.
נכון, הוא לא מתחלק בשלוש, כן? שימו לב, מספר העיים בהתחלה הוא אחד, הוא יכול להיות מוכפל, ואפשר להוריד ממנו שלוש. אז הוא בהתחלה לא מתחלק בשלוש.
אם אנחנו מכפילים מספר שלא מתחלק בשלוש, אז הוא גם כן לא מתחלק בשלוש, נכון? תחשבו על, תוכלו לחשוב על זה או על חלוקה לגורמים, פירוק לגורמים של מספר כלשהו, אין את שלוש בין הגורמים הראשונים שלו, אנחנו לקחנו את כל הגורמים הראשונים והוספנו את הגורמים שתיים, עדיין אין את שלוש, נכון? או אפשר גם לחשוב על זה אם חושבים על חשבון מודולרי, אם יש לו שרית אחת, נכפיל אותו, תהיה לו שרית שתיים, יש לו שרית שתיים, נכפיל אותו, תהיה לו שרית אחת.
שרית אחת נכפיל שרית 2, שרית 2 נכפיל שרית 1, אף פעם לא יגיע לשרית 0. וכמובן שאם מורידים 3 ממספר שלא מתחלק בשלוש, אז הוא עדיין לא יתחלק בשלוש. לא חשוב מה השרית, מורידנו 3, הוא עדיין לא יתחלק בשלוש. אז זו בדיוק ההוכחה, שוב, כיוון שאך ורק הכלל השני והשלישי הם מה שמשנים את מספר ה-I, אוקיי? וההוכחה בשלמותה, אם אנחנו רוצים להגיד את ההוכחה בשלמותה, אז זו קבוצה שבנייה אינדוקטיבית, אז בשביל להראות שכל העברים בקבוצה הזאת מקיימים את השמורה, אז צריך להראות ש...
הבסיס מקיים את השמורה, כן? כל אחד מהבסיסים, במקרה שלנו הבסיס זה רק, הבסיס זה רק המילה mi, כן? אז כל אחד מהאיברים בבסיס, וכל אחת מהגזירות, כל אחד מכללי היצירה שומר על השמורה, אוקיי? אז בדקנו שmi, מספר i לא מתחלק ב-3, והכלל... כלג זירה הראשון לא משנה את מספר העין, ולכן אם הוא לא התחלק בשלוש קודם, אז הוא גם לא התחלק בשלוש אחר כך.
כלג זירה השני, השני, מכפיל את מספר העין, אבל אם מכפילים מספר שלא מתחלק בשלוש, אז מקבלים מספר שלא מתחלק בשלוש. כלל השלישי מוריד שלוש ממספר העין, אז אם מספר כלשהו לא התחלק בשלוש, אחרי שנוריד ממנו שלוש, הוא עדיין לא התחלק בשלוש, והכלל הרביעי לא משנה את מספר העין, ולכן גם הוא... טוב לנו וזו ההוכחה.
שוב, ברגע שהבנו את התשובה, אני מניח שכולנו הבנו את ההוכחה צ'יק צ'אק, ואולי לא הבנו למה חזרנו להוכחה כל כך הרבה פעמים, אז הסיבה היא שההוכחה, מה שרצינו להראות, זה איך מוכיחים שאיבר לא שייך לקבוצה במקרה של קבוצה בנייה אינדוקטיבית. אוקיי. עוד קצת קבוצות בניות אינדוקטיבית, אז אם יש לנו את הקבוצה S, שהיא 3, 7, 11, 15 וכו, אפשר לדבר על קבוצה שבנייה אינדוקטיבית, הקבוצה S, במקום לתאר אותה ככה, אנחנו מתארים אותה, אנחנו אומרים ש-3 זה הבסיס, 3 שייך ל-S, ואם איבר שייך ל-S, אז האיבר ועוד 4 שייך ל-S, אוקיי? לא תמיד בנייה אינדוקטיבית זה הבחירה הראשונה שלנו, אבל במקרה הזה למשל, זו בחירה טובה יותר. כי פה יש פה שלוש נקודות, ואולי אתם ואני חושבים שהבא בתור יהיה 19 וכו', אבל יכול להיות שאחרים חושבים שדווקא משהו אחר יהיה פה בשלוש נקודות.
פה הם לא יכולים לחשוב את זה. מכרוזות, אני מקווה שאתם כבר מכירים, ואם לא אז אני מציג לכם פה, הנה קריאש קורס בזה, מה זה מכרוזות במדעי המחשב. המכרוזת אפסילון זה המכרוזת ללא אותיות, מכרוזת הרקע, מכרוזת באורך אפס.
הסימן בחזקת N זה שרשור. כלומר, A בחזקת N זה AAAA, N פעמים. יופי.
אז המכרוזת, סליחה, קבוצת המכרוזות, Epsilon, AC, AACC, AAACCC, זה קבוצה שפסיק שלוש נקודות, שוב, היא מוגדרת לא יפה פה, כי יש לנו פה שלוש נקודות, אבל היא מוגדרת מושלם פה, כי פה כתוב A בן, C בן, זה הגדרה טובה. עכשיו אנחנו נמצא להגדרה אינדוקטיבית, נהדר, אבל פה הגדרה אינדוקטיבית היא יותר טובה מהגדרה הזאת, אבל היא לא טובה כמו הגדרה הזאת, הגדרה הזאת היא הגדרה הכי טובה שיכולה להיות, הגדרה פשוטה מאוד, היא גם מגדירה את כל העברים בבת אחת, להבדיל מההגדרה האינדוקטיבית, ששם אנחנו לפי הגדרה האינדוקטיבית, אולי אנחנו לא יודעים האם a, a, a, a, c, c, c, האם היא מילה בשפה או לא מילה בשפה. האם היא עבר בקבוצה או לא עבר בקבוצה. אוקיי? על פי הגדרה הזאת.
אנחנו צריכים לגזור אותה. ופה אנחנו ישר יודעים, אנחנו לא צריכים לגזור, אנחנו יודעים. אוקיי, אז מהי ההגדרה האדוקטיבית של הקבוצה הזאת? אפסילון שייך ל-s, המחוז דרכה שייך ל-s, ואם איזושהי מילה, אם איזושהי מכרוזת שייך ל-s, אז...
אפשר להוסיף A לפני המחוזת ו-C אחרי המחוזת ונקבל מחוז אחרת ששייכת ל-X. טוב, עכשיו מה זה לוגיקה? בואו נחזור ללוגיקה. אז לוגיקה זה, הנה שקף שהולך לחזור כל הסמסטר שוב ושוב, לוגיקה זה שפה פורמלית, שפה פורמלית L, מין L כזו, קליגרפית מיוחדת, שבעזרתה אפשר לבנות נוסחאות אל, ויחס נביאה.
מה היחס נביאה אומר בקורס שלנו? היחס נביאה אומר יחס בין תת קבוצות של... נוסחאות מוגדרות היטב לבין נוסחה מוגדרת היטב אחת ספציפית. אוקיי?
אז זה לוגיקה תמיד, סליחה, זה לוגיקה בקורס שלנו. באופן כללי, בדרך כלל היחס נביאה יהיה בין קבוצות של נוסחאות לבין נוסחה אחת ספציפית. אבל יכול להיות, יכולה להיות איזושהי גלוריקה מאוד מאוד מיוחדת שעבורה, לא יודע, שעבורה גם מצד שמאל תהיה דווקא נוסחה ספציפית.
או גם מצד ימין יהיו קבוצות. שוב, זה פחות מקובל, זה פחות אינטואיטיבי-מתמטית. אינטואיטיבי-מתמטית, יש לנו אוסף הנחות, ואנחנו מסיקים מסקנה אחת.
אנחנו רוצים לדעת איזה מסקנה אנחנו מסיקים. ולכן ככה אנחנו מגדירים את זה בקורס שלנו, זו הגדרה הבסיסית של מה זה לוגיקה. אז מתחילים עם מה זה שפה פורמלית.
שפה פורמלית בשביל להגדיר אותה צריך להגדיר את האלפבט שלה, כלומר איזה תווים חוקיים, ואיך יוצרים נוסחאות מוגדורות היטב. אז בשפה הפורמלית שלנו, רק כל מה שאני אומר עכשיו זה ראינו שבוע שעבר, או שאנחנו פעם ראשונה רואים? פעם ראשונה. פעם ראשונה, אוקיי, אז אנחנו פעם ראשונה, אז השפה המוגדרת היטב שלנו היא שפת התחשיב הפסוקים, היא מורכבת ככה, היא מורכבת ממשתנים, משתנים אנחנו לא מגבילים את עצמנו, יש לנו אין סוף משתנים, ואנחנו גם לא מגבילים את עצמנו באיך אנחנו מסמנים אותם. בשלב הזה אנחנו סמנים אותם בתור התחלה ב-P1, P2 וכו'.
אבל תוך דקה שתיים אנחנו כבר נרשה לכל מכרוזת להיות משתנה. זה הדבר הלא מוגבל. מה כן מוגבל?
יש לנו קשרים. אנחנו משתמשים בארבעת הקשרים האלה בלבד. הקשר וגם, הקשר אור, הקשר חץ והקשר נות. שימו לב שכל מה שאתם יודעים על הקשרים האלה הוא נהדר. אני לא אומר לכם שכחו את זה, אבל אנחנו צריכים להתעלם מזה, אוקיי?
הקשר וגם הוא במקרה הולך להגיד לנו את מה שהקשר וגם באמת אומר, אבל הוא יכול להגיד גם כל דבר אחר. כרגע אנחנו מגדירים שפה פורמלית, אוקיי? אז מבחינתנו הדברים האלה הם אך ורק סימנים, אך ורק צורות, אוקיי?
צורות שאיתם אנחנו נשתמש. מה עוד שייך לאלף ב', הסוגר השמאלי והסוגר הימני גם כן שייכים לאלף ב'. וזה הכל.
חוץ מזה אסור להשתמש בשום דבר, אוקיי? כל סימן שאתם מכירים עם מתמטיקה לא שייך לתחשיב הפסוקים. אלא אם כן הוא מופיע פה, אלא אם כן הוא משתנה, או שהוא אחד מהארבעת הקשרים האלה, או שהוא אחד מהסוגרים, זה בסמאלי או ימני.
אוקיי? יופי. למה דווקא ארבעת הקשרים האלה?
כי זה מה שנוח לנו, אלה ארבעת הקשרים שאנחנו צריכים בשביל להסביר את כל מה שאנחנו צריכים להסביר, אנחנו נראה, לא בקרוב עוד שבועיים או שלושה, נראה למה הקשרים האלה, איזה תתי קבוצה שלהם יכולנו לבחור ואיזה עוד קשרים יש, בפרופוזישיאל לוגיק באופן כללי. יש כמובן עוד קשרים שאפשר להשתמש מהם, ואנחנו נשתמש רק בארבעת אלה. אוקיי, אחרי שהגדלנו את ה-A-B, אנחנו רוצים להגדיר את קבוצת הנוסחאות, המוגדרות היטב.
ככה אנחנו קוראים לנוסחה. אנחנו קוראים לנוסחה, נוסחה מוגדרת היטב. אז נוסחה מוגדרת היטב תוגדר אינדוקטיבית. כלומר, נגדיר בסיס לנוסחה מוגדרת היטב וצעד, בדיוק כמו שהגדרנו קבוצות עד עכשיו.
אוקיי, לנוסחה מוגדרת היטב קוראים well-formed formulas, או לנוסחות מוגדרת היטב קוראים well-formed formulas, ואנחנו מסמנים אותם ב-WFF. אז איך נראית כל WFF? קודם כל, כל המשתנים האטומיים, הם בעצמם כבר נוסחאות מוגדורות היטב.
כלומר, הנוסחה פי 7 היא נוסחה. או המשתנה פי 7 הוא גם משתנה, אבל הוא גם נוסחה. אנחנו גם נקרא לה נוסחה אטומית, בשביל לשים לב שאין שם קשרים. זה הבסיס. מה יהיה הצעד?
הצעד זה, נניח שפי ופסאי, אין זוג נוסחאות מוגדרות היטב. אז הנוסחה, סוגר שמאלי, קשר נוט, הנוסחה פי. וסוגר ימני, היא נוסחה מוגדרת היטב. עוד פעם, סוגר שמאלי, קשר נוט, אחר כך איזושהי נוסחה שכבר קיבלנו, ואחר כך הסוגר הימני. זו נוסחה מוגדרת היטב.
כלומר, בפרט, אולי זה אומר שה... אה, אם הוא לב, הנוסחה... הנוסחה הזאת היא לא נוסחה מוגדרת היטב, אוקיי? וזה אסור להשתמש, אוקיי? זה כן נוסחה מוגדרת היטב.
אתה יכול להסבר למה? אני יכול, אני... לא, אני לא יכול, זו הבעיה.
זו הבעיה. נתלי, נתליה? נתלי. נתלי, כן.
נתלי. אני... אני יכול להתנצל אולי, אני יכול להתנצל שאני לא יכול להסביר, אבל אני לא יכול להסביר, אוקיי, מה שאני יכול לעשות זה להסביר למה אני לא יכול להסביר.
הסיבה שאני לא יכול להסביר היא בגלל שמדובר על צורת כתיבה, וצורת כתיבה היא הדבר השרירותי ביותר שיכול להיות. אנחנו באופן שרירותי קובעים את הכללים. וברגע שאנחנו קופיים, אלה הכללים. את יכולה, נתלי, תכנת את פעם ב-C?
כן, בטח. כן? יופי. את יכולה להסביר לי אולי למה ב-C נקודה פסיק מופיעה בסוף משפט ולא נקודות עין? או ולא, לא יודע, סימן טילדה?
סוג של מוסכמה אולי? אוקיי, אז מוסכמה זה מילה טובה, אז זה מוסכמה, אוקיי. אוקיי. בסדר?
כן. במילים אחרות זה שרירותי, אי אפשר להסביר למה. הסיבה שאני אומר שזה לא, היא בגלל שאני נוטה לכתוב כזה דבר שוב ושוב, אוקיי? וזו טעות, וגם סטודנטים נוטים לכתוב דברים שהם טעות, אז אני אומרת לכן זה לא. בסדר?
כן. אוקיי. אז לא שתלתי את נתלי והשאלה הזאת לא הייתה מוזמנת, אבל השאלה הזאת הייתה הכי הכי מתאימה פה בנקודה הזאת, בשביל להבין שמדובר במוסכמה, באיזושהי החלטה שרירותית. ברגע שהחלטנו מה נוסחות המוגדרות היטב, אז אלה נוסחות וזהו.
אנחנו לא יכולים להחליף אותן. אז זו נוסחה מגדרת היטב, עוד נוסחה מגדרת היטב זה כמובן סוגר שמאלי, פי איזושהי נוסחה כלשהי קודמת, פי הקשר וגם הנוסחה פסאי וסוגר ימני, וככה גם עם הקשר אור וקשר חץ. אוקיי?
אלה ארבעת כללי הגזירה, ובהינתן זה שהמשתנים האטומיים הם המשחרות האטומיות שלנו. ככה אנחנו יכולים לגזור, ככה אנחנו קוראים לזה, כן? לגזור כל נוסחה מוגדרת היטב שקיימת, אוקיי?
עוד שאלות על ההגדרה? טוב, בואו נעשה קצת דוגמאות, אוקיי? איזה מהנוסחאות שכתובות פה הן נוסחאות מוגדרות היטב, ואיזה הן לא נוסחאות מוגדרות היטב?
אוקיי, האם הנוסחה פי 1 היא נוסחה מוגדרת היטב? כן, אמרת נראה לי את זה בהתחלה, לא? נכון, הנוסחה פי 1 היא נוסחה מוגדרת היטב.
בוא נעשה סימון, לא, זה, זה, יופי. האם הנוסחה פי 1 חץ, פי 2 סוגר ימני היא נוסחה מוגדרת היטב? לא, לא, כי חסר הסוגר ימני. היא כמובן לא נוסחה מוגדרת היטב. כי חסר זה תשובה טובה, אבל אנחנו לא יודעים מה כן חסר, לא חסר, אנחנו יודעים שהיא לא מוגדרת היטב.
יופי. האם הנוסחה סוגר שמאלי, סוגר שמאלי פי שלוש, או פי שלוש סוגר ימני, וגם פי שלוש סוגר ימני. האם הנוסחה מוגדרת היטב? כן.
כן, היא נוסחה מוגדרת איטב, יופי. שאלה אחרונה, האם הנוסחה סוגר? סמלי, סוגר סמלי, נות, פי אחד, סוגר ימני, חץ, פי שתיים, סוגר ימני, האם מוגדרתי טב? כן. כן, ניגמנו לך מוגדרתי טב.
יופי. ועכשיו נחזור למה שאמרנו לפני מלא זמן, בערך חמש דקות, אולי אפילו עשר, על... קבוצות מוגדרות היטב והלוכחות, וננסה לשים לב מה עשינו פה קצת בחופזה.
אמרנו שאיך מוכיחים שאיבר שייך לקבוצה מוגדרת איטב, לקבוצה מוגדרת אינדוקטיבית, סליחה, איך מוכיחים את זה? מראים את סדרת הגזירה, איך מוכיחים שאיבר לא שייך? מוצאים איזושהי תכונה שכל העיוורים בקבוצה המודרת אינדוקטיבית מקיימים, מוכיחים שכולם מקיימים את זה, ומראים שהעיוור הזה לא מקיים את התכונה הזאת. את התכונה שאנחנו קוראים לה לפעמים שמורה או אינבריאנטה.
אוקיי? נכון? במקרה של ארבעה מוסכאות האלה, אנחנו צריכים להראות. בלי פי 1 צריכים להראות הגזירה.
יופי, הגזירה של פי 1 זה פשוט לקחת את פי 1. לשתי הנוסחאות האלה צריך להראות הגזירה. זה כבר יותר מסובך. איך להראים את הגזירה? אז אוקיי, אנחנו לוקחים את פי 3, שהיא נוסחה מוגדרת היטב, לוקחים את פי 3 עוד פעם, היא גם כנוסחה מוגדרת היטב, בונים את הנוסחה, סוגר שמאלי פי 3, אור פי 3, סוגר ימני, איך?
בעזרת כלל הגזירה של אור. אוקיי? ואז לוקחים את הנוסחה שנוצרה פה, ולוקחים שוב את הנוסחה P3, שהיא נוסחה מוגדרת היטב, ומפעילים את הכלל עם ה-וגם, כלומר מוסיפים סוגר שמאלי לפני וסוגר שמאלי אחרי. בסדר?
זה עץ הגזירה של הנוסחה הזו. יופי. מה לגבי, אז ככה עושים את זה, וככה גם עושים את המקרה האחרון. מה לגבי השאלה פה? שמישהי אפילו אמרה כן חסר סוגר סמלי, אז חסר סוגר סמלי זה אולי הכלל שאולי צריך להוכיח.
סליחה? אפשר לומר אולי שיש מספר זוגית של סוגריים בכל... לגמרי, אפשר לומר את זה ואחרי שאנחנו אומרים את זה צריך להוכיח את זה.
אוקיי? אז עושים ממש הוכחה וכאמור... הנה הוכחה, בואו נעבור להוכחה. מישהו הרים את היד, אני ביקשתי לדבר, אם אפשר. אז אפשר שאלה?
כן בטח. יש חוקים כמו בסימני מתמטיקה הרגילים של כיף על סיבור חילוק של מה בקודם, אם לדוגמה לנו את ה-P3 או P3 וגם P3, אבל בלי סוגריים ביניהם. אז פה אנחנו כבר יוצאים מהנוסחות מוגדורות היטב ועוברים למה שאנחנו קוראים במתמטיקה בערך בדרך כלל abuse of notation, כלומר אנחנו לפעמים נכתוב את זה בצורה שונה, ואנחנו נכתוב את זה בצורה שונה כיוון שאנחנו נאמין שיש אוקיי, יש איזשהו משפט שאנחנו לא מלמדים פה בקורס, אבל הוא משפט שהוא במובלה קיים, שקוראים לו משפט הקריאה היחידה, כן?
ונוסחה מוגדרת היטב היא כזו שיש לה קריאה יחידה, שזה הדבר החשוב, כן? שכל מי שקורא את הנוסחה הוא קורא אותו דבר בדיוק, כן? ובעצם אנחנו אומרים, לא פורמלית, שאנחנו נעשה abuse of notation, כן? אנחנו מתישהו נשמיד סוגריים. מתי?
רק כאשר תהיה קריאה יחידה, אוקיי? ועוד דבר, אנחנו עושים את ההשמתה הזאת, אנחנו כותבים בצורה פחות פורמלית, גם בגלל שאנחנו יודעים שיש סדר קדימויות, אוקיי? וסדר קדימויות זה נות הוא הקדימות המרבית. וגם זה הקדימות אחר כך, אחר כך אור ואחר כך רחץ אז עוד פעם, אז אנחנו לא מדברים על סדר הקדימויות, כיוון שאנחנו מגדירים את זה פורמלית, ופורמלית אנחנו לא צריכים לצאת על הקדימויות.
חוץ מזה, עוד סיבה שאני לא אומר את הסדר הקדימויות, היא בגלל שהמחשבה שלנו חייבת להיות הפוכה מהסדר הקדימויות. כי כשאנחנו אומרים סדר הקדימויות, אז אנחנו אומרים מה הוא הכי חשוב, וכשאנחנו... מנסים לקרוא את הנוסחה, אנחנו צריכים לקרוא לפי כאילו מה הכי פחות חשוב. למה? כי הכי פחות חשוב זה הקשר האחרון שנוצר, אז הוא זה שמקשר בין זוג נוסחאות מוגדורות היטב.
אנחנו צריכים כל אחת מהנוסחאות לפענח אותה קודם. זה ברור מה שאמרתי עכשיו, או שזה מבלבל יותר? החלק האחרון... נראה לי שפשוט מתישהו שווה לראות דוגמה איך זה קשור באמת לתמר לקשר האחרון, כדי להבין למה משתמש.
כן, כן, הקשר, טוב, אנחנו נראה את זה, כבר היום אנחנו נראה את זה, כשאנחנו ניתן היום את הסמנטיקה, אמרנו. כן, אני רק רוצה, יופי, אני לא חושב את הזמן לו הזה. אנחנו נראה את הסמנטיקה, אז שם אנחנו נראה בדיוק מה זה, איך עוזרים את הסמנטיקה הזה לפי הקשר האחרון.
אוקיי. אז לגבי השאלה של אוהד אני חוזר אליה בעוד כמה דקות, עכשיו אני חוזר לזה ששמנו לב לזה שאומנם ידענו לגבי הנוסחאות ההן, אבל ידענו רק בגלל שהן היו נוסחאות מאוד מאוד פשוטות, או שאנחנו צריכים עדיין להוכיח את זה. אז טענה שאתם אמרתם שהיא עדיונית מאוד. זה שמספר, או סליחה, טיפה עידון של הטענה, הטענה יהיה שמספר הסוגרים השמאליים יהיה שווה למספר הסוגרים הימניים בכל נוסחה שהיא מוגדלת היטב. אוקיי?
זו הטענה. ואם הטענה הזו נכונה, אז הנוסחה שכתובה פה, נוסחה פי 1 חץ פי 2 סוגר ימני, היא בהכרח נוסחה לא מוגדלת היטב. אבל צריך גם שיהיה הגדרה של הסדר ביניהם, כי לא יכול להיות דוגמה סוגר ימני לפני סוגר שמאלי.
לגמרי. אם יש רק שני סוגרים. לגמרי, אבל זה לא מעניין אותנו.
אני מסכים איתך, אבל, כן, אני אומר שמספיק לי, שבשביל להראות שהנוסחה היא, אוקיי, זה עוד דבר שאולי שווה לי תקבל עליו. בשביל להראות שהנוסחה ה-היא היא לא נכונה, מספיק להגיד שמספר הסוגרים, השמאלי והימני, הוא זהה. אם הנוסחה הייתה כזו שהיא מפרה את תכונת הסוגריים, שדווקא המספר היה כן שווה, אבל הייתה מפרה את תכונת הסוגריים, אז היינו צריכים להראות תכונה יותר עדינה, את התכונה שתכון הסוגריים מתקיימת.
אנחנו לא צריכים במקרה הזה. אנחנו מוכיחים את הדבר הקל ביותר שאנחנו יכולים, אוקיי? אז אני לגמרי מסכים, אוהד זה באמת מתקיים פה הרבה יותר, אנחנו מוכיחים רק דבר פשוט. אוקיי, אז איך מוכיחים שהמספרים שווים? הוכחה באינדוקציית מבנה.
דבר ראשון, מסתכלים על הבסיס. בבסיס יש לנו אך ורק הבסיס של נוסחות מוגדורות היטב. זה נוסחאות אטומיות, נוסחאות אטומיות אין בהן סוגריים, ולכן מספר השמאליים שווה למספר הימניים, שניהם אפס.
עד האינדוקטיה, נניח שעבור זוג נוסחאות, פסי ופי, מספר השמאליים בשניהם שווה, מספר הימניים שווה, כן? מספר השמאליים מסוונים ב-L של פסי, מספר הימניים ב-R של פסי, הם שווה, וכך אותו דבר גם לפי. אז אנחנו עכשיו עושים את צעד האינדוקציה, אז צעד האינדוקציה, מה יהיה מספר השמאליים בנוסחה, סוגר שמאלי פסאי וגם פי סוגר ימני, אוקיי? קצת עדין פה, לסמן, מה שכתוב פה, יש פה ככה.
יש פה את הסוגריים. סמלי ביותר והימני ביותר, זה סוגריים של השם שנתן או השם אל. כן, זה הסוגריים של אל.
זה, זו הנוסחה. נוסחה, יש בה, אוקיי, יש בה את הסוגר הסמלי, בסדר? רק שיהיה ברור להפריד בין הסוגריים שיש להם פה שימוש אחר. יופי, אז מה המספר הסמליים פה?
קודם כל יש לנו את הסוגר הסמלי הזה, אוקיי, את הראשון. והנה ספרנו אחד. אחר כך יש לנו את פסאי, כמה סוגרים סמליים יש בפסאי? יש L של פסאי, סוגרים סמליים.
אחר כך יש את וגם, זה לא סוגר, אחר כך יש את פי, כמה סוגרים סמליים יש בפי? L של פי. יופי, זה מספר סוגרים סמליים בנוסחה הזאת. מה לגבי סוגרים ימניים?
שוב, הסוגרים ימניים. אז זה שייך ל-R, סליחה, זה שייך להגדרה של R הסוגריים השמאליים והימני הזה, אז הסוגר הימני הזה נספר לנו, ועוד כל הסוגריים הימניים שיש ב-P, ועוד כל הסוגריים הימניים שיש ב-P, כלומר, אחד ועוד R של P, ועוד R של P, ולכן הם שווים, בגלל ש-R של P שווה ל-L של P, ו-R של P. פסאי שווה ל-L של פסאי אוקיי? אז זו כל ההוכחה לגבי וגם אבל ההוכחה לגבי אור ולגבי חץ היא דומה והוכחה לגבי נות היא בעצם גם דומה כי זה גם כ-1 בדיוק אוקיי? אוקיי, אז זה הכל אני מניח שציפיתם להוכחה מאוד מאוד פשוטה והיא באמת פשוטה עוד דוגמה לנוסחה, לא לנוסחה, לקבוצה בנויה אינדוקטיבית, קבוצת הפלינדרומים.
כן, קבוצת הפלינדרומים אנחנו קוראים לה פה, אבל זה לא פלינדרומים, אלא קבוצת הפלינדרומים הזוגיים. אני חושב שגם A זה פלינדרום, אבל יש כאלה שרק לפלינדרומים זוגיים קוראים פלינדרומים. מה זה פלנדרום? זה מכרוזת שאפשר לקרוא אותה משמאל לימין ומימין לשמאל, ומה שנקרא זה אותו דבר. אז קבוצת הפלנדרומים הזוגיים מעל ה-ABC, מוגדרת על ידי בסיס, זה המכרוזת הריקה, המכרוזת הריקה היא פלנדרום זוגי, וצעד הוא עבור כל מכרוזת שהיא פלנדרום זוגי.
וכל אחד מהאותיות ה-A-B, בעצם זה צד האינדוקטיה שמו שלושה כללי גזירה, כל אחד מה-A או-B או-C נקרא לו X, עכשיו X זה דווקא תו ולא מכרוזת, ו-S היא מכרוזת, אז X, S, X, המכרוזת שיש בתו הראשון, X, אחר כך כל המכרוזת הקודמת שהייתה, ואחר כך X היא גם מכרוזת שהיא פלנדרום זוגי. אוקיי? אז ככה בנינו את קבוצת הפלנדרומים הזוגי, ותרגיל, אנחנו נדלג עליו עכשיו, אבל כל אחד מוזמן לעשות אותו אחריה שהוא כמה דקות, צריך להוכיח שלכל מכרוזת שהיא שייכת לקבוצת הפלנדרומים הזוגיים, מספר הפעמים ש-A מופיע במחוזת הוא זוגי.
אוקיי? מי שרוצה דווקא להוכיח את זה ל-B או ל-C גם יכול. כמו שאתם רואים, הכל פה סימטרי. בסדר? אוקיי.
בואו נחזור לזה, נחזור לנוסחאות. נוסחות מוגדרות היטב, ננסה עכשיו לעשות הצרנות עם נוסחות מוגדרות היטב, אז הצרנות, פורמליזציות, משפט בשפה טבעית, אנחנו הופכים לנוסחה, או לכמה נוסחות, תלוי איזה מין משפט הוא. אז המשפט, if today is Monday, then there is a logic class, הוא משפט שהופך ל-Monday, חץ logic. זו לא מחוזת, זו לא...
נוסחה מוגדרת היטב, נכון? כי נוסחה מוגדרת היטב אמרנו שחייב להיות לנו סוגר שמאלי בהתחלה וסוגר ימני בסוף, אוקיי? אבל אנחנו לפעמים מרשים לעצמנו.
למה אנחנו מרשים לעצמנו את זה? כיוון שאנחנו יכולים לקרוא את זה רק בצורה אחת, אוקיי? ובאופן כללי, כשיש קשר אחד, אנחנו לפעמים נשמיט את הסוגריים. שוב.
אם חתם או אני משמיטים, מותר לנו. אם אתם משמיטים, אתם צריכים אולי להסביר לנו אחר כך שנשאל. אז נסו לחשוב אם אתם מתכוונים להשמיט או לא.
logic class is held only on Mondays, אז logic held Monday. זה היה הפוך. I always sleep in logic class whenever we speak of...
Set Theory, Logic and Speak of Set Theory, כל זה בסוגריים, חץ, Sleep. שוב, אם יש הערות, אז לפתח מיקרופון ולהעיר. הרבה פעמים בפורמליזציות, בשפה טבעית, הרבה פעמים דברים...
אולי אפשר בעוד צורה, אוקיי? יש מלא מלא פעמים שאפשר בעוד צורה, אז להגיד, ואז אני אגיד שאני מסכים או שאני לא מסכים, אוקיי? ואסביר למה אם אני אגיד שאני לא מסכים. אוקיי, I do not sleep when we speak of the test or during the break. speak of the test or break.
כל זה בסוגריים, חץ, not sleep, ו-I'm happy only if it is not raining, or during logic class, נקודה. מה אומרת לנו נקודה בשפה טבעית? בדרך כלל היא אומרת שאנחנו נתחיל נוסחה אחרת מפה.
אוקיי? יופי. אז נוסחה אחרת, it is raining.
כן, גיא. על הקודם, על הספיק אוף טסט, אינד ברייק, ואז הנוט סליפ. אז הנוט סליפ לא צריך סוגריים, מרגיל?
צריך, בוודאי. גם הנוט סליפ צריך סוגריים, וגם הכל ביחד צריך סוגריים. יש פה השמתה פעמיים של סוגריים, כן.
בשביל שהנוסחת יהיה נוסחה מגדירת היטב, צריך להוסיף גם סוגריים על הסליפ, וגם סוגריים על הנוט סליפ, וגם סוגריים על הכל. צודק לגמרי, כן. אה, סבבה, אוקיי, תודה רבה.
אוקיי, תודה. שוב, use of notation, המרצים מרשים לעצמם, לכם, היום אסור, עוד חודש כבר יהיה קצת יותר מותר. אוקיי. אז כאמור, יש לנו פה נקודה, הנקודה כנראה אומרת שאנחנו נגמור פה פסוק אחד, או נגמור פה נוסחה אחת, ונתחיל נוסחה אחרת, אוקיי?
יופי, זו הנוסחה הראשונה. הנוסחה השנייה, it is raining, but I am still happy, כן? כשכבר דיברנו לגבי המילה בת, בדרך כלל המילה בת יכולה להופיע לנו בתור end, אפשרות שונה זה לעשות את זה בתור נוסחה אחת, ואת זה בתור נוסחה אחרת, אוקיי? זה אולי קצת אפשרות פחות מקובלת, אני אולי אעדיף end, אבל פה לדעתי זה יהיו שתי נוסחות, אבל זה פחות חשוב, אוקיי, זה, אוקיי, תכף נסביר את החשיבות של זה, ויש פה, therefore I am at logic.
מה זה המילה המוזרה הזאת? Therefore זה בדיוק המילה שעליה אנחנו מדברים בכל סמסטר. המילה, therefore, מכאן אפשר להסיק. כלומר, זה סימן ההסיק.
בואו נראה, אנה כתבה את זה, אז שימו לב, אנה. החליטה לפצל את ה-raining והappy לשני משפטים, ואני אמרתי שאני יכול, אולי אני הייתי כותב rain וגם happy בתור משפט אחד, סליחה, בתור פסוק אחד. למה זה פחות משנה? זה פחות משנה כיוון שאנחנו, אני מזכיר, אנחנו מדברים פה על...
יחס עסקה יחס העסקה זה מה שמעניין אותנו. מה שמשמאל זה קבוצה של משפטים, קבוצה של פסוקים, ומה שמימין זה פסוק אחד. אז הקבוצה של פסוקים הזו, תמיד אפשר לקחת את כל הקבוצה של הפסוקים, המון המון פסוקים, ולהפוך את כולם לפסוק אחד גדול.
איך? להוריד את כל הפסיקים, נשים end במקום, להוסיף את הסוגריים המתאימים, ולהפוך את זה לפסוק אחד ענק. אנחנו נרצה הרי שכל הפסוקים פה יהיו נכונים בשביל שמה שפה יתקיים, בשביל להכרח שמה שפה הוא יתקיים. כלומר, המשמעות של פסיק פה זה וגם?
כן, המשמעות של פסיק מצד שמאל של הסימן יחס הנביאה היא וגם, כן. המשמעות של פסיק זה כחלק מקבוצת ה... הנחות שלנו, כן, כן, לגמרי. אם זה בא מימין?
מימין לא באפסיק. אה, אוקיי, סדר. לא יבוא אפסיק, אוקיי?
לא בסמסטר הזה. אוקיי, יופי. אז מה יש לנו פה? יש לנו רק את ה...
I'm happy only if it is not raining or during logic class. אז happy, חץ, not rain, or logic, אוקיי? וה-therefore I meant logic, אז יש לנו פה רק logic. שוב, אנחנו לא מסתכלים על נכונות, אנחנו מסתכלים רק על הצרנה, רק על איך להפוך משפט בשפת גנית למשפט כזה, לפסוק. טוב, הנה אנחנו חוזרים לשקף היפה שלנו, והשקף שואל מה זה לוגיקה, וכאמור...
מה זה לוגיקה? זה קודם כל שפה פורמלית שבעזרתה בונים נוסחאות מוגדורות היטב. במקרה הזה עשינו את זה, עשינו את השפה הפורמלית שלנו ואת הנוסחאות המוגדורות היטב בתחשיב הפסוקים, והלווה הבא שאנחנו צריכים להגדיר זה יחס הנביאה, אוקיי? יחס הנביאה, אמרנו שהוא יחס נביאה בשביל נוסחאות מוגדורות היטב, הוא יחס בין קבוצות של נוסחאות לבין נוסחה ספציפית.
מה אנחנו נרצה מיחס נביאה? אז הנה שלוש תכונות שאנחנו רוצים תמיד מיחס נביאה שוב שקף שיחזור כל הסמסטר שלוש תכונות שאנחנו רוצים תמיד מיחס לנביאה אנחנו תמיד נקיים לשלושת התכונות האלה לא בהכרח כל יחס נביאה שאפשר לחשוב עליו נקיים לשלושת התכונות כלומר יש בהכרח יהיו יחסי נביאה שלא יקיימו את זה אנחנו לא נתקל בהם בסמסטר הזה, אבל אין סיבה שלא יהיו. יופי.
מהן שלא נותנות תוכנונות? עוד רגע, קודם כל, מה זה יחס נביאה? אז יחס נביאה, אנחנו חושבים עליו כמו יחס של תורת הקבוצות. יחס בין קבוצות של נוסחאות מוגדורות היטב לבין נוסחאות מוגדורות היטב. יחס, אני מזכיר יחס בתורת הקבוצות.
או רלציה, זה איזשהו, במקרה הזה, רלציה בינארית, יחס בין שתי קבוצות, הקבוצה הראשונה היא קבוצה של קבוצות של נוסחאות ומגדורות היטב, והקבוצה השנייה היא קבוצת הנוסחאות של מגדורות היטב. אוקיי, מהן שלוש התכונות שאנחנו רוצים שיקיימו? רלפלקסיביות, פרונוטוניות וטרנזיטיביות.
מה זה רלפלקסיביות בקשר ליחס נביאה? אם נוסחה פסאי נמצאת בקבוצה גמא, אז הקבוצה גמא יכולה להוכיח את פסאי, או מהקבוצה גמא נובעת פסאי. זה יחס רפלקסיביות.
כמו רפלקסיביות שדיברנו עליה אולי בתורת הקבוצות. לא איתי, אבל עם אור דיברתם, נכון? רפלקסיביות בתורת הקבוצות הייתה דומה אולי. מונוטוניות, מה זה מונוטוניות?
אם מנוסחה, סליחה, אם מקבוצת נוסחאות גמא נובעת פסאי, וגמא היא תת קבוצה של איזושהי גמא פריים, אז גם מגמא פריים נובעת הנוסחה פסאי. כלומר, אם אנחנו מוסיפים נוסחאות לגמא, אבל כבר מקודם פסאי נבעה ממנה, אז פסאי לא תפסיק לנבוא ממנה. התמשיך עם בועמנו שוב, יחס נבא, אנחנו רוצים שיקיים מונוטרוניות.
יופי. התכונה האחרונה היא תכונה טרנזיטיביות, אם מגמה נובעת פסאי ומגמה ופסאי נובעת פי, כלומר, מה זה מגמה פסיק פסאי? זה אומר שאוספנו את פסאי לקבוצה גמה, או אחדנו את הקבוצה שיש בה אך ורק.
הנוסחה פסאי, אחד מאותיים קבוצה גמה שיש בה עוד כך וכך נוסחאות. גמה פסיק פסאי, זה אפשר לראות את זה, או לחשוב על זה בתור איכון של קבוצות. אז מההתחלה, אם מגמה נובעת פסאי, ומגמה ופסאי ביחד נובעת פי, אז כבר מגמה נובעת פי. אנחנו רוצים שיחס נביאה יקיים את ה...
טרנזיטיביות, ויקיים את המונוטוניות ואת הרפלקסיביות. יופי. יחס נביאה אפשר להגדיר בשתי צורות. בצורה אחת סמנטית, כמו שנעשה היום, בצורה של משמעות, ובצורה שנייה סינטקטית. בצורה הסמנטית מה היא אומרת?
היא אומרת שמגמה נובעת סמנטית נוסחה פסי, עם כל מודל של גמא הוא גם מודל של פסי בסמנטיקה הספציפית S. מה זה מודל? מודל זה, אנחנו שוב נגדיר בהמשך, נגדיר היום אפילו, אבל בגדול מודל זה משהו שאומר שמשהו נכון.
שוב, בסמנטיקה אנחנו יכולים להגיד נכון, בסינטקטית אנחנו לא יכולים להגיד נכון. אז מודל זה משהו כזה. לעומת אותה, דרך הסינטקטית לא הוכיח, לא נעשה את זה היום, נעשה את זה בהמשך. מגמה נובעת סינטקטית פסאי, אם יש לנו לפסאי איזושהי הוכחה במערכת דידקטית D מגמה. אוקיי, אז זה לא אומר לנו כלום, כי אנחנו לא יודעים לא מה זה הוכחה ולא מה זה מערכת ולא כלום.
אוקיי, אז סינטקטית זה יהיה טיפה יותר מסובך, נגדיר בהמשך, אבל סינטקטית יש יחס נביאה כאשר יש הוכחה, וסמנטית אומרת כאשר יש מודל של גמא, אז יש מודל של פסי. אם זה נכון, אז מתקיים יחס נביאה. יופי, עשינו את כל השיעור הזה בשביל להגיע לשלושה השקפים האחרונים, שהם מגדירים לנו את יחס הנביאה הסמנטי, ובשביל להגדיר את יחס הנביאה הסמנטי של CPL, CPL תחשיב הפסוקים הסמנטי, אוקיי?
אוקיי, בשביל להגדיר... סמנטיקה, דבר ראשון שאנחנו צריכים להגדיר זה ערכי ענת. אנחנו מגדירים זוג ערכי ענת, אחד מהם T, אחד מהם F. כולם יודעים למה בחרנו באותיות T ו-F? כולם יודעים.
נכון שכולם יודעים? יופי, עכשיו כולם לא שוכחים, אבל מכניסים את זה לאיזושהי קופסה. אין פה שיפוטיות, יש ערך אמת 1 שקוראים לו T, וערך אמת 1 שקוראים לו F. אוקיי?
יופי. טבלאות אמת. אנחנו מגדירים לכל אחד מהקשרים שאמרנו שאנחנו משתמשים בהם, אנחנו מגדירים טבלת אמת, והטבלת אמת היא מה שמגדירה את הקשר. עד עכשיו הקשר היה אך ורק צורה.
בסמנטיקה, לקשר יש גם טבלת אמת, והוא מוגדר על ידי טבלת אמת. כלומר, אם היינו מגדירים את טבלת אמת, לא יודע, שאיזשהו קשר וגם אומר תמיד F, אז המשמעות של הקשר וגם הייתה תמיד להפוך את הכל ל-F. המשמעות של הקשר היא מגיעה מטבלת האמת. איך קוראים טבלאות אמת? טבלת אמת של נוט היא מאוד קלה לקרוא, אם הערך האמת הוא T, אז הוא הופך לפולס, אם הערך האמת הוא F, אז זה הופך ל-T, אמרתי false, יצא לי, התפלק לי, אוקיי?
אתם בטח תשימו לב עוד כמה דקות שבאמת זה יהיה ככה, אבל כרגע זה רק T ו-F, אוקיי? אם זה T הופך ל-F, אם זה F הופך ל-T. איך קוראים קשרים בינאריים? קשרים בינאריים קוראים כאילו מה שמתחת לקשר הוא נמצא משמאלו, ומה שמימין לקשר נמצא מימינו. אז הקשר חץ, אם יש לנו...
T משמאל ו-T מימין נותן T אם יש לנו T משמאל ו-F מימין נותן F והקשר חץ, אם יש לנו F משמאל ו-T מימין נותן T ואם יש לנו F משמאל ו-F מימין נותן T אוקיי? כן אתה בעצם מגדיר עלינו פה פשוט סוג של, לא יודע, שוויון כזה של, לא יודע, כאילו אין פה שום קשר לוגי או משהו? הוא שומע?
אני אומר, כאילו אין פה, זה לא מסתמך על שום קשר לוגי, כאילו T משמאל וחץ T מימין זה תמיד יהיה שווה ל-T, זה מה שאתה מנסה להגיד לנו פה? כן. בלי שום הקשר או איזה משהו? אז אקשר אנחנו נוכל להכניס אקשר, אנחנו אמרנו שאנחנו מדברים על סמנטיקה, אז כאילו יש לנו משמעות, כן? המשמעות של הקשר חץ אנחנו רוצים שהמשמעות יהיה אם-אז, אוקיי?
ובאמת, אם לסבתא היו גלגלים אז היא הייתה נוסעת לבאר שבע, ובאמת לסבתא יש גלגלים ובאמת היא נוסעת לבאר שבע, הסימן שהמשפט הזה הוא משפט נכון מבחינתנו, זה מה שאנחנו יודעים עליו. אוקיי? הקשר הוא מתאים ל-אם-אז, אבל הרעיון הוא שבשביל המשמעות אנחנו לא צריכים לא לחשוב על אם-אז, לא לחשוב על הקשר הזה בתור הקשר end, אלא זה הצורה שלו, זה הגדרה שלו וזהו. זה הרעיון של לוגיקה. כאילו את כל מה שאנחנו יודעים.
עוד רגע, אנחנו נראה ש... טוב, לא שכחנו באמת, כי אנחנו משתמשים בזה, אבל הרעיון הוא שרק מפה מגיע הערך. ובשביל זה גם הסימון פה הוא לא הקשר וגם, אלא הקשר וגם עם איזשהו טילדה מעליו, שזה הסמה של הערך שאנחנו נותנים לקשר וגם.
אוקיי. שרוצה? אם אני יכול להסתכל על טבלת האמת של שני משתנים על סמן בינארי, אז בעצם אני, ואני רואה שזה סימטרי, כאילו הערכים שאני מקבל הם סימטרים, זה אומר שגם היחס הוא סימטרי?
לגמרי, לא היחס אלא הקשר, כן, הקשר הוא סימטרי. הקשר, כן. כן, לגמרי, ושוב. וזה נכון רק כשאנחנו מדברים על משמעות ועל תבלות האמת, אז כן, אז זה נכון, שאנחנו נוכל להשתמש בה, למשל, סימטריה, בגלל סימטריה של תבלת האמת.
מעולה, כן. שוב, כל זה בהמשך, עוד לא, אבל כן. אוקיי, עכשיו, מה אנחנו עושים עכשיו?
אנחנו מדברים על ולואציה. מה זה ולואציה? ולואציה...
אנחנו נחשוב עליה בתור הסמה, כן? הסמה של ערכי אמת, כלומר OTOF, לכל אחד מהמשתנים בנוסחה, ועכשיו אנחנו נספר איך אנחנו מוצאים את הערך של הנוסחה. אוקיי, אז ולואציה אנחנו חושבים עליה עכשיו בתור פונקציה מנוסחה. בנוסחאות ל-KMH, TOF, איך הפונקציה הזאת היא מוגדרת? היא מוגדרת אינדוקטיבית.
ערך הבסיס אנחנו מקבלים מתוך, אמרנו שאפלואליאציה היא גם הסמה, אז ערך הבסיס אנחנו קבלים מתוך ההסמה, לכל אחד מהמשתנים של הנוסחה אנחנו מציבים O, T, O, F, V, צעד ההגדרה, אם יש לנו, אנחנו רוצים לחשב את V של איזשהו קשר עם כך וכך נוסחאות פנימיות, אז אנחנו הולכים לטבלת האמת של הקשר הזה, ומפעילים את V על כל אחת מהנוסחות הפנימיות. שימו לב, כתוב פה נוסחות פנימיות מפסי 1 עד פסי N, אבל הקשרים שלנו, עד עכשיו דיברנו עליהם, הם קשר אונרי וקשר בינרי. אז N פה הוא או שווה 1 או שווה 2. אבל זו הגדרה פורמלית עבור קשר כלשהו, אולי יש לנו גם קשר שמקשר בין 17 משתנים. כלומר, אין סיבה שלא יהיה. אז זו הגדרה של ולואציה, בואו נראה מה זה אומר.
למשל, אם אנחנו נותנים למשתנה לוג'יק את הערך T, למשתנה Monday את ערך האמת T ולמשתנה Sleep את ערך האמת F, אז ה-V של Logic חץ Sleep, אנחנו רואים שלוגיק זה T ו-Sleep זה F, ואנחנו הולכים לטבלת האמת של חץ, אנחנו רואים T חץ F זה F. אנחנו אומרים ש... ה-V של logic חץ ליפ הוא F.
F, אוקיי? הלאה. V של logic וגם not Monday, אז Monday זה T.
נוט מנדי יהיה F, ולא חשוב מה לוגיק, גם אם F נותן F. אוקיי? בסדר? רואים מה אני עושה? רואים איך זה קשור להגדרה המסובכת לפני רגע של זה, של ולואטיה?
כן. אוקיי? הגדרנו הגדרה מאוד מסובכת, אבל הנה אנחנו מראים כמה זה בעצם לא מסובך.
אוקיי, טוב מאוד. הנה אנחנו עוברים ל... עוקים את הלוח, יופי. ואנחנו עוברים לקשר, אלסטחלה, יחס לנביאה, CPL. זה מה שאנחנו רצינו להראות היום, זה הדבר החשוב, יחס לנביאה, CPL. אז בשביל...
יחס נביאה סמנטיה, אמרנו שאנחנו צריכים להגדיר מה זה מודל. אמרנו שאם יש לנו מודל משמאל, אז הוא צריך להיות מודל מימין. אז מה זה מודל? ולואציה V היא מודל של נוסחה פסאי, איזושהי נוסחה מוגדרת היטב, אם ורק אם V של פסאי שווה ל-T. אוקיי?
אז הבטחתי לכם שזה יהיה קצר. זה שאין שום הבדל בין T ל-F, אז עד לפני שנייה לא היה שום הבדל בין T ל-F, ברגע זה שמנו הבדל, אמרנו שאנחנו רוצים דווקא לקחת את הערך T, ערך האמת T, ולהגיד שהוא חשוב לנו יותר, או שהוא חשוב לנו להגדרה של מודל. אוקיי?
אז ווליואציה היא מודל של נוסחה עם הערך הוא T. אוקיי? שוב, וליאציה היא מודל, אנחנו בודקים מהי הווליאציה, האם הווליאציה היא מודל של נוסחה.
יופי, אז אם יש לנו מודל של נוסחה, אז מה תהיה וליאציה, אז מתי וליאציה תהיה מודל של קבוצת נוסחאות, אז היא תהיה מודל של קבוצת נוסחאות, אם ורק אם היא מודל של כל אחת מהנוסחאות בקבוצה, כמובן. אוקיי? אז וליאציה היא מודל של קבוצת נוסחאות, אם ורק אם היא מודל של כל אחת מהנוסחאות, אז... רק דוגמאות, נניח ש-V ווליאציה כך ש-V של P1 זה T ו-V של P2 זה F, האם V היא מודל של קבוצת הנוסחאות הזאת?
P1 פסיק P1 חץ נות P2. אז מה צריך לעשות? אנחנו צריכים לבדוק האם היא מודל של הווליאציה של... האם הפליאציה היא מודל של הנוסחה הראשונה, והאם היא מודל של הנוסחה השנייה?
אז הנוסחה השנייה הראשונה היא פי 1, ו-v של פי 1 הוא t, אז כן, אז היא מודל של הנוסחה פי 1. האם הווליואציה היא מודל של P1 חץ נות P2? אוקיי, אז P2 זה F, נות P2 זה T, P1 זה T, אז יש לנו פה T חץ T, ואנחנו חוזרים לטבלת האמת של חץ, ואנחנו רואים שטבלת האמת של חץ T חץ T נותן T, לכן הנוסחה הזאת, הווליואציה היא מודל שלה, והנוסחה הזאת, הווליואציה היא מודל שלה, ולכן הווליואציה היא מודל של כל ה... נוסחאות שיש בקבוצה, ולכן היא מודל של הקבוצה הזאת.
יופי. אורן, זאת אומרת, איבלואציה זה בעצם, זה שקול פרדיקט, כמו שיש בדיסקרטית? רדיקט, לא, זה לא שקול רדיקט בכלל, לא, איבלואציה זה הסמה, למשתנים, אוקיי?
פרידיקט אנחנו נדבר כשנגיע לפרידיקט לוג'יק, לתחשיב היחסים, אוקיי? אוקיי. ווליואציה היא השמה למשתנים, והמשתנים הערכים שלהם הם רק T ו-F, נכון?
אלה כאמת שיש לנו. האם V, הוליואציה הזאת שנותנת לפי 1T ולפי 2F, האם היא מודל? של הקבוצה הזאת, קבוצה שיש בה שוב את P1 חץ נות P2, אנחנו כבר יודעים שהיא מודל של הנוסחה הזאת, ויש לנו גם את הנוסחה P2, האם V היא מודל של P2? לא.
V של P2 היא F, אז לכן V היא לא מודל של כל הקבוצה הזאת, כי יש לנו לפחות נוסחה אחת ש-V היא לא מודל שלה. זאת תשובה במקרה הראשון מכן, המקרה השני היא לא. טאוטולוגיות, או סימן יחס הנביאה ללא שום קבוצה מצד שמאל, או אם תרצו, קבוצה ריקה מצד שמאל.
אז יחס נביאה CPL, פסאי, זה כמו להגיד שפסאי היא טאוטולוגיה, שתי דרכים להגיד אותו דבר. מתי זה מתקיים? אם ורק אם כל וליאציה שנחשוב עליה, היא תהיה מודל של פסאי. אוקיי?
נוסחה היא טאוטולוגיה, אם ורק אם כל וליאציה שקיימת, היא חייבת להיות מודל שלה. אוקיי? יש דוגמאות לטאוטולוגיות, נחשוב על איזושהי נוסחה, שכל וליאציה תהיה מודל שלה. מישהו יכול לחשוב על נוסחה שכל וליוואציה היא מודל שלה? נוסחה שתמיד כל וליוואציה עליה תהיה T?
מה אם הם רטובים זה נחשב תאוטולוגיה? מה אם הם רטובים זה נחשב תאוטולוגיה בשפה טבעית, אבל אני שואל על נוסחה... אפשר נגיד ליצור שפה כאילו, שענית מחוקר השפה?
לא, השפה קיימת, השפה היא תחשיב הפסוקים, אוקיי? והנוסחאות הן נוסחאות כמו פי אחד חץ נות פי שתיים, זה סוג של נוסחה. הנוסחה הזאת היא לא תאוטולוגיה, אוקיי? אבל יש נוסחאות שהן כן תאוטולוגיות. שומע?
A or not A. מעולה. מעולה.
שדן אומרת A or not A. שוב, אני כותב את זה בלי סובריים כי מותר לי, נכון? אבל תחשבו שיש פה גם סובריים. אוקיי?
זו מוסחה שהיא את האוטולוגיה. אוקיי? לכל הערך שאנחנו ניתן למשתנים שלה, המשתנים שלה זה רק A, אוקיי?
לכל הערך שאנחנו ניתן ל-A, הנוסחה, הערך של הנוסחה יהיה True, יהיה T, אוקיי? מעולה. עוד דוגמה.
עוד דוגמה, תהיה P חץ. פי, אם פי אז פי, אוקיי? זה גם כן נוסחה של תאוטולוגיה, אוקיי? וכמובן, אין סוף לדוגמאות, אני לא חייב להיות להיות עם משתנה אחד בלבד, יכול להיות יותר, אבל אלה תאוטולוגיה.
יופי, אז זה לגבי תאוטולוגיה, אבל אנחנו אמרנו שאנחנו רוצים את יחס הנביאה CPL, זה מה שאנחנו מחפשים מתחילת השיעור. אז יחס הנביאה CPL, מקבוצת נוסחאות גמא נובעת CPL נוסחה פסי, אם ורק אם, כל ולואציה שהיא מודל של גמא, היא מודל של פסי, בדיוק כמו שהבטחנו בהגדרה של מה זה יחס נביאה סמנטי, בדיוק ככה יחס נביאה סמנטי CPL מתנהג. עכשיו אנחנו גם מבינים מה זה, כי הגדרנו גם מה זה מודל.
אוקיי? יופי. טוב שהגענו לזה, זה מה שרצינו להגיע אליו, זה החשוב, ואנחנו נמשיך בשבוע הבא, אחרי שאנחנו כבר יודעים את ההגדרה הזאת. שאלות.
אוקיי, אין שאלות, אני חוזר על המשפט האחרון לפני שאני סוגר את הוידאו. המשפט האחרון הוא... מגמא נובעה cpl פסי אם ורק אם כל ולואטיה שהיא מודל של גמא, כלומר ולואטיה שנותנת t לכל אחת מהנוסחאות בגמא, היא מודל של פסי. זה יחס נביאה cpl, להתראות להקלטה, ביי ביי.
עכשיו ללא הקלטה, האם מישהו רוצה לשאול עוד איזושהי שאלה? להגיד משהו? תודה רבה רון.
תודה. סוף שבוע נעים לכולם, נתראה שבוע הבא. ביי ביי.
ביי תודה. תודה רבה. תודה רבה.