1.1 Resni£nostne tabele

Univerza v Ljubljani Pedago²ka fakulteta

Oddelek za matematiko in ra£unalni²tvo Katedra za algebro in analizo

Tadej Star£i£

NALOGE IZ LOGIKE IN MNOšIC Z RE’ITVAMI

U£no gradivo

Ljubljana, 2015

Predgovor

Razumevanje matemati£nih teorij se lahko utrdi in poglobi le tako, da se matemati£ne koncepte in tehnike dokazovanja preizkusi z re²evanjem nalog.

Pri£ujo£a zbirka vsebuje naloge z re²itvami oziroma nasveti za re²e- vanje. Obsega osnove s podro£ja logike, natan£neje izjavnega ra£una, ter osnove teorije mnoºic. Teme, povezane z izjavnim ra£unom so ekvivalenca izjav, kvantikatorji, logi£no sklepanje in metode dokazovanja. Teorija mno- ºic pa se, poleg klasi£nih osnov o mnoºicah, dotakne ²e relacij, funkcij in mo£i mnoºic. To so temeljni matemati£ni koncepti, ki jih je nujno razumeti na vseh podro£jih matematike. Naloge so samostojne in se praviloma ne sklicujejo na ostale naloge. Na koncu so zbrane ²e re²itve, ve£inoma dokazi in uporabni nasveti, veliko nalog pa je re²enih tudi v celoti.

Izbor nalog je potekal od ²tudijskega leta 2011/12 do sedaj, v tem £asu namre£ na Pedago²ki fakulteti Univerze v Ljubljani med drugim vodim vaje iz predmeta Logika in mnoºice. V veliki meri so to naloge z vaj, doma£ih na- log, izpitov in kolokvijev pri omenjenem predmetu. Vrstni red nalog, njihova teºavnost in struktura zato naravno sledijo toku premi²ljevanja ²tudenta.

Zbirka je tako ²e posebej namenjena ²tudentom Pedago²ke fakultete, ²tudij- skega programa dvopredmetnega u£itelja matematike, ki logiko in mnoºice poslu²ajo v prvem letniku ²tudija. Gotovo pa bo prav pri²la tudi ²tudentom, ki poslu²ajo sorodna predavanja na drugih fakultetah. Njen osnovni namen je pomo£ pri ²tudiju, pravi pomen bo zato dobila le v povezavi s celotnim

²tudijskim procesom.

Pa veliko veselja pri re²evanju!

Ljubljana, april 2015 dr. Tadej Star£i£

Kazalo

1 Logika 4

1.1 Resni£nostne tabele . . . 4

1.2 Ekvivalenca izjav . . . 6

1.3 Kvantikatorji . . . 9

1.4 Logi£no sklepanje . . . 11

1.5 Metode dokazovanja . . . 13

2 Mnoºice 17 2.1 Mnoºice in podmnoºice . . . 17

2.2 Unije in preseki . . . 19

2.3 Poten£na mnoºica in kartezi£ni produkt . . . 21

2.4 Relacije . . . 23

2.5 Funkcije in mo£ mnoºic . . . 25

3 Re²itve 28 3.1 Logika . . . 28

3.1.1 Resni£nostne tabele . . . 28

3.1.2 Ekvivalenca izjav . . . 29

3.1.3 Kvantikatorji . . . 31

3.1.4 Logi£no sklepanje . . . 33

3.1.5 Metode dokazovanja . . . 35

3.2 Mnoºice . . . 39

3.2.1 Mnoºice in podmnoºice . . . 39

3.2.2 Unije in preseki . . . 41

3.2.3 Poten£na mnoºica in kartezi£ni produkt . . . 43

3.2.4 Relacije . . . 45

3.2.5 Funkcije in mo£ mnoºic . . . 47

1 Logika

1.1 Resni£nostne tabele

1. Naj bodop,q inrenostavne izjave, ki sestavljajo naslednje sestavljene izjave:

(a) (p∨p)⇔p,

(b) (¬p∨ ¬q)⇒ ¬(p∨q), (c) ¬(p⇒q)⇔(p∧ ¬q), (d) (p⇒(¬r∨q))∧r,

(e) (p∧(q ⇒r))⇔ ¬p∨(¬r∧q), (f) (p⇒(q∨ ¬r))⇔(r∧ ¬p), (g) (¬p∧(r ⇒q))⇔(r∨(p⇒ ¬q)), (h) (¬q∨(r⇒p))⇒(r∧(p⇔q)),

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

• Za zgoraj podane sestavljene izjave zapi²i resni£nostne tabele.

Ugotovi, katere izmed danih izjav so tavtologije, katere protislovja in katere so fakti£ne izjave. Razmisli, katera od izjav je resni£na in katera neresni£na, £e je presni£na, q inr pa neresni£ni.

• Za vsako od izjav p, q, r in p ⇒ (q∨r) ugotovi, ali je resni£na oziroma neresni£na, £e je dana sestavljena izjava resni£na?

2. Na nekem otoku ºivijo resnicoljubni vitezi in laºnivi oprode. Izjava doma£ina je torej resni£na natanko tedaj, ko je ta vitez, ter neresni£na natanko tedaj, ko je oproda. Naslednje probleme zapi²i v jeziku izjavne logike in s pomo£jo resni£nostne tabele dolo£i tipe doma£inov. Na otoku sre£amo

(a) dva doma£ina in eden od njiju izjavi, da je vsaj eden od njiju oproda.

(b) dva doma£ina in eden od njiju izjavi: Ce sem jaz vitez, je on oproda."

(c) dva doma£ina in eden od njiju izjavi, da sta bodisi oba viteza bodisi oba oprodi.

(d) tri doma£ine, A, B in C. Najprej doma£in A izjavi: Ce je C oproda, potem je tudi B oproda.' B izjavi: C je vitez ali A je vitez.

(e) tri doma£ine, A, B in C. Najprej doma£in A izjavi, da sta B in C viteza. Nato paB pravi: A je vitez in C je oproda.

3. Na dvori²£u so Jani, Miha in Luka igrali nogomet in eden izmed njih je dal gol. Po koncu igranja so rekli:

Janez: Miha je dal gol.

Miha: Janez je dal gol.

Luka: Jaz nisem dal gola.

Kdo je dal gol, £e sta vsaj dva izmed njih lagala.

1.2 Ekvivalenca izjav

1. Dani so pari izjav:

(a) I ≡ p∨q, J ≡ q ⇔(p∨q),

(b) I ≡ p∧((q ⇒r)∨r), J ≡ (p∧ ¬q)∨r, (c) I ≡ (r⇒ ¬p)∧ ¬q, J ≡ r ⇒(p∨q),

(d) I ≡ ¬q⇒((r⇔q)∧p), J ≡ (¬q⇒r)⇔(q∧p), (e) I ≡ (r∧(p∨ ¬q))⇒ ¬p, J ≡ r⇔(p⇒ ¬q), (f) I ≡ (¬p∨s)⇒(q∧r), J ≡ (p∨ ¬r)∧q,

• Ugotovi, ali sta izjaviI inJ ekvivalentni, ter ju zapi²i v normalni disjunktivni obliki (NDO).

• Ali je mo£ iz resni£nosti izjavI in J sklepati na resni£nost kate- rekoli od izjav p, q, r, p∨q inp⇔(q∧r).

2. Dokaºi, da so spodaj podani pari ekvivalentnih izjav, noben par ekvi- valentnih izjav pa ni ekvivalenten nobenemu drugemu paru:

(a) (A⇔(C∨B))∧C, A∧C,

(b) (A⇒C)∨(¬B ⇒C), (A∨ ¬B)⇒C, (c) (¬A∨B)⇒C, (¬A⇒C)⇒(B ⇒C), (d) (A∧B)∨(¬B∧ ¬C), (A∧B)⇔(B∨C),

(e) (A⇒B)∧(C∨B), (¬A∧C)∨B, (f) A⇒B, A⇒((B∧C)∨B),

(g) (A∧(B ⇒C))∨C, (A∧ ¬B)∨C, (h) A∨B∨C, (¬A⇒B)∨C∨A,

(i) A∧(¬B∨C), (A∧ ¬B)∨(A∧C). 3. Dani so pari izjav:

(a) I ≡ (ƒe sem pameten, potem nisem sre£en), ali sem pameten.

J ≡ ƒe sem pameten, (potem sem pameten in sre£en).

(b) I ≡ Sem pameten in (sem sre£en ali bogat).

J ≡ ƒe sem pameten in nesre£en, potem sem pameten in reveº.

(c) I ≡ ƒe sem pameten, potem sem sre£en in nisem bogat.

J ≡(ƒe sem pameten, potem nisem bogat) in (£e sem pameten, potem sem sre£en).

(d) I ≡ ƒe sem neumen ali nesre£en, potem sem nesre£en in reveº.

J ≡ (ƒe sem bogat natanko takrat, ko nisem pameten), (potem nisem bogat in sem sre£en.)

• Zapi²i pripadajo£e enostavne izjave, nato pa z njimi in s pomo£jo logi£nih veznikov zapi²i izjavi I inJ.

• Ugotovi, ali sta izjaviI inJ ekvivalentni, ter ju zapi²i v normalni disjunktivni obliki (NDO).

• Ali je mo£ iz resni£nosti izjavI in J sklepati na resni£nost kate- rekoli od izjav: P ≡Sre£en sem natanko tedaj, ko sem bogat. ter Q≡ Sem sre£en ali sem pameten.

4. Dane so izjave

(a) Naravno ²tevilo n je sodo in ni deljivo s3. (b) ¬(p∨ ¬q)∧(¬r ⇒ ¬p).

(c) (p⇒(q∨ ¬r))⇔(r∧ ¬p). (d) (¬q∨(r⇒p))⇒(r∧(p⇔q)),

(e) (ƒe grem v kino natanko takrat, ko se ne u£im Logike), (potem ne grem v kino in se u£im Logiko).

• S pomo£jo znanih ekvivalenc danim izjavam poi²£i ekvivalentne izjave, ki so sestavljene le iz negacij enostavnih izjav ter logi£nih veznikov ∧ in∨.

• Dane izjave podaj v normalni disjunktivni obliki (NDO).

• Zanikaj dane izjave, ter jih s pomo£jo znanih ekvivalenc zapi²i v

