MATEMATIƒNA LOGIKA IN LOGIƒNE NALOGE

UNIVERZA V LJUBLJANI PEDAGO’KA FAKULTETA

KATJA ZUPANƒIƒ

MATEMATIƒNA LOGIKA IN LOGIƒNE NALOGE

DIPLOMSKO DELO

LJUBLJANA, 2013

PEDAGO’KA FAKULTETA

Univerzitetni ²tudijski program prve stopnje Dvopredmetni u£itelj MATEMATIKA - RAƒUNALNI’TVO

KATJA ZUPANƒIƒ

MENTOR: doc. dr. PRIMOš ’PARL SOMENTOR: asist. MATEJ ZAPU’EK

MATEMATIƒNA LOGIKA IN LOGIƒNE NALOGE

DIPLOMSKO DELO

LJUBLJANA, 2013

Zahvala

Zahvaljujem se o£etu in materi, ki sta mi omogo£ila ²tudij, in bratu Nejcu, ki mi je vedno stal ob strani.

Zahvaljujem se prijateljem, ki so me spodbujali in mi nudili oporo, ko sem jo potrebovala.

Zahvaljujem se mentorju doc. dr. Primoºu ’parlu za strokovno pomo£, nasvete in potrpeºljivost pri nastajanju diplomskega dela. Zahvaljujem se somentorju asist. Mateju Zapu²ku za vso pomo£ in podano znanje v £asu

²tudija.

Povzetek

V diplomskem delu Matemati£na logika in logi£ne naloge predstavimo ne- kaj osnov teorije matemati£ne logike, strategije re²evanja logi£nih nalog in primere nalog, ki se pojavljajo na logi£nih tekmovanjih v osnovni in srednji

²oli.

V prvem delu predstavimo osnove matemati£ne logike, ki so potrebne za razumevanje in uspe²no re²evanja logi£nih nalog. Najprej spoznamo objekte, s katerimi operiramo. To so izjave in izjavni vezniki. V nadaljevanju preu-

£imo odnose med njimi, se seznanimo s pojmom enakovrednosti izjav, izbra- nimi oblikami izjav, polnimi nabori veznikov ter logi£nimi posledicami, na koncu pa vse to poveºemo in uporabimo pri sklepanju v izjavnem ra£unu.

Sledi kraj²i uvod v osnove teorije mnoºic, ki jih potrebujemo za razlago po- membnega dela matemati£ne logikepredikatnega ra£una.

V drugem delu diplomskega dela spoznamo na£ine dokazovanja resni£- nosti ali neresni£nosti izjav. Seznanimo se z u£inkovito univerzalno metodo re²evanja matemati£nih logi£nih nalog, ki nam lahko pomaga pri uspe²nem re²evanju poljubnega matemati£nega problema.

V zadnjem delu diplomskega dela naredimo kratek pregled logi£nih nalog, ki se pojavljajo na slovenskem tekmovanju v logiki, ki jih organizira Zveza za tehni£no kulturo Slovenije. Za konec nekatere po korakih re²imo.

Klju£ne besede: matemati£na logika, strategija re²evanja, logi£na naloga.

MSC(2010) Klasikacija: 03F03, 03B05.

Abstract

In this BSc thesis entitled Mathematical logic and logical puzzles we intro- duce some basics concerning the theory of mathematical logic, strategies for solving logical problems and examples of such problems that occur in logic competitions in primary and secondary schools.

In the rst part we introduce the basics of mathematical logic required for the understanding and successful solving of logical problems. Firstly we introduce the objects with which we work. These are propositions and propo- sitional conjunctions. Next we study the relations between them, introduce the concept of equivalence of propositions, the selected forms of propositions, the full collection of conjunctions and the logical implications. At the end we use all this knowledge in the propositional calculus. What follows is a short introduction into set theory that is needed in an important part of mathematical logicpredicate calculus.

In the second part of this thesis we establish dierent ways of proving the truthness or falseness of propositions. We consider an eective, universal method for solving mathematical logical problems which may be helpful in solving any mathematical problem.

In the last part of this thesis we make a brief summary of logical problems that occur in Slovene logic competitions organised by the Slovene technical culture association (ZOTKS). At the end we provide examples of dierent types of such problems and solve some of them step by step.

Key words: mathematical logic, strategy of solving, logical problem.

MSC(2010) Classication: 03F03, 03B05.

Kazalo

Zahvala Povzetek Abstract

1 Uvod 1

2 Izjave 3

2.1 Osnove matemati£ne logike . . . 3

2.2 Izjavne povezave . . . 4

2.3 Enakovredni izjavni izrazi . . . 8

2.4 Izbrane oblike izjav . . . 10

2.5 Polni nabori izjavnih veznikov . . . 13

2.6 Sklepanje in dokazovanje v izjavnem ra£unu . . . 14

2.7 Osnove predikatnega ra£una . . . 19

3 Strategije re²evanja 23 3.1 Dokazovanje matemati£nih izjav . . . 23

3.2 Koraki re²evanja . . . 26

4 Logi£ne naloge 27 4.1 Primeri nalog . . . 28

5 Sklep 41

Literatura 43

Izjava

Poglavje 1 Uvod

Preden se lotimo pregleda teorije, naredimo kratek zgodovinski uvod, kate- rega bomo povzeli po [2].

Logika se je za£ela razvijati v anti£ni Gr£iji in Indiji v tesni povezavi s lozojo in matematiko. Prvi predstavniki so bili znani lozo Zenon Ele- atski, Sokrat, Platon in matematik Evklid. Svoje u£ence so u£ili, kako se izraºati, kako braniti svoja prepri£anja in teze. Sprva so logiko imenovali dialekta, kar v resnici pomeni razprava. V takratnem £asu so v nekaterih mestnih drºavicah o politi£nih vpra²anjih odlo£ali in razglabljali vsi mo²ki, starej²i od 21 let. Zbirali so se na agorah (trgih), kjer so zagovarjali svoje predloge in zavra£ali trditve drugih. Ravno to je bil takrat glavni predmet logike.

Velik prelom je logika doºivela, ko je Aristotel razvil prvi urejeni sistem logike imenovan Silogizem, logiko pa je predstavil kot temelj lozoje.

Med 11. in 15. stoletjem se je logika pou£evala v ²olah zahodne Evrope.

Abelard je povzel znanje gr²ke logike in izdal pet knjig z naslovom Dialekta.

Ve£jega razvoja logika v tem obdobju ni doºivela.

Za£etek sodobne logike je leta 1879 nakazal Gottlob Frege s svojim delom Begrisschrift, ko je natan£no opredelil splo²nost in eksistence, simbolizacijo ter predikatni ra£un. Njegov na£rt je bil zgraditi matematiko na logi£nih temeljih. šal mu to ni uspelo, ker sta njegovo teorijo spodbila Russel in Gödel s svojimi paradoksi in izreki.

Zastoj razvoja logike je povzro£il, da se je predmet po£asi za£el umikati iz ²olskega programa. Ravno tako logika ni imela velike podpore pri mate- matikih, saj so bili le ti prepri£ani, da je preve£ besedna in nekoristna. V 80. letih 19. stoletja pa je splo²no zanimanje ponovno zraslo s knjigami

1

Raymonda Smullyana, ki je k logiki pristopil na povsem druga£en na£inz logi£nimi ugankami. Sledile so ²e druge zbirke in ra£unalni²ki programi za pou£evanje logike. Od leta 2002 pa se logika v osnovnih ²olah v Sloveniji pou£uje kot izbirni predmet.

Matemati£na logika je pomembna predvsem zato, ker poljubno trditev prevede v razli£ne oblike z namenom, da bolje razumemo, kaj je njeno spo- ro£ilo. Na podlagi tega se tudi laºje odlo£imo, ali je trditev resni£na ali neresni£na. Matemati£na logika preu£uje tudi povezave med trditvami, in si- cer nas predvsem zanima, kaj nam to, da poznamo resni£nost ali neresni£nost ene trditve, pove o drugi. S tem se bomo ukvarjali v nadaljevanju.

Poglavje 2 Izjave

V tem diplomskem delu bomo matemati£no logiko obravnavali v nekoliko poenostavljeni obliki. Povsem striktna in matemati£no korektna obravnava bi namre£ bistveno pove£ala obseg tega diplomskega dela, poleg tega pa bi na ta na£in obravnava postala prezahtevna in tako ne bi bila dostopna ²ir-

²emu krogu bralcev. Slede£a teorija, ki jo bomo v za£etnih razdelkih povzeli po [3] in [8], bo tako bralcu razumljiva tudi brez poglobljene matemati£ne izobrazbe. Podrobnej²o razlago lahko zahtevnej²i bralec najde v knjigah [3], [4] in [5].

2.1 Osnove matemati£ne logike

Predmet matemati£ne logike so izjave. Izjava je trditev, ki jo lahko razumemo

²ele, ko poznamo pomen besed, ki jo sestavljajo. Pravimo, da poznamo semantiko jezika, v katerem je izjava zapisana.

Denicija 1. Izjava je smiselna trditev, ki je bodisi resni£na (oznaka 1) bodisi neresni£na (oznaka 0).

Denicija 2. Izjava je enostavna ali sestavljena. Enostavne izjave ne mo- remo raz£leniti na enostavnej²e izjave. Sestavljena izjava je grajena s po- vezovanjem enostavnih izjav s pomo£jo logi£nih veznikov (ne, in, ali, £e ...

potem, £e in samo £e ...).

Izjave, ki so pomembne za matemati£no logiko, in s katerimi se bomo ukvarjali mi, so predvsem sestavljene izjave. Ko ugotavljamo resni£nost enostavne izjave, analiza njene strukture ni potrebnaodgovor glede njene

3

resni£nosti bodisi poznamo bodisi ne. Pri sestavljenih izjavah pa si lahko v£asih z analizo strukture zelo pomagamo. S tako vrsto analize se ukvarja matemati£na logika.

O sestavljenih izjavah lahko povemo naslednje:

1. Resni£nost oziroma neresni£nost sestavljene izjave je odvisna od resni£- nosti ali neresni£nosti enostavnih izjav, ki jo sestavljajo, ter od logi£nih veznikov, ki enostavne izjave povezujejo.

2. S pomo£jo logi£ne analize sestavljene izjave lahko dobimo nove izjave, ki so vsebinsko enakovredne za£etni sestavljeni izjavi.

2.2 Izjavne povezave

2.2.1 Izjavni vezniki

V tem razdelku se bomo seznanili z logi£nimi vezniki, ki jih uporabljamo pri gradnji sestavljenih izjav.

Sestavljene izjave gradimo s pomo£jo logi£nih veznikov. Le-ti so lahko:

• 0-mestni (resnica, neresnica),

• 1-mestni (negacija),

