חזור לתיקייה: 02340292 - לוגיקה למדעי המחשב

1 - תחשיב הפסוקים

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • מבנה תחשיב הפסוקים
  • סינטקס
  • סמנטיקה

1 - תחשיב הפסוקים

02340292

לוגיקה למדעי המחשב

רשימות הרצאה לקריאה בשבת

תחשיב הפסוקים

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

מבנה תחשיב הפסוקים

סינטקס

הגדרה 1 (קבוצת פסוקים)

נגדיר באינדוקציה קבוצת פסוקים WFFWFFWFF. (ראשי תיבות של: Well Formed Formulas)

  • פסוקים אטומיים: Vars={pi∣i∈N}Vars=\left\{ p_{i}\mid i \in \mathbb{N} \right\}Vars={pi​∣i∈N} (מותר לקרוא להם משתנים)
  • קשרים לוגיים: Symb=\left\{ (,),\lnot,\lor,\land,\to \right\} (ניתן לקרוא להם סימנים)

נגדיר X=(Vars∪Symb)∗X=(Vars \cup Symb)^*X=(Vars∪Symb)∗ עולם, B=VarsB=VarsB=Vars בסיס ו-F=\left\{ f_{\lnot},f_{\lor},f_{\land},f_{\to} \right\} קבוצת פונקציות ואז WFF=XB,FWFF=X_{B,F}WFF=XB,F​.
(נשים לב כי f_{\lnot}(\alpha)=(\lnot\alpha) כאשר השאר מוגדרות f☺︎(α,β)=(α☺︎β)f_{☺︎}(\alpha,\beta)=(\alpha☺︎\beta)f☺︎​(α,β)=(α☺︎β) עבור ☺︎∈{∧,∨,→}☺︎ \in \left\{ \land,\lor,\to \right\}☺︎∈{∧,∨,→})

דוגמה (לפסוקים ב-WFFWFFWFF)

א. p6p_{6}p6​ - הוא פסוק אטומי (הוא בבסיס)
ב. p19p_{19}p19​ - גם כן בבסיס.
ג. (\lnot\;\!\;\! p_{6}) - הפעלת פונקציה.
ד. (p6→p19)(p_{6}\to p_{19})(p6​→p19​)

מתקבלת קבוצה ∞\infty∞-ית של פסוקים.

משפט (הקריאה היחידה)

בהנתן φ∈WFF\varphi \in WFFφ∈WFF מתקיים בדיוק אחד מהתנאים הבאים:

  1. קיים iii יחיד כך ש-φ=pi\varphi=p_{i}φ=pi​.
  2. קיים α∈WFF\alpha \in WFFα∈WFF יחיד כך ש-\varphi=(\lnot\alpha).
  3. קיימים α,β∈WFF\alpha,\beta \in WFFα,β∈WFF יחידים ו-☺︎∈{∧,∨,→}☺︎ \in \left\{ \land,\lor,\to \right\}☺︎∈{∧,∨,→} כך ש-φ=(α☺︎β)\varphi=(\alpha☺︎\beta)φ=(α☺︎β).

נסתכל על עץ יצירה של הפסוק: (p_{5}\to(p_{2}\lor(\lnot p_{3}))). הוא יראה כך:
​1 - תחשיב הפסוקים 2026-11-08 15.02.39.excalidraw.svg
נשים לב כי יש לנו רק אפשרות אחת ליצור עץ שכזה אם הפסוק מוגדר היטב עם הסוגריים.
אינטואיטיבית, המשפט טוען בדיוק את זה. כלומר, יש לפסוק רק דרך אחת לפרק אותו. (לבצע לו parsing באופן יותר פורמלי)

