Diszkr´ et matematika I. k¨ oz´ epszint
Diszkr´et matematika I. k¨oz´epszint 2. el˝ oad´as
M´erai L´aszl´ o di´ai alapj´an Komputeralgebra Tansz´ ek
2014. ˝ osz
2014. ˝ osz
1.
Diszkr´ et matematika I. k¨ oz´ epszint
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: ?
2014. ˝ osz
2.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ 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.
3.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ 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.
4.
Diszkr´ et matematika I. 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
2014. ˝ osz
5.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Logikai jelek A k¨oznyelvben a vagy h´aromf´ele ´ertelemmel b´ırhat: ´ re´a ki gy´avas´agb´ ol vagy lomhas´agb´ol Megenged˝o vagy ,,Atok 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
6.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ 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)
7.
Diszkr´ et matematika I. k¨ oz´ epszint
Kvantorok
Kvantorok ∃ egzisztenci´alis kvantor: ,,l´etezik”, ,,van olyan”. ∀ univerz´alis kvantor: ,,minden”. P´elda V (x): x ver´eb. M(x): x mad´ar. Minden ver´eb mad´ar. ∀x(V (x) ⇒ M(x)). Van olyan mad´ar, ami ver´eb. ∃x(M(x) ∧ V (x)). Minden ver´eb mad´ar, de nem minden mad´ar ver´eb. (∀x(V (x) ⇒ M(x))) ∧ (∃x(M(x) ∧ ¬V (x))).
2014. ˝ osz
8.
Diszkr´ et matematika I. k¨ oz´ epszint
Formul´ak
A formul´ak predik´atumokb´ ol ´es logikai jelekb˝ ol alkotott ,,mondatok”.
Defin´ıci´o(Formul´ak) A predik´atumok a legegyszer˝ ubb, u ´n. elemi formul´ak. Ha A, B k´et formula, akkor ¬A,(A ∧ B) ,(A ∨ B), (A ⇒ B), (A ⇔ B) is formul´ak. Ha A egy formula ´es x egy v´altoz´ o, akkor (∃xA) ´es (∀xA) is formul´ak. P´elda Minden ver´eb mad´ar, de nem minden mad´ar ver´eb. (∀x(V (x) ⇒ M(x))) ∧ (∃x(M(x) ∧ ¬V (x))). Ez egy formula. Ha nem okoz f´elre´ert´est, a z´ar´ ojelek elhagyhat´ oak.
2014. ˝ osz
9.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Z´art/ nyitott formul´ak
Defin´ıci´o Ha A egy formula ´es x egy v´altoz´ o, akkor (∃xA) ´es (∀xA) formul´akban az x v´altoz´o minden el˝ofordul´asa az A formul´aban a kvantor hat´ask¨or´eben van. Ha egy formul´aban a v´altoz´ o adott el˝ ofordul´asa egy kvantor hat´ask¨or´eben ot¨ ott, egy´ebk´ent szabad. van, akkor az el˝ofordul´as k¨ Ha egy formul´aban a v´altoz´ onak van szabad el˝ ofordul´asa, akkor a v´altoz´o szabad v´altoz´o, egy´ebk´ent k¨ ot¨ ott v´altoz´ o. Ha egy formul´anak van szabad v´altoz´ oja, akkor nyitott formula, egy´ebk´ent z´art formula. P´elda Gy (x, y ): x gyereke y -nak. ∃y Gy (x, y ): x-nek l´etezik sz¨ ul˝ oje.
10.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Z´art/nyitott formul´ak P´elda E (x): x egy egyenes. P(x): x egy pont. I (x, y ): x illeszkedik y -ra. E (x), P(x), I (x, y ) (elemi) nyitott formul´ak. A(x, y ) legyen E (x) ∧ P(y ) ∧ I (x, y )! Az x egyenes illeszkedik az y pontra. B(x, y ) legyen P(x) ∧ P(y ) ∧ ¬(x = y )! Az x ´es y pontok k¨ ul¨onb¨oz˝oek. C(x) legyen ∃y (E (x) ∧ P(y ) ∧ I (x, y ))! Van olyan y pont, ami illeszkedik az x egyenesre. Itt x szabad y k¨ot¨ott v´altoz´ o. D() legyen ∀x (E (x) ⇒ ∃y (E (x) ∧ P(y ) ∧ I (x, y ))) Minden x egyenes eset´en, van olyan y pont, ami illeszkedik az x egyenesre. Itt x, y k¨ot¨ott v´altoz´o.
11.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Halmazok Halmazelm´eletben az alapvet˝ o fogalmak predik´atumok, nem defini´aljuk o˝ket: A halmaz (rendszer, oszt´aly, ¨ osszess´eg,...) elemeinek gondolati burka. x ∈ A, ha az x eleme az A halmaznak. A halmazok alapvet˝o tulajdons´agai axi´ om´ak, nem bizony´ıtjuk ˝oket. P´elda:
Meghat´arozotts´agi axi´oma Egy halmazt az elemei egy´ertelm˝ uen meghat´aroznak. K´et halmaz pontosan akkor egyenl˝ o, ha ugyanazok az elemeik. Egy halmaznak egy elem csak egyszer lehet eleme.
12.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Halmazok R´eszhalmazok
Defin´ıci´o Az A halmaz r´eszhalmaza a B halmaznak: A ⊂ B, ha ∀x(x ∈ A ⇒ x ∈ B). Ha A ⊂ B-nek, de A 6= B, akkor A val´ odi r´eszhalmaza B-nek: A ( B. A r´eszhalmazok tulajdons´agai:
´ ıt´as (Biz. HF) All´ 1 2 3
∀A A ⊂ A (reflexivit´as). ∀A, B, C (A ⊂ B ∧ B ⊂ C ) ⇒ A ⊂ C (tranzitivit´as). ∀A, B (A ⊂ B ∧ B ⊂ A) ⇒ A = B (antiszimmetria).
Halmazok egyenl˝os´ege egy tov´abbi tulajdons´agot is teljes´ıt: 3’. ∀A, B A = B ⇒ B = A (szimmetria).
13.
Diszkr´ et matematika I. k¨ oz´ epszint
Halmazok
Defin´ıci´o A halmaz ´es F(x) formula eset´en {x ∈ A : F(x)} = {x ∈ A|F(x)} halmaz elemei pontosan azon elemei A-nak, melyre F(x) igaz. P´elda {z ∈ C : Im z = 0}: val´ os sz´amok halmaza. n {z ∈ C : ∃n ∈ N z = 1}: komplex egys´eggy¨ ok¨ ok halmaza.
2014. ˝ osz
14.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Halmazok
Speci´alis halmazok ¨ Ures halmaz Annak a halmaznak, melynek nincs eleme a jele: ∅. A meghat´arozotts´agi axi´oma alapj´an ez egy´ertelm˝ u. ∀A A halmaz ⇒ ∅ ⊂ A Halmaz megad´ asa elemei felsorol´ as´ aval. Annak a halmaznak, melynek csak az a elem az eleme a jel¨ ol´ese: {a}. Annak a halmaznak, melynek az a ´es b az eleme a jel¨ ol´ese: {a, b},. . . Speci´alisan ∅ = {}, illetve, ha a = b, akkor {a} = {a, b} = {b}.
15.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
M˝uveletek halmazokkal Defin´ıci´o Az A ´es B halmazok uni´ oja: A ∪ B az a halmaz, mely pontosan az A ´es a B elemeit tartalmazza. ´ aban: Legyen A egy olyan halmaz, melynek az elemei is halmazok Altal´ (halmazrendszer). Ekkor ∪A = ∪{A : A ∈ A} = ∪A∈A A az a halmaz, mely az A ¨osszes elem´enek elem´et tartalmazza. Speci´alisan: A ∪ B = ∪{A, B}. P´elda {a, b, c} ∪ {b, c, d} = {a, b, c, d} {n : n ≡ 0 mod 2} ∪ {n : n ≡ 1 mod 2} = Z R¨ ovidebben, ha a = {n : n ≡ a mod m}, akkor m = 2 eset´en 0 ∪ 1 = Z ´ aban Altal´ ∪{a : a ∈ {0, 1, . . . , m − 1}} = ∪m−1 a=0 a = Z
16.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
M˝uveletek halmazokkal Az uni´o tulajdons´agai
´ ıt´as All´ 1 2 3 4 5
A∪∅=A A ∪ B = B ∪ A (kommutativit´as) A ∪ (B ∪ C ) = (A ∪ B) ∪ C (asszociativit´as) A ∪ A = A (idempotencia) A⊂B ⇔A∪B =B
Bizony´ıt´as 1. Egy x pontosan akkor eleme mindk´et oldalnak, ha x ∈ A 2. Egy x pontosan akkor eleme mindk´et oldalnak, ha x ∈ A vagy x ∈B 3-as, 4-es hasonl´o 5. ⇒: A ⊂ B ⇒ A ∪ B ⊂ B, de A ∪ B ⊃ B mindig teljes¨ ul, ´ıgy A ∪ B = B. ⇐: Ha A ∪ B = B, akkor A minden eleme eleme B-nek.
17.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
M˝uveletek halmazokkal Defin´ıci´o Az A ´es B halmazok metszete: A ∩ B az a halmaz, mely pontosan az A ´es a B k¨oz¨os elemeit tartalmazza: A ∩ B = {x ∈ A : x ∈ B}. ´ aban: Legyen A egy olyan halmaz, melynek az elemei is halmazok Altal´ (halmazrendszer)! Ekkor ∩A = ∩{A : A ∈ A} = ∩A∈A A a k¨ovetkez˝o halmaz ∩A = {x : ∀A ∈ A x ∈ A} Speci´alisan: A ∩ B = ∩{A, B}. P´elda {a, b, c} ∩ {b, c, d} = {b, c}. Ha En = {z ∈ C : z n = 1} az n-edik egys´eggy¨ ok¨ ok halmaza, akkor E 2 ∩ E 4 = E2 E 6 ∩ E 8 = E2 En ∩ Em = E(n,m) ∩∞ n=1 En = E1 = {1}
18.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
M˝uveletek halmazokkal
Defin´ıci´o Ha A ∩ B = ∅, akkor A ´es B diszjunktak. Ha A egy halmazrendszer ´es ∩A = ∅, akkor A diszjunkt, illetve A elemei diszjunktak. Ha A egy halmazrendszer ´es A b´armely k´et eleme diszjunkt, akkor A elemei p´aronk´ent diszjunktak. P´elda Az {1, 2} ´es {3, 4} halmazok diszjunktak. Az {1, 2}, {2, 3} ´es {1, 3} halmazok diszjunktak, de nem p´aronk´ent diszjunktak. Az {1, 2}, {3, 4} ´es {5, 6} halmazok p´aronk´ent diszjunktak.
19.
Diszkr´ et matematika I. k¨ oz´ epszint
M˝uveletek halmazokkal
A metszet tulajdons´agai
´ ıt´as (Biz. HF) All´ 1 2 3 4 5
A∩∅=∅ A ∩ B = B ∩ A (kommutativit´as) A ∩ (B ∩ C ) = (A ∩ B) ∩ C (asszociativit´as) A ∩ A = A (idempotencia) A⊂B ⇔A∩B =A
2014. ˝ osz
20.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
M˝uveletek halmazokkal
Az uni´o ´es metszet disztributivit´asi tulajdons´agai
´ ıt´as All´ 1 2
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
Bizony´ıt´as 1
2
x ∈ A ∩ (B ∪ C ) ⇔ x ∈ A ∧ x ∈ B ∪ C . ´Igy x pontosan akkor eleme a bal oldalnak, ha x ∈ A ∧ x ∈ B vagy x ∈ A ∧ x ∈ C azaz x ∈ (A ∩ B) ∪ (A ∩ C ). HF. hasonl´o
21.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
K¨ul¨onbs´eg, komplementer
Defin´ıci´o Az A ´es B halmazok k¨ ul¨ onbs´ege az A \ B = {x ∈ A : x 6∈ B}.
Defin´ıci´o Egy r¨ogz´ıtett X alaphalmaz ´es A ⊂ X r´eszhalmaz eset´en az A halmaz komplementere az A = A0 = X \ A.
22.
Diszkr´ et matematika I. k¨ oz´ epszint
Komplementer tulajdons´agai
´ ıt´as (Biz. HF) All´ A = A; 2 ∅ = X; 3 X = ∅; 4 A ∩ A = ∅; 5 A ∪ A = X; 6 A ⊂ B ⇔ B ⊂ A; 7 A ∩ B = A ∪ B; 8 A ∪ B = A ∩ B; A 7. ´es 8. ¨osszef¨ ugg´esek az u ´n. de Morgan szab´alyok. 1
2014. ˝ osz
23.
Diszkr´ et matematika I. k¨ oz´ epszint
Szimmetrikus differencia
Defin´ıci´o Az A ´es B halmazok szimmetrikus differenci´aja az A 4 B = (A \ B) ∪ (B \ A).
´ ıt´as (Biz. HF) All´ A 4 B = (A ∪ B) \ (A ∩ B).
2014. ˝ osz
24.
Diszkr´ et matematika I. k¨ oz´ epszint
2014. ˝ osz
Hatv´anyhalmaz
Defin´ıci´o Ha A egy halmaz, akkor azt a halmazrendszert, melynek elemei az A halmaz ¨osszes r´eszhalmaza, az A hatv´anyhalmaz´anak mondjuk ´es 2A -val jel¨olj¨ uk. A = ∅, 2∅ = {∅} A = {a}, 2{a} = {∅, {a}} A = {a, b}, 2{a,b} = {∅, {a}, {b}, {a, b}}
´ ıt´as (Biz. HF) All´ |2A | = 2|A|
25.
