IV. A MATEMATIKAI LOGIKA ELEMEI

Fejezet tartalma

Vissza 84

Tartalomjegyzék

A matematikai logika elemei

IV. A

MATEMATIKAI LOGIKA ELEMEI

IV.1. Kijelentések, logikai értékek

1.1. Értelmezés. Állításnak nevezünk minden nyelvtani értelemben vett kijelentő mondatot. Például a következő mondatok állítások: 1. A háromszög oldalfelezői összefutóak. 2. A víz 1 atm nyomásnál 100 C-on forrik. 3. Az emberi szervezetben a legtöbb Ca a csontokban található. 4. Peru fővárosa Stockholm. 5. A Duna hajózható. 6. A nagymama megőszült. 7. Az iskola legjobb nője Erzsi. 8. A világűrben vannak olyan értelmes lények, amelyek nem a Tejútrendszerben élnek. 9. Jövő héten esni fog az eső. 10. Ez a mondat hamis. Próbáljuk eldönteni, hogy az előbbi állítások közül melyek igazak és melyek hamisak. Az 1., 2., 3., és 5. állításokról tudjuk, hogy igazak, a 4.-ről tudjuk, hogy hamis (mert Stockholm Svédország fővárosa). A 6. állításról csak akkor tudjuk eldönteni, hogy igaz vagy sem, ha tudjuk, hogy kinek a nagymamájáról van szó. A 7. állítás szubjektív, ezért nem tudjuk eldönteni, hogy igaz-e vagy sem. A 8. állításról ismereteink korlátoltsága miatt nem tudjuk eldönteni, hogy igaz-e vagy sem. A 9. állítást ismét nem tudjuk igaznak vagy hamisnak minősíteni. A 10. állítás már bonyolultabb eset: ha feltételezzük, hogy igaz, akkor mivel önmagára vonatkozik hamisnak kell lennie. Ha viszont feltételezzük, hogy hamis, akkor nem lehet igaz amit állít, tehát igaznak kell lennie. Látható, hogy az ellentmondás feloldható, ha elfogadjuk, hogy erről az állításról sem lehet eldönteni, hogy igaz vagy hamis. A továbbiakban azokat az állításokat, amelyekről eldönthető, hogy igazak-e vagy hamisak kijelentésnek nevezzük. Ha a kijelentés igaz azt mondjuk, hogy igazságértéke vagy logikai értéke 1, ellenkező esetben 0. IV.1.1. Logikai műveletek A nyelv nagyon sok összetett mondata valamilyen logikai műveletet fed. Vizsgáljuk például a következő összetett kijelentések igazságértékét. IV.1.1.1. Konjunkció 1. A Hold a Föld körül kering és a Föld a Nap körül kering. 2. A farkasok húsevők és Kant költő volt. 3. A búza egy fém szerkezet és a kovácsok fizikai munkát végeznek. 4. Az őzek a sivatagban élnek és a számítógép tejes laskával működik. Az első kijelentés igaz, míg a többi nem, mert Kant nem volt költő (filozófus), a búza nem fémszerkezet, az őzek nem élnek a sivatagban és a számítógép nem laskával működik. Ez alapján, ha p és q két kijelentés, akkor a „ p és q ” is egy kijelentés és ez a kijelentés pontosan akkor igaz, ha mindkét kijelentés igaz. Értelmezés. A „ p és q ” kijelentést a p ∧ q szimbólummal jelöljük és p és q konjunkciójának nevezzük. Az előbbi megállapítást a következő igazságtáblázatba foglalhatjuk: p q p∧q 0 0 0 0 1 0 1 0 0 1 1 1

Fejezet tartalma

Tartalomjegyzék


85

IV.1.1.2. Diszjunkció Vizsgáljuk meg a következő összetett kijelentéseket: 1. A teknősbéka tud repülni vagy a számítógép tud úszni. 2. A bolha tud ugrani vagy a kutya nem tud harapni. 3. A természetes számok halmaza üres halmaz, vagy léteznek prímszámok. 4. Az AEÁ elnöke 2001-ben Bill Clinton vagy az AEÁ elnöke George W. Bush. Az első állítás hamis, mert a teknősbéka nem tud repülni és a számítógép sem tud úszni (egyelőre), a többi állítás viszont igaz, mert van legalább egy igaz részállítása (a bolha tud ugrani, az AEÁ elnöke 2001-ben George W. Bush és léteznek prímszámok). Értelmezés. Ha p és q két kijelentés, akkor a „ p vagy q ” kijelentést a p és q diszjunkciójának nevezzük és p ∨ q -val jelöljük. Az előbbiek alapján a következő táblázatba foglalhatjuk az igazságértékeket: p q p∨q 0 0 0 0 1 1 1 0 1 1 1 1 IV.1.1.3. Tagadás A legegyszerűbb logikai művelet, amit majdnem mindenki már kiskorában elsajátít, a tagadás. Egy állítás tagadását legtöbbször az állítmány elé tett „nem” szócskával fejezzük ki. Tagadjuk a következő kijelentéseket és vizsgáljuk meg a logikai értéküket: 1. A Biblia egy könyv. – igaz 2. A cápák ragadozó halak. – igaz 3. A bálnák emlősök. – igaz 4. A szénmonoxid nem mérgező az emberre nézve. – hamis A kijelentések tagadása a következő: 1. A Biblia nem könyv. – hamis 2. A cápák nem ragadozó halak. – hamis 3. A bálnák nem emlősök – hamis 4. A szénmonoxid mérgező az emberre nézve. – igaz Ha p egy kijelentés, akkor a p tagadását  p -vel jelöljük és „non p”-nek olvassuk. Az előbbiek alapján, ha p igaz, akkor  p hamis és fordítva. Ezt a következő táblázatba foglalhatjuk: p p 0 1 1 0 Feladat. Bizonyítsd be, hogy a  ( p ∧ q) kijelentés pontosan akkor igaz amikor a

( p) ∨ ( q)

kijelentés. Fogalmazd meg ezt nyelvi szinten, majd járj el hasonlóképpen a

 ( p ∨ q) kijelentéssel. Megoldás. Készítsük el mindkét kijelentés igazságtáblázatát. p q p∧q  ( p ∧ q) 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0

Fejezet tartalma

86

Tartalomjegyzék

A matematikai logika elemei p

q

p

q

( p) ∨ ( q)

0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 A két táblázat alapján a két kijelentés egy időben igaz. Nyelvileg ez a következőképpen fogalmazható meg: A p ∧ q kifejezés pontosan akkor hamis, ha p hamis vagy q hamis. Hasonlóan mondhatjuk, hogy a p ∨ q kijelentés pontosan akkor hamis, ha p is hamis és q is hamis. Ez matematikai szimbólumokkal úgy írható, hogy a  ( p ∨ q) pontosan akkor igaz,

( ) ( )

( ) ( )

( ) ( )

amikor a  p ∧  q igaz. Rövidebben a  ( p ∧ q) ≡  p ∨  q és  ( p ∨ q) ≡  p ∧  q

