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

גליון 2

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

גליון 2

02340129

מבוא לתורת הקבוצות ואוטומטים למדמח

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

גליון 2

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

uni-folder.vercel.app

תרגיל 2

תרגיל (2 [א])

תהיינה AAA ו-BBB קבוצת. יהי SSS יחס דו-מקומי מעל AAA ויהי TTT יחס דו-מקומי מעל BBB.
נגדיר יחס דו-מקומי RRR מעל A×BA\times BA×B:

R={((a,b),(c,d))∣(a,c)∈S∧(b,d)∈T}R = \{((a, b),(c, d)) | (a, c) \in S \land (b, d) \in T\}R={((a,b),(c,d))∣(a,c)∈S∧(b,d)∈T}

הוכיחו: אם SSS ו-TTT יחסי שקילות, אזי RRR יחס שקילות.

הוכחה:
יהא ((a,b),(c,d))∈R((a,b),(c,d))\in R((a,b),(c,d))∈R. על פי הגדרת RRR מתקיים כי aScaScaSc ו-bTdbTdbTd. על פי הנתון, S,TS,TS,T יחסי שקילות ולכן, על פי הגדרת יחס שקילות, הם יחסים סימטריים. לכן, על פי הגדרת הסמטריות, מתקיים cSacSacSa ו-dTbdTbdTb. ולכן: (c,a)∈S(c,a)\in S(c,a)∈S ו-(d,b)∈T(d,b)\in T(d,b)∈T. ולכן, על פי הגדרת RRR מתקיים: ((c,d),(a,b))∈R((c,d),(a,b))\in R((c,d),(a,b))∈R לכל a,b,c,da,b,c,da,b,c,d ולכן, על פי הגדרת יחס סמטרי, RRR הינו יחס סימטרי.
נקח את (a,b)(a,b)(a,b) ונראה כי הוא ביחס עם עצמו ב-RRR:
על פי הגדרת יחס סמטרי, אנו יודעים כי S,TS,TS,T הינם יחסים רפלקסיביים. לכן, על פי הגדרת הרפלקסיביות aSaaSaaSa ו-bTbbTbbTb. לכן, על פי הגדרת RRR, (a,b)R(a,b)(a,b)R(a,b)(a,b)R(a,b) מתקיים לכל a,ba,ba,b (נראה כי {((a,b),(a,b))∣(a,a)∈S∧(b,b)∈T}\{ ((a,b),(a,b)) |(a,a)\in S \land (b,b)\in T\}{((a,b),(a,b))∣(a,a)∈S∧(b,b)∈T} מתקיים). לכן, על פי הגדרת יחס רפלקסיבי, RRR הינו יחס רפלקסיבי.
יהא ((c,d),(m,n))∈R((c,d),(m,n))\in R((c,d),(m,n))∈R. על פי הגדרת RRR מתקיים cSmcSmcSm ו-dTndTndTn. על פי הגדרת יחס שקילות, S,TS,TS,T טרנזיטיביים ולכן aSmaSmaSm(ראו את החלק הראשון בתשובה) ו-bTnbTnbTn. לכן, על פי הגדרת RRR מתקיים: (a,b)R(m,n)(a,b)R(m,n)(a,b)R(m,n) לכל a,b,c,d,m,na,b,c,d,m,na,b,c,d,m,n ולכן, על פי הגדרת טרנזיטיביות, RRR הוא יחס טרנזיטיבי.

מכיוון ש-RRR מקיים רפלקסיביות, סימטריות וטרנזיטיביות, על פי הגדרת יחס שקילות, RRR הינו יחס שקילות.
∎

תרגיל (2 [ב])

הוכיחו: אם S,TS,TS,T יחסי סדר חלקיים, אזי RRR יחס סדר חלקי.