£imbolj enostavni obliki, t.j. poi²£i ekvivalentne izjave, ki so sesta- vljene le iz negacij enostavnih izjav ter logi£nih veznikov. (Nasvet:

Lahko zapi²e² kar NDO negacije.

5. Kako lahko standardne logi£ne operacije izrazimo s pomo£jo veznika, ki je deniran na naslednji na£in:

(a) Izjavap↑q (Sheerjev veznik) je resni£na natanko tedaj, ko vsaj ena izmed izjavp inq ni resni£na.

(b) Izjava p ↓ q (Lukasiewicz-Pierceov veznik) je resni£na natanko tedaj, ko sta obe izjavi p inq neresni£ni.

6. Na otoku resnicoljubnih vitezov in laºnivih oprod sre£amo doma£ina.

Kak²no vpra²anje mu moramo zastaviti, da bomo dobili odgovor 'da' natanko tedaj, ko bo dan ponedeljek? Kaj pa ga moramo vpra²ati, da bomo izvedeli, ali govori resnico?

1.3 Kvantikatorji

1. Naslednje izjave zapi²i v matemati£ni obliki z uporabo logi£nih veznikov in kvantikatorjev, ter jih tudi zanikaj:

(a) Vsi ljudje, ki ne nosijo o£al, nosijo kape.

(b) Za vsako bolezen raste roºica na tem svetu, ki jo pozdravi.

(c) Za vsaj eno ²tevilo a iz mnoºice A velja, da jea² v mnoºiciB. (d) Za vsako celo ²tevilo velja: £e je to ²tevilo deljivo s 6, potem je

deljivo tudi z 2in 3.

(e) Za vsako racionalno ²tevilo obstaja naravno ²tevilo, ki je ve£je od tega ²tevila.

(f) Za vsakx∈R obstaja tak y∈R, da je x= 2y.

(g) Za neko ²tevilo m iz mnoºice M ⊂ N velja: £e je ²tevilo m naj- manj²e ²tevilo iz mnoºice M, potem je m delitelj vsakega ²tevila iz mnoºice M.

(h) ƒe ima1lasnostP, ter £e iman+ 1 lastnostP, ko ima nlastnost P, potem imajo lastnostP vsa naravna ²tevila.

(i) Vsako ²tevilo iz mnoºice A ⊂ N, ki je ve£je od 10, je popolni kvadrat nekega ²tevila iz mnoºice A.

(j) Za vsako celo ²tevilo velja: £e je kub tega ²tevila deljiv z2, potem je tudi to ²tevilo deljivo z2,

(k) Za vsako naravno ²tevilo n velja: ²tevilo n da pri deljenju s 3 ostanek 1 natanko tedaj, ko da tudi njegov kub n³ pri deljenju s 3ostanek 1.

(l) Za vsak realen >0 obstaja tako naravno ²tevilo N, da za vsako naravno ²tevilon, ki je ve£je od N, velja ¹_n < .

2. Z besedami £imbolj enostavno pojasni dane izjave in njihove negacije:

(a) ∀x: (∃y: (x= 2y)), kjer so domena pogovora realna ²tevila, (b) ∃n: (∃m: (n=m²)), kjer so domena pogovora naravna ²tevila,

(c) ∀x: (∃y: (y > x)), kjer so domena pogovora realna ²tevila, (d) ∀f: (∃g: (g ≥f)), kjer so domena pogovora pozitivne funkcije,

(e) ∀y∀x: (xy= 0 ⇒x= 0∨y = 0), kjer x, y ∈R,

(f) ∃n: (∀m: (n 6= m³) ∧ ∀k: (n 6= k²)), kjer so domena pogovora naravna ²tevila,

(g) ∃n: (∃m: (n = m²)∨ ∀k: (n 6= k³)), kjer so domena pogovora na- ravna ²tevila,

(h) ∃n: (∃m: (n = m²)∧ ∀k: (n 6= k³)), kjer so domena pogovora na- ravna ²tevila,

(i) ∃n: ((∃r: (n = 2r)) ∨ (∀s: (n 6= 3s))), kjer so domena pogovora cela ²tevila,

(j) ∃n: (∀m: (n 6= 3m + 1) ⇔ ∃r: (n³ = 4r + 1)), kjer so domena pogovora cela ²tevila,

(k) ∀m: (∀N: (∃n: ((n > N) ∧ (_n¹2 < _m¹)))), kjer so domena pogovora naravna ²tevila.

(l) ∀A: (∃B: ((A ⊂ B ∧ A 6= B) ⇒ P(A) 6= B), kjer so domena pogovora podmnoºice mnoºice naravnih ²tevil.

Ali je katera od danih izjav resni£na?

1.4 Logi£no sklepanje

1. Za dani par izjav P in Q ugotovi, katera od izjav je potreben oziroma zadosten pogoj (ali oboje):

(a) P: 26 deli naravno ²tevilon. Q: 13 deli naravno ²tevilon. (b) P: Za realni ²tevili a inb veljaab >0.

Q: Realni ²tevili a inb sta pozitivni.

(c) P: n je liho ²tevilo. Q: n³ je liho ²tevilo.

(d) P: Realno ²tevilox re²i neenakost x² < x. Q: Realno ²tevilox je manj²e od 1.

2. Ugotovi, zakaj je kon£ni sklep logi£na posledica predhodnih predpo- stavk. Zapi²i ²e formalni dokaz v jeziku simbolne logike in vsak korak utemelji s pravili sklepanja.

(a) P: a > b ⇒a >2, Q: a > b. Sklep R: a >2. (b) P: a > b ⇒a >2, Q: a ≤2. Sklep R: a≤b.

(c) P: x >0⇒y >0,Q: y >0⇒z <0. SklepR: x >0⇒z <0. (d) P: Ne more² biti hkrati sre£en in bogat. Q: Sem sre£en.

Sklep R: Torej nisem bogat.

3. Razloºi posamezne korake v danih dokazih oziroma dokaze dopolni:

1.p⇒ ¬q pr

2.¬q ⇒ ¬r pr 3.(r ⇒ ¬p)⇒t pr

4. . . . HS(1,2) 5.r ⇒ ¬p . . .

6. MP(3,5)

1.p∧ ¬p pr 2.p . . . 3.¬p . . . 4.¬p∨q . . . 5.p⇒q . . .

6. . . . M P(2,5) ,

1.(¬q∨r)⇒(¬p∧q) pr 2.(q∧ ¬r)⇒s pr

3.¬s pr

4.¬(q∧ ¬r) . . .

5.¬q∨r . . .

6.¬p∧q . . .

7.q . . .

1.(q∨r)⇒(p∧ ¬q) predp 2.(¬q∧ ¬r)⇒s predp

3.¬s predp

4. . . . M T(2,3)

5.q∨r . . .

6.p∧ ¬q . . .

7. . . .

8.r . . .

4. Naj bodo resni£ne izjave ¬q ⇒ r, p∨q in r ⇒ ¬p. Ali smemo odtod kaj sklepati o resni£nosti oziroma neresni£nosti katere od izjav r ⇒ q in¬p∧q? ƒe je odgovor pritrdilen, zapi²i tudi formalni dokaz s pravili sklepanja.

5. Dane so sestavljene izjave:

P ≡ ƒe je ºival na sliki plazilec ali sesalec, diha s plju£i in ne zna leteti.

Q≡ šival na sliki je plazilec.

R ≡ šival na sliki ne zna leteti.

Iz trditev P in Q izpelji trditve R. Zapi²i tudi formalen dokaz, kjer natan£no pojasni svoje sklepe.

6. Dane so sestavljene izjave:

P ≡ ƒe bi bil lep ali pameten, potem bi bil sre£en in bogat.

Q≡ Nisem bogat.

R ≡ Nisem niti lep niti pameten.

(a) Zapi²i pripadajo£e enostavne izjave, nato pa z njimi in s pomo£jo logi£nih veznikov zapi²i izjave P,Q in R.

(b) Utemelji, zakaj lahko iz resni£nosti trditev P in Q sklepa² na re- sni£nost trditveR. Zapi²i tudi formalen dokaz in natan£no pojasni svoje sklepe.

1.5 Metode dokazovanja

1. Najprej direktno in nato z analizo primerov dokaºite naslednje trditve:

(a) ’tevilo n³−n je deljivo s 3za vsako naravno ²tevilo n. (b) Za vsako naravno ²tevilon je izraz n²−n+ 5 liho ²tevilo.

(c) Naj bostaminn naravni ²tevili. ƒe je ²tevilo3m+nliho, potem je ²tevilo m² +n² tudi liho.

2. S protislovjem oziroma indirektno (t.j. namesto trditve A⇒B dokaºi

¬B ⇒ ¬A.) dokaºi naslednje trditve:

(a) ƒe je ²teviloa re²itev ena£be a²−7a+ 12 = 0, potem je a 6= 0. (b) ƒe je vsota kubov dveh naravnih ²tevil liha, potem je eno od ²tevil

liho in drugo sodo.

(c) V decimalnem zapisu ²tevila √

2 se vsaj ena (dve) izmed ²tevk pojavi neskon£nokrat.

(d) ƒe je2ⁿ+ 1pra²tevilo za naravo ²tevilon ≥2, potem jenpotenca

²tevila 2.

(e) Pra²tevil je neskon£no mnogo.

3. Z indukcijo dokaºi naslednje trditve:

(a) Za vsako naravno ²tevilon velja1³+ 2³+ 3³+· · ·+n³ = (ⁿ⁽ⁿ⁺¹⁾₂ )². (b) Za vsako naravno ²tevilon je izraz 5ⁿ−4n−1deljiv s 16.

(c) Izraz ⁿ₃³ +ⁿ₂² +ⁿ₆ je celo ²tevilo za vsako naravno ²tevilon. (d) Vsota notranjih kotov konveksnega n-kotnika za n ≥ 3 je enaka

(n−2)π.

4. Naj bodop, q in r naslednje enostavne izjave:

b ≡ Sem bogat. p≡ Sem pameten. s≡ Sem sre£en.

Dane so ²e sestavljene izjave:

P ≡ ƒe sem pameten, potem sem nesre£en in bogat.

Q≡ ƒe nisem pameten, potem sem sre£en.

R ≡ Sem sre£en ali nisem bogat.

(a) S pomo£jo izjav b, pin s, ter logi£nih veznikov zapi²i P, Q inR?

(b) Ali je mo£ iz resni£nosti izjav P, Q in R sklepati o resni£nost oziroma neresni£nosti izjav p in s. ƒe je odgovor za katero od izjav 'da', potem svojo trditev utemelji ²e s formalnim dokazom.

5. Dane so izjave:

P ≡ ƒe se u£im ali delam doma£e naloge, potem (naredim izpit in grem v kino).

Q≡ Naredim izpit in (ne grem v kino ali se u£im).

R ≡ U£im se natanko tedaj, ko (naredim izpit in grem v kino).

(a) Zapi²i pripadajo£e enostavne izjave, nato pa z njimi in s pomo£jo logi£nih veznikov zapi²i izjave P,Q in R.

(b) Ali je mo£ iz resni£nosti izjavP inQsklepati na resni£nosti izjave Roziroma izjave Delam doma£e naloge.? ƒe je odgovor za katero od izjav pritrdilen, potem svojo trditev utemelji ²e s formalnim dokazom s pravili sklepanja.

6. Dane so izjave:

P ≡ ƒe nisem bogat, potem sem pameten.

Q≡ ƒe sem nesre£en ali pameten, potem sem mlad.

R ≡ ƒe sem mlad, potem sem ²tudent.

S ≡ ƒe sem bogat, potem sem nesre£en.

(a) Zapi²i pripadajo£e enostavne izjave, nato pa z njimi in s pomo£jo logi£nih veznikov zapi²i izjave P,Q, R in S.

(b) Ali je mo£ iz resni£nosti izjavP,Q, R inS sklepati na resni£nost katerekoli od izjav: Sem ²tudent. ter Sem bogat..

7. Dane so izjave:

(a) P ≡ ƒe mi²i ne ple²ejo, potem je ma£ka doma.

Q≡ Ma£ke ni doma ali mi²i ple²ejo.

R≡ ƒe so mi²i doma, potem ple²ejo.

S ≡ Mi²i ple²ejo.

(b) P ≡ ƒe se ne u£im, potem (ne naredim izpita in ne grem na morje).

Q≡ ƒe se u£im, potem (naredim izpit in grem na morje).

R≡ ƒe se ne u£im, potem ne znam.

S ≡ ƒe se u£im, potem (znam ali grem na morje).

(c) P ≡ ƒe govorim resnico, potem sem po²ten ali nesre£en.

Q≡ ƒe sem bogat, potem sem sre£en in nepo²ten.

R≡ Govorim resnico ali sem reven.

S ≡ Nisem bogat.

• Zapi²i pripadajo£e enostavne izjave, nato pa z njimi in s pomo£jo logi£nih veznikov zapi²i izjave P,Q, R in S.

• Dokaºi, da je iz resni£nosti izjav P, Q in R mo£ sklepati na re- sni£nost izjave S. Zapi²i ²e formalnim dokaz s pomo£jo pravil sklepanja.

8. Razloºi posamezne korake v danih dokazih ali dokaze dopolni:

1. p⇒(q∧r) predp 2. (q∨s)⇒u predp

3. u⇒ ¬t predp

4. (q∨s)⇒ ¬t . . . 5.1. . . . 5.2. q∧r . . .

5.3. q . . .

5.5. q∨s . . .

5.6. ¬t . . .

5. p⇒ ¬t PS(5.1−5.6) 6. t⇒ ¬p . . .

,

1.p⇒(q∧r) predp 2.¬p⇒(¬q∧ ¬r) predp

3.¬p⇒ ¬s predp

4.1. . . . predp P S 4.2.q∧r . . .

4.3.r . . .

4.4.r∨ ¬s . . . 4.p⇒r∨ ¬s . . .

5.s⇒p . . .

6. . . . HS(4,5)

1.(p∨q)⇒(s⇒ ¬q) predp 2.(¬r∨p)∧s predp

3.¬q ⇒ ¬p predp

4.¬r∨p . . .

5.1. r . . .

5.2. . . . DS(4,5.1) 5.3. p∨q . . .

5.4. s⇒ ¬q . . .

5.5. . . . HS(3,5.4)

5.6. s . . .

5.7.¬p . . .

5.8.¬p∧p . . .

5.9. 0 . . .

5. . . .

1.(¬p⇒q) predp 2.(¬s∧q)⇒r predp 3. p∨ ¬r predp 4.¬r⇒ ¬s predp 5.1.¬p . . .

5.2. . . . DS(3,5.1) 5.3.¬(¬s∧q) . . .

5.4. s∨ ¬q . . .

5.5. . . . MP(4,5.2) 5.6.¬q . . .

5.7. . . . 5.8.¬q∧q . . .

5.9.0 . . .

5. . . .

1.¬p∨q predp 2.(¬s∨q)⇒t predp 3.1.¬t . . . 3.2.¬(¬s∨q) . . . 3.3.s∧ ¬q . . . 3.4.¬q . . .

3.5. . . . DS(1.,3.4.) 3.¬t ⇒ ¬p . . .

1. p⇒(q∨r) predp

2.¬r predp

3.1. p . . . 3.2. q∨r . . . 3.3. q . . . 3. p⇒q . . .

,

1. p∨(r ⇒s) predp

2. p ⇐⇒ s predp

3.1.¬p∧r . . .

3.2.¬p . . .

3.3. . . . DS(1,3.2) 3.4.(p⇒s)∧(s⇒p) . . .

3.5. s⇒p . . .

3.6. r⇒p . . .

3.7. . . . MT(3.2,3.6)

3.8. . . .

3.9. . . .

3.10. 0 . . .

3.¬(¬p∧r) . . .

4. p∨ ¬r . . .

,

9. V celoti dokaºi izjavi ¬t ⇒ ¬p in p ⇒ (s ∧ ¬q), pri £emer ²tevilo korakov dokaza ni vnaprej predpisano:

1.¬p∨q predp 2.(¬s∨q)⇒t predp . . .

. . .

∗.¬t⇒ ¬p

1.¬r∧s predp

2.(p∨ ¬q)⇒(¬q∨r) predp . . .

. . .

∗. p⇒(s∧ ¬q)

10. Dane so izjave ¬q ⇒ r, r ⇒ ¬q in p∨q. Ali lahko iz danih izjav izpeljemo izjaveq inr∧p? ƒe je odgovor za katero od izjav pritrdilen, zapi²i tudi formalen dokaz s pravili sklepanja.

11. Naj bodo p, q, r in s enostavne izjave, ki sestavljajo izjave:

(a) I ≡ (r⇒ ¬p)∧ ¬q, J ≡ r ⇒(p∨q) K ≡ ¬q∧ ¬r. (b) I ≡ (¬p∨s)⇒(q∧r), J ≡ (p∨¬r)∧q, K ≡ ¬p ⇐⇒ (r∧q), Ali je mo£ iz resni£nosti izjav I in J sklepati na resni£nost izjave K.

2 Mnoºice

2.1 Mnoºice in podmnoºice

1. Naslednje mnoºice zapi²i eksplicitno, t.j. na²tej njihove elemente:

(a) {2n−3|n∈Z}, (b) {m∈Q|2m−3∈Z},

(c) {x∈R|x²−10x+ 16<0}, (d) {n∈N|n >4⇒3n+ 1 ≤20}.

2. Z matemati£nimi in logi£nimi simboli zapi²i naslednje mnoºice:

(a) vsa pozitivna realna ²tevila, ki so koreni naravnega ²tevila.

(b) Naravna ²tevila, ki so ali deljiva s4 ali pa so njihovi kubi manj²i od 30.

(c) vsa naravna ²tevila, ki niso deljiva s 4ali pa so popolni kvadrati.

3. Ali je katera izmed danih mnoºic podmnoºica druge, sta morda kateri enaki? (Svoj odgovor natan£no utemelji.)

(a) A={2n−1|n ∈Z}, B ={n∈Z| ∃m∈Z:n= (2m+1)³}. (b) A={(2n−1)³ |n ∈Z}, B ={m∈Q|(2m+ 1)³ ∈Z},

C ={(2s+ 3)³ |s ∈Z}.

(c) A={(2n)²−1|n ∈N}, B ={4n+ 3|n ∈N∪ {0}}.

(d) A={n∈N|ostanek ²tevila n pri deljenju s 3 je 1}, B ={n² ∈N|ostanek ²tevila n pri deljenju s 3 je 2}. (e) A={x³ |x∈Q}, B ={x∈R|x³ ∈Q}..

(f) A={x² |x∈Q}, B ={x∈R|x² ∈Q}.

(g) A={ⁿ₂ + 1|n ∈Z}, B ={m∈Z| ^m₂ + 1∈Z}, C ={k ∈Q|2k∈Z}.

4. Naslednjo izjavo o podmnoºicah mnoºice naravnih ²tevil zapi²i v ma- temati£ni obliki, t.j. z uporabo logi£nih veznikov in kvantikatorjev, nato pa izjavo ²e dokaºi:

Za vsako mnoºico A velja: ƒe A vsebuje kak²no podmnoºico B, tako da je A razli£na od B, potem A ni prazna mnoºica.

5. Dana je izjava o podmnoºicah mnoºice celih ²tevil:

∀A:

(∃B: (B ∈ P(A)∧B 6=∅))⇒A6=∅

(a) Na £im bolj enostaven na£in dano izjavo zapi²i z besedami, nato pa izjavo tudi utemelji.

(b) V £im bolj enostavni matemati£ni obliki, t.j. z uporabo logi£nih veznikov in kvantikatorjev, podaj negacijo dane izjave.

6. Pokaºi naslednje trditve:

(a) ∅ 6={∅},

(b) ƒe jeA⊆ ∅, potem velja A=∅. 7. Dani sta mnoºici

(a) A={∅,1,{1}},

(b) A={∅,1,{1,∅},{{1}}}.

Za vsako izmed mnoºic

∅,{∅},{1},{1,{∅}},{{1}},{1,{1}}

ugotovi, ali je element in ali je podmnoºica mnoºice A.

2.2 Unije in preseki

1. Poi²£i mnoºice A∪B, A∩B, A\B in A^c, £e je

(a) A={n∈N|n je deljiv z 10}, B ={n ∈N|n je deljiv s 6}, (b) A= [0,2] inB = (−1,1).

2. Dokaºi ali s protiprimerom ovrzi naslednje trditve:

(a) (A\B)\C =A\(B∪C), (b) (A\B)\C =A\(B\C),

(c) (A\B)\C = (A\C)\B,

(d) (B\(A∪C))∪C = (C∪B)\(A\C), (e) A\(B\C) = (A\(B∪C))∪(A∩C), (f) (A\(B∩C))∪(B\C) = (A∪B)\(B ∩C), (g) (B∪C)\((A∪B)∩C) = (B \C)∪(C\(A∪B)), (h) (B\C)∪(C∩A)⊆B∪C,

(i) (A\(C∪B))∪B = (B∪A)\(C\B),

(j) (B\(A∩C))∪(A\C) = (B\A)∪((A∪B)\C), (k) (B∪C)\((A∪B)∩C) = (B \C)∪(C\(A∪B)),

(l) (B∪C)\((A∩B)∩C) = (B \C)∪(C\(A∪B)).

Skiciraj Vennove diagrame danih mnoºic, nato pa napravi ²e dokaz.

3. Dokaºi ali s protiprimerom ovrzi naslednje trditve:

(a) (A∪B)\C ⊆A ⇐⇒ B ⊆A∪C.

(b) C∩B ⊆(B\A)∩(C∪A)⇒A∩B =∅, (c) A∩B ⊆(A∪B)\C ⇒A∩B∩C =∅.

(d) A∩C ⊆B ∧ A∩B ⊆C ⇐⇒ A∩B =A∩C, (e) C∩B ⊆(B\A)∩(C∪A) ⇐⇒ A∩B∩C =∅.

(f) A∩C ⊆B ∧ A∩B ⊆C ⇐⇒ A∩B =A∩C, (g) (A\B)\C ⊆A\(B \C),

(h) A∩B =A∩C ∧ A∪B =A∪C ⇒ B =C,

(i) C\B =∅ ⇒ (A∩B)∪C ⊆(A∩C)∪B, (j) (A∩B)\C =B\C ⇐⇒ B ⊆A∪C,

(k) C∩B ⊆(B\A)∩(C∪A) ⇐⇒ A∩B∩C =∅,

4. Zapi²i na £im bolj enostaven na£in:

(a) S∞

n=1(n, n+ 1), (b) T∞

n=1(n, n+ 1), (c) S∞

n=1[−1 + ¹_n,1 + _n¹), (d) T∞

n=1[−1 + ¹_n,1 + _n¹), (e) S

x∈R⁻(x,0), (f) T

x∈R⁺(−x, x), (g) S∞

n=1[_n¹,2n+ 1], (h) T∞

n=1[_n¹,2n+ 1], (i) S∞

n=1[−_n¹, n), (j) T∞

n=1[−_n¹, n).

5. Dokaºi ali ovrzi naslednjo trditev:

(a) ƒe so mnoºice A_α, α ∈ I, paroma disjunktne, potem je njihov presek enak T

α∈IA_α =∅. (b) S∞

n=1(A_n×B_n)⊂S∞

n=1A_n×S∞ n=1B_n, (c) T∞

n=1A_n×T∞

n=1B_n⊂T∞

n=1(A_n×B_n).

2.3 Poten£na mnoºica in kartezi£ni produkt

1. Dane so mnoºice (a) A={1,2}, (b) A={1,{1}},

(c) A={1,∅}, B =P(A), (d) A={{∅}}, B =P(A).

Na²tej elemente mnoºic P(A) inP(B). 2. Dane so mnoºice

(a) A={1,{a}}, (b) A={∅,{1}}, (c) A={1, a,∅},

(d) A={∅, a,{a},{a}},{a,∅}}, Za vsako izmed mnoºic

∅,{∅},1,{{1}},{1, a},{a},{a,{a}},{{a,∅}}

ugotovi, ali je element in ali je podmnoºica poten£ne mnoºice P(A). 3. Naj boA neprazna mnoºica. Ugotovi, katere izmed mnoºic

∅,{∅}, A,{A},{A,∅}

so elementi in katere podmnoºice mnoºic P(A) inP(P(A)).

4. Dokaºi, da ima poten£na mnoºica mnoºice N_n={1,2, . . . , n} natanko 2ⁿ elementov.

5. Dokaºi ali ovrzi naslednje trditve:

(a) P(A)⊆ P(B) ⇐⇒ A⊆B, (b) {∅}=P(A) ⇐⇒ A=∅,

(c) P(A)∩ P(B) =P(A∩B),

(d) P(A)∪ P(B) =P(A∪B)⇒A=B, (e) P(A)\ P(B) =P(A\B),

6. Naj bo A = {1,2}, B = {1,∅} in C = [1,3). ƒimbolj natan£no opi²i naslednje mnoºice:

(a) A×B, (b) A×A×A,

(c) A×C, (d) C×C.

7. Dokaºi ali s protiprimerom ovrzi naslednje trditve:

(a) (A×B)∪(C×D)⊆(A∪C)×(B∪D), (b) A×(B∩C) = (A×B)∩(A×C),

(c) A×(B\C) = (A×B)\(A×C),

(d) (A\B)×(C\D) = ((A×C)\(A×D))\(B\C), (e) (A\B)×(C\D) = ((A×C)\(B×C))\(A×D), (f) (A\B)×(C\D) = (A×C)\((B×C)∪(A×D)), (g) (A∆B)×C = (A×C)∆(B×C).

8. Dokaºi ali s protiprimerom ovrzi trditev

P(A×B) =P(A)× P(B).

2.4 Relacije

1. Dane so relacije:

(a) R = {(−1,0),(−1,1),(2,1),(2,−1),(2,0),(2,2),(1,1)} na mno- ºici {−1,0,1,2},

(b) R = {(0,1),(0,2),(1,2),(1,3),(2,1),(2,3),(2,0),(3,0)} na mno- ºici {0,1,2,3},

(c) R ={(x, y)∈N ×N | x|y} na mnoºiciN ={1,2,3,4,5,6}.

• Relacije predstavite z gra.

• Ali je katera izmed relacij reeksivna, simetri£na, asimetri£na, antisimetri£na, tranzitivna, ekvivalen£na, sovisna ali strogo so- visna? Ali je katera relacija delne urejenosti oziroma linearne ure- jenosti.

2. Dane so relacije:

(a) relacija biti pametnej²i na mnoºici ljudi.

(b) relacija biti babica na mnoºici ºensk.

(c) relacija biti sestra na mnoºici ºensk.

(d) aRb ⇐⇒ a−b ∈Z, a, b∈R.

(e) aRb ⇐⇒ 3|(2a−b) na mnoºici N.

(f) xRy ⇐⇒ x²−y² ∈Z.

(g) xRy ⇐⇒ bxc =byc, a, y ∈ R, kjer bxc pomeni najve£je celo

²tevilo, ki ne presega x.

(h) (x, y) T (x⁰, y⁰) ⇐⇒ 2x+ 3y= 2x⁰+ 3y⁰, (x, y),(x⁰, y⁰)∈R². (i) x R y ⇐⇒ (x−y)√

2 ∈Z, x, y ∈R, (j) ARB ⇐⇒ A∩B =∅, A, B ∈ P(N).

(k) relacija pravokotnsti na mnoºici vseh premic v ravnini, (l) (x, y) R (x⁰, y⁰) ⇐⇒ x²+y² =x⁰²+y⁰² na mnoºiciR², (m) (x, y) R (x⁰, y⁰) ⇐⇒ x+x⁰ =y+y⁰, (x, y),(x⁰, y⁰)∈R².

(n) ⇐⇒ x+y⁰ +z =x⁰+y+z⁰, (x, y, z) R (x⁰, y⁰, z⁰)∈Z×Z×Z.

(o) xTy ⇐⇒ sin(x) =−sin(y), x, y ∈R.

(p) (x, y, z) R (x⁰, y⁰, z⁰) ⇐⇒ xy⁰z =x⁰yz⁰,(x, y, z, x⁰, y⁰, z⁰)∈Z.

(q) relacija na mnoºici vseh polinomov z realnimi koecienti:

p R q ⇐⇒ x⁵|(p(x)−q(x)).

(r) relacija na mnoºici vseh polinomov druge stopnje:

p(x) Rq(x) ⇐⇒ p, q imata enake ni£le. (s) ARB ⇐⇒ (A∪N)∩B 6=∅ na poten£ni mnoºici P(R).

• Preverite, ali so dane relacije reeksivne, simetri£ne, asimetri£ne, antisimetri£ne, tranzitivne, ekvivalen£ne, sovisne ali strogo sovi- sne. Ali je katera relacija relacija delne urejenosti oziroma linearne urejenosti.

• ƒe je katera izmed relacij ekvivalen£na, opi²i njene ekvivalen£ne razrede. Izberi si tudi nek elementx₀ (npr. 0) in eksplicitno podaj ekvivalen£ni razred tega elementa, t.j. poi²£i vse takex, za katere veljaxRx₀.

3. Dokaºi, da za relacijo R na mnoºici X veljajo naslednje trditve:

(a) Kompozitum relacij R ◦ R⁻¹ je simetri£na relacija.

(b) ƒe je relacija R reeksivna, potem so tudi njen inverz R⁻¹ in kompozituma relacij R ◦ R⁻¹ ter R ◦ R reeksivne relacije.

(c) ƒe je relacija R tranzitivna, potem sta tudi njen inverz R⁻¹ in kompozitum R ◦ R tranzitivni relaciji.

(d) ƒe je relacija R tranzitivna in ireeksivna, potem je asimetri£na.

4. Dani sta simetri£ni relaciji R in T. Dokaºi, da je potem kompozitum relacijR◦T simetri£na relacija natanko tedaj, ko velja R◦T = T◦R. 5. Na mnoºiciX sta dani simetri£ni in reeksivni relaciji R₁ in R₂. Ugo- tovi, ali je tudi relacija xRy ⇐⇒ (x R₁y)∧(x R₂y) na mnoºici X simetri£na in reeksivna.

6. Naj bosta ∼1 in ∼2 ekvivalen£ni relaciji na mnoºici X. Ugotovite, ali je naslednja relacija na X vedno ekvivalen£na:

(a) xRy ⇐⇒ (x∼₁ y)∧(x∼₂ y), (b) xRy ⇐⇒ (x∼₁ y)∨(x∼₂ y).

2.5 Funkcije in mo£ mnoºic

1. Dani sta relaciji

(a) R ={(−2,3),(0,1),(1,2),(−1,2),(2,3)} iz mnoºice {−2,−1,0,1,2} v mnoºico{1,2,3},

(b) R ={(0,−1),(1,0),(2,1),(3,2),(2,3)}na mnoºici{−1,0,1,2,3}. Ali je katera izmed relacij R, R⁻¹ ali R ◦ R⁻¹ funkcija? ƒe je od- govor za katero od relacij pritrdilen, potem ugotovi, ali je injektivna, surjektivna oziroma bijektivna?

2. Dane so preslikave:

(a) Funkcija, ki slika iz mnoºice vseh ljudi v mnoºico vseh barv, ter vsakemu £loveku priredi naravno barvo njegovih las.

(b) Funkcija, ki slika iz mnoºice vseh ²tudentov na PeF v kartezi£ni produkt N×N, ter vsakemu ²tudentu priredi urejen par, vpisno

²tevilko in njegova leta.

(c) FunkcijaN→Z, ki ²tevilu priredi ²tevilo vseh njegovih deliteljev.

(d) f:R\ {1} →R\ {1}, f(x) = ^x+1_x−1. (e) f:R\ {1} →R\ {2}, f(x) = ^2x_x3³−1⁺³. (f) g:Z^2×2 →Z,

a b c d

7→(2a+ 3d+ 1). (g) f:N×N→N×Z, f(a, b) = (2a+b, b−3a).

(h) f:N→N, f(n) =

2n+ 1, n sodo 3n+ 1, n liho , (i) f:Q² →Q², f(a, b) = (a−b², b³+ 2).

(j) f:R×R→R^2×2, (a, b)7→

a²−b 1

0 a

. (k) f:Z×Z→Z, f(a, b) =a+b.

(l) f:Z→N, f(x) =

3x, x≥2 5−3x, x≤1 . (m) f:Z×Z→Z×Z, f(a, b) = (a b, a).

(n) f:N×N→Z×Z, f(a, b) = (a², a−b). (o) f:P(Q)× P(Q)→ P(Q), f(A, B) = A∩B.

(p) f:Z→Z², f(x) = (x², x³). (q) f:P(R)→Z, f(A) =

min(A∩N), A∩N6=∅

−1, A∩N=∅ (r) f:P(R)→N∪ {0}, f(A) =

min(A∩N), A∩N6=∅

0, A∩N=∅ ,

Razi²£i injektivnost, surjektivnost in bijektivnost danih preslikav. ƒe je katera izmed preslikav bijekcija, ji poi²£i ²e njen inverz.

3. Dani sta preslikavi f:X → Y in g:Y →X. Dokaºi ali ovrºi naslednje trditve:

(a) ƒe staf ing injektivni (surjektivni), potem je tudig◦f injektivna (surjektivna).

(b) ƒe jeg surjektivna (f injektivna), potem jeg◦f tudi surjektivna (injektivna).

(c) ƒe je g ◦f surjektivna (injektivna), potem je g surjektivna (f injektivna).

(d) Naj boX =Y. Potem je preslikava f:X →X bijekcija natanko tedaj, ko je tudi f◦f je bijekcija.

4. Dani sta funkciji

(a) f:N∪ {0} →N, f(n) =

2n, n sodo 3n−1, n liho , (b) f:Z→Z×Z, f(x) = (x², x³).

• Poi²£i sliki f({0,1,2}) in f(N).

• Dolo£i tiste od praslik f⁻¹({1,2,3,4})inf⁻¹({(1,−1),(4,8)}), ki so dobro denirane.

5. Dana je preslikava f:X → Y in mnoºici A, B ⊆ X. Dokaºi naslednje trditve:

(a) A⊆f⁻¹(f(A)); £e jef injektivna velja enakost.

(b) f(A)\f(B)⊆f(A\B); £e je f injektivna, velja ena£aj, 6. Dana je funkcija f in relacija na njeni domeniD_f:

xRy ⇐⇒ f(x) = f(y), x, y ∈ D_f. Ali je katera relacija ekvivalen£na?

7. Pokaºi, da so dani pari mnoºic enake kardinalnosti, ter eksplicitno po- daj oziroma opi²i bijekcijo med njimi:

(a) N inN\{1,2,3},

(b) N in{−6,−3,0,3,6,9,12, . . .}, (c) {1,2} ∪ {n ∈N|3 deli n}in N, (d) N×N in{

a b 2b 3b

|a, b∈N},

(e) (0,^π₂) (ali (0,1)) in R⁺. (Nasvet: Poi²£i injektivno funkcijo z ustrezno ni£lo ter polom.)

(f) [1,2] in[3,5],

(g) (0,1) in [0,1), (Nasvet: Poi²£i najprej bijekcijo med ustreznima

²tevnima podmnoºicama.) (h) P(Z)in P(N),

(i) R in(0,1]×Z.

8. Pokaºi, da je mo£ poten£ne mnoºice ve£ja od mo£i same mnoºice.

3 Re²itve

3.1 Logika

3.1.1 Resni£nostne tabele

1. Vse izjave obravnavamo na enak na£in. Oglejmo si zato le izjavo (f).

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

0 0 0 1 1 0 0 1

0 0 1 1 0 1 1 1

0 1 0 1 1 0 0 1

0 1 1 1 1 1 1 1

1 0 0 1 1 0 0 0

1 0 1 0 0 1 0 1

1 1 0 1 1 0 0 1

1 1 1 1 1 0 0 1

Iz vrstic v tabeli, kjer je vrednost dane izjave enaka 1, t.j. druga,

£etrta in ²esta vrstica, lahko preberemo, da imata v teh primerih tudi izjavi r in(p⇒q)∨r vrednosti1, ostale izjave p, q inr pa zavzamejo obe vrednosti 0 in 1. ƒe je torej dan izjava resni£na, sta resni£ni tudi izjavi r in(p⇒q)∨r, o resni£nosti oziroma neresni£nosti ostalih izjav p, q in r pa ne moremo sklepati.

2. Vseh primerov se lotimo na enak na£in. Oglejmo si denimo primer (d).

Najprej izberemo ustrezne enostavne izjave:

p≡ A je vitez. q≡ B je oproda. r≡ C je vitez.

Izjavi, ki sta jih dala doma£ina, sedaj opi²emo z izjavamaI ≡:¬r⇒q, ter J ≡:p∧ ¬r, ter zapi²emo resni£nostno tabelo:

p q r I ≡ ¬r ⇒q J ≡ p∨r

0 0 0 0 0

0 0 1 1 1

0 1 0 1 0

0 1 1 1 1

1 0 0 0 1

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

Opazimo, da je za vrednost p ∼ 1 doma£in A resnicoljubni vitez in mora biti I ∼ 1, za p ∼0 pa je A laºnivi oproda in mora biti I ∼ 0. Podobno sklepamo, da je za q ∼ 1 doma£in B oproda in J ∼ 0, za q ∼0 pa je B vitez in J ∼1. Mogo£ je torej le primer v ²esti vrstici, torej so vsi doma£ini vitezi.

3. Luka je dal gol.

3.1.2 Ekvivalenca izjav

1. Vse pare izjav obravnavamo na enak na£in. Natan£neje si zato oglejmo le primer (e).

Zapi²imo resni£nostno tabelo za dane izjave, pri £emer so v prvih treh stolpcih vrednosti izjavp,qinr, sledita stolpca z vrednostmi izjav I in J, itd:

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

0 0 0 1 1 1 1

0 0 1 1 0 1 1

0 1 0 0 1 1 0

0 1 1 0 1 0 0

1 0 0 1 1 0 1

1 0 1 0 1 0 1

1 1 0 0 1 0 1

1 1 1 0 1 1 1

Ker se resni£nostna stolpca izjav I in J ne ujemata, izjavi nista ekvi- valentni. Iz vrstic v tabeli, kjer je vrednost posamezne izjave enaka 1 lahko seveda takoj preberemo tudi normalni disjunktivni obliki izjav.

I ∼ (¬p∧ ¬q∧ ¬r)∨(¬p∧ ¬q∧r)∨(p∧ ¬q∧ ¬r),

J ∼ (¬p∧ ¬q∧ ¬r)∨(¬p∧q∧ ¬r)∨(¬p∧q∧r)∨(p∧ ¬q∧ ¬r)

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

Primera oziroma vrstici, ko sta hkrati obe izjavi I inJ resni£ni, sta v tabeli pod£rtana. Vidimo, da lahko tedaj sklepamo, da sta izjaviq inr neresni£ni, izjavaq ⇒presni£na, o izjavahpinp⇔(q∧r)ne moremo sklepati ni£esar.

2. Vse pare izjav obravnavamo na enak na£in, primerjajmo zato le para pod (e) in (f). Pa zapi²imo resni£nostno tabelo:

A B C (A⇒B)∧(C∨B) A⇒((B ∧C)∨B)

(¬A∧C)∨B A⇒B

0 0 0 0 1

0 0 1 1 1

0 1 0 1 1

0 1 1 1 1

1 0 0 0 0

1 0 1 0 0

1 1 0 1 1

1 1 1 1 1

Stolpca v resni£nostni tabeli sta razli£na, torej para izjav res nista ekvivalentna.

3. Vse pare izjav obravnavamo enako. Oglejmo si natan£ne denimo primer (d). Izberimo enostavne izjave:

b ≡ Sem bogat. p≡ Sem pameten. s ≡ Sem sre£en.

S pomo£jo izbranih enostvnih izjav lahko naprej podamo izjave I ≡ (¬p∨ ¬s)⇒(¬b∧ ¬s), J ≡(b ⇔ ¬p)⇒(¬b∧s), P ≡ s⇔b, Q≡s∨p,

ter zapi²emo resni£nostno tabelo:

b p s (¬p∨ ¬s)⇒(¬b∧ ¬s) (b ⇔ ¬p)⇒(¬b∧s) P Q

0 0 0 1 1 1 0

0 0 1 0 1 0 1

0 1 0 1 0 1 1

0 1 1 1 1 0 1

1 0 0 0 0 0 0

1 0 1 0 0 1 1

1 1 0 0 1 0 1

1 1 1 1 1 1 1

Odtod takoj sledi, da izjavi P inQnista ekvivalentni, njuna normalna disjunktivna oblika pa je:

P ∼ (¬p∧ ¬q∧ ¬r)∨(¬p∧q∧ ¬r)∨(¬p∧q∧r)∨(p∧q∧r), Q ∼ (¬p∧ ¬q∧ ¬r)∨(¬p∧ ¬q∧r)∨(¬p∧q∧r)∨(p∧q∧ ¬r)

∨(p∧q∧r).

Izjavi I inJ sta resni£ni v primerih, ki so v tabeli pod£rtani, t.j. prva

£etrta in zadnja vrstica. Vidimo, da tedaj o izjavah P inQne moremo sklepati ni£esar.

4. Vseh izjav se lotimo na podoben na£in, zato si natan£neje oglejmo naprimer (b).

Veznik⇒izrazimo z∨, ter upo²tevamo de Morganov zakon, pa dobimo izjavo zgolj z negacijami enostavnih izjav, ter le z veznikoma ∧ in∨:

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

NDO izjave pa preberemo iz resni£nostne tabele kot v nalogi 4:

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

S pomo£jo znanih ekvivalenc zapi²imo negacijo v enostavnej²i obliki:

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

Lahko pa bi zapisali tudi z normalno disjunktivno obliko negacije izjave.

5. Dovolj bo izraziti konjunkcijo in negacijo. Z malce ra£unaja dobimo

¬p ∼ p↑p, p∧q ∼ (p↑q)↑(p↑q),

¬p ∼ p↓p, p∧q ∼ (p↓p)↓(p↓q).

6. V ponedeljek bi tako vitez kot oproda z Da odgovorila na vpra²anje:

Ali je res, da si ti vitez natanko tedaj, ko je danes ponedeljek? Na vpra²anje: Ali je res, da si ti vitez ali oproda? pa bi vitez odgovoril z Da, oproda pa z Ne.

3.1.3 Kvantikatorji

1. (a) Izjava: ∀x: (¬p(x)⇒q(x)), p(x)≡x nosi o£ala ,q(x)≡x nosi kapo.

Negacija: ∃x: (¬p(x)∧ ¬q(x)).

(b) Izjava: ∀x:∃y: (r(x, y)), r(x, y)≡x pozdravi y. Negacija: ∃x: (∀y: (¬r(x, y))).

(c) Izjava: ∃a: (a² ∈A). Negacija: ∀a: (a² ∈/ A).

(d) Izjava: ∀n: (6|n ⇒(2|n)∧(3|n)). Negacija: ∃n: (6 |n∧(2-n∨3-n)). (e) Izjava: ∀q: (∃n: (n∈N∧n > q)).

Negacija: ∃q:∀n: (n ∈N⇒n≤q).

(f) Izjava: ∀x: (∃y: (x= 2y)). Negacija: ∃x:∀y(x6= 2y).

(g) Izjava: ∃m: ((∀n: (n > m))⇒(∀k)(m|k)). Negacija: ∀m: ((∀n: (n > m))⇒(∃k: (m-k))).

(h) Izjava: ((1 ∈P)∧(∀n: (n ∈P ⇒n+ 1∈P)))⇒(N⊂P). Negacija: ((1∈P)∧(∀n: (n∈P ⇒n+ 1 ∈P)))∧N *P.

(i) Izjava: ∀a: (a >10⇒(∃b: (a=b²))). Negacija: ∃a: (a >10∧(∀b: (a6=b²))).

(j) Izjava: ∀n: (2|n³ ⇒2|n). Negacija: ∃n: (2 |n³∧2-n).

(k) Izjava: ∀n: (∃m: (n= 3m+ 1) ⇐⇒ (∃k: (n³ = 3k+ 1))). Negacija: ∃n: (∃m: (n= 3m+ 1) ⇐⇒ ∀k: (n³ 6= 3k+ 1)). (l) Izjava: ∀: (∃N: (n > N ⇒ _n¹ < )).

Negacija: ∃: (∀N: (n > N ∧ _n¹ ≥)).

2. (a) Izjava: Za vsak x∈R obstaja y∈R, da je x= 2y.

Negacija: Obstaja realno ²tevilo, ki ni dvakratnik nobenega real- nega ²tevila.

(b) Izjava: Neko naravno ²tevilo je popolni kvadrat.

Negacija: Nobeno naravno ²tevilo ni popolni kvadrat.

(c) Izjava: Ne obstaja najve£je realno ²tevilo.

Negacija: Neko realno ²tevilo je najve£je.

(d) Izjava: Vsaka pozitivna realna funkcija je manj²a ali enaka neki pozitivni realni funkciji.

Negacija: Obstaja nenegativna realna funkcija, ki je manj²a od vsake nenegativne realne funkcije.

(e) Izjava: ƒe je produkt dveh realnih ²tevilxinyenak0, je vsaj eno izmed ²tevil x iny enako 0.

Negacija: Obstajata neni£elni ²tevilixiny, da je njun produkt 0.

(f) Izjava: Nekatera naravna ²tevila niso niti popolni kubi niti po- polni kvadrati.

Negacija: Vsako naravno ²tevilo je popolni kub ali popolni kva- drat.

(g) Izjava: Obstajajo naravna ²tevila, ki so popolni kvadrati ali niso popolni kubi.

Negacija: Vsako naravno ²tevilo je popolni kub in ni popolni kva- drat.

(h) Izjava: Nekatera naravna ²tevila so deljiva z 2ali niso deljiva s3. Negacija: Vsako naravno ²tevilo je deljivo s 3 in ni deljivo z2. (i) Izjava: Obstajajo cela ²tevila, ki dajo pri deljenju s 4 ostanek 1

natanko tedaj, ko pri deljenju s 3 ne dajo ostanka 1.

Negacija: Vsako naravno ²tevilo da pri deljenju s 3 ostanek 1 natanko tedaj, ko da pri deljenju s 4ostanek 1.

(j) Izjava: Za poljubni naravni ²tevili m in N obstaja tako naravno

²tevilo n, ki je ve£je od N in _n¹² < _m¹.

Negacija: Obstajata naravni ²tevili m in N, da za vsako naravno

²tevilo n, ki je ve£je N, velja: _n¹2 ≥ _m¹.

(k) Izjava: Za vsako mnoºico A obstaja mnoºica B, da velja: £e je A prava podmnoºica mnoºiceB, potem je P(A)6=P(B).

Negacija: Obstaja taka mnoºica A, ki je prava podmnoºica vsake mnoºice B in P(A) =P(B).

3.1.4 Logi£no sklepanje

1. (a) Q je (izklju£no) potreben pogoj za P. (13|39, 26-39.)

(b) P je (izklju£no) potreben pogoj zaQ. ((−2)·(−1)>,−1,−2≤0.) (c) P je potreben in zadosten pogoj za Q, ter obratno.

(d) P je (izklju£no) zadosten pogoj za Q. (−1<1, (−1)² >−1.) 2. Sklepi:

(a) Modus ponens (MP):

P: p⇒q Q: p R: q

(b) Modus tolens (MT):

P: p⇒q Q: ¬q R: ¬p

(c) Hipoteti£ni silogizem (HS):

P: p⇒q Q: q⇒r R: p⇒r

(d) Disjunktivni silogizem (DS):

P: p∨q Q: ¬q R: p

3. Uporabimo oznake za sklepe kot v nalogi 2:

1. p⇒ ¬q pr 2.¬q ⇒ ¬r pr 3.(r ⇒ ¬p)⇒t pr 4. p⇒ ¬r HS(1,2) 5. r ⇒ ¬p ∼4

6. t MP(3,5)

1. p∧ ¬p pr 2. p P o(1) 3.¬p P o(1) 4.¬p∨q P r(3) 5. p⇒q ∼4 6. q M P(2,5) 1.(¬q∨r)⇒(¬p∧q) pr

2.(q∧ ¬r)⇒s pr

3.¬s pr

4.¬(q∧ ¬r) M T(2,3)

5.¬q∨r ∼4

6.¬p∧q M P(1,5)

7. q P o(6)

1.(q∨r)⇒(p∧ ¬q) predp 2.(¬q∧ ¬r)⇒s predp

3.¬s predp

4.¬(¬q∧ ¬r) M T(2,3)

5. q∨r ∼4

6. p∧ ¬q M P(1,5)

7.¬q P o(6)

8. r DS(5,7)

4. O izjavi ¬p∧r ne moremo sklepati ni£esar. Pri vrednostih enostavnih izjav p ∼ 1, q ∼ 1 in r ∼ 0 so namre£ dane predpostavke resni£ne, izjava p∧r pa neresni£na; pri vrednostih enostavnih izjavp∼0,q∼1 in r∼0 pa so dane predpostavke resni£ne, izjava p∧r pa resni£na.

Zapi²imo sedaj dokaz izjave r⇒q (oznake kot v nalogi 2):

1. p∨q pr 2. r ⇒ ¬p pr 3.¬q ⇒r pr 4.¬p⇒q ∼1 5. r ⇒q HS(2,4)

5. Po trditvi Q je ºival na sliki plazilec, potem pa je tudi plazilec ali sesalec (sklep pridruºitve). Po sklepu modus ponens, iz ugotovljenega in trditveP ugotovimo, da ºival diha s plju£i in ne zna leteti. Torej ne zna leteti (sklep poenostavitve).

6. (a) b≡ Sem bogat. l ≡ Sem lep. p≡ Sem pameten., P ≡ (l∨p)⇒(s∧b), Q≡ ¬b, R≡ ¬l∧ ¬p.

(b) Izpeljava trditve R (oznake za sklepe so kot v nalogi 2):

1.(l∨p)⇒(s∧b) pr

2.¬b pr

3.¬b∨ ¬s P r(2) 4.¬(s∧b) ∼3 5.¬(l∨p) M T(1,4)

6.¬l∧ ¬p ∼3

3.1.5 Metode dokazovanja

1. Vse primere dokaºemo na podoben na£in, dokaºimo zato le primer (a).

Lo£imo tri primere, ki za k ∈N zajamejo vsa naravna ²tevilan: n = 3k−2: n³−n = 3(9k³ −6k²+ 3k−2),

n = 3k−1: n³−n = 3(9k³ −3k²), n = 3k: n³−n= 3(9k³−k).

’tevilo n je torej vedno deljivo s 3. 2. (a) Zaa= 0, je a²−7a+ 12 = 126= 0.

(b) ƒe bi bili sta obe ²tevili iste parnosti, bi bila tudi njuna kuba iste parnosti, vsota kubov pa seveda soda.

(c) ƒe bi se vsaka ²tevka v decimalnem zapisu pojavila kon£nokrat, bi bil zapis kon£en.

(d) Upo²tevaj, da se da izraz mⁿ+ 1 razcepiti, £e je n liho.

(e) Predpostavi nasprotno, da je pra²tevil kon£no mnogo, t.j. p₁, p₂,. . ., p_n, ter razmisli, kak²no ²tevilo je potem p₁p₂· · ·p_n+ 1. 3. (a) Zan = 1 enakost jasno drºi.. Vzemimo sedaj n+ 1 £lenov vsote,

jih po indukcijski predpostavkin zamenjajmo s 'formulo' ^n(3n−1)₃ , ter dobljen vsoto preuredimo:

1³+ 2³+. . .+ (n+ 1)³ = (ⁿ⁽ⁿ⁺¹⁾₂ )²+ (n+ 1)³ = (^(n+1)(n+2)₂ )². (b) Oglejmo si indukcijski korak. Po indukcijski prepostavki za nekn

velja5ⁿ−4n−1 = 16k ali5ⁿ= 16k+ 4n+ 1, kjerk ∈Z. Potem velja5ⁿ⁺¹−4(n+ 1)−1 = 5(16k+ 4n+ 1)−4n−5 = 16(5k−n).

(c) Ra£un: ⁽ⁿ⁺¹⁾₂ ⁴ + ⁽ⁿ⁺¹⁾₃ ³ + ⁿ⁺¹₆ = ⁿ₂⁴ +ⁿ₃³ +ⁿ₆ + 2n³+ 4n²+ 3n+ 1 (d) V indukcijskem koraku (n+ 1)-kotnik razreºi na n-kotnik in tri-

kotnik, ter uporabi indukcijsko predpostavko na n-kotniku.

4. (a) P ≡ p⇒(¬s∧b), Q≡ ¬p⇒s, R≡ s∨ ¬b.

(b) Opazi, da so pri naborih vrednosti p∼1, s ∼1, b ∼1 ter p∼0, s∼ 1, b∼ 0izjave P, Q in R resni£ne, kar pomeni, da o izjave p ni mo£ sklepati ni£esar.

Zapi²imo sedaj dokaz izjave s:

1. p⇒(¬s∧b)) predp 2.¬p⇒s predp 3. s∨ ¬b predp

