Diszkr´ et matematika 1. k¨ oz´ epszint
Diszkr´et matematika 1. k¨oz´epszint 2. el˝ oad´as
Nagy G´abor
[email protected] [email protected] compalg.inf.elte.hu/∼ nagy M´erai L´aszl´ o di´ai alapj´an Komputeralgebra Tansz´ ek
2017. ˝ osz
2017. ˝ osz
1.
Diszkr´ et matematika 1. k¨ oz´ epszint
Komplex sz´amok ´abr´azol´asa A komplex sz´amok a komplex sz´ams´ıkon: Im(z) 6 z = a + bi= r (cos ϕ + i sin ϕ) r ϕ
$ -Re(z)
Ha z = a + bi ∈ C, ahol a, b ∈ R, akkor a, Im(z) = b. √ Re(z) = p A (Re(z), Im(z)) vektor hossza: r = a2 + b 2 = |z|2 . A z nemnulla sz´am argumentuma ϕ = arg (z) ∈ [0, 2π) A koordin´at´ak trigonometrikus f¨ uggv´enyekkel kifejezve: Re(z) = a = r · cos ϕ, Im(z) = b = r · sin ϕ
2017. ˝ osz
2.
Diszkr´ et matematika 1. k¨ oz´ epszint
Komplex sz´amok trigonometrikus alakja Defin´ıci´o z ∈ C nemnulla sz´am trigonometrikus alakja a z = r (cos ϕ + i sin ϕ), ahol r > 0 a sz´am abszol´ ut ´ert´eke. Figyelem! A 0-nak nem haszn´aljuk a trigonometrikus alakj´at. A trigonometrikus alak nem egy´ertelm˝ u: r (cos ϕ + i sin ϕ) = r (cos(ϕ + 2π) + i sin(ϕ + 2π)).
Defin´ıci´o Egy nemnulla z ∈ C argumentuma az a ϕ = arg (z) ∈ [0, 2π), melyre z = |z|(cos ϕ + i sin ϕ). z = a + bi algebrai alak; z = r (cos ϕ + i sin ϕ) trigonometrikus alak. Itt a = r cos ϕ, b = r sin ϕ.
2017. ˝ osz
3.
Diszkr´ et matematika 1. k¨ oz´ epszint
´ er´es algebrai alakr´ol trigonometrikus alakra Att´
a + bi = r (cos ϕ + i sin ϕ) a = r cos ϕ b = r sin ϕ
Ha a 6= 0, akkor tgϕ = ba , ´es ´ıgy ϕ=
b arctg a , ha a > 0;
arctg ba + π, ha a < 0.
2017. ˝ osz
4.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Sz´amol´as trigonometrikus alakkal Legyenek z, w ∈ C nemnulla komplex sz´amok: z = |z|(cos ϕ + i sin ϕ), w = |w |(cos ψ + i sin ψ) A szorzatuk: zw = |z|(cos ϕ + i sin ϕ) · |w |(cos ψ + i sin ψ) = = |z||w |(cos ϕ cos ψ − sin ϕ sin ψ + i(cos ϕ sin ψ + sin ϕ cos ψ)) = add´ıci´os k´epletek: cos(ϕ + ψ) = cos ϕ cos ψ − sin ϕ sin ψ sin(ϕ + ψ) = cos ϕ sin ψ + sin ϕ cos ψ = |z||w |(cos(ϕ + ψ) + i sin(ϕ + ψ)) A szorzat abszol´ ut ´ert´eke: |zw | = |z||w |. A szorzat argumentuma: ha 0 ≤ arg (z) + arg (w ) < 2π, akkor arg (zw ) = arg (z) + arg (w ); ha 2π ≤ arg (z) + arg (w ) < 4π, akkor arg (zw ) = arg (z) + arg (w ) − 2π. A sin, cos f¨ uggv´enyek 2π szerint periodikusak, az argumentum meghat´aroz´as´an´al reduk´alni kell az argumentumok ¨ osszeg´et.
5.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Moivre-azonoss´agok T´etel HF Legyenek z, w ∈ C nemnulla komplex sz´amok: z = |z|(cos ϕ + i sin ϕ), w = |w |(cos ψ + i sin ψ), ´es legyen n ∈ N. Ekkor zw = |z||w |(cos(ϕ + ψ) + i sin(ϕ + ψ)); z w
=
|z| |w | (cos(ϕ
− ψ) + i sin(ϕ − ψ)), ha w 6= 0;
z n = |z|n (cos nϕ + i sin nϕ). A sz¨ogek ¨osszead´odnak, kivon´ odnak, szorz´ odnak. Az argumentumot ezek ut´an redukci´oval kapjuk! Geometriai jelent´es Egy z ∈ C komplex sz´ammal val´ o szorz´as a komplex sz´ams´ıkon mint ny´ ujtva-forgat´as hat. |z|-vel ny´ ujt, arg (z) sz¨ oggel forgat.
6.
Diszkr´ et matematika 1. k¨ oz´ epszint
Komplex sz´amok gy¨okei P´elda 8 √ Sz´amoljuk ki 1+i -t: 2 8 8 8 1+i √ √1 + i √1 = = cos π4 + i sin π4 = 2 2 2 = cos 8 · π4 + i sin 8 · π4 = cos 2π + i sin 2π = 1 Tov´abbi komplex sz´amok, melyeknek a 8-adik hatv´anya 1: 1; −1; i : i 8 = (i 2 )4 = (−1)4 = 1; −i; 1+i √ ; − 1+i √ ; 2 2 8 8 1+i 8 √ : i · 1+i √ √ s˝ot: ±i · 1+i = i · = 1 · 1 = 1. 2 2 2
2017. ˝ osz
7.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Gy¨okvon´as A z = |z|(cos ϕ + i sin ϕ) ´es w = |w |(cos ψ + i sin ψ) trigonometrikus alakban megadott komplex sz´amok pontosan akkor egyenl˝oek: |z|(cos ϕ + i sin ϕ) = |w |(cos ψ + i sin ψ), ha |z| = |w | ϕ = ψ + k · 2π valamely k ∈ Z sz´am eset´en. n-edik gy¨okvon´as: Legyen z n = w : z n = |z|n (cos nϕ + i sin nϕ) = |w |(cos ψ + i sin ψ). Ekkor p |z|n = |w | ⇒ |z| = n |w | nϕ = ψ + k · 2π valamely k ∈ Z eset´en, vagyis: ϕ = ψn + k · 2π en. n valamely k ∈ Z eset´ Ha k ∈ {0, 1, . . . , n − 1}, akkor ezek mind k¨ ul¨ onb¨ oz˝ o komplex sz´amot adnak.
8.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Gy¨okvon´as
T´etel Legyen z = |z|(cos ϕ + i sin ϕ), n ∈ N. Ekkor a z n-edik gy¨okei azok a w -k, amikre w n = z: p ϕ 2kπ ϕ 2kπ w = n |z| cos + + i sin + n n n n k = 0, 1, . . . , n − 1.
9.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Gy¨okvon´as
p ϕ 2kπ ϕ 2kπ n w = |z| cos + + i sin + : k = 0, 1, . . . , n − 1. n n n n P´elda q Sz´am´ıtsuk ki a 6 √1−i ´ert´ek´et! 3+i √ √ √2 √ 7π 1 − i = 2 2 − i 22 = 2 cos 7π 4 + i sin 4 √ √ 3 + i = 2 23 + i 12 = 2 cos π6 + i sin π6 Mivel q 6
=
− π6 = 19π ert: 12 , ez´ q 19π = 6 √12 cos 19π = 12 + i sin 12 cos 19π+24kπ + i sin 19π+24kπ : k = 0, 1, . . . , 5. 72 72
7π 4
1−i √ 3+i 1 √ 12 2
10.
Diszkr´ et matematika 1. k¨ oz´ epszint
Komplex egys´eggy¨ok¨ok Defin´ıci´o Az εn = 1 felt´etelnek eleget tev˝ o komplex sz´amok az n-edik egys´eggy¨ok¨ok: 2kπ 2kπ (n) εk = εk = cos + i sin : k = 0, 1, . . . , n − 1. n n Nyolcadik komplex egys´eggy¨ ok¨ ok
6 ε '$ εr3 r 2 rε1 ε4 r 1 rε0 = r r rε7 ε&% 5 ε6
2017. ˝ osz
11.
Diszkr´ et matematika 1. k¨ oz´ epszint
Gy¨okvon´as
Pozit´ıv val´os sz´amok n´egyzetgy¨ oke: legyen r > 0 val´ os sz´am, √ ekkor az x 2 = r megold´asai: ± r .
T´etel Legyen z ∈ C nemnulla komplex sz´am. n ∈ N ´es w ∈ C olyan, hogy w n = z. Ekkor z n-edik gy¨ okei fel´ırhat´ oak a k¨ ovetkez˝ o alakban: w εk : k = 0, 1, . . . n − 1.
Bizony´ıt´as A w εk sz´amok mind n-edik gy¨ ok¨ ok: (w εk )n = w n εnk = z · 1 = z. Ez n k¨ ul¨onb¨oz˝o sz´am, ´ıgy az ¨ osszes gy¨ ok¨ ot megkaptuk.
2017. ˝ osz
12.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Rend Bizonyos komplex sz´amok hatv´anyai periodikusan ism´etl˝odnek: 1, 1, 1, . . . −1, 1, −1, 1, . . . i, −1, −i, 1, i, −1, . . . 1+i √ , i, −1+i √ , −1, −1−i √ , −i, 1−i √ , 1, 1+i √ , i, . . . 2 2 2 2 2 ´ aban: Altal´ 2π cos( 2π ul¨ onb¨ oz˝ o hatv´anya van. n ) + i sin( n )-nek n darab k¨
Defin´ıci´o Egy z komplex sz´am k¨ ul¨ onb¨ oz˝ o (eg´esz kitev˝ os) hatv´anyainak sz´am´at a z rendj´enek nevezz¨ uk ´es o(z)-vel jel¨ olj¨ uk. P´elda 1 rendje 1; 2 rendje ∞ : 2, 4, 8, 16, . . . ; −1 rendje 2: 1, −1; i rendje 4: 1, i, −1, −i.
13.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Rend
T´etel Egy z komplex sz´amnak vagy b´armely k´et eg´esz kitev˝ os hatv´anya k¨ ul¨onb¨oz˝o (ilyenkor a rendje v´egtelen), vagy pedig a hatv´anyok a rend szerint periodikusan ism´etl˝ odnek. A rend a legkisebb olyan pozit´ıv d sz´am, melyre z d = 1. Tov´abb´a z k = z l ⇔ o(z)|k − l. Speci´alisan z k = 1 ⇔ o(z)|k.
Bizony´ıt´as NB. Tal´an k´es˝obb...
14.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Primit´ıv gy¨ok¨ok Az n-edik egys´eggy¨ok¨ok rendje nem felt´etlen¨ ul n: 4-edik egys´eggy¨ok¨ok: 1, i, −1, −i. 1 rendje 1; −1 rendje 2; i rendje 4.
Defin´ıci´o Az n-ed rend˝ u n-edik egys´eggy¨ ok¨ ok a primit´ıv n-edik egys´eggy¨ok¨ok. A t´etel k¨ovetkezm´enyei:
K¨ovetkezm´eny Egy primit´ıv n-edik egys´eggy¨ ok hatv´anyai pontosan az n-edik egys´eggy¨ok¨ok. Egy primit´ıv n-edik egys´eggy¨ ok pontosan akkor k-adik egys´eggy¨ok, ha n|k.
15.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Primit´ıv egys´eggy¨ok¨ok P´elda Primit´ıv 1. egys´eggy¨ ok: 1; Primit´ıv 2. egys´eggy¨ ok: −1;
√
3 Primit´ıv 3. egys´eggy¨ ok¨ ok: −1±i ; 2 Primit´ıv 4. egys´eggy¨ ok¨ ok: ±i; Primit´ıv 5. egys´eggy¨ ok¨ ok: . . . (HF)
Primit´ıv 6. egys´eggy¨ ok¨ ok:
√ 1±i 3 . 2
´ ıt´as(NB.) All´ Egy cos 2kπ + i sin 2kπ n-edik egys´eggy¨ ok pontosan akkor primit´ıv n n n-edik egys´eggy¨ok, ha (n, k) = 1.
16.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Matematikai logika
A logika a helyes k¨ovetkeztet´es tudom´anya. Alkalmaz´asi ter¨ uletek: matematika; informatika; mesters´eges intelligencia; ... P´elda Minden bog´ar rovar. tagad´as: Van olyan bog´ar, ami nem rovar. Esik az es˝o, de meleg van, b´ar a nap is elb´ ujt, ´es az id˝o is k´es˝ore j´ar. tagad´as: ?
17.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Axiomatikus m´odszer
A tudom´anyok a val´os´ag egy r´esz´enek modellez´es´evel foglalkoznak. Axiomatikus m´odszer: k¨ ozismert, nem defini´alt fogalmakb´ol (alapfogalmakb´ol) ´es bizonyos feltev´esekb˝ ol (axi´ om´akb´ ol) a logika szab´alyai szerint milyen k¨ ovetkeztet´eseket vonunk le (milyen t´eteleket bizony´ıtunk). P´elda Euklid´ eszi geometria Alapfogalmak Axi´ om´ak pont, p´arhuzamoss´agi axi´oma, egyenes, ... s´ık. Az axiomatikus m´odszer el˝ onye: el´eg ellen˝ orizni az axi´ om´ak teljes¨ ul´es´et.
18.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Predik´atumok
Defin´ıci´o Predik´atum: olyan v´altoz´ okt´ ol f¨ ugg˝ o defini´alatlan alapfogalom, amelyhez a v´altoz´oik ´ert´ek´et˝ol f¨ ugg˝ oen valamilyen igazs´ag´ert´ek tartozik: igaz (I , ↑), hamis (H, ↓), ´es a kett˝ o egyidej˝ uleg nem teljes¨ ul. P´elda M(): Minden jog´asz hazudik. Sz(x): x egy sz´am. E (x): x egy egyenes. P(x): x egy pont. I (x, y ): x illeszkedik y -ra. F (x, y ): x az y f´erje. Gy (x, y , z): x az y ´es z gyermeke.
0-v´altoz´ os, ´ert´eke: I. 1-v´altoz´ os, ´ert´eke: Sz(1)=I, SZ(h)=H. 1-v´altoz´ os. 1-v´altoz´ os. 2-v´altoz´ os. 2-v´altoz´ os. 3-v´altoz´ os.
19.
Diszkr´ et matematika 1. k¨ oz´ epszint
Logikai jelek A predik´atumokat logikai jelekkel tudjuk ¨ osszek¨ otni: Tagad´ as, jele: ¬A. ´ jele: A ∧ B. Es, Vagy, (megenged˝o), jele: A ∨ B. Ha..., akkor... (implik´aci´ o), jele: A ⇒ B. Ekvivalencia, jele: A ⇔ B. Igazs´ agt´ abl´ azat A B ¬A A ∧ B I I H I I H H H H I I H H H I H
A∨B I I I H
A⇒B I H I I
A⇔B I H H I
2017. ˝ osz
20.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Logikai jelek A k¨oznyelvben a vagy h´aromf´ele ´ertelemmel b´ırhat: ´ Megenged˝o vagy ”Atok re´a ki gy´avas´agb´ ol vagy lomhas´agb´ol elmarad,. . . ” A∨B I H I I I H I H Kiz´ar´o vagy: ”Vagy bolondok vagyunk ´es elvesz¨ unk egy sz´alig, vagy ez a mi hit¨ unk val´os´agra v´alik.” A⊕B I H I H I H I H ¨ Osszef´erhetetlen vagy: ”Iszik vagy vezet!” A||B I H I H I H I I
21.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
Logikai jelek
Az implik´aci´o (A ⇒ B) csak logikai ¨ osszef¨ ugg´est jelent ´es nem okozatit! A⇒B I H
I I I
H H I
P´elda 2 · 2 = 4 ⇒ i 2 = −1 2 · 2 = 4 ⇒ kedd van Hamis ´all´ıt´asb´ol minden k¨ ovetkezik: P´elda 2 · 2 = 5 ⇒ i 2 = −2 Adott logikai jel, m´as m´ odon is kifejezhet˝ o: (A ⇒ B) ⇔ (¬A ∨ B)
22.
Diszkr´ et matematika 1. k¨ oz´ epszint
2017. ˝ osz
A logikai m˝uveletek tulajdons´agai, ´ıt´eletlogikai t´etelek
´ ıt´as All´ 1
2 3
4 5 6 7 8
(A ∨ (B ∨ C )) ⇔ ((A ∨ B) ∨ C ), (A ∧ (B ∧ C )) ⇔ ((A ∧ B) ∧ C ) (asszociativit´as); (A ∨ B) ⇔ (B ∨ A), (A ∧ B) ⇔ (B ∧ A) (kommutativit´as); (A∧(B ∨C )) ⇔ ((A∧B)∨(A∧C )), (A∨(B ∧C )) ⇔ ((A∨B)∧(A∨C )) (disztributivit´as); (¬(A ∨ B)) ⇔ (¬A ∧ ¬B), (¬(A ∧ B)) ⇔ (¬A ∨ ¬B) (De Morgan); (A ⇒ B) ⇔ (¬B ⇒ ¬A) (a kontrapoz´ıci´ o t´etele); ((A ⇒ B) ∧ A) ⇒ B; ((A ⇒ B) ∧ (B ⇒ C )) ⇒ (A ⇒ C ) (szillogizmus); ((A ⇒ B) ∧ (B ⇒ A)) ⇔ (A ⇔ B).
23.