• 2-mestni (osnovni vezniki: konjunkcija, disjunkcija, implikacija, ekviva- lenca in dopolnilni vezniki: ekskluzivna disjunkcija, Sheerjev veznik, Lukasiewiczev veznik).

Preden se poglobimo v analizo posameznih veznikov, na²tejmo nekaj dogo- vorov, ki se jih bomo drºali v nadaljevanju:

1. Enostavne izjave ozna£ujemo z malimi tiskanimi £rkami p, q,r, ...

2. Sestavljene izjave ozna£ujemo z velikimi tiskanimi £rkami £rkamiA,B, C, ...

3. Resni£na izjava ima vrednost 1, neresni£na pa vrednost 0.

Posamezni veznik je deniran tako, da povemo, kdaj je ustrezna sestavljena izjava resni£na in kdaj neresni£na. To najlaºje predstavimo s pomo£jo re- sni£nostne tabele, v katero za vsak moºen nabor enostavnih izjav, ki dano

2.2. IZJAVNE POVEZAVE 5 izjavo sestavljajo, zapi²emo vrednost pripadajo£e sestavljene izjave. Stolpec, v katerem so te vrednosti zbrane, imenujemo kon£ni stolpec resni£nostne ta- bele. Izjavo, zapisano z enostavnimi izjavami in povezano z logi£nimi vezniki, imenujemo izjavni izraz. Denirajmo sedaj posamezne veznike.

Denicija 3. Negacija izjave je resni£na natanko tedaj, ko je ta izjava ne- resni£na in je neresni£na, ko je ta izjava resni£na. Oznaka negacije izjave p je ¬p in jo beremo kot ne p.

p ¬p

0 1

1 0

Tabela 2.1: Resni£nostna tabela izjavnega izraza¬p.

Denicija 4. Konjunkcija dveh enostavnih izjav je resni£na natanko tedaj, ko sta resni£ni obe izjavi in je neresni£na v vseh ostalih primerih. Oznaka konjunkcije izjav p in q je p∧q in jo beremo kot p in q.

p q p∧q

0 0 0

0 1 0

1 0 0

1 1 1

Tabela 2.2: Resni£nostna tabela izjavnega izraza p∧q.

Ker logi£ne veznike deniramo s tem, da dolo£imo, pri katerih nabo- rih vrednosti pripadajo£ih enostavnih izjav je ustrezna sestavljena izjava re- sni£na, jih lahko deniramo kar preko resni£nostne tabele. Ostale veznike tako denirajmo kar s tabelo 2.3.

ime veznika oznaka resni£nostna beremo kot tabela

disjunkcija ∨ 0 1 1 1 pali q - mogo£e oboje

implikacija ⇒ 1 1 0 1 £ep potem q

ekvivalenca ⇔ 1 0 0 1 pje ekvivalentno q

ekskluzivna disjunkcija Y 0 1 1 0 bodisi pbodisi q

Sheerjev veznik ↑ 1 1 1 0 nep ali ne q

Lukasiewiczev veznik ↓ 1 0 0 0 niti p niti q

p 0 0 1 1

q 0 1 0 1

Tabela 2.3: Tabela logi£nih veznikov.

2.2.2 Mo£ veznikov

Ve£krat se zgodi, da v sestavljeni izjavi nastopa ve£ veznikov. V tem primeru je potrebno imeti dogovor o mo£i veznikov. To pomeni, da dolo£imo vrstni red izra£unavanja. ƒe z oklepaji ni dolo£eno druga£e, je vrstni red mo£i veznikov slede£: ¬veºe mo£neje kot ∧ inY, ki veºeta mo£neje kot ∨ in↑ in

↓, ki veºejo mo£neje kot⇒, ki veºe mo£neje kot⇔. Kadar v izjavi nastopajo vezniki iste mo£i, upo²tevamo pravilo z leve proti desni.

Zgled Sestavljeno izjavo

p∨q⇔ ¬q⇒p∧ ¬¬q torej beremo kot

(p∨q)⇔((¬q)⇒(p∧(¬(¬q)))).

2.2.3 Vrste izjav

V matemati£ni logiki imamo tri vrste izjav, ki jih lo£imo glede na to, ali se njihova resni£nost lahko spreminja s spreminjanjem vrednosti izjav, ki jo sestavljajo, ali ne.

Denicija 5. Izjava je tavtologija, £e je resni£na ne glede na vrednosti eno- stavnih izjav, ki izjavo sestavljajo. Izjava je protislovje, £e je neresni£na ne glede na vrednosti enostavnih izjav, ki izjavo sestavljajo. Ostale izjave so fakti£ne.

2.2. IZJAVNE POVEZAVE 7 Zgled Ugotovimo vrste naslednjih sestavljenih izjav:

1. (p∧(p⇒q))⇒q 2. (p∨q)⇔ ¬(p↑q) 3. ¬(¬p⇒q)∧ ¬(¬q∨r)

To najlaºje storimo preko resni£nostne tabele.

p q (p ∧ (p ⇒ q)) ⇒ q

0 0 0 1 1

0 1 0 1 1

1 0 0 0 1

1 1 1 1 1

Tabela 2.4: Resni£nostna tabela izjavnega izrazap∧(p⇒q))⇒q.

p q (p ∨ q) ⇔ ¬ (p ↑ q)

0 0 0 1 0 1

0 1 1 0 0 1

1 0 1 0 0 1

1 1 1 1 1 0

Tabela 2.5: Resni£nostna tabela izjavnega izraza (p∨q)⇔ ¬(p↑q).

p q r ¬ (¬ p ⇒ q) ∧ ¬ (¬ q ∨ r)

0 0 0 1 1 0 0 0 1 1

0 0 1 1 1 0 0 0 1 1

0 1 0 0 1 1 0 1 0 0

0 1 1 0 1 1 0 0 0 1

1 0 0 0 0 1 0 0 1 1

1 0 1 0 0 1 0 0 1 1

1 1 0 0 0 1 0 1 0 0

1 1 1 0 0 1 0 0 0 1

Tabela 2.6: Resni£nostna tabela izjavnega izraza ¬(¬p⇒q)∧ ¬(¬q∨r). Opazimo, da ima tabela 2.4 v kon£nem stolpcu same 1, kar pomeni, da je izjava vedno resni£na. Izjavap∧(p⇒q))⇒q je torej tavtologija. Izjava (p∨q)⇔ ¬(p↑q)je fakti£na. V tabeli 2.5 namre£ vidimo, da se pojavljajo tako0kot 1. Podobno s pomo£jo tabele 2.6 ugotovimo, da je izjava¬(¬p⇒ q) ∧ ¬(¬q ∨ r) protislovna. Ne glede na nabor vrednosti izjav, ki izjavo sestavljajo, je v kon£nem stolpcu vedno 0.

2.3 Enakovredni izjavni izrazi

še na za£etku poglavja smo omenili, da nas obi£ajno zanima le, kaj nam neka izjava pove, ne pa na kak²en na£in. S pomo£jo logi£ne analize lahko izjave z enakim pomenom zapi²emo na razli£ne na£ine. V tem razdelku bomo vpeljali pojem enakovrednosti izjav in si nekaj znanih podrobno pogledali.

Denicija 6. Izjavi p in q sta enakovredni (tudi ekvivalentni), £e je izjava p ⇔ q tavtologija. Dejstvo, da sta izjavi p in q ekvivalentni, zapi²emo s p∼q.

2.3. ENAKOVREDNI IZJAVNI IZRAZI 9 Izrek 1. Naj bodo p, q in r poljubne enostavne izjave. Tedaj veljajo logi£ne ekvivalence, ki so zbrane v tabeli 2.7

logi£na ekvivalenca za poljubne izjave p, q, r velja:

zakon dvojne negacije E1: p∼ ¬(¬p) idenpotentnost E2: p∧p∼p

E3: p∨p∼p E4: p⇒p∼1 E5: p⇔p∼1 komutativnost E6: p∧q∼q∧p

E7: p∨q∼q∨p E8: p⇔q ∼q⇔p

asociatovnost E9: p∧(q∧r)∼(p∧q)∧r E10: p∨(q∨r)∼(p∨q)∨r absorpcija E11: p∨(p∧q)∼p

E12: p∧(p∨q)∼p

distributivnost E13: p∨(q∧r)∼(p∨q)∧(p∨r) E14: p∧(q∨r)∼(p∧q)∨(p∧r) de Morganova zakona E15: ¬(p∧q)∼ ¬p∨ ¬q

E16: ¬(p∨q)∼ ¬p∧ ¬q

kontrapozicija E17: p⇒q ∼ ¬q⇒ ¬p∼ ¬p∨q ekvivalenca E18: p⇔q ∼(p⇒q)∧(q ⇒p)

E19: p⇔q ∼(¬p∨q)∧(p∨ ¬q) E20: p⇔q ∼(p∧q)∨(¬p∧ ¬q) Tabela 2.7: Tabela osnovnih logi£nih ekvivalenc.

S pomo£jo logi£nih ekvivalenc lahko dano izjavo zapi²emo v razli£nih ena- kovrednih oblikah. Na ta na£in lahko sporo£ilo izjave veliko bolje razumemo in tako laºje sodimo o njeni resni£nosti oziroma neresni£nosti. Seveda je ekvivalenca izjav dejansko ekvivalen£na relacija. Velja namre£:

1. reeksivnost: A∼A, saj je A⇔A tavtologija,

2. simetri£nost: £e velja A ∼ B, potem velja tudi B ∼ A, saj je A ⇔ B tavtologija natanko tedaj, ko je B ⇔A tavtologija,

3. tranzitivnost: £e velja A∼ B in B ∼C, potem velja tudi A ∼C, saj

£e sta namre£ tako A ⇔ B kot B ⇔ C tavtologiji, je tudi A ⇔ C tavtologija.

Ekvivalence najlaºje dokaºemo s pomo£jo resni£nostne tabele. Za zgled do- kaºimo veljavnost prvega de Morganovega zakona.

Dokaz.

de Morganov zakon I p q (¬ (p∧q)) ⇔ (¬p ∨ ¬q)

0 0 1 0 1 1 1 1

0 1 1 0 1 1 1 0

1 0 1 0 1 0 1 1

1 1 0 1 1 0 0 0

Tabela 2.8: Dokaz de Morganovega zakona I.

Dokaze ostalih ekvivalenc naredimo na podoben na£in. Lahko pa si seveda pomagamo tudi z ºe dokazanimi ekvivalencami. Tako lahko na primer takrat, ko dokaºemo ºe vse ekvivalence doE18, ekvivalenco E19dokaºemo takole:

Dokaz. Dokaz ekvivalenceE19pri£nimo z izjavnim izrazom(¬p∨q)∧(p∨¬q). Izjavni izraz(¬p∨q)lahko zaradiE17zapi²emo kot(p⇒q), izjavni izraz(p∨

¬q)pa zaradiE7kot(¬q∨p). Dobimo izraz(p⇒q)∧(¬q∨p). Poenostavimo lahko ²e del izraza, in sicer (¬q∨p), ki je zaradi E17ekvivalenten (q ⇒p). Izraz (p ⇒ q)∧(q ⇒ p) je po E18 enakovreden izjavnemu izrazu p ⇔ q. Torej velja p⇔q∼(¬p∨q)∧(p∨ ¬q).

2.4 Izbrane oblike izjav

Do sedaj smo imeli podane sestavljene izjave, katerih resni£nost smo ugo- tavljali s pomo£jo resni£nostne tabele. V tem razdelku se bomo ukvarjali z vpra²anjem, kako iz resni£nostne tabele razbrati izjavo. V nadaljevanju bomo spoznali dva na£ina, ki nam to omogo£ata. Teorijo bomo povzeli po [8], [10] in [11].

2.4. IZBRANE OBLIKE IZJAV 11

2.4.1 Disjunktivna normalna oblika

Denicija 7. Disjunktivna normalna oblika (DNO) sestavljene izjave A je ekvivalenten izjavni izraz, ki je disjunkcija konjunkcij izjavnih spremenljivk in/ali njihovih negacij.

Algoritem DNO:

Izhajamo iz nabora izjav p₁, p₂, p₃, ..., p_n, ki sestavljajo izjavo B. Vsakemu naboru vrednosti izjav p1, p2, p3, ..., pn, pri katerem je sestavljena izjava B resni£na, priredimo osnovno konjunkcijo A_j =Vn

i=1a_ij, kjer so:

a_ij =

p_i ; £e je pri tem naboru vrednost p_i enaka 1

¬p_i ; £e je pri tem naboru vrednost p_i enaka 0

Dobljene izjavne izraze A_j z disjunkcijo poveºemo v sestavljeno izjavo. Do- bimo disjunktivno normalno obliko izjave.

Zgled Poi²£imo disjunktivno normalno obliko izjave z resni£nostno tabelo 2.9.

p q kon£ni stolpec osnovna konjunkcija

0 0 1 ¬p∧ ¬q

0 1 0

1 0 1 p∧ ¬q

1 1 0

Tabela 2.9: Zapis izjave v DNO.

Dobimo izjavo (¬p∧ ¬q)∨(p∧ ¬q), ki jo lahko ²e poenostavimo v:

(¬p∨p)∧ ¬q∼1∧ ¬q∼ ¬q.

Izrek 2. Vsaki izjavi, ki ni protislovje, lahko priredimo disjunktivno nor- malno obliko.

Dokaz. Izjava, ki ni protislovje, ima v kon£nem stolpcu resni£nostne tabele vsaj eno1. Dobimo torej vsaj eno osnovno konjunkcijo. Po algoritmu DNO lahko izrazu priredimo disjunktivno normalno obliko.

2.4.2 Konjunktivna normalna oblika

Denicija 8. Konjunktivna normalna oblika (KNO) sestavljene izjave A je ekvivalenten izjavni izraz, ki je konjunkcija disjunkcij izjavnih spremenljivk in/ali njihovih negacij.

Algoritem KNO:

Izhajamo iz nabora izjav p₁, p₂, p₃, ..., p_n, ki sestavljajo izjavo B. Vsakemu naboru vrednosti izjav p₁, p₂, p₃, ..., p_n, pri katerem je sestavljena izjava B neresni£na, priredimo osnovno disjunkcijo A_j =Wn

i=1a_ij, kjer so:

a_ij =

¬p_i ; £e je pri tem naboru vrednost p_i enaka 1 pi ; £e je pri tem naboru vrednost pi enaka 0

Dobljene izjavne izraze A_j s konjunkcijo poveºemo v sestavljeno izjavo. Do- bimo konjunktivno normalno obliko izjave.

Zgled Poi²£imo konjunktivno normalno obliko izjave z resni£nostno tabelo 2.10.

p q kon£ni stolpec osnovna disjunkcija

0 0 1

0 1 0 p∨ ¬q

1 0 1

1 1 0 ¬p∨ ¬q

Tabela 2.10: Zapis izjave v KNO.

Dobimo izjavo (p∨ ¬q)∧(¬p∨ ¬q), ki jo lahko ²e poenostavimo v:

(p∧ ¬p)∨ ¬q ∼0∨ ¬q ∼ ¬q.

Izrek 3. Vsaki izjavi, ki ni tavtologija, lahko priredimo konjunktivno nor- malno obliko.

Dokaz. Izjava, ki ni tavtologija, ima v kon£nem stolpcu resni£nostne tabele vsaj eno 0. Ker torej dobimo vsaj eno osnovno disjunkcijo, lahko izrazu priredimo konjunktivno normalno obliko.

Izrek 4. Vsaki izjavi lahko poi²£emo ekvivalentno izjavo, ki jo zapi²emo samo z izjavnimi vezniki ¬,∧ in ∨ter enostavnimi izjavami, od katerih je odvisna.

2.5. POLNI NABORI IZJAVNIH VEZNIKOV 13 Dokaz. Vsaka izjava, zapisana v KNO ali DNO obliki, je zapisana le z izjav- nimi vezniki ¬,∧,∨. V izreku 2 smo dokazali, da izjavo, ki ni protislovje, lahko zapi²emo v DNO obliki. Podobno smo v izreku 3 dokazali, da izjavo, ki ni tavtologija, lahko zapi²emo v KNO obliki. Posledi£no smo dokazali, da lahko vsako izjavo zapi²emo samo z izjavnimi vezniki ¬,∧,∨ ter njenimi enostavnimi izjavami.

2.5 Polni nabori izjavnih veznikov

V prej²njem razdelku smo videli, da lahko vsako izjavo zapi²emo le z ve- zniki ¬,∧,∨. V tem razdelku nas bo zanimalo, ali obstaja ²e kak²en nabor veznikov, ki nam to omogo£a.

Denicija 9. Mnoºica izjavnih veznikov N je poln nabor izjavnih veznikov,

£e za vsak izjavni izraz A obstaja enakovreden izjavni izraz B, ki vsebuje samo veznike iz N.

Trditev 1. Naj bo M neka mnoºica izjavnih veznikov in P neki poln nabor izjavnih veznikov. ƒe lahko vsak veznik iz P izrazimo samo z vezniki iz M, je tudi M poln nabor izjavnih veznikov

Dokaz. Podan je poljuben izjavni izraz A. Ker je P poln nabor, obstaja izjavni izrazB, ki je enakovreden Ain vsebuje samo veznike iz P. VB vsak veznik izrazimo le z vezniki iz M in dobimo nov izraz C, ki je ekvivalenten izrazu B. Ker je ekvivalen£na relacija tranzitivna, velja C ∼ A. Sklepamo, da jeM poln nabor izjavnih veznikov.

V prej²njem razdelku smo dokazali, da lahko vsako izjavo zapi²emo v DNO ali KNO obliki. Obe obliki vsebujeta le logi£ne veznike ¬,∧ in ∨, od koder sledi, da je nabor {¬,∧,∨} poln. Ker velja p∨q ∼ ¬(¬p∧q) (upo- raba de Morganovega zakona), sledi, da je tudi {¬,∧} poln nabor logi£nih veznikov. Podobno je zaradi ekvivalencep∨q ∼ ¬(¬p∨ ¬q) poln nabor tudi {¬,∨}. ’e bolj zanimiv pa je v tem pogledu Sheerjev veznik, saj lahko z njim izrazimo vse ostale veznike. To je leta 1913 dokazal Henry M. Sheer¹. Trditev 2. Sheerjev veznik je logi£ni veznik, s katerim lahko izrazimo vse ostale veznike, to je, {↑} je poln nabor logi£nih veznikov.

1poljski logik

Dokaz. Zaradi trditve 1 je dovolj, da s Sheerjevim veznikom izrazimo ve- znika¬ in∧.

1. Negacija: ¬p∼p↑p

Opomba: Izjava p ↑ p je resni£na natanko tedaj, ko je vsaj ena izmed izjavpinpneresni£na. Ker gre za eno in isto izjavo, se to zgodi natanko tedaj, ko jepneresni£na izjava. Iz tabele 2.2 in 2.3 razberemo, da velja (p↑p)∼ ¬(p∧p)^E2∼ ¬p.

2. Konjunkcija: p∧q ∼(p↑q)↑(p↑q)

Opomba: Iz tabele 2.2 in 2.3 razberemo, da velja p∧q ∼ ¬(p ↑ q). Uporabimo ugotovitev iz prve to£ke in zapi²imo konjunkcijo z veznikom Sheer.

3. Ker je nabor veznikov {¬,∧} poln, je poln tudi nabor {↑}.

Podobno bi lahko dokazali, da je tudi Lukasiewiczev veznik zadosten, to pomeni, da je tudi {↓} poln nabor logi£nih veznikov. Vendar pa pretirano skoparjenje s ²tevilom veznikov ni ravno priporo£ljivo. Kmalu se namre£

prepri£amo, da ta dva nabora za zapis poljubne izjave nista preve£ primerna, saj izraz tako ve£krat zapletemo, kot poenostavimo (se pa uporabljata v moderni digitalni elektroniki).

2.6 Sklepanje in dokazovanje v izjavnem ra£unu

Pomemben element matemati£ne logike je sklepanje. V tem podrazdelku se bomo osredoto£ili na pravila sklepanja in pravila dokazovanja, ki nam pomagajo pri re²evanju marsikatere logi£ne naloge. Teorijo bomo povzeli po [8], [10] in [11].

Denicija 10. Izjava p je logi£na posledica izjav q₁, q₂, q₃, ..., q_n natanko tedaj, ko je implikacija q₁ ∧ q₂ ∧ q₃ ∧ ... ∧ q_n ⇒ p tavtologija. Izjavam q₁, q₂, q₃, ..., q_n pravimo predpostavke ali premise, izjavi p posledica, izrazu q₁, q₂, q₃, ..., q_n |= p pa sklep. Sklep je veljaven oziroma pravilen natanko tedaj, ko je pripadajo£a implikacija tavtologija.

2.6. SKLEPANJE IN DOKAZOVANJE V IZJAVNEM RAƒUNU 15

2.6.1 Logi£ne implikacije

Spoznali smo logi£ne ekvivalence, ki nam omogo£ajo zapis dane izjave na ve£ razli£nih na£inov, sedaj pa se bomo posvetili ²e logi£nim implikacijam.

S pomo£jo logi£nih implikacij logi£no sklepamo, saj nam omogo£ajo, da iz danih izjav dobimo nove, ki iz njih logi£no sledijo. S tem ºelimo re£i, da £e izjava p implicira izjavoq, potem lahko trdimo, da bo v vsakem primeru, ko bo izjava p resni£na, zagotovo resni£na tudi izjavaq.