הוכחה: יהי φ∈WFF\varphi \in WFFφ∈WFF.

  • אם ∣φ∣=1|\varphi|=1∣φ∣=1 אז φ∈Vars\varphi \in Varsφ∈Vars. זאת מכיוון ש-φ\varphiφ או ב-VarsVarsVars או התקבל מהפעלת f∈Ff \in Ff∈F. אם φ\varphiφ התקבל מ-fff כלשהי, אזי אורכו אינו 111. לכן, φ∈Vars\varphi \in Varsφ∈Vars ותנאים 2,32,32,3 אינם מתקיימים.

  • אם \varphi=(\lnot\dots) אזי φ\varphiφ התקבל מ-f_{\lnot}(\alpha) כאשר α\alphaα מתקבלת באופן יחיד מהסרת (\lnot ו-))). נשים לב כי זוהי האפשרוית היחידה במצב הזה שכן φ\varphiφ אינו פסוק אטומי כי ∣φ∣>1|\varphi|>1∣φ∣>1 ובנוסף, φ\varphiφ אינו מהצורה (α☺︎β)(\alpha ☺︎\beta)(α☺︎β). כלומר, לא קיימים α,β∈WFF\alpha,\beta \in WFFα,β∈WFF כך ש-φ=f☺︎(α,β)\varphi=f_{☺︎}(\alpha,\beta)φ=f☺︎​(α,β).
    נניח בשלילה כי קיימים α,β\alpha,\betaα,β כאלו, אז α\alphaα מתחיל ב-\Large\lnot. ניתן להוכיח באינדוקצית מבנה, כי לכל α∈WFF\alpha \in WFFα∈WFF או α∈Vars\alpha \in Varsα∈Vars או α=(…\alpha=(\dotsα=(…. (פרמלו)
    ולכן, לא קיימים α,β\alpha,\betaα,β שכאלו ולכן, בהכרח 333 לא מתקיים.

  • אם φ\varphiφ אינו מהצורה 1,21,21,2 הוא חייב להיות מהצורה 333. נראה כי α,β\alpha,\betaα,β אכן מתקבלים באופן יחיד ולשם כך ונוכיח תכונות סוגריים של פסוקים ב-WFFWFFWFF.

    1. טענה: בכל φ∈WFF\varphi \in WFFφ∈WFF מתקיים #((φ)=#)(φ)\#_{(}(\varphi)=\#_{)}(\varphi)#(​(φ)=#)​(φ).
      הוכחה: באינדוקציית מבנה.
      בסיס: לכל pi∈Varsp_{i}\in Varspi​∈Vars מתקיים: #((φ)=0=#)(φ)\#_{(}(\varphi)=0=\#_{)}(\varphi)#(​(φ)=0=#)​(φ).
      צעד: יהיו α,β\alpha,\betaα,β כך ש-#((α)=#)(α)\#_{(}(\alpha)=\#_{)}(\alpha)#(​(α)=#)​(α) וגם #((β)=#)(β)\#_{(}(\beta)=\#_{)}(\beta)#(​(β)=#)​(β). אזי, אם נפעיל את f_{\lnot} נקבל \#_{(}(\lnot\alpha)=1+\#_{(}(\alpha) ו-\#_{)}(\lnot\alpha)=1+\#_{)}(\alpha). לפי הנחת האינדוקציה נקבל: \#_{)}(\lnot\alpha)=\#_{)}(\lnot\alpha).
      עבור ☺︎∈{∧,∨,→}☺︎ \in \left\{ \land,\lor,\to \right\}☺︎∈{∧,∨,→} והפונקציה f☺︎(α,β)=(α☺︎β)f_{☺︎}(\alpha,\beta)=(\alpha☺︎\beta)f☺︎​(α,β)=(α☺︎β) מתקיים: #((α☺︎β)=1+#((α)+#((β)\#_{(}(\alpha☺︎\beta)=1+\#_{(}(\alpha)+\#_{(}(\beta)#(​(α☺︎β)=1+#(​(α)+#(​(β) ו-#)(α☺︎β)=1+#)(α)+#)(β)\#_{)}(\alpha☺︎\beta)=1+\#_{)}(\alpha)+\#_{)}(\beta)#)​(α☺︎β)=1+#)​(α)+#)​(β). ואז, לפי הנחת האינדוקציה: #((α☺︎β)=#)(α☺︎β)\#_{(}(\alpha☺︎\beta)=\#_{)}(\alpha☺︎\beta)#(​(α☺︎β)=#)​(α☺︎β).
    2. טענה: יהי φ∈WFF\varphi \in WFFφ∈WFF. אזי בכל רישא ממש φ′\varphi'φ′ לא ריקה של φ\varphiφ (רישא ממש אומר φ≠φ′\varphi\neq \varphi'φ=φ′) מתקיים #(φ′>#)φ′\#_{(}\varphi'>\#_{)}\varphi'#(​φ′>#)​φ′.
      הוכחה: באינדוקצית מבנה.
      בסיס: ל-pi∈Varsp_{i}\in Varspi​∈Vars אין רישות ממש לא ריקות ולכן זה נכון באופן ריק.
      צעד: יהיו α,β∈WFF\alpha,\beta \in WFFα,β∈WFF שמקיימים את התוכנה. נוכיח עבור (\lnot\alpha) ועבור (α☺︎β)(\alpha☺︎\beta)(α☺︎β):
      • נתחיל מ-(\lnot\alpha).
        עבור ((( מתקיים #(=1>0=#)\#_{(}=1>0=\#_{)}#(​=1>0=#)​. עבור (\lnot מתקיים #(=1>0=#)\#_{(}=1>0=\#_{)}#(​=1>0=#)​. תהי α′\alpha'α′ רישא ממש של α\alphaα. אזי, עבור (\lnot\alpha'
        מתקיים: #(=1+#((α′)>#)(α′)=#)\#_{(}=1+\#_{(}(\alpha')>\#_{)}(\alpha')=\#_{)}#(​=1+#(​(α′)>#)​(α′)=#)​ לפי הנחת האינדוקציה. לבסוף, עבור (\lnot\alpha מתקיים #(=1+#((α)>#)(α)=#)\#_{(}=1+\#_{(}(\alpha)>\#_{)}(\alpha)=\#_{)}#(​=1+#(​(α)>#)​(α)=#)​ שכן, לפי תכונה 1 מתקיים #((α)=#)(α)\#_{(}(\alpha)=\#_{)}(\alpha)#(​(α)=#)​(α).
      • כעת, עבור (α☺︎β)(\alpha☺︎\beta)(α☺︎β).
        \begin{align*} &( && \#_{(}=1>0=\#_{)}\\ &(\alpha' && \#_{(}=1+\#_{(}(\alpha')>\#_{)}(\alpha')=\#_{)} \\ &(\alpha && \#_{(}=1+\#_{(}(\alpha)>\#_{)}(\alpha)=\#_{)} \\ &(\alpha ☺ && \#_{(}=1+\#_{(}(\alpha)>\#_{)}(\alpha)=\#_{)} \\ &(\alpha ☺ \beta' && \#_{(}=1+\#_{(}(\alpha)+\#_{(}(\beta')>\#_{)}(\alpha)+\#_{)}(\beta')=\#_{)} \\ &(\alpha ☺ \beta & & \#_{(}=1+\#_{(}(\alpha)+\#_{(}(\beta)>\#_{)}(\alpha)+\#_{)}(\beta)=\#_{)} \end{align*}
    3. מסקנה: יהי φ∈WFF\varphi \in WFFφ∈WFF ותהי φ′\varphi'φ′ רישא ממש לא ריקה שלו. אזי φ′∉WFF\varphi'\not\in WFFφ′∈WFF.
      הסבר: אין בה סוגריים מאוזנים.

    יהי φ=(α☺β)\varphi=(\alpha ☺ \beta)φ=(α☺β). נראה כעת כי α,β,☺\alpha,\beta,☺α,β,☺ מתקבלים באופן יחיד.
    נניח בשלילה כי φ=(α☺β)\varphi=(\alpha ☺ \beta)φ=(α☺β) וגם φ=(α′☹β′)\varphi=(\alpha'☹\beta')φ=(α′☹β′) כאשר α≠α′\alpha \neq \alpha'α=α′ וגם β≠β′\beta\neq\beta'β=β′ אך כולם ב-WFFWFFWFF.
    נניח בה"כ כי ∣α∣<∣α′∣|\alpha|<|\alpha'|∣α∣<∣α′∣. אזי, α\alphaα רישא ממש לא ריקה של α′\alpha'α′ וזוהי סתירה לכך ש-α∈WFF\alpha \in WFFα∈WFF לפי טענה 2.
    אם ∣α∣=∣α′∣|\alpha|=|\alpha'|∣α∣=∣α′∣ אזי בהכרח α=α′\alpha=\alpha'α=α′ בסתירה לכך ש-α≠α′\alpha\neq \alpha'α=α′.
    הערה: קיבלנו אלגוריתם לזיהוי α,β\alpha,\betaα,β: נספור סוגריים משמאל עד שנגיע לאיזון (לא כולל ה-((( הראשון)
    ∎

סמנטיקה

לכל שפה, גם טבעית וגם פורמלית יש שני רבדים עקריים:

  • הסינטקס: חוקי הדקדוק, איך צורנית בנויות המילים.
  • הסמנטיקה: מהי המשמעות של המילים.
דוגמה

נסתכל על 3,III3,\mathrm{III}3,III: סינטאקטית הם שונים אך סמנטית הם זהים.

הגדרה 2 (סמנטיקה של תחשיב הפסוקים)

נגדיר קבוצת ערכי אמת: {0,1}\left\{ 0,1 \right\}{0,1} והשמה: z:Vars→{0,1}z:Vars\to \left\{ 0,1 \right\}z:Vars→{0,1} לקבלת: ASN={z  |  השמה  z}ASN=\left\{ z \smid \R{\text{השמה}}\;z \right\}ASN={z∣השמהz} (כאשר ASNASNASN זה קיצור ל-assignment)

הערה

פעם ASNASNASN הייתה מסומנת ASSASSASS.

דוגמה (להשמה)

∀i∈N:  z(pi)=1\forall i\in \mathbb{N}:\;z(p_{i})=1∀i∈N:z(pi​)=1

לרוב נסמן השמה זו: z1z_{1}z1​. באופן דומה:

∀i∈N:  z0(pi)=0\forall i\in \mathbb{N}:\;z_{0}(p_{i})=0∀i∈N:z0​(pi​)=0

וכמובן יכולות להיות עוד הרבה השמות אחרות, נניח ∀i∈N:  z(pi)=i ⁣ ⁣ ⁣(mod  2)\forall i\in \mathbb{N}:\;z(p_{i})=i\pmod{2}∀i∈N:z(pi​)=i(mod2).

הערה

עוצמת קבוצת ההשמות: ∣ASN∣=2ℵ0|ASN|=2^{\aleph_{0}}∣ASN∣=2ℵ0​. זאת מכיוון שניתן לחשוב על כל הפסוקים כוקטור בינארי ∞\infty∞.
כלומר, זה לא ∞\infty∞ בן מניה.

הערה

נשים לב כי ∣WFF∣=ℵ0|WFF|=\aleph_{0}∣WFF∣=ℵ0​ ונראה בהמשך למה זה משמש.