Matematika I. Mőszaki informatikai mérnm. rnökasszisztens. Galambos GáborG JGYPK A Matematika I. fıbb f Halmazok: Alapfogalmak, mőveletek m

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á Reláció ciók: Alapfogalmak, relá reláció ciók tulajdonsá tulajdonságai (reflexí (reflexív, szimszimmetrikus, metrikus, tranzití tranzitív, ekvivalencirelá ekvivalencireláció ció, trichotó trichotómia, 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é é nyekkel, speciá á lis fü ü ggvé é nyek (pl. rekurzí í v fü ü ggvé é ggv speci f ggv rekurz f ggv nyek). Matematikai Logika: Alapfogalmak, logikai mő mőveletek, logikai függvé ggvények, kö következteté vetkeztetések és szabá szabályaik. A lineá lineá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á kombináció ciók, binomiá binomiális együ együttható tthatók, variá variáció ciók. Grá Gráfelmé felmélet: Alapfogalmak, grá gráfok ábrá brázolá zolása, klasszikus grá gráfbejá fbejárások, sok, pá párosí rosítások, magyar mó módszer, fagrá fagráfok. fok.

Matematika I. Mőszaki informatikai mé mérnö rnökasszisztens

Galambos Gá Gábor JGYPK 20082008-2009 Matematika I.

Felsıfokú Szakképzés

1

Matematika I.


2

1

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álszálható függvények vizsgálata: Integrálszámítás:

Matematika I.


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ó”)

3

Matematika I.


4

2

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.

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 ∉ ℕ.

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.

Bármely halmazt egyé egyértelmő rtelmően meghatá meghatározzá rozzák az elemei: ha H egy halmaz, akkor bá á rmely x dologra vagy x ∊ H vagy x ∉ H áll fenn. b 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.

Georg Cantor (1845-1918) alapozta meg a halmazelmélet fogalmát. Matematika I.


5

Matematika I.


6

3

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.

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:

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}.

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

Halmazok ábrá brázolá zolása: VennVenn-diagram

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é Ezért A = ∅. Matematika I.


7

Matematika I.


8

4

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.

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:

Autó Autók

Szemé Személyautó lyautók 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

Matematika I.


10

5

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.

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

Az üres halmaz minden halmaznak ré részhalmaza.

H

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.

A’ A

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

Matematika I.


12

6

Mőveletek halmazokkal

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 vontakoztatott komplekomplementeré menterének a komplementere maga a halmaz. Ha ké két halmaznak ugyanarra a halmazra vonatkoztatott komplekomplementere egyenlı ı , akkor a ké é t halmaz is egyenlı ı egymá á ssal. (Ez egyenl k egyenl egym megfordí megfordítva is igaz.)

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 ∊ 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, {1, 2, 3} 3} és B = {e, {e, f} f} e

A×B=

Matematika I.


13

Matematika I.

f

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


14

7

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ő mővelete nem kommutatí kommutatív. (Nem felcseré felcserélhetı lhetı). A szorzathalmaz kettı 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ı lehetıvé teszi matematikai alakzatok konstrukció konstrukcióját is:

ℕ Matematika I.


15

Matematika I.


16

8

Asszociativitá Asszociativitás

