Sveuˇciliˇste u Zagrebu
PMF-Matematiˇcki odjel
Mladen Vukovi´c
MATEMATIˇ
CKA LOGIKA 1
skripta
ˇ
Cetvrto, izmijenjeno i dopunjeno izdanje
Zagreb, svibanj 2007.
doc.dr. sc. Mladen Vukovi´c: Matematiˇcka logika 1
Recenzenti:
dr. sc. Vladimir G. Kirin , redovni profesor, PMF-MO
dr. sc. Zvonimir ˇ
Siki´c, redovni profesor, FSB
Izdavaˇc: PMF-Matematiˇcki odjel,
Sveuˇciliˇste u Zagrebu,
Zagreb, Bijeniˇcka c. 30
Za tisak pripremio:
Mladen Vukovi´c
c
°
Mladen Vukovi´c, 2007.
CIP - Katalogizacija u publikaciji
Nacionalna i sveuˇciliˇsna knjiˇznica, Zagreb
UDK 510.6(075.8)
164(075.8)
VUKOVI ´
C, Mladen
Matematiˇcka logika 1: skripta / Mladen Vukovi´c -
Zagreb: PMF-Matematiˇcki odjel, 2007. - IV,
248
str.; 24cm
Bibliografija: str.
241
- Indeks
ISBN 953-6076-67-5
990326022
ISBN 953-6076-67-5
2.6.3
Sistem prirodne dedukcije za logiku prvog reda . . . . . . 185
2.7 Teorem potpunosti i posljedice . . . . . . . . . . . . . . . . . . . 188
2.7.1
Konzistentnost . . . . . . . . . . . . . . . . . . . . . . . . 188
2.7.2
Generalizirani teorem potpunosti . . . . . . . . . . . . . . 193
2.7.3
Posljedice generaliziranog teorema potpunosti . . . . . . . 198
2.7.4
Ograniˇcenja logike prvog reda . . . . . . . . . . . . . . . . 206
2.7.5
Kategoriˇcnost teorija . . . . . . . . . . . . . . . . . . . . . 208
2.8 Primjeri teorija prvog reda . . . . . . . . . . . . . . . . . . . . . . 211
2.8.1
Teorije s jednakoˇs´cu . . . . . . . . . . . . . . . . . . . . . 211
2.8.2
Peanova aritmetika . . . . . . . . . . . . . . . . . . . . . . 221
2.8.3
Zermelo–Fraenkelova teorija skupova . . . . . . . . . . . . 226
2.9 Ultraprodukti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Bibliografija
241
Indeks
244
Predgovor
Ova skripta iz matematiˇcke logike nastala je na osnovu zabiljeˇski iz kolegija
Ma-
tematiˇcka logika
koji ve´c niz godina predajem na Matematiˇckom odjelu PMF-a
u Zagrebu. Skripta je prije svega namijenjena studentima koji sluˇsaju kolegije
Matematiˇcka logika 1
i
Matematiˇcka logika
. U ovoj skripti nije obuhva´cen dio o
izraˇcunljivosti koji se predaje u ljetnom semestru u kolegiju
Matematiˇcka logika
.
Nadamo se da ´ce knjiga zanimati i sve one koji ˇzele dublje proniknuti u osnove
matematike, ili ˇzele svoje prije steˇceno znanje osvjeˇziti danaˇsnjim pristupom
matematiˇckoj logici.
Osnovna tema skripte je klasiˇcna logika sudova i predikata. Dane su os-
novne definicije i rezultati o intucionistiˇckoj i modalnoj propozicionalnoj logici.
Neklasiˇcne logike kao ˇsto su npr. viˇsevaljana, fuzzy, linearna, beskonaˇcne logike
i logike viˇseg reda, ovdje se zasebno ne prouˇcavaju.
Jedino predznanje, koje se podrazumijeva za ˇcitanje skripte, je neˇsto malo
o naivnoj teoriji skupova. Npr. pojmovi kao ˇsto su: prebrojiv skup, kardinalni
broj i uredeni skup se koriste u knjizi, ali se posebno ne definiraju.
Na kraju svake toˇcke sakupljeni su zadaci koji imaju za cilj upotpuniti
gradivo. Zbog toga su rutinski zadaci (kao ˇsto je npr. ispitivanje valjanosti
formule; odredivanje normalnih formi, ... ) svedeni na najmanju mogu´cu mjeru.
Zahvaljujem se svim prijateljima i kolegama koji su svojim savjetima i suge-
stijama doprinijeli da ova skripta ˇsto prije izade, te da bude kvalitetnija. Svakako
se ˇzelim posebno zahvaliti profesorima Vladimiru G. Kirinu , Zvonimiru ˇ
Siki´cu
i Deanu Rosenzweigu od kojih sam uˇcio matematiˇcku logiku.
Svaki ispravak, ili pak sugestije, koje bi mogle doprinijeti poboljˇsanju ovog
teksta, rado ´cu prihvatiti.
U Zagrebu, svibanj 2007.
Autor
iii
Uvod
Logika
je grˇcka rijeˇc koja oznaˇcava uˇcenje o govoru, rijeˇci, umu, razumu, razlogu,
miˇsljenju, ... Kao primarno znaˇcenje obiˇcno se uzima
govor
.
ˇ
Sto je matematiˇcka logika? Je li matematiˇcka logika zapravo primjena ma-
tematike prilikom logiˇckih zakljuˇcivanja, ili pak neka ”stroˇza” primjena logike
prilikom matematiˇckih dokaza? Je li logika grana matematike, ili obrnuto, ne
slaˇzu se ni svi logiˇcari u odgovoru. Intuicionisti smatraju da su matematiˇcke
konstrukcije osnova, a logiˇcko rasudivanje je sekundarno. Logicisti pak smatraju
da se matematika zasniva na logici, tj. matematika je grana logike. O svemu
tome ´cemo neˇsto detaljnije re´ci kasnije. Jedno je sigurno: matematiˇcka logika
je jedna od matematiˇckih teorija. Neki njeni veliki dijelovi su: teorija skupova,
teorija modela, teorija dokaza, teorija rekurzije, ...
Sada ´cemo navodenjem najvaˇznijih ˇcinjenica iz povijesti zapadno-europske
matematiˇcke logike pokuˇsati opisati njezin nastanak. Na razvitak europske
matematike i miˇsljenja uop´ce gotovo je jedino utjecala grˇcka matematika i filo-
zofija. Povijest logike se moˇze grubo podijeliti na razdoblja stvaranja i razdoblja
zastoja. Stvarni stvaralaˇcki periodi logike su 4. i 3. st. pr.Kr., zatim od 12. do
15. st., te od sredine 19. st. do naˇsih dana. Dakle, podjela povijesti zapadne
logike slijedi pet velikih razdoblja: tri razdoblja stvaranja i dva razdoblja stag-
nacije. Opisat ´cemo kratko redom svako razdoblje. No, uz razvoj matematiˇcke
logike svakako je blisko povezan i razvoj aksiomatske metode u matematici. Za
bolje razumijevanje povijesti matematiˇcke logike ujedno ´cemo i opisivati razvoj
aksiomatske metode.
Poˇcetak grˇcke logike pada u ˇcetvrto stolje´ce pr.Kr. Prvim ve´cim logiˇcarima
smatraju se Parmenid, Zenon, Sokrat, Platon i Euklid iz Megare. Taj period
razvoja dostiˇze vrhunac genijalnim stvaranjem Aristotela
1
Njemu je prvom us-
pjelo sistematizirati metode rasudivanja koje su do tada bile poznate, te je
prouˇcavanjem silogizama
2
pokuˇsao sustavno opisati sva logiˇcka zakljuˇcivanja.
1
Aristotel, 384.–322. pr.Kr.
2
Aristotelova silogistika ima veliku povijesnu vrijednost, jer je bila prvi primjer stroge
izgradnje jednog formalno-logiˇckog sustava. Tijekom dvaju tisu´clje´ca (do pojave matematiˇcke
1