Izrek 5. Implikacije v tabeli 2.11 so logi£no veljavne.

logi£ne implikacije za poljubne izjave p, q, r velja:

modus ponens (MP) p∧(p⇒q)⇒q modus tolens (MT) ¬q∧(p⇒q)⇒ ¬p disjunktivni silogizem (DS) ¬p∧(p∨q)⇒q

hipoteti£ni silogizem (HS) (p⇒q)∧(q ⇒r)⇒(p⇒r) poenostavitev (Po) p∧q ⇒p

pridruºitev (Pr) p⇒p∨q

zakon o absurdu (p⇒q∧ ¬q)⇒ ¬p

Tabela 2.11: Tabela osnovnih logi£nih implikacij.

Implikacija je logi£no veljavna, £e je tavtologija. Za zgled dokaºimo, da to velja za modus ponens. Ostale implikacije se dokazujejo na podoben na£in.

Dokaz. Implikacijo s pomo£jo znanih ekvivalenc preoblikujmo v tavtologijo.

p∧(p⇒q)⇒q^E17∼ ¬(p∧(p⇒q))∨q

E17∼ ¬(p∧(¬p∨q))∨q

E14∼ ¬((p∧ ¬p)∨(p∧q))∨q

∼ ¬(0∨(p∧q))∨q

∼ ¬(p∧q)∨q

E15∼ (¬p∨ ¬q)∨q

E9∼ ¬p∨(¬q∨q)

∼ ¬p∨1

∼1

2.6.2 Sklepanje v izjavnem ra£unu

Oglejmo si konkreten zgled logi£nega sklepanja.

Zgled Dokaºimo veljavnost naslednjega sklepa: Prebral bom knjigo in nare- dil doma£o nalogo. ƒe bom prebral knjigo, jo bom odnesel v knjiºnico. Torej bom ²el tudi v knjiºnico.

Da formaliziramo sklep, moramo najprej identicirati enostavne izjave, ki v njem nastopajo:

• p≡ Prebral bom knjigo.

• q≡ Naredil bom doma£o nalogo.

• r≡ ’el bom v knjiºnico.

Kon£ni sklep zapi²emo v izjavnem ra£unu:

1. Premise so: p∧q, p⇒r.

2. Posledica je: r.

3. Sklep ima obliko: p∧q, p⇒r |=r.

Dokaºimo veljavnost sklepa s pomo£jo logi£nih implikacij.

• Uporaba Po: iz predpostavkep∧q lahko sklepamo, da velja izjava p.

• Uporaba MP: ker torej vemo, da sta izjavi p in p ⇒ r resni£ni, je resni£na tudi izjavar.

Pri dokazovanju veljavnosti sklepa si lahko pomagamo na ve£ na£inov, in sicer z uporabo resni£nostnih tabel, logi£nih ekvivalenc in implikacij. V na- daljevanju pa si bomo pogledali ²e en na£in. Veljavnost sklepa namre£ lahko pokaºemo tudi s tako imenovanimi pomoºnimi sklepi:

1. pogojni sklep: uporabimo takrat, ko ima posledica obliko implikacije, 2. sklep s protislovjem,

3. analiza primerov: uporabimo takrat, ko ima ena od predpostavk obliko disjunkcije.

Najprej poglejmo, kako se lotimo ugotavljanja pravilnosti sklepa, ko ima posledica obliko implikacije.

2.6. SKLEPANJE IN DOKAZOVANJE V IZJAVNEM RAƒUNU 17 Trditev 3. Pogojni sklep q₁, q₂, q₃, ..., q_n |= p ⇒ r je enakovreden sklepu q₁, q₂, q₃, ..., q_n, p|=r.

Dokaz. Zapi²imo sklep v obliki izjavnega izraza:

(q₁∧q₂∧q₃∧...∧q_n)⇒(p⇒r).

Dokazati moramo, da je sklep enakovreden izrazu (q1∧q2∧q3∧...∧qn∧p)⇒r.

Naj bo Q=q₁∧q₂∧q₃∧...∧q_n.

Q⇒(p⇒r)∼ ¬Q∨(¬p∨r)

∼(¬Q∨ ¬p)∨r

∼ ¬(Q∧p)∨r

∼(Q∧p)⇒r

Sklep, ki ima obliko implikacije, lahko torej najprej prevedemo v sklep, pri katerem prvo enostavno izjavo implikacije dodamo predpostavkam. Do- kazujemo torej sklep, ki ima obliko q₁, q₂, q₃, ..., q_n, p|=r.

Zgled Dokaºimo veljavnost sklepa: p⇒q∨r,¬r |=p⇒q.

Opazimo, da ima sklep obliko implikacije, torej bomo dokazovali s pogoj- nim sklepom.

• predpostavka: p⇒q∨r

• predpostavka: ¬r

• predpostavka pogojnega sklepa: p

• Uporaba MP: (p∧(p⇒(q∨r))) ⇒q∨r

• Uporaba DS: ¬r∧(q∨r)⇒q

• Uporaba pogojnega sklepa: p⇒q

V nadaljevanju se bomo seznanili z dokazovanje sklepa s protislovjem. Po- dobno kot pri dokazovanju s pogojnim sklepom moramo sklepu najprej poi- skati njemu enakovreden sklep. Ko to storimo, ugotavljamo veljavnost sklepa tako kot pri obi£ajnem sklepnem ra£unu.

Trditev 4. Sklepq₁, q₂, q₃, ..., q_n|=pje enakovreden sklepuq₁, q₂, q₃, ..., q_n,¬p|= 0.

Dokaz. Zapi²imo sklep v obliki izjavnega izraza:

(q₁ ∧q₂∧q₃∧...∧q_n)⇒p.

Dokazati moramo, da je sklep enakovreden izrazu (q1∧q2∧q3∧...∧qn∧ ¬p)⇒0) Naj bo Q=q₁∧q₂∧q₃∧...∧q_n.

Q⇒p∼ ¬Q∨p

∼ ¬(Q∧ ¬p)∨0

∼(Q∧ ¬p)⇒0

Za konec si poglejmo ²e dokazovanje sklepa z analizo primerov. Pri tem moramo paziti na to, da iz£rpamo vse moºnosti, saj bo v nasprotnem primeru na² sklep nepopoln.

Trditev 5. Sklepq₁, q₂, q₃, ..., q_n, p₁∨p₂ |=rje enakovreden sklepuq₁, q₂, q₃, ..., q_n, p₁ |= r∧q₁, q₂, q₃, ..., q_n, p₂ |=r.

Dokaz. Zapi²imo sklep v obliki izjavnega izraza:

(q₁∧q₂∧q₃∧...∧q_n)∧(p₁∨p₂)⇒r.

Dokazati moramo, da je sklep enakovreden izrazu

(q₁∧q₂∧q₃∧...∧q_n∧p₁ ⇒r)∧(q₁∧q₂∧q₃∧...∧q_n∧p₂ ⇒r).

Naj bo Q=q1∧q2∧q3∧...∧qn.

Q∧(p₁∨p₂)⇒r ∼ ¬(Q∧(p₁∨p₂))∨r

∼ ¬(Q∧p₁∨Q∧p₂)∨r

∼(¬(Q∧p₁)∧ ¬(Q∧p₂))∨r

∼(¬(Q∧p₁)∨r)∧(¬(Q∧p₂)∨r)

∼(Q∧p₁ ⇒r)∧(Q∧p₂ ⇒r).

2.7. OSNOVE PREDIKATNEGA RAƒUNA 19

2.7 Osnove predikatnega ra£una

Da spoznamo potrebo po vpeljavi dodatne teorije, si poglejmo naslednji pri- mer.

Zgled Podane imamo naslednje izjave:

p≡ Vsi ²tudentje se u£ijo.

q≡ Jan je ²tudent.

r≡ Jan se u£i.

Glede na na²o intuicijo bi moral biti sklepp, q |=r pravilen. Pa vendar tega z doslej sprejetimi dogovori ne moremo dokazati. Teºava je namre£ v tem, da moramo upo²tevati tudi notranjo zgradbo izjavp, q inr. V izjavnem ra£unu nas zanima le zunanja zgradba, tako pa izgubimo povezavo med izjavami. Tu si pomagamo s predikatnim ra£unom, s katerim se bomo povr²no seznanili v nadaljevanju.

Pobliºje poglejmo izjave:

• Izjavi pin q govorita o ²tudentih.

• Izjava q inr govorita o Janu.

• Izjavi pin r pa o u£enju.

V okviru predikatnega ra£una poseºemo v drugo vejo matematike, teorijo mnoºic, zato se bomo najprej seznanili z najosnovnej²imi pojmi in simboli, ki jih bomo potrebovali pri opredelitvi. Teorijo bomo povzeli po [1] in [11].

2.7.1 Predikati in kvantikatorji

Za na²e potrebe bomo rekli, da je mnoºica skupina objektov oziroma re£i z neko lastnostjo. Ozna£evali jih bomo z velikimi tiskanimi £rkami. Objek- tom re£emo tudi elementi in jih bomo ozna£evali z malimi tiskanimi £rkami.

Kadar poljuben element a pripada mnoºici P, s simboli zapi²emo a ∈ P. Mnoºica, ki nima elementov, se imenuje prazna mnoºica. Mnoºico vseh ele- mentov, o katerih je smiselno govoriti, ko imamo nek problem, imenujemo univerzalna mnoºica.

V predikatnem ra£unu uporabljamo dva kvantikatorja; univerzalni (oznaka

∀) in eksisten£ni (oznaka∃) kvantikator.

Zgled Z matemati£nimi simboli zapi²imo izjavi:

• Za vsako celo ²tevilo x velja, da jex² ≥0.

∀x: (x∈Z⇒x² ≥0)

• Obstaja naravno ²tevilo x, da velja x+ 2<4.

∃x: (x∈N∧x+ 2 <4)

Kvantikatorja ponavadi nastopata v povezavi z implikacijo (univerzalni kvan- tikator) in konjunkcijo (eksisten£ni kvantikator). Kvantikatorja imata v povezavi z logi£nimi vezniki naj²ibkej²o mo£, kadar nastopata skupaj pa upo-

²tevamo pravilo z leve proti desni.

Tako kot poznamo ekvivalence med izjavnimi izrazi v izjavnem ra£unu, jih poznamo tudi v predikatnem ra£unu. Za nas bo pomembno predvsem, kaj se zgodi s kvantikatorji, £e pripadajo£o izjavo zanikamo. Pri negaciji se univerzalni kvatikator zamenja z eksisten£nim, eksisten£i pa z univerzalnim.

Poleg zamenjave kvantikatorja se negira tudi kvanticirana izjava.

Oglejmo si nekaj konkretnih zgledov.

• univerzalni kvantikator:

negacija izjave Vsi sanjamo je izjava: Obstaja nekdo, ki ne sa- nja oziroma Nekateri ne sanjajo.

¬(∀x: (x∈Z⇒x² ≥0)) ∼ ∃x: (x∈Z∧x² <0)

• eksisten£ni kvantikator:

negacija izjave Obstaja ma£ka, ki ne lovi mi²i je izjava: Vse ma£ke lovijo mi²i.

¬(∃x: (x∈N∧x+ 2 <4)) ∼ ∀x: (x∈N⇒x+ 2≥4)

Ponovno si poglejmo izjave o ²tudentu Janu. Notranjo zgradbo izjave bi lahko predstavili s stavkom: Za vsak x velja: x je ²tudent ⇒ x se u£i. Za opis notranje zgradbe izjave smo uporabili spremenljivkox, ki ji pravimo tudi individualna spremenljivka. Sestavimo izjavni formuli oziroma predikata:

• Z(x)≡x je ²tudent;

• L(x)≡x se u£i.

2.7. OSNOVE PREDIKATNEGA RAƒUNA 21 Formuli Z(x) in L(x) postaneta izjavi, £e namesto x vzamemo nek konkre- tni objekt. Pravimo mu individualna konstanta. Ker govorimo o ljudeh, se je smiselno dogovoriti, da se vse izjave nana²ajo na ljudi. Pravimo, da so ljudje domena pogovora. Formuli postaneta izjavi tudi, £e pred njiju zapi-

²emo kvantikatorja: za vsakx ali obstaja x. Izjave tako lahko zapi²emo na naslednji na£in:

1. ∀x: (Z(x)⇒L(x)) 2. Z(J an)

3. L(J an) Sklep ima obliko:

∀x: (Z(x)⇒L(x)), Z(J an)|=L(J an).

Predikat predstavlja neko lastnost oziroma odnose, ki jih imajo med seboj individualne spremenljivke s podro£ja pogovora, odvisno od tega, ali je eno- mestni ali ve£mestni. V na²em primeru sta predikata enomestna, saj opazu- jemo le en x naenkrat. V primeru, da bi bila na²a izjava Vsak x je ve£ji od y, pa imamo opravka z dvema individualnima spremenljivkama, predikat pa je 2-mestni.

Zgled Izjave zapi²imo v matemati£ni obliki. Ozna£imo M(x)≡x je Slove- nec, N(x)≡je prijazen.

Vsi Slovenci so prijazni. ∀x: (M(x)⇒N(x)) Vsi Slovenci so neprijazni. ∀x: (M(x)⇒ ¬N(x)) Nekateri Slovenci so prijazni. ∃x: (M(x)∧N(x)) Nekateri Slovenci so neprijazni. ∃x: (M(x)∧ ¬N(x))

Lahko se zgodi, da imamo opravka z obema kvantikatorjema naenkrat. Za bolj²e razumevanje si poglejmo naslednji zgled.

Zgled Naj bo K(x, y) predikat x premaga y. Prevedimo izjave.

∀x∀y :K(x, y) Vsi premagajo vsakogar.

∀y∀x:K(x, y) Vsakogar premaga vsakdo.

∀x∃y :K(x, y) Vsakdo premaga koga.

∀y∃x:K(x, y) Vsakogar nekdo premaga.

∃x∀y :K(x, y) Nekdo premaga vse.

∃y∀x:K(x, y) Nekoga (vedno istega) premagajo vsi.

∃x∃y :K(x, y) Nekdo premaga nekoga.

∃y∃x:K(x, y) Nekdo je premagan.

Ugotovimo, da se v primeru enakih kvantikatorjev pomen izjave z za- menjavo vrstnega reda bistveno ne spremeni. Bolj previdni pa moramo biti, ko kvantikatorja nastopata me²ano. Iz resni£nosti izjave ∀x∃y : K(x, y) namre£ sledi, da je vsakdo bolj²i od vsaj enega (vsak ima lahko svojega poraºenca), medtem ko iz resni£nosti izjave∃y∀x:K(x, y)sledi, da obstaja nekdo, ki ga premagajo vsi.

Poglavje 3

Strategije re²evanja

Logi£ne naloge so ve£krat pravi izziv. V ve£ini primerov je najve£ji problem v tem, da ne vemo, kako se zadeve lotiti. Pa vendar obstaja kar nekaj nasvetov, ki nam re²evanje olaj²ajo. Najprej si bomo pogledali na£ine dokazovanja razli£no strukturiranih matemati£nih izjav, nato pa ²e korake re²evanja. Pri tem se naslonimo na [9].

3.1 Dokazovanje matemati£nih izjav

Pri dokazovanju osnovnih izjav si lahko pomagamo z raznimi triki. Eden izmed najbolj u£inkovitih je, da namesto podane izjave A sku²amo dokazati njej ekvivalentno izjavo B. Ve£krat imamo podano kompleksno izjavo A, o kateri ne znamo povedati veliko. Ko pa jo poenostavimo, ugotovimo, da v resnici o njeni resni£nosti znamo presoditi.

1. Konjunkcija

Vemo, da je konjunkcija p∧q resni£na natanko tedaj, ko sta resni£ni obe izjavi. Ko ugotavljamo resni£nost tak²ne izjave, najprej ugotovimo, ali drºi izjavap, nato pa ²e, ali drºi izjavaq. Izjavi dokazujemo lo£eno.

Zapi²emo dokaz izjave p, nato pa ²e dokaze izjave q. ƒe nam uspe dokazati resni£nost obeh izjav, potem smo izjavo p∧q dokazali. ƒe uspemo pokazati, da katera od izjavp inq ni resni£na, je seveda izjava p∧q neresni£na.

23

2. Implikacija

Implikacija p ⇒ q je neresni£na le v primeru, ko je izjava p resni£na, izjava q pa neresni£na. Pri implikaciji tako na² dokaz temelji na izjavi p. Ta izjava je na²a predpostavka (spomnimo se pogojnega sklepa).

Tako predpostavimo resni£nost izjavepin dokazujemo resni£nost izjave q. Zavedati se moramo, da s tem nismo dokazali resni£nosti izjave q. Dokazali smo le, da £e drºi izjava p, potem drºi tudi izjava q.

3. Disjunkcija

Disjunkcijap∨qje resni£na v treh primerih, nepravilna pa le v enem, in sicer takrat ko sta izjavi pinq neresni£ni. Pri ugotavljanju resni£nosti izjave povezane z disjunkcijo lahko uporabimo nekaj trikov:

• dokaºemo resni£nost pali dokaºemo resni£nost qredko deluje,

• dokaºemo resni£nost njej ekvivalentne izjave: p∨q∼ ¬p⇒q. Primer, ko poi²£emo njej ekvivalentno izjavo, dokazujemo tako, kot smo zapisali pri prej²nji to£ki Implikacija.

4. Ekvivalenca

Pri dokazovanju resni£nosti izjave povezane z ekvivalence uporabimo znano logi£no ekvivalenco p ⇔ q ^E18∼ (p ⇒ q)∧(q ⇒ p). Izjavo raz- delimo na dva dela in dokazujemo po korakih. Najprej predpostavimo p in dokazujemo q. Pravimo, da dokazujemo z leve proti desni. Sledi drugi del dokazovanja, ko predpostavimo q ter dokazujemo p. Pra- vimo, da dokazujemo z desne proti levi. Imamo dva lo£ena poddokaza.

Pri dokazovanju drugega dela izjave se ne smemo sklicevati na to, kar smo ugotovili v prvem delu. V primeru, ko imamo ve£ ekvivalenc npr.

p ⇔ q ⇔ r, ni potrebno, da dokaºemo vse implikacije. Dovolj je, da dokaºemo(p⇒q)∧(q⇒r)∧(r⇒p).

5. Univerzalni kvantikator

Univerzalni kvantikator pravi, da ima vsak elementxiz domene pogo- vora neko lastnost, ozna£imo sϕ(x). ƒe to velja, potem znamo ta pogoj uporabiti tudi za neki poljubno izbrania. Uvedemo novo spremeljivko a in dokaºemo, da tudi zanjo velja pogoj.

3.1. DOKAZOVANJE MATEMATIƒNIH IZJAV 25 6. Eksisten£ni kvantikator

Pri dokazovanju resni£nosti izjave povezane z eksisten£nim kvantika- torjem je v prvem koraku potrebno uganiti konkretni a, za katerega pogoj, ozna£imo ga s ϕ(x), velja. V£asih je teºko najti konkretno vre- dnost a, ki bi ustrezala pogoju. Pomagamo si lahko s posku²anjem, ra£unanjem, razvijanjem pogoja v druge ekvivalentne oblike itd. Pri tem pazimo, da kak²ne re²itve ne izpustimo. Ko najdemo ustrezno vrednost, jo vstavimo v ena£bo in zapi²emo dokaz.

Lahko se zgodi, da bomo naleteli na primere, kjer nam ti nasveti ne bodo pomagali. Zato poznamo ²e en prijem, ki lahko pripelje do re²itve.

1. Dokaz s protislovjem

Ko dokazujemo resni£nost izjave s protislovjem, moramo to posebej opomniti. Recimo, da dokazujemo izjavo A. Prvi korak je, da pred- postavimo ¬A. Pri£nemo z dokazovanjem. Ko izjavo poenostavljamo, ra£unamo, torej logi£no sklepamo, pridemo do neke znane neresni£ne izjave. Ugotovimo, da iz neresni£nosti izjaveAsledi nesmisel. Pridemo torej do protislovja. S tem dokaºemo veljavnost izjaveA.

