חזור לתיקייה: שיעורי בית

גליון 1

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

גליון 1

02340292

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

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

גליון 1

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

uni-folder.vercel.app

תרגיל 2

תרגיל (2)

יהיו WWW קבוצה, B⊆WB \subseteq WB⊆W בסיס ו-FFF קבוצת פעולות (פונקציות מעל WWW). נסמן ב-Λ\LambdaΛ את אוסף הקבוצות המוכלות ב-WWW אשר מכילות את BBB וסגורות תחת FFF. נגדיר את הקבוצות הבאות:
א. X={x∈W∣B,F קיימת סדרת יצירה מעלx-ל}X=\left\{ x\in W \mid B,F \R{\text{ קיימת סדרת יצירה מעל}} x\text{-ל}\right\}X={x∈W∣B,F קיימת סדרת יצירה מעלx-ל}
ב. YYY היא קבוצה המכילה את BBB וסגורה תחת FFF והיא הקבוצה הקטנה ביותר המקיימת זאת: לכל קבוצה Y′Y'Y′ המכילה את BBB וסגורה תחת FFF מתקיים Y⊆Y′Y \subseteq Y'Y⊆Y′.
ג. Z=⋂A∈ΛAZ=\bigcap_{A \in\Lambda}AZ=⋂A∈Λ​A.
הראו כי X=Y=ZX=Y=ZX=Y=Z.

הוכחה:
נראה תחילה כי X⊆YX \subseteq YX⊆Y.
לפי הגדרה, הקבוצה YYY הינה הקבוצה האינדוקטיבית WB,FW_{B,F}WB,F​.
יהי x∈Xx \in Xx∈X. אזי קיימים x=an,an−1,…,a2,a1∈Wx=a_{n},a_{n-1},\dots,a_{2},a_{1}\in Wx=an​,an−1​,…,a2​,a1​∈W כך שלכל 1≤i≤n1\leq i\leq n1≤i≤n מתקיים ai∈Ba_{i}\in Bai​∈B או aia_{i}ai​ התקבל מהפעלת f∈Ff \in Ff∈F על איברים מתוך a1,…,ana_{1},\dots,a_{n}a1​,…,an​.
נראה באינדוקציה כי x∈WB,Fx \in W_{B,F}x∈WB,F​:
בסיס: לפי הגדרת סדרת יצירה a1∈Ba_{1} \in Ba1​∈B. לפי הגדרת קבוצה אינדוקטיבית, B⊆WB,FB \subseteq W_{B,F}B⊆WB,F​ ולכן a1∈WB,Fa_{1}\in W_{B,F}a1​∈WB,F​.
צעד: נניח כי קיים 1≤i<n1\leq i<n1≤i<n כך שלכל 1≤j≤i1\leq j\leq i1≤j≤i מתקיים aj∈WB,Fa_j\in W_{B,F}aj​∈WB,F​ ונראה כי aj+1∈WB,Fa_{j+1}\in W_{B,F}aj+1​∈WB,F​.
אם aj+1∈Ba_{j+1}\in Baj+1​∈B אז מתקיים כי aj+1∈WB,Fa_{j+1}\in W_{B,F}aj+1​∈WB,F​ לפי הנ"ל. אחרת, קיים 1≤k≤j1\leq k\leq j1≤k≤j וקיימים איברים aj1,…,ajka_{j_{1}},\dots,a_{j_{k}}aj1​​,…,ajk​​ שהופיעו מוקדם יותר בסדרה, שעבורם קיימת f∈Ff \in Ff∈F כך ש-aj+1=f(aj1,…,ajk)a_{j+1}=f(a_{j_{1}},\dots,a_{j_{k}})aj+1​=f(aj1​​,…,ajk​​) ולכן, aj+1∈WB,Fa_{j+1}\in W_{B,F}aj+1​∈WB,F​.
לכן, an∈WB,Fa_{n}\in W_{B,F}an​∈WB,F​. כלומר x∈WB,Fx \in W_{B,F}x∈WB,F​. כלומר, x∈Yx \in Yx∈Y. לכן, לפי הגדרת הכלה, X⊆YX \subseteq YX⊆Y.

נראה כעת כי Y⊆ZY \subseteq ZY⊆Z.
לפי הגדרה, הקבוצה YYY הינה הקבוצה האינדוקטיבית WB,FW_{B,F}WB,F​.
יהי x∈Yx \in Yx∈Y. לפי הגדרת YYY לכל, A∈ΛA \in \LambdaA∈Λ מתקיים כי Y⊆AY \subseteq AY⊆A ולכן, לפי הגדרת הכלה, x∈Ax \in Ax∈A.
מכיוון שזה מתקיים לכל A∈ΛA \in\LambdaA∈Λ, לפי הגדרת חיתוך מוכלל, x∈⋂A∈ΛAx \in \bigcap_{A \in\Lambda}Ax∈⋂A∈Λ​A ולכן, x∈Zx \in Zx∈Z.
לכן, לפי הגדרת הכלה, Y⊆ZY \subseteq ZY⊆Z.