4.1.¬s predp RA

4.2. p M T(2,4.1) 4.3.¬s∧b∨q M P(1,4.2)

4.4. b P o(4.3)

4.5. s DS(3,4.4) 4.6.¬s∧s Zd(4.1,4.5)

4.7. 0 ∼5.8

4. s RA(4.1−4.7)

5. (a) u≡ U£im se. d≡ Delam doma£e naloge. i≡ Naredim izpit.

k ≡ Grem v kino.,

P ≡ (u∨d)⇒(i∧k), Q≡ i∧(k∨u), R ≡ u⇔(i∧k).

(b) Opazi, da sta pri naborih vrednosti d∼0,i∼1,u∼0, k∼0 ter d∼ 1, i ∼1, k ∼0, u ∼1 izjavi P in Q resni£ni, kar pomeni, da o izjavi d ni mo£ sklepati ni£esar.

Zapi²imo sedaj dokaz izjave R: 1.(u∨d)⇒(i∧k) predp

2. i∧(k∨u) predp

3.1. u predp PS

3.2. u∨d P r(3.1)

3.3. i∧k M P(3.2,1)

3. u⇒(i∧k) P S(3.1,3.3)

4.1. i∧k predp PS

4.2. k P o(4.1)

4.3.¬k∨u∨q P o(2)

