I.A matematikai logika alapjai A mindennapi életben, a matematikában is használunk egyszerű vagy összetett kijelentő mondatokat. Gyakran egy vagy több kijelentő mondatból újabb kijelentéseket fogalmazunk. A matematikai logika a következtetések szerkezetét vizsgálja matematikai módszerekkel. Formalizál, szabályokat állapít meg, hogy a kijelentésekből újabb kijelentésekre lehessen következtetni. I.1. A kijelentés. A predikátum Kijelentés (állítás, ítélet) egy olyan kijelentő mondat, amelyről egyértelműen el lehet dönteni, hogy igaz, vagy hamis. A matematikai logika nem a kijelentések tartalmával foglalkozik, hanem a szerkezetükkel. Az állítások jelölésére kisbetűket használunk:p, q, r, … Az igaz ítélethez az I vagy az 1, a hamis ítélethez a H vagy 0 logikai értéket (valóságértéket) rendeljük. Megjegyzés: Itt az 1 ill. 0 értékek nem számok, hanem szimbólumok. Arisztotelésztől származik a dichotómia alapelve: -egy állítás nem lehet egyidőben igaz is és hamis is (az ellentmondástalanság elve) -ha egy kijelentés nem igaz, akkor hamis, és ha nem hamis, akkor igaz, harmadik lehetőség nincs ( a harmadik kizárásának elve). Tehát az arisztotelészi alapelvek alapján az állítások logikai értéke egyértelmű, ezt a tapasztalat, vagy a szaktudományok eredményei alapján lehet eldönteni. Pl. A p: „2 + 4 = 6” ítélet igaz, tehát logikai értéke I vagy 1. A q: „4 > 5” kijelentés hamis, tehát logikai értéke H vagy 0. Az r: „Ha egy négyszög átlói merőlegesek egymásra, akkor az rombusz.” Ez az összetett kijelentés hamis, (logikai értéke 0, H), mivel van olyan négyszög, amely nem rombusz (a deltoid) és az átlói merőlegesek egymásra, de egyenlő szárú trapézra is gondolhatunk. Vegyük a „ p ( x) : x + 2 = 5, x ∈ N ” nyitott mondatot. Ez a mondat az x természetes számtól függ és minden x természetes szám behelyettesítése esetén egy kijelentést, állítást kapunk. kapunk. Ezt konkretizálásnak nevezzük. Pl. x = 4 esetén a p(4): „4 + 2 = 5” hamis kijelentést kapjuk. p(x)-et az x változótól függő (egyváltozós) predikátumnak (logikai függvény, nyitott mondat) nevezzük, amelynek jelen esetben az alaphalmaza N. Az alaphalmaz azon elemeinek összességét, amelyre a p(x) kijelentés igaz, a predikátum igazsághalmazának nevezzük.
1
Az itt megadott p(x) predikátum igazsághalmaza az egyenlet megoldását tartalmazza, vagyis a {3} halmaz. Ha a predikátum alaphalmaza nem adott, mindig az értelmezhető legtágabb halmazt tekintjük alaphalmaznak. Pl. „ q ( x) : 4 osztja x − et , x ∈ Z ” szintén egyváltozós kijelentés. Igazsághalmaza tartalmaz minden olyan természetes számot (és ezek ellentéteseit), amelyek a tízesei és egyeseiből alkotott kétjegyű szám osztható 4-gyel. „r(x,y): x + 4y > 10, x,y valós számok” egy kétváltozós predikátum. 1 5 p 6; igaz , p10,− hamis kijelentés. 4 4 Megjegyzés: Az alsó tagozaton a p(x) predikátum gyakran használt formája: + 2 = 5, az r(x,y) alakja pedig: ∆ + 4· > 10, ahol x, y az adott halmaz elemei.
Egyszerű állításokból és nyitott mondatokból logikai műveletekkel új állításokat és nyitott mondatokat képezhetünk.
Logikai műveletek Logikai műveletek a negáció, a konjunkció, a diszjunkció, az implikáció és az ekvivalencia. Ezekkel a műveletekkel összekapcsolt állítások, összetett kijelentések, logikai értékét a komponens állítások logikai értékei egyértelműen meghatározzák. A negáció (tagadás) Értelmezés: Ha p egy kijelentés, akkor a „nem” szó beiktatásával a „nem p” („non p”) (jel. p vagy ¬p ) kijelentést kapjuk, amelyet a p tagadásának nevezünk és amely akkor igaz, ha p hamis és akkor hamis, ha p igaz. Az értelmezés logikai táblázattal megadva:
p ¬p 1 0 0 1
Pl. p: „ Az 1 prímszám.” Tagadása: ¬p: „Az 1 nem prímszám.” q: „A háromszög szögeinek összege nem 180°.” Tagadása: ¬q: „Nem igaz, hogy a háromszög szögeinek összege nem 180°.”, vagy „A háromszög szögeinek összege 180°.” A mellékelt logikai táblázat igazolja a tagadás tulajdonságát: (t1) ¬(¬p) ≡ p. ( a kettős tagadás törvénye: a tagadás tagadása azonos az állítással).
p ¬p ¬(¬p) 1 0 1 0 1 0
(A ≡ jel a két, esetenként összetett állítás egyenértékűségét jelenti, vagyis azt, hogy a fenti táblázat első és utolsó oszlopa teljesen azonos logikai értékű.)
2
A diszjunkció (alternáció, szétválasztás) Értelmezés: Ha p és q két kijelentés, akkor belőlük képezhető a „p vagy q” (jel. p ∨ q ) kijelentés, amely akkor és csakis akkor hamis, ha p is hamis és q is hamis, minden más esetben igaz. Az értelmezést megadó logikai táblázat: Pl. p: „621 osztható 9-cel” q: „3 +3 = 3 · 3”. p ∨ q : „621 osztható 9-cel vagy 3 + 3 = 3 · 3” egy igaz kijelentés az értelmezés alapján.
p 0 1 0 1
q 0 0 1 1
p∨q 0 1 1 1
Megjegyzés: A köznyelv a vagy kötőszót nemcsak a fenti értelmezésnek megfelelő megengedő értelemben használhatja: „Kata este zenét hallgat vagy Kata este tanul”. Használhatja kizáró értelemben is: „Kata este színházba megy vagy Kata este koncertre megy.” A diszjunkció tulajdonságai: (d1) idempotens: p ∨ p ≡ p (d2) asszociatív: ( p ∨ q ) ∨ r ≡ p ∨ (q ∨ r ) (d3) kommutatív: p ∨ q ≡ q ∨ p A fenti tulajdonságok logikai táblázat segítségével igazolhatók.
A konjunkció (összekapcsolás) Értelmezés: Ha p és q két kijelentés, akkor belőlük képezhető a „p és q” (jel. p ∧ q ) kijelentés, amely akkor és csakis akkor igaz, ha p is igaz és q is igaz, minden más esetben hamis. Az értelmezést megadó logikai táblázat:
p q p∧q 0 0 0 Pl. 1 0 0 p: „A 30 páros szám.” 0 1 0 q: „A 30 osztható 5-tel.” 1 1 1 p ∧ q : „A 30 páros szám és osztható 5-tel.” Ez egy igaz kijelentés, mivel a két összekapcsolt kijelentés külön-külön is igaz volt. A konjunkció tulajdonságai: (k1) idempotens: p ∧ p ≡ p (k2) asszociatív: ( p ∧ q ) ∧ r ≡ p ∧ (q ∧ r ) (k3) kommutatív: p ∧ q ≡ q ∧ p A konjunkciót és diszjunkciót összekapcsoló tulajdonság a disztributivítás (széttagolódás):
3
(1) p ∧ (q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r ) , vagyis az „és” disztributív/széttagolódik a „vagy”-ra nézve és ugyanakkor (2) p ∨ (q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r ) , vagyis a „vagy” is disztributív az „és”-re nézve. Az előzőek közül az első igazolása logikai táblázattal: p q r q ∨ r p ∧ (q ∨ r ) p ∧ q p ∧ r ( p ∧ q ) ∨ ( p ∧ r ) 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 A két kivastagított oszlop megegyező logikai értékei alapján a két összetett kijelentés egyenértékű.
Az implikáció (kondicionális, feltételes állítás) Értelmezés: Ha p és q két kijelentés, akkor belőlük képezhető a „ha p akkor q” (p implikálja q-t, jel. p → q ) kijelentés, amely akkor és csakis akkor hamis, ha p igaz és q hamis. Az értelmezést megadó logikai táblázat: Pl. p: „A fecske madár.” q: „A 376 osztható 3-mal.” p → q : „Ha a fecske madár, akkor 376 osztható 3-mal.” Ez egy hamis kijelentés, a megadott értelmezés szellemében. A q → p kijelentés viszont igaz: „Ha 376 nem osztható 3-mal, akkor a fecske madár.”
p 0 1 0 1
q 0 0 1 1
p→q 1 0 1 1
Az implikáció tulajdonságai: (i1) p → q ≡ ¬q → ¬p . A fenti fontos tulajdonságot a kontrapozició elvének nevezzük. Ez szolgál alapul az indirekt bizonyítás esetén. (i2) p → q ≡ ¬p ∨ q A fenti tulajdonságból lehet levezetni az implikáció tagadásának törvényét: (i3) ¬( p → q ) ≡ p ∧ ¬q
Pl. p → q : „Ha egy a szám osztható 10-zel, akkor páros.” A kontraponált állítás:
4
¬q → ¬p : „Ha egy a szám nem páros, akkor nem osztható 10-zel.”
Az ekvivalencia (bikondicionális, kettős feltételes állítás) Értelmezés: Ha p és q két kijelentés, akkor belőlük képezhető a „ p akkor és csakis akkor, ha q” (jel. p ↔ q ) kijelentés, amely akkor és csakis akkor igaz, ha p igaz és q igaz, vagy ha p is hamis és q is hamis. p 0 1 0 1
Az értelmezést megadó logikai táblázat: Az ekvivalencia tulajdonságai: (e1) p ↔ q ≡ q ↔ p
(e2) ( p ↔ q ) ↔ r ≡ p ↔ (q ↔ r ) (e3) p ↔ q ≡ ( p → q ) ∧ (q → p )
q 0 0 1 1
p↔q 1 0 0 1
Más fontos tulajdonságok (egyenértékű összetett kijelentések, logikai képletek) A de Morgan képletek: (m1) ¬( p ∧ q ) ≡ ¬p ∨ ¬q (a konjunkció tagadása) (m2) ¬( p ∨ q ) ≡ ¬p ∧ ¬q (a diszjunkció tagadása) A de Morgan képletekből adódnak még a következők: (m3) p ∧ q ≡ ¬(¬p ∨ ¬q ) ( m 4)
p ∨ q ≡ ¬(¬p ∧ ¬q )
Pl. p: „Az a szám páros.” q: „Az a szám osztható 5-tel.” Erre a két kijelentésre sorra alkalmazzuk a fenti tulajdonságokat: p ∧ q : „Az a szám páros és osztható 5-tel.” Tagadása: ¬( p ∧ q ) : „Nem igaz, hogy (az a szám páros és osztható 5-tel).” Átfogalmazva: ¬p ∨ ¬q : „Az a szám nem páros vagy nem osztható 5-tel.” A tagadás tagadása: ¬(¬p ∨ ¬q ) : „Nem igaz, hogy (az a szám nem páros vagy nem osztható 5-tel).” p ∨ q : „Az a szám páros, vagy osztható 5-tel.” Tagadása: ¬( p ∨ q ) : „Nem igaz, hogy (az a szám páros vagy osztható 5-tel).” Átfogalmazva: ¬p ∧ ¬q : „Az a szám nem páros és nem osztható 5-tel.” A tagadás tagadása: ¬(¬p ∧ ¬q ) : „Nem igaz, hogy (az a szám nem páros és nem osztható 5-tel).”
A tautológia Ha egy összetett kijelentés logikai értéke a benne szereplő egyszerű kijelentések bármely logikai értéke esetén 1, akkor azt tautológiának, vagy azonosan igaz képletnek nevezzük.
5
Pl. (t1) p ∨ ¬p (t2) [ p ∧ ( p → q )] → q A második képlet az ún. „leválasztási szabály” – a direkt bizonyítás következtetési szabálya. A (t2) igazolása: p 1 1 0 0
q 1 0 1 0
p→q
1 0 1 1
p ∧ ( p → q) 1 0 0 0
[ p ∧ ( p → q )] → q 1 1 1 1
Az antilógia Ha egy összetett kijelentés logikai értéke a benne szereplő egyszerű kijelentések bármely logikai értéke esetén 0, akkor antilógiának, kontradikció, azonosan hamisnak nevezzük. Predikátumkalkulus Az előzőekben a kijelentésekkel egyidőben értelmeztük a predikátum fogalmát. Általában a predikátumok is összekapcsolhatók a már előzőleg ismertetett logikai műveletekkel. Így összetett nyitott mondatokat, összetett predikátumokat kapunk. Az előzőben azt is láttuk, hogy a predikátumokból kijelentésekhez konkretizáció útján jutunk. Gyakran találkozunk olyan állításokkal amelyekben szerepel a „minden”, „bármely”, „tetszőleges”, „van olyan”, „létezik” szó. Ezeket a szavakat illtve a hozzájuk tartozó ∀ és ∃ szimbólumokat kvantoroknak nevezzük: univerzális kvantor, illetve exisztenciális kvantor. Ha ezek valamelyikét alkalmazzuk egy predikátumra, akkor ezt kvantifikációnak nevezzük. Ez egy másik módja, hogy a predikátumból kijelentést kapjunk. Pl. p(x): „ x kör alakú, ahol x eleme a logi készlet lapjai U halmazának.” p(x) átfogalmazva: „ A logi készlet lapjainak U halmazában van kör alakú lap.” leírása: „ (∃x ), p( x), x ∈ U ” kiolvasása: „létezik x az U-ban, amelyre p(x)” –nyilván igaz. Pl. „A logi készlet bármely lapja kör alakú.” leírása: „ (∀x ), p( x), x ∈ U ” kiolvasása: „bármely x-re az U-ból p(x)” –nyilván hamis. Pl. p(x): „Az x paralelogramma, x eleme a négyszögek U halmazának.” q(x): „Az x négyzet, x a négyszögek U halmazának eleme.” „ (∀x ), p( x) → q( x), x ∈ U ”: „Minden négyszög, ami paralelogramma, négyzet.” – (H). „ (∀x ), q ( x) → p( x), x ∈ U ”: „Minden négyszög, ami négyzet, az paralelogramma.” – (I)
6
A kvantifikáció szabatos értelmezése: A „ (∃x ), p( x), x ∈ U ” kijelentés akkor és csakis akkor igaz, ha van legalább egy x0 ∈ U elem, amelyre p ( x0 ) igaz. A „ (∀x ), p( x), x ∈ U ” kijelentés akkor és csakis akkor igaz, ha az U halmaz minden eleme esetén igaz kijelentést kapunk. Az utóbbi kijelentés akkor hamis, ha van legalább egy x0 ∈ U elem, amelyre p ( x0 ) hamis. Ezt ellenpéldával történő cáfolásnak nevezzük. Pl. „Bármely törzsszám páratlan.” Ez egy hamis kijelentés, mert van olyan törzsszám, a 2, (ez az ellenpélda) amely páros.
A tagadás szabályai (unáris, egyváltozós predikátumokra): (1) ¬[(∃x ), p( x), x ∈ U ] ≡ (∀x ), ¬p( x), x ∈ U Pl. „Van olyan gyerek, aki szemüveges.” (I) Tagadása: „Nem igaz, hogy van olyan gyerek, aki szemüveges.” Átfogalmazva: „Minden gyerekre igaz, hogy nem szemüveges.” (2) ¬[(∀x ), p( x), x ∈ U ] ≡ (∃x ), ¬p( x), x ∈ U Pl. „Mindenki átmenőt kapott az országos teszten.” (H) Tagadása: „nem igaz, hogy mindenki átmenőt kapott az országos teszten.” Átfogalmazása: „Van olyan, aki nem kapott átmenőt az országos teszten.”
I.2. A fogalom (fakultatív anyag) A fogalom logikai szempontból valamely dolog lényeges jegyeit magába foglaló gondolati egység. Egy fogalomnak van tárgya (konkrétan miről van szó), tartalma, vagyis a fogalom lényeges jegyei és terjedelme (köre). Pl. a háromszög fogalma esetén: a fogalom tárgya maga egy konkrét háromszög, tartalma az, hogy 3 oldala (3 szöge van), terjedelme pedig, hogy az összes háromszögre vonatkozik. A fogalmak terjedelmük szerint lehetnek: - egyedi fogalmak (pl. Nagyküküllő) - általános fogalmak (pl. a négyszög, a test, a természetes szám) - kategória – ez a legáltalánosabb fogalom (pl. mennyiség, tér, halmaz) - viszonyt kifejező fogalom (pl. részhalmaza, osztója, hasonló, kongruens) - idealizált fogalom (pl. pont, egyenes, sík) A definíció új fogalmak bevezetésére szolgál.
7
A definíciónak (meghatározásnak, értelmezésnek) olyannak kell lennie, hogy segítségével egyértelműen el lehessen dönteni valamely dologról, hogy beletartozik-e a definíció által megadott halmazba, vagy sem. A szép definíció elegáns, szabatos, tömör, kimerítő. Ha a tanulók által adott értelmezés hibás, rögtön cáfolunk ellenpéldával. Néhány tipikus definiálási hiba: - Az értelmezés ismeretlen fogalmat tartalmaz. (pl. a háromszög az a sokszög, amelynek három oldala van – amennyiben még nem értelmeztük a sokszög fogalmát) - A definíció homályos (pl. A pont olyan dolog, amelynek nincsenek részei) - Tagadó meghatározás (pl. Egy természetes szám kisebb, mint egy másik, ha nem nagyobb annál) - Körbeforgó meghatározás (A liter azt jelenti, hogy egy edénybe hány liter vizet töltöttünk) - Tág meghatározás: ha elhagytuk a fogalom tartalmának valamely lényeges jegyét (pl. Két félegyenes szöget alkot – lényeges, hogy közös kezdőpontú félegyenesek) - Szűk meghatározás: ha több jegyet veszünk bele a meghatározásba, mint ami szükséges (A gömb azon síkbeli pontok összessége, amelyek egy rögzített ponttól egyenlő távolságra vannak) - Bőbeszédű meghatározás: ha a fogalom olyan jegyeit is tartalmazza az értelmezés, amelyek következmények (Az egyenlő szárú háromszög az a háromszög, amelynek két oldala és két szöge kongruens) Az alapfogalmakat nem definiáljuk, példákkal, leírással szemléltetjük. Tartalmukat azok az axiómák, sarkigazságok (bizonyítás nélkül igaznak elfogadott kijelentések) adják meg, amelyek rájuk vonatkoznak. Például: halmaz, pont, egyenes, sík, stb. – alapfogalmak.
I.3. A tételek A fontosabb igaz matematikai állításokat tételek formájában fogalmazzuk meg. Csak azt az állítást nevezzük tételnek, amit sikerült előzőleg elfogadott tételek, axiómák, ismert fogalmak segítségével bizonyítani. A még nem igazolt, de a tapasztalat alapján igaznak tekinthető állítást sejtésnek nevezzük. Egy sejtés helytelen voltának igazolására elegendő egyetlen, azt cáfoló példát (ellenpéldát) adni. Példák tételekre: (1) Bármely háromszögben a belső szögek összege 180°. (2) A háromszög bármely oldalának hossza kisebb, mint a másik két oldal hosszának összege. (3) Bármely derékszögű háromszögben a két befogó négyzetének összege egyenlő az átfogó négyzetével. (4) A rombusz átlói merőlegesek egymásra. (5) Ha két egész szám szorzata páratlan, akkor összegük páros. (6) Két egymásutáni páros természetes szám szorzata osztható 8-cal. (7) A négyzet átlói kongruensek és merőlegesek egymásra.
8
(8) Bármely a, b valós szám esetén (a + b)(a – b) = a² - b² A tételek általában „ha p, akkor q”, vagyis p ⇒ q szerkezetűek. A p állítást, állításokat premisszá(k)nak, (feltételek) ezek elfogadását feltevésnek nevezzük. A q állítást, állításokat konklúzió(k)nak (következmény), ezeknek az adott feltételek melletti kijelentését következtetésnek nevezzük. Megjegyzés: A p→q implikáció a tételek esetében átíródik p ⇒ q jelöléssé, mivel ez esetben a p-ben szereplő premisszák igazaknak tekintettek és emellett a feltevés mellett próbáljuk meg igazolni a q konklúziókban foglaltakat, vagyis a következménynek is igaznak kell lennie. Egészen pontosan, ha a p→q logikai formula tautológia, akkor ennek jelölése: p ⇒ q .
Egy tétel szerkezetét könnyebb áttekinteni, a feltevését, következtetését fölírni, ha átfogalmazzuk „ha…., akkor….” formába. Pl. (1) Ha egy sokszög háromszög, akkor a belső szögei mértékének összege 180°. (8) Ha a, b két valós szám, akkor (a + b)(a – b) = a² - b². Ha egy tételben a feltételeket, vagy azok egy részét felcseréljük a következményekkel, vagy azok egy részével, akkor a tétel fordított állítását kapjuk. Amennyiben ez az állítás igaz, ezt nevezzük az eredeti tétel (ekkor már direkt tétel) fordított tételének. Sematikusan a p ⇒ q tétel fordított állítása q → p , fordított tétele q ⇒ p alakú. Pl. (3) Ha egy háromszög derékszögű, akkor az átfogó négyzete egyenlő a két befogó négyzetének összegével. ( p ⇒ q ) Ha egy háromszögben az átfogó négyzete egyenlő a két befogó négyzetének összegével, akkor a háromszög derékszögű. ( q ⇒ p ) Mivel a fenti állítás igaz, ez az eredeti tétel fordított tétele (Pithagorász tételének a fordított tétele). A (7)-es tétel fordított állítása: Ha egy négyszögben az átlók kongruensek és merőlegesek egymásra, akkor a négyszög egy négyzet. Ez az állítás hamis, mivel ez egy egyenlő szárú trapézban is igaz. Tehát itt nem beszélhetünk fordított tételről. Megjegyzés: -Amennyiben a direkt tétel fordított tétele is igaz, az mondjuk, hogy p ⇒ q és q ⇒ p , vagyis p ⇔ q , vagyis p és q egymásnak szükséges és elégséges feltételei, azaz a p és q egymással egyenértékűek. Így a Pithagorász tétele egy kijelentésben megfogalmazva: Annak szükséges és elégséges feltétele, hogy egy háromszög derékszögű legyen az, hogy az átfogó négyzete egyenlő legyen a két befogó négyzetének összegével.
9
-A (7)-es tétel megfordítása esetén Az átlók merőlegessége és kongruenciája szükséges, de nem elégséges feltétele a négyszög négyzetté válásának. Ha egy tételben tagadjuk a feltevést és a következtetést is, akkor a tétel ellentétes állítását kapjuk, amennyiben ez igaz, úgy az ellentétes tételét. Sematikusan: ¬p → ¬q, illetve ¬p ⇒ ¬q Pl. A (3)-as esetében: Ha egy háromszög nem derékszögű, akkor az átfogó négyzete nem egyenlő a két befogó négyzetének összegével. A kijelentés igaz, tehát ez a direkt tétel ellentétes tétele. A (7)-es esetében: Ha egy sokszög nem négyzet, akkor átlói nem kongruensek vagy nem merőlegesek egymásra. Ez hamis állítás.
Egy tétel fordított állításának az ellentétese Pl. A (3)-as esetében: Ha egy háromszögben az átfogó négyzete nem egyenlő a két befogó négyzetének összegével, akkor a háromszög nem derékszögű. (I) A (7)-es esetében: Ha egy négyszögben az átlók nem kongruensek vagy nem merőlegesek egymásra, akkor a négyszög nem négyzet. (I) Amit felírtunk, sematikusan: ¬q ⇒ ¬p . A fordított kijelentés ellentétes kijelentése logikailag egyenértékű a direkt tétellel, tehát mindig igaz, vagyis tétel. Ennek belátása a következő azonosságon alapszik: p → q ≡ ¬q → ¬p Ugyanilyen megfontolás alapján egy tétel fordított tétele egyenértékű a direkt tétel ellentétes tételével. I.4. Bizonyítási módszerek Egy kijelentés helyességét bizonyítani azt jelenti, hogy a kijelentés igazságát csupán logikai műveletvégzések során visszavezetni más, már igazolt tételekre, axiómákra. Egy kijelentés helytelen voltának igazolására elegendő egyetlen ellenpélda. A bizonyítás történhet direkt, vagy indirekt módon. A direkt bizonyításnál a feltételekből kiindulva , esetleg más, már bizonyított eredményeket felhasználva, logikai műveletek segítségével jutunk el a konklúzióig. Szerkezete: p ⇒ q Az indirekt bizonyítás a p ⇒ q helyett a vele logikailag egyenértékű ¬q ⇒ ¬p bizonyítást végzi., vagyis a fordított kijelentés ellentétes kijelentését bizonyítja. A bizonyításban segítségünkre vannak a kijelentés és predikátumkalkulus következtetési sémái. 1. A leválasztási szabály (modus ponens), a direkt bizonyítás szabálya: [ p ∧ ( p → q )] ⇒ q Pl.
10
p → q Ha az a szám páros, akkor osztható 2-vel. p Az a szám páros. q (Mindezekből következik, hogy): Az a szám osztható 2-vel. 2. Az indirekt bizonyítás szabálya: [q ∧ (¬p → ¬q )] ⇒ p Pl. q Az a szám osztható 2-vel. ¬p→¬q Ha az a szám nem páros, akkor nem osztható 2-vel. p (Mindezekből következik, hogy): Az a szám páros. 3. A diszjunktív szillogizmus szabálya: [( p ∨ q ) ∧ ¬p] ⇒ q Pl. p ∨ q : Az a természetes szám páros vagy páratlan. ¬p: Az a természetes szám nem páros. q (Akkor) Az a természetes szám páratlan. 4. A láncszabály, vagy feltételes szillogizmus: [( p → q ) ∧ (q → r )] ⇒ ( p → r ) Pl. p→q: Ha az a természetes szám osztható 8-cal, akkor a osztható 4-gyel is. q→r: Ha az a természetes szám osztható 4-gyel, akkor a osztható 2-vel is. p→r (mindezek alapján) Ha az a természetes szám osztható 8-cal, akkor a osztható 2-vel is. Egy bizonyítás gondolatmenete igaz következtetések láncolatát jelenti, míg csak el nem jutunk a következtetésig.
Direkt bizonyítási módszerek Ha a feladat megoldása (vagy egy bizonyítás) az előzményekből közvetlenül következik, direkt bizonyításról beszélünk. Ennek két formáját vizsgáljuk egy feladat megoldását véve alapul. Ha a bizonyítás, esetenként a feladatmegoldás, esetén a következtetések láncolatát a feltevésből, adatokból kiindulva építjük föl, akkor a módszerünk progresszív, szintetikus. Ezt még szintézisnek is nevezzük. Ha a megoldás felépítésében a következtetéstől, a feladat kérdésétől visszafelé haladunk a feltevésig, az adatokig, akkor a módszert regresszív, vagy analitikus, elemző módszernek nevezzük. Ezt még analízisnek is nevezzük. -Az első esetben ilyen kérdéseket teszünk föl: Mit tudok kiszámítani?, bizonyítani? -A második esetben így kérdezünk: Mit kell kiszámítanom, igazolnom ahhoz, hogy…?
11
Így elemezve a feladatot, gyakorlatilag fordított irányban, logikusan megindokolva, felépítjük a megoldás egymásra következő lépéseit, majd a megoldás során a kitűzött számításokat elvégezve választ tudunk adni a feladat kérdésére. Tehát tulajdonképpen a megoldás lépéseinek megtalálása analitikus módon, de a műveletek elvégzése szintetikus módon történik. Feladat Egy raktárba 38 zsák lisztet vittek. Ezekből 18 db 40 kg-os tömegű, 17 db 50 kg-os tömegű zsák. A többi zsák 75 kg-os volt. Hány kg lisztet vittek a raktárba? -A progresszív megoldás: Ki tudom számítani, hogy - hány kg liszt van a 40 kg-os zsákokban: 18 ⋅ 40 = 720 (kg ) - hány kg liszt van az 50 kg-os zsákokban: 17 ⋅ 50 = 850 (kg ) - hány db 75 kg-os zsák van: 18 + 17 = 35, 38 – 35 = 3 - hány kg liszt van a 75 kg-os zsákokban: 75 ⋅ 3 = 225 (kg ) - hány kg liszt van összesen: 720 + 850 + 225 = 1795 (kg Ö.) Felelet: Ö. 1795 kg lisztet vittek . -Az analitikus gondolatmenet: Mit kell kiszámítanom, hogy megtudjam, hogy összesen hány kg-ot vittek? -Hogy hány kg van az egyes fajtájú zsákokban. Ki tudom-e ezt számítani? -Igen, de csak az első két fajta zsák esetében. Hogyan? -Megbeszéljük. Mit kell csinálni, hogy megtudjuk a harmadik fajta zsákokban levő liszt súlyát? -Először ki kell számítani, hogy hány db ilyen fajta zsák van. Ki tudom ezt számítani? -Igen. Hogyan? -Megbeszéljük.
Ebben a pillanatban el van gondolva, meg van beszélve, hogy milyen számításokat kell végezni. Ezt nevezzük tervkészítésnek. A tervet, legalább néhány feladatnál, érdemes le is írni, hogy a gyerekek számára világossá váljék, hogy hogyan gondolkodtunk. A leírására szánt időt nem kell sajnálni, mert megtérül. Már csak a számítások elvégzése következik. Ez nyilván ugyanúgy történik, mint a szintetikus megoldás esetében.
Az indirekt bizonyítási módszerek Az indirekt módszer esetében egy állítás helyes voltát úgy igazoljuk, hogy bebizonyítjuk az ellentétes állítás hamis voltát. Vagyis feltesszük, hogy a bizonyítandó állítás nem igaz. Erre támaszkodva, a logikai következtetések lépéseit helyesen alkalmazva,
12
ellentmondáshoz jutunk. Mivel a következtetésünk lépései helyesek voltak, csak a kiinduló feltétel lehetett helytelen. Tehát a bizonyítandó állítás nem lehet hamis, hanem csakis igaz. A bizonyítás során ellentmondásba kerülhetünk a kiinduló feltevéssel, valamely, már ismert eredménnyel, tétellel, vagy axiómával. A leírt módszert gyakorlatilag a lehetetlenre való visszavezetés módszerének (reductio ad absurdum módszerének) nevezzük. Pólya György szerint az indirekt bizonyítási módszerek és a reductio ad absurdum módszere csak nagyon kevésben (szemléletükben) különböznek egymástól. Ez azt jelenti, hogy gyakorlatilag egymásba átfogalmazhatóak. Feladat Öt sziget közül bármelyiket hajó- illetve repülőjárat köt össze, de csak az egyik úgy, hogy egyik járattal sem lehet három szigetet körbejárni. Igazoljuk, hogy minden szigetről két hajó, és két repülőjárat indul. Megoldás: Jelöljük rendre A, B, C, D, E betűkkel a szigeteket és az őket összekötő szakaszok jelöljék a járatokat.
Feltételezzük, hogy pl. A szigetről nem két repülőút indul. Induljon akkor három, éspedig B, C, D szigetek irányába. Ez azt jelenti, a feladat feltételeit figyelembe véve, hogy az ABC, ACD, ABD háromszögek harmadik oldalán, vagyis a BC, CD és BD oldalakon csakis hajóutak szerepelhetnek. 13
Ez viszont szintén lehetetlen (mert így a B, C, D szigeteket lehetne hajóval körbejárni). Tehát az a feltételezésünk, hogy A-ból 3 repülőút indulhat, nem állhat fönn. Annál kevésbé indulhat négy járat. Ha viszont azt feltételezzük, hogy A-ból 0, vagy 1 repülőút indul, akkor, mivel minden szigetről, mindenikre indul repülő vagy hajóút, az A-ról legalább 3 hajóútnak kell indulnia. Ez viszont az előző gondolatmenet alapján éppúgy lehetetlen, mert akkor megint lenne egy háromszög, amely most repülőkkel lenne körbejárva. E szerint nem marad más lehetőség, mint elfogadni, hogy az A szigetről pontosan két repülőjáratnak és két hajójáratnak kell indulnia. A megoldásnál a lehetetlenre való visszavezetés módszerét alkalmaztuk, ellentmondásba kerülve a feladat adataival. Egy másik indirekt módszer a skatulya-elv (Dirichlet-elv). Feladat Egy 25-ös létszámú osztályban mindenki írt félévi dolgozatot, amelyet a tanár 10-től 3-ig bezárólag osztályozott. Igazoljuk, hogy biztosan volt legalább 4 tanuló, aki azonos dolgozatjegyet kapott. Megoldás. Itt 8 féle osztályzat van, vagyis a skatulyák száma 8. Mivel a 25-ben a nyolc megvan 3szor (a legrosszabb esetre gondolunk,vagyis hogy háromszor sorra kerül minden osztályzat), minden osztályzathoz jut legalább 3 tanuló. De a 25-ig fennmaradó 1 tanuló valamelyik skatulyába bele fog kerülni. Tehát biztosan lesz legalább 4 tanuló, akiknek azonos a félévi jegye. A módszer valóban indirekt, mert abból indultunk ki, hogy minden skatulyába biztosan jusson legalább 3 tanuló. A számítás alapján, viszont következik, hogy biztosan juthat négy is. Itt a Dirichlet-elv egyszerűbb változatát használtuk, miszerint, van n skatulya és k ⋅ n + r , r > 0 darab tárgy. Ha elhelyezzük a tárgyakat a skatulyákba, minden skatulyába jut k darab tárgy, de mivel r > 0 , kell legyen legalább egy skatulya, amelybe k + 1 darab tárgy jutott. A fenti feladat esetén tehát n = 8 és k = 3. Feladat Legalább hány tanulója van annak az iskolának, amelynek tanulói közül biztosan ki tudunk választani 3 tanulót úgy, hogy a születésnapjuk az év azonos dátumán legyen. Megoldás. Most a skatulyák az év napjai. Vagyis 366 skatulyánk van, mivel február 29-e is lehet születési dátum. Tehát ahhoz, hogy az év minden napján biztosan legyen legalább 2
14
szülinap, kell 366 ⋅ 2 = 732 tanuló. Tehát ha énnél eggyel többen vannak, vagyis 733-an, akkor kell legyen legalább egy dátum, amelyre három szülinapos tanuló kerül.
Az induktív bizonyítás módszere A matematikai gondolkodásban gyakran előfordul mind a deduktív, mind az induktív gondolatmenet. A deduktív gondolatmenet esetében egy általános állításból konkrét esetre következtetünk. Pl. Vegyük ezt a tulajdonságot: „Ha egy természetes szám utolsó számjegye osztható 5-tel, akkor maga a szám is osztható 5-tel.” Ez alapján kijelenthetjük, hogy mivel a 7865 szám utolsó számjegye osztható 5-tel, ezért a 7865 is osztható 5-tel. Tehát az általános kijelentést konkretizáltuk egy sajátos esetre. Az induktív gondolatmenet esetében sajátos esetekben érvényes kijelentésekből kiindulva jutunk el általánosan érvényes kijelentésekhez. Magát az eljárást indukciónak nevezzük. Ha az általános kijelentést néhány eset megvizsgálására alapoztuk, és később sem végeztünk igazolására semmilyen eljárást, akkor ezt nem teljes, ún. parciális indukciónak nevezzük. Egy induktíve kikövetkeztetett kijelentés nem mindig igaz, mert néhány eset figyelembevételével általánosít. Pl. Vegyük W. Sierpinski (lengyel matematikus, 1882 – 1969) kijelentését: A 991n² + 1 alakú természetes számok nem négyzetszámok egyetlen n természetes szám esetén sem. A technika előrehaladtával sikerült olyan 29 számjegyű n természetes számot találni, amelyre teljes négyzetet kapunk. A teljes indukció módszere az a következtetési mód, amikor az adott szituáció esetén minden esetet megvizsgáltunk és így vontuk le az általános következtetést. Például, ha az állítás egy véges halmaz elemeire vonatkozik. Pl. Igazoljuk, hogy minden olyan természetes szám 0 és 501 között, amelynek felírásában az utolsó két helyen álló kétjegyű szám osztható 25-tel, maga is osztható 25-tel. Tehát a következő számokról van szó: 25, 50, 75, 100, 125, … , 475, 500, vagyis összesen 20 db. számról. Felírva a számokat nyilvánvaló, hogy a tulajdonság teljesül. Mivel minden esetet megvizsgáltunk, az indukció teljesnek tekinthető. Az olyan típusú kijelentések, amelyek végtelen sok természetes számra érvényesek, teljes indukcióval nem igazolhatók (a végtelen sok számú eset miatt). A (∀n ) p(n ) típusú kijelentések bizonyítására a matematikai indukció módszere szolgál. Ennek több változata van, de mindegyik a Peano-féle axiómarendszeren alapszik. A matematikai indukció elve:
15
Legyen p(n) az n természetes számoktól függő, az n ≥ m természetes számokra érvényesnek bizonyítandó kijelentés. Ha a p(n) kijelentésre érvényesek: - p(m) igaz kijelentés - abból, hogy p(k) kijelentést igaz, igazolni tudjuk, hogy p(k + 1) is igaz kijelentés, ahol k tetszőleges természetes szám akkor, a p(n) kijelentés igaz, minden természetes számra m-től kezdődően. Megjegyzés: A matematikai indukció elve tulajdonképpen azt kéri, hogy legyen egy kiinduló szám, amiről egyenként továbblépkedve (p(k) maga után vonja p(k + 1)-et), „átterjed” a tulajdonság minden természetes számra. Szemléletesen ez olyan, mint amikor egy álló, egymástól megfelelő és egyenlő távolságban lévő, dominókból alkotott sor esetén, az első feldöntésével a dőlés végigterjed az egész soron, amennyiben az sehol nincs megszakítva. Feladat Igazoljuk, hogy minden n ∈ N ∗ természetes szám esetén igaz hogy: 1 + 3 + 5 + ... + (2n − 1) = n 2 Ha ezt az összefüggést „le akarjuk fordítani” az I-IV osztályosok szintjére, akkor így fogalmazhatunk: Tegyük fel, hogy azonos méretű körlapjaink vannak, melyek száma 1-től kezdődően egy tetszőleges páratlan számig minden esetben összeadódik (van 1 db, 1+3 db,1+3+5 db, … körlapunk). Igazoljuk, hogy akármelyik páratlan számmal is végződjék a sorozatunk, felhasználva az összeg összes darabját, ki lehet alakítani belőlük négyzet alakot. Ennek a belátására rendezzük át sorra az egymást követő sorozatokat:
1 = 1² 1 + 3 = 2² 1 + 3 + 5 = 3² 1 + 3 + 5 + 7 = 4² Úgy tűnik, hogy így folytatva, minden esetben megkapjuk a négyzetet. A szigorú bizonyítás a matematikai indukció módszerével történik. I.lépés. Igazoljuk p(1) igazságát: 1 = 12 (A p(n) kijelentés szerkezetével való ismerkedés érdekében, még igazoljuk p(2) és p(3) állítások igaz voltát is, bár ezt az indukciós bizonyítás nem kéri.) p(2): 1 + 3 = 4 = 2 2 igaz, ahol a 3 = 2 ⋅ 2 − 1 . P(3): 1 + 3 + 5 = 9 = 3 2 igaz , ahol 5 = 2 ⋅ 3 − 1 II.lépés Elfogadjuk igaznak a p(k) kijelentést, vagyis: F.: p(k): 1 + 3 + 5 … + (2k – 1) = k² Ennek a segítségével igazoljuk, hogy igaz a p(k + 1) kijelentés, vagyis: 16
K.: p(k + 1): 1 + 3 + 5 +…+(2k + 1) = (k + 1)² (ez utóbbit úgy kaptuk, hogy p(n) kifejezésbe az n helyére (k + 1)-et írtunk.) bizonyítás: Beírjuk az 1 + 3 + 5 +…+(2k + 1) végtelen összegbe az utolsó előtti tagot is, vagyis a 2k + 1 páratlan szám előttit, a (2k – 1)-et. Ezt kapjuk: 1 + 3 + 5 +…+ (2k – 1) + (2k + 1) Nyilván az összeg nem változott meg csak formailag, mivel így láthatóvá vált az utolsó két tag. Az indukciós feltétel alapján az 1 + 3 + 5 … + (2k – 1) összeget helyettesíthetjük k²-tel. Így a következő igaz egyenlőséget kapjuk: 1 + 3 + 5 +…+ (2k – 1) + (2k + 1) = k² + (2k + 1) = k² + 2k + 1 = (k + 1)² Ezzel a következtetés egyenlőségét, vagyis p(k + 1)-et igazoltuk. Így a matematikai indukció elve alapján, p(n) igaz minden nemnulla természetes számra. A fenti egyenlőség jól felhasználható a következő, a IV. osztályban kitűnő tanulóknak javasolható, feladat megoldásában. Feladat: Egy előadóterem első sorában 15 hely van, minden további sorban 2-vel több, mint az előzőben. A nézőtéren 975 hely van. Számítsuk ki, hány sorban találhatók a székek. Megoldás A következő nyitott mondattal kell megbirkózni: 15 + 17 + 19 +… = 975 Egészítsük ki az összeget egészen 1-ig: 1 + 3 + 5 + …+13 = 49. Tehát a 975-höz és hozzáadva a 49-et 1024-et kapunk. Vagyis a következő egyenlőséghez jutunk: 1 + 3 + 5 + …+13+15 + 17 + 19 +… = 1024 Itt jön be az előző állítás felhasználása: az egymás után következő páratlan számok összege egy szám négyzetével egyenlő. Minek a négyzete az 1024? Az 1024 a 32 négyzete. (Megfigyelve a szám nagyságát, próbálgatva ez kiszámítható.) Így kiegészítve tehát 32 sor szék van amiből kivonjuk a kiegészítésre használt 7 sor széket. Felelet. Tehát a 975 szék 25 sorban van elhelyezve. Feladat A következő egyenlőség elég gyakran előfordul az alsó tagozaton, bár igaz, hogy konkrét formában: n ⋅ (n + 1) 1 + 2 + 3 + 4 + ... + n = , bármely n ≥ 1 természetes számra. 2
Az összeg kiszámítása a kisiskolás Gauss nevéhez fűződik. (Carl Fredrich Gauss, német matematikus, „a matematika fejedelme”, 1777 – 1855). A gyerekekkel az összeget „kipárosítással” számítjuk ki, figyelve arra, hogy páros, vagy páratlan számú tagból áll-e az összeg.
17
Ha az összeg páratlan számú tagból áll, az elejére 0-t írunk, így páros számú tag lesz, az összeg értéke viszont nem változott! Az azonosság igazolása szintén matematikai indukcióval történik. Az indukciós bizonyítást az olvasóra bízom. Feladat A következő kijelentés egy sajátos oszthatósági esetet igazol. p(n): Minden nemnulla n természetes számra igaz, hogy minden 9 n − 1 alakú természetes szám osztható 8-cal. Bizonyítás: I.lépés: p(1): 91 − 1 = 8 , ez osztható 8-cal. p(2): 9 2 − 1 = 81 − 1 = 80 , osztható 8-cal. II.lépés: 8 F.: p(k): 9 k − 1 Μ
(
(
)
)
K.: p(k + 1): 9 k +1 − 1 Μ 8 bizonyítás: A 9 k +1 − 1 kifejezést egyenértékű módon átalakítjuk, hogy fel lehessen használni az indukciós feltételt. 9 k +1 − 1 = 9 k ⋅ 9 − 1 = 9 k ⋅ 9 − 9 + 9 − 1 = 9 k ⋅ 9 − 9 + 8 = 9 ⋅ 9 k − 1 + 8 A kapott kéttagú összeg első tagja az indukciós feltétel alapján osztható 8-cal, a másik tag a 8, nyilvánvalóan osztható 8-cal. Mivel az összeg mindkét tagja osztható 8-cal, ezért az egész összeg osztható 8-cal. Ezzel a bizonyítás második része is be van fejezve. Tehát igaz maga a p(n) is, minden megadott n esetén.)
(
)
(
)
Feladat Adott a sík n különböző pontja, amelyek hármanként nem esnek egy egyenesbe (n ≥ 3) . n(n − 1) Igazoljuk, hogy ezen pontok által meghatározott egyenesek száma . 2 Bizonyítás: I.lépés 3 ⋅ (3 − 1) n = 3 egyenes estén 3 db egyenesünk van. Valóban 3 = . 2 II.lépés k (k − 1) F.: p(k): k db pont esetén egyenes van. 2 (k + 1)k K.: p(k + 1): k + 1 db pont esetén db egyenes van. 2 bizonyitás
18
Elképzeljük, hogy előzőleg már megrajzoltuk a k db, hármanként nem egy egyenesen k (k − 1) levő pontot és megrajzoltuk az általuk meghatározott db egyenest. (Ez képezi az 2 indukciós feltételt.) Vegyünk fel melléjük még egy, velük hármanként nem kollineáris pontot. Ebből az utolsó pontból a már megrajzolt egyenesek mellé pontosan k db egyenest kell húzni (az utolsónak felvett pontot összekötni a már ottlevőkkel.) k ⋅ (k − 1) k ⋅ (k − 1) + 2k k 2 − k + 2k k 2 + k k ⋅ (k + 1) +k = = = = egyenes Tehát összesen 2 2 2 2 2 van. Ezzel a bizonyítás véget ért, megadva a feleletet, hogy az adott feltételek mellett valóban n(n − 1) db egyenes köti össze a pontokat.) 2 A feladat tulajdonképpen azt igazoltatta, hogy egy n oldalú konvex sokszög oldalainak és n(n − 1) (n ≥ 3). átlóinak száma összesen 2
Más bizonyítási módszerek Ezek a bizonyítási módszerek tulajdonképpen kombinált módszerek, amelyeknél valamelyik módszer a hangsúlyosabb.
A konstruktív módszer A konstruktív módszer segítségével, esetenként felhasználva a matematika valamely területének eredményeit, gyakorlatilag „megszerkesztjük”, megalkotjuk, megkonstruáljuk magát a megoldást. Feladat - Ha megfelelően vágod le a hétfejű sárkány fejeit, megmenekülsz! - figyelmeztette a királyfit táltos paripája. - Egyiket sem vághatod annyiadikként, ahányadik a nyakán! - Legelőször és negyedikként páratlan sorszámú fejet kell levágnod! - A hatodik fej levágása után már csak ennek két szomszédja maradt levágatlan. A királyfi megmenekült. Milyen sorrendben vágta le a sárkány fejeit? Megoldás. Sorszámozzuk meg a feltételeket. Legyenek ezek (1), (2), (3) a feladatban megadott sorrendben. A levágás sorszámát római számmal, a fejek sorszámát arab számmal fogjuk jelölni. (3)-ból: A hatodik fejet ötödiknek vágja le, lásd (3)-as feltétel. A maradék két szomszéd fejet, az ötödiket és a hetediket az (1) alapján csak így vághatja le: a hetediket hatodiknak, az ötödiket hetediknek: 6. – V. 7. – VI. 5. – VII.
19
Maradt tehát az első négy fej és az első négy hely. A (2) alapján először a harmadik fejet, az elsőt pedig negyediknek vághatja le. A maradék második fejet harmadiknak, negyediket pedig másodiknak fogja levágni. Így a fejek levágási sorrendje: I. – 3., II. – 4., III. – 2., IV. – 1., V. – 6., VI. – 7., VII. - 5. Tehát a megoldás során a feltételekből kiindulva megszerkesztettük a megoldást. Feladat Nagyapa a következőképpen határozza meg éveinek számát: „Mindegyik gyermekemnek annyi gyereke van, mint ahány testvére. Éveim száma együttesen annyi, mint gyerekeim és unokáim száma együttesen.” Hány éves a nagyapa, ha életkora 50 és 80 év között van? Megoldás. Sorbavéve a lehetséges eseteket, megszerkesztjük a megfelelő megoldást. Eleinte jobban áttekinthetők az egyes esetek, ha le is rajzoljuk őket. Az alábbi táblázatban N = nagyapa, Gy = gyereke, U = unokája N Gy U GY U Ö
# ∆
1 0 1
2 2 4
# ∆∆ ¤¤ 3 6 9
4 12 16
5 20 25
# ∆∆∆ ¤¤¤¤¤¤ 6 30 36
7 42 49
8 56 64
# ∆∆∆∆ ¤¤¤¤¤¤¤¤¤¤¤¤ 9 72 81
Végigjárva az egymást követő eseteket, látható, hogy a nagyapa 64 éves. E feladatnál is a megoldás megszerkesztése, megkonstruálása történt meg.
Az algoritmikus módszer Az algoritmus egy eljárás menetét megadó egymásutáni lépések rendszere. Az algoritmus fő jellemzői: -általános, vagyis nemcsak sajátos esetekre alkalmazható, -szabatos és pontos, vagyis az eljárás során mindig eldönthető, hogy melyik lépés következik, -eredményes, vagyis véges számú konkrét lépés után eredményhez is vezet. A matematikában, az alsó tagozatos matematikában is, sok esetben használunk algoritmusokat: a műveletvégzésnél, főleg az írásbeli műveleteknél, az egyenletek megoldásánál, a műveletsorok elvégzésénél, stb. Az algoritmikus gondolkodás előnye, hogy szabatos, pontos, eredményes. Viszont előírásossága folytán gátolja a kreativitás fejlődését, mivel az algoritmus konvergens, a kreativitás viszont divergens gondolkodást igényel. Feladat Egy ötfős kirándulócsoport egy folyóhoz ér, ahol 2 gyerek játszik. Csak egy csónakkal kelhetnek át, amely egyszerre egy kirándulót, vagy legfennebb két gyereket vihet. Át tudnak-e kelni a túlsó partra, s ha igen, hány fordulatból?
20
Megoldás: A következőképpen járhatnak el: átmegy a két gyerek, az egyik visszahozza a csónakot, a másik ottmarad. Aztán átmegy egy kiránduló és a másik gyerek visszahozza a csónakot. Ekkor a folyó innenső oldalán van 4 kiránduló, 2 gyerek és a csónak. Tehát egy felnőtt átszállítása két fordulatba került. Ezt az algoritmust ismételjük még négyszer. Tehát 10 fordulattal jut át minden kiránduló a túloldalra, egészen pontosan 9,5 fordulattal, mivel a feladat nem köti ki, hogy a gyerekek a folyó melyik oldalára kell kerüljenek. A módszer a konstruktív és algoritmikus módszer keveréke, mert az először felépített rendszert ismételjük, ahányszor szükséges.
Az ellenpéldával történő cáfolás módszere Feladat Egy 8x8-as sakktábla minden mezőjét megszámozzuk az 1, 2, 3, 4 számok valamelyikével úgy, hogy bármelyik rácspontra illeszkedő négy mező különböző számokat tartalmazzon. Igaz-e, hogy a sarokmezők között vannak azonos számozásúak? Megoldás Tulajdonképpen megpróbálunk megkonstruálni egy megoldást. 1 2 A mellékelt 2x2-es tábladarabot ráhelyezzük a sakktáblára és a következő 3 4 elrendezést kapjuk: 1 3 1 3 1 3 1 3
2 4 2 4 2 4 2 4
1 3 1 3 1 3 1 3
2 4 2 4 2 4 2 4
1 3 1 3 1 3 1 3
2 4 2 4 2 4 2 4
1 3 1 3 1 3 1 3
2 4 2 4 2 4 2 4
Ezen az elrendezésen látható, hogy a feladat feltétele teljesül, viszont a sarokmezők számozása mind különböző. Tehát amit megszerkesztettünk, az egy ellenpélda. A megszerkesztés azt is mutatja, hogy bárhonnan kezdhetjük a számozott sarkot ráhelyezni a sakktáblára, a fentihez hasonló elhelyezést kapunk. Akkor sem változik a válasz, ha a 2x2-es négyzetben a számozás nem a fent megadott módon, de mindenképpen a feladat kérelmeinek megfelelően van. Tehát a válasz mindenképpen nemleges.
Az invariancia elve A feladat megoldásában segít a feladat megoldásakor, illetve a megoldás lépéseinek felépítésekor kapott bizonyos elemek invarianciája, változatlansága. A megoldás során figyelni kell erre, észre kell venni. 21
Feladat A Csodakert fáin 25 banán és 30 narancs van. Egy-egy alkalommal két gyümölcsöt szakítunk le, de rögtön visszanő egy. Ha egyformákat vettünk le, akkor egy narancs nő, ha különbözőeket, akkor egy banán nő helyettük. Milyen gyümölcs marad utolsónak? Megoldás 1.ha 2 b szakítunk egyszerre: 25 b 23 b 21 b 19 b 30 n 31 n 32 n 33 n 2.ha 2 n. szakítunk: 25 b 25 b 25 b 30 n 29 n 28 n 3.ha 1b és 1n: 25 b 25 b 25 b 30 n 29 n 28 n Tehát megfigyelve a meggondolásokat, látható, hogy a banánok száma mindig páratlan. Tehát a narancs elfogyhat teljesen, de megmarad 1 banán. Itt az invariáns a banánok páratlan száma. Feladat Van 24 papírlap, melyek közül néhányat 10 részre vágtak. Az így kapott részek közül néhányat ismét 10 részre vágtak., és így tovább. Egyszer valaki kijelenti: „Most éppen 2007 papírdarab van.” Jól számolt-e az illető? Megoldás A feladat adataiból következik, hogy a papírfecnik száma 9-cel nő: 24-ről 33-ra 24-ről 42-re, stb. Vagyis ilyen sorban: 24 33 42 51… Ez azt jelenti, hogy ebben a sorban a benne szereplő számoknak 9-cel való osztási maradéka nem változik, mindenik esetben 6, ez osztással kipróbálható. Viszont a 2007-nek 9-cel való osztási maradéka 0, tehát a fenti számok sorába nem illeszkedik a 2007. Másképpen mondva: a 2007 osztható 9-cel, de a kiinduló szám a 24, nem osztható 9-cel, tehát a sorba nem illik bele a 2007. Itt az invariancia a 6-os maradék. De úgy is fogalmazhatnánk, hogy a papírdarabkák száma állandóan 9-cel nő. Feladat Egy hosszú egyenes árokban egy sáska, egy szöcske és egy tücsök ül, ebben a sorrendben. Időnként valamelyik átugorja a szomszédját. Előfordulhat-e, hogy 2007 ugrás után újból a kiinduló sorrendben üljenek? (a rovarok csak az árokban, tehát csak egy egyenes mentén szökdöshetnek!) Megoldás
22
Jelöljük S=sáska, Z=szöcske, T=tücsök. Minden ugráskor egy helycsere történik. A mellékelt ágrajzot kaphatjuk: SZT
A diagramról leolvasható, hogy a páros sorszámú ugrások után kerülhetnek a kiinduló helyzetbe. Tehát a válasz nemleges. Itt az invariancia a párosság. ZST TSZ TZS ZTS ZST ZTS ZST SZT SZT TZS TSZ SZT STZ TSZ STZ
SZT
Feladat Egy téglalap alakú asztalra két játékos egymást váltva egyforma pénzérméket helyez. A már letett pénzeket nem szabad mozdítani, sem rátenni. Az a győztes, aki a pénzét még utolsónak rá tudja tenni az asztalra. Ha jó stratégiával játszik a kezdő, nyerhet. Hogyan? Megoldás A nyerő stratégia lényege az, hogy a kezdő játékos pontosan az asztal közepére teszi az első érmét. Az összes többi esetben a következő érmét úgy teszi, hogy az középpontosan szimmetrikusa legyen a játékostársa által tett érmének. Így a középpontos szimmetria miatt az előző játékos által tett érme szimmetrikusának mindig megmarad a helye. Tehát az első játékos meg tudja nyerni a játékot. Tehát az invariancia a téglalap belső pontjainak szimmetriája a középpontra nézve.
23