הוכחה:
הגדרת יחס סדר חלקי אומרת כי יחס סדר חלקי הינו יחס רפלקסיבי, טרנזיטיבי ואנטי סימטרי.
תחילה, נסתכל בהוכחה של סעיף א', ונראה כי הוכחנו כי כאשר T,ST,ST,S יחסים רפלקסיביים אזי RRR הינו יחס רפלקסיבי וכאשר S,TS,TS,T יחסים טרנזיטיביים, אזי RRR הינו יחס טרנזיטיבי.
יהא ((a,b),(c,d))∈R((a,b),(c,d))\in R((a,b),(c,d))∈R כך ש-((c,d),(a,b))∈R((c,d),(a,b))\in R((c,d),(a,b))∈R. על פי הגדרת יחס סדר חלקי, S,TS,TS,T אנטי סימטריות, ולכן, מכיוון ש-aScaScaSc וגם cSacSacSa מתקיים כי a=ca=ca=c ובנוסף, מכיוון ש-bTdbTdbTd וגם dTbdTbdTb מתקיים כי b=db=db=d ולכן, (a,b)=(c,d)(a,b)=(c,d)(a,b)=(c,d). במידה ו-(a,b)≠(c,d)(a,b)\neq(c,d)(a,b)=(c,d), נראה כי או ש-(a,b)R(c,d)(a,b)R(c,d)(a,b)R(c,d) או (c,d)R(a,b)(c,d)R(a,b)(c,d)R(a,b) מתקיימים, או שביחס RRR אין בכלל קשר בין השניים. לכן, על פי הגדרת האנטי-סימטריות, RRR הינו יחס אנטי סימטרי.

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

תרגיל (2 [ג])

הוכיחו/הפריכו: אם S,TS,TS,T יחסי סדר מלאים, אזי RRR יחס סדר מלא.

הוכחה:
על פי סעיף ב', מכיוון שעל פי הגדרת יחס סדר מלא והנתונים שלנו, S,TS,TS,T הינם גם יחסי סדר חלקיים, RRR הינו יחס סדר חלקי.
כעת, נוכיח כי RRR הינו יחס סדר מלא.
יהיו a,c∈Aa,c \in Aa,c∈A כך שמתקיים (a,c)∈S(a,c)\in S(a,c)∈S. על פי הנתון והגדרת יחס סדר מלא, (c,a)∉S(c,a)\not\in S(c,a)∈S.
יהיו b,d∈Bb,d \in Bb,d∈B כך שמתקיים (b,d)∈T(b,d)\in T(b,d)∈T. על פי הנתון והגדרת יחס סדר מלא, (d,b)∉T(d,b)\not\in T(d,b)∈T.
לאור כך, על פי הגדרת RRR מתקיים כי ((a,b),(c,d))∈R((a,b),(c,d))\in R((a,b),(c,d))∈R.
בנוסף, על פי הגדרת RRR כי על מנת שיתקיים ((c,d),(a,b))∈R((c,d),(a,b))\in R((c,d),(a,b))∈R, צריך להתקיים (c,a)∈S(c,a)\in S(c,a)∈S ו-(d,b)∈T(d,b)\in T(d,b)∈T. דבר זה אינו מתקיים על פי הנכתב הנ"ל.
לכן, לכל a,c∈Aa,c \in Aa,c∈A ו-b,d∈Bb,d \in Bb,d∈B מתקיים ((a,b),(c,d))∈R∨((c,d),(a,b))∈R((a,b),(c,d))\in R \lor((c,d),(a,b))\in R((a,b),(c,d))∈R∨((c,d),(a,b))∈R.
לכן, על פי הגדרת יחס סדר מלא, RRR הינו יחס סדר מלא.
∎

תרגיל 4

תרגיל (4 [א])

תהי AAA קבוצה ויהי RRR יחס דו-מקומי מעל AAA.
היחס RRR יקרא אידמפוטנטי אם R2=RR^2=RR2=R.

הוכיחו: אם RRR אידמפוטנטי, אז Rk=RR^k=RRk=R לכל k≥1k\geq 1k≥1 טבעי.

הוכחה:
נוכיח באינדוקציה כי הטענה מתקיימת.
בסיס: אם k=2k=2k=2 אזי, צ.ל כי R2=RR^2=RR2=R. נתון לנו כי RRR אידמפוטנטי, ולכן, על פי הגדרת המושג, R2=RR^2=RR2=R מה שמקיים בדיוק את התנאי.
צעד: נניח כי Rk=RR^k=RRk=R ונוכיח כי Rk+1=RR^{k+1}=RRk+1=R.
על פי הגדרת החזקה, Rk+1=R∘RkR^{k+1}=R \circ R^kRk+1=R∘Rk. על פי הנחת האינדוקציה Rk=RR^k=RRk=R ולכן Rk+1=R∘RR^{k+1}=R \circ RRk+1=R∘R.
על פי הנתון, R2=RR^2=RR2=R, משמע, R∘R=RR \circ R=RR∘R=R ולכן: Rk+1=RR^{k+1}=RRk+1=R.

