Matematika I. Mőszaki informatikai mérnm. Galambos GáborG JGYPK 2011

Matematika I. Mőszaki informatikai mérnökasszisztens http://jgypk.u-szeged.hu/tanszek/szamtech/oktatas/Matematika-1.pdf

Galambos Gábor JGYPK 2011-2012 Matematika I.

Felsıfokú Szakképzés

1

A Matematika I. fıbb témái: Halmazok: Alapfogalmak, mőveletek halmazokkal, számhalmazok, végtelen halmazok. Relációk: Alapfogalmak, relációk tulajdonságai (reflexív, szimmetrikus, tranzitív, ekvivalencia reláció, trichotómia, rendezés, jólrendezés). Függvények: Alapfogalmak, függvények ábrázolása, mőveletek függvényekkel, speciális függvények (pl. rekurzív függvények). Matematikai logika: Alapfogalmak, logikai mőveletek, logikai függvények, következtetések és szabályaik. Lineáris algebra alapjai: Lineáris egyenletrendszerek, mátrixok, determinánsok, lineáris egyenletrendszerek numerikus megoldásai. Kombinatórika: Alapfogalmak, permutáció és tulajdonságai, kombinációk, binomiális együtthatók, variációk. Gráfelmélet: Alapfogalmak, gráfok ábrázolása, klasszikus gráfbejárások, párosítások, magyar módszer, fagráfok. Matematika I.


2

A Matematika II. fıbb témái: Valószínőségszámítás Intervallum, távolság, környezet Valós függvények Számsorozatok és sorok Függvények határértéke, folytonosság Differenciálszámítás Differenciálható függvények vizsgálata Integrálszámítás

Matematika I.


3

Az elıadás Bánhegyesiné Topor Gizella, Bánhegyesi Zoltán: Matematika , nem matematika szakosoknak.OKJ informatika sorozat. Mőszaki Kiadó, Budapest, 2002. ISBN 963-16-2266-5. (Megrendelhetı: www.muszakikiado.hu.) Csernyák László: Analízis, Matematika közgazdászoknak sorozat. Nemzeti Tankönyvkiadó, Budapest, 2005, ISBN 963 19 3510 8. alapján lett összeállítva. (Keress rá a Google-n: „Csernyák László”)

Matematika I.


4

A közös tulajdonságok alapján csoportba foglalható tárgyakat, fogalmakat halmazoknak nevezzük. Pl. bélyeggyőjtemény, embercsoportok, számok, függvények. A halmazhoz tartozó egyedeket a halmaz elemeinek nevezzük. Melyek az elemek legfontosabb tulajdonságai? Egyértelmően eldönthetı, hogy az elem hozzátartozik-e a halmazhoz. A halmaz minden eleme a többi elemtıl megkülönböztethetı. Egy halmazban egy elem csak egyszer fordul elı. Egy halmaz nem lehet önmagának az eleme. Georg Cantor (1845-1918) alapozta meg a halmazelmélet fogalmát. Matematika I.


5

Azt, hogy egy h dolog eleme a H halmaznak a h ∊ H jelöléssel írjuk le. Ha h nem eleme a H halmaznak, akkor a h ∉ H jelölést alkalmazzuk. Pl. Ha ℕ-nel jelöljük a természetes számok halmazát, akkor 5 ∊ ℕ és -13 ∉ ℕ. Bármely halmazt egyértelmően meghatározzák az elemei: ha H egy halmaz, akkor bármely x dologra vagy x ∊ H vagy x ∉ H áll fenn. Két halmazt akkor tekintünk azonosnak, ha elemei ugyanazok, azaz a H és K halmaz akkor egyenlı, ha h ∊ H esetén h ∊ K is teljesül, és ha h ∉ H akkor h ∉ K is igaz. Jelölése: H = K. Matematika I.


6

Egy halmazt megadhatunk elemeinek felsorolásával vagy egy olyan tulajdonsággal, amely a halmaz elemeit egyértelmően meghatározza. Pl. A 3-mal osztható természetes számok halmaza így írható le: H = {0, 3, 6, 9, …} vagy H = {x | x ∊ ℕ és x osztható 3-mal}. Halmazok ábrázolása: Venn-diagram

Matematika I.


7

Azt a halmazt, amelynek egyetlen eleme sincs, üres halmaznak nevezzük, és ∅ -val vagy { }-val jelöljük. Pl. Tekintsük a következı halmazt: A = {azon valós x számok, amelyekre sin x + cos x = 2 igaz} Mivel sin x és cos x mindig csak -1 és +1 közé esı értékeket vehet fel, ezért az egyenlet csak akkor lehet igaz, ha sin x = 1 és cos x = 1 egyszerre teljesül. π A sin x = 1 megoldása: x = + 2kπ , ahol k ∈ Z . 2 A cos x = 1 megoldása:

x = 2kπ , ahol k ∈ Z .

Ezért nincs olyan x valós szám, amely egyenletünknek megoldása lenne. Ezért A = ∅. Matematika I.


8

Változtassuk meg az A halmaz definícióját: B = {azon valós számok halmaza, amelyekre sin x + cos x = 2 igaz} Van különbség a két definíció között? Az A halmaz üres halmaz, a B halmaz nem üres halmaz, mert egyetlen elemet tartalmaz, ti. az A üres halmazt. Könnyő belátni, hogy csak egy üres halmaz van. (Használni kell a két halmaz azonosságára vonatkozó definíciót.)

Matematika I.


9

Induljunk ki az autók halmazából. Keressünk olyan tulajdonságokat, amelyek alapján tovább bonthatjuk az autók halmazát! Mondjunk további halmazokat, és bontsuk ezeket részekre! Venn diagrammal:

Autók

Személyautók

Matematika I.


10

Egy K halmazt a H halmaz részhalmazának nevezünk, ha a K halmaz minden eleme egyben H-nak is eleme. Jelölése: K ⊆ H. A definícióból következik, hogy minden halmaz része saját magának, hiszen minden x ∊ H -ból következik, hogy x ∊ H, tehát a H ⊆ H tartalmazás mindig igaz. Az üres halmaz minden halmaznak részhalmaza. Egy K halmazt a H halmaz valódi részhalmazának nevezünk, ha a K részhalmaza H-nak és H-nak van legalább egy eleme, amely nem eleme K-nak. Jelölése: K ⊂ H. Tétel: K ⊂ H akkor és csak akkor igaz, ha K ⊆ H, de H ⊈ K . Tétel: Ha K ⊆ H és H ⊆ K , akkor H = K. Matematika I.


11

Tekintsünk egy A halmazt, amely részhalmaza H-nak. Azt a halmazt, amely a H valamennyi A-hoz nem tartozó elemét tartalmazza, az A halmaz H-ra vonatkoztatott komplementer (kiegészítı) halmazának nevezzük. Jelölése: A’ = {x | x ∊ H és x ∉ A } H A’ A

Matematika I.


12

Néhány egyszerő megállapítás: Egy halmaz önmagára vonatkoztatott komplementere az üres halmaz. Az üres halmaz komplementere maga a halmaz. Egy halmaz bármely másik halmazra vonatkoztatott komplementerének a komplementere maga a halmaz. Ha két halmaznak ugyanarra a halmazra vonatkoztatott komplementere egyenlı, akkor a két halmaz is egyenlı egymással. (Ez megfordítva is igaz.)

Matematika I.


13

Mőveletek halmazokkal Az A és B halmazoknak az A × B szimbólummal jelölt Descartes-féle szorzatán az összes olyan rendezett (a,b) párokból álló halmazt értjük, amelyekre a ∊ A és b ∊ B. Jelölése: A × B = { (a,b) | a ∊ A és b ∊ B }. Ha A = B, akkor az A × A helyett az A2 jelölést is használjuk. Pl. Legyen A = {1, 2, 3} és B = {e, f} e

A×B=

f

1 (1, e) (1, f ) 2 (2, e) (2, f ) 3 (3, e) (3, f )

Matematika I.


14

A táblázat felfogható egy speciális szorzótáblának. A szorzathalmaz elemeinek a számát a két halmaz elemeinek szorzata adja. Tétel: A Descartes-szorzás mővelete nem kommutatív. (Nem felcserélhetı). A szorzathalmaz kettınél több halmaz szorzatára is értelmezett, ekkor rendezett hármasok, négyesek, stb. lesznek a szorzathalmaz elemei. A szorzathalmaz lehetıvé teszi matematikai alakzatok konstrukcióját is:

Matematika I.


15

ℕ

ℕ

Matematika I.


16

A mőveletekrıl általában Egy H halmazon értelmezett (belsı, kétváltozós) mővelet nem más, mint a H × H szorzathalmaz leképezése önmagába a H halmazba, azaz minden (x,y) ∊ H × H rendezett párhoz H egy elemét rendeljük hozzá. Matematika jelöléssel: φ: (x,y) ∊ H × H → z = f(x,y) ∊ H Három alapvetı mőveleti tulajdonságot fogunk definiálni: Asszociativitás (csoportosíthatóság) Kommutativitás (felcserélhetıség) Disztributivitás (széttagolhatóság) Matematika I.


17

Asszociativitás Egy H halmazon értelmezett • mőveletet akkor mondunk asszociatívnak, ha bármely x, y, z ∊ H elemre fennáll, hogy (x • y) • z = x • (y • z) = x • y • z. Ha egy mővelet asszociatív, akkor a zárójelet bárhova lehet rakni, de az elemek sorrendje lényeges. • Asszociatív mővelet a valós számok halmazán értelmezett összeadás és szorzás. • Nem asszociatív mővelet a hatványozás, hiszen

(2 )

3 2

≠ 2 (3 ) 2

A bal oldal eredménye 82 = 64, a jobb oldalé 29 = 512.

Matematika I.


18

Kommutativitás Egy H halmazon értelmezett • mőveletet akkor mondunk kommutatívnak, ha bármely x, y ∊ H elemre fennáll, hogy x • y = y • x. Ha egy mővelet kommutatív, akkor a mővelet eredménye független a mőveletben résztvevı elemek sorrendjétıl • Kommutatív mővelet a valós számok halmazán értelmezett összeadás és szorzás, vagy az egybevágósági transzformációk egymás utáni végrehajtása. • Nem kommutatív mővelet a kivonás, hiszen 5 – 3 ≠ 3 – 5.

Matematika I.


19

Disztributivitás Legyen adott a H halmazon értelmezett két mővelet • és ⎕. A • mőveletet balról disztributív a ⎕ mőveletre nézve, ha bármely x, y z ∊ H elemre fennáll, x • (y ⎕ z) = (x • y) ⎕ (x • z) . Legyen adott a H halmazon értelmezett két mővelet • és ⎕. A • mőveletet jobbról disztributív a ⎕ mőveletre nézve, ha bármely x, y z ∊ H elemre fennáll, (x ⎕ y) • z = (x • z) ⎕ (x • y) . Ha egy mővelet balról is és jobbról is disztributív egy másik mőveletre nézve, akkor egyszerően disztributivitásról beszélünk. A valós számok körében definiált szorzás mővelete disztributív az ugyanitt definiált összeadás mőveletére nézve. Matematika I.


20

Zártság A H halmaznak egy K részhalmazát a ⎕ mőveletre nézve zártnak mondunk, bármely x, y ∊ K elemekre igaz, hogy x ⎕ y ∊ K. Pl. a pozitív páratlan számok halmaza az összeadásra nézve nem zárt, de a szorzásra nézve zárt.

Matematika I.


21

Halmazok uniója Az A és B halmazok unióján (egyesítésén) azt a halmazt értjük, amely azokat és csak azokat az elemeket tartalmazza, amelyek A és B közül legalább az egyiknek elemei. Jelölése: A ∪ B. Az A és B halmazokat az unió tagjainak nevezzük. A

B

A halmazok egyesítés három vagy több tagra is definiálható: Az A1, A2,…, An, halmazok unióján (egyesítésén) azt a halmazt értjük, amely azokat és csak azokat az elemeket tartalmazza, amelyek Ai (i=1,2,…, n) halmazok közül legalább az egyiknek elemei. Jelölése: A1 ∪ A2 ∪ … ∪ An. Matematika I.


22

Az unióképzés mőveletének legfontosabb tulajdonságai: Az unióképzés mővelete kommutatív. Az unióképzés mővelete asszociatív. Az unióképzés mővelete idempotens: A ∪ A = A. A ∪ ∅ = A. A ∪ B = B akkor és csak akkor, ha A ⊆ B. A ∪ B = ∅ akkor és csak akkor, ha A = ∅ és B = ∅. Legyen A egy halmaz, és legyen A ⊆ B. Ha A' az A halmaz B-re vonatkoztatott komplementer halmaza, akkor A ∪ A' = B.

Matematika I.


23

Halmazok metszete Az A és B halmazok metszetén (közös részén) azt a halmazt értjük, amely azokat és csak azokat az elemeket tartalmazza, amelyek mind az A mind a B halmaznak elemei. Jelölése: A ∩ B. Az A és B halmazokat az metszet tagjainak nevezzük. Pl. Legyen K = {12 osztói}, és L = {20 osztói}. Ekkor K = {1, 2, 3, 4, 6, 12} és H = {1, 2, 4, 5, 10, 20}. Így A ∩ B ={1, 2, 4}. A metszethalmaz éppen a 12 és 20 közös osztóinak halmaza. A halmazok metszete három vagy több tagra is definiálható: Az A1, A2,…, An, halmazok metszetén azt a halmazt értjük, amely azokat és csak azokat az elemeket tartalmazza, amelyek Ai (i=1,2,…, n) halmazok mindegyikének eleme. Jelölése: A1 ∩ A2 ∩ … ∩ An.

Matematika I.


24

Az metszetképzés mőveletének legfontosabb tulajdonságai: Az metszetképzés mővelete kommutatív. Az metszetképzés mővelete asszociatív. Az metszetképzés mővelete idempotens: A ∩ A = A. A ∩ ∅ = ∅. A ∩ B = A akkor és csak akkor, ha A ⊆ B. Legyen A egy halmaz, és legyen A ⊆ B. Ha A' az A halmaz B-re vonatkoztatott komplementer halmaza, akkor A ∩ A' = ∅. Az unió a metszetképzésre nézve disztributív. A metszet az unióképzése nézve disztributív.

Matematika I.


25

Szemléltessük, hogy unió a metszetképésre nézve disztributív! A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C) A ∪ (B ∩ C ) A

(A ∪ B) ∩ (A ∪ C) B

C

Matematika I.

B

A

C Felsıfokú Szakképzés

26

Halmazok különbsége Az A és B halmazok különbségén az A halmaznak azt a részét értjük, amelyek nem tartoznak a B halmazhoz. Jelölése: A \ B . A különbségképzés mőveletének legfontosabb tulajdonságai: Az A \ B különbséghalmaz mindig részhalmaza A-nak. Amennyiben egy A halmazból kivonjuk annak egy B részhalmazát, akkor a B halmaznak A-ra vonatkozó komplementerét kapjuk: A \ B = B' . A B \ A különbséghalmazt az A \ B szimmetrikus párjának nevezzük. A B \ A és az A \ B halmazoknak nincs közös eleme (diszjunktak). A \ ∅ = A és ∅ \ A = ∅ és A \ A = ∅. A különbségképzés mővelete nem kommutatív. A különbségképzés mővelete nem asszociatív. Matematika I.


27

Szimmetrikus differencia Az A és B halmazok szimmetrikus differenciáján az A ∆ B = {A \ B} ∪ {B \ A} halmazt értjük, A

B

A∆B A definícióból a következı tulajdonságok következnek: A∆A=∅ A∆B=B∆A A ∆ ∅ = ∅ ∆ A = A. ( A ∆ B ) ∆ C = A ∆ ( B ∆ C ) ( a mővelet asszociatív). Matematika I.


28

Venn diagramm segítségével ábrázoljuk a ( A ∆ B ) ∆ C halmazmőveletet!

A

B

C

Matematika I.


29

Számhalmazok Természetes számok A természetes számok halmazát a Peano axiómákkal (1889) írhatjuk le. Giuseppe Peano (1858 – 1932). Kurt Gödel: Minden axiómarendszerben léteznek olyan állítások, amelyek nem eldönthetık, azaz amelyeknek bizonyítása és cáfolata az adott rendszeren belül nem végezhetı el.

