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

1 - הקבוצה הנוצרת וסדרות יצירה

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

1 - הקבוצה הנוצרת וסדרות יצירה

02340292

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

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

הקבוצה הנוצרת וסדרות יצירה

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

uni-folder.vercel.app

הגדרה 1 (סגירות תחת פונקציה)

תהי XXX קבוצה ותהי פונקציה f:X→Xf:X\to Xf:X→X. תהי A⊆XA \subseteq XA⊆X.
הקבוצה AAA נקראת סגורה תחת fff אם לכל a∈Aa \in Aa∈A מתקיים f(a)∈Af(a)\in Af(a)∈A.

הגדרה 2 (סגירות תחת קבוצת פונקציות)

תהי XXX קבוצה ותהי FFF קבוצה של פונקציות מעל XXX. כלומר, לכל f∈Ff \in Ff∈F קיימת מקומיות k∈N+k \in \mathbb{N}^+k∈N+ כך ש-f:Xk→Xf:X^k\to Xf:Xk→X.
תהי A⊆XA \subseteq XA⊆X. נאמר כי AAA סגורה תחת FFF אם לכל f∈Ff \in Ff∈F ולכל a1,…,ak∈Aa_{1},\dots,a_{k}\in Aa1​,…,ak​∈A מתקיים ש-f(a1,…,ak)∈Af(a_{1},\dots,a_{k})\in Af(a1​,…,ak​)∈A.

הגדרה 3 (קבוצה נוצרת (אינדוקטיבית))

יהיו B⊆WB \subseteq WB⊆W ו-FFF אוסף כללי יצירה (פונקציות מעל WWW)
נסמן ב-Λ\LambdaΛ את אוסף הקבוצות המכילות את BBB וסגורות תחת FFF. הקבוצה הנוצרת ע"י BBB ו-FFF הינה:

WB,F:=⋂A∈ΛAW_{B,F}:= \bigcap_{A \in \Lambda} AWB,F​:=A∈Λ⋂​A
הערה

תמיד תהיה קבוצה WB,FW_{B,F}WB,F​ שכן תמיד יש לנו את WWW שהוא העולם כולו, והפונקציות ב-FFF חייבות להיות סגורות תחת WWW לפי משפט.

הגדרה 4 (סדרת יצירה)

סדרת יצירה מעל XB,FX_{\small B,F}XB,F​ עבור איבר a∈Xa \in Xa∈X היא סדרה סופית a1,a2,…,ana_{1},a_{2},\dots,a_{n}a1​,a2​,…,an​ כך ש:
א. a=ana =a_{n}a=an​.
ב. לכל 1≤i≤n1\leq i\leq n1≤i≤n או ai∈Ba_{i}\in Bai​∈B או aia_{i}ai​ התקבל מהפעלת f∈Ff \in Ff∈F על איברים מתוך a1,…,ai−1a_{1},\dots,a_{i-1}a1​,…,ai−1​.

הערה

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

תרגיל

נגדיר את העולם כאוסף המחרוזות W={0,1,…,9,(,),+,−}∗W=\left\{ 0,1,\dots,9,(,),+,- \right\}^*W={0,1,…,9,(,),+,−}∗, את הבסיס כ-B={0,1,…,9}∗B=\left\{ 0,1,\dots,9 \right\}^*B={0,1,…,9}∗ ואת כללי היצירה:

F={f+(x,y)=(x+y),f−(x,y)=(x−y)}F=\left\{ \begin{matrix} f_{+}(x,y)=(x+y), \\ f_{-}(x,y)=(x-y) \end{matrix} \right\}F={f+​(x,y)=(x+y),f−​(x,y)=(x−y)​}

מי מבין האיברים הבאים שייך ל-WB,FW_{B,F}WB,F​?
א. 424242 ב. (42−(1+1))(42-(1+1))(42−(1+1)) ג. −3-3−3.

