טיוטה:משפט הקריאה היחידה

בלוגיקה מתמטית, משפט הקריאה היחידה טוען כי בתחשיב הפסוקים כל פסוק ניתן לקריאה בצורה יחידה, כך שלא מתקבלת דו-משמעות תחבירית (כמתרחש לעיתים בשפות טבעיות) ולא ניתן לייחס לפסוק שני ערכי אמת שונים בו-זמנית.

הגדרה

1. לכל $n\in \mathbb {N}$, פסוק יסודי $P_{n}$ הוא פסוק.
2. אם $a$ פסוק אזי גם $\neg (a)$ פסוק.
3. אם $a,b$ פסוקים אזי גם $(a)\,\square \,(b)$ פסוק, כאשר $\square \in \{\land ,\lor ,\to ,\leftrightarrow \}$ קשר לוגי דו-מקומי.
4. כל פסוק הוא מילה המתקבלת באמצעות שימוש רקורסיבי בכללים הקודמים בלבד.

ניסוח המשפט

פסוק $a$ מופיע בצורה אחת בלבד משלוש הצורות:

1. $a=P_{n}$ פסוק יסודי.
2. $a=\neg (b)$, כאשר $b$ פסוק הנקבע באופן יחיד על ידי $a$.
3. $a=(b)\,\square \,(c)$, כאשר $b,c$ פסוקים הנקבעים באופן יחיד על ידי $a$.

הוכחה

נקדים משפטי עזר אחדים.

למה 1: משפט האינדוקציה לבניית פסוק

תהי תכונה כלשהי אשר:

1. מתקיימת בכל הפסוקים היסודיים $P_{n}$.
2. מקיומה לפסוק $a$ נובע קיומה עבור $\neg (a)$.
3. מקיומה לפסוקים $a,b$ נובע קיומה עבור $(a)\,\square \,(b)$.

אזי התכונה מתקיימת בכל הפסוקים.

למה 2: משפט הסוגריים

בכל פסוק, מספר הסוגריים השמאליים שווה למספר הסוגריים הימניים.

הוכחה:

1. בכל פסוק יסודי $P_{n}$ מופיעים 0 סוגריים שמאליים ו-0 סוגריים ימניים.
2. יהי $a$ פסוק בו מופיעים $m$ סוגריים שמאליים ו-$m$ סוגריים ימניים. לכן בפסוק $\neg (a)$ ישנם $m+1$ סוגריים שמאליים ו-$m+1$ סוגריים ימניים.
3. יהי $a$ פסוק בו מופיעים $m$ סוגריים שמאליים ו-$m$ סוגריים ימניים, ויהי $b$ פסוק בו מופיעים $n$ סוגריים שמאליים ו-$n$ סוגריים ימניים. לכן בפסוק $(a)\,\square \,(b)$ ישנם $m+n+2$ סוגריים שמאליים ו-$m+n+2$ סוגריים ימניים.

ממשפט האינדוקציה לעיל מתקבל כי תכונה זו מתקיימת בכל הפסוקים.

הוכחת המשפט

שגיאות פרמטריות בתבנית:להשלים
פרמטרי חובה [ נושא ] חסרים

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה והשלימו אותו.

ראו גם

• תחשיב הפסוקים
• נוסחה (לוגיקה)
• פסוק (לוגיקה)