Matematika I.


30

A Peano axiómák: 1. A 0 természetes szám, azaz 0 ∊ ℕ. 2. Bármely n természetes számnak létezik egy és csak egy – az n számtól különbözı – n' rákövetkezıje, amelyik szintén természetes szám. 3. Nincs olyan természetes szám, amelynek a 0 a rákövetkezıje. 4. Különbözı természetes számoknak különbözı a rákövetkezıje. 5. Ha egy K halmaz az ℕ részhalmaza, továbbá K rendelkezik az 1es axióma szerinti tulajdonsággal, és minden K-beli elem rákövetkezıje is a K halmazban van, akkor K = ℕ.

Matematika I.


31

A Peano axiómák (formalizáltan): 1. 0 ∊ ℕ. 2. Ha n ∊ ℕ, akkor n' ∊ ℕ. 3. Ha n' = 0, akkor n ∉ ℕ. 4. Ha m, n ∊ ℕ, és m ≠ n, akkor n' ≠ m' . 5. Ha egy K halmazra igaz, hogy (i) K ⊆ ℕ, (ii) 0 ∊ K, (iii) ha n ∊ K, akkor n' ∊ K, akkor K = ℕ.

Matematika I.


32

Az 5-ös axiómát szokás a teljes indukció axiómájának nevezni. Legyen α(n) minden n ∊ ℕ-re értelmezett állítás, és tegyük fel, hogy teljesül a következı két feltétel: az α(1) állítás igaz, ha valamely n ∊ ℕ esetén α(n) igaz, akkor α(n+1) is igaz, Ekkor α(n) minden n ∊ ℕ esetén igaz. A teljes indukció axiómájának változata: Legyen k ∊ ℕ, és α(n) minden k ≤ n ∊ ℕ-re értelmezett állítás, és tegyük fel, hogy teljesül a következı két feltétel: az α(k) állítás igaz, ha valamely n ∊ ℕ esetén α(n) igaz, akkor α(n+1) is igaz, Ekkor α(n) minden k ≤ n ∊ ℕ esetén igaz. Matematika I.


33

Nézzünk egy teljes indukciós bizonyítást: Bizonyítsuk be, hogy az elsı n természetes szám összege n ( n + 1) S (n ) = . 2 Biz. 1. A tétel állítása n = 1-re igaz, hiszen S(1) = 1. 2. Tegyük fel, hogy az állítást valamely n ≥ 1-re már beláttuk. Ekkor n ( n + 1) n ( n + 1) + 2 ( n + 1) S ( n + 1) = S ( n ) + ( n + 1) = + ( n + 1) = = 2 2 ( n + 1)( n + 2 ) = . 2 Ezért a tétel állítása igaz. Matematika I.


34

ℕ-ben két mővelet definiálható: az összeadás, és a szorzás. mindkét mőveletre bebizonyítható, hogy asszociatív és kommutatív, és belátható, hogy a z összeadás a szorzásra nézve disztributív mővelet. Esetleg beszélni az egységelemrıl és a zérus elemrıl.

Matematika I.


35

Egész számok Próbáljuk meg kiterjeszteni a természetes számok halmazát, és az azon értelmezett összeadás és szorzás mőveletét. A halmaz kiterjesztésénél tartsuk be a következı elveket: • Az új halmaznak a természetes számok halmaza legyen részhalmaza. • Az új halmaz elemein legyen elvégezhetı a kivonás mővelete. • Az összeadás és a szorzás mőveletét úgy kell értelmezni az új halmazon, hogy ha a mőveleteket ℕ-beli elemekre alkalmazzuk, akkor ugyanazt az eredményt kell kapnunk, mint korábban. • Érvényesüljön a permanencia elve, azaz mőveletekre minél több azonosság maradjon érvényben.

Matematika I.


36

Az n természetes szám ellentettjének nevezzük, és –n-nel jelöljük az n + x = 0 egyenlet megoldását. Tehát –n-et az n +(–n) = (–n) + n = 0 összefüggés értelmezi. A pozitív természetes számok ellentettjei a természetes számokkal együtt alkotják az egész számok halmazát. Az egész számok halmazának jele: ℤ. A permanencia elvének megfelelıen az összeadás az egész számok halmazán a következıképpen értelmezhetı: Tetszıleges n, m ∊ ℕ-re, (–n) +(–m) = – (n + m). ha n > m  n − m,  n + (− m) = (− m) + n =  0, ha n = m − (n − m), ha n < m.  Matematika I.


37

Racionális számok Legyen p, q ∊ ℕ és q ≠ 0. Keressük qx = p egyenlet megoldását az egész számok halmazán. Ha a megoldás nem egész, akkor a p-nek qval való osztását jelöljük p/q-val, és ezt egy új számnak tekintjük. A p/q alakú számokat, ahol q ≠ 0, racionális (tört)számoknak nevezzük, ahol p a törtszám számlálója és q a törtszám nevezıje. A racionális számok jelölése: ℚ. Az egész számok olyan törtszámok, amelyeknek nevezıje 1. A racionális számok halmazán a racionális mőveletek – összeadás, kivonás, szorzás, osztás – elvégezhetık. (Ez azt jelenti, hogy e mőveletek eredménye nem vezet ki a racionális számok halmazából.) Matematika I.


38

Amennyiben azt akarjuk, hogy a

p alakú számok ugyanúgy visel1

kedjenek, mint az egész számok továbbá az eddigi mőveletek tulajdonságai (asszociativitás, kommutativitás, disztributivitás) érvényben maradjanak, az összeadást és a szorzást a következıképpen kell definiálni:

a c ad + bc + = b d bd

a c ac ⋅ = b d bd

Matematika I.


39

Bizonyítsuk be, hogy a 3,2121212… végtelen szakaszos tizedes tört egy racionális szám tizedes tört alakja!

3,212121... = 3 +

21 21 21 1 1  1  + + + L = 3 + 21 + + + L  2 = 2 4 6 4 6 10 10 10  10 10 10 

1 1 21 100 21 318 = 3 + 21 ⋅ 2 ⋅ = 3+ ⋅ = 3+ = 10 1 − 1 100 99 99 99 10 2

Keressünk általános megoldást egy végtelen szakaszos tizedes tört racionális törtszámmá alakítására! Matematika I.


40

A racionális pontok a számegyenesen ábrázolhatók. Belátható, hogy a számegyenesen bármely két racionális pont között van egy – a két számtól eltérı – újabb racionális pont.

⇩ A racionális pontok a számegyenesen egyenletesen sőrőn helyezkednek el.

Matematika I.


41

Valós számok Vannak olyan számok, amelyek nem írhatók fel két egész szám hányadosaként. Ilyen pl. a 2 . Bizonyítsuk be, hogy a

p 2 nem írható fel alakban, ahol p,q ∊ ℤ. q

Biz.

p Tfh. az állítás nem igaz. Ekkor 2 = , ahol (p,q) = 1. q 2 p Emeljük mindkét oldalt négyzetre: 2 = 2 . q Ebbıl adódik, hogy 2q2 = p2, ami lehetetlen, hiszen p és q relatív prímek. Matematika I.


42

Azokat a számokat, amelyek nem írhatók fel két egész szám hányadosaként, irracionális számoknak nevezzük. Jele: ℚ. Az irracionális számok azok a számok, amelyek végtelen – nem szakaszos – tizedes tört formájában felírhatók. A racionális pontok bár mindenütt sőrőn helyezkednek el a számegyenesen, mégsem töltik azt teljesen ki. A „lukakban” helyezkednek az irracionális számok. A racionális és az irracionális pontok teljesen kitöltik a számegyenest. A számegyenes pontjainak megfeleltethetı számok halmazát a valós számok alkotják. Jele: ℝ.

Matematika I.


43

Tétel: Az irracionális számok halmaza a racionális számok komplementer halmaza a valós számok halmazára vonatkozóan. ℚ* = ℝ ∖ ℚ.

Termé Természetes szá számok

Matematika I.

Egé Egész szá számok

Racioná Racionális szá számok


Való Valós szá számok

44

Algebrai és transzcendens számok Láttuk azt, hogy a számhalmazok között a valós számok halmaza a legtágabb halmaz, amely két diszjunkt halmazra – a racionális és az irracionális – bontható. Létezik a valós számok halmazának másféle felbontása részhalmazokra? Kis kitérı következik

Matematika I.


45

Polinomokról általában A polinom (többtagú algebrai kifejezés) egy olyan kifejezés, melyben csak számok és változók egész kitevıjő hatványainak szorzatai illetve ilyenek összegei szerepelnek. Például: p(x,y,z,u) = 5x4y6 - 3xz3+11y15u7 q(x) = 2x2 + 6x + 9 A polinomban a számokkal szorzott hatványszorzatokat monomnak (egytagoknak) nevezzük. Pl. p-nél az 5x4y6, a 3xz3 és az 11y15u7 tagok). A monomokban lévı számszorzókat a polinom együtthatóinak hívjuk.

Matematika I.


46

Mőveletek polinomokkal Az egyes monomokban a változók kitevıinek összege adja meg az adott monom fokát. A polinom fokának a benne lévı monomok fokának maximumát tekintjük. A 0 fokú monomokat konstans polinomoknak nevezzük. Egynemőnek nevezünk két monomot, ha csak együtthatóban különböznek. Polinomokat úgy adunk össze, hogy az egynemő egytagok együtthatóit összeadjuk:

p ( x , y ) = 5 x 2 y + 2 xy 2 + 6 y 3

q ( x, y, z ) = 2 x 2 y − 7 xy 2 + 8 yz 6 ( p + q )( x , y , z ) = 7 x 2 y − 5 xy 2 + 6 y 3 + 8 yz 6 Matematika I.


47

A polinomok szorzásakor „minden tagot minden taggal beszorzunk” és a keletkezı szorzatokban az azonos változók hatványait az azonos alapú hatványok szorzásának szabályával számítjuk ki. Pl.:

p ( x , y ) = x 2 + xy q ( x, z ) = 3 x 3 − 7 z 2 ( p ⋅ q )( x , y , z ) = x 2 3 x 3 + x 2 ( − 7 z 2 ) + xy 3 x 3 + xy ( − 7 z 2 ) =

= 3 x 5 − 7 x 2 z 2 + 3 x 4 y − 7 xyz 2

Matematika I.


48