4.4. u DS(4.3,4.2)

4.(i∧k)⇒ P S(4.1−4.4)

5.(u⇒(i∧k))∧((i∧k)⇒) Zd(3,4)

6. u⇔(i∧k) ∼5

6. (a) b≡ Sem bogat. p≡ Sem pameten. s≡ Sem sre£en.

m≡ Sem mlad., t ≡ Sem ²tudent.

(b) Dokaºimot:

1.¬b⇒p predp 2.(¬s∨p)⇒m predp

3. m⇒t predp

4. b⇒ predp

5.1.¬t predp RA

5.2.¬m M T(3,5.1) 5.3.¬(s∨p) M P(2.1,5.2) 5.4. s∧ ¬p ∼5,3

5.5. s P o(5) 5.6.¬b M T(4,5.5) 5.7.¬p P o(5.4) 5.8. p M P(1,5.6) 5.9. p∧ ¬p Zd(5.7,5.8) 5.10. 0 ∼5.9

5. t RA(5.1−5.50) Opazimo, da so pri naborih vrednosti b∼0, p∼1, m ∼1, t ∼1, s ∼0, ter b ∼ 1, s ∼0, m ∼ 1, t ∼1, p ∼1 izjave P, Q, R in S resni£ne, kar pomeni, da o izjavi d ni mo£ sklepati ni£esar.

