Download Zapiski iz matematike PDF

TitleZapiski iz matematike
LanguageEnglish
File Size819.8 KB
Total Pages107
Table of Contents
                            Osnove logike
	Uvod v logiko
	Izjave
	Izjavne povezave
	Pravilnostne tabele
	Vrste izjav
	Enakovredne izjave
	Implikacija in ekvivalenca
	Izbrana oblika
	Logicna implikacija in logicna ekvivalenca
	Sklepanje
	Dokazovanje v matematiki
	Predikati in kvantifikatorji
Teorija množic
	Uvod
	Operacije z množicami
	Povezava med izjavami in množicami
Relacije
	Uvod
	Kartezicni produkt
	Relacije
	Tipi relacij
	Ekvivalencna relacija
	Relacije urejenosti
Funkcije
	Lastnosti funkcij
	Operacije s funkcijami
	Inverzna funkcija
	Kardinalnost množic
Kombinatorika
	Osnovna pravila
	Permutacije
	Kombinacije
Grafi
	Osnovni pojmi
	Osnovni primeri grafov
	Izomorfizem grafov
	Dvodelni grafi
	Regularni grafi
	Sprehodi in obhodi
	Drevesa
Matrike
	Osnovni pojmi
	Operacije z matrikami
	Množenje matrik – matricno množenje
	Determinante
	Rang matrike
	Obratna matrika
Sistemi linearnih enacb
	Matricni zapis sistema enacb
	Reševanje sistema linearnih enacb
	Gaussov postopek
	Rang matrike po Gaussovem postopku
	Rešljivost sistemov
	Homogeni sistemi
	Racunanje obratne matrike po Gaussovem postopku
	Uporaba obratne matrike pri reševanju sistemov linearnih enacb
	Cramerjevo pravilo
Vektorski prostori
	Osnovni primeri in definicije
	Vektorski podprostor
	Linearna kombinacija
	Linearna odvisnost
	Baza
	Skalarni produkt v prostoru Vn, norma vektorja, ortogonalnost
                        
Document Text Contents
Page 1

Zapiski iz matematike

doc. dr. Damjan Škulj, Fakulteta za družbene vede

22. november 2011

1 Osnove logike

1.1 Uvod v logiko
Logika je veda, ki proučuje načela pravilnega mišljenja. Proučuje tiste oblike mišljenja, ki nas od znanih
dejstev vodijo do novih spoznanj. Tem miselnim procesom pravimo sklepanje. Pri pravilnem sklepanju
mora vsak korak nedvoumno in objektivno slediti iz prejšnjih.

V matematiki skušamo logične argumente formalizirati v obliki formalnih izjav. Za te skušamo ugo-
toviti pod katerimi pogoji so pravilne in katere posledice iz njih nedvoumno sledijo. Za začetek si bomo
torej ogledali jezik in osnovna pravila formalne logike. Definirali bomo pojem (formalne) izjave in osnovne
načine za sestavljanje izjav v nove izjava, ki jih omogočajo izjavne povezave. Ugotavljanje, pod katerimi
pogoji je neke izjava pravilna, je mogoče s pravilnostnimi tabelami in pravili o enakovrednih izjavah.
Na koncu si bomo ogledali osnovne postopke dokazovanja v matematiki in uporabe kvantifikatorjev pri
tvorjenju izjav.

1.2 Izjave
Osnovni gradnik sklepanja so izjave. Za izjavo štejemo vsako trditev, za katero je mogoče vsaj načeloma
ugotoviti njeno pravilnost. Za vse trditve, ki imajo enak pomen, bomo šteli, da predstavljajo isto izjavo.

Primer 1.1. Primeri izjav:

• Štiri je sodo število.

• Kit je riba.

• Na Zemlji živi 7 milijard ljudi.

Prva izjava je pravilna, druga je nepravilna, o pravilnosti tretje pa ne moremo vedeti z gotovostjo, vendar
je zagotovo pravilna ali nepravilna.