Speciális polinomok A polinomok legegyszerőbb megjelenési formái az egyváltozós polinomok. Például az 8x3 – 7x2 + 36 egy harmadfokú, egyváltozós polinom. Az x fokszáma szerint csökkenı sorrendbe írva, az elsı monom foka 3, a másodiké 2, a harmadiké 0. A harmadfokú tag együtthatója 8, a másodfokúé -7, a konstans tag 36. Egy polinomot homogén fokszámúnak nevezünk, ha benne minden monom foka egyenlı. Pl. a binomiális tétel: (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 Matematika I.


49

Egy a számot algebrai számnak nevezünk, ha létezik olyan racionális együtthatós polinom, amelynek a gyöke. Ha az a számhoz ilyen polinom nem található, akkor a transzcendens szám. Ha az a számhoz található egy n-ed fokú polinom, amelynek ı gyöke, de egyetlen alacsonyabb fokú polinomnak a már nem gyöke, akkor a egy n-ed fokú algebrai szám. Tétel: az elsıfokú algebrai számok a racionális számok. Tétel: Elsınél magasabb fokú algebrai szám nem lehet racionális szám.

Matematika I.


50

Az irracionális algebrai számok megközelíthetık racionális számok sorozatával. A 2 esetében ez a sorozat: 1,

14 141 1414 14142 , , , 10 100 1000 10000

Liouville: A

1 1 1 1 a = 1 + + 1⋅2 + 1⋅2⋅3 + L + 1⋅2⋅3Ln + L q q q q végtelen sor határértéke minden q > 1 esetén transzcendens szám. A π és az e is transzcendens szám. (Errıl többet a gyakorlaton)

Matematika I.


51

Számhalmazok számossága Végtelen halmazok Természetes számból vagy a négyzeteikbıl van több? Az A és a B halmazról akkor mondjuk, hogy egyenlı számosságúak, ha van olyan kölcsönösen egyértelmő megfeleltetés az elemeik között, amely A minden eleméhez B egy meghatározott elemét rendeli hozzá, és amely B minden elemét hozzárendeli A valamely eleméhez. 0

1

2

3

4

↑↓

↑↓

↑↓

↑↓

0

1

4

9

↑↓

Matematika I.

16


n …

↑↓

…

n2 52

Azt az eredményt kaptuk, hogy a természetes számok és a négyzeteik ugyanannyian vannak, azaz ℕ és a négyzetszámok halmaza azonos számosságú. Az eredmény meglepı,hiszen azt kaptuk, hogy a „rész” ugyanannyi, mint az „egész”!

⇩ Végtelen halmazok esetében nincs értelme a „több”, a „kevesebb” vagy az „ugyannyi” kifejezéseknek. Végtelennek nevezzük azt a halmazt, amelynek van önmagával egyenlı számosságú valódi részhalmaza. Matematika I.


53

Megszámlálhatóan végtelen halmazok Megszámlálhatóan végtelen – vagy megszámlálható – halmazoknak nevezzük azokat a halmazokat, amelyeknek ugyanannyi elemük van, mint amennyi természetes szám.

⇩

Ha A megszámlálható halmaz, akkor elemei kölcsönösen megfeleltethetık a természetes számok halmazának elemeivel. Könnyő belátni, hogy a természetes számok helyett tekinthetjük a pozitív természetes számok halmazát. Miért?

⇩ A pozitív természetes számoknak való egyértelmő megfeleltetés azt jelenti, hogy a halmaz elemei sorbarendezhetık. Matematika I.


54

Ha az elemek sorbarendezhetık, akkor az A halmaz felírható végtelen sorozat formájában: a1, a2, a3, a4, …,an, … Ennek az a következménye, hogy ha egy halmaz elemei sorbarendezhetık, akkor a halmaz elemeinek számossága megegyezik a természetes számok számosságával. Egyszerő példák: A pozitív páros számok és a prímszámok halmaza megszámlálható. Tétel: Egy megszámlálható halmaz bármely végtelen részhalmaza szintén megszámlálható. Bizonyítás egyszerő. Matematika I.


55

Tétel: Megszámlálható és véges halmaz egyesítésével nyert halmaz is megszámlálható. Biz. Ha A = {a1, a2, a3, a4, …,an, …} az adott megszámlálható halmaz és b1, b2, b3, …, bk a véges halmaz elemei, akkor az új halmaz elrendezése: b1, b2, b3, …, bk, a1, a2, a3, a4, …,an, … és a hozzárendelés – eltolással – ismét megoldható. Az összes egész számok halmaza is megszámlálható. Nagyság szerint az elemek nem alkotnak sorozatot, de a sorba rendezés más módon elérhetı: 0 1 2 3 4 5 …

↑↓ 0

Matematika I.

↑↓ -1

↑↓ 1

↑↓ -2

↑↓ 2

↑↓

-3


… 56

Következmény: ℕ és ℤ azonos számosságúak: | ℕ | = | ℤ |. Általánosítás-1: két megszámlálható halmaz egyesítésével kapott halmaz is megszámlálható. Általánosítás-2: megszámlálhatóan végtelen sok megszámlálható halmaz egyesítésével kapott halmaz is megszámlálható.

⇩ A racionális számok halmaza megszámlálható. Figyelem: ez azt jelenti, hogy ugyanannyi racionális szám van, mint ahány pozitív egész szám!

Matematika I.


57

Az elıbbi állítás bizonyításához elıször belátjuk, hogy a pozitív racionális számok halmaza megszámlálható: Alkossuk meg a következı elrendezést: 1/1

2/1

3/1

4/1

1/2

2/2

3/2

4/2

1/3

2/3

3/3

4/3

1/4

2/4

3/4

4/4

Járjuk be a táblázatot átlósan! Hagyjuk ki a táblázatból az egyszerősíthetı törteket balra tolva a sort! A maradék táblázatban minden pozitív racionális szám egyszer szerepel. Matematika I.


58

Ugyanezt a rendezést elvégezhetjük a negatív racionális számokra is, és alkalmazzuk a két megszámlálható halmaz egyesítésére kimondott tételt! Ha fenti kiinduló táblázatban a p/q alakú törtek helyére (p,q) alakú rendezett párokat írunk, akkor azt kapjuk, hogy a pozitív egész számokból képezhetı rendezett párok halmaza is megszámlálható.

Matematika I.


59

Kontinuum számosságú halmazok Vizsgáljuk meg a valós számok halmazát, és bevezetıként tegyük fel, hogy ezek a számok is megszámlálhatóan végtelen halmazt alkotnak. Ekkor a (0,1) intervallumba esı valós számok halmaza – mint a valós számok halmazának végtelen részhalmaza – megszámlálható. Ezért ebbe az intervallumba esı elemek sorozatba rendezhetık. Legyen a sorozat tagjainak tizedestört kifejtése a következı: a1 = 0, a11a12 a13a14 ...

a2 = 0, a21a22 a23a24 ... a3 = 0, a31a32 a33 a34 ... ahol ank az n-edik valós szám k-adik tizedes jegyét jelöli. Matematika I.


60

Most állítsuk elı a

b = 0 , b1b 2 b3 b 4 ... számot a következıképpen: b1-et úgy választjuk, hogy a11 ≠ b2-et úgy választjuk, hogy a22 ≠ b3-et úgy választjuk, hogy a33 ≠ és így tovább…

b1. Ezért a1 ≠ b. b2. Ezért a2 ≠ b. b3. Ezért a3 ≠ b.

Olyan számot konstruáltunk tehát, amely nincs a megszámlálhatóan végtelen sok szám között. Mivel ilyen konstrukcióból végtelen sok készíthetı, ezért a (0,1) intervallum valós számainak halmaza nem megszámlálhatóan végtelen. Egy olyan halmazhoz jutottunk, amelyben az elemek száma több, mint a megszámlálhatóan végtelen számosságú halmazok elemszáma. Matematika I.


61

A végtelennek ezt a másik „fokozatát” – Cantor nyomán – kontinuumszámosságnak nevezzük. A valós számok halmaza tehát nem megszámlálható. Ez csak akkor lehet, ha az irracionális számok halmaza sem megszámlálható. Cantor: Létezik-e olyan számosság, amely a végtelen számosságnál nagyobb, de a kontinuumszámosságnál kisebb? P. Cohen (1963): A kérdés a halmazelmélet axiómáiból nem cáfolható meg, de bizonyítani sem lehet. Létezik-e a kontinuumszámosságnál nagyobb számosság?

Matematika I.


62

Egy A halmaz összes részhalmazainak halmazát az A hatványhalmazának nevezzük. Jele: P(A). Bizonyítható, hogy minden A halmazra | A | < | P(A) |. Következmény: Minden számosságnál van nagyobb számosság. A tételnek olyan következményei vannak, amelyek antinómiához vezetnek. Az antinómia olyan állítás, amelynek az igazsága is és a tétel tagadása is bizonyítható

Matematika I.


63

Relációk, függvények A mindennapi életben kapcsolatok vesznek körül bennünket: Szülı – gyermek Adós – hitelezı Eladó – vevı stb… A matematika – többek között – tanulmányozza a halmazok ill. azok elemei közötti kapcsolatokat. Ezeket relációknak nevezzük. Jelölése: a ℜ b (a relációban van b-vel).

Matematika I.


64

Pl. Legyen H = {1, 2, 3, 4, 5}. Az a ℜ b jelentse: a kisebb b-nél. Elıször ábrázoljuk a relációt egy ábrával, amelyben a pontok jelölik a számokat, és a nyilak a relációt: Ha a relációban van b-vel, akkor a-ból irányított nyíl (él) mutat b-be: 1

5

2

3

4 Mely számokat jelölik az egyes pontok? Matematika I.


65

Pl. Legyen H = {2, 3, 4, 5, 6, 7, 8, 9, 10}. Az a ℜ b jelentse: a osztója b-nek. Az ábránkon – az elızıhöz hasonlóan – ha a relációban van b-vel, akkor a-ból irányított nyíl (él) mutat b-be. Vegyük figyelembe, hogy bármely a ∊ ℕ+-ra: a | a. (Ezt egy hurok éllel jelöljük.) 10

8 4

5 2

6 3

7 9

Mely számokat jelölik az egyes pontok? Matematika I.


66

Binér (kételemő) reláció Az A és B halmazok közötti binér ℜ reláció az (a, b) (a ∊ A, b ∊ B) rendezett párok egy részhalmaza. A részhalmaznak azon (a, b) párok lesznek az elemei, amelyekre a ℜ b teljesül. Általánosan fogalmazva: a reláció két vagy több halmaz Descartesféle szorzatának egy részhalmaza. Pl. Legyen A = {1, 3, 6} és B = {0, 2, 4, 5}. Határozzuk meg az a + b < 7 reláció elemeit, ahol a ∊ A, b ∊ B. 0 2 4 5 1 (1, 0) (1, 2) (1, 4) (1, 5) 3 (3, 0) (3, 2) (3, 4) (3, 5) 6 (6, 0) (6, 2) (6, 4) (6, 5) Matematika I.


67

Egy relációt meghatározhatunk Az alaphalmaz és valamely tulajdonság megadásával A relációhoz tartozó rendezett párok felsorolásával Gráffal Táblázattal A matematika gyakran csak egy halmaz elemei közötti relációkkal foglalkozik. Ilyenkor az A × A szorzathalmaz részhalmazait kell megadni.

Matematika I.


68

Binér relációk tulajdonságai Ha ℜ a H halmazon értelmezett reláció, és az a ℜ a a halmaz minden elemére teljesül, akkor az ℜ reláció reflexív. Példák reflexív relációkra:

A pozitív természetes számok halmazán: a osztója b-nek. A sík valamennyi egyenesének a halmazán: a párhuzamos b-vel. A valós számok halmazán: a egyenlı b-vel.

Hogyan néz ki a reláció, ha azt táblázatosan vagy gráffal adjuk meg?

Matematika I.


69

h1

h1

h2

h3

h4

h5

h2 h3 h4 h5

h1

h2

h5

h4

Matematika I.


h3

70

Egy H halmazon értelmezett ℜ binér relációt akkor mondunk szimmetrikusnak, ha bármely a,b ∊ H-ra a ℜ b és b ℜ a egyaránt fennáll. Példák szimmetrikus relációkra:

A pozitív természetes számok halmazán: a egyenlı b-vel. A sík valamennyi háromszögének a halmazán: a hasonló b-hez. A sík valamennyi egyenesének a halmazán: a merıleges b-re. A valós számok halmazán: a nem egyenlı b-vel.

Hogyan néz ki a reláció, ha azt táblázatosan vagy gráffal adjuk meg? Matematika I.


71

h1

h1

h2

h3

h4

h5

h2 h3 h4 h5

h1

h2

h5

h4

Matematika I.


h3

72

Antiszimmetrikusnak nevezünk egy relációt, ha bármely a,b ∊ H-ra az a ℜ b és a b ℜ a relációk közül legfeljebb az egyik áll fent. Ha az a ℜ a reláció jelenlétét kizárjuk, akkor szigorú értelemben antiszimmetrikus a reláció, ellenkezı esetben tágabb értelemben antiszimmetrikus. Példák szigorúan antiszimmetrikus relációkra:

A pozitív természetes számok halmazán: a kisebb b-nél. A valódi részhalmaza B-nek. A természetes számok halmazán: a „rákövetkezıje” b-nek.

A szigorúan antiszimmetrikus reláció gráfreprezentációja nem tartalmaz hurkot. Matematika I.


73

Egy H halmazon értelmezett ℜ binér relációt akkor mondunk tranzitívnak, ha bármely a,b,c ∊ H-ra a ℜ b és b ℜ c-bıl következik, hogy a ℜ c. Példák tranzitív relációkra:

A pozitív természetes számok halmazán: a kisebb b-nél. A pozitív természetes számok halmazán: a osztója b-nek. A sík valamennyi háromszögének a halmazán: a hasonló b-hez. A sík valamennyi egyenesének a halmazán: a párhuzamos b-vel. Az A részhalmaza B-nek (A ⊆ B).

Matematika I.


74

Ekvivalenciarelációk A reflexív, szimmetrikus és tranzitív relációt ekvivalenciarelációnak nevezzük. Jelölése: a ~ b. Pl. Legyen H egy cég összes dolgozóinak a halmaza. Az a ℜ b jelentse azt, hogy „ a ugyanazon az emeleten dolgozik, mint b. Világos, hogy ez a reláció reflexív, mert a ℜ a. szimmetrikus, mert ha a ℜ b , akkor b ℜ a. tranzitív, hiszen a ℜ b és b ℜ c , akkor a ℜ c. További példák: A pozitív természetes számok halmazán: a egyenlı b-vel. A sík valamennyi egyenesének a halmazán: a párhuzamos b-vel. A részhalmaza B-nek (A ⊆ B). Matematika I.


75

Egy nevezetes ekvivalencia reláció a kongruencia reláció: Legyen a,b ∊ ℤ és m ∊ℕ.

a ≡ b (mod m )

Olvasva: a kongruens b-vel modulo m. Jelentése: a és b m-mel osztva ugyanazt a maradékot adja. Azok a számok, amelyek kongruensek egymással (modulo m), azok egy maradékosztályba tartoznak. Tétel: A maradékosztályok az egész számok halmazának diszjunkt részhalmazait alkotják, ha m-et rögzítjük. Bizonyítsuk be (esetleg a gyakorlaton), hogy a kongruencia ekvivalenciareláció.

Matematika I.


76

Ekvivalenciosztályok Legyen ℜ a T halmazon értelmezett ekvivalenciareláció, és legyen a ∊ T. Az a ekvivalenciaosztályának nevezzük T-nek az a-val ekvivalens elemeinek halmazát, azaz az a-val relációban lévı elemek halmazát. Jelölése: T(a). (T(a) ⊂ T ). Tétel: Legyen a,b ∊ T , és a ≠ b. Ha T(a)-nak és T(b)-nek van nem üres metszete, akkor a két ekvivalenciaosztály megegyezik Tegyük fel, hogy a T(a) és T(b) ekvivalenciosztályoknak van közös eleme. Legyen ez x. Mivel x ∊ T(a) és x ∊ T(b), ezért x ~ a és x ~ b egyidejőleg. Így a tranzitivitás miatt a ~ b., ezért a ∊ T(b), ami miatt T(a) ⊆ T(b). Hasonlóan megmutatható, hogy T(b) ⊆ T(a). Így T(a) = T(b). Matematika I.


77

Következmény: Két különbözı ekvivalanciaosztály metszete az üres halmaz. Egy ekvivalenciaosztályt bármely eleme meghatározza. Ha T az alaphalmaz, akkor T* jelöli a T halmazhoz tartozó ekvivalenciaosztályok halmazát. Példa. Legyen T az egész számok halmaza. Az egész számokat írjuk tört alakba, és a T halmazon értelmezzük a következı relációt: ω ℜ ω' , ahol ω = a / b és ω' = a' / b' és a b' = a' b, b ≠ 0, b' ≠ 0.

6 3 Ezért például ℜ . 5 10

Lássuk be, hogy az így definiált reláció reflexív, szimmetrikus és tranzitív. (Azaz ekvivalenciareláció.) Határozzuk meg az ekvivalenciaosztályok számát! Matematika I.


78

Vannak más relációk is, amelyek – tulajdonságai miatt – kitüntetett figyelmet érdemelnek. A H halmazt rendezettnek mondjuk, ha elemein értelmezve van egy a ≺ b reláció, amely rendelkezik az alábbi tulajdonságokkal: a ≺ a hamis (irreflexivitás) ha a ≺ b igaz, akkor b ≺ a hamis (asszimetria) ha a ≺ b igaz, és b ≺ c igaz, akkor a ≺ c igaz (tranzitivitás) ha a ≠ b, akkor az a ≺ b és a b ≺ a közül legalább az egyik igaz (trichotómia).

Matematika I.


79

A természetes számok halmaza, a racionális számok halmaza és a valós számok halmaza rendezett a ” < ” ( ” > ” ) relációra nézve. Egy rendezett halmazt jólrendezettnek mondunk, ha bármely nem üres részhalmazának van kezdı eleme, azaz olyan eleme, amelyet – az adott rendezés szerint – az adott részhalmaz egyetlen eleme sem elız meg. Példák A természetes számok nagyság szerint rendezett halmaza jólrendezett. A racionális és a valós számok halmaza nem jólrendezett halmaz. Bizonyítsuk be, hogy a racionális számok halmaza nem jólrendezett!

Matematika I.


80

Függvények Ha valamely A halmaz elemeihez adott utasítás szerint egy B halmaz elemeit rendeljük hozzá úgy, hogy A minden elemének megfeleltünk legalább egy B-beli elemet, akkor azt mondjuk, hogy az A halmazt leképezzük a B halmazra vagy halmazba. Ha a B halmaz összes elemét megfeleltjük A elemeinek, akkor a B halmazra képezünk. Ha a B halmaz egy részhalmazát feleltjük meg A elemeinek, akkor a B halmazba képezünk. Az A-t tárgyhalmaznak, elemeit tárgyelemeknek nevezzük. Az B-t képhalmaznak, elemeit képelemeknek nevezzük. A leképezést a hozzárendelési elıírás és a tárgyhalmaz egyértelmően meghatározza. Jelölése: φ: A → B, vagy a → φ(a), ha a ∊ A. Matematika I.


81

Ha minden a ∊ A-ra (a; φ(a)) ∊ A × B, akkor a φ relációt leképezésnek nevezzük. A φ és δ leképezéseket akkor tekintjük egyenlınek, ha bármely a ∊ A esetén φ(a) = δ(a). A leképezéseket a tárgyelemekhez rendelt képelemek száma, ill. a képelemekhez rendelt tárgyelemek száma szerint osztályozhatjuk: Ha minden egyes képelemnek csak egy tárgyeleme van, akkor a leképezés egy-egyértelmő vagy kölcsönösen egyértelmő.

B

A Matematika I.


82

Ha valamely képelemnek több tárgyeleme van, akkor a leképezés több-egyértelmő.

B

A

Pl. háromszögek → területük

Matematika I.


83

Ha több képelemnek egy tárgyeleme van, akkor a leképezés egytöbbértelmő.

B

A

Pl. anya → gyerekei

Matematika I.


84

Ha több képelemnek több tárgyeleme is lehet, akkor a leképezés több-többértelmő.

B

A

Pl. tulajdonosok → cégek

Matematika I.


85

A függvény mint leképezés Legyen adott két halmaz, A és B. Függvénynek nevezünk minden olyan binér (kételemő) relációt, amely az A halmaz minden elemének a B halmaz egyetlen elemét felelteti meg. Következmény: Minden függvény reláció, de nem minden reláció függvény: a függvény egy A halmaznak egyértelmő leképezése egy B halmazra. Az A halmazt a függvény értelmezési tartományának, a B halmazt a függvény értékkészletének nevezzük. A függvénykapcsolat jelölése: y = f(x).

Matematika I.


86

A fentiek értelmében egy függvény akkor van pontosan meghatározva, ha megadjuk Az értelmezési tartományt (az A halmazt) az értékkészletet (a B halmazt) A hozzárendelést, azaz azt a leképezést, amely minden x ∊ A elemet társít egy y ∊ B elemmel. Ha B minden eleme képe az A halmaz egy elemének, akkor az f függvényt szürjektívnek nevezzük. Ha az A halmaz két különbözı elemének mindig különbözık a Bbeli képei, akkor a leképezés injektív. Ha egy függvény egyszerre szürjektív és injektív (azaz kölcsönösen egyértelmő), akkor bijektív.

Matematika I.


87

A függvények ábrázolása, megadása A függvények, mint speciális binér relációk megadását négy módon végezhetjük:

utasítás táblázat Descartes diagram Venn diagram Függvények ábrázolása utasítással

Például: f: ℝ → ℝ, f(x) = 2x2 – 3.

Matematika I.


88

Függvények megadása táblázattal

a1 a2 a3 a4 a5

b1

b2 +

b3

b4

b5

+ + + +

ahol ai ∊ A és bi ∊ B, i = 1,2,…,5.

Matematika I.


89

Függvények megadása Descartes diagrammal

Vegyük észre, hogy a diagram elkészítését egy y = (x-3)2 függvénykapcsolat alapján végeztük el. Matematika I.


90

Függvények megadása Venn diagrammal

B

A

A két halmazt zárt síkidomban elhelyezett pontok ábrázolják. Minden pontot nyíl köt össze a képével. A kiinduló halmaz minden pontja egyetlen nyíl kiindulópontja.

Matematika I.


91

Az összetett függvény Legyen adott három halmaz, A, B, C, és legyen f az A egy leképezése B-be, és g a B leképezése C-be. Feleltesse meg f az A minden elemének a B egy és csakis egy y elemét, és feleltesse meg g a B ezen y elemének C egy és csakis egy z elemét. Így az A minden x elemének megfelel C egy és csakis egy z eleme. Az így definiált hozzárendelés leképezte az A halmazt a C halmazba: z = g(f(x)). Ez az új leképezés az f és g függvénybıl álló összetett leképezés, a két leképezés szorzata. Jelölése: g ∘ f. Az f és g leképezések g ◦ f szorzatán az f és g leképezések egymás utáni végrehajtását értjük ebben a sorrendben. (Az f függvény értékkészletét tartalmaznia kell a g függvény értelmezési tartományának!) Matematika I.


92

Tétel: Két leképezés összetétele nem kommutatív. Példa: Legyen f : ℝ → ℝ, f(x) = 2x2 – 3, g : ℝ → ℝ, g(x) = cos x. Ekkor g ∘ f = cos (2x2 – 3 ) és f ◦ g = 2 cos2 x – 3.

Ábrázoljuk a két függvényt!

Matematika I.


93

Inverz függvény Az f: A → B létesítsen az A és B elemei között kölcsönösen egyértelmő hozzárendelést. Ekkor B minden eleme egyetlen A-beli elemnek a képe, azaz minden y ∊ B-hez tartozik egyetlen x ∊ A úgy, hogy y = f(x). Így a B-n értelmezett g függvényt kaptunk: g: B → A. Ha y ∊ B, akkor g(y) az az egyértelmően meghatározott x ∊ A, amelyre f(x) = y. Ezt a függvényt az f függvény inverz függvényének nevezzük. Jelölése: f -1. Ha f -1 az f függvény inverze, akkor f értelmezési tartománya az f -1 függvény értékkészlete, és f értékkészlete az f -1 értelmezési tartománya. Matematika I.


94

Ha az (x, f(x)) az f grafikonjának egy pontja, akkor az (f(x), x) az f -1 függvény grafikonjának egy pontja, azaz a két függvény grafikonjai egymásnak tükörképei, ahol a tükrözés tengelye az y = x egyenes. f : ℝ → ℝ, f(x) = 2x, f -1(x) = log2 x, f(x) = 2x f -1(x) = log2 x

Matematika I.


95

Rekurzív sorozatok Oldjuk meg a következı feladatot: Hány nyúl származik egyetlen pár nyúltól, ha tudjuk, hogy minden pár havonta új párnak ad életet, és az újszülött nyulak két hónapos koruktól lesznek szülıképesek? hónap 1 nyúlpár 1

2 1

3 2

4 3

5 5

6 8

7 13

8 21

9 34

10 55

Fibonacci sorozat: an = an-1 + an-2 n n  1 1+ 5  1− 5    −  an =  5  2   2    

Matematika I.


96

A Fibonacci-sorozat néhány tulajdonsága:

A sorozat n. eleme 1-gyel nagyobb, mint az elsı n-2 elem összege. an akkor osztható 2-vel, ha ha n = 3k alakú. 4 oszója an -nek, ha n = 6k alakú.

Nyitott probléma: A Fibonacci-sorozatban véges sok, vagy végtelen sok prímszám van-e?

Matematika I.


97

Az ítélet mint függvény

Az ”a táncolt b-vel” reláció egy alaphalmazon értelmezett tulajdonság. Ha az (a,b) párra a tulajdonság fennáll – azaz az állítás igaz – akkor a pár a relációhoz tartozik. Az így elıállított függvény értelmezési tartománya az összes lehetséges párok halmaza, az A × B halmaz. A szorzathalmaz minden eleméhez egy igaz vagy egy hamis érték tartozik. Ezért a kapott függvény minden elempárhoz egy logikai értéket rendel. Az így kapott függvényt kijelentésfüggvénynek (predikátumfüggvénynek) nevezzük.

Matematika I.


98

A matematikai logika alapjai A logika a gondolkodás tárgyát képezı konkrét problémáktól, tartalmi információktól elvonatkoztat, és a gondolkodási folyamat elemeinek, megállapításainak közös, a következtetés szempontjából lényeges tartalmát használja fel. Ez a közös tartalom, vagy közös jellemzı az állítások igazságértéke, ami alatt a klasszikus kétértékő logikában azt a tényt érjük, hogy egy állítás igaz vagy nem igaz (hamis). A logikának azt az ágát, amely a fenti módon közelíti a gondolkodás kérdéseit klasszikus – kétértékő – logikának nevezzük.(Ez azt jelenti, hogy a klasszikus kétértékő logika számára az állítások két lehetséges igazságértéke az alap. Ez az igazságérték bizonytalanságot nem tartalmaz, a két igazságérték kizárja egymást.) Matematika I.


99

Egy megállapítást a logika szempontjából akkor tekintünk állításnak, ha eldönthetı róla, hogy igaz vagy hamis. Többértékő logikák létezése: fuzzy logika. A matematikai logikát elsısorban a matematikai kutatásokban alkalmazzák, de a mindennapi élet és a kutatások minden olyan területén használható, ahol az igazságérték – mint absztrakció – elfogadható. Így a számítástudomány és a mesterséges intelligencia is alkalmazza a matematikai logikát. A matematikai logika kiemelkedı alakjai: • Gottfried Wilhelm Leibnitz (1646 – 1716) • George Boole (1815 – 1864) Matematika I.


100

Állításon vagy kijelentésen olyan kijelentı mondatot értünk, amely egyértelmően igaz vagy hamis. Egy állítás egyidejőleg nem lehet igaz is és hamis is (ellentmondástalanság elve). Egy állítás nem lehet sem nem igaz sem nem hamis (kizárt harmadik elve). Vannak olyan kijelentések, amelyekkel a logika nem foglalkozik: • x < 5, mert adott x nélkül az állításnak nincs meghatározott igazságértéke. • ”az út holnap csúszós lesz”, mert az adott pillanatban nem dönthetı el az állítás. • az ”azért …, mert” típusú állítások.

Matematika I.


101

Mőveletek állításokkal, logikai értékekkel Logikai mőveleten olyan eljárást értünk, amely egy vagy több kijelentésbıl (ezek a mővelet tagjai) olyan kijelentést képez (ez a mővelet eredménye), amelynek igaz vagy hamis voltát a tagok igaz, ill. hamis volta egyértelmően meghatározza. A mőveleteket egy-, két-, három-, … n-változósnak nevezzük aszerint, hogy egy-, két-, három-, … n kijelentésbıl képeznek új kijelentést. Az állítások körében is elegendı a logikai értékek közötti mőveleteket tisztázni.

Matematika I.


102

Negáció Egy p kijelentés negációján (tagadásán) a ”nem igaz, hogy p” kijelentést (vagy ennek egy nyelvtanilag átfogalmazott alakját) értjük. ”A számítógép nem síkidom”. Ez egy egyváltozós ítélet, amely egy állítás (ti. ”A számítógép síkidom”) tagadásából áll. (Nem vizsgáljuk az eredeti állítás igazságtartalmát.) A negáció mőveletének igazságtáblája: p ¬p i h

Matematika I.


h i

103

Konjunkció Két kijelentés, p és q konjunkcióján (összekapcsolásán) a ”p és q” kijelentést (vagy ennek egy nyelvtanilag átfogalmazott alakját) értjük. ”A 3 osztója a 12-nek és a 4 osztója a 16-nak.” Ez az állítás igaz, mert az elıtagja és az utótagja is igaz. A konjunkció akkor és csak akkor igaz, ha mindkét tagja igaz. Jelölése: p ∧ q. A konjunkció mőveletének igazságtáblája: p

q

i i h h

i h i h

Matematika I.


p∧ q i h h h

104

Diszjunkció Két kijelentés, p és q diszjunkcióján (szétválasztásán) a ”p vagy q” kijelentést (vagy ennek egy nyelvtanilag átfogalmazott alakját) értjük. (Megengedı értelmő összekapcsolás.) ”Tejet vagy kakaót reggelizünk.” Ez az állítás akkor igaz, ha legalább az egyik tagja igaz. Jelölése: p ∨ q. A diszjunkció mőveletének igazságtáblája:

Matematika I.


p

q

i i h h

i h i h

p∨ q i i i h

105

Az ítéletkalkulusban a logikai értékeket, a logikai változókat és a rajtuk végzett mőveleteket leíró jelsorozatokat az ítéletkalkulus formuláinak nevezzük. Két formulát azonosnak nevezünk, ha a két formula a benne szereplı változók minden lehetséges értékére ugyanazt a logikai értéket állítja elı. Példa: A ∪ (B ∩ C ) = A A bizonyítás abból áll, hogy kimutatjuk az a ∊ A ∨ (a ∊ A ∧ a ∊ B ) állítás akkor és csak akkor igaz, amikor az a ∊ A állítás. Elegendı azt bebizonyítani, hogy az állítások a változók logikai értékeire megegyeznek. Matematika I.


106

Tehát azt kell igazolnunk, hogy p, q tetszıleges állítások esetén a fönnáll-e a p = p ∨ (p ∧ q ) egyenlıség. Készítsük el az igzságtáblázatot: p

q

i i h h

i h i h

r=p∧q p∨r i h h h

i i h h

Mivel táblázatunk elsı és utolsó oszlopa megegyezik, ezért az állításunk igaz.

Matematika I.


107

Tétel: Bármely logikai mővelet kifejezhetı a negáció és a konjunkció mőveletével. Nem bizonyítjuk, de megmutatjuk az elıállításokat: p ∨ q = ¬( ¬ p ∧ ¬ q )

Matematika I.

p

q ¬p ¬q

i i h h

i h i h

h h i i

h i h i

p∨q

¬( ¬ p ∧ ¬ q )

i i i h

i i i h


108

A logikai mőveletek tulajdonságai Logikai ”vagy”: kommutatív: p ∨ q = q ∨ p asszociatív: (p ∨ q) ∨ r = p ∨ (q ∨ r) disztributív: p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) idempotens: p ∨ p = p Logikai ”és”: kommutatív: p ∧ q = q ∧ p asszociatív: (p ∧ q) ∧ r = p ∧ (q ∧ r) disztributív: p ∧(q ∨ r) = (p ∧ q) ∨ (p ∧ r) idempotens: p ∧ p = p Matematika I.


