Departman za matematiku i informatiku
Prirodno-
matematič
ki fakultet
Univerzitet u Novom Sadu
Matematička logika
Madarász Sz. Rozália
Novi Sad, novembar 2012.
Predgovor
Ovaj tekst je pomo´
cni materijal koji sluˇ
zi da studentima olakˇ
sa pra´
cenje kur-
seva
Matematiˇ
cka logika
odnosno
Matematiˇ
cka logika u raˇ
cunarstvu
na Departmanu za matematiku i informatiku PMF Univerziteta u Novom
Sadu. On nije dovoljan da bi se kursevi savladali u potpunosti, jer ne sadˇ
zi
zadatke, a ˇ
cesto nedostaju i primeri koji bi ilustrovali date pojmove odnosno
teoreme. Navedene kurseve je, naravno, najlakˇ
se savladati tako ˇ
sto se re-
dovno pohad¯a nastava (predavanja i veˇ
zbe) i koristi dopunska literatura. No,
iskustvo pokazuje da izvestan broj studenata nije u mogu´
cnosti da pohad¯a
nastavu, pa ove skripte sluˇ
ze umesto (tud¯ih) beleˇ
ski sa predavanja.
Grubo govore´
ci, kurs
Matematiˇ
cka logika
, koji se pod raznim nazivima
sluˇ
sa na osnovnim ili master studijama matematike, oslanja se na poglavlja
1, 2 i 4, a kurs
Matematiˇ
cka logika u raˇ
cunarstvu
na poglavlja 1, 2
i 3. No, predavanja iz navedenih kurseva se svake godine prilagod¯avaju
sluˇ
saocima, u zavisnosti od predznanja i zainteresovanosti, pa shodno tome,
ove skripte ´
ce ponekad biti presiromaˇ
sne u odnosu na pokriveni materijal, a
opet neke godine se ne stigne da se obradi svaka tema koja je ovde navedena.
Na kraju, shvatite ovaj materijal kao ”ˇ
zivo bi´
ce”, koje ´
ce vremenom
rasti, menjati se i poboljˇ
savati. Nikako ga ne treba shvatiti kao neˇ
sto ˇ
sto
je zavrˇ
seno i spremno za ˇ
stampu.
Savetujemo takod¯e da se poseti sajt
http://sites.dmi.rs/personal/madaraszr/ i proveri ima li neˇ
sto ˇ
sto bi moglo
biti od koristi ˇ
citaocu prilikom spremanja ispita iz navedenih kurseva.
Roz´
alia Sz. Madar´
asz
1
Sadrˇ
zaj
1
Iskazna logika
7
1.1
Poˇ
ceci logike i matematiˇ
cke logike
. . . . . . . . . . . . . . .
7
1.2
Logika iskaza . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3
Sintaksa iskazne logike . . . . . . . . . . . . . . . . . . . . . .
10
1.4
Interpretacije . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.5
Tautologije, logiˇ
cka ekvivalencija . . . . . . . . . . . . . . . .
14
1.6
Normalne forme i baze iskazne algebre . . . . . . . . . . . . .
18
1.7
Modeli i teorije . . . . . . . . . . . . . . . . . . . . . . . . . .
21
1.8
Logiˇ
cka (semantiˇ
cka) posledica . . . . . . . . . . . . . . . . .
24
1.9
Semantiˇ
cki tabloi . . . . . . . . . . . . . . . . . . . . . . . . .
26
1.10 Deduktivni sistemi . . . . . . . . . . . . . . . . . . . . . . . .
30
1.11 Iskazni raˇ
cun - deduktivni sistem za iskaznu logiku . . . . . .
33
1.12 Mala teorema kompletnosti i odluˇ
civost iskaznog raˇ
cuna . . .
41
1.13 Teorema kompletnosti i kompaktnost . . . . . . . . . . . . . .
44
1.14 Rezolucija u iskaznoj logici
. . . . . . . . . . . . . . . . . . .
50
2
Predikatska logika
57
2.1
O predikatskoj logici . . . . . . . . . . . . . . . . . . . . . . .
57
2.2
Sintaksa predikatske logike
. . . . . . . . . . . . . . . . . . .
59
2.3
Semantika predikatske logike
. . . . . . . . . . . . . . . . . .
61
3
4
Sadrˇ
zaj
2.4
Operatori Mod i Th, semantiˇ
cke posledice . . . . . . . . . . .
66
2.5
Valjane formule . . . . . . . . . . . . . . . . . . . . . . . . . .
68
2.6
Preneksna forma i skolemizacija . . . . . . . . . . . . . . . . .
74
2.7
Rezolucija u predikatskoj logici -Uvod . . . . . . . . . . . . .
79
2.8
Klauzalna forma i Erbranova teorema
. . . . . . . . . . . . .
80
2.9
Rezolucija u predikatskoj logici . . . . . . . . . . . . . . . . .
84
2.10 Rezolucija u predikatskoj logici - Primeri . . . . . . . . . . . .
88
2.11 Predikatski raˇ
cun kao deduktivni sistem . . . . . . . . . . . .
92
2.12 Pouzdanost i kompletnost predikatskog raˇ
cuna
. . . . . . . .
99
2.13 Predikatska logika sa jednakoˇ
s´
cu . . . . . . . . . . . . . . . . 104
3
Temporalne logike
109
3.1
Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.2
Sintaksa i semantika PTL . . . . . . . . . . . . . . . . . . . . 110
3.3
Linear time propositional temporal logic . . . . . . . . . . . . 113
3.4
Deduktivni sistem za linear time propositional temporal logic 116
4
Skupovi, ordinali, kardinali
121
O paradoksima u matematici . . . . . . . . . . . . . . . . . . . . . 121
Naivna teorija skupova i paradoksi . . . . . . . . . . . . . . . . . . 123
Kako izbe´
ci paradokse u teoriji skupova . . . . . . . . . . . . . . . 125
Malo filozofije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
ZF sistem aksioma za teoriju skupova
. . . . . . . . . . . . . . . . 130
Operacije sa skupovima . . . . . . . . . . . . . . . . . . . . . . . . 134
Relacije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Funkcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Aksioma izbora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
ured¯eni skupovi - Osnovne definicije . . . . . . . . . . . . . . . . . 141
Induktivnost i dobro ured¯eni skupovi . . . . . . . . . . . . . . . . . 146