פתרון א':
424242 כן נמצא שכן 42∈B42 \in B42∈B שכן B=⋃i=1∞{σ1σ2…σi∣∀1≤j≤i:  σi∈{0,1,…,9}}\displaystyle B=\bigcup_{i=1}^\infty \left\{ \sigma_{1}\sigma_{2}\dots\sigma_{i} \mid \forall 1\leq j\leq i:\; \sigma_{i}\in \left\{ 0,1,\dots,9 \right\} \right\}B=i=1⋃∞​{σ1​σ2​…σi​∣∀1≤j≤i:σi​∈{0,1,…,9}}. באופן פורמלי:
לפי הגדרת BBB מתקיים 42∈B42 \in B42∈B. לפי תכונות הקבוצה האינדוקטיבית נובע כי 42∈B⊆WB,F42 \in B \subseteq W_{B,F}42∈B⊆WB,F​.

פתרון ב':
נתון כי 1∈B1 \in B1∈B ולכן, לפי תכונות קבוצה אינדוקטיבית נובע כי 1∈B⊆WB,F1 \in B \subseteq W_{B,F}1∈B⊆WB,F​.
יש סגירות תחת f+f_{+}f+​ ולכן, (1+1)=f+(1,1)∈WB,F(1+1)=f_{+}(1,1)\in W_{B,F}(1+1)=f+​(1,1)∈WB,F​.
יש סגירות תחת f−f_{-}f−​ ולכן, (42−(1+1))=f−(42,f+(1,1))∈WB,F(42-(1+1))=f_{-}(42,f_+(1,1))\in W_{B,F}(42−(1+1))=f−​(42,f+​(1,1))∈WB,F​.
לכן, (42−(1+1))∈WB,F(42-(1+1))\in W_{B,F}(42−(1+1))∈WB,F​.

הערה

היינו יכולים ליצור את סדרת היצירה:

  • 424242 נמצא בבסיס. נקבע a1=42a_{1}=42a1​=42.
  • 111 נמצא בבסיס. נקבע a2=1a_{2}=1a2​=1.
  • נקבע a3=f+(a2,a2)=(1+1)a_{3}=f_{+}(a_{2},a_{2})=(1+1)a3​=f+​(a2​,a2​)=(1+1).
  • נקבע a4=f−(a1,a3)=(42−(1+1))a_{4}=f_{-}(a_{1},a_{3})=(42-(1+1))a4​=f−​(a1​,a3​)=(42−(1+1)).

מכיוון שקיימת סדרת יצירה עבור a4a_{4}a4​ מעל B,FB,FB,F אזי מתקיים a4∈WB,Fa_{4}\in W_{B,F}a4​∈WB,F​.

פתרון ג':
האיבר −3-3−3 אינו יכול להיות בקבוצה הזו. באופן פורמלי נשתמש באינדוקציית מבנה:

משפט (ההוכחה באינדוקציית מבנה)

נתונה קבוצה XXX, תת קבוצה B⊆XB \subseteq XB⊆X וקבוצת פונקציות FFF מעל XXX.
נתונה T⊆XT \subseteq XT⊆X. אם מתקיימים התנאים הבאים:

  1. מתקיים B⊆TB \subseteq TB⊆T
  2. הקבוצה TTT סגורה תחת FFF

אזי, XB,F⊆TX_{\small B,F}\subseteq TXB,F​⊆T

הוכחת ג':
נגדיר T=B∪{{(}⋅w⋅{)}∣w∈W}T=B \cup \left\{ \left\{ ( \right\}\cdot w \cdot\left\{ ) \right\} \mid w \in W \right\}T=B∪{{(}⋅w⋅{)}∣w∈W}.
בסיס: B⊆TB \subseteq TB⊆T לפי הגדרה.
סגור: נקח f∈Ff \in Ff∈F ונקח x,y∈Tx,y \in Tx,y∈T.
אם f=f+f=f_{+}f=f+​ אזי f+(x,y)=(x+y)f_{+}(x,y)=(x+y)f+​(x,y)=(x+y). מתקיים כי x+y∈Wx+y \in Wx+y∈W ולכן, (x+y)∈T(x+y)\in T(x+y)∈T.
אם f=f−f=f_{-}f=f−​ אזי f−(x,y)=(x−y)f_{-}(x,y)=(x-y)f−​(x,y)=(x−y). מתקיים כי x−y∈Wx-y\in Wx−y∈W ולכן (x−y)∈T(x-y)\in T(x−y)∈T.
לכן, לפי הגדרה, TTT סגורה תחת FFF.