109

További logikai mőveletek A ”p akkor q” alakú kifejezéseket implikációnak nevezzük. (Itt p az elıtag és q az utótag.) ”Ha a részvények ára csökken, akkor nem adom el ıket.” (Amennyiben a részvények ára nem csökken, akkor igaznak tekintjük az állítást akár eladtam a részvényeket, akár nem, mert erre vonatkozóan nem mondtunk elıre .) Jelölése: p → q. Az implikáció mőveletének igazságtáblája:

Matematika I.


p

q

i i h h

i h i h

p→ q i h i i 110

Tétel: Az implikáció nem kommutatív és nem asszociatív mővelet. Az implikáció kifejezése diszjunkcióval és negációval: p

¬p

i i h h

h h i i

q i h i h

¬p ∨ q

p

q

p→ q

i h i i

i i h h

i h i h

i h i i

Ezért: p → q = ¬p ∨ q. Amennyiben figyelembe vesszük az implikáció kifejezhetıségét a negációval és a konjunkcióval, azt kapjuk, hogy: p → q = ¬(p ∧ ¬ q). Matematika I.


111

A ”ha p akkor q, és ha q akkor p” alakú kifejezéseket ekvivalenciának nevezzük. ”Egy négyszög akkor és csak akkor húrnégyszög, ha szemközti szögeinek összege 180°.” (Figyeljük meg, hogy itt két állítást tettünk egyszerre.) Jelölése: p ↔ q. A definíció szerint p ↔ q = (p → q) ∧ ( q → p) Az ekvivalencia mőveletének igazságtáblája: p

q

p↔q

i i h h

i h i h

i h h i

p ↔ q = (p → q) ∧ ( q → p) p ↔ q = (¬p ∨ q) ∧ (¬q ∨ p) p ↔ q = ¬(p ∧ ¬ q) ∧ ¬(¬p ∧ q) Matematika I.


112

A ”nem igaz, hogy ha p akkor q, és ha q akkor p” alakú kifejezéseket antivalenciának nevezzük. A mővelet a ”kizáró vagy ismert” (XOR). Az antivalencia akkor és csak akkor igaz, ha a két állítás logikai értéke különbözı. Jelölése: p ⊕ q. A mővelet az igazságtáblázatból kizárja azokat az eseteket, amelyekben mindkét állítás igaz, tehát formálisan az ekvivalencia tagadását jelenti. p ⊕ q = ¬(p ↔ q ) Az antivalencia mőveletének igazságtáblája: p⊕q=q⊕p p ⊕ q = ¬(p ↔ q ) p ⊕ q = ¬(p ∧ q) ∧ ¬(¬ p ∧ ¬ q) p ⊕ q = (¬ p ∧ q) ∨ (p ∧ ¬ q) Matematika I.


p

q

p↔q

i i h h

i h i h

h i i h 113

A ”sem p sem q” alakú összetett kifejezéseket sem-sem (Webb-féle) mőveletnek nevezzük. A mővelet a diszjunkció tagadása (NOR). Jelölése: p ↓ q. Érvényes a következı azonosság: p ↓ q = ¬(p ∨ q ) A Webb-féle mővelet igazságtáblája: p↓q=q↓p

Matematika I.


p

q

p↓q

i i h h

i h i h

h h h i 114

A ”nem p vagy nem q” alakú kifejezéseket Sheffer-féle mőveletnek nevezzük. ”Vagy iszik az ember vagy vezet.” A mővelet a konjunkció tagadása (NAND). Ebben az esetben a két kijelentés közül legfeljebb az egyik igaz. Jelölése: p | q. Érvényes a következı két azonosság: p | q = ¬(p ∧ q ) Az Sheffer-féle mővelet igazságtáblája:

Matematika I.


p | q = ¬p ∨ ¬ q p

q

p|q

i i h h

i h i h

h i i i 115

A logikai függvény fogalma Az eddigiekben kétváltozós mőveleteket vizsgáltunk, amelyek tekinthetık kétváltozós függvényeknek is. Ebben az esetben az értelmezési tartomány az {i, h} halmaz és az értékkészlet is az {i, h} halmazból való. Legyen i = 1 és n = 0. Az ilyen típusú függvényeket igazságfüggvénynek vagy Boolefüggvénynek nevezzük. A kétváltozós Boole-függvények mintájára definiálható az nváltozós Boole-függvény is: ekkor mind az értelmezési tartomány, mind az értékkészlet egy olyan szám n-es, amelynek elemei a {0, 1} halmazból származnak. Matematika I.


116

Hány darab n-változós Boole-függvény van? Az értéktáblázatnak n oszlopa van, és minden helyre vagy 0-t vagy 1-et írunk. Ezért összesen 2n sorunk lesz. Minden sorban kétféle módon választhatjuk meg a függvényén rtéket, ti. vagy 0-t vagy 1-t. Így a Boole függvények száma: 2 2 .

Matematika I.

2n

n

2n

2 .

1

2

4

2

4

16

3

8

256

4

16

65536

5

32

4294967296

6

64

1,84 ·1019


117

p 1 0 1 0 q 1 1 0 0 f1 f2 f3 f4 f5 f6 f7 f8

1 1 1 1 1 1 1 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

f9 0 0 0 f10 0 0 0 f11 0 0 1 f12 0 0 1 f13 0 1 0 f14 0 1 0 f15 0 1 1 f16Matematika 0 1 1I.