• Eksisten£ni kvantikator: Ko dokazujemo resni£nost izjave po- vezane z eksisten£nim kvantikatorjem po metodi dokaza s proti- slovjem, predpostavimo¬(∃x(x∈A∧ϕ(x)), kar pa je ekvivalentno izjavi ∀x(x ∈ A ⇒ ¬ϕ(x)). Pri£nemo z dokazovanjem. Ponovno na neki to£ki pridemo do protislovja.

• Disjunkcija: V primeru dokazovanja resni£nosti izjave povezane z disjunkcije s protislovjem predpostavimo ¬(p∨q), ki je ekviva- lentno izjavi ¬p∧ ¬q. Izpeljemo protislovje.

• Implikacija: Resni£nost izjave povezane z implikacijo dokaºemo s protislovjem tako, da predpostavimo ¬(p⇒q), ki je ekvivalentno izjavi p∧ ¬q. Izpeljemo protislovje.

Poglejmo ²e, kako se na re²evanje logi£nih nalog pripravimo. Postopek re-

²evanja nalog poteka v ²tirih korakih. Metoda se imenuje Polyajeva metoda, opis pa bomo povzeli po [1]. V prvem koraku moramo nalogo razumeti, v drugem si oblikujemo na£rt, ki nas bo vodil do re²itve, v tretjem pri£nemo z izvajanjem na²ega na£rta, v zadnjem, £etrtem, pa preverimo ustreznost re²itve, ki smo jo dobili.

3.2 Koraki re²evanja

1. Razumevanje problema

Ko dobimo nalogo, pozorno preberemo navodila. ƒe naletimo na be- sedo, ki je ne poznamo, poi²£emo razlago. Iz navodil razberemo podane podatke ter cilje naloge. Lahko si pomagamo s skico, opornimi to£kami in drugimi na£ini, ki nam pomagajo zbistriti misli. Ko ugotovimo, kaj naloga od nas zahteva, oblikujemo na£rt re²evanja.

2. Oblikovanje na£rta

V primeru, da smo ºe re²evali podoben primer, si lahko pomagamo z izku²njami. V nasprotnem primeru je potrebno, da dobro poznamo te- orijo. Poznavanje raznih denicij, trditev in izrekov nam bo re²evanje problema poenostavilo. Vedeli bomo tudi, kje za£eti in kako nadalje- vati. Ko smo teoreti£no podkovani, pri£nemo z re²evanjem.

3. Izvajanje na£rta

Po korakih re²imo problem. Re²itev ²e enkrat preverimo in se tako prepri£amo o pravilnosti. Tudi £e se nam zdi re²itev popolnoma logi£na, jo za nekaj £asa odmislimo in se vrnimo k njej kasneje. Prepri£ajmo se, da smo upo²tevali vse pogoje v navodilu ter uporabili vse potrebne denicije ali izreke.

4. Pogled nazaj

V zadnji fazi re²evanja re²itev utemeljimo ali poi²£emo ²e kak²en dokaz, ki bi utrdil na²o re²itev. Dobra metoda preverjanja pravilnosti re²ene naloge je, da za mnenje vpra²amo prijatelja. Ve£krat se zgodi, da smo kaj spregledali, posledi£no pa se spremeni tudi potek nadaljnega re²evanja. Ko smo o pravilnosti re²itve prepri£ani, jo zapi²emo.

Vsakega matemati£nega problema se moramo lotiti strukturirano, saj nam bo to omogo£ilo, da se bomo znali spopasti tudi z bolj zahtevnimi nalogami.

Poglavje 4

Logi£ne naloge

U£enci se v osnovni ²oli z logi£nim na£inom razmi²ljanja sre£ajo ºe v prvi triadi. Nau£ijo se razvr²£ati predmete ali pojme glede na dolo£ene lastnosti, dolo£iti povezave med dolo£enimi predmeti ali pojmi, prepoznavati odnose med njimi in podobno. Ob£asno re²ijo tudi kak²no nalogo, v kateri nastopajo dolo£ene izjave iz vsakdanjega ºivljenja in morajo presoditi o tem, kako re- sni£nost oziroma neresni£nost ene vpliva na resni£nost oziroma neresni£nost druge. V ²estem razredu se z izjavami bolj poglobljeno sre£ajo pri obravnavi ena£b in neena£b. Izjave, s katerimi se seznanijo, so enostavne in se nana-

²ajo predvsem na odnose med ²tevili. Na podro£ju logike v Sloveniji najbolj intenzivno delujeta Zaloºni²ko podjetje LOGIKA d.o.o s prevodi in izdajo knjig na temo logike ter z izdajo revije Logika in Razvedrilna matematika in Zveza za tehni£no kulturo Slovenije z organizacijo tekmovanj iz matema- ti£ne logike. Tekmovanje je namenjeno osnovno²olcem, srednje²olcem in tudi

²tudentom. Gre za pester nabor nalog, ki je primeren starostni skupini tek- movalcev. Naloge so primerljive z nalogami, s katerimi se sre£ujejo u£enci na drugih logi£nih tekmovanjih po svetu. Najbolj²i tekmovalci imajo moºnost priprave na Lingvisti£no olimpijado, ki poteka na mednarodni ravni. Na- loge, ki jih re²ujejo, se neposredno nana²ajo na sklepanje v izjavnem ra£unu, od u£enca pa zahtevajo predvsem prepoznavanje vzorcev. V nadaljevanju si bomo pogledali nekaj primerov nalog, ki jih re²ujejo u£enci na Logi£nem tekmovanju, in podrobno opisali korake re²evanja.

27

4.1 Primeri nalog

Po pregledu [2] in [12], sem zasledila naslednje tipe nalog:

1. osnove izjavne logike,

2. nabor izjav kot pomo£ pri razvrstitvi elementov v mnoºice, 3. matemati£ne uganke,

4. okolje z dolo£enimi pravili.

4.1.1 Osnove izjavne logike

Re²evalec ugotavlja pravilnost ali nepravilnost podane izjave. Izjave so se- stavljene, povezane z osnovnimi vezniki. Tema je matemati£na (odnosi med

²tevili, liki) kot tudi vseºivljenska (sorodstvene vezi, splo²ne teme). Re²e- valec mora biti dobro seznanjen z lastnostmi posameznega veznika. Vedeti mora, da je pravilnost sestavljene izjave odvisna od pravilnosti enostavnih izjav in veznikov, ki te izjave povezujejo.

Nalogo 4.1 so re²evali u£enci ²estega in sedmega razreda na ²olskem tek- movanju 18. slovenskega tekmovanja v logiki, leta 2003. Naloga se nahaja v [2], na strani 108. Zaradi bolj²e preglednosti bomo izjave dokazovali sproti.

Za na²e potrebe bomo vzeli le prvih7 izjav.

Naloga 4.1. Pri naslednjih izjavah ugotovite, ali je izjava vedno resni£na ali ne.

a. Zunaj deºuje ali ne deºuje.

Sestavljeno izjavo razdelimo na enostavni izjavi. To sta p: Zunaj deºuje in q: Zunaj ne deºuje. Opazimo, da je izjava qzanikanje izjave p. Izjavi sta povezani z veznikom ali. ƒe ºelimo, da bo sestavljena izjava resni£na, mora biti zaradi veznika pravilna vsaj ena izmed enostavnih izjav. Ker vemo, da veljap∨ ¬p∼1, je izjava resni£na.

b. Ni res, da zunaj deºuje in ne deºuje.

Izjava je zanikanje izjave: Zunaj deºuje in ne deºuje. Re²evanja nalog tak²nega tipa se najlaºje lotimo tako, da v za£etnem koraku ugotavljamo resni£nost izjave brez zanikanja. Enostavni izjavi sta enaki kot pri prej-

²nji nalogi, druga£na pa je njuna povezava. Povezani sta z veznikom in.

4.1. PRIMERI NALOG 29 Ker se izjavi med sabo izklju£ujeta, je izjava brez zanikanja neresni£na.

Posledi£no je zanikana izjava resni£na.

c. ƒe je naravno ²tevilo n deljivo z 2 in z 8, potem je deljivo tudi s 16. Opravka imamo z implikacijo. Izjava nam pove, da za vsako naravno

²tevilo, ki je deljivo z 2 in z 8 velja, da je deljivo tudi s 16. Kmalu ugotovimo, da iz predpostavke o deljivosti ²tevila z 2 in z 8 ni mogo£e dokazati deljivosti ²tevila s 16. Re²evanja naloge tak²nega tipa se lotimo tako, da sku²amo dokazati, da izjava ni pravilna. Ker gre za izjavo oblike

∀n : (n ∈ N∧2 |n∧8 | n ⇒16 |n), je njena negacija ∃n : (n ∈ N∧2 | n∧8|n∧16-n). Tako ²tevilo seveda zlahka najdemovzemimo8. Vemo, da je ²tevilo deljivo z 2, ravno tako vemo, da je ²tevilo deljivo z 8. Vemo pa tudi, da ²tevilo 8 ni deljivo s 16, torej je izjava neresni£na.

d. Naravno ²tevilo n je deljivo s 16 natanko tedaj, ko je deljivo z 2 in z 8. Tokrat gre za ekvivalenco. Pri na£inih dokazovanja smo dejali, da ekvi- valenco dokazujemo z implikacijo najprej z leve proti desni, nato pa ²e z desne proti levi. Da bo izjava resni£na, morata biti resni£ni tudi obe implikaciji. Pri prej²njem primeru smo dokazali, da implikacija z desne proti levi ne drºi. Posledi£no je ta izjava neresni£na.

e. ƒe je naravno ²tevilo n deljivo s 16, potem je deljivo z 2 in z 8.

Ponovno imamo opravka z implikacijo. Izjava nam pove, da je vsako naravno ²tevilo, ki je deljivo s 16, deljivo tudi z 2 in z 8. Pri nalogah tak²nega tipa moramo uporabiti malce matemati£nega znanja. Poljubno naravno ²tevilo n, ki je deljivo s 16, lahko zapi²emo kot 16·k, kjer je k neko naravno ²tevilo. ’tevilo n lahko torej zapi²emo tudi kot 2·8·k in tako je torej deljivo z 2 in8. Izjava je resni£na.

f. U£itelji vedno laºejo, ob ponedeljkih pa ne laºejo.

Izjava vsebuje kvantikator vsak. Izhajamo iz predpostavke, da vsi u£itelji vedno laºejo, to pomeni, da ne obstaja dan, da ne bi lagali. Potem je nemogo£e, da ob ponedeljkih ne bi lagali. ƒe torej drºi, da u£itelji vedno laºejo, potem morajo lagati tudi ob ponedeljkih (spomnimo se pogojnega sklepa). Izjava je neresni£na.

g. Ni res, da u£itelj laºe ali ne laºe.

Opravka imamo z zanikanjem izjave U£itelj laºe ali ne laºe. Razdelimo

sestavljeno izjavo na enostavni izjavi. To sta: p: U£itelj laºe in q: U£i- telj ne laºe. Podobno kot pri prvem primeru opazimo, da je izjava q zanikanje izjave p. Zaradi veznika ali je sestavljena izjava brez zanikanja resni£na natanko tedaj, ko je resni£na vsaj ena izmed enostavnih izjav.

Ker se izjavi med seboj izklju£ujeta, je izjava brez zanikanja resni£na.

Posledi£no je zanikana izjava neresni£na.

Nalogo 4.2 so re²evali u£enci devetega razreda osnovne ²ole in prvega letnika srednje ²ole na drºavnem tekmovanju 18. slovenskega tekmovanja v logiki, leta 2003. Naloga se nahaja v [2], na strani 121. Za na²e potrebe bomo vzeli le 10 izjav in eno situacijo. Zaradi laºje preglednosti bomo izjave dokazovali sproti.

Naloga 4.2. Ugotovi resni£nost danih stavkov v podani situaciji.

D

B A C

1. Ali lik A ni bel ali lik A ni srednje velikosti.

Pri nalogah tak²nega tipa mora re²evalec s pomo£jo slike ugotoviti, ali je dana izjava resni£na. V prvem koraku ugotovimo kateri lik izjava opisuje in katere lastnosti so v njej navedenev na²em primeru barva in velikost lika A. Razdelimo sestavljeno izjavo na enostavni izjavi: p:

Lik A ni bel in q: Lik A ni srednje velikosti. Enostavni izjavi sta povezani z ekskluzivno disjunkcijo, torej mora biti pravilna natanko ena izmed enostavnih izjav, da bo sestavljena izjava pravilna. S pomo£jo skice ugotovimo lastnostilikAje siv in srednje velikosti. LikAtorej ni bel, je pa srednje velik. Prvi del izjave je pravilen, drugi pa nepravilen.

Trditev je resni£na.

4.1. PRIMERI NALOG 31 2. Lik A je majhen in lik B je srednje velikosti.

Izjava je povezana z veznikom in, torej morata biti obe enostavni izjavi resni£ni. Ugotovili smo ºe, da je likAsrednje velikosti, zato ni potrebno ugotavljati ²e resni£nosti drugega dela. Izjava je neresni£na.

3. Lik D ni srednje velikosti in lik A ni siv.

Opazujemo lika D in A. Izjava pravi, da lik D ni srednje velikosti.

Pogledamo lik in ugotovimo, da izjava drºi. Lik D je namre£ velik.

Drugi del izjave pravi, da lik A ni siv. še v prvi izjavi smo ugotovili, da je lik A siv, torej ta del trditve ne drºi, izjava pa je neresni£na.

4. Ni res, da: Lik C ni bel ali je lik C srednje velikosti.

Izjava je zanikanje izjave: Lik C ni bel ali je lik C srednje velikosti.

Podobno kot v prej²nji nalogi, lahko ugotovimo resni£nost izjave brez zanikanja, nato pa na koncu le zaobrnemo vrednost in dobimo zanikano izjavo. Zahtevnej²emu re²evalcu pa lahko predstavimo re²evanje naloge z uporabo drugega de Morganovega zakona, ki zanikani izjavi priredi ekvivalentno izjavo: LikC je bel in likC ni srednje velikosti. Iz skice vidimo, da je lik C bel in srednje velikosti, torej je izjava neresni£na.

5. Ni res, da: ali lik C ni velik ali je lik B velik.

Izjava je zanikanje izjave: BodisiCni velik, bodisiBje velik. Opravka imamo z zanikanjem ekskluzivne disjunkcije. Pogledamo na skico in vi- dimo, da je likCsrednje velik, likBpa je majhen. Izjava brez zanikanja je resni£na, torej je zanikana izjava neresni£na.

6. Lik B ni trikotnik in lik B je velik.

Na skici pogledamo likB. Vidimo, da je ²tirikotnik in je majhen. Drugi del izjave je torej napa£en, saj ni res, da je lik B velik. Zaradi veznika in je izjava neresni£na.

7. Ni res, da: lik B je trikotnik, £e in samo £e lik D ni kvadrat.

Izjava je zanikanje ekvivalence. Opazujemo lika B in D. Ni res, da je likB trikotnik, kot trdimo v izjavi, vendar pa drºi, da likDni kvadrat.

Izjava brez zanikanja je neresni£na, torej je zanikana izjava resni£na.

8. Noben lik ni siv.

Izjava nam pove, da ne obstaja lik, ki bi bil siv. Naloge tak²nega tipa se lotimo tako, da sku²amo poiskati vsaj en lik, ki bi bil siv, saj potem

vemo, da je izjava neresni£na. Ker s skice vidimo, da je lik A siv, je izjava neresni£na.

9. Ni res, da: vsaj en lik je trikotnik.

Izjava je zanikanje eksisten£nega kvantikatorja. Poi²£emo njej ekvi- valentno izjavo: Noben lik ni trikotnik. S skice vidimo, da je izjava neresni£na, saj je likA trikotnik.

10. Ni res, da: vsaj en lik ni bel.

Ponovno smo zanikali eksisten£no izjavo. Nova ekvivalentna izjava bi lahko bila: Vsi liki so beli. Izjava je neresni£na, saj je lik A siv.

4.1.2 Nabor izjav kot pomo£ pri razvrstitvi elementov v mnoºice

Naloge naslednjega tipa vsebujejo veliko podatkov, zaradi £esar se pri re²eva- nju lahko hitro zmedemo. Re²evalec pri re²evanju neposredno ne potrebuje teoreti£ne podlage o matemati£ni logiki, mora pa znati povezovati dane izjave in ugotoviti, kaj ena pove o drugi.

Nalogo 4.3 so re²evali u£enci sedmega in osmega razreda na drºavnem tekmovanju 17. slovenskega tekmovanja v logiki, leta 2002. Naloga se nahaja v [2], na strani 79.

Naloga 4.3. ’tirje matemati£ni £asopisi (The Mathematical Gazette, Crux Mathematicorum, Mathematics Competitions, Teaching Children Math) izha- jajo v Avstraliji, ZDA, Veliki Britaniji in Kanadi. V njih so ²tirje matematiki (Gardiner, Hafner, Ljubenov, Battista) v razli£nih letih (1999, 2002, 2000, 2001) in razli£nih letnikih (6, 14, 26, 86)objavili svoje prispevke. Za vsak

£asopis ugotovi drºavo, kjer izhaja in matematika, leto in letnik, ko je iz²el matematikov prispevek, £e velja:

1. Gardinerjev prispevek je iz²el v Veliki Britaniji ali v Avstraliji.

2. ƒasopis Teaching Children Math ne izhaja v Avstraliji in v nalogi ni omenjen za l. 2002.

3. Naloga se ne nana²a na 6. ali 14. letnik £asopisa The Mathematical Gazette.

4. ƒasopis iz leta 2002 je iz²el v Kanadi ali Veliki Britaniji.

4.1. PRIMERI NALOG 33 5. V kanadskem £asopisu ni objavil prispevka ne Ljubenov ne Battista.

6. Crux Mathematicorum izhaja v Kanadi, omenjen pa je za l. 2000.

7. ƒasopis Mathematics Competitions ne izhaja v Veliki Britaniji in ni omenjen za l. 1999.

8. V nalogi nastopa 26. letnik £asopisa Crux Mathematicorum, ne nastopa pa 14. letnik £asopisa Teaching Children Math.

9. Ljubenov ni pisal v 6. letniku, Gardiner pa ni pisal v avstralskem £aso- pisu.

Postopek re²evanja

Nalogo je potrebno re²evati strukturirano. Med podanimi izjavami najprej poi²£emo tiste, ki nam nekaj to£no dolo£ijo. Nato pregledamo ²e ostale izjave in poi²£emo povezave med njimi. Na vsakem koraku razmisleka ugotovljena dejstva zapi²emo v tabelo. Ena izmed moºnosti je tudi, da v krog zapi²emo naslove £asopisov, imena drºav, imena matematikov, leta izdaje in letnike, nato pa jih med sabo povezujemo glede na to, kaj nam izjave povedo. Po- dobno lahko zapi²emo vse moºnosti v tabelo (kvadratno mreºo), nato pa glede na izjave dodajamo povezave. V obeh primerih lahko razberemo, kaj ºe vemo in katere povezave so ²e moºne. Dobljene podatke nato na koncu zapi²emo v tabelo.

• ’esta izjava to£no dolo£a dolo£eno povezavo: Crux Mathematicorum izhaja v Kanadi, omenjen pa je za l. 2000.

• Osma izjava nam pove, da se naloga nana²a na 26. letnik £asopisa Crux Mathematicorum.

• S pomo£jo tretje izjave vidimo, da se naloga ne nana²a na 6. ali 14.

letnik £asopisa The Mathematical Gazette. Zaradi prej²nje ugotovitve se ne nana²a niti na 26. letnik. Torej se nana²a na 86. letnik.

• Zaradi drugega dela osme izjave ugotovimo, da se naloga v £asopisu Teaching Children Math nana²a na 6. letnik, naloga v Mathematics Competitions pa na 14. letnik.

• Prva izjava pove, da je Gardiner pisal v reviji, ki izhaja v Avstraliji ali v Veliki Britaniji. Zaradi devete izjave ugotovimo, da Gardiner ni pisal v avstralskem £asopisu, torej je pisal v £asopisu iz Velike Britanije.

• S pomo£jo ²este in £etrte izjave ugotovimo, da je £asopis iz leta 2002 iz²el v Veliki Britaniji. Zaradi prej²nje ugotovitve tudi vemo, da je v tem £asopisu objavil Gardiner.

• Zaradi druge izjave in prej²njih ugotovitev vemo, da £asopis Teaching Children Math ne izhaja v Veliki Britaniji, Kanadi in Avstraliji. Torej izhaja v ZDA.

• Zaradi sedme izjave in doslej ugotovljenega, revija Mathematics Com- petitions izhaja v Avstraliji, posledi£no pa The Mathematical Gazette izhaja v Veliki Britaniji.

• Po zgornjem je torej Gardiner objavil v The Mathematical Gazette, pripadajo£i £lanek pa je iz²el leta 2002.

• Zaradi sedme izjave je torej £lanek iz Mathematics Competitions iz²el leta 2001, £lanek iz Teaching Children Math pa leta 1999.

• Zaradi pete izjave je v kandskem £asopisu pisal Hafner.

• Zaradi devete izjave je torej v reviji Teaching Children Math objavil Battista, v reviji Mathematics Competitions pa Ljubenov.

V tabeli 4.1 so podane re²itve.

£asopis drºava matematik leto izdaje letnik

The Mathematical Velika Britanija Gardiner 2002 86.

Gazette

Crux Kanada Hafner 2000 26.

Mathematicorum

Mathematics Avstralija Ljubenov 2001 14.

Competitions

Teaching Children ZDA Battista 1999 6.

Math

Tabela 4.1: Re²itev naloge 4.3.

4.1. PRIMERI NALOG 35

4.1.3 Matemati£ne uganke

Naslednji tip nalog, poleg znanja o matemati£ni logiki, zahteva tudi nekaj splo²nega matemati£nega znanja. Re²evalec mora biti pozoren na to, kaj mu izjave dejansko povedo in katera ²tevila je pametno izlo£iti ali uporabiti, da ne bo imel teºav v nadaljevanju.

Nalogo 4.4 so re²evali u£enci osmega in devetega razreda na drºavnem tekmovanju 25. slovenskega tekmovanja v logiki, leta 2010. Naloga se nahaja na [12].

Naloga 4.4. a) Bojan je za rojstni dan, 21.decemba, ºelel obiskati svojo pri- jateljico Gabrijelo. Ko je pri²el v vas, v kateri je stanovala, je ugotovil, da je pozabil, na kateri hi²ni ²tevilki stanuje. Spomnil se je le, da je ²tevilka med ²tevilkama 12 in 21. Mimoido£ega je zato vpra²al:

