שינויים

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

88-101 חשיבה מתמטית

הוסרו 32 בתים, 08:38, 11 ביולי 2011
/* פסוקים מורכבים */
את הקשרים שפגשנו (לא, וגם, או, אם-אז, אם-ורק-אם) אפשר להפעיל לא רק על אטומים, אלא גם על פסוקים.
'''דוגמא'''. אם אדם הוא מאושר אם ורק אם הוא לומד דברים חדשים, אז אדם שאינו לומד דברים חדשים אינו מאושר. (שמצרינים ל"אם (A אם ורק אם B), אז (אם לא B, אז לא A)").
עד כאן לא הגדרנו מהו "פסוק". פסוק הוא בסופו של דבר רצף של תווים, שכל אחד מהם הוא או אחד האטומים (מקובל להניח שעומדת לרשותנו אספקה אינסופית של אטומים), או אחד מסימני הקשרים, או אחד הסימנים המיוחדים "(" ו")" שתפקידם להבטיח קריאה חד-משמעית של הפסוק. לדוגמא, הפסוק <math>\ A \wedge B \vee C</math> אינו ניתן לקריאה באופן ברור: אין לדעת האם הכוונה היא ל-<math>\ (A \wedge B) \vee C</math> או ל-<math>\ A \wedge (B \vee C)</math>. ('''תרגיל''': מצא ערכי אמת של A,B,C שיתנו ערכי אמת שונים לשני הפסוקים האחרונים). הכלל במקרה של ספק הוא פשוט: עדיף לבזבז מאה זוגות סוגריים מיותרים, מאשר להשמיט זוג סוגריים חיוני אחד.
כמובן שלא כל רצף של סימנים הוא פסוק. "<math>\ )A\vee\neg\wedge)BA\neg</math>" אינו פסוק. אפשר '''להגדיר פסוקים ''' מהו פסוק "באינדוקציה על המבנה": * כל פסוק הוא או אטום, או בצורה שיש לו הצורה <math>\ \neg(x)</math> כאשר x הוא פסוק, או בצורה הצורה <math>\ (x)R(y)</math>, כאשר R הוא אחד מסימני הקשרים הבינאריים, ו-x,y הם פסוקים.
הגדרה זו היא אחת מאבני היסוד של '''הלוגיקה הפסוקית''', המטפלת בפסוקים באופן פורמלי.
'''תרגיל'''. הוכח, באינדוקציה על אורך הפסוק, שאפשר לבנות מכונה שתזהה האם רצף של תווים הוא פסוק או לא (הנח שהמכונה יודעת לזהות אטומים).