1 0 1 0 1 0 1 0

f1 f2 f3 f4 f5 f6 f7 f8

= q ∨ ¬q = p ∨q = p → q = ¬p ∨ q =q = q → p = ¬q ∨ p =p = p ↔ q = (p → q) ∧ ( q → p) =p∧q

0 1 0 1 0 1 0 1

f9 = q ∧ ¬q f10 = p ↓ q = ¬(p ∨ q ) f11 = ¬(p → q) = p ∧ ¬q f12 = ¬q f13 = ¬(q → p) = q ∨ ¬p f14 = ¬p f15 = p ⊕ q f16 = p | q =Felsıfokú ¬(p ∧ qSzakképzés )

„mindig” diszjunkció implikáció q implikáció p ekvivallencia konjunkció „soha” „sem-sem” implikáció tagadása negáció implikáció tagadása negáció antivalencia Sheffer mővelet 118

Normálformák és függvényrendszerek A kétváltozós függvényeknél láttuk, hogy mindegyik felírható a negáció, a konjunkció valamint a diszjunkció mőveleteinek segítségével. Megmutatható ez érvényes az n-változós Boole-függvényekre is oly módon, hogy felírható egy olyan formula, amely az adott n változóból épül fel, és mőveletként a ¬, a ∧ és a ∨ logikai mőveleteket használjuk. Az így felírt formula értéke pontosan akkor lesz igaz, amikor az átalakítandó függvény értéke is igaz. A fenti állítást nem bizonyítjuk, hanem egy példát mutatunk a konstrukcióra. Matematika I.


119

x1

x2

x3

g(x1,x2,x3)

1

1

1

0

1

1

0

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

0

0

1

1

0

0

0

0

g(x1,x2,x3) = (x1 ∧ ¬x2 ∧ ¬x3) ∨ (¬x1 ∧ x2 ∧ ¬x3) ∨ (¬x1 ∧ ¬x2 ∧ x3)

Matematika I.


120

Eljárás-1: olyan formulát állítottunk elı, amivel az értéktáblázattal megadott igazságfüggvényt ki tudjuk fejezni. A formula jellemzıi: a formula konjunkciók diszjunkciója, minden konjunkciós tag vagy egy változó vagy annak a negáltja, minden diszjunkciós tagban minden változó szerepel, ugyanaz a változó egy konjunkcióban csak egyszer szerepel, nincs két olyan diszjunkciós tag, amelyek csak a változók sorrendjében különböznek.

A fenti tulajdonságú formulát teljes diszjunktív normálformának nevezzük. Matematika I.


121

x1

x2

x3

h(x1,x2,x3)

1

1

1

1

1

1

0

0

1

0

1

1

1

0

0

1

0

1

1

0

0

1

0

0

0

0

1

0

0

0

0

1

h(x1,x2,x3) = (¬x1∨¬x2∨x3)∧(x1∨¬x2∨ ¬x3)∧(x1∨¬x2∨x3)∧(x1∨x2∨ ¬x3)

Matematika I.


122

Eljárás-2: olyan formulát állítottunk elı, amivel az értéktáblázattal megadott igazságfüggvényt ki tudjuk fejezni. A formula jellemzıi: a formula diszjunkciók konjunkciója, minden diszjunkciós tag vagy egy változó vagy annak a negáltja, minden konjunkciós tagban minden változó szerepel, ugyanaz a változó egy diszjunkcióban csak egyszer szerepel, nincs két olyan konjunkciós tag, amelyek csak a változók sorrendjében különböznek.

A fenti tulajdonságú formulát teljes konjunktív normálformának nevezzük. Matematika I.


123

A fenti két elıállítás következménye, hogy a három mővelet (¬, ∧, ∨) teljes függvényrendszert alkot, azaz bármely igazságfüggvény elıállítható ezek segítségével. Tétel: A negáció és konjunkció (¬, ∧) önmagukban is teljes függvényrendszert alkotnak. Biz. A tétel állítása azonnal következik abból, hogy a diszjunkció kifejezhetı a fenti két mővelet segítségével: p ∨ q = ¬( ¬ p ∧ ¬ q )

Matematika I.


124

Gyakorlat anyaga: A következtetés Gyakran használt következtetési szabályok Leválasztási szabály Elvevı szabály Hipotetikus szillogizmus Indirekt bizonyítás Kontrapozíció

Matematika I.


125

Logikai áramkörök Gyakran elıfordul, hogy adott elemekbıl kell összeállítani áramkört oly módon, hogy az elıre meghatározott gyakorlati célt elégítsen ki. A legegyszerőbb esetekben az áramkört áramforrásból, kapcsolókból és fogyasztókból kell felépíteni. Soros kapcsolás esetében annak feltétele, hogy az áramkörben áram folyjék az, hogy mindkét kapcsoló be legyen kapcsolva: x1

x2

Legyen xi értéke igaz, ha az xi kapcsoló bekapcsolt állapotban van. Annak logikai feltétele, hogy a lámpa égjen: x1 ∧ x2 . Matematika I.


126

Párhuzamos kapcsolás esetében annak feltétele, hogy az áramkörben áram folyjék az, hogy legalább az egyik kapcsoló be legyen kapcsolva: x1 x2

Legyen xi értéke igaz, ha az xi kapcsoló bekapcsolt állapotban van. Annak logikai feltétele, hogy a lámpa égjen: x1 ∨ x2 .

Matematika I.


127

