'''משפט'''. כל פסוק לוגי שקול להצבת האטומים <math>\ A_i</math> ושלילתם <math>\ \neg A_i</math>, בפסוק שבו מופיעים רק הקשרים "או" ו"וגם".
== כמתים תחשיב פרידקטים ==
הלוגיקה שלמדנו עד כה מאפשרת לטפל רק במצבים קונקרטיים: הצלחת הזו אדומה, הכלב הזה נובח. כלים אלו אינם מאפשרים לנסח אפילו טענות פשוטות כמו * לכל מספר יש מספר גדול יותראו * מישהו כתב את הדפים האלה. כדי להצרין טענות כאלה, המופיעות במתמטיקה בכל מקום, עלינו לרכוש שני כלים חדשים: פרדיקטים וכמתים. === פרדיקטים === בלוגיקה מתמטית, '''פרדיקט''' הוא פונקציה המקבלת משתנה או כמה משתנים, ומחזירה ערך אמת (T או F). זוהי הכללה של האטומים שפגשנו קודם לכן, שאינם אלא פרידקטים ללא משתנים.'''דוגמאות'''. * כדי לומר "התפוח הזה צהוב", אפשר להגדיר פרדיקט <math>\ Y(x)</math>, עם משתנה אחד, המחזיר את הערך T כאשר x צהוב, ואת הערך F בכל מקרה אחר.* כדי לומר "דפנה היא אמא של יובל", אפשר להגדיר פרדיקט <math>\ M(x,y)</math> המקבל ערך T כאשר x היא אמא של y. יש להציב את דפנה במקום x ואת יובל במקום y. בבניית פסוק עם פרדיקטים, מותר להחליף אטומים בפרדיקטים עם משתנים כלשהם (עם חזרות או ללא חזרות). '''תרגיל'''. הגדירו פרדיקטים והצבות במשתנים, כך שהפסוק <math>\ A(x) \vee (B(x,y) \wedge A(y))</math> יצרין את "אורן או חברתו קארין לומדים לוגיקה". פרדיקטים מאפשרים יותר גמישות מסתם אטומים, משום שאפשר להציב בהם בכל פעם משתנים אחרים. חשוב להבין שערך האמת של פסוק המערב בפרדיקטים, כמו <math>\ Y(x) \rightarrow M(x,x)</math> ("אם x צהוב, אז הוא אמא של עצמו") תלוי בערך המשתנה: בדוגמא הזו, אם x הוא אדם צהוב, הפסוק מקבל את הערך F, ואם x הוא אדם שאינו צהוב, ערך האמת הוא T. גמישות זו עדיין אינה מאפשרת לנסח טענות כלליות, כמו "אף אדם אינו אמא של עצמו". לשם כך יש צורך בכמתים. === כמתים === ה'''כמתים''', המציינים תחולה של משתנה, הם תוספת חיונית למערך הקשרים שלנו. יש שני כמתים: "לכל", המסומן באות <math>\ \forall</math> (זוהי A הפוכה, קיצור של המלה All); ו"קיים", המסומן באות <math>\ \exists</math> (E הפוכה, קיצור של Exists). כשבונים פסוק עם כמתים, מותר לקחת פסוק קיים (הכולל פרדיקטים, שבהם x הוא משתנה), ולבנות:* <math>\ \forall x : P(x)</math> - מקבל ערך אמת T אם הפסוק <math>\ P(x)</math> מקבל ערך אמת לכל הצבה של x.* <math>\ \exists x: P(x)</math> - מקבל ערך אמת T אם יש הצבה של x כך שהפסוק <math>\ P(x)</math> מקבל ערך אמת. '''דוגמא'''. את הפסוק "אין מספר גדול ביותר" אפשר להצרין באופן פשטני, כך: <math>\ \neg \exists x: L(x)</math>, כאשר <math>\ L(x)</math> הוא הפרדיקט "x הוא מספר גדול ביותר". הצרנה מעט יותר מתוחכמת תגדיר את הפרדיקט <math>\ P(x,y)</math> שפירושו "x<y", ותצרין ל-<math>\ \forall x: \exists y: P(x,y)</math>, כלומר, לכל מספר יש מספר הגדול ממנו. גם לאחר ההרחבה הזו, בכל פסוק יש "פעולה אחרונה": הקשר האחרון או הכמת האחרון שהופעל כדי ליצור את הפסוק. לדוגמא: * הפעולה האחרונה ב- <math>\ \forall x: ((x<y) \rightarrow (x<0))</math> ("לכל x, אם x קטן מ-y אז x שלילי") היא הכמת הכולל על x; לעומת זאת הפעולה האחרונה ב- <math>\ (\forall x: (x<y)) \rightarrow (y<0))</math> ("אם כל x הוא קטן מ-y, אז y שלילי") היא הקשר "אם-אז". לפסוקים שיש בהם כמתים אי אפשר לבנות טבלאות אמת, משום שלצד האטומים המקבלים רק שני ערכי אמת אפשריים, יש בהם משתנים העשויים לעבור על-פני מספר אינסופי של אפשרויות. לכן הלוגיקה המטפלת בפסוקים עם כמתים (הנקראת "לוגיקה מסדר ראשון") מורכבת יותר מן הלוגיקה הפסוקית, ויש לה יכולת ביטוי רחבה יותר. גם בלוגיקה זו אומרים ששני פסוקים <math>\ \varphi, \psi</math> הם שקולים אם <math>\ \varphi \leftrightarrow \psi</math> מקבל ערך אמת לכל הצבה של המשתנים המעורבים. כבר למדנו כיצד לשלול פסוק שבו הפעולה האחרונה היא אחד הקשרים. כדי לשלול פסוק שבו הפעולה האחרונה היא כמת מפעילים שתי הבחנות פשוטות, שנציג כדוגמאות:* "לא כל תפוח הוא צהוב" שקול לכך ש"קיים תפוח שאינו צהוב".* "לא קיים תפוח צהוב" שקול לכך ש"כל תפוח אינו צהוב".כלומר, לכל פרדיקט P, * <math>\ \neg \forall x: P(x) \equiv \exists x: \neg P(x)</math>, וכך גם* <math>\ \neg \exists x: P(x) \equiv \forall x: \neg P(x)</math>. אפשר "לחסוך" ולהשתמש רק באחד משני הכמתים:* <math>\ \exists x: P(x) \equiv \neq \forall x: \neg P(x)</math> ("קיים סוס שחור" = "אין זה נכון שכל הסוסים אינם שחורים"). באופן הזה אפשר להחליף כל מופע של הכמת "קיים" במופע אחד של הכמת "לכל"; כמובן, גם ההיפך אפשרי. בפועל, שני הכמתים נמצאים בשימוש מתמטי תמידי. הכמתים היסודיים מאפשרים לנסח טענות סטנדרטיות נוספות. * <math> \exists x : (P(x) \wedge \forall y : (P(y) \rightarrow x=y))</math> -- "קיים x המקיים את התכונה P, ובנוסף, כל y המקיים את התכונה P שווה ל-x". כלומר: "קיים x יחידהמקיים את התכונה P". לפעמים מקצרים את הפסוק הזה וכותבים <math>\ \exists! x: P(x)</math>. אפשר לראות בצירוף "<math>\ \exists !</math>" כמת שלישי, קיימים למרות שכאמור לעיל ניתן להגדיר אותו באמצעות שני הכמתים האחרים (בנוכחות פרדיקט השוויון). לפעמים רוצים לומר שיש אינסוףמספרים המקיימים תכונה מסויימת. אפשר לעשות זאת כך: * <math>\ \forall n : \exists x : ((x>n) + כימות יחסי \wedge P(קיים אפסילון x))</math>: "לכל n יש x גדול מאפסממנו המקיים את התכונה". אם היה רק מספר סופי של מספרים המקיימים את התכונה המדוברת, אז הפסוק היה שקרי משום שאפשר היה לבחור בתור n את המספר הגדול ביותר. לצרכי נוחות, מרשים מעט יותר גמישות במבנה הפסוקים, כך שאפשר יהיה לכמת "כימות יחסי". לדוגמא, מותר לכתוב* <math>\ \forall x>0: \exists y>0: y<x</math> - "לכל אפסילון גדול מאפסמספר חיובי x יש מספר חיובי y הקטן ממנו", כלומר "אין מספר חיובי קטן ביותר", בתור קיצור לכתיבה המלאה <math>\ \forall x: ((x>0)\rightarrow (\exists y: ((y>0) \wedge (y<x))))</math> - "לכל מספר x, אם הוא חיובי, אז קיים מספר y שהוא חיובי וקטן מ-x".
== הוכחה ==