(a) Ali je hi²na ²tevilka deljiva z 2?

(b) Ali je hi²na ²tevilka deljiva s 3?

Ko je sli²al oba odgovora je rekel: ’e vedno ne vem, kje stanuje moja prijateljica. Na izbiro imam dve hi²ni ²tevilki. Povejte mi ²e, ali je v hi²ni

²tevilki ²tevilo 2? Ko mu je mimoido£i odgovoril na ²e zadnje vpra²anje, se je Bojan odpravil proti hi²i, za katero je bil prepri£an, da v njej ºivi njegova prijateljica.

• Na katere izmed hi²nih ²tevilk se Bojan zagotovo ni odpravil? Razloºi.

b) Ko je pozvonil, mu je vrata odprl popolni neznanec. Ko mu je Bojan razloºil, zakaj je tam, se je za£el gospod glasno smejati in dejal: Ta, ki vam je odgovarjal na vpra²anja, je najve£ji laºnivec v celi vasi. Nikoli ne govori resnice! Bojan je pomislil za trenutek, nato pa vzkliknil: Sedaj vem, kje ºivi moja prijateljica.

Odgovori na naslednja vpra²anja in podrobno razloºi potek re²evanja:

• Na kateri hi²ni ²tevilki je najprej pozvonil Bojan?

