חזור לתיקייה: תרגול

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

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • כללי

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

02340292

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

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

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

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

uni-folder.vercel.app

תרגיל

האם (p0→(p1∨p2))(p_{0}\to(p_{1}\lor p_{2}))(p0​→(p1​∨p2​)) פסוק חוקי?

נגדיר סדרת יצירה ואז, לפי משפט (p0→(p1∨p2))∈WFF(p_{0}\to(p_{1}\lor p_{2}))\in WFF(p0​→(p1​∨p2​))∈WFF.

(AP)p0.1(AP)p1.2(AP)p2.3(F∨(2,3))(p1∨p2).4(F→(1,4))(p0→(p1∨p2)).5\begin{align*} (AP) & & p_{0} && .1 \\ (AP) & & p_{1} & & .2 \\ (AP) & & p_{2} & & .3 \\ (F_{\lor}(2,3)) & & (p_{1}\lor p_{2}) & & .4 \\ (F_{\to}(1,4)) & & (p_{0}\to(p_{1}\lor p_{2})) & & .5 \end{align*}(AP)(AP)(AP)(F∨​(2,3))(F→​(1,4))​​p0​p1​p2​(p1​∨p2​)(p0​→(p1​∨p2​))​​.1.2.3.4.5​
תרגיל

הוכיחו כי (()∉WFF(()\not\in WFF(()∈WFF.

הוכחה:
נגדיר: T={α∈W∣#AP(α)≥1}T=\left\{ \alpha \in W \mid \#_{AP}(\alpha)\geq 1 \right\}T={α∈W∣#AP​(α)≥1}. נראה באינדוקציית מבנה כי WFF⊆TWFF \subseteq TWFF⊆T.
בסיס:

∀pi∈B:  #AP(pi)=1≥1\forall p_{i} \in B:\; \#_{AP}(p_{i})=1\geq1∀pi​∈B:#AP​(pi​)=1≥1

צעד: יהי α,β∈T\alpha,\beta \in Tα,β∈T ונפעיל עליהם את F→F_{\to}F→​.

#AP(F→(α,β))=#AP(α)+#AP(β)≥2≥1\#_{AP}(F_{\to}(\alpha,\beta))=\#_{AP}(\alpha)+\#_{AP}(\beta)\geq 2 \geq 1#AP​(F→​(α,β))=#AP​(α)+#AP​(β)≥2≥1

באותו האופן עבור שאר הפונקציות ובכך TTT סגורה מעל FFF ולכן WFF⊆TWFF \subseteq TWFF⊆T.
מכיוון ש-#AP((())=0\#_{AP}{\Large(}((){\Large)}=0#AP​((())=0 ולכן, (()∉T(()\not\in T(()∈T ובפרט (()∉WFF(()\not\in WFF(()∈WFF.
∎

תרגיל

הוכיחו כי (p_{0}(\lnot p_{1}))\to p_{2} אינו פסוק חוקי.

הוכחה:
נגדיר: T={α∈W∣#AP(α)=#∘(α)+1}T=\left\{ \alpha \in W \mid \#_{AP}(\alpha)=\#_{\circ}(\alpha)+1 \right\}T={α∈W∣#AP​(α)=#∘​(α)+1}
נראה באינדוקציית מבנה כי WFF⊆TWFF \subseteq TWFF⊆T.
בסיס: יהי pi∈APp_{i}\in APpi​∈AP. אזי: #AP(pi)=1=#∘(pi)+1=0+1\#_{AP}(p_{i})=1=\#_{\circ}(p_{i})+1=0+1#AP​(pi​)=1=#∘​(pi​)+1=0+1.
צעד: יהיו α,β∈T\alpha,\beta \in Tα,β∈T. אזי, #AP(α)=#∘(α)+1\#_{AP}(\alpha)=\#_{\circ}(\alpha)+1#AP​(α)=#∘​(α)+1 ו-#AP(β)=#∘(β)+1\#_{AP}(\beta)=\#_{\circ}(\beta)+1#AP​(β)=#∘​(β)+1.

#AP(F→(α,β))=#AP((α→β))=#AP(α)+#AP(β)=#∘(α)+1+#∘(β)+1\#_{AP}(F_{\to}(\alpha,\beta))=\#_{AP}((\alpha\to\beta))=\#_{AP}(\alpha)+\#_{AP}(\beta)=\#_{\circ}(\alpha)+1+\#_{\circ}(\beta)+1#AP​(F→​(α,β))=#AP​((α→β))=#AP​(α)+#AP​(β)=#∘​(α)+1+#∘​(β)+1 #∘(F→(α,β))=#∘((α→β))=#∘(α)+#∘(β)+1\#_{\circ}(F_{\to}(\alpha,\beta))=\#_{\circ}((\alpha\to\beta))=\#_{\circ}(\alpha)+\#_{\circ}(\beta)+1#∘​(F→​(α,β))=#∘​((α→β))=#∘​(α)+#∘​(β)+1

ולכן:

#AP(F→(α,β))=#∘(F→(α,β))+1\#_{AP}(F_{\to}(\alpha,\beta))=\#_{\circ}(F_{\to}(\alpha,\beta))+1#AP​(F→​(α,β))=#∘​(F→​(α,β))+1

כנדרש.
∎