7. Re²uj podobno kot naloge 4,5 in6. 8. Dopolnjeni dokazi:

1. p⇒(q∧r) predp 2. (q∨s)⇒u predp

3. u⇒ ¬t predp

4. (q∨s)⇒ ¬t . . . 5.1. . . . 5.2. q∧r . . .

5.3. q . . .

5.5. q∨s . . .

5.6. ¬t . . .

5. p⇒ ¬t PS(5.1−5.6) 6. t⇒ ¬p . . .

,

1.p⇒(q∧r) predp 2.¬p⇒(¬q∧ ¬r) predp

3.¬p⇒ ¬s predp

4.1. . . . predp P S 4.2.q∧r . . .

4.3.r . . .

4.4.r∨ ¬s . . . 4.p⇒r∨ ¬s . . .

5.s⇒p . . .

6. . . . HS(4,5)

1.¬p∨q predp 2.(¬s∨q)⇒t predp 3.1.¬t . . . 3.2.¬(¬s∨q) . . . 3.3.s∧ ¬q . . . 3.4.¬q . . .

3.5. . . . DS(1.,3.4.) 3.¬t ⇒ ¬p . . .

1. p⇒(q∨r) predp

2.¬r predp

3.1. p . . . 3.2. q∨r . . . 3.3. q . . . 3. p⇒q . . .