• Na kateri hi²ni ²tevilki ºivi Bojanova prijateljica?

Postopek re²evanja

Posvetimo se najprej prvemu delu naloge. Poglejmo vse moºne scenarije.

1. Mimoido£i odgovori obakrat z da: Zapi²imo ²tevila in pre£rtajmo tista, ki niso deljiva z 2 ali s 3: 12, 13, 14, 15, 16, 17, 18, 19, 20, 21.

Ostaneta nam dve ²tevili: 12 in 18. V eni izmed njiju je ²tevka 2. Ko mu je mimoido£i odgovoril na zadnje vpra²anje, je vedel, katera vrata so pravilna.

2. Mimoido£i odgovori obakrat z ne: Zapi²imo ²tevila in pre£rtajmo tista, ki so deljiva z 2 ali s 3: 12, 13, 14, 15, 16, 17, 18, 19, 20, 21.

Ker nam ostanejo tri ²tevila, ta scenarij ni moºen, saj je Bojan pred zadnjim vpra²anjem dejal, da ima na voljo le2 hi²ni ²tevilki.

3. Mimoido£i odgovori najprej z da potem z ne: Zapi²imo ²tevila in pre£rtajmo tista, ki niso deljiva z2ali pa so deljiva s 3: 12, 13, 14, 15, 16, 17, 18, 19, 20, 21. Ker nam ostanejo tri ²tevila, tudi ta scenarij ni moºen.

4. Mimoido£i odgovori najprej z ne, potem pa z da: Zapi²imo ²tevila in pre£rtajmo tista, ki so deljiva z 2 ali pa niso deljiva s 3: 12, 13,

14, 15, 16, 17, 18, 19, 20, 21. Ostaneta nam dve ²tevili: 15 in 21. V eni izmed njiju je ²tevka 2. Ko mu je mimoido£i odgovoril na zadnje vpra²anje, je torej vedel, katera vrata so pravilna.

Ugotovimo, da Bojan zagotovo ni potrkal na vrata ²tevilka 13,14,16,17,19 ali20, hkrati pa tudi vemo, da je mimoido£i na drugo vpra²anje odgovoril z da.

Sedaj pa si poglejmo ²e primer b). Ker je gospod dejal, da so bile vse iz- jave, ki jih je podal mimoido£i, laº, se zadeve nekoliko spremenijo.

1. ƒe je mimoido£i prvi£ odgovoril z da, iskano ²tevilo ni deljivo z2niti s3; tako so v igri ²tevila13,17in19. Potemtakem je moral mimoido£i na dodatno vpra²anje odgovoriti z da, vendar Bojan kljub temu ²e vedno ne bi mogel ugotoviti, na kateri hi²ni ²tevilki stanuje njegova prijateljica.

2. Torej je mimoido£i na prvo vpra²anje odgovoril z ne in zato je iskano

²tevilo deljivo z 2, ne pa tudi s 3. Dobimo kandidate 14,16 in 20. Le 20 vsebuje ²tevko 2, torej je moral mimoido£i na dodatno vpra²anje odgovoriti z ne, kar pomeni, da prijateljica v resnici stanuje na hi²ni

4.1. PRIMERI NALOG 37

²tevilki20. Ker mu je torej mimoido£i dejal, da v hi²ni ²tevilki ni ²tevke 2je Bojan pozvonil na vratih ²tevilka 15.

4.1.4 Okolje z dolo£enimi pravili

Gre za priljubljene naloge, ki se pojavljajo v raznih ugankah. Zaradi njih je matemati£na logika postala zanimiva ²ir²emu krogu, predvsem po zaslugi Smullyana [7], ki je v svojih knjigah bralca postavil v okolje z dolo£enimi pravili in podal kup ugank, s katerimi se je bilo potrebno spopasti. Obi£ajno imamo opravka z dvema tipoma ljuditistimi, ki laºejo, in tistimi, ki govorijo resnico. Ob£asno pa se jim pridruºi ²e tretjitak, ki izmeni£no govori resnico ali laº. Re²evalec mora dobro poznati pravila izjavne logike, natan£no mora preu£iti pravila danega okolja, ravno tako pa mora biti pozoren, da preveri vse moºne scenarije. Na za£etku namre£ ne vemo, kdo nam govori resnico in kdo laº, to ugotovimo ²ele po pogovoru z mimoido£imi.

Nalogo 4.5 so re²evali dijaki prvega in drugega letnika na drºavnem tek- movanju 17. slovenskega tekmovanja v logiki, leta 2002. Naloga se nahaja v [2], na strani 81.

Naloga 4.5. Na otoku vitezov, oprod in normalneºev vitezi vedno govorijo resnico, oprode vedno neresnico, normalneºi pa v£asih resnico in v£asih ne- resnico. Tokrat imamo opravka z doma£ini A, B, C in D. Med njimi je vsaj en vsake vrste. Neko£ so dejali:

A: B ni vitez in vsaj eden od naju je oproda.

B: ƒe sem vitez, potem je A oproda.

C: ƒe sem vitez, potem je A oproda.

D: Sem normalneº.

Logik, ki se je trenutno mudil na otoku, je sli²al ta razgovor in je nato vpra²al B-ja, ali je C Vitez. B je odgovoril da ali ne in logik je ugotovil, kaj je vsak izmed njih.

Kaj so doma£ini?

Postopek re²evanja

Najprej natan£no pogledamo, kak²ni so pogoji in kaj nam izjave dejansko povedo. Vemo, da je med njimi vsaj en vsake vrste, torej je vsaj en normalneº,

vsaj en oproda in vsaj en vitez. Vidimo, da sta izjavi B in C enaki in ker poznamo pravila implikacije, vemo tudi, da sta ti izjavi resni£ni, saj bi morala biti v nasprotnem primeru izjava Sem vitez pravilna, torej bi bila B in C viteza, kar pa ne gre, saj vitezi ne laºejo (pridemo do protislovja). To seveda tudi pomeni, da noben izmed B inC ni oproda.

1. Pokaºimo najprej, da je vsaj eden izmed B inC vitez. V nasprotnem primeru (ponovno uporabimo dokaz s protislovjem) mora biti vitez vsaj eden izmedAinD. KerD o£itno ni vitez (vitez namre£ ne bi lagal, da je normalneº), je tedaj vitez A. Potem pa je B oproda, kar ºe vemo, da ni res. Potemtakem je res vsaj eden od B in C vitez, posledi£no pa je izjava ƒe sem vitez, potem je A oproda resni£na. Ker je oseba, ki to govori, vitez, se to zgodi le, £e je A oproda. Torej je A zagotovo oproda.

2. Ker torejAlaºe, izjava Vsaj eden od naju zB je oproda pa je pravilna, mora biti izjava B ni vitez neresni£na in zato je B vitez.

3. Ker potrebujemo ²e normalneºa, je to vsaj eden izmed doma£inov C in D. Brez upo²tevanja dodatnega odgovora B-ja, je torej C vitez ali normalneº,D pa oproda ali normalneº.

4. Denimo sedaj, da je B odgovoril z ne. Ker ºe vemo, da je B vitez, je tedaj C normalneº, D pa je ²e vedno lahko oproda ali normalneº.

V tem primeru torej ne moremo ugotoviti, kaj je D. Zato je moral B odgovoriti z da, posledi£no pa je C vitez, Dpa je normalneº.

Pravilen odgovor je torej, da jeA oproda, B vitez, C vitez in D normalneº.

Omenili smo, da je Smullyan v svojih knjigah izoblikoval dolo£eno okolje, nato pa preko ugank bralcu predstavil mimoido£e. Tako nam predstavi otok vitezov in oprod, otok spra²evalcev, otok sanj, pa tudi medplanetarno zme-

²njavo. Kon£ni rezultat je vedno istinekateri akterji govorijo resnico, drugi pa neresnico. Pri tak²nih nalogah je zelo pomembno, da kot bralec natan£no razumemo pravila podanega okolja in znamo nato izjave in vpra²anja obrav- navati tako, da bomo vedeli, kdo je na² sogovornik. Re²evalec mora svoje razmi²ljanje popolnoma prilagodi danem okolju. Lahko se namre£ zgodi, da so na²i mimoido£i obi£ajni ljudje, vendar pa imajo neko lastnost, ki lo£i laºnivca od resnicoljuba. Podajmo nekaj uporabnih nasvetov iz [6]:

1. Pri re²evanju si pomagajmo z analizo primerovzapis scenarijev.

4.1. PRIMERI NALOG 39 2. Laºnivec ne bo nikoli trdil, da je laºnivec.

3. Resnicoljub ne bo nikoli trdil, da je laºnivec.

4. Kadar si dve izjavi nasprotujeta, je ena zagotovo laº.

5. Resnicoljub ne more podati izjav, ki se med sabo izklju£ujejo.

6. Kadar nas nekaj zanima in ne poznamo mimoido£ega, vpra²amo: ali ..., £e in samo £e vi govorite resnico? ali Ali oseba va²ega tipa trdi, da ...? Ne glede na to, ali mimoido£i laºe ali govori resnico, bo odgovor da potrdil na²e vpra²anje, odgovor ne pa zavrnil.

7. Kadar imamo podano vpra²anje, odgovora pa ne, preverimo obe mo- ºnosti. ƒe vemo, da smo, ko smo dobili odgovor na neko vpra²anje, vedeli, ali je izjava resnica ali laº, potem je pravilna tista moºnost, ki nam da to£en odgovor.