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

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

הגדרה

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

ניסוח המשפט

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

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

הוכחה

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

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

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

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

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

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

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

הוכחה:

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

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

ראו גם

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