Izjave označujemo z velikimi tiskanimi črkami: A,B,C1, X, . . .. Vsaka izjava v matematični logiki je
lahko pravilna (p) ali napačna (n). Izjave delimo še na:

enostavne izjave so tiste, ki jih ne moremo razčleniti na bolj enostavne;

sestavljene izjave so zgrajene iz enostavnih s pomočjo izjavnih povezav.

1

Page 2

Primer 1.2. V sestavljeni izjavi ’Če sije sonce, je toplo.’ sta enostavni izjavi ’Sije sonce.’ in ’Toplo je.’

V logiki ugotavljamo, kako je s pravilnostjo sestavljenih izjav v odvisnosti od pravilnosti enostavnih izjav,
iz katerih je sestavljena.

1.3 Izjavne povezave
Sestavljene izjave so zgrajene iz enostavnih izjav s pomočjo ene ali več izjavnih povezav. Osnovne izjavne
povezave so negacija, s katero izjavo zanikamo; konjunkcija, ki označuje, da veljata dve izjavi hkrati in
disjunkcija, ki označuje, da velja vsaj ena od navedenih izjav.

Negacija izjave A je izjava, ki jo zapišemo ¬A in pomeni izjavo ’ni res, da velja A’ ali na kratko, ’ne
A’. Negacija pravilne izjave je vselej nepravilna in obratno.

Primer 1.3. Če je izjava A: ’Danes je nedelja.’, je izjava ¬A: ’Danes ni nedelja.’

Konjunkcija je izjavna povezava, ki dvema izjavama A in B priredi novo izjavo A ∧B, ki pomeni ’A in
hkrati B’ ali ’A in B’. Konjunkcija izjav je pravilna natanko takrat, ko sta pravilni obe izjavi.

Primer 1.4. Izjava ’Kit je riba in štiri je sodo število.’ je konjunkcija izjav.

Disjunkcija izjav A in B je izjava, ki jo zapišemo A∨B in pomeni ’A ali B’. (To pomeni, da velja izjava
A ali izjava B ali pa obe hkrati.) Disjunkcija izjav je pravilna natanko takrat, ko je pravilna vsaj ena od
izjav.

Primer 1.5. Izjava ’Danes je sreda ali pa sije sonce.’ je disjunkcija izjav.

Podobno kot pri računskih operacijah s števili moramo tudi pri izjavnih povezavah upoštevati vrstni
red. Velja, da najmočneje veže negacija, nato konjunkcija in nato disjunkcija. Če želimo spremeniti vrstni
red, kot ponavadi uporabimo oklepaje.

Primer 1.6. Izjava ¬A ∨B je enaka izjavi (¬A) ∨B in je različna od izjave ¬(A ∨B).

1.4 Pravilnostne tabele
Kako je pravilnost sestavljene izjave odvisna od pravilnosti enostavnih izjav, ki jo sestavljajo lahko prika-
žemo s pravilnostno tabelo. To sestavljata:

• Nabor vseh možnih vrednosti enostavnih izjav, ki sestavljajo sestavljeno izjavo – določila izjave. Tak
nabor imenujemo prostor izjave. Sestavlja ga 2n določil.

• Pravilnosti sestavljene izjave pri posameznih določilih. Določila, pri katerih je izjava pravilna, se-
stavljajo prostor pravilnosti izjave.

Zapišimo najprej pravilnostne tabele za sestavljene izjave, ki vsebujejo eno od naštetih izjavnih povezav.
Izjavna povezava negacija deluje na eni izjavi, zato njen prostor sestavljata le dve vrednosti.

A ¬A
p n
n p

2

Page 53

?

Slika 22: Prvi graf je dvodelen, drugi pa je lih cikel, zato ga ne moremo pobarvati z dvema barvama.

A B

E

CD

Slika 23: Eulerjev obhod je
na primer zaporedje točk
ADEBCEA.

Sprehod v grafu je tako zaporedje ne nujno različnih točk A1, . . . , Ar,
da velja (Ai, Ai+1) ∈ P za i = 1, . . . , r − 1. Točki A1 in Ar sta krajišči
sprehoda. Če velja A1 = Ar, pravimo takemu sprehodu obhod.