,

1. p∨(r ⇒s) predp

2. p ⇐⇒ s predp

3.1.¬p∧r . . .

3.2.¬p . . .

3.3. . . . DS(1,3.2) 3.4.(p⇒s)∧(s⇒p) . . .

3.5. s⇒p . . .

3.6. r⇒p . . .

3.7. . . . MT(3.2,3.6)

3.8. . . .

3.9. . . .

3.10. 0 . . .

3.¬(¬p∧r) . . .

4. p∨ ¬r . . .

1.(p∨q)⇒(s⇒ ¬q) predp 2.(¬r∨p)∧s predp

3.¬q ⇒ ¬p predp

4.¬r∨p P o(2)

5.1. r predp RA

5.2. p DS(4,5.1)

5.3. p∨q P r(5.2) 5.4. s⇒ ¬q M P(1,5.3) 5.5. s⇒ ¬p HS(3,5.4)

5.6. s P o(2)

5.7.¬p M P(5.5,5.6)

5.8.¬p∧p Zd(5.2,5.7)

5.9. 0 ∼5.8

5.¬r RA(5.1−5.9)

1.(¬p⇒q) predp 2.(¬s∧q)⇒r predp 3. p∨ ¬r predp 4.¬r⇒ ¬s predp

5.1.¬p predp RA

