DRˇ
ZAVNI UNIVERZITET U NOVOM PAZARU
DEPARTMAN ZA MATEMATI ˇ
CKE NAUKE
Matematiˇ
cka logika - predavanaja
Emir Zogi´
c
Novi Pazar, 2017/2018. godina
Sadrˇ
zaj
1
Iskazna algebra
3
1.1
Iskazi. Osnovne operacije sa iskazima. . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Iskazna algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Hipoteze i posledice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.4
Iskazne funkcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.5
Baze iskazne algebre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2
Bulove algebre
15
2.1
Aksiome Bulove algebre
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2
Parcijalno ured¯enje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3
Bulovi izrazi i Bulove funkcije . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.4
Izomorfizmi Bulovih algebri . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3
Predikatske formule
23
4
Formalne teorije
31
5
Iskazni raˇ
cun
L
33
5.1
Aksiome i prve posledice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.2
Stav dedukcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
5.3
Osnovne leme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
5.4
Glavna interpretacija. Potpunost. Neprotivureˇ
cnost. Odluˇ
civost . . . . . . . . .
39
6
Kvantifikatorski raˇ
cun prvog reda
K
43
6.1
Aksiome. Neprotivureˇ
cnost. Stav dedukcije . . . . . . . . . . . . . . . . . . . . .
43
7
Teorija skupova
47
7.1
Aksiome ZF teorije skupova . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
7.2
Relacije i funkcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
7.3
Kardinalni brojevi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
1
1
ISKAZNA ALGEBRA
1
Iskazna algebra
1.1
Iskazi. Osnovne operacije sa iskazima.
Definicija 1.1.
Iskaz je reˇ
cenica koja moˇ
ze da bude samo taˇ
cna ili samo netaˇ
cna.
Primer 1.
Navodimo nekoliko primera iskaza:
1. Broj 5 je jednak zbiru brojeva 2 i 3.
2. Broj 3 je manji od broja 2.
3. Za svaki realan broj
x
je
x
= 1
.
Definicija 1.2.
Iskaz ”
p
i
q
”naziva se konjunkcija iskaza
p
i
q
i oznaˇ
cava se sa
p
∧
q
. Ko-
njunkcija iskaza
p
i
q
je taˇ
can iskaz ako su oba iskaza
p
i
q
taˇ
cna, a netaˇ
can iskaz ako je bar
jedan od iskaza
p
i
q
netaˇ
can.
Definicija 1.3.
Iskaz ”
p
ili
q
”naziva se disjunkcija iskaza
p
i
q
i oznaˇ
cava se sa
p
∨
q
. Disjunk-
cija iskaza
p
i
q
je netaˇ
can iskaz ako su oba iskaza
p
i
q
netaˇ
cna, a taˇ
can iskaz u svim ostalim
sluˇ
cajevima.
Definicija 1.4.
Iskaz ”ako
p
, onda
q
”naziva se implikacija, redom, iskaza
p
i
q
i oznaˇ
cava se
sa
p
⇒
q
. Implikacija iskaza
p
i
q
je taˇ
can iskaz u svim sluˇ
cajevima, osim ako je iskaz
p
taˇ
can,
a iskaz
q
netaˇ
can.
Umesto reˇ
cenice ”ako
p
, onda
q
”, upotrebljavaju sesa istim znaˇ
cenjem, i reˇ
cenice: ”iz
p
sledi
q
”, ”
p
povlaˇ
ci
q
”, ”
p
je dovoljan uslov za
q
”i ”
q
je potreban uslov za
p
”.
Definicija 1.5.
Iskaz ”
p
je ekvivalentno
q
”naziva se ekvivalencija iskaza
p
i
q
i oznaˇ
cava se sa
p
⇔
q
. Ekvivalencija iskaza
p
i
q
je taˇ
can iskaz ako su oba iskaza
p
i
q
taˇ
cna, ili oba netaˇ
cna.
Ako je jedan od iskaza
p
i
q
taˇ
can, a drugi netaˇ
can ekvivalencija je netaˇ
can iskaz.
Umesto reˇ
cenice ”
p
je ekvivalentno
q
”takodje se koriste, sa istim znaˇ
cenjem, i reˇ
cenice: ”
p
ako
i samo ako
q
”i ”
p
je potreban i dovoljan uslov za
q
”.
Definicija 1.6.
Iskaz ”nije
p
”naziva se negacija iskaza
p
i oznaˇ
cava se sa
¬
p
. Negacija
¬
p
taˇ
cnog iskaza
p
je netaˇ
can iskaz, a negacija
¬
p
netaˇ
cnog iskaza
p
je taˇ
can iskaz.
Uvedimo sada oznake
>
(ˇ
cita se:
te
) za taˇ
cno,
⊥
(ˇ
cita se:
ne te
) za netaˇ
cno i pojam istinitosne
vrednosti.
Na osnovu gornjih definicija, istinitosne vrednosti konjunkcije, disjunkcije, implikacije, ekviva-
lencije i negacije mogu se, u zavisnosti od istinitosnih vrednosti iskaza
p
i
q
, predstaviti pomo´
cu
3
1
ISKAZNA ALGEBRA
1.2
Iskazna algebra
tablica istinitosti
tih operacija:
τ
(
p
)
τ
(
q
)
τ
(
p
∧
q
)
>
>
>
>
⊥
⊥
⊥
>
⊥
⊥
⊥
⊥
τ
(
p
)
τ
(
q
)
τ
(
p
∨
q
)
>
>
>
>
⊥
>
⊥
>
>
⊥
⊥
⊥
τ
(
p
)
τ
(
q
)
τ
(
p
⇒
q
)
>
>
>
>
⊥
⊥
⊥
>
>
⊥
⊥
>
τ
(
p
)
τ
(
q
)
τ
(
p
⇔
q
)
>
>
>
>
⊥
⊥
⊥
>
⊥
⊥
⊥
>
τ
(
p
)
τ
(
¬
p
)
>
⊥
⊥
>
.
1.2
Iskazna algebra
Definicija 1.7.
Ured¯ena ˇ
sestorka
(
{>
,
⊥}
,
¬
,
∧
,
∨
,
⇒
,
⇔
)
je iskazna algebra ako i samo ako su
operacije
¬
,
∧
,
∨
,
⇒
,
⇔
definisane slede´
cim tablicama
¬
> ⊥
⊥ >
∧
>
⊥
> >
⊥
⊥ ⊥
⊥
∨
>
⊥
> >
>
⊥ >
⊥
⇒ >
⊥
>
>
⊥
⊥
>
>
⇔ >
⊥
>
>
⊥
⊥
⊥
>
.
Definicija 1.8.
Iskazna slova su znaci
p, q, r, . . . , p
1
, q
1
, r
1
, . . . , p
n
, q
n
, r
n
, . . .
a iskazne kon-
stante znaci
>
i
⊥
.
Definicija 1.9.
1
0
Iskazna slova i iskazne konstante su iskazne formule.
2
0
Ako su
A
i
B
iskazne formule, tada su
¬
A
,
(
A
∧
B
)
,
(
A
∨
B
)
,
(
A
⇒
B
)
i
(
A
⇔
B
)
iskazne
formule.
3
0
Iskazne formule se grade samo konaˇ
cnom primenom delova
1
0
i
2
0
ove definicije.
Primer 2.
Prema prethodnoj definiciji,
p, q
6
,
>
,
(
¬
p
∧
q
)
,
((
p
∧
q
)
⇒
p
)
,
¬⊥
,
((
p
⇒ >
)
∧
(
p
∨
¬
q
))
su formule, dok
¬
, p
∨ ∨
, p
¬
,
((
p
∧
nisu formule.
Konjunkcija formula
A
1
, . . . , A
n
u oznaci
A
1
∧
. . .
∧
A
n
, je formula
A
1
za
n
= 1 i formula
(
A
1
∧
. . .
∧
A
n
−
1
)
∧
A
n
za
n >
1.
Na sliˇ
can naˇ
cin se definiˇse proˇsirena disjunkcija.
Vrednost neke iskazne formule
F
(oznaˇ
cava se sa
τ
(
F
)), zavisi od vrednosti njenih iskaznih slova.
Vrednost iskaznih slova
u
1
, u
2
, . . . , u
n
je ured¯ena
n
−
torka konstanti
>
i
⊥
. Takvih
n
−
torki ima
2
n
. Na primer, vrednosti iskaznih slova
p, q, r
su
(
>
,
>
,
>
)
,
(
>
,
>
,
⊥
)
,
(
>
,
⊥
,
>
)
,
(
>
,
⊥
,
⊥
)
,
(
⊥
,
>
,
>
)
,
(
⊥
,
>
,
⊥
)
,
(
⊥
,
⊥
,
>
)
,
(
⊥
,
⊥
,
⊥
)
.
4
1
ISKAZNA ALGEBRA
1.3
Hipoteze i posledice
6.
(
p
⇒
q
)
⇒
(
¬
q
⇒ ¬
p
)
- zakon kontrapozicije
7.
p
∨
p
⇔
p, p
∧
p
⇔
p
- zakon idempotencije za
∨
i
∧
8.
p
∨
q
⇔
q
∨
p, p
∧
q
⇔
q
∧
p
- zakon komutativnosti za
∨
i
∧
9.
p
∨
(
q
∨
r
)
⇔
(
p
∨
q
)
∨
r
,
p
∧
(
q
∧
r
)
⇔
(
p
∧
q
)
∧
r
- zakon asocijativnosti za
∨
i
∧
10.
p
∨
(
p
∧
q
)
⇔
p, p
∧
(
q
∨
r
)
⇔
p
- zakoni apsorpcije
11.
p
∨
(
q
∧
r
)
⇔
(
p
∨
q
)
∧
(
p
∨
r
)
,
p
∧
(
q
∨
r
)
⇔
(
p
∧
q
)
∨
(
p
∧
r
)
- zakoni distributivnosti
12.
¬
(
p
∨
q
)
⇔ ¬
p
∧ ¬
q
,
¬
(
p
∧
q
)
⇔ ¬
p
∨ ¬
q
- De Morganovi zakoni
1.3
Hipoteze i posledice
Neka je
F
skup formula iskazne algebre i naka je
A
formula iskazne algebre.
Definicija 1.12.
Formula
A
je (semmantiˇ
cka) posledica skupa formula F ako i samo ako za sve
vrednosti iskaznih slova koja uˇ
cestvuju u F i
A
, vaˇ
zi: ako sve formule skupa
F
imaju vrednost
>
tada i formula
A
ima vrednost
>
.
Iskazne formule iz F se u tom sluˇ
caju zovu pretpostavke ili hipoteze. ˇ
Cinjenicu da je formula
A
posledica skupa formula F zapisujemo u obliku F
|
=
A
.
Kako po definiciji konjunkcije formula
F
1
∧ · · · ∧
F
n
ima vrednost
>
ako i samo ako sve formule
F
1
, . . . , F
n
imaju vrednost
>
, to vaˇ
zi
{
F
1
, . . . , F
n
} |
=
F
ako i samo ako
F
1
∧
. . .
∧
F
n
|
=
F
.
Umesto
{
F
1
, . . . , F
n
} |
=
F
piˇse se kra´
ce
F
1
, . . . , F
n
|
=
F
.
Komentar 1.1.
Iz prethodne definicije proizilazi
F
1
, . . . , F
n
|
=
F
i u sluˇ
caju kada ne postoji
nijedna vrednost uˇ
cestvuju´
cih slova za koju su sve formule
F
1
, . . . , F
n
taˇ
cne.
Primer 4.
Formula
¬
q
⇒ ¬
p
je posledica formule
p
⇒
q
.
Zaista, iz tablice istinitosti
p
q
¬
p
¬
q p
⇒
q
¬
q
⇒ ¬
p
>
>
⊥
⊥
>
>
>
⊥
⊥
>
⊥
⊥
⊥
>
>
⊥
>
>
⊥
⊥
>
>
>
>
se vidi da formula
p
⇒
q
ima vrednost
>
u taˇ
cno tri sluˇ
caja i u svakom od njih i formula
¬
q
⇒ ¬
p
ima vrednost
>
. Dakle,
p
⇒
q
|
=
¬
q
⇒ ¬
p
.
Tvrd
¯enje 1.2.
Neka su
F
1
, . . . , F
n
, F
iskazne formule. Tada vaˇ
zi
F
1
, . . . , F
n
|
=
F
ako i samo ako
|
=
F
1
∧ · · · ∧
F
n
⇒
F.
6
