Funkcije in mo£ mnoºic - 1.1 Resni£nostne tabele

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.

(d) f:R\ {1} →R\ {1}, f(x) = ^x+1_x−1.

(p) f:Z→Z², f(x) = (x², x³).

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). 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)

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),

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))).

(d) Izjava: ∀n: (6|n ⇒(2|n)∧(3|n)).

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.

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.)

3. Uporabimo oznake za sklepe kot v nalogi 2:

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

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.

(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 o izjavi d ni mo£ sklepati ni£esar.

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

1.¬b⇒p predp resni£ne, kar pomeni, da o izjavi d ni mo£ sklepati ni£esar.

7. Re²uj podobno kot naloge 4,5 in6.

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

9. Napravi dokaza s pogojnim sklepom.

10. Izpeljimo izjavo q z analizo primerov:

1.¬q⇒r predp

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

In document 1.1 Resni£nostne tabele (Strani 25-39)