5.2.¬r DS(3,5.1) 5.3.¬(¬s∧q) M T(2,5.2) 5.4. s∨ ¬q ∼5.3 5.5.¬s MP(4,5.2) 5.6.¬q DS(5.4,5.6) 5.7. q M P(1,5.1) 5.8.¬q∧q Zd(5.6,5.7)

5.9.0 ∼5.8

5. p RA(5.1−5.9)

9. Napravi dokaza s pogojnim sklepom.

10. Izpeljimo izjavo q z analizo primerov:

1.¬q⇒r predp 2. r⇒ ¬p predp 3. p∨q predp

4. r predp

5.¬p⇒q ∼4 6. r⇒q M P(2,4) 7. q M P(4,6) ,

1.¬q ⇒r predp 2. r ⇒ ¬p predp 3. p∨q predp 4.¬r predp 5.¬¬q M T(1,4)

Izjave p∧rpa ne moremo izpeljati, saj so pri vrednosti enostavnih izjav p ∼ 1, q ∼ 1 in r ∼ 0 predpostavke resni£ne, izjava p∧r pa neresni£na.

11. (a)

1.(r⇒ ¬p)∧ ¬q predp 2. r ⇒(p∨q) predp

3.¬q P o(1)

4.1. r predp RA

4.2. p∨q M P(2,3.1) 4.3. r⇒ ¬p P o(1)

4.4.¬p M P(4.1,4.3)

4.5. q DS(3,4.2)

4.6. q∧ ¬q Zd(3,4.5)

4.7.0 ∼4.6

4.¬r predp RA(4.1−4.7) 5.¬r∧ ¬q Zd(3,4)

(b)

1.(¬p∨s)⇒(q∧r) predp 2.(p∨ ¬r)∧q predp

3.¬q P o(2)

4. p∨ ¬r P o(2)

5.1.¬p predp PS

5.2. r DS(4,5.2)

5.3. r∧q Zd(3,5.2)

5.¬p⇒(r∧q) predp PS(5.1−4.3)

6.1. r∧q predp PS

6.2. r P o(6.1)

6.3.¬p DS(4,6.2)

6.(r∧q)⇒ ¬p predp PS(6.1−6.3) 7.((r∧q)⇒ ¬p)∧(¬p⇒(r∧q)) Zd(5,6)

8.¬p ⇐⇒ (r∧q) ∼7

3.2 Mnoºice

3.2.1 Mnoºice in podmnoºice 1. (a) {1,−1,3,−3, . . .},

(b) {0,¹₂,−¹₂,²₂,−²₂,³₂,−³₂, . . .}, (c) {2,10},

(d) {1,2,3,4,5,6}. 2. (a) {√

n|n ∈N},

(b) {n∈N|(4|n)∨(n³ <30)}, (c) {n² |n ∈N} ∪ {n∈N|4-n}.

3. (a) A je mnoºica lihih ²tevil, B pa mnoºica kubov vseh lihih ²tevil.

Jasno B ⊂A in B 6=A.

(b) A inB sta mnoºici kubov vseh lihih ²tevil, B pa vsebuje vsa cela

²tevila in vse ulomke z imenovalcem 2.

(c) Opazi(2n)²−1 = 4n²−1 = 4(n²−1) + 3in izpeljiA⊂B,A6=B. (d) Opazi, da ²tevilo oblike (3k+ 2)² ostanek 1 pri deljenu s 3, zato

B ⊂A. Obratno ne velja, saj denimo 3∈A, vendar 3∈/ B. (e) ElementiAso oblikey=x³zax∈Q. Jasno je potemy³ =x⁹ ∈B

oziroma A⊂B. Obratno ne velja, da √³

2∈B\A. (f) Re²ujemo podobno kot primer (e).

(g) A in C sta mnoºici ulomkov z imenovalcem 2, B pa je mnoºica sodih ²tevil. SlediB ⊂A=C, B 6=A.

4. Matemati£na oblika izjave:

∀A: (∃B: (B ⊂A∧A6=B)⇒A6= 0).

Dokaz: Ker B ⊂ A in A 6= B, obstaja nek element v A \B, torej A6={∅}.

5. (a) Izjava z besedami: Za vsako mnoºico A velja: ƒe obstaja element poten£ne mnoºice A, ki ni ∅, potem tudi A ni prazna mnoºica.

Utemeljitev izjave: Elementi poten£ne mnoºice A so podmnoºice mnoºice A, zato je element poten£ne mnoºice, ki ni prazna mno- ºica, neprazna podmnoºica mnoºice A.

(b) Negacija izjave: ∃A: ((∀B: (B *A∨B =∅))∧A=∅) 6. (a) {∅} vsebuje element, zato to ni prazna mnoºica.

(b) Relacija A⊂ ∅pomeni, da so vsi elementi mnoºice Avsebovani v

∅. Torej je moºno leA =∅. 7. (a) elementi A: ∅, {1},

podmnoºiceA: ∅, {∅},{1}, {∅,1}, {{1}}, {1,{1}},

(b) elementi A: ∅, {{1}},

podmnoºiceA: ∅, {∅},{1}, {∅,1},

3.2.2 Unije in preseki

1. (a) A∪B ={n ∈N: 10|n ∨ 6|n}, A∩B ={n ∈N: 10|n ∧ 6|n}, A\B ={n∈N: 10 |n ∧ 6-n}, A^c={n∈N: 10 -n}

(b) A∪B = (−1,2], A∩B = [0,1),A\B = [1,2],A^c =R\[0,2], 2. Vse primere se da obravnavati enako. Natan£no si zato oglejmo le nakaj

primerov (a), (b), (f) in (i). Neenakost bomo obrgli s protiprimerom, vsake od enakosti pa se bomo lotili na druga£en na£in.

(a) Enakost v primeru (a) dokaºimo tako, da zapisa mnoºic v enakosti preoblikujemo enostavnej²ega, a seveda ekvivalentnega:

(A\B)\C = A\(B∪C) (A∩B^c)∩C^c = A∩(B∪C)^c (A∩B^c)∩C^c = A∩(B^c∩C^c) Vidimo, da enakost res velja.

(b) Enakost v primeru (b) v splosnem ne velja. Za A = {1,2,3}, B = {3,4} in C = {1,3} denimo dobimo (A\B)\C = {2} in A\(B\C) ={1,2}

(f) Pa pokaºimo primer (f). Enakost mnoºic bomo pokazali tako, da bomo pokazali obe vsebovanosti. Pri tem nam je v pomo£ tudi Vennov diagram.

Lotimo se najprej vsebovanosti ⊂, pokaºimo (A\(B∩C))∪(B\C)⊂(A∪B)\(B ∩C).

Takoj opazimo, da je A\(B ∩C) ⊂ (A∪B)\(B ∩C), saj je A ⊂ A∪ B. Velja pa tudi (B \C) ⊂ (A∪ B)\(B ∩C), saj B ⊂A∪B in B∩C ⊂C.

Pokaºimo sedaj ²e obratno vsebovanost⊃. Vzemimo poljubni element x ∈ A\(B∩C), t.j. x ∈ A in x /∈ B ∩C. Nato lo£imo dve moºnosti. ƒe je x ∈ A, potem je jasno x ∈ A \(B ∩ C).

ƒe pa x ∈ B, potem pa je x ∈ B \C. V obeh primerih velja x∈(A\(B∩C))∪(B\C).

(i) Dokaºimo ²e enakost (i). Tretja moºnost dokazovanja je tabela po zgledu resni£nostne tabele pri logiki. V tabeli bo z 1 ozna-

£eno, £e element je vsebovan v mnoºici, sicer pa z0. Pa zapi²imo pripadajo£o resni£nostno tabelo:

A B C (A\(C∪B))∪B (B ∪A)\(C\B)

0 0 0 0 0

0 0 1 0 0

0 1 0 1 1

0 1 1 1 1

1 0 0 1 1

1 0 1 0 0

1 1 0 1 1

1 1 1 1 1

Stolpca v tabeli sta enaka, kar implicira enakost mnoºic.

3. Vse primere se dokaze na podoben na£in, zato bomo natan£no dokazali le en primer z unijo in en primer s presekom, npr. (g) in (h).

Pokaºimo najprej, da je S∞

n=1[_n¹,2n+ 1] = (0,∞). Hitro opazimo, da so intervali[¹_n,2n+1]vsebovani v(0,∞)za vsen∈N, zato je potem unija teh intervalov vsebovana v(0,∞). Za dokaz obratne vsebovanosti pa izberimo poljubnix∈(0,∞)in pokaºimo, da je tudi element unije.

Za dovolj velik n bo jasno _n¹ < x < 2n+ 1, ter tako x ∈ [_n¹,2n+ 1]. Odtod pa ºe sledi x∈S∞

n=1[_n¹,2n+ 1]. Nadalje pokaºimo T∞

n=1[_n¹,2n+ 1] = [1,3]. Opazimo, da je[1,3]⊆ [_n¹,2n + 1] za vse n ∈ N, zato je interval [1,3] zagotovo vsebovan v preseku intervalov [_n¹,2n+ 1], n ∈ N. Obratno pa vzemimo poljuben x ∈ T∞

n=1[¹_n,2n + 1] iz preseka, torej zanj velja x ∈ [_n¹,2n + 1] in

1

n < x≤n za vse n∈N. To pa pomeni, da mora biti x∈[1,3].

(a) R\Z, (b) ∅,

(c) (−1,2), (d) [0,1],

(e) (−∞,0), (f) {0}, (g) (0,∞), (h) [1,3].

(i) [−1,∞), (j) [0,1).

4. (a) Pa denimo, da presek ni prazen, t.j. obstaja x∈ T

α∈IA_α. To pa pomeni, da je x∈A_α

(b) Vzamemo element poljubni (a, b)∈ S∞

n=1(A_n×B_n) torej (a, b)∈ (Am×Bm). To pomeni, da je a ∈An0 in b∈ Bn0 za nek n0 ∈N.

Odtod jasno sledi, da je a ∈ S∞

n=1A_n in b ∈ S∞

n=1B_n. S tem je vsebovanost dokazana.

5. Podobno kot v (a) vzemi poljubni (a, b) ∈ T∞