נראה כעת כי Z⊆XZ \subseteq XZ⊆X.
לכל איבר ב-BBB קיימת סדרת יצירה באורך 1 לפי הגדרת סדרת יצירה מעל B,FB,FB,F ולכן B⊆XB \subseteq XB⊆X.
יהי x∈Xx \in Xx∈X ותהי f∈Ff \in Ff∈F. ל-xxx קיימת סדרת יצירה a1,…,an=xa_{1},\dots,a_{n}=xa1​,…,an​=x לפי הגדרת XXX. נגדיר את סדרת היצירה a1,…,an,an+1=f(x)a_{1},\dots,a_{n},a_{n+1}=f(x)a1​,…,an​,an+1​=f(x). מכיוון שזוהי סדרת יצירה חוקית מעל B,FB,FB,F מתקיים כי f(x)∈Xf(x)\in Xf(x)∈X ולכן, לפי הגדרה, XXX סגורה תחת FFF.
לכן, לפי הגדרה, X∈ΛX \in \LambdaX∈Λ. ולכן, ⋂A∈ΛA⊆X\bigcap_{A \in\Lambda}A \subseteq X⋂A∈Λ​A⊆X שכן לפי הגדרת חיתוך לכל איבר x∈⋂A∈ΛAx \in \bigcap_{A \in\Lambda}Ax∈⋂A∈Λ​A מתקיים כי:

∀A∈Λ:  x∈A\forall A \in\Lambda:\; x \in A∀A∈Λ:x∈A

ובפרט x∈Xx \in Xx∈X.
לכן, לפי הגדרת הקבוצה, Z⊆XZ \subseteq XZ⊆X.

בכך, מתקיים כי Y⊆Z⊆XY \subseteq Z \subseteq XY⊆Z⊆X ובנוסף X⊆YX \subseteq YX⊆Y ולכן, לפי הכלה דו כיוונית, X=YX=YX=Y. בנוסף, Z⊆X⊆YZ \subseteq X \subseteq YZ⊆X⊆Y וגם Y⊆ZY \subseteq ZY⊆Z ולכן, לפי הכלה דו כיוונית Y=ZY=ZY=Z.
לכן, לפי טרנזיטיביות השוויון, X=Y=ZX=Y=ZX=Y=Z.
∎

תרגיל 5

תרגיל (5 [א])

נסמן ב-WFF_{\left\{ \lnot,\to \right\}} את קבוצת הפסוקים החוקיים הנוצרת מהפסוקים האטומיים APAPAP ומכללי היצירה F_{\lnot},F_{\to}.
הגדירו באינדוקציית מבנה מהם תתי הפסוקים של \alpha \in WFF_{\left\{ \lnot,\to \right\}}.

נגדיר f:WFF_{\left\{ \lnot,\to \right\}}\to \mathbb{P}(WFF_{\left\{ \lnot,\to \right\}}) כך שלכל פסוק \alpha \in WFF_{\left\{ \lnot,\to \right\}} מתקיים כי f(α)f(\alpha)f(α) היא קבוצת תת הפסוקים של α\alphaα.
בסיס: (עבור α∈AP\alpha \in APα∈AP) מתקיים כי f(α)={α}f(\alpha)=\left\{ \alpha \right\}f(α)={α}.
צעד: נחלק למקרים.

  • עבור \beta \in WFF_{\left\{ \lnot,\to \right\}} שנסמן f(β)=Bf(\beta)=Bf(β)=B המקיימת F_{\lnot}(\beta)=\alpha. אזי, מתקיים כי: f(\alpha)=\left\{ (\lnot\beta) \right\}\cup B וזאת מכיוון ש-F_{\lnot}(\beta)=(\lnot\beta)=\alpha.
  • עבור \beta,\gamma \in WFF_{\left\{ \lnot,\to \right\}} שנסמן f(β)=B,f(γ)=Cf(\beta)=B,f(\gamma)=Cf(β)=B,f(γ)=C המקיימים F→(β,γ)=αF_{\to}(\beta,\gamma)=\alphaF→​(β,γ)=α. אזיף מתקיים כי f(α)={(β→γ)}∪B∪Cf(\alpha)=\left\{ (\beta\to\gamma) \right\}\cup B \cup Cf(α)={(β→γ)}∪B∪C שכן F→(β,γ)=(β→γ)F_{\to}(\beta,\gamma)=(\beta\to\gamma)F→​(β,γ)=(β→γ).
תרגיל (5 [ב])

נסמן ב-WFF_{\left\{ \lnot,\to \right\}} את קבוצת הפסוקים החוקיים הנוצרת מהפסוקים האטומיים APAPAP ומכללי היצירה F_{\lnot},F_{\to}.
תהא B \subseteq WFF_{\left\{ \lnot,\to \right\}} קבוצת הפסוקים בהם מופיעים לכל היותר 2 פסוקים אטומיים שונים (ייתכנו מספר מופעים של אותו פסוק אטומי) נסמן:

X=WFF_{\left\{ \lnot ,\to \right\}},\;MP(\alpha,\beta)=\begin{cases} \gamma, & \beta=(\alpha\to\gamma)\R{\text{ כך ש-}} \gamma \in WFF\R{\text{אם קיים }} \\ \alpha & \R{\text{אחרת}} \end{cases}

הוכיחו/הפריכו: WFF_{\left\{ \lnot,\to \right\}}\subseteq X_{B,\left\{ MP,F_{\to} \right\}}.

הטענה לא נכונה.
יהיו α,β,γ∈AP\alpha,\beta,\gamma \in APα,β,γ∈AP. מכיוון ש-α,β\alpha,\betaα,β הינם פסוקים אטומיים, בפסוק δ=α→β\delta=\alpha\to\betaδ=α→β יש לכל היותר 2 פסוקים אטומים שונים ולכן, לפי הגדרה, δ∈B\delta \in Bδ∈B ובנוסף, γ∈B\gamma\in Bγ∈B שכן AP⊆BAP \subseteq BAP⊆B.
לפי הגדרת WFF_{\left\{ \lnot,\to \right\}} והגדרת F_{\lnot} מתקיים כי:

\epsilon\underset{\begin{matrix}\downarrow\\ \R{\text{סימון}}\end{matrix}}{=}(\lnot((\alpha\to\beta)\to\gamma))=(\lnot (\delta\to\gamma))=(\lnot F_{\to}(\delta,\gamma))=F_{\lnot}(F_{\to}(\delta,\gamma))\in WFF_{\left\{ \lnot,\to \right\}}

כעת, נניח בשלילה כי ε∈XB,{MP,F→}\epsilon \in X_{B,\left\{ MP,F_{\to} \right\}}ε∈XB,{MP,F→​}​ לפי משפט, קיימת סדרת יצירה ל-ε\epsilonε מעל B,{MP,F→}B,\left\{ MP,F_{\to} \right\}B,{MP,F→​}.
לפי הגדרה, קיימים a1,a2,…,an=εa_{1},a_{2},\dots,a_{n}=\epsilona1​,a2​,…,an​=ε כך שלכל 1≤i≤n1\leq i\leq n1≤i≤n מתקיים ש-ai∈Ba_{i}\in Bai​∈B או ש-aia_{i}ai​ נוצר מהפעלת {MP,F→}\left\{ MP,F_{\to} \right\}{MP,F→​} על איברים מתוך {a1,…,ai−1}\left\{ a_{1},\dots,a_{i-1} \right\}{a1​,…,ai−1​}. נקח את הסדרת היצירה המינימלית עבור ε\epsilonε, כלומר, לכל 1≤i≤n−11\leq i\leq n-11≤i≤n−1 מתקיים כי ai≠εa_{i}\neq\epsilonai​=ε.
מכיוון ש-α,β,γ∈f(ε)\alpha,\beta,\gamma \in f(\epsilon)α,β,γ∈f(ε) מתקיים כי יש בו יותר מ-2 פסוקים אטומיים שונים(שכן α≠β≠γ\alpha\neq \beta\neq\gammaα=β=γ) ולכן, ε∉B\epsilon \not\in Bε∈B ולכן n>1n>1n>1. מכיוון ש-ε\epsilonε מתחיל ב-(\lnot הוא בהכרח לא נוצר מהפונקציה F→F_{\to}F→​ לפי הגדרה.
לכן, קיימים 1≤i,j<n1\leq i,j<n1≤i,j<n כך ש-MP(ai,aj)=εMP(a_{i},a_{j})=\epsilonMP(ai​,aj​)=ε. נחלק למקרים לפי הגדרת MPMPMP:

  • אופציה 1: ε=ai\epsilon=a_{i}ε=ai​ בסתירה לכך שלכל 1≤m≤n−11\leq m \leq n-11≤m≤n−1 מתקיים am≠εa_{m}\neq \epsilonam​=ε.
  • אופציה 2: aj=(ai→ε)a_{j}=(a_{i}\to\epsilon)aj​=(ai​→ε). לפי הגדרת הפסוק, מתקיים כי aj=F→(ai,ε)a_{j}=F_{\to}(a_{i},\epsilon)aj​=F→​(ai​,ε) ולכן, קיים 1≤k≤j−11\leq k\leq j-11≤k≤j−1 כך ש-ak=εa_{k}=\epsilonak​=ε בסתירה לכך שלכל 1≤m≤n−11\leq m \leq n-11≤m≤n−1 מתקיים am≠εa_{m}\neq \epsilonam​=ε.

לכן, הגענו לסתירה ובכך ε∉XB,{MP,F→}\epsilon \not\in X_{B,\left\{ MP,F_{\to} \right\}}ε∈XB,{MP,F→​}​. לכן, לפי הגדרת הכלה WFF_{\left\{ \lnot,\to \right\}}\not\subseteq X_{B,\left\{ MP,F_{\to} \right\}}.