A mő mőveletekrı veletekrıl általá ltalában Egy H halmazon értelmezett (belsı (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 f(x,y)) ∊ H Három alapvetı alapvetı mőveleti tulajdonsá tulajdonságot fogunk definiá definiálni:


Ha egy mő 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ő 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ő mővelet a hatvá hatványozá nyozás, hiszen

(2 )

3 2

Asszociativitá Asszociativitás (csoportosí (csoportosítható thatóság) Kommutativitá Kommutativitás (felcseré (felcserélhetı lhetıség) Disztributivitá Disztributivitás (szé (széttagolható ttagolhatóság) Matematika I.

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 .

2 ≠ 2 (3 )

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

17

Matematika I.


18

9

Kommutativitá Kommutativitás

Disztributivitá Disztributivitá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.

Legyen adott a H halmazon értelmezett ké két mő mővelet • és ⎕. A • mőveletet balró disztributív a ⎕ mőveletre né nézve, ha bá bármely x, y z balról disztributí ∊ H elemre fenná fennáll, x • (y ⎕ z) = (x (x • y) ⎕ (x • z) .

Ha egy mő mővelet kommutatí kommutatív, akkor a mő mővelet eredmé eredménye fü független a mőveletben ré résztvevı sztvevı elemek sorrendjé sorrendjétıl • Kommutatí Kommutatív mő 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á á s utá á ni vé é grehajtá á sa. egym ut v grehajt • Nem kommutatí kommutatív mő mővelet a kivoná kivonás, hiszen 5 – 3 ≠ 3 – 5.

Matematika I.


Legyen adott a H halmazon értelmezett ké két mő mővelet • és ⎕. A • mőveletet jobbró disztributív a ⎕ mőveletre né nézve, ha bá bármely x, y z jobbról disztributí ∊ H elemre fenná fennáll, (x ⎕ y) • z = (x (x • z) ⎕ (x • y) . Ha egy mő 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ő egyszerően disztributí vitásró sról beszé beszélünk. disztributívitá A való valós szá számok kö körében definiá definiált szorzá szorzás mő mővelete disztributí disztributív az ugyanitt definiá definiált összeadá sszeadás mő mőveleté veletére né nézve.

19

Matematika I.


20

10

Zártsá rtság

Halmazok unió uniója

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.

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.

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á á sra né é zve zá á rt. szorz n z

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ó (egyesítésén) azt a halmazt értjü rtjük, amely unióján (egyesí 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.


21

Matematika I.


22

11

Az unió unióképzé pzés mő mőveleté veletének legfontosabb tulajdonsá tulajdonságai:

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.

Az unió unióképzé pzés mő mővelete kommutatí kommutatív. Az unió unióképzé pzés mő mővelete asszociatí asszociatív. Az unió unióképzé pzés mő mővelete idempotens: idempotens: A ∪ A = A. A ∪ ∅ = A.

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ö közös osztó osztóinak halmaza.

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

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éne eleme. Jelö Jelölése: A1 ∩ A2 ∩ … ∩ An.

Matematika I.


24

12

Az metszetké metszetképzé pzés mő mőveleté veletének legfontosabb tulajdonsá tulajdonságai:

Bizonyí Bizonyítsuk be, hogy unió unió a metszetké metszetképésre nézve disztributí disztributív!

Az metszetké metszetképzé pzés mő mővelete kommutatí kommutatív.

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

Az metszetké metszetképzé pzés mő mővelete asszociatí asszociatív. A ∪ (B ∩ C )

Az metszetké metszetképzé pzés mő mővelete idempotens: idempotens: A ∩ A = A. A ∩ ∅ = ∅.

A

A ∩ B = A akkor és csak akkor, ha A ⊆ B.

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

B

A

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épésre nézve disztributí disztributív. A metszet az unió unióképzé pzése né nézve disztributí disztributív.

Matematika I.


C

25

Matematika I.

C Felsıfokú Szakképzés

26

13

Halmazok kü különbsé nbsége

Szimmetrikus differencia

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ő 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 = A' . 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 (diszjunktak). A \ ∅ = ∅ és ∅ \ A = ∅ és A \ A = ∅. A kü különbsé nbségké gképzé pzés mő mővelete nem kommutatí kommutatív. A kü különbsé nbségké gképzé pzés mő mővelete nem asszociatí asszociatív. Matematika I.


27

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ı vetkezı tulajdonsá tulajdonságok kö következnek: A∆A=∅ A∆B=B∆A A ∆ ∅ = ∅ ∆ A = A. ( A ∆ B ) ∆ C = A ∆ ( B ∆ C ) ( a mő mővelet asszociatí asszociatív). Matematika I.


28

14

Szá Számhalmazok

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

A

Termé Természetes szá számok A termé természetes szá számok halmazá halmazát a Peano axó axómákkal (1889) írhatjuk le.

B

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ı nthetık, azaz amelyeknek bizonyí bizonyítása és cá cáfolata az adott rendszeren belü ü l nem vé é gezhetı ı el. bel v gezhet C

Matematika I.


29

Matematika I.


30

15

A Peano axió axiómák:

A Peano axió axiómák (formalizá (formalizáltan):

1. A 0 termé természetes szá szám, azaz 0 ∊ℕ.

1. 0 ∊ ℕ.

2. Bármely n termé természetes szá számnak lé létezik egy és csak egy – az n szá számtó mtól kü különbö nbözı – n' rákövetkezı vetkezıje, amelyik szinté szintén termé természeszetes szá szám.

2. Ha n ∊ ℕ, akkor n' ∊ ℕ.

3. Nincs olyan termé természetes szá szám, amelynek a 0 a rá rákövetkezı 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ı 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ı vetkezıje is a K halmazban van, akkor K = ℕ.

Matematika I.


31

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

16

Az 55-ös axió axiómát szoká szokás a teljes indukció axiómájának nevezni. indukció axió Legyen α(n) minden n ∊ ℕ-re értelmezett állí llítás, és tegyü tegyük fel, hogy teljesü teljesül a kö következı 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é é n igaz. eset

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ı vetkezı két felté feltétel: az α(k) állí llítás igaz, ha valamely n ∊ ℕ eseté esetén α(n) igaz, akkor α(n+1) n+1) is igaz, Ekkor α(n) minden k ≤ n ∊ ℕ eseté esetén igaz. Felsıfokú Szakképzés

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

A teljes indukció axiómájának vá változata: ltozata: indukció axió

Matematika I.

Nézzü zzünk egy teljes indukció indukciós bizonyí bizonyítást: Bizonyí Bizonyítsuk be, hogy az elsı elsı n termé természetes szá szám összege n ( n + 1) S (n ) = . 2

33

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

17

Egé Egész szá számok

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

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ő mőveleté veletét. A halmaz kiterjeszté kiterjesztésénél tartsuk be a kö következı 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ı gezhetı a kivoná kivonás mővelete. • Az összeadá sszeadás és a szorzá szorzás mő mőveleté veletét úgy kell értelmezni az új halhalmazon, mazon, hogy ha a mő mőveleteket ℕ-beli elemekre alkalmazzuk, akkor ugyanazt az eredmé eredményt kell kapnunk, mint korá korábban. • Érvé rvényesü nyesüljö ljön a permanencia elve, azaz mő mőveletekre miné minél tö több azonossá azonosság maradjon érvé rvényben.

Matematika I.


35

Matematika I.


36

18

Az n termé természetes szá ellentettjének nevezzü nevezzük, és –n-nel jelö jelöljü ljük az szám ellentettjé 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ı megfelelıen az összeadá sszeadás az egé egész szá számok halmazá halmazán a kö következı vetkezıképpen értelmezhetı rtelmezhetı: Tetszı 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ó való osztá osztását jelö jelöljü ljük p/qp/q-val, és ezt egy új szá 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ı 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ı nevezıje 1. A racioná racionális szá számok halmazá halmazán a racioná racionális mő mőveletek – összeadá sszeadás, kivoná kivonás, szorzá szorzás, osztá osztás – elvé elvégezhetı 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

19

Amennyiben azt akarjuk, hogy a

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

kedjenek, kedjenek, mint az egé egész szá számok tová továbbá bbá az eddigi mő 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á á lni: vetkez defini

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 

a c ad + bc + = b d bd = 3 + 21 ⋅

a c ac ⋅ = b d bd

1 1 21 100 21 318 ⋅ = 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.


39

Matematika I.


40

20

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á számtó mtól elté eltérı – újabb racioná racionális pont.

⇩

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

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

2 nem írható rható fel

p alakban, ahol p,q ∊ℤ. q

Biz.

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

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


41

Matematika I.


42

21

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.

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. ℚ* = ℝ ∖ ℚ.

A racioná racionális pontok bá bár mindenü mindenütt ső 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.

Termé Természetes szá számok

Egé Egész szá számok

Racioná Racionális szá számok

Való Valós szá számok

A szá számegyenes pontjainak megfeleltethetı megfeleltethetı szá számok halmazá halmazát a való valós szá számok alkotjá alkotják. Jele: ℝ.

Matematika I.


43

Matematika I.


44

22

Algebrai és transzcendens szá számok

Polinomokró Polinomokról általá ltalában

Láttuk azt, hogy a szá számhalmazok kö között a való valós szá számok halmaza a legtá legtágabb halmaz, amely ké két diszjunkt halmazra – a racioná 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?

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

Kis kité kitérı következik

A monomokban lévı szá számszorzó mszorzókat a polinom együ tthatóinak együttható hívjuk.

Matematika I.


45

Matematika I.


46

23

Mőveletek polinomokkal Az egyes monomokban a vá változó ltozók kitevı 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ő Egynemőnek nevezü nevezünk egy monomot, monomot, ha csak együ együttható tthatóban különbö nböznek.

A polinomok szorzá beszorzunk” szorzásakor „minden tagot minden taggal beszorzunk” és a keletkezı 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

Polinomokat úgy adunk össze, ssze, hogy az egynemő 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

Matematika I.


48

24

Speciá Speciális polinomok A polinomok legegyszerő legegyszerőbb megjelené megjelenési formá formái az egyvá ltozós egyváltozó 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ı kkenı sorrendbe írva, az elsı elsı monom foka 3, a má á sodiké é 2, a harmadiké é 0. m sodik harmadik

Egy a szá számot algebrai szá nevezünk, ha lé létezik olyan racioná racionális számnak nevezü együ együttható tthatós polinom, amelynek a gyö gyöke. 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á már nem gyö gyöke, akkor a egy n-ed fokú fokú algebrai szá szám.

A harmadfokú harmadfokú tag együ együttható tthatója 8, a má másodfokúé sodfokúé -7, a konstans tag 36.

Tétel: az elsı elsıfokú fokú algebrai szá számok a racioná racionális szá számok.

Egy polinomot homogé homogén fokszá fokszámúnak nevezü nevezünk, ha benne minden monom foka egyenlı egyenlı. Pl. a binomiá binomiális té tétel:

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

(a + b) b)4 = a4 + 4a 4a3b + 6a 6a2b2 + 4ab 4ab3 + b4 Matematika I.


49

Matematika I.


50

25

Szá Számhalmazok szá számossá mossága

Az irracioná irracionális algebrai szá számok megkö megközelí zelíthetı 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

Végtelen halmazok Termé Természetes szá számbó mból vagy a né négyzeteikbı gyzeteikbıl van tö több?

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.

Az A és a B halmazró halmazról akkor mondjuk, hogy egyenlı számossá mosságúak, ak, egyenlı szá ha van olyan kö kölcsö lcsönösen egyé egyértelmő rtelmő megfelelteté megfeleltetés az elemeik között, amely A minden elemé eleméhez B egy meghatá meghatározott elemé elemét rendeli hozzá hozzá, és amely B minden elemé elemét hozzá hozzárendeli A valamely elemé eleméhez.

a = 1+

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

0

1

2

3

4

↑↓

↑↓

↑↓

↑↓

↑↓

0 Matematika I.


51

Matematika I.

1

4

9

16


n …

↑↓

…

n2 52

26

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ı meglepı,hiszen azt kaptuk, hogy a „rész” sz” ugyanannyi, mint az „egé egész” sz”!

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ü nevezzük azokat a halmazokat, amelyeknek ugyanannyi elemü elemük van, mint amennyi termé é szetes szá á m. term sz

⇩

⇩

Ha A megszá megszámlá mlálható lható halmaz, akkor elemei kö kölcsö lcsönösen megfelelmegfeleltethetı tethetık a termé természetes szá számok halmazá halmazának elemeivel.

Végtelen halmazok eseté esetében nincs értelme a „több” bb”, a „kevesebb” kevesebb” vagy az „ugyannyi” ugyannyi” kifejezé kifejezéseknek.

Könnyő 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?

Végtelennek nevezzü nevezzük azt a halmazt, amelynek van önmagá nmagával egyenlı egyenlı szá számossá mosságú való valódi ré részhalmaza. Matematika I.


53

⇩

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


54

27

Ha az elemek sorbarendezhetı 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ı 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ő Egyszerő példá ldák: A pozití pozitív pá páros szá számok és a prí prímszá mszámok halmaza megszá megszámlá mlálható 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ó.

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 = {a {a1, a2, a3, a4, …,an, …} az adott megszá megszámlá mlálható lható halmaz és b1, b2, b3, …, bk a vé véges halmaz elemei, akkor az új halmaz elrendezé elrendezése: b1, b2, b3, …, bk, a1, a2, a3, a4, …,an, … és a hozzá hozzárendeleé rendeleé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 sorbarendezé sorbarendezés más módon elé elérhetı rhetı: 0 1 2 3 4 5 …

↑↓

Bizonyí Bizonyítás egyszerő egyszerő.

0

Matematika I.


55

Matematika I.

↑↓ -1

↑↓ 1

↑↓ -2

↑↓ 2

↑↓

-3


… 56

28

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ó.

Az elı elıbbi állí llítás bizonyí bizonyításához elı 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ı vetkezı elrendezé elrendezést:

Á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í egyesítésével kapott halmaz is megszá megszámlá mlálható 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

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á á blá á zatbó t bl zatból az egyszerő egyszerősíthetı 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

29

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 (p,q)) alakú alakú rendezett pá párokat írunk, akkor azt kapjuk, hogy a poztí poztív egé egész szá számokbó mokból ké képezhetı pezhetı rendezett pá párok halmaza is megszá megszámlá mlálható lható.

Kontinuum szá számossá mosságú halmazok Vizsgá Vizsgáljuk meg a való valós szá számok halmazá halmazát, és bevezetı 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ı esı való valós szá számok halmaza – mint a való valós szá á mok halmazá á nak vé é gtelen ré é szhalmaza – megszá á mlá á lható ó . sz halmaz v r megsz ml lhat Ezé Ezért ebbe az intervallumba esı esı elemek sorozatba rendezhetı rendezhetık. Legyen a sorozat tagjainak tizedestö tizedestört kifejté kifejtése a kö következı vetkezı: a1 = 0, a11a12 a13a14 ...

a2 = 0, a21a22 a23a24 ... a3 = 0, a31a32 a33a34 ... ahol ank az n-dik való ó s szá val szám k-dik tizedesjegyé tizedesjegyét jelö jelöli. Matematika I.


59

Matematika I.


60

30

A vé végtelennek ezt a má másik „fokozatá fokozatát” – Cantor nyomá nyomán – kontikontinuumszá á mossá á gnak nevezzü ü k. nuumsz moss nevezz

Most állí llítsuk elı elı a

b = 0 , b1b 2 b3 b 4 ... szá számot a kö következı vetkezıképpen:

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ó.

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í szíthetı thetı, ezé ezért a (0,1 (0,1)) intervallum való valós szá számainak halmaza nem megszá megszámlá mlálható lhatóan vé végtelen. Egy olyan halmazhoz jutottunk, amelyben az elemek szá száma tö több. Matematika I.


61

Cantor: 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

31

Relá Reláció ciók, fü függvé ggvények

Egy A halmaz összes ré részhalmazainak halmazá halmazát az A hatvá hatványhalnyhalmazá mazának nevezzü nevezzük. Jele: P(A).

A mindennapi életben kapcsolatok vesznek körüll bennü bennünket: Szü Szülı – gyermek Adó Adós – hitelezı hitelezı Eladó Eladó – vevı vevı stb… stb…

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

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 bb-vel).

Matematika I.


64

32

Pl. Pl. Pl. Legyen H = {1, 2, 3, 4, 5}. Az a ℜ b jelentse: a kisebb b-nél. Elı 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

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ı 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é hurokéllel jekö jeköljü ljük.) 10

8 5

2

4

5 2

3

4

3


7 9

Mely szá számokat jelö jelölik az egyes pontok?

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

6

65

Matematika I.


66

33

Biné Binér (ké (kételemő telemő) relá reláció ció Az A és B halmazok kö közötti biné binér ℜ relá reláció ció az az (a, b) b) (a (a ∊ A, b ∊ B) rendezett pá párok egy ré részhalmaza. A ré részhalmaznak azon (a, (a, b) b) 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} éa 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á Gráffal 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

34

Biné Binér relá reláció ciók tulajdonsá tulajdonságai Ha ℜ a H halmazon értelmezett relá reláció ció, és a 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:

h1

h1

69

h4

h5

h1

h2

h5

h4

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


h3

h2 h3 h4 h5

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ı egyenlı b-vel.

Matematika I.

h2

Matematika I.


h3

70

35

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:

h1

h1

71

h4

h5

h1

h2

h5

h4

Hogyan né néz ki a relá reláció ció, ha azt tá táblá blázatosan vagy grá gráffal adjuk meg? Felsıfokú Szakképzés

h3

h2 h3 h4 h5

A pozití pozitív termé természetes szá számok halmazá halmazán: a egyenlı 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í sík valamennyi egyenesé egyenesének a halmazá halmazán: a merı merıleges b-re. A való valós szá számok halmazá halmazán: a nem egyenlı egyenlı b-vel.

Matematika I.

h2

Matematika I.


h3

72

36

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. 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ı ellenkezı esetben tágabb értelemben antiszimmetrikus.

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:

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ı vetkezıje” je” b-nek.

A pozití pozitív termé természetes szá számok halmazá halmazán: a kisebb b-nél. A pozití pozitív termé természetes szá számok halmazá 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. A ré részhalmaza BB-nek (A (A ⊆ B).

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


73

Matematika I.


74

37

Ekvivalenciarelá Ekvivalenciareláció ciók A reflexí reflexív, szimmetrikus és tranzití tranzitív relá reláció ciót ekvivalencirelá ciónak ekvivalencirelá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ı 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 (A ⊆ B). Matematika I.


75

Egy nevezetes ekvivalencia relá reláció ció a kongruencia relá reláció ció: Legyen 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 (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ögzí gzítjü tjük. Bizonyí Bizonyítsuk be (esetleg a gyakorlaton), hogy a kongruencia ekviekvivalenciarelá valenciareláció ció.

Matematika I.


76

38

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 (T(a) ⊂ T ).

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á 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.

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

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ı vetkezı relá reláció ciót: ω ℜ ω' , ahol ω = a / b és ω' = a' / b' b' és a b' b' = a' b, b ≠ 0.

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ő 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).

Ezé Ezért pé példá ldául

Matematika I.


77

3 5

ℜ

6 . 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

39

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 (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). mia).

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ı kezdı eleme, azaz olyan eleme, amelyet – az adott rendezé rendezés szerint – az adott ré részhalmaz egyetlen eleme sem elı 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ólrendezett halmaz. Bizonyí Bizonyítsuk be, hogy a racioná racionális szá számok halmaza nem jólrendezett! lrendezett!

Matematika I.


79

Matematika I.


80

40

Ha minden a ∊ A-ra (a (a; φ(a)) ∊ A × B, akkor a φ relá reláció ciót leké pezésleképezé nek nevezzü nevezzük.

Függvé ggvények Ha valamely A halmaz elemeihez adott utasí utasítás szerint egy B halmaz elemeit rendeljü rendeljük hozzá hozzá úgy, hogy A minden elemé 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ü ü nk. pez 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ı elıírás és a tá tárgyhalmaz egyé egyértelmő rtelmően meghatá meghatározza. Jelö Jelölése: φ: A → B, vagy a → φ(a), ha a ∊ A. Matematika I.


81

A φ és δ leké leképezé pezéseket akkor tekintjü tekintjük egyenlı egyenlınek, nek, ha bá bármely a ∊ A eseté esetén φ(a) = δ(a). 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ő rtelmő vagy kölcsö lcsönösen egyé egyértelmő rtelmő.

B

A Matematika I.


82

41

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

B

A


B

A

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

Matematika I.

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

Pl. anya → gyerekei

83

Matematika I.


84

42

A fü függvé ggvény mint leké leképezé pezés

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ő rtelmő.

Legyen adott ké két halmaz, A és B. Függvé ggvénynek nevezü nevezünk minden olyan biné binér (ké (kételemő 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 minden relá reláció ció függvé ggvény: a fü függvé ggvény egy A halmaznak egyé egyértelmő rtelmő leké leképezé pezése egy B halmazra.

B

A

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).

Pl. tulajdonosok → cégek

Matematika I.


85

Matematika I.


86

43

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é é nyt szü ü rjektí í vnek nevezzü ü k. ggv sz rjekt nevezz Ha az A halmaz ké két kü különbö nbözı elemé elemének mindeig különbö nbözık a B-beli 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érelmő relmő, 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 descardes diagram Venn diagram Függvé ggvények ábrá brázolá zolása utasí utasítással

Példá ldául: f: ℝ Matematika I.

→ ℝ, f(x) = 2x2 – 3. Felsıfokú Szakképzés

88

44

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

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

a1 a2 a3 a4 a5

b1

b2 +

b3

b4

b5

+ + + +

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

Matematika I.


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

Matematika I.


90

45

Az összetett fü függvé ggvény

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

B

A

Legyen adott há három halmaz, A, B, C, C, és legyen f az A egy leké leképezé pezése B-be, és g a B leké leképezé pezése C-be. 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á definiált hozzá hozzárendelé rendelés leké leképezte az A halmazt a C halmazba: z = g( g(f(x)). Ez az új leké leképezé pezés az f és g függvé ggvénybı 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.

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

Matematika I.


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á utáni vé végrehajtá grehajtását értjü rtjük ebben a sorrendben. (Az f függvé ggvény érté rtékké kkészleté szletét tartalmazni a kell a g függvé ggvény értelmezé rtelmezési tartomá tartományá nyának!) 91

Matematika I.


92

46

Inverz fü függvé ggvény

Tétel: 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.

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ő 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ő 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.

Ekkor g ∘ f = cos (2x (2x2 – 3 ) és f ◦ g = 2 cos2 x – 3.

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

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. nya. Matematika I.


93

Matematika I.


94

47

Ha az (x (x, f(x)) az f grafikonjá grafikonjának egy pontja, akkor az (f (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

Rekurzí Rekurzív sorozatok Oldjuk meg a kö következı vetkezı feladatot: feladatot: Há Hány nyú nyúl szá származik egyetlen pá pár nyú ú ltó ó l, ha tudjuk, hogy minden pá á r havonta ú j pá á rnak ad é letet, és ny lt p p 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ú nyúlpá lpár 1

f -1(x) = log2 x

2 1

3 2

4 3

5 5

6 8

7 13

8 21

9 35

10 56

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

Matematika I.


95

Matematika I.


96

48

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

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

A sorozat n. eleme 11-gyel nagyobb, mint az elsı 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éges sok, vagy vé végtelen sok prí prímszá mszám vanvan-e?

Matematika I.


97

Az ”a tá táncolt bb-vel” vel” relá reláció ció egy alaphalmazon értelmezett tulajdontulajdon-ság. Ha az (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ı 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ü kijelentésfü függvé ggvényt kijelenté sfüggvé ggvénynek (predik (predikáátumfü tumfüggggvénynek) nynek) nevezzü nevezzük.

Matematika I.


98

49

A matematikai logika alapjai A logika a gondolkodá gondolkodás tá tárgyá rgyát ké képezı pezı konkré konkrét problé problémáktó któl, tartalmi informá á ció ó któ ó l elvonatkoztat, é s a gondolkodá á si folyamat inform ci kt gondolkod elemeinek, megá kö a kö megállapí llapításainak közös, következteté vetkeztetés szempontjá szempontjából lé lényeges tartalmá tartalmát haszná használja fel. Ez a kö közös tartalom, vagy kö közös jellemzı jellemzı az állí llítások igazsá igazságérétke, tke, 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á gondolkodás ké kérdé rdéseit klasszikus – kétérté rtékő – logiká 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á á g é rté é k bizonytalansá á got nem tartalmaz, a ké igazs rt bizonytalans két igazsá igazságérté rték kizá kizárja egymá egymá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ı nthetı róla, hogy igaz vagy hamis. Többé bbérté rtékő logiká logikák lé létezé tezése: fuzzy logika A matematikai logiká logikát elsı 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 inteligencia is alkalmazza a matematikai logiká logikát. A matematikai logika kiemelkedı kiemelkedı alakjai: • Gottfried Wilheim Leibnitz (1646 – 1716) • George Boole (1815 – 1864) Matematika I.


100

50

Állí llításon vagy kijelenté kijelentésen olyan kijelentı kijelentı mondatot értü rtünk, amely egyé egyértelmő rtelmően iga vagy hamis. Egy állí llítás egyidejő egyidejőleg nam 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é nélkü lkül az állí llításnak nincs meghatá meghatározott igazigazságérté rtéke. ke. • ”az út holnap csú csúszó szós lesz” lesz”, mert az adott pillanatban nem dönthetı 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ő mőveleten olyan eljá eljárást értü rtünk, amely egy vagy tö több kijelenté kijelentésbı sbıl (ezek a mő 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ő 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ı sbıl ké képeznek új kijelenté kijelentést. Az állí llítások kö körében is elegendı elegendı a logikai érté rtékek kö közötti mőveleteket tisztá tisztázni.

Matematika I.


102

51

Negá Negáció ció

Konjunkció Konjunkció

Egy p kijelenté kijelentés negá negáció cióján (tagadá (tagadásán) a ”nem igaz, hogy p” kijelenté é st (vagy ennek egy nyelvtanilag átfogalmazott alakjá kijelent alakját) értjü rtjük.

Két kijelenté kijelentés, p és q konjunkció sszekapcsolásán) a ”p és q” konjunkcióján (összekapcsolá 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á á ltozó ó s egyv ltoz í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 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ı 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

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

Matematika I.


p∧ q i h h h

104

52

Diszjunkció Diszjunkció Két kijelenté kijelentés, p és q diszjunkció (szétvá tválasztá lasztásán) a ”p vagy q” diszjunkcióján (szé kijelenté kijelentést (vagy ennek egy nyelvtanilag átfogalmazott alakjá alakját) értjü rtjük. (Megengedı (Megengedı értelmő rtelmő összekapcsolá sszekapcsolás.) ”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

Az ítéletkalkulusban a logikai érté rtékeket, a logikai vá változó ltozókat és a rajtuk vé végzett mő mőveleteket leí leíró jelsorozatokat az ítéletkalkulus formulá formuláinak nevezzü nevezzük. Két formulá nevezünk, nk, ha a ké két formula a benne szereplı szereplı formulát azonosnak nevezü változó ltozók minden lehetsé lehetséges érté rtékére ugyanazt a logikai érté rtéket állí llítja elı elı. Példa:

p∨ q

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.

i i i h

Elegendı Elegendı azt bebizonyí bebizonyítani, hogy az állí llítások a vá változó ltozók logikai érté rtékeire megegyeznek. 105

Matematika I.


106

53

Tehá Tehát azt kell igazolnunk, hogy p, q tetszı tetszıleges állí llítások eseté esetén a fönná nnállll-e a p ∨ (p ∧ q ) egyenlı egyenlıség. 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

Nem bizonyí bizonyítjuk, de megmutatjuk az elı elıállí llításokat:

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

Tétel: Bármely logikai mő mővelet kifejezhetı kifejezhetı a negá negáció ció és a konjunkció konjunkció mőveleté veletével.

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

i i h h

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

Matematika I.


107

Matematika I.

p

q ¬p ¬q

i i h h

i h i h

h h i i

h i h i

p∨r i i i h


¬(¬ p ∧ ¬ q ) i i i h

108

54

Tová További logikai mő mőveletek

A logikai mő mőveletek tulajdonsá tulajdonságai Logikai ”vagy” vagy”:

A ”p akkor q” alakú alakú kifejezé kifejezéseket impliká implikáció ciónak nevezzü nevezzük. (Itt p az elı elıtag és q az utó utótag.)

kommutatí kommutatív: p ∨ q = q ∨ p

asszociatí asszociatív: (p (p ∨ q) ∨ r = p ∨ (q ∨ r)

”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ı elıre .) Jelö Jelölése: p → q.

disztributí disztributív: p ∨ (q ∧ r) = (p (p ∨ q) ∧ (p ∨ r) idempotens: idempotens: p ∨ p = p Logikai ”és ”és”:

Az impliká implikáció ció mőveleté veletének igazsá igazságtá gtáblá blája:

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: idempotens: p ∧ p = p Matematika I.


109

Matematika I.


p

q

i i h h

i h i h

p→ q i h i i 110

55

Tétel: Az impliká implikáció ció nem kommutatí kommutatív és nem asszociatí asszociatív mő 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

”Egy né négyszö gyszög akkor és csakkor 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)

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


A ”ha p akkor q, és ha q akkor p” p” alakú alakú kifejezé kifejezéseket ekvivalenciá ekvivalenciának nevezzü nevezzük.

111

Az ekvivalencia mő 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

56

A ”nem igaz, hogy ha p akkor q, és ha q akkor p” p” alakú alakú kifejezé kifejezéseket antivalenciá antivalenciának nevezzü nevezzük.

A ”sem p sem q” alakú alakú összetett kifejezé kifejezéseket semsem-sem (Webb (Webb--féle) le) mőveletnek nevezzü nevezzük.

A mő 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ő mővelet a diszjunkció diszjunkció tagadá tagadása (NOR). Jelö Jelölése: p ↓ q.

A mő 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 )

Érvé rvényes a kö következı vetkezı azonossá azonosság: 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

A WebbWebb-féle mővelet igazsá igazságtá gtáblá blája: p↓q=q↓p

113

Matematika I.


p

q

p↓q

i i h h

i h i h

h h h i 114

57

A ”nem p vagy nem q” alakú alakú kifejezé kifejezéseket Sheffer -féle mőveletnek nevezzü nevezzük.

A logikai fü függvé ggvény fogalma

”Vagy iszik az ember vagy vezet.” vezet.” A mő mővelet a konjunkció konjunkció tagadá tagadása (NAND). Ebben az esetben a ké két kijelenté kijelentés kö közül legfeljebb z egyik igaz. Jelö Jelölése: p | q.

Az eddigiekben ké kétvá tváltozó ltozós mő mőveleteket vizsgá vizsgáltunk, amelyek tekinthetı 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. 0. Az ilyen tí típusú pusú függvé ggvényeket igazsá igazságfü gfüggvé ggvénynek vagy BooleBoolefüggvé ggvénynek nevezzü nevezzük.

Érvé rvényes a kö következı 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

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. 115

Matematika I.


116

58

Hány darab n-változó ltozós BooleBoole-függvé ggvény van?

p 1 0 1 0 q 1 1 0 0

Az érté rtéktá ktáblá blázatnak n oszlopa van, és minden helyre vagy 00-t vagy n 1-et írunk. Ezé é rt ö sszesen 2 sorunk lesz. Ez Minden sorba ké kétfé tféle mó módon vá választhatjuk meg a fü függvé ggvényé nyértek, ti.

f1 f2 f3 f4 f5 f6 f7 f8

2n

vagy 00-t vagy 11-t. Így a Boole függvé ggvények szá száma: 2 . n 1 2 3 4 5 6 Matematika I.

2n 2 4 8 16 32 64

n

22 . 4 16 256 65536 4294967296 1,84 ·1019


117

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ővelet 118

59

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ó ltozóból épül fel, és mő mőveletké 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 1

x2 1

x3 1

g(x1,x2,x3) 0

1 1 1 0 0 0 0

1 0 0 1 1 0 0

0 1 0 1 0 1 0

0 0 1 0 1 1 0

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

Matematika I.


120

60

Eljá Eljárás-1: olyan formulá formulát állí llítottunk elı elı, amivel az érté rtéktá ktáblá blázattal megadott igazsá igazságfü gfüggvé ggvényt ki tudjuk fejezni. A formula jellemzı jellemzıi: a formula konjukció konjukciók diszjunkció diszjunkciója, ja, minden konjukció konjukció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é é ben kü ü l ö nbö ö znek. sorrendj k nb

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


121

x1 1

x2 1

x3 1

h(x1,x2,x3) 1

1 1 1 0 0 0 0

1 0 0 1 1 0 0

0 1 0 1 0 1 0

0 1 1 0 0 0 1

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

Matematika I.


122

61

Eljá Eljárás-2: olyan formulá formulát állí llítottunk elı elı, amivel az érté rtéktá ktáblá blázattal megadott igazsá igazságfü gfüggvé ggvényt ki tudjuk fejezni. A formula jellemzı jellemzıi: a formula diszjunkció diszjunkciók konjukció konjukciója, ja, minden diszjunkció diszjunkciós tag vagy egy vá változó ltozó vagy annak a negá negáltja, minden konjukció konjukció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 konjukció változó ltozók konjukciós tag, amelyek csak a vá sorrendjé sorrendjében kü különbö nböznek.

A fenti ké két elı elıállí llítás kö következmé vetkezménye, hogy a há három mő mővelet (¬ (¬, ∧, ∨) teljes fü függvé ggvényrendszert alkot, azaz bá bármely igazsá igazságfü gfüggvé ggvény elı elıállí llítható tható ezek segí segítsé tségével. Tétel: A negá negáció ció és konjunkció konjunkció és a negá negáció ció (¬, ∧) önmagukban is teljes fü 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ı kifejezhetı a fenti ké két mő mővelet segí segítsé tségével: p ∨ q = ¬(¬ p ∧ ¬ q )

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


123

Matematika I.


124

62

Logikai áramkö ramkörök Gyakorlat anyaga:

Gyakran elı elıfordul, hogy adott elemekbı elemekbıl kell összeá sszeállí llítani áramkö ramkört oly mó módon, hogy az elı elıre meghatá meghatározott gyakorlati cé célt elé elégítsen ki. A legegyszerő 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.

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

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é é tele, hogy a lá felt lámpa égjen: x1 ∧ x2 . Matematika I.


125

Matematika I.


126

63

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 .

Az automatá automaták A kibernetiká talakíító kibernetikában (informatiká (informatikában) a különflé nflée informá információá cióátalak eszkö eszközöket automatá automatáknak nevezzü nevezzük. Egy automatá automatának vé véges sok bemenete van, ezek kí kívülrı lrıl kapjá kapják az informá á ció ó t. inform ci Az automata mő mőködése úgy jellemezhetı jellemezhetı, hogy megadjuk a kimeneteken megjelenı megjelenı adatot a bemenı 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 nyí nyílvá lvá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.


127

Matematika I.


128

64

Egyszerő 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ő mővelet elı 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ö ö r ö k. Jellemzı ı ik: ramk Jellemz

A diszjunkció diszjunkciónak megfelelı 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:

A konjunkció konjunkciónak megfelelı 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ö Jelölése:

A negá negáció ciónak megfelelı 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:

VAGY

NEM

ÉS

Matematika I.


129

Matematika I.


130

65

A digitá digitális ké készü szülékek építıelemeinek legjelentı 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ı megfelelı áramkö ramkörökbı kbıl – így az ÉS, a VAGY és a NEM áramkö ramkörökbı kbıl – felé felépíthetı thetık. Példa

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

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

Matematika I.


132

66

A lineá lineáris algebra alapjai

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

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

a2 x + b2 y = c2 Az un. ”egyenlı 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ı elsıfokú fokú egyenletet má már egyszerő egyszerően megoldhatjuk.

Matematika I.


133

( a1b2 − a2b1 ) x = c1b2 − c2b1 Ebbı 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

67

Figyeljü Figyeljük meg a kapott megoldá megoldások szerkezeté szerkezetét! Mind a szá számlá mlálóban, mind a nevezı 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ő mőveleti utasí utasításra a kö következı vetkezı jelö jelölést: a b a1b2 − a2b1 = 1 1 . a2 b2

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

Ezt az új objektumot az a1, a2, b1, b2 szá számokbó mokból ké képzett másodrendő 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é mellékátló tló menté mentén fekszenek.

ahol

Egy má másodrendő 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ı fekvı szá számok szorzatá szorzatát.

Matematika I.


135

Dx =

c1 c2

b1 , b2

Dy =

a1 a2

c1 , c2

D=

a1 a2

b1 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á á mokat. sz Matematika I.


136

68

Példa:

A má másodrendő sodrendő determiná determináns tulajdonsá tulajdonságai

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

Tétel: A determiná determináns érté rtéke elı 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.

= 1 − 3 = −2 ≠ 0.

−

Dy =

1 7 1 5

y=

Dy D

= −2. −

=


a1 a2

b1 a = −(a1b2 − a2b1 ) = a2b1 − a1b2 = 2 b2 a1 b1 b = −(a1b2 − a2b1 ) = b1a2 − a1b2 = 1 b2 b2

b2 , b1 a1 . a2

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

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

a1 a2

137

Matematika I.


138

69

Következmé vetkezményny-2: Minden olyan té tétel, amely érvé rvényes egy másodrensodrendő determiná determináns soraira kimondva, érvé rvényes marad akkor is, ha azt a determiná determináns oszlopaira mondjuk ki.

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

a1 a1

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ı.

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

Biz.

a b a k 1 1 = k (a1b2 − a2b1 ) = a1kb2 − b1ka2 = 1 a2 b2 ka2

Következmé vetkezményny-3: Ha a má másodrendő 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.

b1 . kb2

Biz.

a1 ka 1 Matematika I.


139

Matematika I.

b1 a =k 1 kb 1 a1

b1 = 0. b1


140

70

Tétel: Ha má másodrendő sodrendő determiná determinánsban valamelyik sor 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 a 2 + c2

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

a 1 + ka 2 a2

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

=

Matematika I.

a1 a2

b1 c1 + b2 c2

b1 . b2


141

Matematika I.

b1 + kb 2 a = 1 b2 a2

b1 ka 2 + b2 a2

kb 2 = b2 b2 a = 1 b2 a2

=

a1 a2

b1 a +k 2 b2 a2

=

a1 a2

b1 . b2


b1 b2

142

71

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

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

a11

a12

a13

a21

a22

a23

a31

a32

a33

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

a11

a12

a13

a21

a22

a23 = a11a22 a33 + a12 a23a31 + a13 a21a32

a31

a32

a33

− a13a22a31 − a12a21a33 − a11a23a32.

Matematika I.


143

Matematika I.


144

72

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

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

a11

a12

a13

a21

a22

a23

a 11

a 12

a 13

a31

a32

a33

a 21

a 22

a 23 =

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

a11

a12

a13

a11

a12

a21

a22

a23

a31

a32

a33

a21 a31

a22 a32

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

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

a22

a23

a32

a33

− a12

a21 a23 a31 a33

+ a13

a21 a22 a31 a32

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


145

Matematika I.


146

73

Egy harmadrendő harmadrendő determiná determináns aij elemé eleméhez tartozó tartozó aldeterminá aldeterminánson azt a má másodrendő 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ó

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

a 11

a 12

a 13

a21 x1 + a22 x2 + a23 x3 = b2

a 21

a 22

a 23

a31 x1 + a32 x2 + a33 x3 = b3

a 31

a 32

a 33

Jelı Jelıljü ljük az egyenletrendszer determiná determinánsá nsát D-vel, és jelı jelılje Di azt a harmadrendő harmadrendő determiná determinánst, nst, amelyet D-bıl úgy kapunk, hogy D idik oszlopá oszlopát az egyenletrendszer jobboldalá jobboldalán álló lló érté rtékekkel helyettesí helyettesítjü tjük. Pl. a11 a12 b1

Jelö Jelölése:

A13 =

a21 a22 a31 a32

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


147

Matematika I.

D3 = a21

a22

b2

a31

a32

b3


148

74

Tétel(Cramer 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ı egyenlı, amelynek nevezı nevezıje a rendszer determiná determinánsa, szá számlá mlálója pedig Di:

xi =

Di , D

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

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

Matematika I.


150

75

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

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

6 x1 + 10 x2 + 3 x3 = 4 Az egyenletrendszer determiná determinánsa: 1 −2 1 D = 3 8 − 6 = 24 + 72 + 30 − 48 +18 + 60 = 156 6 10 3

x1 =

D1 104 2 = = D 156 3

x2 =

D2 − 39 1 = = D 156 4

Szá Számoljuk most ki a Di determiná determinánsok érté rtékeit:

x3 =

D 3 130 5 = = D 156 6

3 x1 + 8 x2 − 6 x3 = −5

2 −2 D1 = − 5 8 4 Matematika I.

10

1 − 6 = 104 3

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

4


D3 = 130

3 151

Az érté rtékek visszahelyettesí visszahelyettesítésével helyessé helyességét! Matematika I.

ellenı ellenırizzü rizzük


a

megoldá megoldás

152

76

Az n-ed rendő rendő determiná determinánsokra érvé rvényes té tételek I.

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

a21

a22 K a2 n

M an1

M O M an 2 K ann

n

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

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


153

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ı 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 oszlooszlo-pokra is.) A determiná determináns érté rtéke elı 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

77

Az n-ed rendő rendő determiná determinánsokra érvé rvényes té tételek II.

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

Ha a determiná determináns fı fıátló tlója felett (alatt) csupa zé zérus elem áll, akkor a determiná determináns érté rtékét a fı 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é sszegére, akkor a determiná determináns felí felírható rható ké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övekszik. (Kö (Következmé vetkezmény: ha a determiná determináns egyik sora egy má másik sor többszö bbszöröse, akkor a determiná determináns érté rtéke zé zérus.) 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

4

8

12

1

2

3

1

2

3

8 12

20 32

24 = 4 8 36 12

20 32

24 = 4 ⋅ 4 2 36 12

5 32

6 = 36

3 2 3 16 6 5 6 =0 3 9 8 9

Matematika I.


156

78

Mátrixok


100 101 102 103 101 102 103 104 102 103 104 103 104 105

105 106

=

100 1 2 101 1 2

3 3

102 103

3 3

1 2 1 2

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

=0

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


1 0

0 1

0 0

0 1 0 105

Matematika I.

0 0

0 0 0 1

=1

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. Felsıfokú Szakképzés

157

Matematika I.


158

79

Két má mátrix akkor és csak akkor egyenlı típusú pusúak, és az egyenlı, ha azonos tí 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.

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!

Speciá Speciális má mátrixok:

Példa:

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á mátrix: trix: aij = aji antiszimmetrikus mátrix: trix: aij = -aji , ha i ≠ j, és aii = 0 Matematika I.

Mőveletek má mátrixokkal


2  1

159

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

Matematika I.

1 3


4  4 

160

80

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:

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

 1 3  −1

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

cij = ai1b1 j + ai 2 b2 j + K + ain bnj = ∑ aik bkj

6  9 

k =1

Példa Legyenek A1, A2, …, An azonos tí típusú pusú mátrixok, és legyenek adotadot-tak 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

 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, mentes, de asszociatí asszociatív és az összessze-adá adásra né nézve disztributí disztributív. Matematika I.


162

81

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

Az En×n mátrixot egysé gmátrixnak nevezzü nevezzük, ha eii = 1, 1, és eij = 0, 0, ha egységmá i ≠ j.

Példa:

Egy A = (a (aij)n×n négyzetes má mátrix inverzé inverzén azt a A-1 = (a (aij)-1n×n mátrixot értjü rtjük, amelyre igaz, hogy

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

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

AA−1 = A−1 A = E

Példa:

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

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

Az A má mátrixot szingul szinguláárisnak nevezzü nevezzük, ha det A = 0

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 a szá számítás helyessé helyességét! Matematika I.


163

Matematika I.


164

82

Tétel: Legyen A invertá invertálható lható mátrix, az inverzé inverzét jelö jelölje B=( 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. 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

(−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 −3 det A Felsıfokú Szakképzés

(−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 ( −1) 3+ 2 det A23 − 1 1 b32 = = = det A −3 3

b23 =

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

b33 =

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

2

b11 =

Matematika I.

b21 =

165

Matematika I.

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

b31 =

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

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


166

83

Lineá Lineáris egyenletrendszerek  1   3 B= 1 − 2  3 

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

2  AB =  1 1 

Matematika I.

1 −1 1

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

1 3 −1 1 3

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

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


0 1 0

Legyen Amxn egy má mátrix, b1, b2, …, bm pedig skalá skalárok. 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

0  0 1 

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á á m á nak nevezzü ü k. sz nevezz

167

Matematika I.


168

84

Bevezetve az ismeretlenekbı ismeretlenekbıl és a jobb oldali skalá skalárokbó rokból 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á lineáris egyenletrendszerhez tartozó 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á lineáris egyenletrendszerrı egyenletrendszerrıl beszé beszélünk, mí míg ellenkezı ellenkezı esetben inhomogé inhomogén lineá lineáris egyenletrendszerrı 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 + a22ξ 2 + K + a2 nξ n = b2 L a m1ξ1 + am 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ı ettıl elté eltérı megoldá megoldást nemtriviá nemtriviális megoldá megoldásnak nevezzü nevezzük. Matematika I.


170

85

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 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ı egyenlı, amelynek nevezı nevezıje a rendszer determiná determinánsa, szá számlá mlálója pedig Di:

xi =

Di , D

i = 1,2, K, n.

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ü együttható ttható mátrixa háromszö romszög alakú alakú. Matematika I.


171

Matematika I.


172

86

Az algoritmus: algoritmus:

a11(0)x1+

A szá számítások befejezé befejezése utá után a következı vetkezı feladatot kapjuk: kapjuk:

a12(0)x2

+ …

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

…

+

a1n(0)xn

=

a(0)1n+1

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

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

a22(1)x2 +

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

a1n(0)xn =

a1n+1(0)

+

a2n(1)xn =

a2n+1(1)

…………………………………………………

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

ann(n-1)xn =

1. Minden 1 és n-1 közé esı esı i-re végezzü gezzük el a következı 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


173

ann+1(n-1)

Amibı Amibıl a megoldá megoldás:

a (jnj+−11 ) − xj =

(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.

…

+

Matematika I.

a

n

∑a

t= j+1 ( j −1 ) jj

( j −1 ) jt

xt ,


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

174

87

Mekkora a mőveletigé veletigény (osztá osztások és a szorzá szorzások szá száma) ma) ?

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

2x1 + 3x2 -

x1-x2-2x3 =1

x3 = 9

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

− x2 =

1 3 + 2 2 = 2 1 2 Felsıfokú Szakképzés

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

=

q3(1)= -5

q2(0)=1/2 q3(0)=1/2

Matematika I.

2x1 + 3x2 -

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

x1+2x2+x3 =4

A megoldá megoldás: x3 = - 1

x3 = 9

2 ∑ (n − j ) j =1

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

n −1

− 1) =

n−1

+ 2 ∑ (n − j ) j =1

2 n 3 + 3n 2 − 5n 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: x1 =

9 −(6 + 1) =1 2 175

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


176

88

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

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

1. Minden 1 és n-1 közé esı esı i-re végezzü gezzük el a következı vetkezıket: ket:

Biz.:

2. Legyen a kj( j − 1 ) = max a lj( n − 1 )

Mivel az A mátrix nem szingulá szinguláris, ezé ezért det(A)≠ 0.

j≤l≤ n

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ı fıátló tlóba esı esı elemek szerint:

3. Ha k ≠ j, akkor cseré cseréljü ljük meg a k. sort a j. sorral.

(1 ) ( 2 ) ( n −1 ) det( A ) = ± a 11( 0 ) a 22 a 33 K a nn ≠0

4. Folytassuk az eljá eljárást, a GaussGauss-eliminá elimináció ció (2) és (3) lé lépésével. Attó Attól fü függı ggıen, hogy pá páros vagy pá páratlan szá számú sorcseré sorcserét hajtottunk végre. Matematika I.


177

Matematika I.


178

89

Hatá Határozzuk meg a az elı elızı egyenletrendszer megoldá megoldását a fı 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

Matematika I.

2x1 + 3x2 -

x3 = 9

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

x3 = 9

5 1 9 - x2 - x3 = − 2 2 2 14 14 x3 = 10 10 Felsıfokú Szakképzés

2x1 + 3x2 -

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

x3 = 9

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

q3(1)= 1/5 1/5

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

Teljes fı 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 } x3=-1, x2=2, x1=1 179

Matematika I.


180

90

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

j=1

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

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 ) − xp j = Matematika I.

j ≤ n -1

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)

t = j +1 ( j −1 ) jj

a

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

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

n

∑ a(jtj −1 ) x pt

3x2 + 2x1 -

VÉGE 181

Matematika I.


182

91

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

3x2 - x3 +

Gauss-Jordan elimináció

2x1 = 9

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

a11x1 + a12x2

+ …

+ a1nxn

a21x1 + a22x2

+

+ a2nxn = a2n+1

…

= a1n+1

………………………………………………… p = (2,3,1) an1x1 + an2x2 q3(1)= -5/7

+ …

+ annxn

= ann+1 ahol ain+1=bi

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

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

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


183

Matematika I.


184

92

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

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

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

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

(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) (1) (0)x + (1)x an1(0)x1+ an2(1) … + ann(0) n = a nn+1 2

1. Minden 1 és n-1 közé esı esı i-re végezzü gezzük el a következı vetkezıt: (i-1) az egyenletrendszer j. sora az i. lépésben. 2. Legyen sj(isben. Tegyü Tegyük fel, fel, (i-1)≠0. hogy aii(i-

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

(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.


s1(1)=s1(0)/a11(0),

185

Matematika I.


j=2, …,n

186

93

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

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

2x1+3x2-x3=9

………………………………………………… an2(0)x2 + … + ann(1)xn = a(0)nn+1

x1+2x2+x3 =4

2 1

x1-x2-2x3 =1

1

1

s1(1)=s1(0)/a11(0),

0

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

Matematika I.


j=2 ,…, n

0 187

3 2 1 2 5 − 2

Matematika I.

1 2 3 2 3 − 2

9 2

−

− −

1 2 7 2

=

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

1 0 −5 0 1 3 0 0


6

6 − 1 − 6

=

=

188

94

Mátrix invertá invertálása GaussGauss-Jordan eliminá elimináció cióval

1 0 −5 0 1

3

6 − 1

0 0 6 − 6

=

1 0 0

1

0 1 0

2

0 0 1

− 1

Az elı elızıekben leí leírt mó módszer egyszerő 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é egységmá gmátrixszá trixszá alakí alakítottunk: E k E k −1 K E1 A = I

A má mátrix tehá tehát invertá invertálható lható és inverze: Amibı Amibıl a megoldá megoldás:

Matematika I.

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

x3= -1 x2 = 2 x1 = 1


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”. 189

Matematika I.


190

95

(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ı 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ı 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.

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

1 0 0

Matematika I.


191

0 1 0

2

0 0 1 −3

Matematika I.

1

0 0

=

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

1

1 1 1 1 2 2 2 1 2

1

0

−1 0 1

1

=

0 0 1

= 0 1 1 −1 1 0

Ellenı Ellenırzé rzés:

1

1 0 0

×

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

2

−1

0

2

0

−1

−3

1

1


=

=

1 0 0 0 1 0 0 0 1 192

96

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

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

v1

v3

e1 e5 v2

e3 e2

v4 e4 v5

E(G) ≔ A G élhalmaza

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

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


193

Matematika I.


194

97

V(G) elemeinek a szá számát a grá gráf rendjé rendjének nevezzü nevezzük. Jelö Jelölése: n(G) n(G). 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ő rendő, m mérető rető grá gráfot G(n,m) vagy Gn,m jelö jelöli.

e2

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.

v3

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

e3

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

v1 v2 v3 v4

v2 e4

e5

v1 v2 v3 v4

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

{

e1

v1

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 195

Matematika I.


196

98

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ı illeszkedı élek szá számát értjü rtjük. Jelö Jelölése: degG v vagy deg v.

2

Jelı Jelılje a v csú csúccsal szomszé csúcsok halmazá halmazát Γ(v). degGv=|Γ(v)|. (v)|. szomszédos csú

3

v1

5

2 v2

v4

v3

degG v2 = 3

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

δ(G) = degG v8 = 1

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

1

v8

v9

degG v4 = 4

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

Csú Csúcsfokszá csfokszámok egy grá gráfban

v∊ G


v7

2

4

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.

Matematika I.

3

2 v5

Egy csú csúcsot párosnak vagy páratlannak nevezzü nevezzük attó attól fü függı ggıen, hogy a fokszá fokszáma pá páros vagy pá páratlan.

v∊ G

v6

197

Matematika I.


198

99

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

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


Azt a grá gráfot, amelynek nincsenek élei üre grá gráfnak nevezzü nevezzük. A H grá gráf a G grá gráf ré részgrá szgráfja, ha V(H)⊆ V(G) és E(H)⊆ E(G). E(G).

Biz.:

Matematika I.

Részgrá szgráfok és induká indukált ré részgrá szgráfok

199

Legyen v∊V(G) V(G) és |V(G)| V(G)| ≥ 2. A H = G – v grá gráf a v csú csúcs tö törlé rlésével áll elı 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), E(G), akkor H = G – e (delete an edge) edge) G-nek egy olyan részgrá szgráfja, amelyre V(H) = V(G) és E(H) = E(G) – {ve}. Matematika I.


200

100

Ha u és v a G nem szomszé szomszédos csú csúcsai, akkor G + f, f, ahol f = uv, 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. v

Ha G egy H részgrá szgráfjá fjának rendje megegyezik G rendjé rendjével, akkor Ht G feszí feszítı részgrá szgráfjá fjának nevezzü nevezzük.

e

G

Matematika I.

G–v


Ha U a V(G) egy ré részhalmaz, szhalmaz, akkor then 〈U 〉 a G-nek egy olyan U által induká á lt grá á fja, amely induk gr csú csúcshalmaza U ⊆ V(G) és élhalmaza minden olyan élet tartalmaz G-bıl, amely illeszkedik az U két elemé elemére.

G–e

201

Matematika I.


202

101

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. ra. Egy grá teljes, ha bá bármely ké két csú csúcsa szomszé szomszédos. gráf teljes,

Ha G = G(m,n), 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.

A Petersen gráf

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


203

Matematika I.


204

102

Egy G grá gráfot k-részesnek mondunk, k ≥ 1, ha a V(G) csú csúcspontjaicspontjainak halmaza úgy particioná á lható ó k r é szhalmazra (V V ,V , … , particion lhat ( 1 2 Vk), hogy E(G) elemei Vi és Vj -beli csú csúcsokat kö kötnek össze, ahol i ≠ j.

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) V(G) u,v∊V(G), uv∊ E(G ) akkor és csak akkor, ha uv ∉ E(G).

Ha k = 2, 2, akkor a grá gráf kétré trészes. Állí llítás-1: Ha G = G(m,n), akkor G egy olyan n-ed rendő rendő grá gráf, amelynek mé mérete: n m =   − m 2

Tétel: tel: Ha G egy r-regular kétré trészes grá gráf, r ≥ 1, akkor |V1| = |V2| . Egy teljes ké kétré trészes grá gráfot, ahol |V1| = r és |V2| = s K(r,s)K(r,s)-el vagy Kr,sel jelı jelıljü ljük . (A K1,s grá gráfot csillagnak nevezzü nevezzük).

Állí llítás- 2: A Kn teljes grá gráf komplemens grá gráfja ( K n ) az n-ed rendő rendő üres.

Matematika I.


205

Matematika I.


206

103

v1

v4

v5

Mőveletek gáfokon

v7

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). v2

v3

v6

v1

v3

v5

v2

v4

v6

v7

V1

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

V2

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


207

Matematika I.


208

104

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:

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: (u (u1,u2) és (v (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

v2

v1 w1 G1 Matematika I.

G2

G1

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

209

Matematika I.

(u1,v2)

(v1,u2)

(v1,v2)

w2 G = G1×G2

G2 Felsıfokú Szakképzés

210

105

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ú csúcsa. Egy W-vel jelö jelölt u–v séta a G grá gráfban a csú csúcspontoknak és 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ı kezdıdik, a v csú csúccsal vé végzı gzıdik, és ei = ui-1ui mindig egy él, i=1,2,… i=1,2,…,k. ,k. A k szá számot a W séta hosszá hosszának nevezzü nevezzük. u1 u4 e1 e5 e4 e2 k=6 u e3 e6 u3 u2=u5 Matematika I.

u6=v


211

Egy u–v sétát zártnak vagy nyitottnak nevezü nevezünk attó attól fü függı 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ı tlıdik, és egy u–v út az egy olyan u–v séta, amelyben csú csúcspont nem ismé ismétlı 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ét is, de a megfordí megfordítottja általá ltalában nem igaz.

Matematika I.


212

106

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

Példa: lda: v2

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

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

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

v1

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

v3 v4

Matematika I.


213

Matematika I.

2

   =    

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

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

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

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

214

107

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.

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

Egy aciklikus grá gráfban nincs kö kör.

Biz.: Házi feladat

Egy kö kör páros, ros, ha hossza pá páros, egyé egyébké bként a kö kör páratlan. ratlan.

Azokt a ré részgrá szgráfokat, amelyek az ekvivalencia relá reláció ció eredmé eredményeké nyeként lé létrejö trejött ekvivalencia osztá osztályoknak felelnek meg, a G grá gráf összefü sszefüggı ggı komponensé komponensének nevezzü nevezzük. A G grá gráf komponenseinek szá számát k(G) jelö jelöli. li.

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ő 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ı thetı a v csú csúccsal, a grá gráfban lé létezik egy u–v út.

Egy összefü sszefüggı ggı grá gráfban az u és v csú csúcsok d(u,v) 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.

Egy grá gráf összefü sszefüggı ggı, ha bá bármely ké két csú csúcsa összekö sszeköthetı thetı. Egyé Egyébké bként a grá gráf nem összefü sszefüggı ggı. Matematika I.


215

Matematika I.


216

108

A feszí feszítı fa problé probléma 0

v1

1

v6

2

v7

3

v8

Egy G grá gráf feszí feszítı részgrá szgráfot értjü rtjük, amely fa. feszítı fáján azt a feszí

2 v5 2

1 v2

2

3 v4

v3

v9 v1

v2

szint 0 szint 1

v6

v3

v5

Tétel: tel: Minden összefü sszefüggı ggı fának van feszí feszítı részgrá szgráfja Proof. By construction. We choose an arbitrary vertex x∊ V. Let

v9

v4

v7

szint 2

v8

szint 3

Vi={ y ∊ G : d(x,y)= i, i=1,2,… i=1,2,…,M }. If yi∊ Vi , i > 0 and x,z1,z2,…,zi-1,yi is an x – yi path then d(x,z d(x,zj)= j, 0 < j < i. It is clear that Vj ≠ Ø, if j < M, and for any y ∊ Vi, i ≤ M, there exists at least one y'∊ Vi-1, which adjacent to y in G. ({y' ({y',y} ∊ E(G)).

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


217

Matematika I.


218

109

x

V0

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 tuljdonsá tuljdonsággal rendelkezı 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΄ T=(V,E΄) összefü sszefüggı ggı feszí feszítı fát, amelyre f (T ) = ∑ f ( xy ) , minimá minimális. lis. xy ∈ E

…

V1

V2

VM-2

VM-1

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

VM

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


219

Matematika I.


220

110

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ı thetı fel! Példa: lda:

Kruskal Algoritmus (1956): Válasszuk ki a legolcsó legolcsóbb élet G-bıl, azaz azt az élet, amelyre f(e) f(e) minimá minimális. lis. A kö következı 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ı lekbıl. Ha ilyen él má á r nincs, akkor vé é get é r az algoritmus. m v 1

1

3

3

2

4

3

3 3

2

4

5

3

Matematika I.

4

2

4

5

f(T1)=15

1

1 3

2

4

2


3

221

Matematika I.

4

2


222

111

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

2

4

5

w( H ) = ∑ e∈E ( H ) w(e).

f(T2)=15

1 3

Matematika I.

4

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).

2


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, amelynek é lei sú ú lyozva ggv nevezz lynak s vannak, súlyozott grá gráfnak nevezzü nevezzük. Legyen w: E(G)→ E(G)→ℝ+ egy fü függvé ggvény. ny. Terjesszü Terjesszük ki a fü függvé ggvény definició definicióját egy grá gráf H ⊆ G részgrá szgráfjá fjára:

2

4

A legrö legrövidebb út problé problémája

223

Matematika I.


224

112

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ı 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.

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

S 0 = { u0 },

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

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

The Dijkstra algorithm (1959)

HA Si = V(G) akkor az algoritmus befejezı befejezıdik. dik.

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ı vekvı Si halmazt ké készí szít, ahol 0 ≤ i ≤ n – 1, és {u0} ⊆ Si ⊆ V(G). V(G).

Ha Si ≠ V(G) V(G) akkor W = { vi | vi ∈ Si , l( vi ) = minv∈Si l( v )} és legyen ui+1 a W egy tetszı tetszıleges csú csúcspontja. cspontja.

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 tá á volsá á g á t adja meg az u csú ú cstó ó l az 〈 S 〉 induká cs t vols indukált részgrá szgráf0 cs cst ban. ban. Matematika I.


225

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

113

Mi a Dijkstra' Dijkstra's Algoritmus Algoritmus bonyolultsá bonyolultsága? ga?

Euler gráfok

n-ben polinomiá polinomiális: lis: O(n2). Példa: lda: v2

2

4

2

1 u0

7

Step

v3

v1

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

Egy olyan kö körutat a G grá gráfban, amely tartalmazza a G összes élét Euler körnek mondjuk.

Si

0

0

7

1

2

∞ u0

Egy Euler ösvé svény tartalmazza az összes élet, de nem zá zárt. rt.

1 1

1

0

7

1

2

2 u0 v2

Egy grá gráf Euler grá gráf, ha benne lé létezik EulerEuler-kör.

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

Tétel : Egy összefü sszefüggı 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.

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.


Egy G grá gráfot párosnak (páratlannak) ratlannak) mondunk, ha minden csú csúcsa páros (pá (páratlan).

227

Matematika I.


228

114

Definiá Definiáljuk a kö következı vetkezı sorozatot: a sorozatban egy bető 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ı letrıl a má másikra. Ha ilyen út lé létezne, akkor az leí leírható rható lenne 8 bető betővel, amelyek mindegyiké mindegyikét az A, B, C és D bető betőkbı kbıl vá választjuk Mivel minden hí hídon pontosan egyszer szabad átmenni, ezé ezért az A és B bető betők ebben a sorozatban ké kétszer fordulnak úgy elı elı, hogy ık egymá egymást kö követik. Ugyanez a helyzet az A és C bető 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ő betőbıl kell állni a sorozatnak. Ez pedig lehetetlen. Matematika I.


229

Matematika I.


230

115

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é két vá város kö közötti utazá utazás kö költsé ltsége ismert. Keressü Keressünk egy haté hatékony algoritmust, amely megtalá megtalálja a legolcsó legolcsóbb utat.

C

A

D

Mit jelent a „haté hatékony algoritmus” algoritmus”? A vá válasz meglepı meglepı: nem ismert az, hogy lé léteziktezik-e haté hatékony lgoritmus a problé probléma megoldá megoldására.

B

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á utazás alatt ugyanazt a vá várost ké kétszer is érintse.

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


231

Matematika I.


232

116

Azt a kö körutat, amely tartalmazza a problé problémához tartozó tartozó grá gráf minden csú csúcspontjá cspontját, Hamiltonian körnek nevezzü nevezzük. Azt a grá gráfot, amelynek van Hamilton köre, Hamilton grá gráfnak nevezzü nevezzük. 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 csk egyszer érint? Matematika I.


233

A dodekaéder gráfja Matematika I.


234

117

Hamilton 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ı mezıjét úgy, hogy minden mezı mezıt érintü rintünk, egyikre sem lé lépünk ké kétszer, és a vé végén vissza jutunk a kiinduló kiindulópontra.

A gazdasá gazdaságos Hamilton kör meghatá meghatározá rozásánál lé lényegesen egyszeegyszerőbb az a feladat, hogy lé léteziktezik-e Hamilton 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ı nthetı, hogy egy grá gráf HamiltonHamilton-grá gráf-e vagy sem? Tétel (Dirac): Dirac): Ha G egy 2n2n-ed rendő 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ő rendő, n ≥ 3, és minden nem szomszé szomszédos u, v csú csúcspontjá cspontjára deg u + deg v ≥ n, akkor G HamiltonHamilton-grá gráf.

Matematika I.


235

Matematika I.


236

118

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ı ggı r-regulá reguláris grá gráf, amelynnek legalá legalább 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ı thetı 3r+13r+1el. . el

Matematika I.


237

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

Matematika I.


238

119

Matematika I. Mőszaki informatikai mérnm. rnökasszisztens. Galambos GáborG JGYPK A Matematika I. fıbb f Halmazok: Alapfogalmak, mőveletek m

Recommend Documents