Sprehod (obhod), v katerem se točke sicer ponavljajo, povezave pa
ne, imenujemo enostavni sprehod (obhod). Graf G je povezan, če med
poljubnima točkama A in B obstaja tak sprehod, da sta ti točki njegovi
krajišči.

Eulerjev sprehod (obhod) je tak enostaven sprehod (obhod), ki vse-
buje vse povezave grafa G. Tak graf lahko narišemo z eno potezo, ne da
bi dvignili svinčnik, ali šli dvakrat po isti povezavi.

Izrek 6.2.

1. Graf G ima Eulerjev obhod natanko tedaj, ko so vse njegove točke
sode stopnje.

2. Graf G ima Eulerjev sprehod natanko tedaj, ko ima največ dve
točki z liho stopnjo.

6.7 Drevesa
Povezan graf brez ciklov imenujemo drevo.

Izrek 6.3. Za povezan graf G z n točkami so ekvivalentne naslednje trditve.

1. graf G je drevo;

2. graf G ima natanko n− 1 povezav;

3. če grafu G odstranimo katerokoli povezavo, izgubi povezanost;

4. če grafu G dodamo katerokoli povezavo, dobimo cikel.

53

Page 54

Naloge

1. Nariši grafe K6, P4 in C7.
2. Ugotovi, ali sta grafa v naslednjih parih izomorfna. (Če sta, poišči izomorfizem, če pa nista, to dokaži.)

(a)

A1

A3

A4

A7

A2

A5

A6

A8

in

B1 B2

B3B4

B5 B6

B7B8

(b)

A1 A2

A4A5

A3A6

in C6

3. Za dane grafe ugotovi, ali so dvodelni (navodilo: če je graf dvodelen, pobarvaj njegove točke z belo
in črno barvo tako, da nobeni sosednji točki nista pobarvani z isto barvo; če pa ni dvodelen, poišči v
njem lih cikel); regularni in ali imajo Eulerjev obhod oziroma sprehod.
(a)

A1 A2

A4A6
A3

A5

(b)

B1 B2

B3B4

B5 B6

B7B8

54

Page 106

(c) Npr. b2 =


21

3


 , b3 =


 1−5

1




11. (a) Vektorja b1 in b2 sta linearno neodvisna, b3 pa lahko nadomestimo z vektorjem


00

1


.

(b) Vektorja b1 in b2 sta linearno neodvisna, b3 pa lahko nadomestimo z vektorjem


10

0


.

(c) Vektorja b1 in b2 sta linearno odvisna. Vektor b1 lahko dopolnimo do baze z vektorjema


01

0


 in


00

1


.

12. (a) ‖x‖ =


6, ‖y‖ =


5,d(x,y) =


17, ϕ ≈ 123◦
(b) ‖x‖ =


2, ‖y‖ =


5,d(x,y) =


3, ϕ ≈ 50◦

(c) ‖x‖ =


14, ‖y‖ =


41,d(x,y) =


91, ϕ ≈ 139◦

13. (a) Ortogonalni komplement je enoparametrična družina vektorjev


3t6t
t


 ; t ∈ R.

(b) Ortogonalni komplement je enoparametrična družina vektorjev


−t/198t/19

t


 ; t ∈ R.

(c) Ortogonalni komplement je dvoparametrična družina vektorjev


(s− 2t)/2s

t


 ; s, t ∈ R.

14. (a) Pripadajoča ortonormirana baza je

b1 =
1


5


 10
−2


 , b2 =


01

0


 , b3 = 1√

5


20

1




(b) Pripadajoča ortonormirana baza je

b1 =
1


5


 20
−1


 , b2 = 1√

5


10

2


 , b3 =


01

0




106

Page 107

(c) Pripadajoča ortonormirana baza je na primer

b1 =
1


2


 1−1

0


 ; b2 = 1√

2


11

0


 ; b3 =


00

1




107

Similer Documents