n=1A_n ×S∞ n=1B_n, ter ugotovi, da je potem a ∈An in b ∈ Bn za vse n. Odtod sledi (a, b)∈T∞

n=1(A_n×B_n).

3.2.3 Poten£na mnoºica in kartezi£ni produkt 1. (a) P(A) ={∅,{1},{2},{1,2}},

(b) P(A) ={∅,{1},{{1}},{1,{1}}}, (c) P(A) ={∅,{1},{∅},{1,∅}},

P(B) ={∅,{∅},{{1}},{{∅}},{{1,∅}},{∅,{1}},{∅,{∅}},{∅,{1,∅}}, {{1},{∅}},{{1},{1,∅}},{{∅},{1,∅}},{∅,{1},{∅}},{∅,{1},{1,∅}}, {∅,{∅},{1,∅}},{{1},{∅},{1,∅}},{∅,{1},{∅},{1,∅}}}

(d) P(A) ={∅,{{∅}}},

P(B) ={∅,{∅},{{{∅}}},{∅,{{∅}}}}. 2. (a) elementi P(A): ∅,

podmnoºiceP(A): ∅, {∅}, {{1}},

(b) elementi P(A): ∅, {∅},{{1}}

podmnoºiceP(A): ∅, {∅},

(c) elementi P(A): ∅, {∅},{1, a}, {a}, podmnoºiceP(A): ∅, {∅}, {{1}},

(d) elementi P(A): ∅, {∅},{a},{a,{a}}, {{a,∅}}

podmnoºiceP(A): ∅, {∅}, {{a,∅}}. 3. elementi P(A): ∅, A,

podmnoºice P(A): ∅, {∅},{A},{∅, A}, elementi P(P(A)): ∅, {{∅}}, {A}, {∅, A}

podmnoºice P(P(A)): ∅,{∅}, {A}.

4. Spomni se, da je vsak element poten£ne mnoºice podmnoºica mnoºice N_n, ki bodisi vsebuje neko ²tevilo m ∈ N_n bodisi ga ne vsebuje. Po osnovnem izreku lahko tako podmnoºico mnoºice Nn izberemo na 2ⁿ na£inov.

5. (a) Velja.

Relacija P(A) ⊆ P(B) pomeni, da so vsi elementi mnoºice P(A) tudi elementi mnoºice P(B). Tudi mnoºica A je torej vse- bovana v P(A), kar pomeni, da jeA podmnoºica B.

Obratno, naj bo A ⊂ B. Potem so vse podmnoºice mnoºice A tudi podmnoºiceB, od koder ºe slediP(A)⊆ P(B).

(b) Velja. Sledi neposredno iz denicije prazne in poten£ne mnoºice.

(c) Velja. Opazi, da so elementi mnoºiceP(A)∩ P(B)natanko mno- ºice, ki so hkrati podmnoºice mnoºicA inB, torej presekaA∩B. (d) V splo²nem ne velja. Oglej si primerA ={1} inB ={2}.

(e) V splo²nem ne velja. Opazi naprimer, da je∅vsebovana v mnoºici P(A\B), vendar ni vsebovana v P(A)\ P(B).

6. (a) A×B ={(1,1),(1,∅),(2,1),(2,∅)},

(b) A×A×A={(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2), (2,2,1),(2,2,2)},

(c) A×C = ({1} ×[1,3))∪ {2} ×[1,3), (d) C×C={(x, y)|x, y ∈[01,3)}.

7. Vse enakosti oziroma vsebovanosti pokaºemo na enak na£in, zato si natan£neje oglejmo le primer (e).

Potrebno bo dokazati vsako vsebovanost posebej. Najprej poka- ºimo

(A\B)×(C\D) = (A×C)\((B×C)∪(A×D)).

Vzemimi torej poljuben element(x, y)∈(A\B)×(C\D), torejx∈A\B iny∈C\D. Zaradix∈Ainy∈B velja(x, y)∈A×D, zaradix /∈B in x /∈D pa velja(x, y)∈/ (B×C)∪(A×D).

Obratno vzemimo poljuben(x, y)∈(A×C)\((B×C)∪(A×D)). Jasno je potemx∈Ainy∈C. Ker(x, y)∈/ (B×C)∪(A×D), potem sledi x /∈B im y /∈D.

8. Enakost ne velja; P(A×B)vsebuje podmnoºice A×B, P(A)× P(B) pa so urejeni pari podmnoºic A oziroma B.

3.2.4 Relacije

4. (a) antisimetri£na, tranzitivna, sovisna.

(b) ireeksivna, sovisna.

(c) relacija delne urejenosti.

2. (a) asimetri£na, tranzitivna.

(b) asimetri£na.

(c) simetri£na.

(d) ekvivalen£na;

ekvivalen£ni razredi[x]_R ={x+n|n∈Z}, x∈[0,1).

(e) simetri£na. (aRb pomeni 3|(2a−b) oziroma 2a−b = 3k. Sledi 2b−a= 2(2a−3k)−a= 3a−3k, k∈Z, kar pomeni bRa.) (f) ekvivalen£na; ekvivalen£ni razredi [x]R ={±√

x²+n |n∈Z}. (g) ekvivalen£na; ekvivalen£ni razredi[n, n+ 1), n∈Z.

(h) ekvivalen£na; ekvivalen£ni razredi so premice v ravnini s koeci- entom ²₃.

(i) ekvivalen£na; ekvivalen£ni razredi[x]_R ={x+^√n₂ |n∈Z}. (j) simetri£na.

(k) asimetri£na.

(l) ekvivalen£na; ekvivalen£ni razredi so izhodi²£e, ter kroºnice s sre- di²£em v izhodi²£u.

(m) simetri£na.

(n) ekvivalen£na; ekvivalen£ni razredi so ravnine v prostoru z normalo (1,−1,1).

(o) simetri£na.

(p) reeksivna, simetri£na.

(q) ekvivalen£na;

ekvivalen£ni razredi[p(x)]_R ={q(x) +x⁵k(x)|k polinom }. (r) ekvivalen£na; ekvivalen£ni razredi so mnoºice polinomov z enakimi

ni£lami.

(s) nima nobene od na²tetih lastnosti.

3. (a) Vzemimo poljuben(a, b)∈ R ◦ R⁻¹. Potem obstajac∈X, da je (a, c)∈ R⁻¹in(c, b)∈ R. Odtod sledi(c, a)∈ R in(b, c)∈ R⁻¹, kar pa pomeni (b, a)∈ R ◦ R⁻¹.

(b) Sledi neposredno iz denicij.

(c) Vzemimo take a, b, c, da je aR⁻¹b in bR⁻¹c. Sledi bRa in cRb, zaradi reeksivnost R pa tudi cRa. To pa pomeni aR⁻¹c in tranzitivnost R⁻¹ je dokazana.

Vzemimo sedaj a, b, c, da velja a( R ◦R)b in b( R ◦ R )c. Po deniciji kompozituma obstajata e, f ∈ X, da je aRe, eRb, ter bRf, fRc. Ker je R tranzitivna, dobimo aRb in bRc, kar pomeni a( R ◦ R )c.

(d) Trditev dokaºimo indirektno. Naj torej R ne bo asimetri£na, ter naj obstajata a, b∈ X, da je aRb inbRa. Zaradi tranzitivnosti relacije je potm aRa in R ne more biti ireeksivna.

4. Naj bo najprej R◦T simetri£na. Vzemimo sedaj poljuben(a, b)∈ R◦ T, kar pomeni, da obstajac∈X, da je(a, c)∈ T in(c, b)∈ R. Zaradi simetri£nosti relacij R in T odtod dobimo (c, a) ∈ T in (b, c) ∈ R. To pa pomeni, da je (b, a)∈ T ◦ R. Pokazali smo R ◦ T ⊂ T ◦ R, obratno vsebovanost pa dokaºemo podobno.

3. Sledi neposredno iz denicij.

4. (a) V splo²nem ne. Oglejmo si primer mnoºice s tremi elementiX = {x, y, z}. Naj relacijama ∼₁ in∼₂ zaporedoma pripadata razbitji {{x},{y, z}} in {{x, y},{z}}. Odtod in iz denicije relacije R potem sledi, da je (x, y),(y, z) ∈ R in (x, z)6∈ R, ter zato R ni tranzitivna.

(b) Je ekvivalen£na, kar sledi neposredno iz denicij.

3.2.5 Funkcije in mo£ mnoºic

1. (a) R je funkcija; je surjektivna in ni injektivna,

R⁻¹ ={(3,−2),(1,0),(2,1),(2,−1),(3,2)} ni funkcija, R◦R⁻¹ ={(3,3),(1,1),(2,2)} je funkcija (bijektivna).

(b) R ni funkcija,

R⁻¹ ={(−1,0),(0,1),(1,2),(2,3),(3,2)} je funkcija (niti surjek- tivna niti injektivna),

R◦R⁻¹ ={(−1,−1),(0,0),(1,1),(1,3),(2,2),(3,3)} ni funkcija.

2. (a) Niti surjektivna niti injektivna.

(b) Ni surjektivna, je injektivna.

(c) Ni surjektivna, ni injektivna.

(d) Je bijektivna; inverzna funkcija f⁻¹(x) = ^x+1_x−1. (e) Je bijektivna; inverzna funkcija f⁻¹(x) =

qx+3 x−2. (f) Je surjektivna, ni injektivna

(g) Je injektivna, ni surjektivna. (To£ka (2,1) ni v sliki funkcije.) (h) Ni surjektivna, je injektivna. (Predpisa funkcije sta injektivna in

slikata v soda oziroma liha ²tevila.)

(i) Ni surjektivna, je injektivna. (To£ka(0,0) ni v sliki funkcije, saj ena£bab³+ 2 = 0 nima racionalne re²itve.)

(j) Ni surjektivna, je injektivna.

(k) Je surjektivna, ni injektivna.

(l) Ni surjektivna, je injektivna. (Predpisa funkcije sta injektivna in slikata ²tevila, ki dajo pri deljinju s 3 ostanek 2oziroma 0.) (m) Ni surjektivna, ni injektivna. (To£ka (1,0) ni v sliki funkcije;

f(1,0) =f(2,0) = (0,0).)

(n) Ni surjektivna, je injektivna. (To£ka (−1,0) ni v sliki funkcije.) (o) Je surjektivna, ni injektivna

(p) Ni surjektivna, je injektivna.

(q) Ni surjektivna, ni injektivna. (To£ka 0 ni v sliki funkcije.)

(r) Je surjektivna, ni injektivna. (Za vsakn ∈Njemin({n}∩N) =n.) 3. Vse trditve se dokaºejo na podoben na£in, neposredno preko denicij.

Pokaºimo zato le trditev (c).

Naj bo najprej g ◦f surjektivna. Za poljuben z ∈ Z potem ob- staja x ∈ X, da je z = g(f(x)). Torej se x preslika v z, kar pomeni surjektivnost g. ƒe pa je g ◦f injektivna, potem za poljubna x, y z lastnostjo f(x) =f(y)oziroma g(f(x)) =g(f(y))takoj dobimax=y. 4. (a) f({1,2,3,4}) ={2,4,8}; f(N))so ²tevila, ki so deljiva s 4, ali pa

dajo ostanek2 pri deljenju s6.

f⁻¹({4,8,10})) ={2,3,4}; f⁻¹({(1,−1),(4,8)}) ni smiselno de- nirana.