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

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

Galambos Gá Gábor JGYPK 2011 2011--2012 2012 Matematika I.

Felsıfokú Szakképzés

1

A Matematika I. fı fıbb té témái: Halmazok: Alapfogalmak, mő mőveletek halmazokkal, szá számhalmamhalmazok, zok, vé végtelen halmazok. Relá á ció Rel ciók: Alapfogalmak, relá reláció ciók tulajdonsá tulajdonságai (reflexí (reflexív, szimszimmetrikus, metrikus, tranzití tranzitív, ekvivalencia relá reláció ció, trichotó trichotómia, rendezé rendezés, jó jólrendezé rendezés). Függvé ggvények: Alapfogalmak, fü függvé ggvények ábrá brázolá zolása, mő mőveletek függvé ggvényekkel, speciá speciális fü függvé ggvények (pl. rekurzí rekurzív fü függvé ggvények). Matematikai logika: Alapfogalmak, logikai mő ő veletek, logikai m függvé ggvények, kö következteté vetkeztetések és szabá szabályaik. Lineá ineáris algebra alapjai: Lineá Lineáris egyenletrendszerek, má mátrixok, determiná determinánsok, lineá lineáris egyenletrendszerek numerikus megoldá megoldásai. Kombinató Kombinatórika: rika: Alapfogalmak, permutá permutáció ció és tulajdonsá tulajdonságai, kombiná á ció ó k, binomiá á lis együ ü ttható ó k, variá á ció ó k. kombin ci binomi egy tthat vari ci Grá Gráfelmé felmélet: Alapfogalmak, grá gráfok ábrá brázolá zolása, klasszikus grá gráfbejá fbejárások, pá párosí rosítások, magyar mó módszer, fagrá 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ö közös tulajdonsá tulajdonságok alapjá alapján csoportba foglalható foglalható tárgyakat, fogalfogalmakat halmazoknak nevezzü nevezzük. Pl. bé bélyeggyő lyeggyőjtemé jtemény, embercsoportok, szá számok, fü függvé ggvények. A halmazhoz tartozó tartozó egyedeket a halmaz elemeinek nevezzü nevezzük. Melyek az elemek legfontosabb tulajdonsá tulajdonságai? Egyé Egyértelmő rtelmően eldö eldönthetı nthetı, hogy az elem hozzá hozzátartoziktartozik-e a halmazhoz. A halmaz minden eleme a tö többi elemtı elemtıl megkü megkülönbö nböztethetı ztethetı. Egy halmazban egy elem csak egyszer fordul elı elı. Egy halmaz nem lehet önmagá 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ö jelöléssel írjuk le. Ha h nem eleme a H halmaznak, akkor a h ∉ H jelö jelölést alkalmazalkalmazzuk. zuk. Pl. Ha ℕ-nel jelö jelöljü ljük a termé természetes szá számok halmazá halmazát, akkor 5 ∊ ℕ és -13 ∉ ℕ. Bármely halmazt egyé egyértelmő rtelmően meghatá meghatározzá rozzák az elemei: ha H egy halmaz, akkor bá bármely x dologra vagy x ∊ H vagy x ∉ H áll fenn. Két halmazt akkor tekintü tekintünk azonosnak, azonosnak, ha elemei ugyanazok, azaz a H és K halmaz akkor egyenlı egyenlı, ha h ∊ H eseté esetén h ∊ K is teljesü teljesül, és ha h ∉ H akkor h ∉ K is igaz. Jelö Jelölése: H = K. K. Matematika I.


6

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

Matematika I.


7

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

x = 2kπ , ahol k ∈ Z .

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


8

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

Matematika I.


9

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

Autó Autók

Szemé Személyautó lyautók

Matematika I.


10

Egy K halmazt a H halmaz részhalmazá szhalmazának nevezü nevezünk, ha a K halhalmaz minden eleme egyben H-nak is eleme. Jelö Jelölése: K ⊆ H. A definí definíció cióból kö következik, hogy minden halmaz ré része sajá saját magá magának, hiszen minden x ∊ H -ból következik, hogy x ∊ H, tehá tehát a H ⊆ H tartalmazá tartalmazás mindig igaz. Az üres halmaz minden halmaznak ré részhalmaza. Egy K halmazt a H halmaz való valódi részhalmazá szhalmazának nevezü nevezünk, ha a K részhalmaza H-nak és H-nak van legalá legalább egy eleme, amely nem eleme K-nak. Jelö 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ü Tekintsünk egy A halmazt, amely ré részhalmaza H-nak. Azt a halmazt, amely a H valamennyi A-hoz nem tartozó tartozó elemé elemét tartalmazza, az A halmaz H-ra vonatkoztatott komplementer (kiegé (kiegészí szítı) halmazá halmazának nevezzü nevezzük. Jelö Jelölése: A’ = {x {x | x ∊ H és x ∉ A } H A’ A

Matematika I.


12

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

Matematika I.


13

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

A×B=

Matematika I.

f (1, f )

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


14

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

Matematika I.


15

ℕ

ℕ

Matematika I.


16

A mőveletekrıl általá ltalában Egy H halmazon értelmezett (belsı, ké kétvá tváltozó ltozós) mővelet nem má más, mint a H × H szorzathalmaz leké leképezé pezése önmagá nmagába a H halmazba, azaz minden (x,y (x,y)) ∊ H × H rendezett pá párhoz H egy elemé elemét rendeljü rendeljük hozzá hozzá. Matematika jelö jelöléssel:

φ: (x,y (x,y)) ∊ H × H → z = f(x,y) x,y) ∊ H Három alapvetı mőveleti tulajdonsá tulajdonságot fogunk definiá definiálni: Asszociativitá Asszociativitás (csoportosí (csoportosítható thatóság) Kommutativitá Kommutativitás (felcseré (felcserélhetıség) Disztributivitá Disztributivitás (szé (széttagolható ttagolhatóság) Matematika I.


17

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

(2 )

3 2

2 ≠ 2 (3 )

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

Matematika I.


18

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

Matematika I.


19

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


20

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

Matematika I.


21

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

B

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


22

Az unió unióképzé pzés mőveleté veletének legfontosabb tulajdonsá tulajdonságai: Az unió unióképzé pzés mővelete kommutatí kommutatív. Az unió unióképzé pzés mővelete asszociatí asszociatív. Az unió unióképzé 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é metszetén (kö (közös ré részé szén) azt a halmazt értjü rtjük, amely azokat és csak azokat az elemeket tartalmazza, amelyek mind az A mind a B halmaznak elemei. Jelö Jelölése: A ∩ B. Az A és B halmazokat az metszet tagjainak nevezzü nevezzük. Pl. Legyen K = {12 osztó osztói}, és L = {20 osztó osztói}. Ekkor K = {1, 2, 3, 4, 6, 12} és H = {1, 2, 4, 5, 10, 20}. Így A ∩ B ={1, ={1, 2, 4}. A metszethalmaz éppen a 12 és 20 kö ö z ö s osztó ó inak halmaza. k oszt A halmazok metszete há három vagy tö több tagra is definiá definiálható lható: Az A1, A2,…, An, halmazok metszeté metszetén azt a halmazt értjü rtjük, amely azokat és csak azokat az elemeket tartalmazza, amelyek Ai (i=1,2, =1,2,…, n) n) halmazok mindegyiké mindegyikének eleme. Jelö Jelölése: A1 ∩ A2 ∩ … ∩ An.

Matematika I.


24

Az metszetké metszetképzé pzés mőveleté veletének legfontosabb tulajdonsá tulajdonságai: Az metszetké metszetképzé pzés mővelete kommutatí kommutatív. Az metszetké metszetképzé pzés mővelete asszociatí asszociatív. Az metszetké metszetképzé 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ó unió a metszetké metszetképzé pzésre né nézve disztributí disztributív. A metszet az unió unióképzé pzése né nézve disztributí disztributív.

Matematika I.


25

Szemlé Szemléltessü ltessük, hogy unió unió a metszetké metszetképésre né nézve disztributí disztributív! A ∪ (B ∩ C ) = (A (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ü különbsé nbsége Az A és B halmazok különbsé nbségén az A halmaznak azt a ré részé szét értjü rtjük, amelyek nem tartoznak a B halmazhoz. Jelö Jelölése: A \ B . A kü különbsé nbségké gképzé pzés mőveleté veletének legfontosabb tulajdonsá tulajdonságai: Az A \ B különbsé nbséghalmaz mindig ré részhalmaza A-nak. Amennyiben egy A halmazbó halmazból kivonjuk annak egy B részhalmaszhalmazát, akkor a B halmaznak A-ra vonatkozó vonatkozó komplementeré komplementerét kapjuk: A \ B = B' . A B \ A különbsé nbséghalmazt az A \ B szimmetrikus pá párjá rjának neveznevezzük. A B \ A és az A \ B halmazoknak nincs kö közös eleme (diszjunktak). A \ ∅ = A és ∅ \ A = ∅ és A \ A = ∅. A kü különbsé nbségké gképzé pzés mővelete nem kommutatí kommutatív. A kü ü l ö nbsé é gké é pzé é s m ő velete nem asszociatí k nbs gk pz asszociatív. Matematika I.


27

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

B

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


28

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

A

B

C

Matematika I.


29

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

Matematika I.


30

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

Matematika I.


31

A Peano axió axiómák (formalizá (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) ii) 0 ∊ K, (iii (iii)) ha n ∊ K, akkor n' ∊ K, akkor K = ℕ.

Matematika I.


32

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


33

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

n ( n + 1) n ( n + 1) + 2 ( n + 1) + ( n + 1) = = 2 2

( n + 1)( n + 2 ) . 2 Ezé Ezért a té tétel állí llítása igaz. =

Matematika I.


34

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

Matematika I.


35

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

Matematika I.


36

Az n termé természetes szá szám ellentettjé ellentettjének nevezzü nevezzük, és –n-nel jelö jelöljü ljük az n + x = 0 egyenlet megoldá megoldását. Tehá Tehát –n-et az n +(– +(–n) = (– (–n) + n = 0 összefü sszefüggé ggés értelmezi. A pozití pozitív termé természetes szá számok ellentettjei a termé természetes szá számokkal együ együtt alkotjá alkotják az egé számok halmazá halmazát. Az egé egész szá számok egész szá halmazá á nak jele: ℤ . halmaz A permanencia elvé elvének megfelelıen az összeadá sszeadás az egé egész szá számok halmazá á n a kö ö vetkez ı k é ppen é rtelmezhet ı : halmaz k Tetszıleges n, m ∊ ℕ-re, 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á Racionális szá számok Legyen p, q ∊ ℕ és q ≠ 0. Keressü Keressük qx = p egyenlet megoldá megoldását az egé egész szá számok halmazá halmazán. Ha a megoldá megoldás nem egé egész, akkor a p-nek qval való ó osztá á s á t jelö ö ljü ü k p/qval, é s ezt egy ú j szá val oszt jel lj p/q számnak tekintjü tekintjük. A p/q alakú alakú szá számokat, ahol q ≠ 0, racioná racionális (tö (tört)szá rt)számoknak neveznevezzük, ahol p a tö törtszá rtszám szá számlá mlálója és q a tö törtszá rtszám nevezıje. je. A racioná racionális szá számok jelö jelölése: ℚ. Az egé egész szá számok olyan tö törtszá rtszámok, amelyeknek nevezıje 1. A racioná racionális szá számok halmazá halmazán a racioná racionális mőveletek – összeadá sszeadás, kivoná kivonás, szorzá szorzás, osztá osztás – elvé elvégezhetık. (Ez azt jelenti, hogy e mőveletek eredmé eredménye nem vezet ki a racioná racionális szá számok halmazá halmazából.) Matematika I.


38

Amennyiben azt akarjuk, hogy a

p alakú alakú szá számok ugyanú ugyanúgy viselvisel1

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

a c ad + bc + = b d bd

a c ac ⋅ = b d bd

Matematika I.


39

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

3,212121... = 3 +

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

= 3 + 21 ⋅

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

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


40

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

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

Matematika I.


41

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

2 nem írható rható fel

p alakban, ahol p,q ∊ ℤ. q

Biz.

p , ahol (p,q) = 1. q 2 p Emeljü Emeljük mindké mindkét oldalt né négyzetre: 2 = 2 . q Tfh. az állí llítás nem igaz. Ekkor 2 =

Ebbıl adó adódik, hogy 2q2 = p2, ami lehetetlen, hiszen p és q relatí relatív prí prímek. Matematika I.


42

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

Matematika I.


43

Tétel: Az irracioná irracionális szá számok halmaza a racioná racionális szá számok komplementer halmaza a való valós szá számok halmazá halmazára vonatkozó 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á számok Láttuk azt, hogy a szá számhalmazok kö között a való valós szá számok halmaza a legtá á gabb halmaz, amely ké é t diszjunkt halmazra – a racioná legt k racionális és az irracioná irracionális – bontható bontható. Létezik a való valós szá számok halmazá halmazának má másfé sféle felbontá felbontása részhalmaszhalmazokra? zokra? Kis kité kitérı következik

Matematika I.


45

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

Matematika I.


46

Mőveletek polinomokkal Az egyes monomokban a vá változó ltozók kitevıinek összege adja meg az adott monom foká fokát. A polinom foká fokának a benne lé lévı monomok foká fokának maximumá maximumát tekintjü tekintjük. A 0 fokú fokú monomokat konstans polinomoknak nevezzü nevezzük. Egynemőnek nevezü nevezünk ké két monomot, ha csak együ együttható tthatóban különbö nböznek. Polinomokat úgy adunk össze, ssze, hogy az egynemő egytagok együ együttható 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á beszorzunk” szorzásakor „minden tagot minden taggal beszorzunk” és a keletkezı szorzatokban az azonos vá változó ltozók hatvá hatványait az azonos alapú alapú hatvá hatványok szorzá szorzásának szabá szabályá lyával szá 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á Speciális polinomok A polinomok legegyszerőbb megjelené megjelenési formá formái az egyvá egyváltozó ltozós polinomok. Példá ldául az 8x3 – 7x2 + 36 egy harmadfokú harmadfokú, egyvá egyváltozó ltozós polinom. Az x fokszá fokszáma szerint csö csökkenı sorrendbe írva, az elsı monom foka 3, a má á sodiké é 2, a harmadiké m sodik harmadiké 0. A harmadfokú harmadfokú tag együ együttható tthatója 8, a má másodfokúé sodfokúé -7, a konstans tag 36. Egy polinomot homogé homogén fokszá fokszámúnak nevezü nevezünk, ha benne minden monom foka egyenlı. Pl. a binomiá binomiális té tétel: (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 Matematika I.


49

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

Tétel: az elsıfokú fokú algebrai szá számok a racioná racionális szá számok. Tétel: Elsınél magasabb fokú fokú algebrai szá szám nem lehet racioná racionális szá szám.

Matematika I.


50

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

14 141 1414 14142 , , , 10 100 1000 10000

Liouville: Liouville: A

1 1 1 1 + 1⋅2 + 1⋅2⋅3 + L + 1⋅2⋅3Ln + L q q q q végtelen sor hatá határérté rtéke minden q > 1 eseté esetén transzcendens szá szám. a = 1+

A π és az e is transzcendens szá szám. (Errıl tö többet a gyakorlaton)

Matematika I.


51

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

1

2

3

4

↑↓

↑↓

↑↓

↑↓

↑↓

0 Matematika I.

1

4

9

16


n …

↑↓

…

n2 52

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

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


53

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

⇩

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

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


54

Ha az elemek sorbarendezhetık, akkor az A halmaz felí felírható rható végtegtelen sorozat formá formájában:

a1, a2, a3, a4, …,an, … Ennek az a kö következmé vetkezménye, hogy ha egy halmaz elemei sorbarendezhetık, akkor a halmaz elemeinek szá számossá mossága megegyemegegyezik a termé természetes szá számok szá számossá mosságával. Egyszerő példá ldák: A pozití pozitív pá páros szá számok és a prí prímszá mszámok halmaza megszá á mlá á lható ó . megsz ml lhat

Tétel: Egy megszá megszámlá mlálható lható halmaz bá bármely vé végtelen ré részhalmaza szinté szintén megszá megszámlá mlálható lható. Bizonyí Bizonyítás egyszerő. Matematika I.


55

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

↑↓ 0

Matematika I.

↑↓ -1

↑↓ 1

↑↓ -2

↑↓ 2

↑↓

-3


… 56

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

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

Matematika I.


57

Az elıbbi állí llítás bizonyí bizonyításához elıszö ször belá belátjuk, hogy a pozití pozitív racioná racionális szá számok halmaza megszá megszámlá mlálható lható: Alkossuk meg a kö következı elrendezé 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á táblá blázatot átló tlósan! Hagyjuk ki a tá táblá blázatbó zatból az egyszerősíthetı törteket balra tolva a sort! A maradé maradék tá táblá blázatban minden pozití pozitív racioná racionális szá szám egyszer szerepel. Matematika I.


58

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

Matematika I.


59

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

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


60

Most állí llítsuk elı a

b = 0 , b1b 2 b3 b 4 ... szá számot a kö következıképpen: b1-et úgy vá választjuk, hogy a11 ≠ b1. Ezé Ezért a1 ≠ b. b2-et úgy vá választjuk, hogy a22 ≠ b2. Ezé Ezért a2 ≠ b. b3-et úgy vá választjuk, hogy a33 ≠ b3. Ezé Ezért a3 ≠ b. és így tová tovább… bb… Olyan szá számot konstruá konstruáltunk tehá tehát, amely nincs a megszá megszámlá mlálható lhatóan végtelen sok szá szám kö között. Mivel ilyen konstrukció konstrukcióból vé végtelen sok készí í thet ı , ezé é rt a (0,1) intervallum való ó s szá á mainak halmaza nem sz ez val sz megszá megszámlá mlálható lhatóan vé végtelen. Egy olyan halmazhoz jutottunk, amelyben az elemek szá száma tö több, bb, mint a megszá megszámlá mlálható lhatóan vé végtelen szá számossá mosságú halmazok elemszá elemszáma. ma. Matematika I.


61

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

Matematika I.


62

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

Matematika I.


63

Relá Reláció ciók, fü függvé ggvények A mindennapi életben kapcsolatok vesznek kö körül bennü bennünket: Szü Szülı – gyermek Adó Adós – hitelezı Eladó Eladó – vevı stb… stb… A matematika – többek kö között – tanulmá tanulmányozza a halmazok ill. azok elemei kö közötti kapcsolatokat. Ezeket relá reláció cióknak nevezzü nevezzük. Jelö Jelölése: a ℜ b (a relá reláció 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ö ször ábrá brázoljuk a relá reláció ciót egy ábrá brával, amelyben a pontok jelö jelölik a szá számokat, és a nyilak a relá reláció ciót: Ha a relá reláció cióban van b-vel, akkor a-ból irá irányí nyított nyí nyíl (é (él) mutat b-be: 1

5

2

3

4 Mely szá számokat jelö 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ó osztója b-nek. Az ábrá bránkon – az elızıhöz hasonló hasonlóan – ha a relá reláció cióban van b-vel, akkor a-ból irá irányí nyított nyí nyíl (é (él) mutat b-be. Vegyü Vegyük figyelembe, hogy bármely a ∊ ℕ+-ra: ra: a | a. (Ezt egy hurok éllel jelö jelöljü ljük.) 10

8 4

5 2

6 3

7 9

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


66

Biné Binér (ké (kételemő) relá reláció ció Az A és B halmazok kö közötti biné binér ℜ relá reláció ció az (a, b) (a ∊ A, b ∊ B) rendezett pá á rok egy ré é szhalmaza. A ré é szhalmaznak azon (a, b) pá p r r párok lesznek az elemei, amelyekre a ℜ b teljesü teljesül. Általá ltalánosan fogalmazva: a relá ció két vagy tö több halmaz DescartesDescartesreláció féle szorzatá szorzatának egy ré részhalmaza. Pl. Legyen A = {1, 3, 6} és B = {0, 2, 4, 5}. Hatá Határozzuk meg az a + b < 7 relá reláció 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á reláció ciót meghatá meghatározhatunk Az alaphalmaz és valamely tulajdonsá tulajdonság megadá megadásával A relá reláció cióhoz tartozó tartozó rendezett pá párok felsorolá felsorolásával Grá á ffal Gr Táblá blázattal A matematika gyakran csak egy halmaz elemei kö közötti relá reláció ciókkal foglalkozik. Ilyenkor az A × A szorzathalmaz ré részhalmazait kell megadni.

Matematika I.


68

Biné Binér relá reláció ciók tulajdonsá tulajdonságai Ha ℜ a H halmazon értelmezett relá reláció ció, és az a ℜ a a halmaz minden elemé elemére teljesü teljesül, akkor az ℜ relá reláció ció reflexí reflexív. Példá ldák reflexí reflexív relá reláció ciókra: A pozití pozitív termé természetes szá számok halmazá halmazán: a osztó osztója b-nek. A sí sík valamennyi egyenesé egyenesének a halmazá halmazán: a párhuzamos b-vel. A való valós szá számok halmazá halmazán: a egyenlı b-vel.

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

Matematika I.

h1 h1


h2

h3

h4

h5

h2 h3 h4 h5

h1

h2

h5

h4

Matematika I.

69


h3

70

Egy H halmazon értelmezett ℜ biné binér relá reláció ciót akkor mondunk szimmetrikusnak, szimmetrikusnak, ha bá bármely a,b ∊ H-ra a ℜ b és b ℜ a egyará egyaránt fenná fennáll. Példá ldák szimmetrikus relá reláció ciókra: A pozití pozitív termé természetes szá számok halmazá halmazán: a egyenlı b-vel. A sí sík valamennyi há háromszö romszögének a halmazá halmazán: a hasonló hasonló b-hez. A sí í k valamennyi egyenesé é nek a halmazá á n: a mer ıleges b-re. s egyenes halmaz A való valós szá számok halmazá halmazán: a nem egyenlı b-vel.

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

h1 h1


h2

h3

h4

h5

h2 h3 h4 h5

h1

h2

h5

h4

Matematika I.

71


h3

72

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

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

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


73

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

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

Matematika I.


74

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


75

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

a ≡ b (mod m )

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

Matematika I.


76

Ekvivalenciosztá Ekvivalenciosztályok Legyen ℜ a T halmazon értelmezett ekvivalenciarelá ekvivalenciareláció ció, és legyen a ∊ T. Az a ekvivalenciaosztá ekvivalenciaosztályá lyának nevezzü nevezzük T-nek az a-val ekviekvivalens elemeinek halmazá halmazát, azaz az a-val relá reláció cióban lé lévı elemek halmazá halmazát. Jelö 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é két ekvivalenciaosztá ekvivalenciaosztály megegyezik Tegyü Tegyük fel, hogy a T(a) és T(b) ekvivalenciosztá ekvivalenciosztályoknak van kö közös eleme. Legyen ez x. Mivel x ∊ T(a) és x ∊ T(b), ezé ezért x ~ a és x ~ b egyidejőleg. Így a tranzitivitá tranzitivitás miatt a ~ b., ezé ezért a ∊ T(b), ami miatt T(a) ⊆ T(b). Hasonló Hasonlóan megmutatható megmutatható, hogy T(b) ⊆ T(a). Így T(a) = T(b). Matematika I.


77

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

6 3 ℜ . 5 10

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


78

Vannak má más relá reláció ciók is, amelyek – tulajdonsá tulajdonságai miatt – kitü kitüntetett figyelmet érdemelnek. A H halmazt rendezettnek mondjuk, ha elemein értelmezve van egy a ≺ b relá reláció ció, amely rendelkezik az alá alábbi tulajdonsá tulajdonságokkal:

a ≺ a hamis (irreflexivitá (irreflexivitás) ha a ≺ b igaz, akkor b ≺ a hamis (asszimetria) ha a ≺ b igaz, és b ≺ c igaz, akkor a ≺ c igaz (tranzitivitá (tranzitivitás) ha a ≠ b, akkor az a ≺ b és a b ≺ a közül legalá legalább az egyik igaz (trichotó (trichotómia).

Matematika I.


79

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

Matematika I.


80

Függvé ggvények Ha valamely A halmaz elemeihez adott utasí utasítás szerint egy B halmaz elemeit rendeljü ü k hozzá á ú gy, hogy A minden elemé rendelj hozz elemének megfeleltü megfeleltünk legalá legalább egy B-beli elemet, akkor azt mondjuk, hogy az A halmazt leké leképezzü pezzük a B halmazra vagy halmazba. Ha a B halmaz összes elemé elemét megfeleltjü megfeleltjük A elemeinek, akkor a B halmazra képezü pezünk. Ha a B halmaz egy ré részhalmazá szhalmazát feleltjü feleltjük meg A elemeinek, akkor a B halmazba képezü pezünk. Az A-t tárgyhalmaznak, rgyhalmaznak, elemeit tárgyelemeknek nevezzü nevezzük. Az B-t képhalmaznak, phalmaznak, elemeit képelemeknek nevezzü nevezzük. A leké leképezé pezést a hozzá hozzárendelé rendelési elıírás és a tá tárgyhalmaz egyé egyértelmően meghatá meghatározza. Jelö 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á reláció ciót leké leképezé pezésnek nevezzü nevezzük. A φ és δ leké leképezé pezéseket akkor tekintjü tekintjük egyenlınek, nek, ha bá bármely a ∊ A eseté é n φ ( a ) = δ ( a ). eset A leké leképezé pezéseket a tá tárgyelemekhez rendelt ké képelemek szá száma, ill. a képelemekhez rendelt tá tárgyelemek szá száma szerint osztá osztályozhatjuk: Ha minden egyes ké képelemnek csak egy tá tárgyeleme van, akkor a leké leképezé pezés egyegy-egyé egyértelmő vagy kölcsö lcsönösen egyé egyértelmő.

B

A Matematika I.


82

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

B

A

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

Matematika I.


83

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

B

A

Pl. anya → gyerekei

Matematika I.


84

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

B

A

Pl. tulajdonosok → cégek

Matematika I.


85

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

Matematika I.


86

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

Matematika I.


87

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

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

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

Matematika I.


88

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

b1 a1 a2 a3 a4 a5

b2 +

b3

b4

b5

+ + + +

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

Matematika I.


89

Függvé ggvények megadá megadása Descartes diagrammal

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


90

Függvé ggvények megadá megadása Venn diagrammal

B

A

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

Matematika I.


91

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


92

Tétel: Ké Két leké leképezé pezés összeté sszetétele nem kommutatí 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á brázoljuk a ké két fü függvé ggvényt!

Matematika I.


93

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


94

Ha az (x, f(x)) az f grafikonjá grafikonjának egy pontja, akkor az (f(x), x) az f -1 függvé ggvény grafikonjá grafikonjának egy pontja, azaz a ké két fü függvé ggvény grafikonjai egymá egymásnak tü tükörké rképei, ahol a tü tükrö 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í Rekurzív sorozatok

Oldjuk meg a kö következı feladatot: Há Hány nyú nyúl szá származik egyetlen pá pár nyú nyúltó ltól, ha tudjuk, hogy minden pá pár havonta új pá párnak ad életet, és az újszü jszülött nyulak ké két hó hónapos koruktó koruktól lesznek szü szülıképesek? hónap 1 nyú ú lpá á r ny lp 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 FibonacciFibonacci-sorozat néhány tulajdonsá tulajdonsága:

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

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

Matematika I.


97

Az ítélet mint fü függvé ggvény

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

Matematika I.


98

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


99

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


100

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

Matematika I.


101

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

Matematika I.


102

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

Matematika I.

h i


103

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

q

i i h h

i h i h

Matematika I.


p∧ q i h h h

104

Diszjunkció Diszjunkció Két kijelenté kijelentés, p és q diszjunkció diszjunkcióján (szé (szétvá tválasztá lasztásán) a ”p vagy q” kijelenté kijelentést (vagy ennek egy nyelvtanilag átfogalmazott alakjá alakját) értjü ü k. (Megenged ı é rtelm ő ö sszekapcsolá á s.) rtj sszekapcsol ”Tejet vagy kakaó kakaót reggelizü reggelizünk.” nk.” Ez az állí llítás akkor igaz, ha legalá legalább az egyik tagja igaz. Jelö Jelölése: p ∨ q. A diszjunkció diszjunkció mőveleté veletének igazsá igazságtá gtáblá 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é rtékeket, a logikai vá változó ltozókat és a rajtuk vé végzett mőveleteket leí leíró jelsorozatokat az ítéletkalkulus formulá formuláinak nevezzü nevezzük. Két formulá formulát azonosnak nevezü nevezünk, nk, ha a ké két formula a benne szereplı változó ltozók minden lehetsé lehetséges érté rtékére ugyanazt a logikai érté rtéket állí llítja elı. Példa: A ∪ (B ∩ C ) = A A bizonyí bizonyítás abbó abból áll, hogy kimutatjuk az a ∊ A ∨ (a ∊ A ∧ a ∊ B ) állí llítás akkor és csak akkor igaz, amikor az a ∊ A állí llítás. Elegendı azt bebizonyí bebizonyítani, hogy az állí llítások a vá változó ltozók logikai érté rtékeire megegyeznek. Matematika I.


106

Tehá Tehát azt kell igazolnunk, hogy p, q tetszıleges állí llítások eseté esetén a fönná á lle a p = p ∨ ( p ∧ q ) egyenl ı s é g. nn ll Készí szítsü tsük el az igzsá igzságtá gtáblá blázatot: 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á táblá blázatunk elsı és utolsó utolsó oszlopa megegyezik, ezé ezért az állí llításunk igaz.

Matematika I.


107

Tétel: Bármely logikai mővelet kifejezhetı a negá negáció ció és a konjunkció konjunkció mőveleté é vel. velet Nem bizonyí bizonyítjuk, de megmutatjuk az elıállí 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á tulajdonságai Logikai ”vagy” vagy”: kommutatí kommutatív: p ∨ q = q ∨ p asszociatí asszociatív: (p (p ∨ q) ∨ r = p ∨ (q ∨ r) disztributí disztributív: p ∨ (q ∧ r) = (p (p ∨ q) ∧ (p ∨ r) idempotens: p ∨ p = p Logikai ”és ”és”: kommutatí kommutatív: p ∧ q = q ∧ p asszociatí asszociatív: (p (p ∧ q) ∧ r = p ∧ (q ∧ r) disztributí disztributív: p ∧(q ∨ r) = (p (p ∧ q) ∨ (p ∧ r) idempotens: p ∧ p = p Matematika I.


109

Tová További logikai mőveletek A ”p akkor q” alakú alakú kifejezé kifejezéseket impliká implikáció ciónak nevezzü nevezzük. (Itt p az elıtag és q az utó utótag.) ”Ha a ré részvé szvények ára csö csökken, akkor nem adom el ıket.” ket.” (Amennyiben a ré részvé szvények ára nem csö csökken, akkor igaznak tekintjü tekintjük az állí llítást aká akár eladtam a ré részvé szvényeket, aká akár nem, mert erre vonatkozó vonatkozóan nem mondtunk elıre .) Jelö Jelölése: p → q. Az impliká implikáció ció mőveleté veletének igazsá igazságtá gtáblá 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á implikáció ció nem kommutatí kommutatív és nem asszociatí asszociatív mővelet. Az impliká implikáció ció kifejezé kifejezése diszjunkció diszjunkcióval és negá negáció 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é Ezért: p → q = ¬p ∨ q. Amennyiben figyelembe vesszü vesszük az impliká implikáció ció kifejezhetıségét a negá negáció cióval és a konjunkció konjunkcióval, azt kapjuk, hogy: p → q = ¬(p ∧ ¬ q). Matematika I.


111

A ”ha p akkor q, és ha q akkor p” p” alakú alakú kifejezé kifejezéseket ekvivalenciá á nak nevezzü ü k. ekvivalenci nevezz ”Egy né négyszö gyszög akkor és csak akkor hú húrné rnégyszö gyszög, ha szemkö szemközti szö szögeinek összege 180° 180°.” (Figyeljü (Figyeljük meg, hogy itt ké két állí llítást tettü tettünk egyszerre.) Jelö Jelölése: p ↔ q. A definí definíció ció szerint p ↔ q = (p → q) ∧ ( q → p) Az ekvivalencia mőveleté veletének igazsá igazságtá gtáblá 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” p” alakú alakú kifejezé kifejezéseket antivalenciá nevezzük. antivalenciának nevezzü A mővelet a ”kizá kizáró vagy ismert” ismert” (XOR). Az antivalencia akkor és csak akkor igaz, ha a ké két állí llítás logikai érté rtéke kü különbö nbözı. Jelö Jelölése: p ⊕ q. A mővelet az igazsá igazságtá gtáblá blázatbó zatból kizá kizárja azokat az eseteket, amelyekben mindké mindkét állí llítás igaz, tehá tehát formá formálisan az ekvivalencia tagadá tagadását jelenti. p ⊕ q = ¬(p ↔ q ) Az antivalencia mőveleté veletének igazsá igazságtá gtáblá 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ú alakú összetett kifejezé kifejezéseket semsem-sem (Webb(Webb-féle) mőveletnek nevezzü nevezzük. A mővelet a diszjunkció diszjunkció tagadá tagadása (NOR). Jelö Jelölése: p ↓ q. Érvé rvényes a kö következı azonossá azonosság: p ↓ q = ¬(p ∨ q ) A WebbWebb-féle mővelet igazsá igazságtá gtáblá 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ú alakú kifejezé kifejezéseket ShefferSheffer-féle mőveletnek nevezzü nevezzük. ”Vagy iszik az ember vagy vezet.” vezet.” A mővelet a konjunkció konjunkció tagadá tagadása (NAND). Ebben az esetben a ké két kijelenté kijelentés kö közül legfeljebb az egyik igaz. Jelö Jelölése: p | q. Érvé rvényes a kö következı két azonossá azonosság: p | q = ¬(p ∧ q ) Az ShefferSheffer-féle mővelet igazsá igazságtá gtáblá 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ü függvé ggvény fogalma Az eddigiekben ké kétvá tváltozó ltozós mőveleteket vizsgá vizsgáltunk, amelyek tekinthetık ké kétvá tváltozó ltozós fü függvé ggvényeknek is. Ebben az esetben az értelmezé rtelmezési tartomá tartomány az {i, {i, h} h} halmaz és az érté rtékké kkészlet is az {i, {i, h} h} halmazbó halmazból való való. Legyen i = 1 és n = 0. Az ilyen tí Booletípusú pusú függvé ggvényeket igazsá igazságfü gfüggvé ggvénynek vagy Boolefüggvé ggvénynek nevezzü nevezzük. A ké kétvá tváltozó ltozós BooleBoole-függvé ggvények mintá mintájára definiá definiálható lható az nváltozó ltozós BooleBoole-függvé ggvény is: ekkor mind az értelmezé rtelmezési tartomá tartomány, mind az érté rtékké kkészlet egy olyan szá szám n-es, amelynek elemei a {0, 1} halmazbó halmazból szá származnak. Matematika I.


116

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

n

2n

22 .

1

2

4

2

4

16

3 4

8 16

256 65536

5

32

4294967296

6

64

1,84 ·1019

Matematika I.


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.

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

1 0 1 0 1 0 1 0

f1 f2 f3 f4 f5 f6 f7 f8

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” mindig” diszjunkció diszjunkció impliká implikáció ció q impliká implikáció ció p ekvivallencia konjunkció konjunkció „soha” soha” „semsem-sem” sem” impliká implikáció ció tagadá tagadása negá negáció ció impliká implikáció ció tagadá tagadása negá negáció ció antivalencia Sheffer mő mővelet 118

Normá Normálformá lformák és fü függvé ggvényrendszerek A ké kétvá tváltozó ltozós fü függvé ggvényekné nyeknél lá láttuk, hogy mindegyik felí felírható rható a negá negáció ció, a konjunkció konjunkció valamint a diszjunkció diszjunkció mőveleteinek segí segítsé tségével. Megmutatható Megmutatható ez érvé rvényes az n-változó ltozós BooleBoole-függvé ggvényekre is oly módon, hogy felí felírható rható egy olyan formula, amely az adott n változó ó b ó l é p ü l fel, és mőveletké ltoz veletként a ¬, a ∧ és a ∨ logikai mőveleteket haszná használjuk. Az így felí felírt formula érté rtéke pontosan akkor lesz igaz, amikor az átalakí talakítandó tandó függvé ggvény érté rtéke is igaz. A fenti állí llítást nem bizonyí bizonyítjuk, hanem egy pé példá ldát mutatunk a konstrukció 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á Eljárás-1: olyan formulá formulát állí llítottunk elı, amivel az érté rtéktá ktáblá blázattal megadott igazsá igazságfü gfüggvé ggvényt ki tudjuk fejezni. A formula jellemzıi: a formula konjunkció konjunkciók diszjunkció diszjunkciója, ja, minden konjunkció konjunkciós tag vagy egy vá változó ltozó vagy annak a negá negáltja, minden diszjunkció diszjunkciós tagban minden vá változó ltozó szerepel, ugyanaz a vá változó ltozó egy konjunkció konjunkcióban csak egyszer szerepel, nincs ké két olyan diszjunkció diszjunkciós tag, amelyek csak a vá változó ltozók sorrendjé sorrendjében kü különbö nböznek.

A fenti tulajdonsá tulajdonságú formulá formulát teljes diszjunktí diszjunktív normá normálformá lformának nevezzü 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á Eljárás-2: olyan formulá formulát állí llítottunk elı, amivel az érté rtéktá ktáblá blázattal megadott igazsá igazságfü gfüggvé ggvényt ki tudjuk fejezni. A formula jellemzıi: a formula diszjunkció diszjunkciók konjunkció konjunkciója, ja, minden diszjunkció diszjunkciós tag vagy egy vá változó ltozó vagy annak a negá negáltja, minden konjunkció konjunkciós tagban minden vá változó ltozó szerepel, ugyanaz a vá változó ltozó egy diszjunkció diszjunkcióban csak egyszer szerepel, nincs ké két olyan konjunkció konjunkciós tag, amelyek csak a vá változó ltozók sorrendjé é ben kü ü l ö nbö ö znek. sorrendj k nb

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


123

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

Matematika I.


124

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

x2

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


126

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

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

Matematika I.


127

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


128

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

Matematika I.


129

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

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

Matematika I.


130

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

ÉS VAGY

NEM

ÉS

x2 Matematika I.


131

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

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

Matematika I.


133

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

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

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

Hasonló Hasonlóan kapjuk, hogy

y=

Matematika I.

c1a2 − c2 a1 a1c2 − a2c1 = , a2b1 − a1b2 a1b2 − a2b1

ha a1b2 − a2b1 ≠ 0


134

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

Matematika I.


135

A má másodrendő determiná determináns segí segítsé tségével az egyenletek megoldá megoldásai a következı alakban írható ó k fel: rhat c1 b1 a1 c1 Dy c b2 a c2 D x= 2 y= 2 = x, = , 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á determinánsá nsának nevezzü nevezzük. A Dx (ill. a Dy) determiná determinánst a D-bıl úgy kapjuk, hogy az x (ill. az y) együ együttható tthatóinak helyé helyébe beí beírtuk az egyenletrendszer jobb oldalá oldalán álló lló szá számokat. Matematika I.


136

Példa:

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

D= és

Dx = Ezé Ezért:

x=

7 3 5 1

1 3 1 1 = −8,

Dx − 8 = = 4, D −2

= 1 − 3 = −2 ≠ 0.

Dy =

1 7

= −2.

1 5

y=

Dy D

=

−2 = 1. −2

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


137

A má másodrendő determiná determináns tulajdonsá tulajdonságai Tétel: A determiná determináns érté rtéke elıjelet vá vált, ha ké két sorá sorát (vagy ké két oszlopá oszlopát) megcseré megcseréljü 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é vetkezményny-1: A determiná determináns érté rtéke nem vá változik, ha az elemeket a fıátló tlóra tü tükrö krözzü zzük. Matematika I.


138

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

k

a1

b1

a2 b2

= k (a1b2 − a2b1 ) = a1kb2 − b1ka2 =

Matematika I.


a1

b1

ka2

kb2

.

139

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

a1

b1

a1

b1

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

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

Matematika I.

a1

b1

ka 1

kb 1

=k

a1

b1

a1

b1


= 0.

140

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

a1 + c1

b1

a 2 + c2

b2

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

a1

b1

a2

b2

+

Matematika I.

c1

b1

c2

b2

.


141

Tétel: Egy determiná determináns érté rtéke nem vá változik, ha egy sorá sorának konstanskonstans-szorosá szorosát hozzá hozzáadjuk a má 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

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

a11 a21

a12 a22

a13 a23

a31

a32

a33

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

a11 a21

a12 a22

a13 a23 = a11a22 a33 + a12 a23a31 + a13a21a32

a31

a32

a33

− a13a22a31 − a12a21a33 − a11a23a32 .

Matematika I.


144

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

a11 a21

a12 a22

a13 a23

a31

a32

a33

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

a11 a21

a12 a22

a13 a23

a11

a12

a21

a22

a31

a32

a33

a31

a32

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


145

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

a 11 a 21

a 12 a 22

a 13 a 23 =

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

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

a22

a23

a32

a33

Matematika I.

− a12

a21 a23 a31 a33

+ a13

a21 a22 a31 a32


146

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

a 11 a 21

a 12 a 22

a 13 a 23

a 31

a 32

a 33

Jelö Jelölése:

A13 =

a21 a22 a31 a32

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


147

Az elsıfokú fokú három ismeretlenes egyenletrendszer Tekintsü Tekintsük a kö 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ö Jelöljü ljük az egyenletrendszer determiná determinánsá nsát D-vel, és jelö jelölje Di azt a harmadrendő determiná determinánst, nst, amelyet D-bıl úgy kapunk, hogy D idik oszlopá á t az egyenletrendszer jobboldalá oszlop jobboldalán álló lló érté rtékekkel helyettesí helyettesítjü tjük. Pl. a11 a12 b1 D3 = a21 a22 b2 a31 a32 b3 Matematika I.


148

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

xi =

Di , D

i = 1,2,3.

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

Matematika I.


149

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

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

1 2 1 D2 = 3 − 5 − 6 = −39 6 4 3

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

D3 = 130


151

Ezé Ezért az egyenletrendszer megoldá megoldása:

D1 104 2 = = D 156 3

x1 =

x2 =

D2 − 39 1 = =− D 156 4

x3 =

D 3 130 5 = = D 156 6

Az érté rtékek helyessé helyességét! Matematika I.

visszahelyettesí visszahelyettesítésével

ellenırizzü rizzük


a

megoldá megoldás

152

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

a21 M an1

a22 K a2 n M

O

M

n

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

an 2 K ann

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


153

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


154

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


155

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

4 8 12

8 12 1 20 24 = 4 8

2 20

3 1 24 = 4 ⋅ 4 2

32

32

36

36

12

2 5

12 32

3 6 = 36

3 2 3 16 6 5 6 =0 3 36 32 36

Matematika I.


156


100

101 102

103

100

1 2

3

101 102 102 103

103 104

104 101 1 2 = 105 102 1 2

3 =0 3

103

105

106

3

104

103

1 2


1

0

0

0

0 0

1 0

0 1

0 =1 0

0

0 105

Matematika I.

1 Felsıfokú Szakképzés

157

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

 a11 a12  a a An×m =  21 22 M M  a a  n1 n2

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

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


158

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


159

Mőveletek má mátrixokkal Az A = (a (aij)n×m és B = (b (bij)n×m mátrixok összegé sszegén azt a C = (c (cij)n×m mátrixot értjü rtjük, amelyre cij = aij + bij. Összeadni csak azonos tí típusú 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á skalárral úgy szorzunk, szorzunk, hogy a má mátrix minden elemé elemét szorozzuk a konstanssal. Ha A = (a (aij)n×m és λ egy való valós szá szám, akkor C = (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í típusú 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

i

Ai

i =1

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


161

Az A = (aij)n×m és B = (bij)p×q mátrixokat – ebben a sorrendben – konformá konformábilisnek nevezü nevezünk, ha m = p. Az A = (aij)n×m és B = (bij)m×l mátrixok szorzatá szorzatán azt a C = (cij)n×l mátrixot értjü 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á mátrixszorzá trixszorzás nem kommutatí kommutatív, és nem zérusosztó rusosztó-mentes, de asszociatí asszociatív és az összeadá sszeadásra né nézve disztributí disztributív. Matematika I.


162

Az A = (aij)n×m mátrix transzponá transzponáltjá ltján azt az Az A* = (aji)*m×n mátrixot értjü 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á determinánsá nsán a má mátrix elemeibıl ké képzett determiná determinánst értjü rtjük. Jelö Jelölése: |A| vagy det A. Az A mátrixot regulá regulárisnak nevezzü nevezzük, ha det A ≠ 0. Az A má mátrixot szingulá szingulárisnak nevezzü nevezzük, ha det A = 0

Matematika I.


163

Az En×n mátrixot egysé gmátrixnak nevezzü nevezzük, ha eii = 1, és eij = 0, ha egységmá i ≠ j. Egy A = (aij)n×n négyzetes má mátrix inverzé inverzén azt a A-1 = (aij)-1n×n mátrixot értjü 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 A−1 =  9 1  3

1 9 2 − 9 1 − 3

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

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


164

Tétel: Legyen A invertá invertálható lható mátrix, az inverzé inverzét jelö jelölje B=(bij). Ekkor fenná fennáll, hogy (−1)i + j det Aji bij = . det A ahol Aji az A mátrix aji elemé eleméhez tartozó tartozó adjungá adjungált aldeterminá aldetermináns.

Példa: Szá Számítsuk ki az A mátrix inverzé 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 = = = det A −3 3 det A −3 3 (−1)1+3 det A31 0 b13 = = =0 det A −3

b11 =

Matematika I.


b21 =

(−1)2+1 det A12 − 3 = =1 det A −3

b22 =

(−1) 2+ 2 det A22 3 = = −1 det A −3

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

b31 =

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

b33 =

 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 

165

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


166

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

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

2  AB =  1 1 

1 −1 1

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

Matematika I.

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á Lineáris egyenletrendszerek

Legyen Amxn egy má mátrix, b1, b2, …, bm pedig skalá skalárok. Lineá Lineáris egyenletrendszernek nevezzü nevezzük az alá 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á számot az ismeretlenek szá számának, nak, mí míg m-et az egyenletek szá számának nevezzü nevezzük.

Matematika I.


168

Bevezetve az ismeretlenekbıl és a jobb oldali skalá skalárokbó rokból ké képezett  x1   b1       x2  b  X =  B = 2  M M     x  b   n  n oszlopmá oszlopmátrixokat (oszlopvektorokat), a lineá lineáris egyenletrendszert rövidí vidített (má (mátrix alakban megadott) formá formában is felí felírhatjuk: AX = B A lineá á ris egyenletrendszerhez tartozó line tartozó alapmá alapmátrix az A mátrix, mí míg az un. bıvített alapmá alapmátrix: 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á skalárok mindegyike zé zéró, akkor homogé homogén lineá á ris egyenletrendszerr ı l beszé é l ü nk, mí í g ellenkez ı esetben line besz m inhomogé inhomogén lineá lineáris egyenletrendszerrıl. A (ξ1, ξ2, … , ξn) vektort a lineá lineáris egyenletrendszer megoldá megoldásának nevezzü ü k, ha nevezz 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ü teljesül. Triviá Triviális megoldá megoldás alatt a csupa zé zérusbó rusból álló lló megoldá megoldást értjü rtjük. Az ettıl elté eltérı megoldá megoldást nemtriviá nemtriviális megoldá megoldásnak nevezzü nevezzük. Matematika I.


170

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

xi =

Matematika I.

Di , D

i = 1,2,K , n.


171

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

a11x1 + a12x2

+ …

+ a1nxn

a21x1 + a22x2

+

+ a2nxn = a2n+1

…

= a1n+1

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

+ …

+

annxn

= ann+1 ahol ain+1=bi

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


172

Az algoritmus: 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ü gezzük el a következıket: ket: (i-1)-vel az egyenletrendszer j. sorá 2. Jelö Jelöljü ljük sj(isorát az i. lépésben. sben. (i1) (i Tegyü Tegyük fel, fel, hogy aii ≠0. (i-1)=a (i(i-1)/a (i(i-1). Legyen qj(iji ii (i) = s (i(i-1) –q (i(i-1)s (i(i-1) minden j>i3. Legyen sj(i) j>i-re. re. j j i Matematika I.


173

A szá számítások befejezé befejezése utá után a következı feladatot kapjuk: 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á megoldás:

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

a

n

∑a

t= j+1 ( j −1 ) jj

( j−1 ) jt

xt ,


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

174

Hatá Határozzuk meg a következı egyenletrendszer megoldá megoldását! 2x1+3x2-x3=9

2x1 +3x2 -

x= 9

2x1 +3x2 -

3

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

x1+2x2+x3 =4 x1-x2-2x3 =1

x= 9

3

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

q3(1)= -5

q2(0)=1/2 q3(0)=1/2 A megoldá megoldás: x3= -1 Matematika I.

− x2 =

1 3 + 2 2 = 2 1 2

x1 =

9 −(6 + 1) =1 2


175

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

∑ [(n − j )(n −

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

j=1

=

2 ∑ (n − j ) j=1

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

n −1

n −1

+ 2 ∑ (n − j ) j=1

2n 3 + 3n 2 − 5n − 1) = 6

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

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


176

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

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

Matematika I.


177

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

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

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


178

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

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

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

Matematika I.

2x1 + 3x2 -

x3 =

9

5 3 7 - x2 - x3 = − 2 2 2 1 3 1 x2 + x3 = 2 2 2 q3(1)= 1/5 1/5

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


179

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

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

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

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


180

j=1

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

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

Hibajelzé Hibajelzés

t=p 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,… (i=j+1,…,n) (i=j+1,..,n k=j+1,… k=j+1,…,n+1) j=j+1

a (jnj+−11 ) − xpj =

n

∑a

t = j +1 ( j −1 ) jj

a

Matematika I.

( j −1 ) jt

x pt

j ≤ n -1

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

VÉGE


181

Hatá Határozzuk meg az elızı egyenletrendszer megoldá megoldását a fıelem kivá á lasztá á s á nak mó ó dszeré é vel! ! kiv laszt 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 1/3 Matematika I.


182

3x2 - x3 + 2x1 = 9

3x2 - x3 +

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

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ü Figyeljük meg az indexeket és permutá permutáció ció vektor viszonyá 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á eljárás lényege: nyege: Ekvivalens átalakí talakításokkal olyan egyenletegyenletrendszer kialakí í t á sa, , amelynek együ ü ttható ó m á trixa egysé é gmá á kialak sa egy tthat egys gm trix. 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ü gezzük el a következıt: (i-1) az egyenletrendszer j. sora az i. lépésben. 2. Legyen sj(isben. Tegyü Tegyük fel, fel, (i1) (i hogy aii ≠0. (i-1)/a (i(i-1), 3. Legyen si(i)= si(iii (i) = s (i(i-1) – a (i)s (i) (i) minden j≠i-re. és sj(i) re. j ij i Matematika I.


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

185

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

(0)x (1) (0) (0)x + a21(0)x1 + a22(1) … + a2n(1) n = a 2n+1 2 ………………………………………………… (0)x + (1)x (0) (1) 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. 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. re. j=2 ,…, n

Matematika I.


187

Hatá Határozzuk meg az elızı egyenletrendszer megoldá megoldását a fıelem kivá á lasztá á s á nak mó ó dszeré é vel! ! kiv laszt 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 0 0


3 6

6 − 1 − 6

=

=

188

1 0 −5

6

0 1 3 − 1 0 0 6 − 6

Amibıl a megoldá megoldás:

Matematika I.

=

1 0 0

1

0 1 0 0 0 1

2 − 1

x3= -1 x2= 2 x1= 1


189

Mátrix invertá invertálása GaussGauss-Jordan eliminá elimináció cióval Az elızıekben leí leírt mó módszer egyszerő gyakorlati mó módszert ad mátrixok invertá invertálható lhatóságának eldö eldönté ntésére és az inverzmá inverzmátrix meghameghatározá rozására. ra. Megjegyzé Megjegyzés. (Má (Mátrix invertá invertálása szimultá szimultán Gauss eliminá elimináció cióval.) Legyen adva egy né négyzetes má mátrix, melyet Gauss eliminá elimináció cióval egysé é gmá á trixszá á alakí í tottunk: egys gm trixsz alak E k E k −1 K E1 A = I A má mátrix tehá tehát invertá invertálható 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á elimináció cióval, azaz elemi sorá sorátalakí talakításokkal egysé egységmá gmátrixszá trixszá alakí alakítjuk, s ugyanezeket az elemi sorá sorátalakí talakításokat vé végrehajtjuk az egysé egységmá gmátrixon, a végeredmé geredmény A inverze lesz. Tehá Tehát az eliminá elimináció ciót egyszerre, szimultá szimultán hajtjuk vé végre a ké két má mátrixon, de az elemi sorá sorátalakí talakításokat az A hatá határozza meg, az egysé egységmá gmátrix csak ”elszenvedi” elszenvedi”. Matematika I.


190

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

Matematika I.


191

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

=

1 0 0 0 1 0 0 0 1

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

1

Matematika I.

1 2 2 2 1 2

1

=

1 0 0 0 1 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 1 1

Ellenırzé rzés:

1

×

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


=

1 0 0

=

0 1 0 0 0 1 192

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

v1

v3

e3

e1 e5

e2

v4 e4 v5

v2

E(G) ≔ A G élhalmaza

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

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


194

V(G) elemeinek a szá számát a grá rendjének nevezzü nevezzük. Jelö Jelölése: n(G) n(G). gráf rendjé E(G) elemeinek a szá számát a grá gráf mé méreté retének nevezzü nevezzük. Jelö Jelölése: m(G) m(G).

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

{

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

{

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

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

∆(G) = max degG v a G grá gráf maximá maximális fokszá 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ú Csúcsfokszá csfokszámok egy grá gráfban Matematika I.


198

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

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

Matematika I.


199

Részgrá szgráfok és induká indukált ré részgrá szgráfok Azt a grá gráfot, amelynek nincsenek élei üres grá gráfnak nevezzü nevezzük. A H grá gráf a G grá gráf részgrá szgráfja, fja, ha V(H)⊆ V(G) és E(H)⊆ E(G). Legyen v∊V(G) V(G) és |V(G)| ≥ 2. A H = G – v grá gráf a v csú csúcs tö törlé 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 vv-re. Ha e∊ E(G), akkor H = G – e (egy él kitö kitörlé rlése) se) G-nek egy olyan részgrá 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é szomszédos csú csúcsai, akkor G + f, ahol f = uv, jelö jelöli azt a grá gráfot, amelynek csú csúcshalmaza V(G) és élhalmaza E(G) ∪ { f }. Ezé Ezért G ⊆ G + f. Ha G egy H részgrá szgráfjá fjának rendje megegyezik G rendjé rendjével, akkor Ht G feszí í t ı r é szgrá á fjá á nak nevezzü ü k. fesz szgr fj nevezz Ha U a V(G) egy ré részhalmaz, szhalmaz, akkor 〈U 〉 a G-nek egy olyan U által induká indukált grá gráfja, amely csú csúcshalmaza U ⊆ V(G) és élhalmaza minden olyan élet tartalmaz G-bıl, amely illeszkedik az U két elemé elemére.

Matematika I.


202

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

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

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


203

A Petersen gráf Matematika I.


204

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

Matematika I.


205

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

Egy teljes ké trészes grá gráfot, ahol |V1| = r és |V2| = s K(r,s)K(r,s)-el vagy Kr,skétré el jelö jelöljü ljük . (A K1,s grá gráfot csillagnak nevezzü nevezzük).

Matematika I.


v1

v4

v5

v2

v3

v6

v1

v3

v5

v2

v4

v6

206

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á gráf egyesí egyesítésén (unió (unióján) azt a G = G1 U G2 grá gráfot értjü rtjük, amelyre V(G) = V(G1) U V(G2) és E(G) = E(G1) U E(G2).

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

Matematika I.


208

Két grá gráf összekapcsolá sszekapcsolásán azt a G = G1+G2 grá gráfot értjü 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: lda:

G1 Matematika I.

G2

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

209

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

(u1,u2) u2

w1 G1

(u1,w2)

v2

v1

(v1,u2) w2

(v1,v2) (v1,w2) G = G 1 ×G 2

G2

Matematika I.

(u1,v2)


210

Grá Gráfok bejá bejárása Legyen Legyen u és v a G grá gráf – nem szü szüksé kségké gképpen kü különbö nbözı – két csú ú csa. Egy W vel jelö ö lt u – v s é ta a G grá á fban a csú ú cspontoknak és cs jel gr cs az éleknek egy olyan W: u = u0,e1,u1,e2,u2,….,uk-1,ek,uk = v véges, alterná alternáló sorozata, amely az u csú csúcsponttal kezdıdik, a v csú csúccsal vé végzıdik, és ei = ui-1ui mindig egy él, i=1,2,… i=1,2,…,k. A k szá számot a W séta hosszá á nak nevezzü ü k. hossz nevezz 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ü nevezünk attó attól fü függıen, hogy u = v vagy u ≠ v. A u-v ösvé svény az egy olyan u–v séta, amelyben él nem ismé ismétlıdik, és egy u–v út az egy olyan u–v séta, amelyben csú csúcspont nem ismé ismétlıdik. dik. Következmé vetkezményny-1: minden út egyben ısvé svény is. is. Következmé vetkezményny-2: Minden út egyben sé séta is, de a megfordí megfordítottja általá ltalában nem igaz.

Matematika I.


212

Példa: 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 , v3 , v 2 , v4

Matematika I.

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


213

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

Példa: 0  1 A= 1  0 

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

2

   =    

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

v2

v1

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

W1 : v1 , v3 , v1 , v3 W2 : v1 , v2 , v1 , v3

v3

W3 : v1 , v3 , v2 , v3

v4 Matematika I.

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

W4 : v1 , v3 , v4 , v3 Felsıfokú Szakképzés

214

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


215

Tétel: Egy G grá üggı” relá gráf csú csúcshalmazá cshalmazán értelmezett „összef „összefü reláció ció egy ekvivalancia relá reláció ció.

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

Matematika I.


0

v1

1

v6

2

v7

216

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í feszítı fa problé probléma Egy G grá gráf feszí feszítı fáján azt a feszí feszítı részgrá szgráfot értjü rtjük, amely fa. Tétel: Minden összefü sszefüggı fának van feszí feszítı részgrá szgráfja Biz. Biz.: Konstrukció Konstrukcióval. Vá Válasszunk egy tetszıleges x∊ V csú csúcspontot. Legyen Vi={ y ∊ G : d(x,y)= i, i=1,2,… i=1,2,…,M }.

Ha yi∊ Vi , i > 0 és x,z1,z2,…,zi-1,yi egy x – yi út, akkor d(x,z d(x,zj)= j, 0 < j < i. Az vilá világos, hogy Vj ≠ Ø, ha j < M, és bá bármely y ∊ Vi-hez, hez, i ≤ M, létezik legalá legalább egy y'∊ Vi-1, amely szomszé szomszédos y-nal. ({y' ({y',y} ∊ E(G)). Matematika I.


x

V0

218

…

V1

V2

VM-2

VM-1

VM

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


219

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

Az ilyen tulajdonsá tulajdonságú feszí feszítı részfá szfát gazdasá gazdaságos feszí feszítı fának nevezzü nevezzük.

Matematika I.


220

Egy való valós problé probléma: Egy adott ré régió gióban falvakat akarunk összekö sszekötni vízvezeté zvezetékkel. Ismerjü Ismerjük, hogy mennyibe kerü kerül az egyes flvak közötti vezeté vezetékek felé felépítése. Keressü Keressük meg azt a há hálózatot, mely a legkevesebb kö költsé ltséggel építhetı fel! Példa: 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ó legolcsóbb élet G-bıl, azaz azt az élet, amelyre f(e) ) minimá á lis. . f(e minim lis A kö következı élet a mé még ki nem vá választottak kö közül mindig úgy választjuk, hogy az a legolcsó legolcsóbb legyen. A vá választá lasztásná snál arra kell ügyelnü gyelnünk, hogy nem ké képezhetü pezhetünk kö körutat a kivá kiválasztott élekbıl. Ha ilyen él má már nincs, akkor vé véget ér az algoritmus. 1 3

2

4 3 3

2

4

5

f(T1)=15

1 3

2

4

Matematika I.


222

2. Algoritmus: Az algoritmus lé lényege az, hogy drá drága élet csak akkor szabad vá választani, ha biztosí biztosítani akarjuk a grá gráf összefü sszefüggıségét. Töröljü ljük tehá tehát a legdrá legdrágább élet a grá gráfbó fból mind mindaddig, amí amíg a grá gráf összefü sszefüggı marad. Ha ilyen él má már nincs, akkor vé 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ö legrövidebb út problé problémája Rendeljü Rendeljünk a G grá gráf minden (u,v )∊ E(G) éléhez egy w(u,v) w(u,v) függvé é nyt, é s nevezzü ü k ezt s ú lynak. . Azt a grá á fot, , amelynek élei ggv nevezz lynak gr fot súlyozva vannak, súlyozott grá gráfnak nevezzü nevezzük. Legyen w: E(G)→ℝ+ egy fü függvé ggvény. ny. Terjesszü Terjesszük ki a fü függvé ggvény definí definíció cióját egy grá gráf H ⊆ G részgrá szgráfjá fjára: w( H ) = ∑e∈E ( H ) w(e).

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


224

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


225

Elıkészí szítı lépés:

i = 0,

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

S 0 = { u 0 },

Iterá Iteráció ciós lé lépés:

Ha Si = V(G) akkor az algoritmus befejezıdik. 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ú csúcspontja. cspontja. Ha l(ui+1) = ∞ vagy ui+1 = v0 akkor az algoritmus megá megáll. 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' Dijkstra's Algoritmus Algoritmus bonyolultsá bonyolultsága? ga? n-ben polinomiá polinomiális: lis: O(n2). Példa: lda: v2

2

4

2

1 u0

7

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

v3

v1

Si

0

0

7

1

2

∞ u0

1 1

1

0

7

1

2

2

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

u0 v2

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


228

Matematika I.


229

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


230

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


232

Azt a kö körutat, amely tartalmazza a problé problémához tartozó tartozó grá gráf minden csú csúcspontjá cspontját, Hamilton körnek nevezzü nevezzük. Azt a grá gráfot, amelynek van Hamilton kö köre, Hamilton grá gráfnak nevezzü ü k . nevezz Az elnevezé elnevezés onnan ered, hogy Sir William Rowan Hamilton 18571857ben konstruá konstruált egy já játékot, amely sorá során a feladat az volt, hogy miké miként lehet a dodekaé dodekaéder csú csúcsaiba vert szö szögeken vé végigvezetni egy madzagot úgy, hogy minden csú csúcsot csak egyszer érintü rintünk. Ez volt 19. szá század “Rubik kocká 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ö köröket (é (és Hamilton utakat) má már korá korábban is vizsgá vizsgáltak. 17591759-ben Euler tanulmá tanulmányozta azt a problé problémát, hogy lehetsé lehetségesges-e a huszá huszárral bejá bejárni a sakktá sakktábla mind a 64 mezıjét úgy, hogy minden mezıt érintü rintünk, egyikre sem lé lépünk ké kétszer, és a vé végén vissza jutunk a kiinduló ó pontra. kiindul

Matematika I.


235

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


236

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

Matematika I.


237

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

Matematika I.


238

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

Recommend Documents