לפי אינדוקציית מבנה, WB,F⊆TW_{B,F}\subseteq TWB,F​⊆T. מכיוון ש-−3∉T-3 \not\in T−3∈T מתקיים כי −3∉WB,F-3 \not\in W_{B,F}−3∈WB,F​.
∎

תרגיל

יהיו קבוצה WWW, בסיס B⊆WB \subseteq WB⊆W וקבוצות כללי יצירה F1F_{1}F1​ ו-F2F_{2}F2​.
א. הוכיחו/הפריכו: WB,F1∪WB,F2⊆WB,F1∪F2W_{B,F_{1}}\cup W_{B,F_{2}}\subseteq W_{B,F_{1}\cup F_{2}}WB,F1​​∪WB,F2​​⊆WB,F1​∪F2​​.
ב. הוכיחו/הפריכו: WB,F1∪F2⊆WB,F1∪WB,F2W_{B,F_{1}\cup F_{2}}\subseteq W_{B,F_{1}}\cup W_{B,F_{2}}WB,F1​∪F2​​⊆WB,F1​​∪WB,F2​​.

טענה א' נכונה.
הוכחה א': (באמצעות אינדוקציית מבנה)
לפי הגדרת קבוצה אינדוקטיבית, B⊆WB,F1∪F2B \subseteq W_{B,F1\cup F_{2}}B⊆WB,F1∪F2​​.
לפי הגדרת קבוצה אינדוקטיבית, WB,F1∪F2W_{B,F_{1}\cup F_{2}}WB,F1​∪F2​​ סגורה תחת F1∪F2F_{1}\cup F_{2}F1​∪F2​. לכל f∈F1f \in F_{1}f∈F1​ מתקיים f∈F1∪F2f \in F_{1}\cup F_{2}f∈F1​∪F2​ לפי הגדרת איחוד ולכן, WB,F1∪F2W_{B,F_{1}\cup F_{2}}WB,F1​∪F2​​ סגורה תחת F1F_{1}F1​.
לכן, לפי אינדוקציית מבנה, WB,F1⊆WB,F1∪F2W_{B,F_{1}}\subseteq W_{B,F_{1}\cup F_{2}}WB,F1​​⊆WB,F1​∪F2​​.
באותו האופן, WB,F2⊆WB,F1∪F2W_{B,F_{2}}\subseteq W_{B,F_{1}\cup F_{2}}WB,F2​​⊆WB,F1​∪F2​​.
לפי תכונות האיחוד, WB,F1∪WB,F2⊆WB,F1∪F2W_{B,F_{1}}\cup W_{B,F_{2}}\subseteq W_{B,F_{1}\cup F_{2}}WB,F1​​∪WB,F2​​⊆WB,F1​∪F2​​.
∎

טענה ב' אינה נכונה.
הפרכה ב':
נגדיר א"ב Σ={a,b}\Sigma=\left\{ a,b \right\}Σ={a,b} ונקח את העולם שלנו להיות W=Σ∗W=\Sigma^*W=Σ∗ ואת הבסיס שלנו להיות B={ε}B=\left\{ \epsilon \right\}B={ε}.
נגדיר F1={fa(x)=xa}F_{1}=\left\{ f_{a}(x)=xa \right\}F1​={fa​(x)=xa} ו-F2={fb(x)=xb}F_{2}=\left\{ f_{b}(x)=xb \right\}F2​={fb​(x)=xb}.
נשים לב כי ε∈B⊆WB,F1∪F2\epsilon \in B \subseteq W_{B,F_{1}\cup F_{2}}ε∈B⊆WB,F1​∪F2​​ מהגדרת קבוצה אינדוקטיבית. f(ε)∈WB,Ff(\epsilon)\in W_{B,F}f(ε)∈WB,F​ לפי תכונת סגירות של קבוצה אינדוקטיבית.
נגדיר את TTT כקבוצת כל המילים המכילות רק aaa-ים. אזי ε∈T\epsilon \in Tε∈T באופן ריק ולכן B⊆TB \subseteq TB⊆T.