Az automaták A kibernetikában (informatikában) a különféle információ átalakító eszközöket automatáknak nevezzük. Egy automatának véges sok bemenete van, ezek kívülrıl kapják az információt. Az automata mőködése úgy jellemezhetı, hogy megadjuk a kimeneteken megjelenı adatot a bemenı adatok függvényében, azaz megadjuk a k darab kimeneti információt leíró n-változós függvényeket (ahol k a kimenetek száma, n pedig a bemenetek számának felel meg). Az is nyilvánvaló, hogy mind a bemenetek mind a kimenetek igazságfüggvények (az értékkészlete a {0, 1} halmazból kerül ki. Az automaták ennél bonyolultabbak, de nekünk most ennyi elég. Matematika I.


128

Egyszerő véges automatáknak nevezzük azokat az elektronikus áramköri egységeket, amelyek az egyes logikai áramköröknek felelnek meg. Mivel minden logikai mővelet elıállítható a konjunkció, a diszjunkció és a negáció segítségével (ezek teljes függvényrendszert alkotnak), ezért ezek a leggyakrabban alkalmazott áramkörök. Jellemzıik: A konjunkciónak megfelelı ÉS kapunak két (esetleg több) bemenete és egy kimenete van. A kimeneten akkor és csak akkor van impulzus – ezt jelöljük 1-gyel – ha mindegyik bemeneten van impulzus. Jelölése: ÉS

Matematika I.


129

A diszjunkciónak megfelelı VAGY kapunak két (esetleg több) bemenete és egy kimenete van. A kimeneten akkor és csak akkor van impulzus – ezt jelöljük 1-gyel – ha legalább bemeneten van impulzus. Jelölése: VAGY

A negációnak megfelelı NEM (INVERTER) kapunak egy bemenete és egy kimenete van. A kimeneten akkor és csak akkor van impulzus – ezt jelöljük 1-gyel – ha a bemeneten nincs impulzus. Jelölése: NEM

Matematika I.


130

A digitális készülékek építıelemeinek legjelentısebb csoportját az un. logikai áramkörök alkotják. A logikai áramkörök bármely teljes logikai függvényrendszernek megfelelı áramkörökbıl – így az ÉS, a VAGY és a NEM áramkörökbıl – felépíthetık. Példa A logikai ”kizáró vagy” (XOR) normál formája: x1 ⊕ x2 = (¬ x1 ∧ x2) ∨ (x1 ∧ ¬ x2) x1 NEM

ÉS VAGY

NEM

ÉS

x2 Matematika I.


131

Gyakorlat: Készítsük el más logikai függvény áramkörét! Logikai programozás Nem kétértékő logikák

Matematika I.


132

A lineáris algebra alapjai Oldjunk meg egy kétismeretlenes lineáris egyenletrendszert! Induljunk ki az elsıfokú kétismeretlenes lineáris egyenletrendszer általános alakjából: a1 x + b1 y = c1

a2 x + b2 y = c2 Az un. ”egyenlı együtthatók” módszerét fogjuk alkalmazni: olyan konstansokkal szorozzuk a két egyenletet, hogy az egyenletek összeadása után csak az x (ill. az y) maradjon ismeretlenként az egyenletben. Az így kapott egyismeretlenes elsıfokú egyenletet már egyszerően megoldhatjuk.

Matematika I.


133

Szorozzuk meg az elsı egyenletet b2-vel, a másodikat (-b1)-gyel, majd adjuk össze az egyenleteket. Azt kapjuk, hogy:

(a1b2 − a2b1 ) x = c1b2 − c2b1 Ebbıl kapjuk:

c1b2 − c2b1 x= a1b2 − a2b1 (Ennek a kifejezésnek akkor van csak értelme, ha a1b2 − a2b1 ≠ 0. ) Hasonlóan kapjuk, hogy

c1a2 − c2 a1 a1c2 − a2 c1 y= = , a2b1 − a1b2 a1b2 − a2b1

Matematika I.

ha a1b2 − a2b1 ≠ 0


134

Figyeljük meg a kapott megoldások szerkezetét! Mind a számlálóban, mind a nevezıben négy-négy számból azonos módon képeztünk egy új számot. Vezessük be erre a mőveleti utasításra a következı jelölést: a1 b1 a1b2 − a2b1 = . a2 b2 Ezt az új objektumot az a1, a2, b1, b2 számokból képzett másodrendő determinánsnak nevezzük. Azt mondjuk, hogy az a1, b2 elemek a fıátló mentén, míg az a2, b1 elemek a mellékátló mentén fekszenek. Egy másodrendő determináns értékét úgy számoljuk ki, hogy a fıátlóbeli elemek szorzatából kivonjuk a mellékátló mentén fekvı számok szorzatát.

Matematika I.


135

A másodrendő determináns segítségével az egyenletek megoldásai a következı alakban írhatók fel: c1 b1 a1 c1 Dy c 2 b2 a 2 c2 Dx x= = , y= = , a1 b1 a1 b1 D D a 2 b2 a 2 b2 ahol

Dx =

c1

b1

c2

b2

,

Dy =

a1

c1

a2

c2

,

D=

a1

b1

a2

b2

Itt D-t az egyenletrendszer determinánsának nevezzük. A Dx (ill. a Dy) determinánst a D-bıl úgy kapjuk, hogy az x (ill. az y) együtthatóinak helyébe beírtuk az egyenletrendszer jobb oldalán álló számokat. Matematika I.


136

Példa:

x + 3y = 7 x+ y =5 Most a rendszer determinánsa:

D= és

Dx = Ezért:

7 3 5 1

1 3 1 1 = −8,

Dx − 8 x= = = 4, D −2

= 1 − 3 = −2 ≠ 0.

Dy =

1 7 1 5

= −2.

Dy

−2 y= = = 1. D −2

Helyettesítéssel ellenırizzük az eredmény helyességét! Matematika I.


137

A másodrendő determináns tulajdonságai Tétel: A determináns értéke elıjelet vált, ha két sorát (vagy két oszlopát) megcseréljük. Biz.

−

a1

b1

a2

b2

−

a1

b1

a2

b2

= −(a1b2 − a2b1 ) = a2b1 − a1b2 =

a2

b2

a1

b1

= −(a1b2 − a2b1 ) = b1a2 − a1b2 =

,

b1

a1

b2

a2

.

Következmény-1: A determináns értéke nem változik, ha az elemeket a fıátlóra tükrözzük. Matematika I.


138

Következmény-2: Minden olyan tétel, amely érvényes egy másodrendő determináns soraira kimondva, érvényes marad akkor is, ha azt a determináns oszlopaira mondjuk ki. Tétel: Ha egy determinánst egy sorának minden elemét megszorozzuk egy k konstanssal, akkor a determináns értéke k-szorosára nı. Biz.

a1 b1 a1 k = k (a1b2 − a2b1 ) = a1kb2 − b1ka2 = a2 b2 ka2

Matematika I.


b1 . kb2

139

Tétel: Ha a másodrendő determináns két sora elemrıl-elemre megegyezik, akkor a determináns értéke nulla. Biz.

a1

b1

a1

b1

= ( a 1b1 − a 1b1 ) = 0 .

Következmény-3: Ha a másodrendő determináns egyik sora a másik sorának többszöröse, akkor a determináns értéke nulla. Biz.

Matematika I.

a1

b1

ka 1

kb 1

= k

a1

b1

a1

b1


= 0.

140

Tétel: Ha másodrendő determinánsban valamelyik sor (vagy oszlop) felbontható két elem összegére, akkor a determináns felírható két determináns összegeként. Biz.

a1 + c1

b1

a 2 + c2

b2

= (a1 + c1 )b2 − (a2 + c2 )b1 = = (a1b2 − a2b1 ) + (c1b2 − c2b1 ) = =

Matematika I.

a1

b1

a2

b2

+

c1

b1

c2

b2

.


141

Tétel: Egy determináns értéke nem változik, ha egy sorának konstans-szorosát hozzáadjuk a másik sorhoz. Biz.

a 1 + ka 2

b1 + kb 2

a2

b2

=

= =

Matematika I.

a1

b1

a2

b2

a1

b1

a2

b2

a1

b1

a2

b2

+

ka 2

kb 2

a2

b2

+k

a2

b2

a2

b2

=

=

a1

b1

a2

b2

.


142

Gyakorlat: Oldjuk meg a 100. oldalon levı 3 feladatot!

Matematika I.


143

Harmadrendő determinánson a következı 3×3-as elrendezést értjük:

a11 a21 a31

a12 a22 a32

a13 a23 a33

amelynek értékét a következı képlettel számítjuk ki:

a11 a21 a31

a12 a22 a32

a13 a23 = a11a22 a33 + a12 a23a31 + a13 a21a32 a33

− a13a22a31 − a12a21a33 − a11a23a32.

Matematika I.


144

Egy harmadrendő determináns fıátlóján az a11 és az a33 elemeket összekötı egyenes szakaszt értjük:

a11 a21 a31

a12 a22 a32

a13 a23 a33

A determináns mellékátlója az a13 és az a31 elemeket összekötı egyenes szakasz. A determináns értékét a Sarrus szabállyal határozhatjuk meg:

a11 a21 a31

a12 a22 a32

a13 a23 a33

a11

a12

a21

a22

a31

a32

a11a22a33+ a12a23a31 + a13a21a32 − a13a22a33 − a11a23a32 −a11a23a32 Matematika I.


145

Kifejtési Tétel: A harmadrendő determináns értéke kiszámítható másodrendő determinánsok súlyozott összegeként. Biz.

a 11

a 12

a 13

a 21

a 22

a 23 =

a 31 a 32 a 33 a11a22 a33 + a12 a23a31 + a13a21a32 − a13a22 a31 − a12 a21a33 − a11a23a32 =

a11 (a22 a33 − a23a32 ) + a12 (a23a31 − a21a33 ) + a13 (a21a32 − a22 a31 ) = a22 a11 a32

a23 a21 a23 a21 a22 − a12 + a13 a33 a31 a33 a31 a32

Matematika I.


146

Egy harmadrendő determináns aij eleméhez tartozó aldeterminánson azt a másodrendő determinánst értjük, amelyet úgy kapunk, hogy elhagyjuk a determináns i. sorát és j. oszlopát. Az aij elemhez tartozó

a 11 a 21 a 31

a 12 a 22 a 32

a 13 a 23 a 33

Jelölése:

a21 a22 A13 = a31 a32 Megjegyzés: a Kifejtési Tételben az aldetermináns elıjele +1, ha a az indexek összege páros, és (–1), ha az indexek összege páratlan. Matematika I.


147

Az elsıfokú három ismeretlenes egyenletrendszer Tekintsük a következı egyenletrendszert! a11 x1 + a12 x2 + a13 x3 = b1

a21 x1 + a22 x2 + a23 x3 = b2 a31 x1 + a32 x2 + a33 x3 = b3 Jelöljük az egyenletrendszer determinánsát D-vel, és jelölje Di azt a harmadrendő determinánst, amelyet D-bıl úgy kapunk, hogy D idik oszlopát az egyenletrendszer jobboldalán álló értékekkel helyettesítjük. Pl. a11 a12 b1 D3 = a21 a22 b2 a31 a32 b3 Matematika I.


148

Tétel(Cramer szabály): Ha az egyenletrendszer determinánsa nem 0, akkor az egyenletrendszernek pontosan egy megoldása van. Az i-dik ismeretlen értéke egy olyan törttel egyenlı, amelynek nevezıje a rendszer determinánsa, számlálója pedig Di:

Di xi = , D

i = 1,2,3.

Megjegyzés: A tétel állítása igaz n ismeretlenes egyenletrendszer esetén is.

Matematika I.


149

Gyakorlat: könyv 103-104. oldalon lévı példák.

Matematika I.


150

Oldjuk meg a következı egyenletrendszert: x1 − 2 x2 + x3 = 2

3 x1 + 8 x2 − 6 x3 = −5 6 x1 + 10 x2 + 3 x3 = 4 Az egyenletrendszer determinánsa: 1 −2 1 D = 3 8 − 6 = 24 + 72 + 30 − 48 +18 + 60 = 156 6 10 3 Számoljuk most ki a Di determinánsok értékeit:

2 −2 1 D1 = − 5 8 − 6 = 104 4 10 3 Matematika I.

1 2 1 D2 = 3 − 5 − 6 = −39 6 4 3 Felsıfokú Szakképzés

D3 = 130

151

Ezért az egyenletrendszer megoldása:

D1 104 2 x1 = = = D 156 3 D2 − 39 1 x2 = = =− D 156 4 D 3 130 5 x3 = = = D 156 6 Az értékek visszahelyettesítésével helyességét! Matematika I.

ellenırizzük a megoldás


152

A determináns fogalmának általánosítása n-ed rendő determinánsnak nevezzük azt az n2 elembıl álló, n sorba és n oszlopba rendezett táblázatot, amelynek értékét a következıképpen számítjuk ki: a11 a12 K a1n

a21

a22 K a2 n

M an1

M O M an 2 K ann

n

= ∑ (−1)i + j aij Aij j =1

ahol Aij az aij elemhez tartozó (n-1)-ed rendő aldetermináns. Megjegyzés: a fenti kifejtést az aldeterminánsokon addig folytatjuk, amíg másodrendő aldeterminánsokhoz nem jutunk. (Rekurzív definíció) Matematika I.


153

Az n-ed rendő determinánsokra érvényes tételek I. A determinánst bármely sora vagy oszlopa szerint kifejtve ugyanazt az eredményt kapjuk. A determináns értéke nem változik, ha elemeit a fıátlóra tükrözzük. (Következmény: a sorokra kimondott tételek érvényesek az oszlopokra is.) A determináns értéke elıjelet vált, ha két sorát megcseréljük. Ha a determináns két sora megegyezik, akkor a determináns értéke zérus. Ha a determináns valamely sora csupa zérus elemet tartalmaz, akkor a determináns értéke zérus. Ha egy determináns valamely sorának elemeit egy másik sorhoz tartozó aldeterminánsokkal szorozzuk, akkor a kapott szorzat értéke zérus Matematika I.


154

Az n-ed rendő determinánsokra érvényes tételek II. Ha a determináns fıátlója felett (alatt) csupa zérus elem áll, akkor a determináns értékét a fıátlóbeli elemek szorzatából megkaphatjuk. Ha egy determináns egy sorában minden elem felbontható két elem összegére, akkor a determináns felírható két determináns összegeként. Ha a determináns egy sorának minden elemét megszorozzuk egy k konstanssal, akkor a determináns értéke k-szorosára növekszik. (Következmény: ha a determináns egyik sora egy másik sor többszöröse, akkor a determináns értéke zérus.) A determináns értéke nem változik, ha valamely sorához egy másik sorának konstansszorosát hozzáadjuk. Matematika I.


155

Határozzuk meg az alábbi determináns értékét:

4

8

12

1

2

3

1

2

3

8

20

24 = 4 8

20

24 = 4 ⋅ 4 2

5

6 =

12

32

36

32

36

32 36

3

2

12

12

3

16 6 5 6 =0 3 36 32 36

Matematika I.


156


100

101 102

101 102 103 102 103 104 103 104 105

103

100

1 2

104 101 1 2 = 105 102 1 2 106 103 1 2

3 3 =0 3 3


1

0

0 0 0

1 0 0 1 0 105

Matematika I.

0

0 0 =1 0 1 Felsıfokú Szakképzés

157

Mátrixok Mátrixnak nevezünk n×m darab téglalap alakban elrendezett valós számot. Jelölése A(n,m) vagy An×m, ahol n×m a mátrix típusa, n a mátrix sorainak, m a mátrix oszlopainak száma.

 a11 a12   a21 a22 An×m =  M M  a a  n1 n2

K a1m   K a2m  O M   K anm 

A mátrixban található aij számok a mátrix elemei, ahol i-t sorindexnek, j-t oszlopindexnek nevezzük. Matematika I.


158

Két mátrix akkor és csak akkor egyenlı, ha azonos típusúak, és az azonos helyen álló elemeik megegyeznek. Azaz A = (aij)n×m és B = (bij)p×q esetén A = B, ha n = p és m = q, továbbá aij = bij minden i,j párra, ahol 1 ≤ i ≤ n, 1 ≤ j ≤ m. Speciális mátrixok: négyzetes (kvadratikus) mátrix: n = m. sormátrix: n = 1. oszlopmátrix: m = 1. zérusmátrix: aij = 0, minden i,j párra. egységmátrix: aii = 1 és aij = 0, ha i ≠ j. szimmetrikus mátrix: aij = aji antiszimmetrikus mátrix: aij = -aji , ha i ≠ j, és aii = 0 Az utolsó három definíció csak négyzetes mátrixokra érvényes! Matematika I.


159

Mőveletek mátrixokkal Az A = (aij)n×m és B = (bij)n×m mátrixok összegén azt a C = (cij)n×m mátrixot értjük, amelyre cij = aij + bij. Összeadni csak azonos típusú mátrixokat lehet! Példa:

2  1

− 1 3   − 1 2 1  1  +   =  2 3   4 1 1  5

Matematika I.

1 3


4  4

160

Mátrixot egy λ skalárral úgy szorzunk, hogy a mátrix minden elemét szorozzuk a konstanssal. Ha A = (aij)n×m és λ egy valós szám, akkor C = (cij)n×m = λ A, ha cij = λ aij ∀ 1 ≤ i ≤ n, 1 ≤ j ≤ m . Példa:

 1 3  −1

2  3  =  3 − 3

6  9

Legyenek A1, A2, …, An azonos típusú mátrixok, és legyenek adottak a k1, k2,…kn konstansok. Ekkor a L = k 1 A1 + k 2 A2 + ... + k n An =

n

∑k A i

i

i =1

kifejezést az A1, A2, …, An mátrixok lineáris kombinációjának nevezzük. Matematika I.


161

Az A = (aij)n×m és B = (bij)p×q mátrixokat – ebben a sorrendben – konformábilisnek nevezünk, ha m = p. Az A = (aij)n×m és B = (bij)m×l mátrixok szorzatán azt a C = (cij)n×l mátrixot értjük, amelyre m

cij = ai1b1 j + ai 2 b2 j + K + aim bmj = ∑ aik bkj k =1

Példa

 5 2   2 A ⋅ B =  − 1 1   3 1  1  

3 0

 12 15 − 1   =  − 1 − 3 2   9  7

− 1  3  − 1 

Tétel: A mátrixszorzás nem kommutatív, és nem zérusosztó-mentes, de asszociatív és az összeadásra nézve disztributív. Matematika I.


162

Az A = (aij)n×m mátrix transzponáltján azt az Az A* = (aji)*m×n mátrixot értjük, amelyre aij = a*ji Példa:

 2 4 1  A =   5 1 3

 2 5   ∗ A =  4 1  1 3  

Egy négyzetes A mátrix determinánsán a mátrix elemeibıl képzett determinánst értjük. Jelölése: |A| vagy det A. Az A mátrixot regulárisnak nevezzük, ha det A ≠ 0. Az A mátrixot szingulárisnak nevezzük, ha det A = 0

Matematika I.


163

Az En×n mátrixot egységmátrixnak nevezzük, ha eii = 1, és eij = 0, ha i ≠ j. Egy A = (aij)n×n négyzetes mátrix inverzén azt a A-1 = (aij)-1n×n mátrixot értjük, amelyre igaz, hogy

AA−1 = A−1 A = E

Példa:

 1 2 −1   A =  2 1 − 3  1 −1 1   

2  9 5 −1  A = 9 1  3

1 9 2 − 9 1 − 3

5   9  1 − 9 1   3 

A mátrixszorzás segítségével ellenırizzük a számítás helyességét! Matematika I.


164

Tétel: Legyen A invertálható mátrix, az inverzét jelölje B=(bij). Ekkor fennáll, hogy (−1)i + j det Aji bij = . det A ahol Aji az A mátrix aji eleméhez tartozó adjungált aldetermináns. Példa: Számítsuk ki az A mátrix inverzét, ha 2 1 1    A =  1 − 1 − 1 1 1 2   

2

1

1

det A = 1 − 1 − 1 = −3 1

1

2

(−1)1+1 det A11 −1 1 (−1)1+ 2 det A21 − 1⋅1 1 b12 = = = = = b11 = det A −3 3 −3 3 det A (−1)1+3 det A31 0 = =0 b13 = −3 det A Matematika I.


165

(−1)2+1 det A12 − 3 b21 = = =1 det A −3 (−1) 2+ 2 det A22 3 b22 = = = −1 det A −3

(−1)3+1 det A13 2 2 b31 = = =− det A −3 3 (−1) 3+ 2 det A23 − 1 1 b32 = = = det A −3 3

(−1) 2+3 det A32 3 b23 = = =1 det A −3

( −1) 3+ 3 det A33 − 3 b33 = = =1 det A −3

 1   3 B= 1 − 2  3 

2 1 1    A =  1 −1 −1 1 1 2   

Matematika I.

1  0 3  − 1 − 1 1 1  3 


166

 1   3 B= 1 − 2  3 

2 1 1    A =  1 −1 −1 1 1 2   

2  AB =  1 1 

Matematika I.

1 −1 1

 1 1   3 − 1  1 2 2  −  3

1 3 −1 1 3

1  0 3  − 1 − 1 1 1  3 

 0  1   − 1 =  0 1   0 


0 1 0

0  0 1 

167

Lineáris egyenletrendszerek

Legyen Amxn egy mátrix, b1, b2, …, bm pedig skalárok. Lineáris egyenletrendszernek nevezzük az alábbi egyenletrendszert a11 x1 + a12 x2 + K + a1n xn = b1 a21 x1 + a22 x2 + K + a2 n xn = b2

L am1 x1 + am 2 x2 + K + amn xn = bm

Az n számot az ismeretlenek számának, míg m-et az egyenletek számának nevezzük.

Matematika I.


168

Bevezetve az ismeretlenekbıl és a jobb oldali skalárokból képezett  x1   b1       x2  b2  X =  B=  M M     x  b   n  n oszlopmátrixokat (oszlopvektorokat), a lineáris egyenletrendszert rövidített (mátrix alakban megadott) formában is felírhatjuk: AX = B A lineáris egyenletrendszerhez tartozó alapmátrix az A mátrix, míg az un. bıvített alapmátrix:  a11 a12 L a1n b1     a21 a22 L a2 n b2   M M   a  a L a b mn m  m1 m 2 Matematika I.


169

Ha a b1, b2, … , bm skalárok mindegyike zéró, akkor homogén lineáris egyenletrendszerrıl beszélünk, míg ellenkezı esetben inhomogén lineáris egyenletrendszerrıl. A (ξ1, ξ2, … , ξn) vektort a lineáris egyenletrendszer megoldásának nevezzük, ha a11ξ1 + a12ξ 2 + K + a1nξ n = b1 a 21ξ1 + a 22ξ 2 + K + a 2 nξ n = b2 L a m1ξ1 + a m 2ξ 2 + K + a mnξ n = bm

teljesül. Triviális megoldás alatt a csupa zérusból álló megoldást értjük. Az ettıl eltérı megoldást nemtriviális megoldásnak nevezzük. Matematika I.


170

Tétel: A homogén lineáris egyenletrendszernek mindig van megoldása, hiszen a triviális megoldás egy ilyen rendszernek megoldása. A Cramer szabály állítása igaz n ismeretlenes egyenletrendszer esetén is. Tétel(Cramer szabály): Ha az egyenletrendszer determinánsa nem 0, akkor az egyenletrendszernek pontosan egy megoldása van. Az i-dik ismeretlen értéke egy olyan törttel egyenlı, amelynek nevezıje a rendszer determinánsa, számlálója pedig Di:

Di xi = , D

Matematika I.

i = 1,2, K, n.


171

Lineáris egyenletrenszerek numerikus megoldása Gauss elimináció

a11x1 + a12x2

+ …

+ a1nxn

a21x1 + a22x2

+

+ a2nxn = a2n+1

…

= a1n+1

………………………………………………… an1x1 + an2x2

+ …

+ annxn

= ann+1 ahol ain+1=bi

Az eljárás lényege: Olyan egyenletrendszer kialakítása, amelynek együttható mátrixa háromszög alakú. Matematika I.


172

Az algoritmus:

a11(0)x1+ a12(0)x2 + …

+ a1n(0)xn = a(0)1n+1

a21(0)x1 + a22(0)x2 +

+ a2n(0)xn = a(0)2n+1

…

………………………………………………… an1(0)x1+ an2(0)x2 + …

+ ann(0)xn = a(0)nn+1

1. Minden 1 és n-1 közé esı i-re végezzük el a következıket: 2. Jelöljük sj(i-1)-vel az egyenletrendszer j. sorát az i. lépésben. Tegyük fel, hogy aii(i-1)≠0. Legyen qj(i-1)=aji(i-1)/aii(i-1). 3. Legyen sj(i) = sj(i-1) –qj(i-1)si(i-1) minden j>i-re. Matematika I.


173

A számítások befejezése után a következı feladatot kapjuk: a11(0)x1 + a12(0)x2 + … a22(1)x2 +

…

+

a1n(0)xn =

a1n+1(0)

+

a2n(1)xn =

a2n+1(1)

………………………………………………… ann(n-1)xn =

ann+1(n-1)

Amibıl a megoldás:

a xj = Matematika I.

( j −1 ) jn + 1

− a

n

∑

a (jt j − 1 ) x t

t= j+1 ( j −1 ) jj

,


j = n , ( n − 1 ), K ,1

174

Határozzuk meg a következı egyenletrendszer megoldását! 2x1+3x2-x3=9 x1+2x2+x3 =4 x1-x2-2x3 =1 q2(0)=1/2 q3(0)=1/2 A megoldás: x3 = - 1 Matematika I.

2x1 +3x2 -

x= 9

3

1 3 1 x2 + x3 = 2 2 2 5 3 7 - x2 - x3 = − 2 2 2

2x1 +3x2 -

x= 9

3

1 3 1 x2 + x3 = 2 2 2 6x3 = −6

q3(1)= -5 1 3 − + 2 2 = 2 x2 = 1 2 Felsıfokú Szakképzés

9 −(6 + 1) x1 = =1 2 175

Mekkora a mőveletigény (osztások és a szorzások száma) ? Az algoritmusból adódik, hogy minden j-re (n-j) osztást és (n-j)(nj+1) szorzást kell elvégezni. Ezért: n −1

∑ [(n − j )(n −

j + 1 ) + (n − j )] =

j=1

=

∑ (n − j ) j=1

(n − 1 ) n (2 n − 1 ) + n (n − 1 ) = 6

n −1

2

n −1

+ 2 ∑ (n − j ) j=1

2 n 3 + 3n 2 − 5n 6

A visszahelyettesítés mőveletigénye n osztás és n(n-1)/2 szorzás. Ezért az összes mővelet:

2n3 + 3n 2 − 5n n 2 + n n3 + 3n 2 − n 1 3 2 + = = n + O(n ) 6 2 3 3 Matematika I.


176

Gauss elimináció fıelem kiválasztással 1. Minden 1 és n-1 közé esı i-re végezzük el a következıket: 2. Legyen a kj( j − 1 ) = max a lj( n − 1 ) j≤l≤ n

3. Ha k ≠ j, akkor cseréljük meg a k. sort a j. sorral. 4. Folytassuk az eljárást, a Gauss-elimináció (2) és (3) lépésével.

Matematika I.


177

Tétel: Ha a lineáris egyenletrendszer A mátrixa nem szinguláris, akkor a fenti eljárással kiválasztott (0 ) (1) (2) ( n −1 ) a11 , a 22 , a 33 ,K , a nn elemek egyike sem lehet zérus.

Biz.: Mivel az A mátrix nem szinguláris, ezért det(A)≠ 0. A fıelemkiválasztásos Gauss módszer végén fejtsük ki a „kiháromszögelt” mátrixot a fıátlóba esı elemek szerint: (1 ) ( 2 ) ( n −1 ) det( A ) = ± a 11( 0 ) a 22 a 33 K a nn ≠0

Attól függıen, hogy páros vagy páratlan számú sorcserét hajtottunk végre. Matematika I.


178

Határozzuk meg a az elızı egyenletrendszer megoldását a fıelem kiválasztásának módszerével!

2x1+3x2-x3=9 x1+2x2+x3 =4 x1-x2-2x3 =1 q2(0)=1/2 q3(0)=1/2

Matematika I.

2x1 + 3x2 -

x3 =

9

1 3 1 x2 + x3 = 2 2 2 5 3 7 - x2 - x3 = − 2 2 2

2x1 + 3x2 -

x3 =

9

5 3 7 - x2 - x3 = − 2 2 2 12 12 x3 = 10 10 Felsıfokú Szakképzés

2x1 + 3x2 -

x3 =

9

5 3 7 - x2 - x3 = − 2 2 2 1 3 1 x2 + x3 = 2 2 2

q3(1)= 1/5

x3=-1, x2=2, x1=1 179

Gauss elimináció teljes fıelem kiválasztással

Az elızı módszert szokás részleges fıelem kiválasztásnak nevezni.

Teljes fıelem kiválasztásnál az együttható mátrix „maradék” részének legnagyobb abszolút értékő elemét sor- és oszlopcserékkel a mátrix diagonális elemének helyére visszük. Azaz a j. lépésben legyen

a (pqj −1 ) = max { a ik( j − 1 ) : j ≤ i , k ≤ n } Matematika I.


180

pj=j (j=1,2,…,n)

j=1

a (pqj )meghatározása a (pqj ) =0

Hibajelzés

t=pj pj=pq a ij( j ) = a ij( j ) / a (jj j ) a ik( j ) = a ik(j) - a ij(j) a ij(j)

pq=t

(i=j+1,…,n) (i=j+1,..,n k=j+1,…,n+1) j=j+1

a (jnj+−11 ) − xpj = Matematika I.

j ≤ n-1

n

( j −1 ) a ∑ jt x pt

t = j +1 ( j −1 ) jj

a

, j = n ,( n − 1 ),K ,1 Felsıfokú Szakképzés

VÉGE 181

Határozzuk meg az elızı egyenletrendszer megoldását a fıelem kiválasztásának módszerével!

2x1+3x2-x3=9

3x2+2x1-x3=9

x1+2x2+x3 =4

2x2+x1+x3 =4

x1-x2-2x3 =1

-x2+x1-2x3 =1

p = (1,2,3)

p = (2,1,3)

3x2 + 2x1 -

x3 = 9

1 5 - x1 + x3 = - 2 3 3 5 7 x1 - x3 = 4 3 3

q2(0)=2/3 q3(0)=-1/3 Matematika I.


182

3x2 - x3 + 2x1 = 9 7 1 - x3 − x1 = 4 3 3 5 1 x3 − x1 = −2 3 3

3x2 - x3 +

2x1 = 9

7 1 - x3 − x1 = 4 3 3 18 18 x1 = 21 21

p = (2,3,1) q3(1)= -5/7

x1=1, x3=-1, x2=2

Figyeljük meg az indexeket és permutáció vektor viszonyát! Matematika I.


183

Gauss-Jordan elimináció

a11x1 + a12x2

+ …

+ a1nxn

a21x1 + a22x2

+

+ a2nxn = a2n+1

…

= a1n+1

………………………………………………… an1x1 + an2x2

+ …

+ annxn

= ann+1 ahol ain+1=bi

Az eljárás lényege: Ekvivalens átalakításokkal olyan egyenletrendszer kialakítása, amelynek együttható mátrixa egységmátrix. Matematika I.


184

a11(0)x1+ a12(0)x2 + …

+ a1n(0)xn = a(0)1n+1

a21(0)x1 + a22(0)x2 + … + a2n(0)xn = a(0)2n+1 ………………………………………………… an1(0)x1+ an2(0)x2 + … + ann(0)xn = a(0)nn+1 1. Minden 1 és n-1 közé esı i-re végezzük el a következıt: 2. Legyen sj(i-1) az egyenletrendszer j. sora az i. lépésben. Tegyük fel, hogy aii(i-1)≠0. 3. Legyen si(i)= si(i-1)/aii(i-1), és sj(i) = sj(i-1) – aij(i)si(i) minden j≠i-re. Matematika I.


185

(0)x + a11(0)x1+ a12(1) … 2

(0)x (1) (0) + a1n(1) n = a 1n+1

(0)x (1) (1) (0) (0)x + a21(0)x1 + a22(1) … a a + = 2n n 2n+1 2 ………………………………………………… (1)x (1) (0) (0)x + an1(0)x1+ an2(1) … + ann(0) n = a nn+1 2

s1(1)=s1(0)/a11(0), sj(1) = sj(0) – a11(1)s1(1) minden j ≠ i-re.

Matematika I.


j=2, …,n

186

Az i. lépésben:

x1 + + a1i(0)x2 + … +a1n(0)xn = a(0)1n+1 ………………………………………………… aii(0)x2 + … + a2n(0)xn = a(0)2n+1 ………………………………………………… an2(0)x2 + … + ann(1)xn = a(0)nn+1 s1(1)=s1(0)/a11(0), sj(1) = sj(0) – a11(1)s1(1) minden j ≠ i-re. j=2 ,…, n

Matematika I.


187

Határozzuk meg az elızı egyenletrendszer megoldását a fıelem kiválasztásának módszerével! 2x1+3x2-x3=9 x1+2x2+x3 =4

2 1

x1-x2-2x3 =1

1

1 0 0

3 2 1 2 5 − 2

Matematika I.

1 − 2 3 2 3 − 2

9 2 − −

1 2 7 2

=

−1 9 1 4 −1 − 2 1 3 2

1 0 −5 0 1 3 0 0


6

6 − 1 − 6

=

=

188

1 0 −5 6 0 1 3 − 1 0 0 6 − 6

Amibıl a megoldás:

Matematika I.

=

1 0 0 0 1 0 0 0 1

1 2 − 1

x3 = - 1 x2 = 2 x1 = 1


189

Mátrix invertálása Gauss-Jordan eliminációval Az elızıekben leírt módszer egyszerő gyakorlati módszert ad mátrixok invertálhatóságának eldöntésére és az inverzmátrix meghatározására. Megjegyzés. (Mátrix invertálása szimultán Gauss eliminációval.) Legyen adva egy négyzetes mátrix, melyet Gauss eliminációval egységmátrixszá alakítottunk: E k E k −1 K E1 A = I

A mátrix tehát invertálható és inverze:

A −1 = E k E k −1 K E1 = E k E k −1 K E1 I

Ez azt jelenti, hogy ha az A mátrixot Gauss eliminációval, azaz elemi sorátalakításokkal egységmátrixszá alakítjuk, s ugyanezeket az elemi sorátalakításokat végrehajtjuk az egységmátrixon, a végeredmény A inverze lesz. Tehát az eliminációt egyszerre, szimultán hajtjuk végre a két mátrixon, de az elemi sorátalakításokat az A határozza meg, az egységmátrix csak ”elszenvedi”. Matematika I.


190

(A módszer végrehajtásakor természetesen nem kell az elemi mátrixokat felírni, azoknak csak a bizonyításnál van szerepük.) Gyakorlatilag leírjuk egymás mellé az invertálandó mátrixot (bal oldal) és az egységmátrixot (jobb oldal), majd 1. Gauss eliminációval lépcsıs alakúra hozzuk ezt a „hosszú” mátrixot. Ha a baloldali négyzetes mátrix nem tartalmaz csupa zéróból álló sort (háromszög alakú és a fıátlóban nincs zérus), akkor a mátrix invertálható, s az eljárást folytatjuk. 2. Elemi sorátalakításokkal alulról fölfelé haladva elérjük, hogy a baloldalon egységmátrix legyen. A jobb oldalon az inverzmátrix van.

Matematika I.


191

Határozzuk meg a következı mátrix inverzét! 1 1 1 1 2 2 2 1 2

1 0 0 0 1 0 0 0 1

2 −1 0 0 1 1 −1 1 0 0 0 1 −3 1 1

=

Ellenırzés:

1 1 1 1 2 2 2 1 2

Matematika I.

1 1

1 1 0 0 1 −1 1 0 0 −1 0 − 2 0 1

=

1 0 0 2 −1 0 0 1 0 2 0 −1 0 0 1 −3 1 1

1 0 0

=

1 0

=

×

2 2 −3

−1 0 0 −1 1


1

1 0 0

=

0 1 0 0 0 1 192

Megoldható, hogy a kombinatórika a gyakorlat anyaga legyen?? Javaslat: Kezdjük a félév gyakorlatát a kombinatórikával. Ez elegendı idıt ad az elıadásnak ahhoz, hogy elıre haladjon!

Matematika I.


193

Gráfelmélet alapjai Legyen V elemeknek egy véges halmaza, és E a V elemeibıl képezett rendezett párok – esetleg üres – halmaza. Gráfnak nevezzük a V és E által meghatározott struktúrát. Jelölése: G(V,E) V(G) ≔ A G csúcshalmaza

v1

v3

e1 e5 v2

e3 e2

v4 e4 v5

E(G) ≔ A G élhalmaza

• e1 = {v1,v4} összeköti a v1 és v4 csúcsokat • v3 és v2 szomszédos csúcsok, • e2 és e4 szomszédos élek, • e4 és v5 illeszkednek.

Idınként a v1v2 jelölést fogjuk használni a {v1,v2} helyett. Matematika I.


194

V(G) elemeinek a számát a gráf rendjének nevezzük. Jelölése: n(G). E(G) elemeinek a számát a gráf méretének nevezzük. Jelölése: m(G). Az n-ed rendő, m mérető gráfot G(n,m) vagy Gn,m jelöli. Legyen a G gráf csúcshalmaz V(G) = {v1, v2, … , vn} és élhalmaza E(G) = {e1, e2, … , em}. A gráf leírható mátrixokkal. A szomszédsági mátrix A(G) = [aij]nxn ahol 1 ha vivj ∊ E(G) aij = 0 ha vivj ∉ E(G)

{

Az illeszkedési mátrix B(G) = [bij]nxm ahol bij = Matematika I.

{

1 ha vi és ej illeszkedik 0 különben. Felsıfokú Szakképzés

195

e1

v1 e3

e2

v1 v2 v3 v4

0 1 A= 1  0

1 1 0 0 1 1  1 0 1  1 1 0

e4 e5

v3

v1 v2 v3 v4

v2

v4

  B =    

e1 e2 e3 e4 e5

1 1 0 0 0  1 0 1 1 0  0 1 1 0 1   0 0 0 1 1 

v1 v2 v3 v4

Egy gráf, és a hozzá tatozó szomszédsági és illeszkedési mátrixok Matematika I.


196

Csúcsok fokszáma Egy G gráf v csúcsának fokszámán a csúcshoz illeszkedı élek számát értjük. Jelölése: degG v vagy deg v. Jelılje a v csúccsal szomszédos csúcsok halmazát Γ(v). degGv=|Γ(v)|. Egy csúcsot párosnak vagy páratlannak nevezzük attól függıen, hogy a fokszáma páros vagy páratlan. Egy csúcsot izoláltnak nevezünk, ha deg v = 0, és vég-csúcsnak, ha deg v = 1.

δ(G) = min degG v a G gráf minimális fokszáma. v∊ G

∆(G) = max degG v a G gráf maximális fokszáma. v∊ G

Matematika I.


197

2

v1

5

v6

3

v7

1

v8

2 v5 2

3 v2

degG v2 = 3

2

4 v4

v3

v9

degG v4 = 4

δ(G) = degG v8 = 1

degG v9 = 2 ∆(G) = degG v6 = 5

Csúcsfokszámok egy gráfban Matematika I.


198

Tétel (“Kézfogási“ Lemma): Tekintsük a G(n,m) gráfot, ahol V(G) = {v1, v2, …, vn}. Ekkor n

∑ degG vi = 2m i=1 Biz.: Az állítás azonnal következik abból a ténybıl, hogy minden él két csúcsra illeszkedik. Következmény: Bármely gráfban a páratlan csúcsok száma mindig páros.

Matematika I.


199

Részgráfok és indukált részgráfok Azt a gráfot, amelynek nincsenek élei üres gráfnak nevezzük. A H gráf a G gráf részgráfja, ha V(H)⊆ V(G) és E(H)⊆ E(G). Legyen v∊V(G) és |V(G)| ≥ 2. A H = G – v gráf a v csúcs törlésével áll elı G-bıl, ha V(H) = V(G) – {v} és E(H) a G azon éleit tartalmazza, amelyek nem illeszkednek v-re. Ha e∊ E(G), akkor H = G – e (egy él kitörlése) G-nek egy olyan részgráfja, amelyre V(H) = V(G) és E(H) = E(G) – {ve}. Matematika I.


200

v

e

G

Matematika I.

G–v


G–e

201

Ha u és v a G nem szomszédos csúcsai, akkor G + f, ahol f = uv, jelöli azt a gráfot, amelynek csúcshalmaza V(G) és élhalmaza E(G) ∪ { f }. Ezért G ⊆ G + f. Ha G egy H részgráfjának rendje megegyezik G rendjével, akkor Ht G feszítı részgráfjának nevezzük. Ha U a V(G) egy részhalmaz, akkor 〈U 〉 a G-nek egy olyan U által indukált gráfja, amely csúcshalmaza U ⊆ V(G) és élhalmaza minden olyan élet tartalmaz G-bıl, amely illeszkedik az U két elemére.

Matematika I.


202

Speciális gráfok Egy G gráfot r-reguláris gráfnak nevezünk, ha deg v = r a G gráf minden v csúcsára. Egy gráf teljes, ha bármely két csúcsa szomszédos.

Ha G = G(m,n), akkor G (n-1)-reguláris, és m = n(n-1)/2. Jelölése: Kn.

4-reguláris gráfok. Matematika I.


203

A Petersen gráf Matematika I.


204

Egy G gráf komplemens gráfján azt a G gráfot értjük, amelyre V(G )= V(G) u,v∊V(G), uv∊ E(G ) akkor és csak akkor, ha uv ∉ E(G). Állítás-1: Ha G = G(m,n), akkor G egy olyan n-ed rendő gráf, amelynek mérete: n m =   − m 2 Állítás- 2: A Kn teljes gráf komplemens gráfja ( K n ) az n-ed rendő üres.

Matematika I.


205

Egy G gráfot k-részesnek mondunk, k ≥ 1, ha a V(G) csúcspontjainak halmaza úgy particionálható k részhalmazra (V1,V2,…,Vk), hogy E(G) elemei Vi és Vj -beli csúcsokat kötnek össze, ahol i ≠ j. Ha k = 2, akkor a gráf kétrészes. Tétel: Ha G egy r-reguláris kétrészes gráf, r ≥ 1, akkor |V1| = |V2| . Egy teljes kétrészes gráfot, ahol |V1| = r és |V2| = s K(r,s)-el vagy Kr,sel jelöljük . (A K1,s gráfot csillagnak nevezzük).

Matematika I.


206

v1

v4

v5

v2

v3

v6

v1

v3

v5

v2

v4

v6

v7

v7

V1

V2

Egy kétrészes gráf két különbözı (izomorfikus) ábrázolása Matematika I.


207

Mőveletek gáfokon Két gráf egyesítésén (unióján) azt a G = G1 U G2 gráfot értjük, amelyre V(G) = V(G1) U V(G2) és E(G) = E(G1) U E(G2).

Példa: 3K1 U 2K3 U K2,2.

Matematika I.


208

Két gráf összekapcsolásán azt a G = G1+G2 gráfot értjük, amelyre V(G) = V(G1) U V(G2) és E(G) = E(G1) U E(G2) U{uv | u∊V(G1) és v ∊ V(G2)}.

Példa:

G1 Matematika I.

G2

G1+G2 Felsıfokú Szakképzés

209

Két gráf direkt szorzatán azt a G = G1 × G2 gráfot értjük, amelyre V(G) = V(G1) × V(G2) és két csúcs: (u1,u2) és (v1,v2) akkor és csak akkor szomszédos, ha vagy u1 = v1 és u2v2∊E(G2) vagy u2= v2 és u1v1∊E(G1) Példa: u1

(u1,u2) u2

w1 G1 Matematika I.

(u1,w2)

v2

v1

(u1,v2)

(v1,u2) w2

(v1,v2) (v1,w2) G = G1×G2

G2 Felsıfokú Szakképzés

210

Gráfok bejárása Legyen u és v a G gráf – nem szükségképpen különbözı – két csúcsa. Egy W-vel jelölt u–v séta a G gráfban a csúcspontoknak és az éleknek egy olyan W: u = u0,e1,u1,e2,u2,….,uk-1,ek,uk = v véges, alternáló sorozata, amely az u csúcsponttal kezdıdik, a v csúccsal végzıdik, és ei = ui-1ui mindig egy él, i=1,2,…,k. A k számot a W séta hosszának nevezzük. u1 u4 e1 e5 e4 e2 k=6 u e3 e6 u3 u2=u5 Matematika I.

u6=v


211

Egy u–v sétát zártnak vagy nyitottnak nevezünk attól függıen, hogy u = v vagy u ≠ v. A u-v ösvény az egy olyan u–v séta, amelyben él nem ismétlıdik, és egy u–v út az egy olyan u–v séta, amelyben csúcspont nem ismétlıdik. Következmény-1: minden út egyben ısvény is. Következmény-2: Minden út egyben séta is, de a megfordítottja általában nem igaz.

Matematika I.


212

Példa: v2 v4 v5

v3

v1

W : v1 , v 2 , v 3 , v 2 , v 5 , v 3 , v 4 T : v1 , v 2 , v 5 , v1 , v 3 , v 4 P : v1 , v 3 , v 2 , v 4

Matematika I.

egy v1-v4 séta de nem ösvény. egy ösvény de nem út. egy út.


213

Tétel: Ha A a G szomszédsági mátrixa, és V(G) = {v1,v2,…,vn}, akkor az Ak hatványmátrix (i,j) eleme, k ≥ 1, megadja a k hosszúságú vi-vj sétákat a G gráfban. Példa: 0  1 A= 1  0 

1 1 0  0 1 0 A  1 0 1  0 1 0  v2

v1 v3 v4 Matematika I.

2

   =    

2 1 1 1

1 2 1 1

1 1 3 0

1 1 0 1

      

2  3 3 A = 4  1 

3 4 1  2 4 1 4 2 3  1 3 0 

W1 : v1 , v3 , v1 , v3 W2 : v1 , v2 , v1 , v3 W3 : v1 , v3 , v2 , v3 W4 : v1 , v3 , v4 , v3 Felsıfokú Szakképzés

214

Egy nem triviális zárt ösvényt körútnak nevezünk, és azt a körutat, amelyben n különbözı csomópont szerepel, kırnek nevezzük. Egy aciklikus gráfban nincs kör. Egy kör páros, ha hossza páros, egyébként a kör páratlan. Egy k hosszúságú kört k-körnek nevezünk. A 3-kör a háromszög. Azt az n-ed rendő gráfot, amely út, Pn jelöli, és Cn egy n csúcspontú kört jelöl. Egy u csúcsról azt mondjuk, hogy összeköthetı a v csúccsal, a gráfban létezik egy u–v út. Egy gráf összefüggı, ha bármely két csúcsa összeköthetı. Egyébként a gráf nem összefüggı. Matematika I.


215

Tétel: Egy G gráf csúcshalmazán értelmezett „összefüggı” reláció egy ekvivalancia reláció. Biz.: Házi feladat Azokat a részgráfokat, amelyek az ekvivalencia reláció eredményeként létrejött ekvivalencia osztályoknak felelnek meg, a G gráf összefüggı komponensének nevezzük. A G gráf komponenseinek számát k(G) jelöli. Egy összefüggı gráfban az u és v csúcsok d(u,v) távolságán a két csúcspont között megadható u−v utak minimális hosszát értjük.

Matematika I.


216

0

v1

1

v6

2

v7

3

v8

2 v5 2

1 v2

2

3 v4

v3

v9 v1

v2

szint 0 szint 1

v6

v3

v5

v9

v4

v7

szint 2

v8

szint 3

Távolsági szintek a v1 csúcsból kiindulva. Matematika I.


217

A feszítı fa probléma Egy G gráf feszítı fáján azt a feszítı részgráfot értjük, amely fa. Tétel: Minden összefüggı fának van feszítı részgráfja Biz.: Konstrukcióval. Válasszunk egy tetszıleges x∊ V csúcspontot. Legyen Vi={ y ∊ G : d(x,y)= i, i=1,2,…,M }. Ha yi∊ Vi , i > 0 és x,z1,z2,…,zi-1,yi egy x – yi út, akkor d(x,zj)= j, 0 < j < i. Az világos, hogy Vj ≠ Ø, ha j < M, és bármely y ∊ Vi-hez, i ≤ M, létezik legalább egy y'∊ Vi-1, amely szomszédos y-nal. ({y',y} ∊ E(G)). Matematika I.


218

x

V0

…

V1

V2

VM-2

VM-1

VM

Következmény-1: A G(n,m) feszítıfája: T(n,n-1). Matematika I.


219

Az optimalizáció-elmélet egyik ismert problémája az, hogy hogyan lehet megtalálni egy gráf valamilyen speciális tulajdonsággal rendelkezı feszítı fáját. Legyen adott a G=(V,E) gráf és egy pozitív értékő f függvény, amely + a gráf élein van definiálva: f: E→ℝ . Keressük azt a T=(V,E΄) összefüggı feszítı fát, amelyre f (T ) = ∑ f ( xy ) , minimális. xy ∈ E Az ilyen tulajdonságú feszítı részfát gazdaságos feszítı fának nevezzük.

Matematika I.


220

Egy valós probléma: Egy adott régióban falvakat akarunk összekötni vízvezetékkel. Ismerjük, hogy mennyibe kerül az egyes flvak közötti vezetékek felépítése. Keressük meg azt a hálózatot, mely a legkevesebb költséggel építhetı fel! Példa:

1

3

2

4 3 3

2

4

5 1 3

Matematika I.

4

2


221

Kruskal Algoritmus (1956): Válasszuk ki a legolcsóbb élet G-bıl, azaz azt az élet, amelyre f(e) minimális. A következı élet a még ki nem választottak közül mindig úgy választjuk, hogy az a legolcsóbb legyen. A választásnál arra kell ügyelnünk, hogy nem képezhetünk körutat a kiválasztott élekbıl. Ha ilyen él már nincs, akkor véget ér az algoritmus. 1 3

2

4 3 3

2

4

5

f(T1)=15

1 3

Matematika I.

4

2


222

2. Algoritmus: Az algoritmus lényege az, hogy drága élet csak akkor szabad választani, ha biztosítani akarjuk a gráf összefüggıségét. Töröljük tehát a legdrágább élet a gráfból mindaddig, amíg a gráf összefüggı marad. Ha ilyen él már nincs, akkor véget ér az algoritmus. 1 3

2

4 3 3

2

4

5

f(T2)=15

1 3

Matematika I.

4

2


223

A legrövidebb út problémája Rendeljünk a G gráf minden (u,v )∊ E(G) éléhez egy w(u,v) függvényt, és nevezzük ezt súlynak. Azt a gráfot, amelynek élei súlyozva vannak, súlyozott gráfnak nevezzük. Legyen w: E(G)→ℝ+ egy függvény. Terjesszük ki a függvény definícióját egy gráf H ⊆ G részgráfjára: w( H ) = ∑e∈E ( H ) w(e).

Számos olyan optimalizációs probléma létezik, amely egy súlyozott gráfban keres egy olyan részgráfot, amely valamilyen tulajdonság szerint minimális (vagy maximális). Matematika I.


224

A legrövidebb út problémája: adott egy súlyozott gráf, (vasút hálózat). Határozzuk meg a legrövidebb utat a gráf – elıre adott – két csúcspontja (városa) között. Ebben a környezetben az út hosszán a út által reprezentált részgráf súlyát fogjuk érteni. The Dijkstra algorithm (1959) Tegyük fel, hogy az u0 és a v0 csúcsok közötti út hosszát akarjuk meghatározni: Az algoritmus egy fokozatosan növekvı Si halmazt készít, ahol 0 ≤ i ≤ n – 1, és {u0} ⊆ Si ⊆ V(G). Minden lépésben egy cimkét rendelünk a csúcspontokhoz: l:(G)→ℝ∪{∞} úgy, hogy a v ∊ S csúcshoz tartozó l(v) címke a v csúcs távolságát adja meg az u0 csúcstól az 〈S 〉 indukált részgráfban. Matematika I.


225

Elıkészítı lépés: i = 0,

S 0 = { u0 },

ha v = u0 0,  l(v) =  w(u0, v), ha u0 ≠ v és (u0, v)∈E(G)  ∞ különben 

Iterációs lépés: Ha Si = V(G) akkor az algoritmus befejezıdik. Ha Si ≠ V(G) akkor W = { vi | vi ∈ Si , l( vi ) = minv∈Si l( v )} és legyen ui+1 a W egy tetszıleges csúcspontja. Ha l(ui+1) = ∞ vagy ui+1 = v0 akkor az algoritmus megáll. Ha l (ui+1) < ∞ akkor Si+1 = Si U {ui+1}, és legyen

l ( z) = min{l ( z), l (ui +1 ) + w (ui +1 , z) | (ui +1, z) ∈ E(G), z ∈ Si +1} i=i+1. Matematika I.


226

Mi a Dijkstra's Algoritmus bonyolultsága? n-ben polinomiális: O(n2). Példa: v2

2 2

1 u0

7

Step l(u0) l(v1)l(v2) l(v3) l(v0)

v3 4 v1

Si

0

0

7

1

2

∞ u0

1 1

1

0

7

1

2

2 u0 v2

3

2

0

5

1

2

2 u0 v2 v0

3

0

5

1

2

2 u0 v2 v0 v3

4

0

5

1

2

2 u0 v2 v0 v3 v1

v0

ui +1 = { vi | vi ∈ Si , l( vi ) = minv∈Si l( v )} l( z ) = min{ l( z ), l( ui +1 ) + w ( ui +1 , z ) | ( ui +1 , z ) ∈ E( G ), z ∈ Si +1 } Matematika I.


227

Euler gráfok Egy olyan körutat a G gráfban, amely tartalmazza a G összes élét Euler körnek mondjuk. Egy Euler ösvény tartalmazza az összes élet, de nem zárt. Egy gráf Euler gráf, ha benne létezik Euler-kör. Egy G gráfot párosnak (páratlannak) mondunk, ha minden csúcsa páros (páratlan). Tétel : Egy összefüggı gráfban akkor és csak akkor van Euler-körút, ha a gráf minden csúcsa páros. Matematika I.


228

Matematika I.


229

Definiáljuk a következı sorozatot: a sorozatban egy bető azt a szárazföldet jelenti, amelyhez az út során elérkeztünk, és két egymás utáni elem azt a hidat jelenti, amelyen át kell kelni útban az egyik területrıl a másikra. Ha ilyen út létezne, akkor az leírható lenne 8 betővel, amelyek mindegyikét az A, B, C és D betőkbıl választjuk Mivel minden hídon pontosan egyszer szabad átmenni, ezért az A és B betők ebben a sorozatban kétszer fordulnak úgy elı, hogy ık egymást követik. Ugyanez a helyzet az A és C betőpárral is. Mivel öt híd vezet az A által jelölt területre, ezért A-nak a jó megoldásban háromszor kell megjelenni. (Két pár jelöl egy-egy belépést és kilépést az A területre, egy pedig vagy kilépést vagy belépést A-ra.) Hasonló megfontolásból, B, C és D kétszer jelenik meg a sorozatban. Ezért legalább 9 betőbıl kell állni a sorozatnak. Ez pedig lehetetlen. Matematika I.


230

C

A

D

B

The seven bridges on the Pregel in Königsberg Matematika I.


231

Hamilton utak Az utazó ügynök problémája: egy utazóügynök n várost akar meglátogatni úgy, hogy az út végén visszaérjen a központi irodába. Bármely két város közötti utazás költsége ismert. Keressünk egy hatékony algoritmust, amely megtalálja a legolcsóbb utat. Mit jelent a „hatékony algoritmus”? A válasz meglepı: nem ismert az, hogy létezik-e hatékony algoritmus a probléma megoldására. Variáns: Ha az úttól azt követeljük meg, hogy körút legyen, azaz nincs megengedve az, hogy az utazás alatt ugyanazt a várost kétszer is érintse. Matematika I.


232

Azt a körutat, amely tartalmazza a problémához tartozó gráf minden csúcspontját, Hamilton körnek nevezzük. Azt a gráfot, amelynek van Hamilton köre, Hamilton gráfnak nevezzük. Az elnevezés onnan ered, hogy Sir William Rowan Hamilton 1857ben konstruált egy játékot, amely során a feladat az volt, hogy miként lehet a dodekaéder csúcsaiba vert szögeken végigvezetni egy madzagot úgy, hogy minden csúcsot csak egyszer érintünk. Ez volt 19. század “Rubik kockája “. 1855-ben Thomas P. Kirkman következı kérdést tette fel: Legyen adott egy poliéderhez tartozó gráf. Lehet-e mindig konstruálni egy olyan körutat, amely minden csúcspontot egyszer és csak egyszer érint? Matematika I.


233

A dodekaéder gráfja Matematika I.


234

Hamilton köröket (és Hamilton utakat) már korábban is vizsgáltak. 1759-ben Euler tanulmányozta azt a problémát, hogy lehetséges-e a huszárral bejárni a sakktábla mind a 64 mezıjét úgy, hogy minden mezıt érintünk, egyikre sem lépünk kétszer, és a végén vissza jutunk a kiindulópontra.

Matematika I.


235

A gazdaságos Hamilton kör meghatározásánál lényegesen egyszerőbb az a feladat, hogy létezik-e Hamilton kör a gráfban? Erre a kérdésre sincs jó válasz. Van-e olyan feltétel, amely alapján eldönthetı, hogy egy gráf Hamilton-gráf-e vagy sem? Tétel (Dirac): Ha G egy 2n-ed rendő gráf, és minden csúcspontja legalább n-ed fokú, akkor a gráf Hamilton-gráf. Tétel (O. Ore, 1960): Ha G egy n-ed rendő, n ≥ 3, és minden nem szomszédos u, v csúcspontjára deg u + deg v ≥ n, akkor G Hamilton-gráf. Matematika I.


236

Reguláris gráfok esetében a Dirac-tétel javítható: Jackson (1980) kimutatta, hogy minden olyan 2-összefüggı r-reguláris gráf, amelynek legalább 3r csúcspontja van, az Hamilton-gráf. A Petersen gráf mutatja, hogy a 3r feltétel nem helyettesíthetı 3r+1el.

Matematika I.


237

Gyakorlat: Bináris fák és alkalmazásaik: bináris fák ábrázolása rendezés fával tömörítés fával.

Matematika I.


238

Matematika I. Mőszaki informatikai mérnm. Galambos GáborG JGYPK 2011

Recommend Documents