לכן, Rk=RR^k=RRk=R לכל k≥1k\geq 1k≥1.
∎

תרגיל (4 [ב])

הוכיחו: אם RRR יחס שקילות, אז RRR אידמפוטנטי.

הוכחה:
נתון לנו כי RRR הינו יחס שקילות ולכן מקיים רפלקסיביות, סימטריות וטרנזיטיביות.
לכל a,b∈Aa,b \in Aa,b∈A אשר בשבילם aRbaRbaRb, לאור היותו של היחס RRR רפלקסיבי מתקיים גם כי aRaaRaaRa ולכן מתקיים (a,a)∈R∧(a,b)∈R(a,a)\in R \land (a,b)\in R(a,a)∈R∧(a,b)∈R ולכן על פי הגדרת ההרכבה ועל פי הגדרת החזקה מתקיים (a,b)∈R2(a,b)\in R^2(a,b)∈R2. לכן, על פי הגדרת הכלה מתקיים R⊆R2R \subseteq R^2R⊆R2.
לכל a,b∈Aa,b \in Aa,b∈A אשר בשבילם aR2baR^2baR2b, על פי הגדרת החזקה וההרכבה, מתקיים כי (a,c)∈R∧(c,b)∈R(a,c)\in R \land (c,b)\in R(a,c)∈R∧(c,b)∈R. מכיוון ש-RRR טרנזיטיבי, מתקיים כי (a,b)∈R(a,b)\in R(a,b)∈R. לכן, על פי הגדרת הכלה מתקיים R2⊆RR^2 \subseteq RR2⊆R.
לכן, על פי הכלה דו כיוונית, R2=RR^2=RR2=R, ולכן, על פי הגדרת המושג, RRR הינו יחס אידמפוטנטי.
∎

תרגיל (4 [ג])

הוכיחו/הפריכו: אם RRR אידמפוטנטי, אזי RRR יחס שקילות.

הוכחה:
הטענה אינה נכונה. נסתכל על דוגמה נגדית:
יהי RRR יחס מעל A={1,2}A=\{ 1,2 \}A={1,2} כך:

R={(1,1),(2,2),(1,2)}R=\{ (1,1),(2,2),(1,2) \}R={(1,1),(2,2),(1,2)}

על פי הגדרת ∘\circ∘, R∘R={(a,c)∣(a,b)∈R∧(b,c)∈R}R \circ R=\{ (a,c)|(a,b)\in R \land(b,c)\in R \}R∘R={(a,c)∣(a,b)∈R∧(b,c)∈R}.
על פי הגדרת היחס RRR, לכל איבר aRaaRaaRa, במקרה שלנו 111 ו-222, מתקיים (a,a)∈R∧(a,a)∈R(a,a)\in R \land(a,a)\in R(a,a)∈R∧(a,a)∈R ולכן (a,a)∈R2(a,a)\in R^2(a,a)∈R2.
לאיבר (1,2)(1,2)(1,2) מתקיים ש-(1,1)∈R∧(1,2)∈R(1,1)\in R \land(1,2)\in R(1,1)∈R∧(1,2)∈R ולכן (1,2)∈R2(1,2)\in R^2(1,2)∈R2.
לכן, R2={(1,1),(2,2),(1,2)}R^2=\{ (1,1),(2,2),(1,2) \}R2={(1,1),(2,2),(1,2)} ולכן, על פי הגדרת חזקה: R2=R∘R=RR^2=R \circ R=RR2=R∘R=R ולכן, RRR הינו אידמפוטנטי על פי הגדרה.
היחס RRR אינו מקיים סימטריות, שכן על פי הגדרת הסימטריות, אם היחס סמטרי ומתקיים 1R21R21R2 אזי מתקיים 2R12R 12R1 מה שלא מתקיים ביחס RRR שלנו ולכן, היחס אינו סימטרי.
על פי הגדרת יחס שקילות, כדי שיחס יהיה יחס שקילות הוא צריך להיות סימטרי, מה שלא מתקיים כאן ולכן RRR אינו יחס שקילות.
∎