Diszkrét Matematika - Beadandó Feladatok
Demjan Adalbert - SFDAGZ
2014. december 6.
Tartalomjegyzék 1. 2.1-2/c
2
2. 2.2-1/c
3
3. 2.3-13/a
4
4. 2.3-13/b
5
5. 4.1-5/a
6
6. 4.1-5/b
7
7. 4.1-5/c
8
8. 4.4-16
9
9. 4.5-4
10
10.5.2-16
11
11.5.7-15
12
1
1.
2.1-2/c
Bizonyítsuk be, hogy minden A,B,C halmaz esetén A⊆B ⇒A\C ⊆B\C
Az A \ B = A ∩ B azonosságot felhasználva átalakítom az implikált részt. A⊆B ⇒A∩C ⊆B∩C
Ekkor de níció szerint: A ∩ C = {x|x ∈ A ∧ x ∈ C} B ∩ C = {x|x ∈ B ∧ x ∈ C}
Mivel, ha A ⊆ B , akkor x ∈ A ⇒ x ∈ B , így a fentiek alapján x ∈ A ∩ C ⇒ x ∈ B ∩ C,
ami megegyezik A \ C ⊆ B \ C -vel.
2
2.
be:
2.2-1/c
Legyen adott egy ρ ⊆ A × B reláció és legyen A1 , A2 ⊆ A. Bizonyítsuk R%|A1 ∩A2 ⊆ R%|A1 ∩ R%|A2
Elég, ha az értelmezési tartományokra bebizonyítjuk az összefüggést, hiszen ekkor a hozzájuk tartozó értékekre is igaz lesz az állítás. A1 ∩ A2 ⊆ A1 ∩ A2
Mivel a fenti állítás igazságértéke mindig igaz, ezért az eredeti állítást bebizonyítottuk.
3
3.
2.3-13/a
Legyenek f : X → Y és g : Y → Z függvények. Bizonyítsuk be a függvényekre és halmazm¶veletekre vonatkozó alábbi összefüggéseket: f [A ∩ B] ⊆ f [A] ∩ f [B], minden A, B ⊆ X -re
Elég azt vizsgálni, hogy a fenti képek ®sképére igaz-e az összefüggés, mivel adott ®sképekhez adott képek tartoznak. A fenti képek ®sképei: f −1 [A ∩ B] = A ∩ B ∩ Df f −1 [A] = A ∩ Df f −1 [B] = B ∩ Df
Tehát a vizsgálandó összefüggés: A ∩ B ∩ Df ⊆ (A ∩ Df ) ∩ (B ∩ Df )
Mivel a metszet asszociatív és kommutatív, ezért a jobb oldal a következ® alakra hozható: A ∩ B ∩ Df ⊆ A ∩ B ∩ Df ∩ Df
ami A ∩ B ∩ Df ⊆ A ∩ B ∩ Df
Ezzel az állítást bebizonyítottuk, hiszen a fenti összefüggés mindig igaz.
4
4.
2.3-13/b
Legyenek f : X → Y és g : Y → Z függvények. Bizonyítsuk be a függvényekre és halmazm¶veletekre vonatkozó alábbi összefüggéseket: f [A ∪ B] = f [A] ∪ f [B], minden A, B ⊆ X -re
Elég azt vizsgálni, hogy a fenti képek ®sképére igaz-e az összefüggés, mivel adott ®sképekhez adott képek tartoznak. A fenti képek ®sképei: f −1 [A ∪ B] = (A ∪ B) ∩ Df f −1 [A] = A ∩ Df f −1 [B] = B ∩ Df
Tehát a vizsgálandó összefüggés: (A ∪ B) ∩ Df = (A ∩ Df ) ∪ (B ∩ Df )
Mivel a metszet és az unió egymásra nézve disztributív, ezért a jobb oldal a következ® alakra hozható: (A ∪ B) ∩ Df = (A ∪ B) ∩ Df
Ezzel az állítást bebizonyítottuk.
5
5.
4.1-5/a
Bizonyítsuk be, hogy (N; ≤) gyengén trichotom. A fenti reláció gyengén trichotom, mivel minden elem relációban áll egymással, azaz ∀a, b ∈ N(aρb ∨ bρa, esetleg mindkett®)
6
6.
4.1-5/b
Bizonyítsuk be, hogy (N; ≤) teljes rendezés. A fenti reláció teljes rendezés, mivel részbenrendezés: re exív : ∀a ∈ N(aρa) antiszimmetrikus : ∀a, b ∈ N(aρb ∧ bρa ⇒ a = B) tranzitív: ∀a, b, c ∈ N(aρb ∧ bρc ⇒ aρc) és minden eleme összehasonlítható,azaz gyengén trichotom: ∀a, b ∈ N(aρb ∨ bρa, esetleg mindkett®)
7
7.
4.1-5/c
Bizonyítsuk be, hogy (N; ≤) jólrendezés. A fenti reláció jólrendezés, mivel részbenrendezés: re exív : ∀a ∈ N(aρa) antiszimmetrikus : ∀a, b ∈ N(aρb ∧ bρa ⇒ a = B) tranzitív: ∀a, b, c ∈ N(aρb ∧ bρc ⇒ aρc) és minden nem üres részhalmazának van legkisebb eleme.
8
8.
4.4-16
Legyen m, x ∈ Z, m > 0. Bizonyítsuk be, hogy ekkor bmxc =
m−1 P
bx +
i c m
dx −
i e m
i=0
dmxe =
m−1 P i=0
Az els® feladat megoldása: Bal oldal: bmxc = mx ( mivel m, x ∈ Z) Jobb oldal: A szummában lév® mi -es tag minden esetben kisebb mint 1, ezért bx +
Mivel a
m−1 P
bx +
i=0
i c m
i c m
= bxc = x (mivel x ∈ Z)
egy m tagú összeg, így m darab x-et adunk össze,
ami megegyezik m*x-szel. Ezzel megkaptuk a baloldalt. A második feladat megoldása: Bal oldal: dmxe = mx ( mivel m, x ∈ Z) Jobb oldal: A szummában lév® mi -es tag minden esetben kisebb mint 1, ezért dx −
Mivel a
m−1 P
dx −
i=0
i e m
i e m
= dxe = x (mivel x ∈ Z)
egy m tagú összeg, így m darab x-et adunk össze,
ami megegyezik m*x-szel. Ezzel megkaptuk a baloldalt.
9
9.
4.5-4
Adjuk meg az alábbi komplex számok trigonometrikus alakját: √ (1)cosφ − isinφ, (2) − cosφ − isinφ, (3) − 1 − i 3, (4)4i
(1) cosφ + isin(−φ) (2) cos(φ − π) + isin(−φ) + isin 5π ) (3) 2 ∗ (cos 5π 6 6
(4) 4 ∗ (cos π2 + isin π2 )
10
10.
5.2-16
Hány dominóból áll egy szabályos dominókészlet? (A pöttyök száma a dominók két felén 0-9 ig terjed) Az adott dominó mindkét oldalára 10 lehet®ségb®l választhatunk, ekkor ez 10 ∗ 10 = 100 lehet®ség. Azonban ekkor minden olyan lehet®séget kétszer számoltunk, ahol különböz® számú pontok vannak a két oldalon. Ezen lehet®ségek száma 90. Tehát a megoldásunk: 90 2
+ 10 = 55
11
11.
5.7-15
Helyezzünk két üvegtáblát egymásra. Hányféle módon haladhat át vagy ver®dhet vissza egy fénysugár, ha közben pontosan n-szer változtatott irányt? Ha n páros, akkor a páros számú irányváltás miatt a fénysugár átmegy az üveglapokon, és alul jön ki. Ellenkez® esetben a beesési oldalon, azaz felül. Számoljuk össze az n-szer (n ≥ 2) megtör® sugárlehet®ségeket! Ha el®ször az alsó üveg alsó felületén törik meg, akkor onnan annyiféleképpen folytathatja útját, mint amennyiféleképpen n-1 irányváltoztatás esetén haladhat (képzeljük el fejjel lefelé a fénysugár további útját!). Ha viszont a fénysugár els®re már a két üveg határfelületén megtörik, akkor a beesési, fels® felületre ér, onnan újra visszaver®dik, és innen újrakezd®dik a lehet®ségek számolása, de most már csak n-2 irányváltással. A fenti két lehet®ség összege adja a megoldást: an = an−1 + an−2 ,
azaz a fénysugár áthaladási lehet®ségeinek száma a Fibonacci sorozatot követi.
12