szimbólumokkal fejezhetjük ki. Ezeket az összefüggéseket nevezzük De Morgan törvényeinek. IV.1.1.4. Implikáció Vizsgáljuk meg a következő kijelentések logikai értékét: 1. Ha 1+1=2, akkor 1 + 1 ≠ 2 . 2. Ha egy háromszög egyenlő szárú, akkor van két kongruens oldala. 3. Ha 1 + 1 = 3 , akkor a háromszög szögeinek összege 180 ` . 4. Ha a tojás törhetetlen, akkor egyetlen ember sem evett tojáspudingot. Mind a négy példánál jelöljük p -vel az első állítást és q -val a másodikat. Az első esetben p igaz, q hamis és a kijelentés is hamis. A második esetben p -ről nem tudjuk, hogy igaz-e vagy sem, de az összetett kijelentés igaz. A harmadik esetben p hamis, q igaz és az összetett kijelentés igaz. Az utolsó esetben p is és q is hamis, az állítás mégis igaz. Értelmezés. Az előbbiekhez hasonlóan két tetszőleges p és q kijelentés esetén értelmezhetjük a „ha p , akkor q ” kijelentést. Ezt a „ p → q ” szimbólummal jelöljük, implikációnak nevezzük és következő az igazságtáblázata: p q p→q 0 0 1 0 1 1 1 0 0 1 1 1 Az implikáció segítségével értelmezhetjük az ekvivalenciát is. A p és q kijelentéseket ekvivalenseknek nevezzük, ha p → q és q → p . Ezt a p ↔ q szimbólummal jelöljük és az alábbi táblázat szerint kapjuk az igazságtáblázatát: p q p→q q→p ( p → q) ∧ (q → p) 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 A mellékelt táblázat további három művelet értelmezését tartalmazza. Ezeket ritkán fogjuk alkalmazni és a következő a megnevezésük: – Sheffer-féle művelet ↓ – Webb-féle művelet ⊕ – antivalencia vagy összeadás modulo 2.

Fejezet tartalma

Tartalomjegyzék

A matematikai logika elemei p

q

p|q

0 0 0 1 1 0 1 1 Érvényesek a következő tulajdonságok: 1. p | q ≡ ¬ ( p ∧ q) .

1 1 1 0

87 p↓q 1 0 0 0

p⊕q

0 1 1 0

2. p ↓ q ≡ ¬ ( p ∨ q ) . 3. p ⊕ q ≡ ¬ (( p → q) ∧ (q → p ) ) . 4. p | q ≡ q | p , p ↓ q ≡ q ↓ p és p ⊕ q ≡ q ⊕ p . 5. ( p | q | r ) ≠ p | (q | r ) . 6. ( p ↓ q ) ↓ r ≠ p ↓ (q ↓ r ) . IV.1.2. Gyakorlatok és feladatok 1. Készítsd el az alábbi kijelentések logikai értéktáblázatát:

( )

a)   p ;

b) p ∧ p ;

c) p ∨ p ;

d) p ∧ ( p ∨ q ) ;

e) p ∨ ( p ∧ q) ; f) ( p ∨ q) ∨ r ; g) p ∨ (q ∨ r ) ; h) ( p ∧ q ) ∨ r ; i) ( p ∨ q ) ∧ r ; j) ( p ∨ q ) ∧ (q ∨ r ) ; k) ( p ∧ r ) ∨ (q ∧ r ) . 2. Bizonyítsd be a következő összefüggéseket: a) p ∧ q ≡ q ∧ p ; b) p ∨ q ≡ q ∨ p ; c) p ∧ (q ∧ r ) ≡ ( p ∧ q ) ∧ r ; d) p ∨ (q ∨ r ) ≡ ( p ∨ q ) ∨ r ; e) p ∨ (q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r ) ; f) p ∧ (q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r ) . 3. Bizonyítsd be a következő összefüggéseket: a) p ↔ q ≡ q ↔ p ; b) ( p → q ) → r ≠ p → (q → r ) ;

( ( )) ;

c) p → q ≡ p ∧  q

( ) ( )

d) p → q ≡  q →  p .

4. Bizonyítsd be, hogy az alábbi kijelentések logikai értéke 1 függetlenül az őket alkotó kijelentések logikai értékétől. a) p → ( p ∨ q ) ; b) ( p ∧ q ) → p ; c) ( p ∧ ( p → q)) → q ; d) (( p → q) ∧ (q → r )) → q ; e) p → q → ((q → r ) → ( p → r )) ;

( )

g) p ∨  p ;

( ( )) .

h)  p ∧  p

Értelmezés. Az ilyen kifejezéseket tautológiának nevezzük. 5. Hány különböző módon lehet kitölteni az alábbi táblázat harmadik oszlopát, ha minden helyre 0 vagy 1 kerülhet? Bizonyítsd be, hogy a  , ∨ , ∧ műveletek segítségével mindegyik oszlop kifejezhető. p q (p, q) 0 0 0 1 1 0 1 1 6. Az előbbi műveletek közül melyek kommutatívak és melyek asszociatívak?

Fejezet tartalma

88

Tartalomjegyzék


7. Valaki 4 kártyát tett ki elénk. Mindegyiknek az egyik oldalán egy betű áll, másik oldalán egy szám. Legalább hány kártyát kell megfordítanunk ahhoz, hogy ellenőrizzük a következő kijelentéseket (külön-külön), ha a IV.1. ábrán látható betűket és számokat látjuk: a) Ha az egyik oldalon nagy betű áll, a másik oldalon páros szám áll. b) Ha az egyik oldalon páratlan szám áll, akkor másik oldalon mássalhangzó van.

a A

1

2

IV.1. ábra

IV.1.3. Predikátumok és kvantorok A kijelentések vizsgálatánál láttuk, hogy az „x osztja 6-ot”, „ a < b ” állítások nem kijelentések, mert nem pontosan definiált alannyal rendelkeznek. Ha az előbbi állításokban x -t, a -t és b -t valamilyen számokkal helyettesítjük, akkor kijelentésekhez jutunk. Az ilyen állításokat predikátumoknak nevezzük. 1.3.1. Értelmezés. Azokat az állításokat, amelyekben egy vagy több változó szerepel és azzal a tulajdonsággal rendelkeznek, hogy a változóknak minden megengedett értékére kijelentéshez jutunk, predikátumnak nevezzük. A predikátum értelmezéséhez szükséges megadni, hogy a változói milyen halmazokból vehetik fel az értékeiket. 1.3.2. Példák. 1. P ( x) : „ x − 1 = 7 ”, ahol x ∈ . 2. P ( x) : „ x -nek hét oldala van”, ahol x ∈ { háromszög, négyszög } . 3. P( x, y ) : „ x tulajdonosa y -nak”, ahol x az emberek halmaza és y a biciklik halmaza. 4. P( x, y ) : „ x ≥ y ”, x ∈ + és y ∈ − . Az előbbi példáknál látható, hogy léteznek olyan predikátumok, amelyek a változók egyetlen értékére sem válnak igaz kijelentésekké (pl. 2.) és olyan predikátumok, amelyek a változók minden értékére igaz kijelentést szolgáltatnak. Általában képezhetjük a következő kijelentéseket: „Létezik x ∈ A úgy, hogy P ( x) igaz legyen”. „Bármely x ∈ A esetén P ( x) igaz”. 1.3.3. Értelmezés. Az elsőt a ∃ x ∈ A : P ( x) , míg a másodikat a ∀ x ∈ A : P ( x) szimbólummal jelöljük. A ∀ és ∃ szimbólumot univerzális illetve egzisztenciális kvantoroknak nevezzük. IV.1.3.1. Gyakorlatok 1. Vizsgáljuk meg az alábbi kijelentések logikai értékét: a) ∃ n ∈ : 2n = n 2 ; b) ∀ x ∈ : x 2 ≥ 0 ; c) ∃ n ∈

: n2 + n = 1 ;

d) ∀ x ∈

∃y∈

úgy, hogy x + y = 0 ;

e) ∀ x ∈ [1, 2] : x − 3 x + 2 ≤ 0 . 2. Írd fel kvantorok segítségével az alábbi mondatokat, próbálj minden mondatot kétféleképpen felírni, egyszer univerzális és egyszer egzisztenciális kvantorral. a) Nincsen rózsa tövis nélkül. b) Nem mind arany, ami fénylik. c) Nem minden papsajt. 2

Fejezet tartalma


Tartalomjegyzék

89

3. Tagadd a következő predikátumokat/mondatokat: a) ∀ x ∈ [1, ∞ ] : x > 0 ; b) Bármely erdőlakó tud tüzet rakni. c) Van olyan diák, aki nem tud puskázni. d) Minden tanár érti, amit tanít, kivéve a rendőrtanárt. e) Minden diáknak legalább egy tanár szimpatikus. f) Minden héten legalább egyszer boldog vagyok. g) Létezik olyan tantárgy, amit nem szívesen tanulok. h) Létezik olyan tanár, aki minden őt kedvelő diákot kedvel. IV.1.4. Néhány furfangos logikai feladvány 1.4.1. Az A városban igazmondók (mindig igazat mondanak) és a B városban lókötők (ők mindig hazudnak) laknak. Egy vándor A városba szeretne jutni és egy olyan útkereszteződéshez érkezett, ahonnan az egyik út az A városba, a másik a B városba vezet. A vándor nem tudja, hogy melyik út vezet az A városba és melyik a B városba, de éppen találkozik ott valamelyik város lakójával (de nem tudja, hogy melyik város lakójával!). Egyetlen kérdéssel el tudja-e dönteni, hogy melyik út vezet az A városba? Hát akkor, ha csak olyan kérdést tehet fel, amelyre igennel vagy nemmel lehet válaszolni? Megoldás. Elégséges megkérdezni, hogy: „Mit válaszolna a másik város egy lakója, ha azt kérdezném, hogy melyik út vezet az A városba?” Ha a kérdezett az A városból van, akkor igazat fog mondani, tehát azt mondja, amit egy B városbeli mondana. A B városbeli hazudna, tehát a B város felé vezető utat mutatná, így a kérdezett is a B városba vezető utat fogja mutatni. Ha a kérdezett a B városból van, akkor hazudni fog. De a másik város lakója megmutatná a helyes utat, tehát a kérdezett ebben az esetben is a B városba vezető utat mutatja meg. Ha csak olyan kérdést lehet feltenni, amelyre igennel vagy nemmel lehet válaszolni, akkor a következő kérdés megfelel: „Igaz-e, hogy a másik város lakói azt mondanák, hogy a bal oldali út vezet az A városba?” Ha erre a kérdésre a válasz igen, akkor a bal oldali utat kell választania ellenkező esetben a jobb oldalit. Ez a következő táblázatból olvasható ki: A másik város lakója A kapott válasz A bal oldali út A kérdezett A -ból van mit mondana vezet A -ba Igaz Igaz Nem Nem Igaz Hamis Igen Nem Hamis Igaz Igen Igen Hamis Hamis Nem Igen 1.4.2. A vándor találkozik két emberrel, M -mel és N -nel, akik A -ban, vagy B -ben laknak. Ha M azt mondja, hogy „Én lókötő vagyok, de N nem az.”, meg tudjuk-e állapítani, hogy lókötők vagy sem? Megoldás. Tekintjük a következő állításokat: p : M nem lókötő. q : N nem lókötő. M nem lehet igazmondó, mert akkor állításának saját magára vonatkozó része ellentmondana ennek. Így M lókötő és a kijelentése hamis. Ez csak akkor teljesülhet, ha N is lókötő, tehát a vándor két lókötővel találkozott. A megoldás a formális logika segítségével a következőképpen írható le: p

q

0 0 1 1

0 1 0 1

p 1 1 0 0

( p) ∧ q

p állítása

0 1 0 0

0 0 1 1

Tartalomjegyzék

Fejezet tartalma

90


Mivel az utolsó két oszlop elemei csak az első helyen egyformák, sem p , sem q nem igaz, tehát M is és N is lókötő. IV.1.4.1. Gyakorlatok és feladatok 1. A és B egymástól függetlenül igazmondó vagy lókötő. A azt állítja, hogy „Legalább az egyikük lókötő.” Lókötők-e vagy sem? 2. Meg lehet-e állapítani, hogy lókötők-e, ha A azt mondja, hogy „Lókötő vagyok vagy B igazmondó”? 3. A , B és C egymástól függetlenül igazmondó vagy lókötő és a következőket mondják. A : Mindnyájan lókötők vagyunk. B : Pontosan egy igazmondó van köztünk. Meg lehet-e állapítani, hogy ki lókötő és ki nem? 4. A és B egymástól függetlenül igazmondó, lókötő vagy kiismerhetetlen (ezek néha hazudnak és néha igazat mondanak) Az igazmondókat tartják felsőbb, a kiismerhetetleneket közép és a lókötőket alsóbb osztálynak. A következő két állítás alapján el lehet-e dönteni, A vagy B osztályát? Hát azt, hogy az állítások közül melyik igaz és melyik hamis? A :Alacsonyabb osztálybeli vagyok, mint B . B :Ez nem igaz! 5. A IV.2. ábrán látható ládikák egyikében egy korona van. Meg lehet-e állapítani, hogy melyikben van a korona, ha az egyik ládikán sincs egynél több hamis állítás? A korona nem ebben van. A korona Szent Istváné volt.

A korona nem az 1.ládikában van. A korona II. Lajos királyé volt.

A korona nem ebben van. A korona 2. ládikában van.

IV.2. ábra

6. A és B egymástól függetlenül igazmondó vagy lókötő. A azt állítja, hogy: „Ha én igazmondó vagyok, akkor B is az.” Igazmondókkal vagy lókötőkkel van dolgunk? 7. Egy szultán, akinek két lánya volt, azt mondta egy vendégségbe érkezett hercegnek: – Mondanod kell egy állítást. Ha igaz, hozzád adom a nagyobbik lányomat, ha nem, akkor nem veheted őt feleségül. Kevés gondolkodás után a herceg mondott egy mondatot és a szultán kénytelen volt a kisebbik lányt feleségül adni a herceghez. Mit mondhatott a herceg? 8. Mit mondhatott a herceg, ha a szultán mindkét lányát hozzá kellett adja feleségül?

IV.2. Bizonyítási módszerek IV.2.1. A lehetetlenre való visszavezetés*

(

)

2.1.1. Értelmezés. Ha p és q két állítás, akkor a  ( p → q ) ⇔  q → p  ekvivalencia   alapján történő bizonyítást nevezzük lehetetlenre való visszavezetésnek. Ez gyakorlatilag azt jelenti, hogy igaznak feltételezzük a kijelentés tagadását és megpróbálunk eljutni egy olyan tulajdonsághoz, amely ellentmond a feltevésnek vagy valamilyen más ismert tulajdonságnak. 2.1.2. Példák 1. Bizonyítsuk be, hogy végtelen sok prímszám van. Bizonyítás. Tételezzük fel, hogy véges sok prímszám van és ezek a p1 , p 2 , … p n számok. Vizsgáljuk meg az N = p1 p 2 ⋅ ⋅ p n + 1 számot. N vagy prímszám vagy összetett szám. Az *

Reductio ad absurdum vagy indirekt bizonyítás néven is előfordul

Fejezet tartalma


Tartalomjegyzék

91

N > p j egyenlőtlenségek és a feltevés alapján N nem lehet prímszám. Így N -nek létezik p

prímosztója. Ez a prímosztó nem lehet a p1 , p 2 , … p n számok egyike sem, mert a p j | p1 p 2 p n és p j | N oszthatóságok alapján p j | 1 . Ez ellentmondás, mert minden p j prímszám nagyobb, mint 1 és így nem lehet az 1 osztója. Az előbbi ellentmondás alapján a feltevésünk nem lehet igaz, tehát végtelen sok prímszám létezik. A 2. Bizonyítsuk be, hogy ha egy háromszög két belső szögfelezője IV.3. kongruens, akkor a háromszög egyenlő szárú. ábra M Bizonyítás. Az ABC háromszögben legyen BB ′ és CC ′ a két kongruens belső szögfelező és tételezzük fel, hogy a háromszög nem egyenlő szárú, tehát AB > AC vagy AC > AB . A szimmetria miatt elégséges csak az egyik esetet megvizsgálni, B’ C’ tehát feltételezhetjük, hogy AB > AC .Megszerkesztjük a B ′BC ′M paralelogrammát. Az AB > AC egyenlőtlenség alapján 1 1 m(Cˆ ) > m( Bˆ ) , tehát m(Cˆ ) > m( Bˆ ) és így 2 2 B m(C ′Cˆ A) > m(C ′Mˆ B ′). (1) . Másrészt az MC ′C háromszög egyenlőszárú ( MC ′ = BB ′ = CC ′ ), tehát m(CMˆ C ′) = m(C ′Cˆ M ) (2) . Az (1) és (2) alapján m( B ′Cˆ M ) < m( B ′Mˆ C ) , tehát B ′M < B ′C . De a B ′BC és C ′CB háromszögekben CC ′ = BB ′ , BC = BC és m(C ′Cˆ B ) > m( B ′Bˆ C ), tehát BC ′ > B ′C > B ′M . Ez ellentmondás, mert BC ′ = B ′M az MC ′BB ′ paralelogrammában. (IV.3. ábra)

IV.2.1.1. Gyakorlatok és feladatok 1. Bizonyítsd be, hogy minden természetes szám 1-nél nagyobb egész kitevőjű hatványának kettes számrendszerbeli alakjában előfordul zérus számjegy. 2. Képzeljük el leírva valamilyen sorrendben egymás után a természetes számokat. Karikázzuk be azokat, amelyek legalább akkorák, mint ahányadik helyen állnak a sorban. Bizonyítsuk be, hogy így végtelen sok számot kell bekarikázni. 1  1  esetén sem 3. Bizonyítsd be, hogy az  n 2 − , n 2 +  intervallum egyetlen n ∈ 3n  3n  tartalmaz egész számot. 21n + 4 4. Bizonyítsd be, hogy a tört egyetlen n ∈ estén sem egyszerűsíthető. 14n + 3 5. Bizonyítsd be, hogy ha hét szám közül bármely négy összege nagyobb a többi három összegénél, akkor a számok pozitívak. 6. Bizonyítsd be, hogy ha a , b és c páratlan természetes számok, akkor az ax 2 + bx + c = 0 egyenletnek nincs egész gyöke. m m2 7. Bizonyítsd be, hogy ha 2 ∉ , akkor ∉ ( m, n ∈ , n ≠ 0 ) . n n 2 m m 8. Bizonyítsd be, hogy ha 2 ∈ , akkor ∈ ( m, n ∈ , n ≠ 0 ) . n n 9. Bizonyítsd be, hogy négy egymás utáni természetes szám szorzata nem lehet teljes négyzet.

Fejezet tartalma

92

Tartalomjegyzék


IV.2.2. A matematikai indukció módszere 2.2.1. Feladat. Oszd fel a háromszöglapot 2, 3, 4, 5 ,6 és 7 derékszögű háromszöglapra. Fel tudnád-e bontani 2001 derékszögű háromszögre, hát 12372-re? Megoldás. Minden háromszögnek van olyan magassága, amely a IV.4. ábra háromszög belsejében van. (IV.4. ábra) Ez a magasság két derékszögű háromszögre osztja a háromszöget. Az előbbi két derékszögű háromszög egyikének belsejében húzzuk meg a derékszöghöz tartozó magasságot. Így három derékszögű háromszöget kapunk. Ha ezt folytatjuk rendre kapunk egy-egy felbontást 4, 5, 6 és 7 derékszögű háromszögre (lásd a IV.5. ábrát). Látható, hogy az eljárást folytatva (egy meglevő derékszögű háromszög derékszögéhez tartozó 3

IV.5. ábra

4

5

6

7

magasságát húzzuk meg) minden lépésben eggyel nő a felbontás háromszögeinek száma. Így 2000 lépés után 2001 derékszögű háromszögre és 12371 lépés után 12372 derékszögű háromszögre bonthatjuk az adott háromszöget. Az előbbiek alapján ahhoz, hogy igazoljuk egy természetes számtól függő P (n) állítást bármely n ≥ a esetén, elégséges igazolni, hogy P (a ) igaz és, hogy ha P (n) igaz, akkor P (n + 1) is igaz. Ezt nevezzük a matematikai indukció elvének. Fontossága miatt külön tételként is megfogalmazzuk: 2.2.2. Tétel. Ha P (n) egy állítás, amely n ≥ a természetes számoktól függ és teljesül a következő két tulajdonság: a) P (a ) igaz, b) ha P (n) igaz, akkor P (n + 1) is igaz, akkor P (n) igaz bármely n ≥ a esetén. 2.2.3. Megjegyzések 1 .Az előbbi tétel ekvivalens azzal, hogy bármely X ⊂ halmazban van legkisebb elem. 2. Feladattól függően különböző módosított alakokat is használhatunk. Például, ha P (n) egy állítás, m rögzített szám, és Q(n) pontosan akkor teljesül, ha P (n) , P (n + 1) , … , P (n + m + 1) teljesül, akkor a Q(n) -re használt indukció a P (n) -re átfogalmazva a következőképpen néz ki: 2.2.4. Tétel. Ha P (n) egy állítás, amely természetes számoktól függ és tejesül az alábbi két tulajdonság: a) P (a ) , P (a + 1) , … , P (a + m − 1) igazak, b) P (n) igaz ⇒ P (m + n) igaz, akkor P (n) igaz bármely n ≥ a estén. Ha a H (n) pontosan akkor teljesül, ha P (a ) , P (a + 1) , … , P (a + n) igazak, akkor a H-ra felírt indukció P -re a következő tételt adja:

Fejezet tartalma

Tartalomjegyzék


93

2.2.5. Tétel. Ha P (n) állítás, amely természetes számoktól függ és teljesül az alábbi két tulajdonság: a) P (a ) igaz, b) ha P (a ) , P (a + 1) , … , P (a + n) igaz, akkor P (a + n + 1) is igaz, akkor P (n) igaz bármely n ≥ a esetén. Látható, hogy ezeknek a feltételeknek a használata kiküszöbölhető a P (n) állítás átfogalmazásával. Gyakran előfordul, hogy P (n) → P(n + 1) implikáció igazolásához közbeeső lépések szükségesek. Leggyakrabban P (n) → P(2n) → P (n + 1) közbeeső implikációt vagy még egy indukciót szoktunk használni. IV.2.2.1. Megoldott feladatok 1. Bizonyítsuk be, hogy n(n + 1) n(n + 1)(2n + 1) 1 + 2 + 3 +…+ n = és 12 + 2 2 + 3 2 + … + n 2 = ∀n ∈ * 6 2 n(n + 1) Bizonyítás. P (n) az az állítás, mely szerint 1 + 2 + 3 + … + n = . 2 2⋅3 1⋅ 2 I.. Ellenőrizzük P (1) -et. 1 = , tehát P (1) igaz. 1 + 2 = = 3 , tehát P (2) is igaz. 2 2 II. Ha P (n) igaz, akkor  n ⋅ (n + 1)  1 + 2 + 3 + … + n + (n + 1) = [1 + 2 + 3 + … + n] + (n + 1) =   + (n + 1) = 2   n  ( n + 1 )( n + 2 ) = (n + 1) ⋅  + 1 = , 2 2  tehát P (n + 1) is igaz. A matematikai indukció elve alapján P (n) igaz, bármely n ≥ 1 -re. n(n + 1)(2n + 1) Hasonlóképpen járunk el a második egyenlőséggel is. P (n) :12 + 2 2 + … n 2 = . 6 1⋅ 2 ⋅ 3 = 1 , tehát P (1) igaz. I. 12 = 2 n(n + 1)(2n + 1) II. Ha P (n) igaz, akkor 12 + 2 2 + … + n 2 + (n + 1) 2 = = 2 (n + 1) (n(2n + 1) + 6n + 6) = (n + 1) (2n 2 + 7n + 6) = (n + 1)(n + 2)(2n + 3) , tehát P(n + 1) = 6 6 6 is igaz. A matematikai indukció elve alapján P (n) igaz, bármely n ≥ 1 esetén. Megjegyzés. Sematikusan az indukció leírható a következő P(1) implikációkkal: P(2) P (1) igaz. P(3) P (1) igaz ∧[ P(1) → P (2)] ⇒ P (2) igaz. P(4) P (2) igaz ∧[ P (2) → P (3)] ⇒ P (3) igaz. P(5) P (3) igaz ∧[ P (3) → P (4)] ⇒ P (4) igaz.

P (n − 1) igaz ∧[ P (n − 1) → P (n)] ⇒ P (n) igaz.

IV.6. ábra

P(6)

Fejezet tartalma

94

Tartalomjegyzék


2. Bizonyítsuk be, hogy 4 n + 15n − 1 osztható 9-cel, bármely n ≥ 1 esetén. Bizonyítás. Legyen P (n) : „ 4 n + 15n − 1 9 ”.

(

)

I. 4 + 15 ⋅1 − 1 = 18 és 18 9 , tehát P (1) igaz. 1

II. Ha P (n) igaz, akkor létezik m ∈

úgy, hogy 4 n + 15n − 1 = 9m , tehát 4 n = 9m − 15n + 1 .

Így 4 n +1 = 36m − 60n + 4 , tehát 4 n +1 + 15(n + 1) − 1 = 36m − 45n + 18 = 9(4m − 5m + 2) . Az

(

)

előbbi egyenlőségek alapján 4 n +1 + 15(n + 1) − 1 9 , tehát P (n + 1) igaz. A matematikai indukció elve alapján P (n) igaz bármely n ≥ 1 esetén. 1 1 1 13 + + + > , bármely n ≥ 2 -re. n +1 n + 2 2n 24 1 1 1 13 Bizonyítás. Jelöljük P (n) -nel az „ + + + > ” állítást. n +1 n + 2 2n 24 1 1 7 13 I. + = > , tehát P (2) igaz. 3 4 12 24 1 1 1 1 1 1 1 II. Ha P (n) igaz, akkor + + + + + = + + n+2 n+3 2n 2n + 1 2n + 2 n + 1 n + 2 1 1 1 1 13 1 1 13 + − + − > > , tehát P (n + 1) is igaz. + − 2n n + 1 2n + 1 2n + 2 24 2n + 1 2n + 2 24 A matematikai indukció elve alapján P (n) igaz bármely n ≥ 1 esetén.

3. Bizonyítsd be, hogy

+

4. Bizonyítsd be, hogy 13 + 2 3 + 3 3 + + n 3 teljes négyzet minden n ∈ esetén. Bizonyítás. Ahhoz, hogy indukcióval igazolhassuk a kért tulajdonságot, meg kell fogalmaznunk egy olyan P (n) állítást, amelyre a matematikai indukció elvét alkalmazzuk. E célból vizsgáljuk meg előbb, hogy milyen számok teljes négyzetei jelennek meg. 13 = 12 , 13 + 2 3 = 9 = 3 2 , 13 + 2 3 + 3 3 = 36 = 6 2 , 13 + 2 3 + 3 3 + 4 3 = 100 = 10 2 , 13 + 2 3 + 3 3 + 4 3 + 5 3 = 225 = 15 2 . Tehát, ha N n -nel jelöljük azt a számot, amelynek 13 + 2 3 + 3 3 + + n 3 a négyzete, akkor a következő táblázathoz jutunk: n 1 2 3 4 5 1 3 6 10 15 Nn A táblázat második sorában az egymás utáni elemek különbsége rendre 1, 2, 3, 4, 5, tehát úgy tűnik valamiféle szabályosságra bukkantunk. Ezt ellenőrizhetjük további értékekre a következő táblázat alapján: n 1 2 3 4 5 6 7 8 1 3 6 10 15 21 28 36 Nn A táblázat második sorában a második elemtől kezdődően minden elem a felette álló és a baloldali szomszédjának összege. Eszerint 6=3+3=1+2+3 10=6+4=1+2+3+4 15=10+5=1+2+3+4+5.

Fejezet tartalma

Tartalomjegyzék


95

Tehát az 1. feladat alapján azt sejtjük, hogy N n =

n(n + 1) vagyis 2 2

 n(n + 1)  1 + 2 + 3 + ... + n =   .  2  3

3

3

3

2

 n(n + 1)  Ha P (n) az „ 13 + 2 3 + 3 3 + ... + n 3 =   ” állítás, akkor eddigi számolásaink alapján  2  P (1) , P (2) , ... , P (5) igaz állítások. Másrészt, ha P (n) igaz, akkor 2

 n(n + 1)  3 13 + 2 3 + 3 3 + ... + n 3 + (n + 1) 3 =   + (n + 1) =  2  2

 n2  n 2 + 4n + 4 (n + 1) 2 (n + 2) 2  (n + 1)(n + 2)  (n + 1) 2  + n + 1 = (n + 1) 2 = =   , 4 4 4 2     tehát P (n + 1) igaz. A matematikai indukció elve alapján P (n) igaz, bármely n ≥ 1 esetén. A bizonyított

azonosságból következik, hogy 13 + 2 3 + 3 3 + + n 3 teljes négyzet. Megjegyzés. Az előbb észlelt jelenség, mely szerint egy pontosabb (precízebb) állítást könnyebben tudunk igazolni, mint egy pontatlan állítást, a „kutatók paradoxonjaként” vált ismertté. 5. Bizonyítsuk be, hogy minden 1-nél nagyobb természetes szám felírható 2k1 + 3k 2 alakban, ahol k1, 2 ∈ . Bizonyítás. Világos, hogy ha n = 2k 1 + 3k 2 , akkor n + 2 = 2(k1 + 1) + 3k 2 , tehát ha P (n) az az állítás, mely szerint: „létezik k1, 2 ∈ úgy, hogy n = 2k 1 + 3k 2 ”, akkor P (n) -ből következik P (n + 2) . Így az indukció teljességéhez szükséges ellenőrizni a P (2) és P (3) állításokat. De 2 = 2 ⋅1 + 3 ⋅ 0 és 3 = 2 ⋅ 0 + 3 ⋅ 1 , tehát P (2) és P (3) igazak. Az előbbiek és a matematikai indukció elve alapján P (n) igaz bármely n ≥ 2 esetén. 6. Bizonyítsuk be, hogy ha x1 , x 2 , ... , x n ≥ 0 , akkor x + x 2 + ... x n n x x ... x ≤ 1 . 1 2 n n x + x2 egyenlőtlenség, bármely x1 , x 2 ≥ 0 esetén igaz, mert x1 x 2 ≤ 1 Bizonyítás. Az 2 ( x1 − x 2 ) 2 ≥ 0 . Ez alapján 4

x1 x 2 x 3 x 4 =

x1 x 2

x3 x 4 ≤

x1 x 2 + x 3 x 4

x1 + x 2 x3 + x 4 + 2 2 ≤ = 2

2 x1 + x 2 + x3 + x 4 . = 4 Ha ebben az egyenlőtlenségben x 4 = 3 x1 x 2 x 3 -at választunk, akkor a következő átalakításokat végezhetjük: 44 x1 x 2 x 3 3 x1 x 2 x 3 ≤ x1 + x 2 + x 3 + 3 x1 x 2 x 3 ⇔ 43 x1 x 2 x 3 ≤ x1 + x 2 + x 3 + 3 x1 x 2 x 3 ⇔

Fejezet tartalma

96

Tartalomjegyzék


x1 + x 2 + x 3 , tehát a kitűzött egyenlőtlenség igaz 3 3 (sőt 4) számra is. Ha igaz az egyenlőtlenség n számra és x1 , x 2 , ... , x n , x n +1 , ... , x 2 n 2n darab pozitív szám, akkor ⇔ 33 x1 x 2 x 3 ≤ x1 + x 2 + x 3 ⇔

2n

x1 x 2 ... x n x n +1 ... x 2 n =

n

3

x1 x 2 x 3 ≤

x1 x 2 ... x n

n

x n +1 x n + 2 ... x 2 n ≤

x1 x 2 ... x n + n x n +1 x n + 2 ... x 2 n

n

2

≤

x1 + x 2 + ... + x n x n +1 + x n + 2 + ... + x 2 n + x + x 2 + ... + x 2 n n n ≤ = 1 . 2n 2

Ha

ebben

az

egyenlőtlenségben

x n + 2 = x n + 3 = ... = x 2 n = n +1 x1 x 2 ... x n +1 ,

akkor

az

egyenlőtlenség a következőképpen alakítható: 2n

x1 x 2 ... x n +1 ( n +1 x1 x 2 ... x n +1 ) n −1 ≤

x1 + x 2 + ... + x n +1 + (n − 1) n +1 x1 + x 2 + ... x n +1 2n

⇔

⇔ 2n n +1 x1 x 2 ... x n +1 ≤ x1 + x 2 + ... + x n +1 + (n − 1) n +1 x1 x 2 ... x n +1 ⇔ x1 + x 2 + ... + x n +1 . n +1 x + x 2 + ... + x n x1 x 2 ... x n ≤ 1 , bármely n ≥ 2 és n

⇔ n +1 x1 x 2 ... x n +1 ≤

A matematikai indukció elve alapján

n

x1 , x 2 , ... , x n ≥ 0 számok esetén.

IV.2.2.2. Gyakorlatok és feladatok 1. Bizonyítsuk be, hogy 1 1 1 1 1 a) + + + ... + = 1− ; 1⋅ 2 2 ⋅ 3 3 ⋅ 4 n ⋅ (n + 1) n +1 n(n + 1)(n + 2) ; b) 1 ⋅ 2 + 2 ⋅ 3 + 3 ⋅ 4 + ... + n ⋅ (n + 1) = 3 n n +1 c) (1 + 2)(1 + 2 2 )(1 + 2 4 )(1 + 2 8 ) ⋅ ... ⋅ (1 + 2 2 ) = 2 2 − 1 ; 1  1  1  1  n +1   ; d) 1 − 2 1 − 2 1 − 2  ⋅ ... ⋅ 1 − 2  = 2n 2 3 4 n       n(n + 1) e) 12 − 2 2 + 3 2 − ... + (−1) n −1 n 2 = (−1) n −1 ; 2 n(n + 1) 1 1 1 + + ... + = . f) 1⋅ 3 ⋅ 5 3 ⋅ 5 ⋅ 7 (2n − 1)(2n + 1)(2n + 3) 2(2n + 1)(2n + 3) 2. Számítsd ki az alábbi összegeket, majd bizonyítsd a kapott eredményt a matematikai indukció módszerével: a) 1 ⋅ 2 ⋅ 3 + 2 ⋅ 3 ⋅ 4 + ... + n(n + 1)(n + 2) ; b) 1 ⋅ 3 + 2 ⋅ 5 + 3 ⋅ 7 + ... + n(2n + 1) ;

c) 1 ⋅ 4 + 2 ⋅ 7 + 3 ⋅10 + ... + n(3n + 1) ; e)

1 1 1 + + ... + ; 1⋅ 4 4 ⋅ 7 (3n − 2)(3n + 1)

d)

1 1 1 + + ... + ; 1⋅ 3 3 ⋅ 5 (2n − 1)(2n + 1)

f)

n

4k ; 4 +1

∑ 4k k =1

Tartalomjegyzék

Fejezet tartalma

A matematikai logika elemei n

g)

97

1

∑ (k + 1)

. k + k k +1 3. Számítsd ki a következő összegeket: a) 1 + x + x 2 + x 3 + ... + x n ; k =1

b) x + 2 x 2 + 3 x 3 + ... + nx n ; n −1

x x2 x4 x2 c) . + + + ... + n 1− x 2 1− x 4 1− x8 1− x 2 4. Bizonyítsd be a következő egyenlőtlenségeket: k

k  1 b) 1 +  ≥ 1 + n, k ∈ n  n

a) 2 n ≥ n 2 ∀ n ≥ 4 ;

*

c) (1 + x ) n ≥ 1 + nx (Bernoulli egyenlőtlenség), ha n ∈

(

)

d) 2 n + 1 − 1 < 1 +

1 2

1

+

3

1

+ ... +

n

*

; és x > 0 ;

<2 n ;

1 3 5 2n − 1 1 ⋅ ⋅ ⋅ ... ⋅ < , ∀n >1; 2 4 6 2n 3n + 1 n +1 1 1 1 1 f) < 1 + + + + ... + n
e)

i) 2 n > n 2 + 4n + 5 , ∀ n ≥ 6 ;

j)

n 2 + 2n − 2 < 6

n

∑

k

n 2 + 3n − 4 . 4

k! <

k =2

5. Bizonyítsd be a következő egyenlőtlenségeket: 2

 n  n   n  a)  ∑ ak2   ∑ bk2  ≥  ∑ ak bk  , ha ak , bk ∈  k =1   k =1   k =1 

;

b) a1 + a 2 + ... + a n ≤ a1 + a 2 + ... + a n , ha ak ∈ , k = 1, n ; c) 2 n −1 (a n + b n ) ≥ (a + b) n , ha a, b ∈ d) Ha x1 + x 2 + ... + x n ≤

és a + b > 0 ;

1 és x j ≥ 0 ∀ j = 1, n , akkor 2 (1 − x1 )(1 − x 2 ) ⋅ ... ⋅ (1 − x n ) ≥

e)

n ( x + 1)( x + 2 n)

≤

1 x +1

−

1 x+2

+ ... +

1 x + 2n − 1

[

−

1 ; 2

1 x + 2n

<

]

k

n 1  1   x +  x + 2n +  2  2 

f) Ha k , n ∈ és 0 ≤ x ≤ 1 , akkor 1 − (1 − x) n ≥ 1 − (1 − x k ) n . 6. Bizonyítsd be a következő oszthatóságokat: a) 4 | 15 n + 3 n +1 ; b) 9 | 16 n − 6n − 1 ; c) 7 | 5 ⋅ 2 n −1 + 9 4 n −3 ;

(

(

d) 17 | 3 ⋅ 5

)

2 n +1

+2

3 n +1

);

(

(

e) 133 | 11

)

n+2

+ 12

2 n +1

);

(

(

f) 23 | 2

)

7 n +3

+3

2 n +1

)

⋅ 4 4 n +1 .

;

Tartalomjegyzék

Fejezet tartalma

98


7. Bizonyítsd be, hogy minden háromszög feldarabolható n darab hozzá hasonló háromszögre, ha n ≥ 6 . 8. Feldarabolható-e egy általános háromszög n darab egyenlőszárú háromszögre, ha n ≥ 4 ? 9. Bizonyítsd be, hogy ha n ≥ 6 , akkor egy tetszőleges négyzet feldarabolható n darab négyzetre. 10. Bizonyítsd be, hogy az (n + 1)(n + 2) ⋅ ... ⋅ (2n) szorzatban a 2 kitevője pontosan n . 11. Bizonyítsd be, hogy minden n ∈ * esetén 2 n -nek létezik olyan egész számú többszöröse, amely csak az 1 és 2 számjegyekből áll. 12. Bizonyítsd be, hogy

1 + 2 + ... + n < 2 bármely n ∈

*

esetén.

IV.2.3. A végtelen leszállás elve 2.3.1. Értelmezés. A végtelen leszállás elve a teljes indukció indirekt változata, amelyben nem azt bizonyítjuk be, hogy ha egy természetes számokra vonatkozó állítás igaz az összes n nél kisebb számra, akkor igaz n -re is, hanem azt, hogy ha az állítás nem teljesül egy n természetes számra, akkor van az n -nél kisebb pozitív egész is amire nem teljesül. Egy másik lehetséges megfogalmazás a következő: Ha P (n) egy természetes számoktól függő állítás és létezik olyan n0 ∈ , amelyre P (n 0 )

nem igaz, akkor a H = {n ∈

P (n) nem igaz} halmazban van legkisebb elem. Így ha bármely

n ∈ esetén létezik m ∈ H , m < n , akkor H csak üres halmaz lehet és ezért P (n) igaz minden n ∈ esetén. Ezt a bizonyítási módot néha minimumelvként is emlegetik (ugyanis azt bizonyítjuk, hogy nincs H -nak minimuma). Ezt az elvet használtuk a maradékos osztás

tételének bizonyítására vagy rejtett formában a

2 irracionalitásának bizonyítására.

2.3.2. Példák 1. Oldjuk meg az x 2 + y 2 = 3(u 2 + v 2 ) a természetes számok halmazában. Megoldás. Bizonyítani fogjuk, hogy az egyenlet megoldása x = y = u = v = 0 . Tegyük fel,

hogy van olyan megoldás, amelyre x ≠ 0 . Így létezik a megoldások közt olyan (x, y, u, v ) , amelyre x nem nulla és a lehető legkisebb. Jelöljük ezt a megoldást (x 0 , y 0 , u 0 , v 0 ) -val. Egy szám 3k , 3k + 1 vagy 3k + 2 alakú, tehát a négyzetének 3-mal való osztási maradéka csak 0 vagy 1 lehet. Így az x 2 + y 2 összeg csakis akkor osztható 3-mal, ha x is és y is x 0 = 3x1 ,

osztható 3-mal. Eszerint gondolatmenetet az u + v

y 0 = 3y1

(

)

és 3 x12 + y12 = u 02 + v 02 . Ha az előbbi

összegre alkalmazzuk, következik, hogy u 0 = 3u1 és v 0 = 3v1 , x tehát x1 = 0 < x 0 , tehát ellentmondáshoz jutunk x 0 x12 + y12 = 3 u12 + v12 . De 3 megválasztásával. Így minden (x, y, u, v ) megoldásban x = 0 . Hasonlóképpen látható be, hogy y is nulla, tehát az egyetlen megoldás x = y = u = v = 0 . 2 0

(

2 0

)

2. Milyen a , b természetes számokra osztható a 2 + b 2 − a − b + 1 az ab szorzattal? Megoldás. Bebizonyítjuk, hogy csak az a = b = 1 természetes számokra igaz.. Tegyük fel, hogy ab | a 2 + b 2 − a − b + 1 , a ≤ b , b > 1 és a + b a lehető legkisebb.

(

)

Nyilván a ≠ 1 , mert a = 1 esetén b (1 + b 2 − 1 − b + 1) azaz b ( b 2 − b + 1) , innen b 1 következik, de föltettük, hogy b > 1 .

Fejezet tartalma


Tartalomjegyzék

99

Legyen valamilyen pozitív egész k -ra a 2 + b 2 − a − b + 1 = kab . (1) 2 2 Tekintsük az (1) rendezésével kapott x − (ka + 1) x + (a − a + 1) = 0 egyenletet, ennek (1) szerint b gyöke. Legyen az egyenlet másik gyöke c . Felhasználva mindkét összefüggést és a gyökök és együtthatók közötti összefüggést, azt kapjuk, hogy a 2 − a +1 c = (ka + 1) − b = . b a2 − a +1 1 A c egész, mert c = ka + 1 − b . Másrészt 0 < c < a , mivel c = ≥ és b b a2 − a +1 a2 a2 c= < ≤ = a . Tehát 0 < c < a és c 2 − (ka + 1) + (a 2 − a + 1) = 0 , azaz b b a c 2 + a 2 − c − a + 1 = kca ,

(

)

vagyis ca | c 2 + a 2 − c − a + 1 . Viszont c + b < a + b , ami ellentmond a és b kiválasztásának. Nem léteznek tehát olyan a és b egynél nagyobb egészek, amelyekre teljesül a feladat feltétele. IV.2.3.1. Gyakorlatok és feladatok 1. Van-e nullától különböző természetes megoldása az u 2 = 7v 2 egyenletnek? 2. Bizonyítsd be, hogy ha x 2 + y 2 + 1 = xyz , akkor z = 3 . 3. Határozd meg az összes olyan n természetes számot, amelyre minden n oldalú sokszög felbontható egymás belső pontjait nem metsző átlók segítségével háromszögekre úgy, hogy minden csúcsból páros számú átló induljon ki. 4. Az n ∈ természetes számból kiindulva a következő lépéseket végezzük: a) ha a szám páros, osztjuk 2-vel, b) ha a szám páratlan, hozzáadunk 1-et. Bizonyítsd be, hogy mindig eljutunk 1-hez. :2 :2 +1 :2 +1 :2 +1 :2 :2 18 → 9 → 10 → 5 → 6 → 3 → 4 → 2 → 1 Pl.: n = 36 : 36 → 5. Négy tetszőleges a , b , c , d természetes számból kiindulva a következő lépéseket ismételjük: a meglevő (a, b, c, d ) számnégyest helyettesítjük a ( a − b , b − c , c − d , d − a ) számnégyessel. Bizonyítsuk be, hogy egy idő után csupa 0-t kapunk. IV.2.4. Skatulyaelv 2.4.1. Értelmezés. A skatulyaelv alatt a következő állítást, illetve ennek az általánosításait értjük: Ha n + 1 tárgyat n dobozba helyezünk, lesz olyan doboz, amelybe legalább két tárgy kerül. Általánosabb megfogalmazások: 1. Ha kn + 1 tárgyat n dobozba helyezünk, lesz olyan doboz, amelybe legalább k + 1 tárgy kerül. 2. Ha egy I szakaszt lefedünk kisebb szakaszokkal, amelyeknek I-n kívül nincs pontjuk és hosszaik összege nagyobb mint I hosszának k -szorosa, akkor létezik olyan pont, amit legalább k + 1 kis szakasszal fedtünk le. 3. Ha egy L síkidomot lefedünk több más síkidommal úgy, hogy L-en kívüli részt nem fedünk le és a lefedő idomok összterülete nagyobb mint az L területe, akkor van legalább egy olyan pontja L-nek, amelyet legalább két idommal fedtünk le.

Fejezet tartalma

100

Tartalomjegyzék


IV.2.4.1. Megoldott feladatok 1. Bizonyítsuk be, hogy öt természetes szám közt van kettő, amelynek különbsége osztható néggyel. Megoldás. Készítsünk 4 dobozt, az egyikre írjunk IV.7. ábra 0-t, a másodikra 1-et, a harmadikra 2 3 1 0 2-t, a negyedikre 3-at. (IV.7. ábra) A k ( k ∈ {0, 1, 2, 3 } ) feliratú dobozba helyezzük azt/azokat a számokat, amelynek 4-gyel való osztási maradéka k . Így az öt számot négy dobozba kell helyeznünk, tehát van kettő, amely ugyanabba a dobozba kerül. Ezek különbsége osztható 4-gyel. 2. Bizonyítsuk be, hogy három természetes szám közül kiválasztható 2, amelyek összege vagy különbsége osztható 3-mal. Megoldás. Az a + b vagy a − b pontosan akkor osztható 3-mal, ha a 2 − b 2 osztható 3-mal. Így elégséges kimutatni, hogy kiválasztható kettő, amelyek négyzeteinek különbsége osztható 3-mal. Egy teljes négyzet 3-mal való osztási maradéka csak 0 vagy 1 lehet, tehát a három szám közül kiválasztható kettő, amelyek négyzetének 3-mal való osztási maradéka megegyezik. Ezek különbsége vagy összege osztható 3-mal. IV.8. ábra 3. Egy egységoldalú négyzet belsejében felveszünk öt pontot. Bizonyítsuk 2 -nél. be, hogy van köztük kettő, amelyek távolsága nem nagyobb 2 1 oldalú négyzetre (lásd a Bizonyítás. Osszuk fel a négyzetet, négy darab 2 IV.8. ábrát). Az öt pont közt biztosan létezik kettő, amely ugyanabban a kis 2 négyzetben van. Ezek távolsága nem nagyobb, mint a négyzet átlója, azaz . 2 4. Bizonyítsuk be, hogy 2n + 1 darab 2 n -nél kisebb természetes szám közül kiválasztható három, amely lehet valamilyen háromszög oldalhossza. Bizonyítás. Tekintsük az [1, 2) , [2, 4) , [4, 8) , … , [2 n −1 , 2 n ) intervallumokat. Mivel n intervallumunk és 2n + 1 számunk van, ezek közül kiválasztható 3, amely ugyanabban az intervallumban található. Ha ezek a , b és c , akkor a 2 k −1 ≤ a < 2 k , 2 k −1 ≤ b < 2 k és 2 k −1 ≤ c < 2 k egyenlőtlenségek alapján a + b ≥ 2 k > c , a + c > b és b + c > a , tehát a , b és c lehet egy háromszög oldalhosszainak mérőszáma. 5. Felvettünk a síkban n pontot és ezek közül néhányat összekötöttünk. Bizonyítsátok be, hogy létezik két olyan pont, amelyekből ugyanannyi szakasz indul ki. Megoldás. Egy pontból 0, 1, 2, … , n − 1 szakasz indulhat ki. Ha van olyan pont, amiből nem indul ki szakasz, akkor nincs olyan, amelyből n − 1 indul ki és fordítva, tehát minden pontra a belőle kiinduló szakaszok száma csak n − 1 különböző érték közül kerülhet ki. Mivel n pont van, létezik kettő, amelyekből ugyanannyi szakasz indul ki. 6. Egy egységnyi oldalú négyzet belsejében felvettünk néhány kört, amelyek kerületének összege 10. Bizonyítsuk be, hogy létezik olyan egyenes, amely párhuzamos a négyzet egyik oldalával és legalább négy kört metsz. Bizonyítás. Vetítsük a köröket a négyzet egyik oldalára. A vetületszakaszok hosszainak 10 összege > 3 , tehát van olyan pont a négyzet oldalán, amelyet legalább négy vetület fed. Ha

π

ebből a pontból egy d párhuzamost húzunk a másik oldallal, akkor d legalább négy kört metsz.

Fejezet tartalma


Tartalomjegyzék

101

IV.2.4.2. Gyakorlatok és feladatok 1. Egy tasakban 60 darab cukorka van, 20 áfonyás, 10 almás, 15 narancsos és 15 sárgadinnyés. Egy bekötött szemű gyereknek legalább hány cukorkát kell kiemelnie ahhoz, hogy biztosan legyen közöttük: a) egy áfonyás; b) két áfonyás és két almás; c) két narancsos, egy sárgadinnyés és egy almás; d) mindegyikből egy-egy; e) valamelyikből három egyforma. 2. Egy zsákban 10 pár azonos férfi- és 5 pár női kesztyű van. Legalább hány kesztyűt kell kivennünk ahhoz, hogy: a) legyen egy pár a kivett kesztyűk között; b) legyen egy pár női kesztyű a kivettek között; c) legyen két azonos pár. 3. Igaz-e, hogy egy 25-ös létszámú osztályban van legalább három diák, aki ugyanabban a hónapban született? 4. Egy építkezéshez 50 kőtömböt kell elszállítani, amelyek tömege 370 kg, 372 kg, 374 kg, … , 466 kg. El lehet-e ezeket szállítani egy maximum 3 tonnát szállító teherautóval 7 út alkalmával? 5. Bizonyítsd be, hogy n darab 2n -nél kisebb és n -től különböző természetes szám közül kiválasztható kettő, amelyek összege 2n. 6. Bizonyítsd be, hogy öt, 10-nél nagyobb prímszám közül kiválasztható kettő, melyek különbsége osztható 10-zel! 7. Bizonyítsd be, hogy 7 egész szám közül kiválasztható kettő, amelyek összege vagy különbsége osztható 11-gyel. 8. Bizonyítsd be, hogy 27 darab 100-nál nem nagyobb és 0-tól különböző természetes szám között van kettő, amelyek relatív prímek. 9. Bizonyítsd be, hogy bármely n páratlan számhoz létezik olyan k természetes szám, amelyre 2 k − 1 n . 10. Bizonyítsd be, hogy 6 irracionális szám között mindig van három, amelyek közül bármely kettő összege irracionális. 11. Egy egységoldalú négyzet belsejében felvettünk 51 pontot, Bizonyítsd be, hogy kiválasztható közülük 3, amelyek által meghatározott háromszög köré írható kör sugara kisebb 1 mint . 7 12. Bizonyítsd be, hogy minden 21 oldalú sokszögben van két átló, amelyek által bezárt szög mértéke kisebb mint 1 . 13. Egy 3× 4 -es téglalapban felvettünk 6 pontot. Bizonyítsd be, hogy van köztük kettő,

(

)

amelyek távolsága legfeljebb 5 . 14. A sík minden pontját kékre és pirosra színezzük. Bizonyítsd be, hogy van két azonos színű pont, amelyek távolsága 1. 15. Egy egységoldalú négyzet belsejébe egy konvex sokszöget írtunk, amelynek területe 1 nagyobb mint . Bizonyítsd be, hogy van olyan d egyenes, amely párhuzamos a négyzet 2 1 valamelyik oldalával és a sokszögből -nél hosszabb szakaszt metsz ki. 2

Fejezet tartalma

102

Tartalomjegyzék


IV.2.5. Invariánsok 2.5.1. Feladat. 22 papírlap közül néhányat 10 részre vágtak, majd az így kapott részek közül néhányat ismét 10 részre vágtak és így tovább. Lehetséges-e, hogy ezt néhányszor megismételve 2001 papírdarabot kapjunk? Hát 2002-t? Megoldás. Ha egy lépés előtt m papírdarab van és k darab papírt vágtunk szét, akkor m − k + 10k = m + 9k lesz a papírdarabok száma. Így a papírdarabok számának 9-cel való osztási maradéka nem változik. 22-nek a 9-cel való osztási maradéka 4 és 2001-nek 3, tehát 2001 papírdarabot nem kaphatunk. 2002-nek 9-cel való osztási maradéka 4, tehát az előbbi gondolatmenet alapján nem jutunk ellentmondáshoz. Ez nem jelenti azt, hogy 2002 darab papírt kaphatunk a megadott lépés ismétlésével. Igazoljuk, hogy van olyan lépéssorozat, amellyel elérhető 2002 papírdarab. Vágjunk minden lépésben 1 papírdarabot 10 részre. 220 lépés után pontosan 2002 papírdarabunk lesz. Az előbbi gondolatmenet egy tipikus bizonyítási modell. Ha egy rendszer valamilyen szabályok szerint változik és minden változás során egy E mennyiség megmarad, akkor a kezdeti és a végső állapotban is ugyanaz az E mennyiség. Így ha az A1 és A2 állapothoz rendelt E mennyiségek nem egyformák, akkor A1 -ből A2 nem érhető el. Lássunk néhány további megoldott feladatot: 2.5.2. Feladat. Egy táblára az 1, 2, 3, … , 2001 számokat írjuk. Egy-egy alkalommal letörölünk néhány számot és az összegük 7-tel való osztási maradékát írjuk helyettük. Ezt a lépést addig ismételjük, amíg egy szám marad a táblán. Melyik ez a szám? Megoldás. A táblán levő számok összegének 7-tel való osztási maradéka nem változik, tehát az utolsó szám az 1 + 2 + 3 + ... + 2001 = 2001000 szám 7-tel valóosztási maradéka. Az osztási maradék 1, tehát a táblán az 1 marad. 2.5.3. Feladat. A sík egész koordinátájú pontjaiban három bolha IV.9. ábra ugrál a következő szabályok szerint: ha P , Q és R a három bolha és Q1 Q ugrik, akkor a P vagy R szerinti szimmetrikus pozícióba ugrik (lásd a IV.9. ábrát) és hasonlóan a többiek is. Ha kezdetben a (0, 0) , P Q2 (1, 0) és (1, 1) pontokban voltak, juthatnak-e az (1, 0) , (0, 1) , és R Q (1, 1) pontokba? Megoldás. Jelöljük (x, y ) -nal az ugró bolha koordinátáit és (a, b ) vel az átugrott bolha koordinátáit. Az ugrás után az ugró bolha koordinátái (2a − x, 2b − y ) , tehát az egyes bolhák koordinátáinak paritása nem változik. Mivel kezdetben volt két páros koordinátájú ponton bolha, ezért mindig lesz a három bolha közül egy, amelynek mindkét koordinátája páros. Így a kívánt állás elérhetetlen.

IV.2.5.1. Gyakorlatok és feladatok 1. Egy táblára felírtuk a számokat 1-től 2001-ig majd egy-egy alkalommal a táblán levő számok közül néhányat helyettesítünk a számjegyeik összegével. Ezt a lépést addig ismételjük, amíg egy szám marad a táblán. Melyik az a szám? 2. Egy táblára az x 2 + 7 x + 8 kifejezést írtuk és egy-egy alkalommal valamelyik együtthatót eggyel növelhetjük vagy csökkenthetjük. Bizonyítsd be, hogy ha egy idő után az x 2 − 7 x − 8 kifejezés áll a táblán, akkor volt olyan másodfokú kifejezés a táblán, amelynek van egész gyöke. 3. Egy asztalon 6 pohár áll. Egy-egy alkalommal 5 poharat fordítunk meg. Elérhetjük-e, hogy minden pohár az eredeti helyzetéhez képest fordítva álljon? Hát akkor, ha 5 pohár van és minden lépésben 4-et fordítunk meg.

Tovább

IV. A MATEMATIKAI LOGIKA ELEMEI

Recommend Documents