Elementarna Matematika PDF

E LEMENTARNA M ATEMATIKA TANJA V OJKOVI Ć , D INO P ERAN N ERECENZIRANI NASTAVNI MATERIJALI 2 1 Grad̄a matematike.............................. 4 1.1 Oblici matematičkog mišljenja.................. 5 1.2 Vježbe - Uvod............................

E LEMENTARNA M ATEMATIKA TANJA V OJKOVI Ć , D INO P ERAN N ERECENZIRANI NASTAVNI MATERIJALI 2 1 Grad̄a matematike.............................. 4 1.1 Oblici matematičkog mišljenja.................. 5 1.2 Vježbe - Uvod............................ 10 2 Osnove matematičke logike........................ 12 2.1 Sudovi................................ 12 2.2 Prioritet logičkih veznika..................... 15 2.3 Interpretacije i istinitost sudova................. 16 2.4 Vježbe - Logika 1.......................... 19 2.5 Kvantifikatori............................ 21 2.6 Negacije............................... 23 2.7 Obrat po kontrapoziciji...................... 25 2.8 Korektno zaključivanje....................... 26 2.9 Vježbe - Logika 2.......................... 29 3 Teorija dokaza................................ 32 3.1 Univerzalni dokazi......................... 33 3.2 Egzistencijalni dokazi....................... 33 3.3 Višestruki kvantifikatori...................... 33 3.4 Protuprimjer............................. 36 3.5 Direktni dokaz............................ 36 3.6 Egzistencija i jedinstvenost.................... 38 3.7 Indirektni dokaz - dokaz kontradikcijom............ 39 3.8 Dokaz bikondicionala....................... 40 3.9 Dokaz disjunkcije.......................... 41 3.10 Složeniji dokazi........................... 41 3.11 Vježbe - Dokazi........................... 44 4 Osnove teorije skupova........................... 46 4.1 Pojam skupa............................. 46 4.2 Vježbe - Skupovi 1.......................... 48 4.3 Odnosi med̄u skupovima..................... 48 4.4 Vježbe - Skupovi 2.......................... 51 4.5 Operacije na skupovima...................... 52 4.6 Vježbe - Skupovi 3.......................... 56 4.7 Familije skupova.......................... 58 4.8 Kartezijev umnožak skupova................... 60 4.9 Vježbe - Skupovi 4.......................... 61 4.10 Razni zadaci za vježbu....................... 62 5 Relacije.................................... 66 5.1 Definicija relacije, domena i slika................ 67 5.2 Inverzna relacija.......................... 70 5.3 Vježbe - Relacije 1.......................... 71  3 5.4 Svojstva homogenih relacija................... 73 5.5 Vježbe - Relacije 2.......................... 77 5.6 Relacije ekvivalencije........................ 79 5.7 Vježbe - Relacije 3.......................... 84 5.8 Relacije ured̄aja........................... 85 5.9 Vježbe - Relacije 4.......................... 92 5.10 Razni zadaci za vježbu....................... 94 6 Funkcije.................................... 98 6.1 Definicija funkcije......................... 100 6.2 Jednakost funkcija......................... 103 6.3 Slika i praslika............................ 104 6.4 Vježbe - Funkcije 1.......................... 107 6.5 Restrikcije i proširenja....................... 109 6.6 Injektivnost, surjektivnost, bijektivnost, inverzna funkcija.. 109 6.7 Kompozicija funkcija........................ 114 6.8 Vježbe - Funkcije 2.......................... 116 6.9 Razni zadaci za vježbu....................... 121 7 Realne funkcije realne varijable...................... 125 7.1 Skup realnih brojeva........................ 126 7.2 Prirodno područje definicije i nultočke funkcije........ 127 7.3 Rastuće i padajuće funkcije.................... 127 7.4 Parnost i neparnost funkcija................... 128 7.5 Ograničenost funkcije....................... 130 7.6 Periodičnost funkcije........................ 131 7.7 Neke posebne funkcije....................... 132 7.8 Transformacija grafa funkcije................... 134 7.9 Vježbe - Realne funkcije 1...................... 136 7.10 Osnovne elementarne funkcije.................. 138 7.11 Vježbe - Realne funkcije 2...................... 159 7.12 Elementarne funkcije....................... 161 7.13 Vježbe - Realne funkcije 3...................... 178 7.14 Razni zadaci za vježbu....................... 181 8 Skup kompleksnih brojeva......................... 191 8.1 Polinomi nad poljem kompleksnih brojeva........... 197 8.2 Vježbe - Skup kompleksnih brojeva............... 198 9 Dodatak.................................... 201  1 4 POGLAVLJE Grad̄a matematike 1.1 Oblici matematičkog mišljenja..................... 5 1.2 Vježbe - Uvod............................... 10 Većina znanja koju čovjek akumulira kroz život pomalo se gradi u fazama. Tako bismo i matematičko znanje mogli grubo podijeliti u 3 faze. Prvu fazu karakterizira pitanje "Kako mogu riješiti ovaj zadatak (jednadžbu/integral...)?". Druga faza odred̄ena je pi- tanjem "Zašto moje rješenje funkcionira?", a treća "Što bismo dalje mogli istraživati?". U dosadašnjem matematičkom obrazovanju, najviše ste se bavili prvom fazom, npr. da odredite nultočke polinoma drugog stupnja rečeno vam je da morate riješiti kvadratnu jednadžbu. Fakultetska matematika se većinom bavi drugom fazom, pa ćete tako kroz ove i buduće kolegije naučiti koja je veza kvadratne jednadžbe i nultočaka polinoma drugog stupnja, postoje li slične formule za polinome trećeg i četvrtog stupnja i zašto ne postoje za polinome petog stupnja. Generalna ideja druge faze razvoja matematičara je osvijestiti da matematiku ne čine samo brojevi i računanje, nego radije ideje. Kad vas znatiželja za novom matematikom odvede u postavljanje novih pitanja i vlastito mate- matičko istraživanje, onda ste u fazi tri. Ovaj kolegij i ovi materijali su uvod u drugu fazu. Cilj je razviti vještine čitanja matematičkog teksta i osnove matematičkog izražavanja i pismenosti. Takod̄er ćete upoznati osnove nekoliko različitih područja matematike koja ćete produbiti u nastavku studiranja. Što je matematika? Kakva je priroda matematike? 1. GRAÐA MATEMATIKE 5 Čime se bavi? Kako se stvara i koristi? Koliko je važna? Najstarije poznate matematičke pločice potječu iz 2400. godine p.n.e. Matematika je ljudska djelatnost već tisućama godina i svatko je svjesno ili nesvjesno rabi. Uz golemu populaciju koja se pomalo služi matematikom, postoji i malen broj ljudi koji su profesi- onalni matematičari. Koliko je matematike danas poznato? Smatra se da bi današnje matematičko znanje stalo u otprilike 60 000 knjiga prosječne veličine. Tolika količina znanja daleko nadilazi mogućnost usvajanja bilo kojeg poje- dinca. Danas se smatra da bi dobro obrazovani matematičar mogao imati osnovna zna- nja o otprilike 10% raspoloživog matematičkog znanja. Matematički simboli: Deset znamenki dekadskog brojevnog sustava: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Aritmetičke operacije: +, −, ·, Znakovi grupiranja: (, ), [, ], {, } Znakovi za relacije med̄u brojevima: =, , ≤, ≥ Nepoznanice: x, y, z, a, b,... Simboli diferencijalnog i integralnog računa: ∞, lim, , , ∂,... R P Skupovi brojeva: N, Z, Q, I, R, C Porijeklo nekih simbola: n!- Christian Kramp (1760 - 1826) e ≈ 2.71828 - Leonhard Euler (1707 - 1783) π označava početno slovo grčke riječi perimetar što znači opseg R oznaka za integral predstavlja početno slovo latinske riječi summa 1.1 Oblici matematičkog mišljenja U matematici je od ključne važnosti precizno izražavanje i jasno definiranje pojmova o kojima se izriču tvrdnje. Oblicima matematičkog mišljenja moglo bi se nazvati poima- nje (što su to pojmovi i kako ih definiramo?), prosud̄ivanje (iznošenje sudova, jednos- tavnih i složenih) te zaključivanje (koji sudovi su istiniti i kako to dokazati?). 6 Slika 1: Grčki alfabet Pojmovi i definicije Postoje osnovni pojmovi i izvedeni pojmovi. Osnovni pojmovi se ne definiraju, nego smatramo da su nam intuitivno jasni To su primjerice skup, točka, pravac... Svi ostali pojmovi su izvedeni pojmovi, koji se točno i precizno definiraju. Njihova značenja se opisuju pomoću osnovnih ili ranije definiranih pojmova. Definicijom smatramo nabrajanje nužnih i dovoljnih obilježja pojma povezanih logič- kom rečenicom ili simboličkim zapisom. P RIMJER 1.1 Promotrimo sljedeće pokušaje definicije pojma kvadrat. 1. Kvadrat je pravokutnik koji ima sve četiri stranice jednake, sva četiri kuta jednaka i susjedne stranice su mu okomite. 2. Kvadrat je četverokut koji ima sve četiri stranice jednake. 3. Kvadrat je ono kad imamo četiri dužine koje imaju zajedničke vrhove, a sijeku se pod pravim kutem, pa su još i jednako duge. Prva definicija navodi previše uvjeta, što je nepotrebno, druga premalo, pa ne- dostaju potrebni uvjeti da bi pojam bio kvadrat, a treća nije pregledna, smislena ni sažeta, tj. nije logička rečenica. 4. Kvadrat je pravokutnik kojemu su susjedne stranice jednake duljine. 5. Kvadrat je romb kojemu je jedan kut pravi. 6. Kvardat je romb kojemu su dijagonale jednake duljine. Svaka od ovih definicija je dobra i često se neki pojam može definirati na više načina. Jedna se tvrdnja odabere kao definicija, a ostale tvrdnje se nazivaju karakterizacije pojma. One se izriču s logičkim veznikom ako i samo ako, kako bismo naglasili da je riječ o nužnim i dovoljnim uvjetima, npr. 1. GRAÐA MATEMATIKE 7 Pravokutnik je kvadrat ako i samo ako su mu dijagonale med̄usobno okomite. O karakterizacijama ćemo nešto više reći kasnije. Zadatak 1.2 Pokušajte smisliti što je više moguće loših "definicija" pojmova pravokutnik i kružnica. Za svaki pokušaj napišite zašto definicija nije dobra. Pravila definiranja: 1. Definicija treba biti primjerena pojmu kojeg definira: ne smije biti ni preuska ni preširoka. 2. Definicija treba biti pregledna i sažeta. 3. Definicija ne smije biti izražena slikovitim ni dvosmislenim jezikom. 4. Definicija ne smije biti cirkularna. 5. Definicija ne smije biti negativna ako može biti pozitivna. 6. Mora postojati barem jedan objekt kojeg definicija opisuje. P RIMJER 1.3 Odredite jesu li sljedeće definicije korektne: 1. Sljedbenik broja je veći od njega za 1. 2. Proširiti razlomak znači pomnožiti ga nekim brojem. 3. Neparni brojevi su prirodni brojevi koji nisu djeljivi s 2 i pri dijeljenju s 2 daju ostatak 1. 4. Kružnica je skup točaka u ravnini jednako udaljenih od jedne fiksne točke. 5. Prosti brojevi su prirodni brojevi veći od 1, koji su djeljivi samo s 1 i sa sa- mim sobom. Aksiomi Aksiomi su tvrdnje o osnovnim pojmovima koje se smatraju istinitima te se ne dokazuju. Kod aksiomatskog zadavanja neke teorije poželjno je da izabrani aksiomi zadovoljavaju sljedeća tri principa: Konzistentnost: iz sustava aksioma ne smije se moći istodobno dokazati neka tvrdnja i njezina negacija; 8 Potpunost: svaka tvrdnja, ili njezina negacija, je dokaziva u danom sustavu aksi- oma; Neovisnost: niti jedan od aksioma se ne može dobiti kao posljedica ostalih. Aksiomatska izgradnja matematičke teorije: 1. osnovni pojmovi 2. aksiomi 3. izvedeni pojmovi (definirani) 4. tvrdnje koje se dokazuju (teoremi, propozicije, leme, korolari) Prvi primjer aksiomatski zasnovane matematičke teorije je Euklidska geometrija (oko 300 g.pr.n.e.) - Euklidovo djelo Elementi. Treba napomenuti da nisu sve matematičke teorije aksiomatski zasnovane, dapače, ve- ćina nije, a i kod onih koje jesu javljaju se problemi s ispunjavanjem tri zahtjeva na skup aksioma. Štoviše, Kurt Gödel (1931.) je dokazao da svaki dovoljno složen matematički sustav ne može biti potpun. Više o tome na kolegiju Matematička logika. Teoremi Teoremi su tvrdnje čija se istinitost utvrd̄uje dokazom, tj. logičkim zaključivanjem iz ak- sioma i već dokazanih teorema te teorije. Vjerojatno ste se u dosadašnjem učenju mate- matike susreli i s drugim tipovima tvrdnji koje odgovaraju ovom opisu, propozicijama, lemama i korolarima. Logički gledano, to su sve istinite tvrdnje čija se istinitost utvrd̄uje dokazom, a često ćemo ovdje o općenitom razmatranju sve nazivati teoremima. Primi- jetimo da, kako je teorem tvrdnja koja je istinita, dok ne znamo je li neka tvrdnja istinita, za nju ćemo samo govoriti tvrdnja. U matematičkom udžbeniku ili tekstu nailazit ćemo na različite tipove teorema. Dogovorno se obično uzima: Propozicija – teorem za kojeg postoji kratki i jednostavni dokaz. Lema - teorem koji sam za sebe nije od posebnog značaja, nego služi kao korak u dokazu nekog važnijeg teorema Korolar - teorem koji je neposredna i jednostavna posljedica drugog, prethodno dokazanog teorema P RIMJER 1.4 Primjeri tvrdnji: 1. Ako je broj veći od 10 onda je veći i od 5. p 2. 2 je iracionalan broj. 1. GRAÐA MATEMATIKE 9 3. Neka je u nekom društvu 10 ljudi. Tada med̄u njima postoje barem dvoje koji su rod̄eni na isti dan u tjednu. 4. Prostih brojeva ima beskonačno mnogo. 5. Četverokut je deltoid ako su mu dijagonale okomite. Jesu li ove tvrdnje istinite? U teoremu mora biti jasno uz koje uvjete se razmatra odred̄eni objekt i što se o tom objektu tvrdi. Uvjete u teoremu nazivamo premise, hipoteze ili pretpostavke, a samu tvrdnju zaključkom, posljedicom ili konkluzijom. Teoremi se često izriču u obliku Ako P onda Q. Ako vrijedi P onda vrijedi Q. Neka vrijedi P. Tada vrijedi Q. U svim ovim oblicima, P je pretpostavka, a Q zaključak. Ako teorem nije zadan u nekom od ovih oblika, treba znati odrediti što je pretpostavka, a što zaključak. P RIMJER 1.5 U sljedećim primjerima odredite što su pretpostavke, a što zaključci tvrdnji: 1. Ako je prirodni broj paran onda je djeljiv sa 4. 2. Umnožak dvaju uzastopnih parnih brojeva a i b je djeljiv s 8. 3. Četverokut je paralelogram ako mu se dijagonale raspolavljaju. 4. U paralelogramu se dijagonale raspolavljaju. 5. Dijagonale romba su okomite. 6. Svaki obodni kut nad promjerom kružnice je pravi. 7. Za realne brojeve a, b, c vrijedi: Ako je a + b = 0 onda je c(a + b) = 0. Primijetimo da tvrdnje 3. i 4. nisu iste iako na neki način zvuče slično! U obliku "Ako P onda Q" te tvrdnje bi izgledale ovako: 3. Ako se dijagonale četverokuta raspolavljaju onda je on paralelogram. 4. Ako je četverokut paralelogram onda se njegove dijagonale raspolavljaju. Dakle, preptostavka jedne tvdnje je zaključak druge, i obratno. U tom slučaju kažemo da je jedna tvrdnja drugoj obrat. Što bi bio obrat tvrdnje 2.? Karakterizacije pojma Prisjetimo se da smo za definiciju rekli kako je ona nabrajanje nužnih i dovoljnih uvjeta o nekom pojmu. Što bi značilo nužni, a što dovoljni uvjeti? Nužni uvjeti su oni koje 10 mora ispunjavati svaki taj pojam, tj. ako je neki objekt neki pojam, onda on nužno za- dovoljava taj uvjet, tj neko svojstvo. Na primjer, svakom kvadratu su sve 4 stranice jednake, pa bismo mogli reći da je istinita tvrdnja: "Ako je četverokut kvadrat onda su mu sve četiri stranice jednake". Dovoljni uvjeti su oni uvjeti tj. svojstva koje ako neki objekt ispunjava, onda on spada u odred̄enu skupinu objekata. Na primjer gore izrečeno svojstvo "sve četiri stranice su jednake" nije dovoljan uvjet da bi četverokut bio kvadrat, jer tvrdnja: "Ako su četve- rokutu sve četiri stranice jednake onda je on kvadrat.", nije istinita, s obzirom da ovo svojstvo vrijedi i za romb. Za kvadrat bismo imali dva dovoljna uvjeta (kao što smo vidjeli i u definiciji), pa bismo mogli reći da je istinita tvdnja: "Ako su četverokutu sve četriri stranice jednake i susjedni kutovi pravi onda je on kvadrat". Da povežemo to s pretpostavkama, zaključcima i tvrdnjama, tvrdnja: "Ako je četverokut kvadrat onda su mu sve četiri stranice jednake.", je istinita, a njezin obrat: "Ako su če- tverokutu sve četiri stranice jednake onda je on kvadrat.", nije istinit. No ako kao pretpostavku navedemo uvjete koji su i nužni i dovoljni za neki pojam, onda će biti istinita tvrdnja: "Ako vrijede ti uvjeti onda je objekt neki odred̄eni." i "Ako je objekt neki odred̄eni onda vrijede ti uvjeti." U tom slučaju te dvije tvrdnje možemo obje- diniti u jednu te pretpostavku i zaključak povezati riječima ako i samo ako. Na primjer, kako smo vidjeli u prethodnom primjeru, tvdnje 3. i 4. su obje istinite, pa bismo mogli reći: "Četverokut je paralelogram ako i samo ako mu se dijagonale raspolavljaju." Takve tvrdnje, vezane veznikom "ako i samo ako" nazivamo karakterizacijama pojma. One imaju snagu definicija jer govore o nužnim i dovoljnim uvjetima nekog pojma. U tekstu se često umjesto "ako i samo ako" koristi skraćenica "akko". 1.2 Vježbe - Uvod 1. Koje od sljedećih rečenica su ispravne definicije: (a) Trapez je četverokut koji ima par nasuprotnih paralelnih stranica. (b) Trapez je četverokut kojemu se dijagonale raspolavljaju. (c) Prosti brojevi su prirodni brojevi koji su djeljivi samo s 1 i samim sobom. (d) Skup je kolekcija elemenata povezana nekim svojstvom. (e) Krug polumjera r je skup točaka čija je udaljenost od neke točke manja ili jednaka r. (f) Najveća zajednička mjera brojeva a i b je najveći broj djeljiv s a i b. (g) Za dva pravca kažemo da su okomiti ako je kut kojeg zatvaraju pravi kut. Objasnite za svaku rečenicu zašto je ispravna definicija ili zašto nije. 2. U tvrdnji: „Prirodan broj je djeljiv s 10 kada je djeljiv s 5.“, o danom objektu se tvrdi (tj. zaključak je): (a) da je djeljiv s 5; 1. GRAÐA MATEMATIKE 11 (b) da je djeljiv s 10; (c) da je prirodan broj. Što je objekt o kojem se nešto tvrdi? Kako bi glasio obrat ove tvrdnje? Je li ova tvrdnja istinita? Je li joj istinit obrat? 3. Za svaku od tvrdnji odredite: Objekt o kojem se nešto tvrdi: Pretpostavke: Zaključak: (a) Zbroj triju uzastopnih prirodnih brojeva je uvijek djeljiv s 3. (b) Prirodan broj djeljiv je sa 6 kada je djeljiv s 2 i 3. (c) Kada je barem jedan od faktora umnoška dvaju prirodnih brojeva djeljiv bro- jem c, onda je i umnožak tih brojeva djeljiv s c. (d) Dva prirodna broja a i b biti će djeljiva nekim prirodnim brojem c kada je njihov zbroj djeljiv brojem c. 4. Odredite obrat i ispitajte istinitost obrata i originalne tvrdnje: (a) Dva pravca u istoj ravnini se sijeku. (b) Ako dva skupa imaju točku u presjeku, onda su jednaki ili je jedan podskup od drugog. (c) Ako je zbroj tri cijela broja djeljiv s 15, onda je barem jedan od njih djeljiv s 5 ili barem jedan djeljiv s 3. (d) Umnožak tri prirodna broja a, b, c veća ili jednaka 2 je jednak 102 ako je a = 2, b = 3 i c = 17. (e) Ako je zbroj neparno mnogo prirodnih brojeva paran prirodni broj, onda je med̄u njima parno mnogo neparnih brojeva i barem jedan paran broj. p (f) Realan broj 2 je iracionalni broj. (g) Ako je zbroj tri racionalna broja cijeli broj, onda je barem jedan od njih cijeli broj ili barem jedan od njih zbrojen 10 puta sa samim sobom daje cijeli broj. (h) Ako je četvrokut pravokutnik, onda on ima par nasuprotnih paralelnih stra- nica iste duljine i par jednakih kutova.  2 12 POGLAVLJE Osnove matematičke logike 2.1 Sudovi................................... 12 2.2 Prioritet logičkih veznika........................ 15 2.3 Interpretacije i istinitost sudova.................... 16 2.4 Vježbe - Logika 1............................. 19 2.5 Kvantifikatori............................... 21 2.6 Negacije.................................. 23 2.7 Obrat po kontrapoziciji......................... 25 2.8 Korektno zaključivanje.......................... 26 2.9 Vježbe - Logika 2............................. 29 Matematička logika je fundamentalna matematička disciplina koje ćemo se mi ovdje samo malo dotaknuti, koliko je nužno za daljnje gradivo. Upoznati ćemo neke osnove logike sudova i logike I. reda. 2.1 Sudovi Sud je svaka suvisla izjavna rečenica za koju se može utvrditi je li istinita ili lažna. P RIMJER 2.1 Što od sljedećeg su sudovi: 1. Dva plus dva je jednako četiri. 2. OSNOVE MATEMATIČKE LOGIKE 13 2. Dva plus dva je jednako pet. 3. Koliko je sati? 4. x plus 2 je jednako 8. 5. x = 7 je rješenje jednadžbe x 2 = 49. 6. Broj 0.00001 je mali broj. 7. Ova rečenica je lažna. Prvi je istiniti sud, a drugi lažni sud. Treća rečenica nije sud jer nije izjavna, četvrta nije sud jer bez da znamo što je x, ne možemo reći je li istinita ili lažna. Peto je sud i to istinit (primijetite da to što x = 7 nije jedino rješenje ove jednadžbe, ne znači da je ovaj sud neistinit). Šesto nije sud, jer se ne može utvrditi istinitost pojma "mali broj" te sedmo nije sud, jer utvrd̄ivanje istinitosti dovodi do paradoksa. Primijetimo da će po ovome što smo dosad naučili teoremi biti istiniti sudovi za koje smo dokazali da su istiniti. Lažni sud ne može biti teorem. Postoje tvrdnje za koje na- izgled možemo utvrditi jesu li istinite ili lažne, ali za njih još nije pronad̄en matematički dokaz, a nije pronad̄en dokaz ni da ne vrijede (dokaz njihovih negacija). Takve tvrdnje ne možemo nazvati teoremima, nego ih nazivamo slutnje ili hipoteze. Jedna od najpoz- natjih je Goldbachova hipoteza: Svaki parni broj veći od 2 može se napisati kao zbroj dva prosta broja. Sudove dijelimo na jednostavne i složene. Jednostavni sudovi su oni koji ne sadrže više drugih sudova. Neki primjeri jednostavnih sudova: 4 je paran broj. 4 je neparan broj. 2 < 5. p 2 je iracionalan broj. Zbroj kutova u trokutu je 180 stupnjeva. Neke kvadratne jednadžbe imaju realna rješenja. Vidimo da je sud nekad zgodno napisati matematičkim simbolima, pa ćemo uvesti oz- nake i za same sudove, kako bismo mogli jednostavnije zapisivati složene sudove. Naj- češće ćemo sudove označavati velikom slovima P,Q, R, S,.... Takve oznake sudova nazi- vamo propozicijske varijable (propozicijska logika - logika sudova), no ovdje nećemo ulaziti u pravu strukturu alfabeta logike sudova. Od jednostavnih sudova gradimo slo- žene pomoću pet različitih matematičkih veznika. 1. Negacija suda je sud koji negira istinitost početnog suda. Na primjer negacija suda 2 + 3 = 5 je sud 2 + 3 ̸= 5, a negacija suda "Broj 4 je manji od broja 3." je sud "Broj 14 4 je veći ili jednak broju 3." Za sud P , oznaka negacije je −P ili ¬P. Čitamo "ne-P" ili "non-P". 2. Konjukcija je sud složen od dva suda P i Q te veznika "i". Na primjer, konjukcija sudova "4 je paran broj." i "Prostih brojeva ima beskonačno mnogo." je sud "4 je paran broj i prostih brojeva ima beskonačno mnogo." Za sudove P i Q, oznaka konjukcije je P ∧Q, što čitamo "P i Q". 3. Disjunkcija je sud složen od dva suda P i Q te veznika "ili". Na primjer, disjunkcija sudova "4 je paran broj." i "Prostih brojeva ima beskonačno mnogo." je sud "4 je paran broj ili prostih brojeva ima beskonačno mnogo." Za sudove P i Q, oznaka disjunkcije je P ∨Q, što čitamo "P ili Q". 4. Kondicional je sud koji je tvrdnja da neki zaključak vrijedi uz neku pretpostavku. Složen je od dva suda P i Q uz logički veznik "ako...onda". Na primjer, za navedene sudove "Pravokutnici imaju 4 stranice." i "Kvadrati imaju 4 stranice." kondicional u kojem je "Pravokutnici imaju 4 stranice.", pretpostavka, a "Kvadrati imaju 4 stra- nice.", zaključak, bi glasio "Ako pravokutnici imaju 4 stranice onda kvadrati imaju 4 stranice." Primijetimo da je većina tvrdnji koje smo spominjali u prethodnom poglavlju bila u formi kondicionala. Ovaj isti kondicional možemo pisati i na načine: "Kvadrati imaju 4 stranice ako pravokutnici imaju 4 stranice." "Pravokutnici imaju 4 stranice implicira da kvadrati imaju 4 stranice." Mogli bismo takod̄er kazati: "To da pravokutnici imaju 4 stranice je dovoljan uvjet da bi kvadrati imali 4 stranice." Ako se prisjetimo što smo rekli o nužnim i dovoljnim uvjetima, mogli bismo istu tvrdnju takod̄er formulirati na sljedeći način "Ako kvadrati imaju 4 stranice onda nužno pravokutnici imaju 4 stranice." Drugim riječima, pretpostavka je dovoljan uvjet za zaključak, a zaključak je nužan uvjet za pretpostavku. Ako pretpostavku označimo s P , a zaključak s Q, onda kon- dicional zapisujemo kao P → Q i čitamo na neki od gore predloženih načina. Još jednom napomenimo da P → Q i Q → P nisu isti sudovi. 5. Bikondicional je konjukcija dva kondicionala i spominjali smo ga već kod karak- terizacija pojma. Na primjer za sudove "5 je neparan broj." i "20 je djeljivo sa 4.", bikondicional bi glasio: "5 je neparan broj ako i samo ako je 20 je djeljivo sa 4." 2. OSNOVE MATEMATIČKE LOGIKE 15 Označavamo P ↔ Q. To je ekvivalentno s P → Q ∧Q → P. Možemo kazati i 5 je neparan broj je nužan i dovoljan uvjet da bi 20 bilo djeljivo s 4. P RIMJER 2.2 Formirajte složene sudove ¬R, ¬P ∨ ¬Q, Q → R, R ↔ P , P ∧ Q, ¬P ∧ Q, ¬(P ∧ Q), R ↔ (P ∧Q) i (R ↔ P ) ∧Q ako je P ="Funkcija sinus nije bijekcija." Q ="Funkcija drugog korijena je bijekcija." R ="Funkcija apsolutne vrijednosti nije injekcija." 2.2 Prioritet logičkih veznika Sud zapisan simbolima veznika i propozicijskim varijablama obično nazivamo formu- lom. Ako se u složenom sudu javlja više veznika važno je znati koji je njihov prioritet kako bismo znali ispravno pročitati formulu. Med̄utim, kakav je točno prioritet veznika razlikuje se od literature do literature. Negdje ćete npr. pronaći da konjukcija i disjunk- cija imaju isti prioritet, pa ih se čita s lijeva na desno, a negdje da konjukcija ima veći prioritet. Zato kad vježbate po drugim knjigama, uvijek pogledajte kako je definiran prioritet logičkih veznika u toj literaturi. Kako bismo izbjegli konfuziju, mi ćemo uvi- jek pisati zagrade oko logičkih veznika koji imaju veći prioritet u toj formuli, i poštovat ćemo pravilo da se čitaju od unutrašnjih zagrada prema vanjskima. Iznimka je negacija, koja uvijek ima najveći prioritet, npr. u formuli ¬P ∧ Q, negacija "djeluje" samo na P , a nakon toga se provodi konjukcija. Tako da oko negacije nećemo pisati zagrade. Primijetimo da je po ovom pravilu koje smo dogovorili nekorektno napisati P → Q ∨ R, jer ne znamo koji logički veznik ima veći prioritet, a (P → Q) ∨ R i P → (Q ∨ R) nisu iste formule. Tehnički je nekorektno čak i kad je isti veznik u pitanju, npr. u formuli P ∧ Q ∧ R, no kako za konjukciju i disjunkciju vrijedi asocijativnost (to ćete dokazati na kolegiju Matematička logika!) u takvim formulama ipak možemo izostaviti zagrade te čitati po redu. P RIMJER 2.3 Uz oznake iz prošlog primjera pročitajte formule P ∧ (Q ∨ R) (P ∧Q) ∨ R P ↔ (Q → R) (P ↔ Q) → R 16 2.3 Interpretacije i istinitost sudova Sudovi imaju istinosnu vrijednost, ali formule same po sebi nemaju. Npr. jasno je da je sud 2 + 2 = 4 istinit, dok o formuli P ∧ Q ne možemo ništa reći u ovom obliku. Kad propozicijske varijable P i Q identificiramo s konkretnim sudovima onda bi trebalo biti moguće odrediti istinitost složenog suda, ovisno o istinitosti propozicijskih varijabli i logičkih veznika u formuli. U procesu odred̄ivanja istinitosti jednostavnih i složenih su- dova koristimo se tzv. interpretacijom. Laički rečeno, interpretacija se može shvatiti kao funkcija, čiji je ulaz neki sud, a izlaz je vrijednost ISTINA ili LAŽ, što najčešće ozna- čavamo s 1 ili 0, redom.  1, P je istinit I (P ) = 0, P je lažan Interpretacije formula najčešće zapisujemo semantičkim tablicama u kojima razma- tramo sve moguće kombinacije istinosnih vrijednosti propozicijskih varijabli. P ¬P 0 1 1 0 Za formulu P ∧Q postoje 4 moguće interperetacije. P Q P ∧Q 0 0 ? 0 1 ? 1 0 ? 1 1 ? Konjukcija P ∧ Q je istinita kad su istinite obje propozicijske varijable P i Q, a inače je neistinita, pa je semantička tablica konjukcije: P Q P ∧Q 0 0 0 0 1 0 1 0 0 1 1 1 Disjunkcija P ∧ Q je istinita kad je istinita barem jedna propozicijska varijabla, tj. kada je istinit P ili Q ili oboje, a neistinita samo kada su i P i Q neistinite, pa je semantička tablica disjunkcije: P Q P ∨Q 0 0 0 0 1 1 1 0 1 1 1 1 2. OSNOVE MATEMATIČKE LOGIKE 17 Logička disjunkcija se ponekad naziva inkluzivna disjunkcija, ili "inkluzivno ili". Eks- kluzivna disjunkcija, koja je istinita točno onda kada je istinita točno jedna od propozi- cijskih varijabli, ali ne obje, nema svoj posebni logički veznik, ali je ekvivalentna formuli (P ∨ Q) ∧ ¬(P ∧ Q). (Primijetimo da izraz "ekvivalentna" nismo još formalno objasnili! Za sada smatrajmo da znači "jednako vrijedna".) Postoji mnogo načina na koje se kondicional koristi i mnogo načina kako shvatiti kada je istinit. Ponekad se koristi za izreći jednostavnu posljedicu, npr. "Ako dobijem barem 50 bodova na ispitu, proći ću ispit." Nije uvijek lako shvatiti kako istinitost sudova P i Q utječe na istinitost suda P → Q. Promotrimo sljedeći sud: "Ako je n = 2 onda je n paran broj." To je svakako istinita tvrdnja, pa bismo mogli napisati tablicu: n n=2 n je paran broj Ako je n = 2 onda je n paran broj. 2 ISTINA ISTINA ISTINA Ovo bi odgovaralo interpretaciji formule P → Q za koju su i P i Q istiniti i lako se vidi da je onda istinit i sud P → Q. No, je li to jedina interpretacija za koju je kondicional istinit? Promotrimo tablicu: n n=2 n je paran broj Ako je n = 2 onda je n paran broj. 2 ISTINA ISTINA ISTINA 3 LAŽ LAŽ ISTINA 4 LAŽ ISTINA ISTINA Već smo utvrdili da je "Ako je n = 2 onda je n paran broj." svakako istinita tvrdnja, pa zamišljanje da je n neki drugi broj ne bi to trebalo promijeniti i zadnji stupac je uvijek istina. No, kako vidimo, to nas sad dovodi da P → Q može biti istina čak i ako je P neistina. Dakle, ako je P neistinit, sud P → Q je istinit. Ostaje još razmotriti posljednju kombinaciju, što ako je P istina, Q laž? To je jedina interpretacija za koju je kondicional lažan, što nas dovodi do semantičke tablice za kondicional: P Q P →Q 0 0 1 0 1 1 1 0 0 1 1 1 Vratimo se na primjer "Ako dobijem barem 50 bodova na ispitu, proći ću ispit.", da još jednom intuitivno potvrdimo vrijednosti u ovoj tablici. Kako bi bilo očito da je P → Q istinit kad je P neistinit zamislimo situaciju "Dobila sam manje od 50 bodova na ispitu." Ako u tom slučaju ne biste prošli ispit svejedno ne biste mislili da je došlo do prevare, jer bi činjenica da "Ako dobijem barem 50 bodova na ispitu, proći ću ispit." i dalje vrijedila. 18 Isto tako, ako niste dobili barem 50 bodova na ispitu, a profesor vam svejedno odluči ispit smatrat prolaznim, opet ne biste mislili da je došlo do prevare. Jedina "problema- tična" situacija je ona u kojoj ste dobili barem 50 bodova na ispitu, a profesor kaže da ga svejedno niste prošli. To je upravo interpretacija I (P ) = 1, I (Q) = 0 i zato je u tom slučaju I (P → Q) = 0. Istinitost bikondicionala je nešto jednostavnija, u formuli P ↔ Q doživljavamo da su P i Q na neki način ekvivalentni, pa je bikondicional istinit točno onda kad su P i Q iste istinosne vrijednosti, tj: P Q P ↔Q 0 0 1 0 1 0 1 0 0 1 1 1 P RIMJER 2.4 Napišite semantičku tablicu za formulu (¬P ∧Q) ↔ (¬Q → P ). P RIMJER 2.5 Pomoću semantičke tablice ispitajte istinitost suda: Ako je prva derivacija funkcije sinus funkcija kosinus i druga derivacija funkcije sinus je funkcija sinus, onda je treća derivacija funkcije sinus funkcija kosinus. Označimo sudove propozicijskim varijablama: P ="Prva derivacija funkcije si- nus je funkcija kosinus."; Q ="Druga derivacija funkcije sinus je funkcija sinus.", R ="Treća derivacija funkcije sinus je funkcija kosinus.". Dani složeni sud sada možemo napisati kao formulu (P ∧ Q) → R. Kako bismo ispitali istinitost ovog suda, ne treba nam cijela semantička tablica, samo odgovarajući redak. Dakle tre- baju nam istinosne vrijednost jednostavnih sudova P , Q i R. Lako se prisjetimo da je I (P ) = 1, I (Q) = 0 i I (R) = 0 i sada imamo: P Q R P ∧Q (P ∧Q) → R 1 0 0 0 1 P RIMJER 2.6 Pomoću semantičke tablice ispitajte istinitost svih interpretacija formula P ∧ ¬P i P ∨ ¬P. Što primijećujete? Formula P ∧¬P je neistinita za sve interpretacije, a formula P ∨¬P je istinita za sve interpretacije. Za takve formule imamo posebne nazive, o čemu govori sljedeća definicija. 2. OSNOVE MATEMATIČKE LOGIKE 19 Definicija 2.7 Za formulu kažemo da je ispunjiva ako postoji interpretacija za koju je ta formula istinita. Za formulu kažemo da je oboriva ako postoji interpretacija za koju ta formula nije istinita. Za formulu kažemo da je valjana ili tautologija ako je istinita za svaku svoju in- terpretaciju. Za formulu ažemo da je antitautologija ako je neistinita za svaku svoju interpre- taciju. P RIMJER 2.8 1. Može li formula biti i ispunjiva i oboriva? 2. Je li tautulogija oboriva? 3. Je li tautologija ispunjiva? 4. Je li antitautologija ispunjiva/oboriva? Odgovori na pitanja su 1. Da, 2. Ne, 3. Da, 4. Antitautologija je oboriva, ali ne ispunjiva. 2.4 Vježbe - Logika 1 1. Za svaku od sljedećih rečenica odredite je li ili nije sud i obrazložite. (a) Podijelite kut na tri jednaka dijela. (b) Neke eksponencijalne funkcije su rastuće. (c) Sve eksponencijalne funkcije su rastuće. (d) 3 + 8 = 18. (e) 3 + x = 18. (f) Broj x = 1 je rješenje jednadžbe x 2 − 1 = 0. (g) Logika je lijepa! (h) Funkcija je derivabilna. (i) Ovaj sud je istinit. (j) Ovaj sud je lažan. 2. Koji od sljedećih sudova su istiniti: (a) Ako je 2 paran broj onda je 7 paran broj. (b) Ako je 12 paran broj onda je 4 paran broj. (c) Ako je 8 neparan broj onda je 10 paran broj. (d) Ako je 4 neparan broj onda je 5 paran broj. 20 3. Ispitajte istinitost sljedećih sudova: (a) Svaki prirodni broj je neparan ili kvadratna jednadžba uvijek ima realno rje- šenje. (b) Da bi derivacija funkcije sinus bila funkcija kosinus nužno je da je derivacija konstantne funkcije 0. (c) Ne vrijedi da je 2 + 4 ̸= 6. (d) Funkcija sinus je periodična ako i samo ako svaka eksponencijalna funkcija ima sve nenegativne funkcijske vrijednosti. (e) Ako svaka parabola siječe os x onda elipsa ima samo jedno tjeme. (f) Svaki realni broj je negativan ili pozitivan, ali ne oboje. (g) Da bi derivacija funkcije kosinus bila funkcija sinus dovoljan je uvjet to da je derivacija funkcije sinus funkcija kosinus. p p (a) 2 nije prirodan broj ili 3 nije racionalan broj. (b) Ako je 24 < 20 i 5 prost broj, onda je 4 · 5 < 20. 4 (c) 4 i 6 su relativno prosti ako i samo ako je 6 = 1. 4. Svaku rečenicu nadopunite nekim logičkim veznikom da se dobije istinit sud. Je li to moguće za svaku rečenicu? Postoji li više od jednog veznika koji daju istiniti sud za neke rečenice? Diskutirajte. (a) Trokuti imaju 3 stranice 3 + 5 = 6. (b) 3 + 5 = 6 trokuti imaju 3 stranice. (c) 10 je najveći cijeli broj 0 je najmanji cijeli broj. (d) Derivacija konstentne funkcije je 0 tangente na rastuće funkcije imaju pozitivni koeficijent smjera. 5. Neka je P := "Suma svih kutova u trokutu je 180 stupnjeva.", Q := "3 + 7 = 10" i R :="Funkcija sinus je neprekidna." Napišite riječima sudove: (a) P ∨Q (b) P ∧ ¬Q (c) Q ↔ ¬R (d) P ∨ (R → ¬Q) (e) ¬(P ∧Q) (f) (P ∨Q) ∧ R 6. Ispitajte jesu li sljedeći složeni sudovi tautologija ili antitautologija: (a) (A ∧ B ) ∧ −(A ∨ B ) (b) −(−A −→ B ) ←→ (−A ∧ −B ) 2. OSNOVE MATEMATIČKE LOGIKE 21 (c) (A −→ B ) −→ (−A ∧ B ) 7. Prevedite sljedeće rečenice u formule po ključu: A za Mirko je hrabar. B za Slavko je hrabar. C za Mirko je snažan. D za Slavko je snažan. (a) Mirko je hrabar i snažan ili je to Slavko. (b) I Mirko i Slavko su snažni, ni nijedan od njih nije hrabar. (c) Slavko je hrabar ako je snažan,a Mirko snažan ako je hrabar. (d) Ako barem jedan od njih dvojice nije hrabar, barem je jedan od njih snažan. (e) Ako Mirko nije hrabar i ako nije snažan, onda nije slučaj da je Slavko hrabar ili snažan. (f) I Mirko i Slavko su i hrabni i snažni ako nije slučaj da netko od njih nije barem jedno od toga. 2.5 Kvantifikatori Vidjeli smo na početku poglavlja o logici da rečenica "n je paran broj." nije sud jer nema istinosnu vrijednost. Jedan način kako možemo ovu rečenicu promijeniti u sud je da odaberemo neku konkretnu vrijednost za n, npr. rečenice "Ako je n = 5, n je paran broj." ili "Ako je n = 6, n je paran broj." su sudovi. Još jedan način je da upotrijebimo kvan- tifikatore. Oni su logički veznici logike I. reda koji nam govore koju količinu objekata razmatramo. Na primjer: "Za sve n ∈ N, n je paran broj." ili "Postoji n ∈ N koji je paran broj." Kad kažemo "za sve" onda želimo reći da tvrdnja u nastavku vrijedi za sve elemente ne- kog promatranog skupa, a "postoji" znači da postoji barem jedan element promatranog skupa za kojeg vrijedi tvrdnja. Obje rečenice su sada sudovi, prvi je neistinit, a drugi je istinit. Ova dva kvantifikatora imaju i svoje nazive i simbole. Univerzalni kvantifikator, u oznaci ∀, čita se "za svaki", "za sve", "svi", itd. ovisno o strukturi rečenice. Egzistencijalni kvantifikator, u oznaci ∃, čita se "postoji", "postoji neki", itd. Gornji sudovi zapisani simbolima bili bi: ∀n ∈ N, n je paran. ∃n ∈ N, n je paran. 22 P RIMJER 2.9 Pročitajmo sljedeće tvrdnje: (∀x ∈ R)(∃y ∈ R)x 2 = y. (∃x ∈ R)(∀y ∈ R)x 2 = y. Prvi sud čitamo: "Za svaki realni broj x, postoji realni broj y, takav da je x 2 = y.", a drugi: "Postoji realni broj x, takav da za svaki realni broj y vrijedi x 2 = y." Govore li ovi sudovi isto? Jesu li istiniti? Prvi sud govori o postojanju kvadrata svakog realnog broja i istinit je, dok drugi sud tvrdi da postoji neki realni broj koji kvadriran daje svaki realni broj i naravno, neistinit je. Prethodni primjer pokazuje važnost redoslijeda kvantifikatora. U odnosu na logičke veznike logike sudova, kvantifikatori imaju najveći prioritet. P RIMJER 2.10 Zapišite sljedeće rečenice pomoću kvantifikatora: 1. Svaki prirodan broj manji je od svog kvadrata. 2. Za svaki realan broj postoji realan broj dvostruko veće apsolutne vrijed- nosti. 3. Produkt dva neparna prirodna broja je uvijek neparan. 4. Za svaki realan broj postoji prirodan broj veći od njega. 5. Za svaka dva realna broja je apsolutna vrijednost njihovog zbroja manja ili jednaka od zbroja njihovih apsolutnih vrijednosti. 6. Apsolutna vrijednost razlike dva prirodna broja je uvijek veća ili jednaka 1. 7. Ako je x pozitivan realni broj onda postoji realni broj y koji u zbroju s x daje −6. Rješenja: 1. (∀n ∈ N)(n < n 2 ) 2. (∀x ∈ R)(∃y ∈ R)(|y| = 2|x|) 3. (∀n, m ∈ N), n, m neparni povlači da je n · m neparan (činjenica da je broj neparan može se zapisati i simbolima) 4. (∀x ∈ R)(∃n ∈ N)(n > x) 5. (∀x, y ∈ R)(|x + y ≤= |x| + |y|) 2. OSNOVE MATEMATIČKE LOGIKE 23 6. (∀n, m ∈ N)(|n − m| ≥ 1) 7. (∀x ∈ R+ )(∃y ∈ R)(x + y = −6) 2.6 Negacije Vidjeli smo prije da je ¬P oznaka za ne-P , tj. negaciju od P. Postavlja se pitanje kako negiramo složene sudove? Ono što stalno treba imati na umu, i nekad će olakšati intu- itivno razmatranje negacija, je da ako je tvrdnja P istinita, onda je njezina negacija ¬P nužno neistinita i obratno, ako je P neistinita tvrdnja, onda je ¬P istinit. P RIMJER 2.11 Pokušajte intuitivno negirati sljedeće sudove: 1. P ="Jabuka je voće i lavovi su mačke." 2. Q="Pluton je planet ili satelit." 3. R="Svi Grci su plavokosi." 4. S="Postoji čovjek visok bar 3m." U prvom primjeru, logički veznik "i" u P se pretvara u logički veznik "ili" u ¬P , pa imamo: ¬P = "Jabuka nije voće ili lavovi nisu mačke." Takod̄er je: ¬Q ="Pluton nije planet i nije satelit." Kod posljednja dva primjera imamo kvantifikatore i intuitivno je jasno da su ne- gacije: ¬R ="Nisu svi Grci plavokosi." ¬R ="Postoji Grk koji nije plavokos." ¬S ="Ne postoji čovjek visok barem 3m." ¬S ="Svi ljudi su niži od 3m." Obratimo posebnu pažnju da negacija suda R:="Svi Grci su plavokosi." nije "Ni- jedan Grk nije plavokos." Negacija tvrdnje R treba biti tvrdnja koja obuhvaća sve slučajeve u kojima R nije istina. Na primjer situacija u kojoj je točno pola Grka plavokoso je svakako situacija u kojoj R nije istinit i stoga mora biti obuhvaćena u negaciji od R. Dolazimo do sljedećih zaključaka: ¬(P ∧Q) je ekvivalentno s ¬P ∨ ¬Q 24 ¬(P ∨Q) je ekvivalentno s ¬P ∧ ¬Q ¬(∀x)P (x) je ekvivalentno s (∃x)¬A(x) ¬(∃x)P (x) je ekvivalentno s (∀x)¬A(x) Nekoliko puta smo već spomenuli da formule mogu biti logički ekvivalentne. Bez da dublje ulazimo u područje Matematičke logike, za sada nam je dovoljno to shvatiti tako da su dvije formule logički ekvivalentne ako imaju iste istinosne vrijednosti za sve inter- pretacije, tj. zadnji stupci semantičke tablice su im isti. Zadatak 2.12 Za vježbu napišite semantičke tablice formula ¬(P ∧Q), ¬P ∨¬Q, ¬(P ∨Q) i ¬P ∧ ¬Q i usporedite zadnje stupce onih za koje smo rekli da su ekvivalentne. Za dvije formule, F 1 i F 2 , koje su ekvivalentne, pišemo F 1 ⇐⇒ F 2. Oznaku ⇐⇒ mo- žemo čitati kao "ekvivalentno je", ali takod̄er i kao "ako i samo ako". Iako smo tako čitali logički veznik ↔, često se te dvije oznake koriste jedna umjesto druge. To je malo ne- precizno, ali je intuitivno jasno o čemu je riječ. Promotrimo sada negaciju kondicionala i bikondicionala. Prisjetimo se semantičke tablice kondicionala. P Q P →Q 0 0 1 0 1 1 1 0 0 1 1 1 Jedina interpretacija za koju je kondicional P → Q neistinit je ona u kojoj je P istinit i Q neistinit, tj. u kojoj je P istinit i ¬Q istinit. Pa vrijedi: ¬(P → Q) je ekvivalentno s P ∧ ¬Q. Ilustrirajmo to primjerom. P RIMJER 2.13 Neka je F ≡ (P → Q)="Ako pada kiša onda je travnjak mokar." U kojoj situaciji F neće biti istina? Po onome što znamo o kondicionalu, to je si- tuacija kad je pala kiša, a travnjak nije mokar, dakle tvrdnja P ∧ ¬Q. Ovdje je važno analizirati zašto neke intuitivno očite opcije nisu negacije ove tvrd- nje, npr. "Ako ne pada kiša onda travnjak nije mokar", tj. ¬P → ¬Q. No logički te dvije tvdnje ne ovise jedna o drugoj. To što ako pada kiša znači da će travnjak biti mokar, ništa nam ne govori o situaciji kad kiša ne pada. Možda kiša ne pada, ali netko zalijeva, pa je travnjak svejedno mokar. Još jedna opcija je "Ako je travnjak mokar onda pada kiša.", tj. Q → P. No već smo na početku rekli da ovaj tip tvrdnje nazivamo obratom početne tvrdnje i mogu biti istinita i tvrdnja i njezin obrat ili 2. OSNOVE MATEMATIČKE LOGIKE 25 samo jedno od toga ili nijedno. Za provjeru napišite semantičke tablice tvrdnji P → Q, ¬(P → Q), P ∧ ¬Q, Q → P i ¬P → ¬Q. Koje su logički ekvivalentne? Analogno kako smo došli do negacije kondicionala, dolazimo do negacije bikondici- onala. Pogledajmo u kojim interpretacijama je bikondicional P ↔ Q neistinit. P Q P ↔Q 0 0 1 0 1 0 1 0 0 1 1 1 To su dvije interpretacije, one u kojima su P i Q različite istinitosti. Kako je dovoljno da se jedna od tih interpretacija ostvari da bi bikondicional bio neistinit, intuitivno vidimo da ćemo te dvije mogućnosti povezati veznikom "ili", pa vrijedi: ¬(P ↔ Q) je ekvivalentno s (P ∧ ¬Q) ∨ (¬P ∧Q). P RIMJER 2.14 Napišite semantičke tablice za formule ¬(P ↔ Q) i (P ∧ ¬Q) ∨ (¬P ∧ Q) i uvjerite se da su one ekvivalentne. 2.7 Obrat po kontrapoziciji Sad kad znamo malo o negacijama, analizirajmo sljedeće dvije izjave, za koje uzmimo da pišu iznad ulaza nekog restorana: Dobra hrana nije jeftina. Jeftina hrana nije dobra. Govore li ove dvije izjave isto ili različito? Na prvi pogled govore različito, prva govori nešto o dobroj hrani, a druga o jeftinoj hrani. Označimo propozicijskim varijablama jednostavne sudove u ovim izjavama i napišimo formule koje ih predstavljaju. Kako bismo jednostavnije čitali ove sudove, označimo neku hranu o kojoj govorimo s H. A="H je dobra." B ="H je jeftina." Promišljenim čitanjem, vidimo da su nam dosta ove dvije propozicijske varijable, kako bismo izjave napisali kao formule: A → ¬B B → ¬A Možemo primijetiti da su ove dvije formule u obliku: "Ako P onda Q." i "Ako ne Q onda ne P.". 26 Definicija 2.15 Obrat po kontrapoziciji suda P → Q je sud ¬Q → ¬P. Prikažimo semantičkim tablicama formule P → Q i ¬Q → ¬P. P Q P →Q ¬Q ¬P ¬Q → ¬P 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 Dakle, P → Q je ekvivalentno s ¬Q → ¬P , tj. Kondicional je ekvivalentan sa svojim obratom po kontrapoziciji. Vratimo li se na gornji primjer o hrani, lako zaključujemo da su dane izjave logički ekvi- valentne, tj. govore isto. P RIMJER 2.16 Do sada smo vidjeli da je za sud P → Q: Q → P obrat suda; P ∧ ¬Q negacija suda; ¬Q → ¬P obrat po kontrapoziciji suda. Još spomenimo da se za ovaj sud definira i tzv. suprotni sud: ¬P → ¬Q. Napišite semantičke tablice za sve ove sudove i usporedite njihove istinosne vrijednosti. Koje zaključke možete izvesti? 2.8 Korektno zaključivanje Korektno zaključivanje je proces u kojem od danih pretpostavki dolazimo do korektnog zaključka koji se iz tih pretpostavki može zaključiti. Nekad imamo skup pretpostavki iz kojih ne možemo zaključiti ništa "korisno" za daljnje razmatranje nekog problema i važno je znati prepoznati kad se korektni zaključak može, a kad ne može izvesti. Prep- tostavke i zaključke često pišemo tako da navodimo pretpostavke i onda nakon hori- zontalne crte navedemo zaključak, npr. Sokrat je s Marsa. Marsovci žive na Mjesecu. Sokrat živi na Mjesecu. Bismo li po intuiciji rekli da je ovaj zaključaj izveden korektno? Jesu li pretpostavke isti- niti sudovi? O čemu ovisi je li zaključivanje korektno? Promotrimo sljedeće zaključiva- nje: 2. OSNOVE MATEMATIČKE LOGIKE 27 Sokrat je s Marsa. Marsovci žive na Mjesecu. Jabuka je voće. Je li ovo zaključivanje korektno? Iako je zaključak istinit sud, ne vidimo kako taj sud slijedi iz danih pretpostavki, tako da provedeno zaključivanje nije korektno, dok u gornjem primjeru, iako su obje pretpos- tavke i zaključak neistiniti sudovi, provedeno zaključivanje je logički korektno. Ako pada kiša onda nosim kišobran. Pada kiša Nosim kišobran. Ako bismo sudove zapisali kao formule, ova shema zaključivanja izgledala bi ovako: P →Q P Q Ovo je korektno zaključivanje i ovaj princip zaključivanja naziva se modus ponens. Uz prvu premisu P → Q možemo zamisliti još 3 različite mogućnosti za drugu premisu. U kojem od slučajeva se može izvesti korektni zaključak i koji? Ako pada kiša onda nosim kišobran. Ne pada kiša ? Ako pada kiša onda nosim kišobran. Nosim kišobran. ? Ako pada kiša onda nosim kišobran. Ne nosim kišobran. ? Samo u posljednjoj shemi zaključivanja možemo izvesti zaključak i to "Ne pada kiša.", jer ta shema odgovara obratu po kotrapoziciji originalnog suda. Ova zaključivanja možemo promatrati i preko formula, tj. princip modus ponens mo- žemo zapisati kao jednu formulu: 28 ((P → Q) ∧ P ) → Q. Ta formula je tautologija, tj. istinita je za sve interpretacije, neovisno o istinitosti P i Q. (Provjerite!) Zadatak 2.17 Napišite princip zaključivanja P →Q ¬Q ¬P kao jednu formulu i napišite njezinu semantičku tablicu. Što uočavate? Kao jednu formulu zapisali bismo ((P → Q) ∧ ¬Q) → ¬P. Ako napravimo seman- tičku tablicu vidjet ćemo da je i ovo tautologija. P RIMJER 2.18 Odredite koji od sljedećih zaključaka su korektni i objasnite: Ako je danas nedjelja, onda idem u kino. Danas nije nedjelja. Ne idem u kino. Jesen je ako pada lišće. Jesen je. Pada lišće. Dijagonale romba su okomite. Četverokut je romb. Dijagonale su mu okomite. Ako je danas petak i pada kiša, onda ostajem kući. Danas je petak. Ostajem kući. Ako je jabuka voće i mrkva povrće, onda je kokoš perad. Kokoš nije perad. Jabuka nije voće. 2. OSNOVE MATEMATIČKE LOGIKE 29 Ako idem u školu, onda danas nije subota i nije nedjelja. Danas nije subota i nije nedjelja. Idem u školu. Uputa: Za svaki primjer napravite shemu zaključivanja. Korektno je zaključeno samo o dijagonalama romba, ostali su primjeri pogrešnog zaključivanja. 2.9 Vježbe - Logika 2 1. Prevedite sljedeće rečenice u formule, po ključu: M x za "x je miran/mirna" Lx za "x je lakovjeran/lakovjerna" Z x za "x je zadovoljan/zadovoljna" C x y za "x cijeni y" P x y za "x prezire y" (a) Svi su zadovoljni. (b) Netko je miran. (c) Svi su lakovjerni ili su svi mirni. (d) Svatko miran je i zadovoljan. (e) Nisu svi zadovoljni mirni. (f) Postoji barem jedan miran i lakovjeran. (g) Svi koji su zadovoljni i lakovjerni jesu mirni. (h) Svatko cijeni svakoga. (i) Netko cijeni svakoga. (j) Svatko cijeni nekoga. (k) Nekoga svatko cijeni. (l) Nitko nikoga ne cijeni. (m) Netko nikoga ne cijeni. (n) Tkogod cijeni samog sebe, ne prezire nikoga. (o) Tko cijeni onoga tko ne cijeni njega, lakovjeran je. (p) Nitko ne cijeni one koji ga preziru. (q) Netko prezire one koji ga cijene. (r) Netko prezire samo one koji ga cijene. 2. Zapišite sljedeće tvrdnje kvantifikatorima: (a) Za svaki realni broj ϵ ∈ R+ postoji prirodni broj n 0 takav da za svaki prirodni p broj n vrijedi ako je n ≥ n 0 onda je 1 − ϵ < n n < 1 + ϵ. 30 (b) Za svaki realni broj x i svaki realni broj y postoji prirodni broj n i postoji prirodni broj m takvi da ako je x < y onda je x < 2nm < y. 3. Odredite negacije tvrdnji: (a) (∀x ∈ R)(∀y ∈ R)x = y (b) (∃x ∈ R)x = 2 (c) (∀x ∈ R)(∀y ∈ R)x 2 + y 2 ≥ 0 (d) (∀x ∈ R)(∀y ∈ R)(x ̸= y → 2x ̸= 2y) (e) (∀x ∈ R)(∃y ∈ R)(x > y ∧ y > 0) (f) (∀n ∈ N)2|n ↔ 4|n 2 (g) Negirajte sudove iz Zadatka 2. 4. Neka je S = {1, 2,..., 100}. Napišite negacije sljedećih tvrdnji (u afirmativnom obliku): (a) Barem 3 elemenata iz S su manja od 20. (b) Postoje 2 elementa iz S čija je suma djeljiva s 5. (c) Barem pola elemenata iz S su parni brojevi. (d) Najviše 10 elemenata iz S je djeljivo sa 7. (e) U S postoje 2 različita elementa. (f) U skupu S postoji podskup s 10 elemenata djeljivih s 10. (g) U skupu S postoji podskup s 10 elemenata djeljivih s 10. (h) Svaki nadskup skupa S sadrži element 78. (i) Postoje barem 3 nadskupa skupa S koja sadrže samo parne brojeve. (j) Točno 3 elementa iz S su manja od 20. (k) U S postoji točno jedan element jednak 52. (l) U S postoji barem jedan element jednak 52. 5. Za sljedeće tvrdnje odredite nagaciju, obrat i obrat po kontrapoziciji: (a) Ako je x = 2, onda je x 2 = 4. ¡ ¢ (b) x > 0 ∧ y > 0 −→ x y > 0 (c) x je racionalan broj ako su (x − 1)2 i (x + 1)2 racionalni brojevi. (d) (∀x, y ∈ R)(x < y → x 2 < y 2 ) (e) (∀x, y ∈ R)(x y < 0 → (x < 0 ∨ y < 0)) (f) (∀x ∈ R)(∃n ∈ N)(|n − x| ≤ 1) (g) Za realne brojeve a, b, c vrijedi: Ako je a + b = 0 onda je c(a + b) = 0. (h) Ako je zbroj dva kuta u trokutu jednak 90 stupnjeva, onda je taj trokut pravo- kutan. 2. OSNOVE MATEMATIČKE LOGIKE 31 (i) Dvije funkcije su jednake ako imaju iste domene, kodomene i pravilo pridru- živanja. (j) Svaki prirodni broj koji je djeljiv s 3 i s 4, djeljiv je i sa 6. (k) A i B su disjunktni skupovi ili je A podskup od B , ako je A jednočlan skup ili B prazan skup. 6. Jesi li sljedeći zaključci korektni: (a) Lik je pravokutnik ako ima 4 prava kuta. Ako neki lik ima 4 prava kuta onda on ima 4 stranice. Lik B nema 4 stranice. Zaključak: Lik B nije pravokutnik. (b) Ako Maja pozove Anu na rod̄endan, Ana će Maji kupiti poklon. Ako Ana Maji kupi poklon onda će joj kupiti ruksak. Ako Ana Maji ne kupi ruksak, Maja neće moći ići u školu. Zaključak: Ako Maja ne pozove Anu na rod̄endan, onda neće moći ići u školu. (c) Ako su krave i ovce na istoj livadi onda će krave pojesti više trave od ovaca. Ako krave ne pojedu više trave od ovaca, onda će davati manje mlijeka. Za- ključak: Ako krave ne budu davale manje mlijeka onda krave i ovce nisu na istoj livadi. (d) Ako mama skuha nešto za ručak, onda Marko to mora jesti. Ako Marko po- jede kupus, bit će nezadovoljan cijelo popodne, ali ako Marko ne pojede ku- pus za ručak, onda neće dobiti čokoladu. Mama nije skuhala kupus za ručak. Zaključak: Marko će biti zadovoljan i dobit će čokoladu.  3 32 POGLAVLJE Teorija dokaza 3.1 Univerzalni dokazi............................ 33 3.2 Egzistencijalni dokazi.......................... 33 3.3 Višestruki kvantifikatori......................... 33 3.4 Protuprimjer................................ 36 3.5 Direktni dokaz............................... 36 3.6 Egzistencija i jedinstvenost....................... 38 3.7 Indirektni dokaz - dokaz kontradikcijom............... 39 3.8 Dokaz bikondicionala.......................... 40 3.9 Dokaz disjunkcije............................. 41 3.10 Složeniji dokazi.............................. 41 3.11 Vježbe - Dokazi.............................. 44 Matematički dokaz je niz logički istinitih argumenata koji korektnim zaključivanjem sli- jede jedan iz drugog ili iz prethodno dokazanih tvrdnji. Njime se utvrd̄uje istinitost dane tvrdnje uz dane pretpostavke. Iako je logika ključna u dokazima, oni se rijetko pišu logičkim simbolima, češće su pi- sani običnim rečenicama jezika i često se izostavljaju detalji i koraci, kako bi dokaz bio pregledan i čitljiv. Svrha pisanog dokaza je čitatelja uvjerljivo provesti od pretpostavki do zaključka. Ovom poglavlju je cilj upoznati se s osnovnim principima i metodama dokazivanja. 3. TEORIJA DOKAZA 33 3.1 Univerzalni dokazi Dokazi tvrdnji s univerzalnim kvantifikatorima. Da bismo dokazali tvrdnju (∀x)p(x) moramo pokazati da svaki objekt x iz skupa u kojem promatramo tvrdnju zadovoljava p(x). To radimo tako da uzmemo proizvoljni element a iz skupa i pokažemo da vrijedi p(a). Dokazi obično počinju s: Neka je a proizvoljni broj, element... P RIMJER 3.1 Dokažite tvrdnju: Za sve parne brojeve n je n 2 paran broj. Rješenje. Neka je n proizvoljni parni prirodni broj. To znači da postoji k ∈ N takav da možemo pisati n = 2k. Sada je n 2 = (2k)2 = 4k 2 = 2 · (2k 2 ), pa zaključujemo da je i n 2 paran. 3.2 Egzistencijalni dokazi Dokazi tvrdnji s egzistencijalnim kvantifikatorima. Da bismo dokazali tvrdnju (∃x)p(x), moramo pokazati da u skupu u kojem promatramo tvrdnju postoji element koji zadovoljava p(x). To radimo tako da pronad̄emo pogodnog kandidata b iz skupa i pokažemo da vrijedi p(b). P RIMJER 3.2 Dokažite da postoji cijeli broj koji zadovoljava jednadžbu x 2 + 2x − 3 = 0. Rješenje. Računski lako dolazimo do "kandidata" tj. rješenja ove jednadžbe, x 1 = 1 i x 2 = −3. Vidimo da su oba cijela, pa je bilo koji od njih dobar za dokaz naše tvrdnje. Dokaz: Za x = 1 vrijedi dana jednadžba, pa je tvrdnja dokazana. P RIMJER 3.3 Dokažite da postoji funkcija čija je derivacija f (x) = 2x. Rješenje. Ponovno lako računski dolazimo do kandidata, g (x) = x 2. 3.3 Višestruki kvantifikatori U prošlom poglavlju smo imali mnogo primjera sudova s višestrukim kvantifikatorima i vidjeli smo da redoslijed kvantifikatora mijenja smisao i istinitost tvrdnji, a takod̄er će utjecati i na način dokazivanja. 34 P RIMJER 3.4 Dokažite da za svaki realni broj x postoji realni broj y takav da vrijedi x + y = 2. (∀x ∈ R)(∃y ∈ R)x + y = 2. Primjenjujući što smo rekli o dokazima kvantifikatora, trebali bismo prepostaviti da je a proizvoljni realni broj i onda pronaći realni broj b takav da vrijedi a +b = 2. Očito je za proizvoljni realni broj a, taj kandidat b = 2−a i on zaista postoji i realan je za svaki realni a. Formalno, dokaz bi glasio: Neka je x proizvoljni realni broj. Neka je y = 2 − x. y je takod̄er realan broj i vrijedi x + y = x + 2 − x = 2, pa je tvrdnja dokazana. P RIMJER 3.5 Dokažite da postoji cijeli broj x takav da za svaki cijeli broj y vrijedi x + y = y. (∃x ∈ Z)(∀y ∈ Z)x + y = y. Sada moramo pronaći kandidata b ∈ Z takvog da će za sve cijele brojeve a vrijediti b + a = a. Očito je traženi kandidat broj 0. Formalno, dokaz bi glasio: Neka je x = 0. Neka je y proizvoljan cijeli broj. Vrijedi x + y = 0 + y = y, pa tvrdnja vrijedi. P RIMJER 3.6 Dokažite da postoje realni brojevi a i b takvi da za svaki realni broj x vrijedi (a + 2b)x + (2a − b) = 2x − 6. Analiza: Moramo pronaći dva kandidata, a i b koji zadovoljavaju gornju tvrdnju za svaki realni broj x. Rješavanjem sustava a + 2b = 2 2a − b = −6 dolazimo do kandidata a = −2 i b = 2. Dokaz: Neka je x proizvoljni realni broj te a = −2 i b = 2. Vrijedi: (a + 2b)x + (2a − b) = (−2 + 4)x + (4 − 2) = 2x − 6. P RIMJER 3.7 Dokažite da izmed̄u svaka dva racionalna broja a, b ∈ Q, a < b postoji barem je- dan racionalan broj, tj. (∀a, b ∈ Q)(∃x ∈ Q)a < b → a < x < b. Analiza. Ako nam "na prvu" nije jasno da tvrdnja zaista vrijedi, testiramo na ne- 3. TEORIJA DOKAZA 35 koliko primjera. Promotrimo npr. brojeve 1 i 7 te 0 i 1. Vidimo da prvi primjer obuhvaća nekoliko cijelih brojeva izmed̄u danih granica, pa je lako uočiti traže- nog kandidata. U drugom primjeru nema cijelih brojeva izmed̄u danih granica, ali znamo da da postoji više racionalnih, npr. 12. Kako je 1 2 točno polovina izmed̄u 0 i 1, dolazimo do ideje o pogodnom kandidatu za proizvoljne a i b. Dokaz. Neka su a, b proizvoljni racionalni brojevi takvi da je a < b. Izmed̄u njih će a+b a+b se uvijek nalaziti racionalni broj 2 , tj. vrijedi a < 2 < b. Moramo pokazati da je ovaj broj racioanal i da se zaista nalazi izmed̄u danih brojeva. To da je raciona- lan slijedi iz svojstava skupa racionalnih brojeva (svojstva polja), a nejednakosti a+b a+b dokažimo računski. Znamo da a < 2 < b je ekvivalentno s a < 2 ∧ a+b 2 < b. a+b Dokažimo prvo a < 2. Zbog a < b vrijedi: a + b a + a 2a > = = a. 2 2 a Druga nejednakost se dokazuje analogno (dokažite za vježbu!). Napomena 3.8 U nekim područjima ćete često primijetiti da egzistencijalni dokazi ili dokazi tvrd- nji s višestrukim kvantifikatorima koji sadrže i egzistencijalni, pri uzimanju po- godnog kandidata, samo napišu nekog kandidata, a nije baš najjasnije kako se do njega došlo. Na primjer: Dokažite da je funkcija f (x) = x 2 neprekidna u točki x = 2. Da bi se ovo dokazalo potrebno je da znamo definiciju neprekidnosti funkcije u točki: Neka je D ⊆ R otvoren skup i f : D → R funkcija. Kažemo da je funkcija f nepre- kidna u točki c ∈ D ako vrijedi (∀ϵ > 0)(∃δ > 0)(∀x ∈ D)|x − c| < δ → | f (x) − f (c)| < ϵ. Za ovu gore tvrdnju bi dakle trebalo pokazati da za svaki ϵ > 0 postoji δ > 0 takav da za sve x iz domene ako je |x − 2| < δ onda je |x 2 − 4| < ϵ. U nekim starijim skriptama dokaz glasi ovako: Neka je ϵ > 0 proizvoljan i neka je p p δ = 4 + ϵ − 2. Neka je x ∈ D takav da je |x − 2| < 4 + ϵ − 2. Pokažimo |x 2 − 4| < ϵ. Vrijedi: |x 2 − 4| = |x − 2| · |x + 2| = |x − 2| · |x − 2 + 4| ≤ |x − 2| · (|x − 2| + 4) < p p < δ · (δ + 4) = ( 4 + ϵ − 2) · ( 4 + ϵ + 2) = 4 + ϵ − 4 = ϵ. Ovo je svakako dobar dokaz, i ovako odabrani δ je bio dobat kandidat, no dokaz ne opisuje postupak kako se do tog kandidata došlo. Kad budete sami dokazi- vali tvrdnje, onda kod onih složenijih uvijek napravite nekakvu početnu analizu ili račun, kako biste pripremili teren za dokaz (a i profesori će vas na satu pri dokazi- vanju navoditi kako da to vježbate). Npr. ovdje bi to mogli na sljedeći način: Neka 36 je ϵ > 0 proizvoljan. Treba nam δ takav da za x ∈ D takav da je |x − 2| < δ, slijedi |x 2 − 4| < ϵ. Kako je |x 2 − 4| = |x − 2| · |x + 2| = |x − 2| · |x − 2 + 4| ≤ |x − 2| · (|x − 2| + 4), vidimo da za traženi δ za koji je |x −2| < δ mora vrijediti δ·(δ+4) < ϵ. Rješavanjem p ove kvadratne nejednadžbe dolazimo do kandidata δ = 4 + ϵ − 2. Sada bi dalje slijedio onaj dio gore, u kojemu dokazujemo da vrijedi tvrdnja iz definicije. To nije baš "najčišće", jer nije minimalno koliko je potrebno (samo dati kandidata i po- kazati da za njega tvrdnja vrijedi), ali je čitatelju pregledniji proces dokazivanja. Dakle, imajte na umu da je dokaz jedno, a proces razmišljanja drugo i često se u dokazu ne vidi dobro kako je zapravo do njega došlo. 3.4 Protuprimjer Često moramo dokazati da tvrdnja tipa (∀x)p(x) ne vrijedi. To možemo napraviti tako da dokažemo da tvrdnja (∃x)¬p(x) vrijedi, a to dokazujemo kao egzistencijalni dokaz tako da pronad̄emo objekt a za koji ne vrijedi p(a). Taj objekt nazivamo protuprimje- rom. P RIMJER 3.9 Pokažite da ne vrijedi tvrdnja: (∀x ∈ R)x + 2 = 7. Analiza: Želimo pronaći realan broj x takav da ne vrijedi x + 2 = 7. Lako nalazimo kandidata, npr. broj 6. Dokaz: Tvrdnja ne vrijedi, protuprimjer je x = 6, jer 6 + 2 ̸= 7. P RIMJER 3.10 Dokažite da ne vrijedi tvrdnja: Svaka kvadratna jednadžba ax 2 + bx + c = 0, pri čemu su a, b, c ∈ R, ima realni korijen. Analiza: Sada trebamo pronaći realne brojeve a, b, c takve da jednadžba ax 2 +bx+ c = 0 nema realno rješenje. Prisjetimo se da rješenja jednadžbe drugog stupnja mogu biti i kompleksna i jedan od primjera takve jednadžbe je x 2 + 1 = 0. Stoga uzimamo a = 1, b = 0, c = 1. Dokaz. Tvrdnja ne vrijedi. Uzmimo a = 1, b = 0, c = 1. Sada jednadžbe ax 2 + bx + c = 0 poprima oblik x 2 +1 = 0, a njezina rješenja su kompleksni brojevi i , −i , dakle nema realnog korijena. 3.5 Direktni dokaz Direktni dokaz je uobičajeni način za dokazivanje kondicionala. Koraci su: 1. Identificirati pretpostavke i zaključke. 2. Pretpostaviti da vrijede pretpostavke. 3. TEORIJA DOKAZA 37 3. Analizirati pretpostavke (koja svojstva vrijede i što sve znamo ako znamo pretpos- tavke). 4. Analizirati zaključke (što su im definicije ili karakterizacije, tj. što sve možemo i moramo pokazati da bi izveli zaključak). 5. Provesti niz zaključivanja. Što je tvrdnja složenija, to će biti teže provesti ove korake. Za jednostavne primjere iz ove cjeline, neki od koraka se mogu i preskočiti jer su očigledni. Ipak, pisat ćemo ih, kako bismo usvojili ovu strukturu. P RIMJER 3.11 Dokažite: Za sve cijele brojeve x, ako 4 dijeli x, onda je x paran broj. 1. Identificirati pretpostavke i zaključke: Pretpostavka: x je cijeli broj djeljiv sa 4. Zaključak: x je paran broj. 2. Pretpostaviti da vrijede pretpostavke: Neka je x proizvoljni cijeli broj djeljiv sa 4. 3. Analizirati pretpostavke (koja svojstva vrijede i što sve znamo ako znamo pretpostavke): x je cijeli broj djeljiv sa 4, pa možemo pisati x = 4k, za neki k ∈ Z. 4. Analizirati zaključke (što su im definicije ili karakterizacije, tj. što sve mo- žemo i moramo pokazati da bi izveli zaključak): Trebamo zaključiti da je x paran broj. Da bismo to mogli, dovoljno je da pokažemo kako se x može zapisati kao x = 2l , za neki l ∈ Z. 5. Provesti niz zaključivanja: Kako je x = 4k, za neki k ∈ Z, onda možemo pisati x = 2(2k), pa ako stavimo l = 2k, slijedi da je x = 2l , za neki l ∈ Z. Nekad je teško dokazati kondicional direktno, pa umjesto toga dokažemo njegov obrat po kontrapoziciji. Vidjeli smo da su te dvije tvrdnje ekvivalentne, pa ako dokažemo jednu, slijedi da vrijedi i druga. Ovo se ponekad koristi i u drugim situacijama, kad uočimo neku tvrdnju ekvivalentnu zadanoj (ne nužno njezin obrat po kontrapoziciji), a koju je lakše dokazati. Prisjetimo se da je obrat po kontrapoziciji suda "Ako P onda Q", sud "Ako ¬Q onda ¬P ". P RIMJER 3.12 Dokažite: Za sve prirodne brojeve n, ako je n 2 neparan, onda je i n neparan. Kad bismo krenuli dokazivati ovu tvrdnju direktno, počeli bismo od pretpostavke da je n 2 neparan, tj. možemo pisati n 2 = 2k + 1, za neki k ∈ N. No onda bismo 38 morali nizom zaključivanja doći do činjenice da je i n neparan, što bi računski moralo uključivati operaciju korijenovanja i općenito ne bi tehnički bilo jednos- tavno. Promotrimo obrat po kontrapoziciji ove tvrdnje: Za sve prirodne brojeve n, ako je n paran broj, onda je i n 2 paran broj. Direktni dokaz ove tvrdnje je sljedeći: 1. Identificirati pretpostavke i zaključke: Pretpostavka: n paran broj. Zaključak: n 2 paran broj. 2. Pretpostaviti da vrijede pretpostavke: Neka je n proizvoljni parni prirodni broj. 3. Analizirati pretpostavke (koja svojstva vrijede i što sve znamo ako znamo pretpostavke): Tada n možemo pisati kao n = 2k, za neki k ∈ N. 4. Analizirati zaključke (što su im definicije ili karakterizacije, tj. što sve mo- žemo i moramo pokazati da bi izveli zaključak): Trebamo zaključiti da je n 2 paran broj. Da bismo to mogli, dovoljno je da pokažemo kako se n 2 može zapisati kao n 2 = 2l , za neki l ∈ N. 5. Provesti niz zaključivanja: Kako je n = 2k, za neki k ∈ N, onda vrijedi n 2 = (2k)2 = 4k 2 = 2(2k 2 ), pa ako stavimo l = 2k 2 , slijedi da je n 2 = 2l , za neki l ∈ N. Dokazan je obrat po kontrapoziciji, pa slijedi da vrijedi i originalna tvrdnja. Primijetimo da smo ovu istu tvrdnju već dokazali kod univerzalnog dokaza. Ovi tipovi dokaza koje radimo nisu med̄usobno isključivi, mnogi od njih se preklapaju. Često će neka tvrdnja glasiti: "Za svaki element nekog skupa, ako vrijedi P onda vrijedi Q", tako da je dokaz te tvrdnje istodobno i univerzalni i dokaz kondicionala. 3.6 Egzistencija i jedinstvenost Nekad će biti potrebno dokazati da postoji točno jedan objekt koji zadovoljava danu tvrdnju p(x), tj. da postoji jedinstveni takav objekt. Obično se takvi dokazi provode u dva koraka. Egzistencija: Pokažemo da postoji barem jedan objekt koji zadovoljava p(x). Jedinstvenost: Pokažemo da postoji najviše jedan objekt koji zadovoljava p(x). Ovo se obično provodi tako da pretpostavimo da postoje dva objekta, a i b, za koja vrijedi p(x) i onda pokažemo da je a = b. 3. TEORIJA DOKAZA 39 P RIMJER 3.13 Dokažite da jednadžba 2x + 1 = 5 ima jedinstveno realno rješenje. Egzistencija: Da bismo pokazali da dana jednadžbe ima barem jedno realno rješe- nje, moramo pronaći to rješenje (egzistencijalni dokaz). Jednostavnim računom dolazimo do rješenja x = 2. Jedinstvenost: Prepostavimo da su realni brojevi a i b rješenja dane jednadžbe. Tada vrijedi 2a + 1 = 5 i 2b + 1 = 5, pa vrijedi: 2a + 1 = 2b + 1, 2a = 2b, a = b. 3.7 Indirektni dokaz - dokaz kontradikcijom Dokaz kontradikcijom se provodi na sljedeći način: Pretpostavimo da vrijede sve pret- postavke i negacija zaključka (dakle za tvrdnju P → Q, pretpostavili bismo da vrijedi P ∧ ¬Q, tj. njezina negacija). Dokaz obično počinjemo riječima "Pretpostavimo su- protno,...". Dalje nastavljamo s izvod̄enjem zaključaka, dok ne dod̄emo do "kontradik- cije", tj. neke tvrdnje koja je antitautologija. Obično to bude neka očita neistina, ili tvrdnja suprotna pretpostavci za koju smo pretpostavili da vrijedi. U tom trenutku za- ključujemo da vrijedi početna tvrdnja, jer je za njezinu negaciju dokazano da je neisti- nita. P RIMJER 3.14 p Dokažite da je 2 iracionalan broj. p Pretpostavimo suprotno, da je 2 racionalan broj. Tada se on može zapisati kao p 2 = ba , gdje su a i b cijeli brojevi, b ̸= 0 i ba maksimalno skraćeni razlomak. Kva- driranjem slijedi a2 2= , b2 pa je a 2 = 2b 2 , što znači da je a 2 paran broj. U Primjeru 3.12 smo dokazali da ako je n 2 paran broj, onda je i n paran broj. Sada želimo zaključiti da iz a 2 paran, sli- jedi da je a paran. Možemo li korisititi istu tvrdnju? U kojem su odnosu te dvije tvrdnje? Lako bismo dokazali (može isto pomoću obrata po kontrapoziciji) da ako je kva- drat nekog broja paran, onda je i taj broj paran (dokažite za vježbu!), pa možemo izvesti zaključak da je u ovom slučaju a paran broj, tj. a = 2k, za neki k ∈ Z. No, sada imamo a = 2k i a 2 = 2b 2 4k 2 = 2b 2 b 2 = 2k 2. 40 Odatle slijedi da je b 2 paran broj, pa je i b paran broj. Dobivena je kontradikcija s a pretpostavkom da je b maksimalno skraćen razlomak, pa zaključujemo da vrijedi originalna tvrdnja. Napomena. Samo kratko uočimo što to znači da je kontradikcija antitautologija. U našem zaključivanju imali smo tvrdnje (neke kao pretpostavke, neke kao za- ključke): P = " ba je maksimalno skraćen razlomak" Q= "a je paran broj i b je paran broj" Tvrdnja P ∧ Q je očito antitautologija, neće biti istinita ni za jednu interpretaciju. Za takve tvrdnje nekad i kažemo da su kontradikcije, a u dokazima najčešće for- muliramo kao gore, kad izvedemo neki zaključak koji zajedno s nekom tvrdnjom od ranije daje antitautologiju, kažemo da smo dobili kontradikciju. P RIMJER 3.15 Dokažite: Za sve prirodne brojeve n, ako je n 2 neparan, onda je i n neparan. Ovu tvrdnju smo već dokazali direktnim dokazom pomoću obrata po kontrapo- ziciji u Primjeru 3.12, a sada ćemo pokazati kako bi izgledao dokaz ove tvrdnje kontradikcijom. Ta dva dokaza imaju sličnosti i važno je razlikovati što je točno drukčije u njihovoj provedbi. Tvrdnja je ovaj put oblika P → Q, pa će suprotno biti P ∧ ¬Q. Dakle, pretposta- vimo suprotno, neka je n 2 neparan i n paran prirodni broj. Zbog činjenice da je n paran možemo pisati n = 2k, za neki k ∈ N. No, sada slijedi n 2 = (2k)2 = 4k 2 = 2(2k 2 ), pa je očito i n 2 paran broj, što je kontradikcija s pretpostavkom da je n 2 neparan broj. Dakle, originalna tvrdnja vrijedi. 3.8 Dokaz bikondicionala Vidjeli smo već da je bikondicional P ↔ Q ekvivalentan tvrdnji P → Q ∧Q → P , pa ćemo bikondicional najčešće dokazivati tako da dokažemo dva kondicionala, koristeći direk- tni dokaz, obrat po kontrapoziciji ili dokaz kontradikcijom. Kažemo da moramo doka- zati "dva smjera". P RIMJER 3.16 Dokažite: Za sve prirodne brojeve n vrijedi: n je paran ako i samo ako je n 3 paran. 1. Dokažimo kondicional →: Ako je n paran broj onda je n 3 paran broj. Tvrdnu ćemo dokazati direktno. Neka je n paran. Tada je n = 2k, za neki 3. TEORIJA DOKAZA 41 k ∈ N. Slijedi n 3 = (2k)3 = 8k 3 = 2(4k 3 ), pa je očito i n 3 paran broj. 2. Dokažimo kondicional ←: Ako je n 3 paran broj onda je i n paran broj. Tvrdnju ćemo dokazati obratom po kontrapoziciji. Neka je n neparan broj. Tada je n = 2k − 1, za neki k ∈ N. Sada je n 3 = (2k − 1)3 = 8k 3 − 12k 2 + 6k − 1. S obzirom da su prva tri pribrojnika ovog izraza parna, a posljednji neparan, očito je n 3 neparan broj. Time je dokazan obrat po kontrapoziciji, pa vrijedi i početna tvrdnja. Prisjetimo se još, da smjer → često zovemo smjer nužnosti, a smjer ← smjer do- voljnosti, pa će se u nekim dokazima tako formulirati. 3.9 Dokaz disjunkcije Da dokažemo tvrdnju u kojoj je zaključak P ∨ Q obično pretpostavimo ¬P i dokažemo da odatle (i iz pretpostvaki) slijedi Q. (Možemo i dokazati samo P ili samo Q i odatle naravno slijedi P ∨ Q ali obično se ne može tako lako dokazati samo jedna od tvrdnji P ili Q , inače bi to bio zaključak, a ne P ∨Q). P RIMJER 3.17 Dokažite: Za sve cijele brojeve a i b vrijedi: Ako je ab = 0 onda je a = 0 ili b = 0. Dakle, pretpostavka nam je ab = 0, a zaključak je oblika disjunkcije. Tvrdnju ćemo dokazati tako da uz preptostavku ab = 0 uzmemo i da vrijedi a ̸= 0 i do- kažemo da odatle slijedi b = 0. (Analogno se može pretpostaviti b ̸= 0 i dokazati da je tada a = 0.) Dakle, neka vrijedi ab = 0 i a ̸= 0. Tada ovu jednadžbu možemo podijeliti s a (postoji inverzni element a −1 , podsjetiti se grupa!), pa ostaje b = 0. 3.10 Složeniji dokazi Kad su tvrdnje koje moramo dokazati složenijeg oblika, onda ćemo osnovne metode koje smo dosad naučili korisiti uzastopno, ili na različite kreativne načine kako bismo došli do zaključaka. Točno kako, će ovisiti o obliku tvrdnje i tokom školovanja ćete na- ići na mnogo kreativnih metoda dokazivanja, ali ove dosad navedene leže u srži svega. Ovdje ćemo navesti samo još dva tipa složenijih dokaza. 42 Niz bikondicionala Promotrimo sljedeću tvrdnju iz područja teorije grafova. Teorem 3.18: Neka je G graf s n vrhova. Tada su sljedeće tvrdnje med̄usobno ekvi- valentne: 1. Graf G je stablo; 2. Svaka dva vrha grafa G su povezana točno jednim putem; 3. Graf G je povezan i svaki njegov brid je rezni. Struktura ovog teorema kaže da je (a) ↔ (b), (b) ↔ (c) i (a) ↔ (c), dakle trebalo bi doka- zati tri bikondicionala, u svakome po dva smjera. Med̄utim, ovakav tip tvrdnji se doka- zuje cirkularno. Dakle, ako je tvrdnja koju moramo dokazati oblika P 1 ↔ P 2 ↔ P 3 ↔... ↔ P n , onda da dokažemo sve bikondicionale dovoljno je dokazati: P1 → P2 P2 → P3... P n−1 → P n Pn → P1 Tako da bi u prethodnom teoremu dokazali da iz (a) slijedi (b); iz (b) slijedi (c) i zatim da iz (c) slijedi (a) i to bi zatvorilo krug niza kondicionala, odakle slijedi da su sve te tvrdnje med̄usobno ekvivalentne. Dokaz po slučajevima Ovaj tip dokaza ne odnosi se toliko na složenost tvrdnje, koliko na olakšavanje dokaz- nog procesa razbijanjem pretpostavke ili zaključka na slučajeve. Zamislimo da moramo dokazati tvrdnju P → Q, ali je to iz nekog razloga jako složeno. Med̄utim, uočimo da se P može razbiti na više slučajeva P 1 ,..., P n (npr. ako neku tvrdnju treba dokazati za sve prirodne brojeve, možemo razbiti pretpostavku n je prirodan broj na slučajeve kad je n paran i kad je neparan). Ako dokažemo da u svakom slučaju vrijedi Q tj. da je P1 → Q... P n → Q, onda će odatle slijediti P → Q. 3. TEORIJA DOKAZA 43 P RIMJER 3.19 Dokažite: Ako je n 2 djeljiv s 3, onda je i n djeljiv s 3. Dokažimo tvrdnju obratom po kontrapoziciji. Neka je n prirodan broj koji nije djeljiv s 3. Moramo pokazati da n 2 nije djeljiv s 3. Znamo da ako je broj n djeljiv s 3, možemo ga pisati u obliku n = 3k, za neki k ∈ N. ako n nije djeljiv s 3, onda je njegov ostatak pri dijeljenju s 3 ili 1 ili 2, tj. možemo ga pisati ili kao n = 3k + 1 ili kao 3k + 2. To nas dovodi do dva slučaja na koja se razbija naša pretpostavka da n nije djeljiv s 3. 1. slučaj. Neka je n = 3k +1. Tada je n 2 = (3k +1)2 = 9k 2 +6k +1. Ovo dalje možemo pisati kao n 2 = 3(3k 2 + 2k) + 1, pa vidimo da n 2 nije djeljiv s 3 u ovom slučaju. 2. slučaj. Neka je n = 3k +2. Tada je n 2 = (3k +2)2 = 9k 2 +12k +4 = 9k 2 +12k +3+1, što dalje možemo pisati kao n 2 = 3(3k 2 + 4k + 1) + 1, pa očito ni u ovom slučaju n 2 nije djeljiv s 3. Napomena 3.20 U ovom poglavlju su dani samo kratki pregledi osnovnih metoda dokazivanja s vrlo jednostavnim primjerima koji se oslanjaju na elementarno matematičko zna- nje. Već ste i sami u školovanju susreli još neke metode dokazivanja, npr. dokaz indukcijom, o njemu će biti riječi pri kraju ovog kolegija. Uspješno provod̄enje dokaza se zasniva na dobrom poznavanju matematičkog gradiva, korektnom iz- vod̄enju logičkih zaključaka i poštivanju strukture dokaza. Ovo je samo uvod u teoriju dokaza, a sa svakim novim dokazom u ovom i ostalim kolegijima tokom studiranja ćete naučiti razviti i produbiti svoje vještine dokazi- vanja. Nekoliko korisnih uputa za praćenje i učenje dokaza tokom studiranja: Uvijek se zapitajte što su točno pretpostavke i što točno dokazujemo. Uvijek neka vam bude jasno koji tip dokaza se koristi. U svakom koraku neka bude jasno zašto baš to slijedi iz prethodnog koraka, je li na temelju nekog aksioma, je li očito zbog računa, je li zbog neke pret- postavke ili prije dokazane tvrdnje. Ako je u nekom koraku nejasno zašto sljedeći korak slijedi, dobro provjerite je li nastala greška u zaključivanju. Obratite se profesoru odmah za bilo kakve nejasnoće oko ovih pitanja, male rupe u razumijevanju iz ovog područja postaju samo sve veće ako se ne ra- zjasne. Za lijepi tekst s puno vježbi o teoriji dokaza pogledajte. 44 3.11 Vježbe - Dokazi 1. Dokažite sljedeće tvrdnje: (a) Za sve cijele brojeve x, x − 1 dijeli x 3 − 1. (b) Postoji cijeli broj x za koji je x 2 − 5x + 6 = 0. (c) Kvadrat svakog neparnog broja je neparan broj. (d) Kvadrat nekog cijelog broja je neparan broj. (e) Postoje realni brojevi u i v takvi da je 2u + 5v = −29. (f) Za sve realne brojeve a, b i c, postoji kompleksni broj x takav da je ax 2 +bx + c = 0. 2. Nad̄ite protuprimjere za svaku od sljedećih tvrdnji: (a) Svaki cijeli broj je rješenje jednadžbe x + 1 = 0. (b) Umnožak svaka dva cijela broja je paran broj. (c) Za svaki parni prirodni broj n, broj n 2 je djeljiv s 8. (d) Dva prirodna broja a i b biti će djeljiva nekim prirodnim brojem c kada je njihov zbroj djeljiv brojem c. 3. Dana je tvrdnja: „Postoje pozitivni brojevi x i y takvi da je x − y pozitivan broj.“ Što od sljedećeg je točno? Objasnite. (a) Tvrdnja nije istinita jer za na primjer x = 2, y = 4, x − y = −2 nije pozitivan broj. (b) Tvrdnja je istinita jer je razlika dva pozitivna broja uvijek pozitivan broj. (c) Tvrnja je istinita jer za na primjer x = 4, y = 2, razlika x − y = 2 je pozitivan broj. (d) Tvrdnja nije istinita jer razlika dva pozitivna broja ne mora uvijek biti poziti- van broj. (e) Tvrdnja je istinita jer za na primjer x = 5, y = −1 vrijedi da je razlika x − y = 6 pozitivan broj. 4. Dokažite sljedeće tvrdnje direktnim dokazom: (a) Zbroj dva parna broja je uvijek paran. (b) Umnožak dva neparna broja je uvijek neparan. (c) Kada je barem jedan od faktora umnoška dvaju prirodnih brojeva djeljiv bro- jem c, onda je i umnožak tih brojeva djeljiv s c. (d) Zbroj triju uzastopnih prirodnih brojeva je uvijek djeljiv s 3. 5. Dokažite sljedeće tvrdnje pomoću obrata po kontrapoziciji i svod̄enja na kontra- dikciju: 3. TEORIJA DOKAZA 45 (a) Za sve prirodne brojeve n, ako je n 4 paran onda je i n paran. (b) Za sve prirodne brojeve a i b, ako je umnožak ab paran onda je a paran ili je b paran. a+b p (c) Ako su a i b pozitivni realni brojevi onda vrijedi 2 ≥ ab. 6. Neka je a cijeli broj. Dokažite: a 3 + a 2 + a je paran broj ako i samo ako je a paran broj. 7. Neka je a cijeli broj. Dokažite da su sljedeće tvrdnje ekvivalentne: (a) a je djeljivo sa 3; (b) 3a je djeljivo sa 9; (c) a + 3 je djeljivo sa 3.  4 46 POGLAVLJE Osnove teorije skupova 4.1 Pojam skupa................................ 46 4.2 Vježbe - Skupovi 1............................. 48 4.3 Odnosi med̄u skupovima........................ 48 4.4 Vježbe - Skupovi 2............................. 51 4.5 Operacije na skupovima......................... 52 4.6 Vježbe - Skupovi 3............................. 56 4.7 Familije skupova............................. 58 4.8 Kartezijev umnožak skupova...................... 60 4.9 Vježbe - Skupovi 4............................. 61 4.10 Razni zadaci za vježbu.......................... 62 4.1 Pojam skupa Skup je osnovni pojam koji se ne definira, a intuitivno ga možemo doživljavati kao mnoš- tvo objekata koje nazivamo elementima. Element može biti gotovo bilo što, broj, funk- cija, pravac,... Skupove obično označavamo velikim tiskanim slovima, A, B,C ,.., a ele- mente malim slovima a, b, c, x, y, z,.... Činjenicu da je x element skupa A zapisujemo kao x ∈ A, a činjenicu da y nije element skupa A zapisujemo kao y ∉ A. Ako u skupu A nema nijednog elementa onda kažemo da je A prazan skup i označavamo ga s ;. Skupove možemo zapisivati i zadavati na više načina. Jedan od njih je nabrajanje ele- menata unutar vitičastih zagrada, npr. {a, b, c, d }. Taj način možemo koristiti i kad ne nabrajamo sve elemente, npr. {10, 11,..., 19, 20} ili {1, 2, 3, 4,...} ili {... − 2, −1, 0, 1, 2, 3,...}. 4. OSNOVE TEORIJE SKUPOVA 47 Iako ovim skupovima nisu nabrojani svi elementi, jasno je o kojim skupovima se radi. Skup koji sadrži samo jedan element nazivat ćemo jednočlanim skupom, npr. {a}, dva elementa dvočlanim, {a, b} itd. Unutar vitičastih zagrada svaki je element dovoljno na- brojati jednom, pa je npr. {1, 2, 2} isto što i {1, 2}. Takod̄er, poredak elemenata nije važan, tj. skup {1, 2} isti je kao skup {2, 1}. (Primijetimo da nismo još formalno definirali što znači da su dva skupa jednaka!) Dosad su nam poznati neki specifični skupovi brojeva: Simbol Naziv N skup prirodnih brojeva Z skup cijelih brojeva Q skup racionalnih brojeva R skup realnih brojeva C skup kompleksnih brojeva Skupove N i Z bismo mogli zapisati nabrajanjem elemenata, no prikazati tako skup ra- cionalnih brojeva bilo bi vrlo teško, a skup realnih brojeva i nemoguće, pa promotrimo još neke načine zapisivanja skupova. U budućim poglavljima ćemo bolje upoznati svojstva skupa realnih brojeva, njegov pri- kaz na pravcu i ured̄aj med̄u njegovim elementima te objasniti točnu definiciju zapisa intervala. No za sada, kako je to zapis poznat iz dosadašnjeg školovanja, kako bismo mogli malo detaljnije primjerima ući u teoriju skupova, koristit ćemo intuitivno poz- nate zapise [a, b], 〈a, b〉, [a, b〉, 〈a, b], 〈−∞, b], 〈−∞, b〉, 〈a, ∞〉 i [a, ∞〉. Posljednji način zadavanja skupova je pomoću nekog svojstva, npr. x ∈ N : x je paran © ª {x ∈ R : x > 3 ∧ x ≤ 10} (x, y) ∈ R2 : x 2 + y 2 = 1 © ª Na ovaj način možemo zapisati i skup racionalnih brojeva na o Q= : a, b ∈ Z ∧ b ̸= 0 b 1 Primijetimo da smo na ovaj način naveli brojeve 2 i 42 , što je isti racionalni broj. No, kako smo rekli gore, taj broj postoji samo jednom u skupu racionalnih brojeva, kao i ostali, bez obzira što je više puta naveden. Više o ovome i o točnoj definiciji skupa Q će biti riječi u kasnijim poglavljima. P RIMJER 4.1 Ispitajte što od sljedećeg je istina: 1. 4.3456 ∈ C 2. 〈1, 3〉 = {2} 48 3. 0 ∈ ; 4. {;