U ˇ
CITELJSKI FAKULTET U SOMBORU
dr Aleksandar Petojevi´c
KURS IZ MATEMATIKE I
TEORIJA I REˇ
SENI ZADACI
Sombor, 2003.
Glava 1
Matematiˇ
cka logika
1.1
Teorija
Definicija 1.
Iskazi su one reˇcenice o kojima ima smisla govoriti da li su
taˇcne ili su netaˇcne (imaju samo jednu iskaznu vrednost).
Notacija 1.
Za oznaˇcavanje iskaza koristimo slova
p, q, r...
.
Definicija 2.
Disjunkcija redom iskaza
p, q
jeste iskaz ”
p
ili
q
”. Dis-
junkcija je netaˇcan iskaz samo ako su i iskaz
p
i iskaz
q
netaˇcni. U svim
ostalim sluˇcajevima je taˇcan iskaz. Disjunkciju ”
p
ili
q
” oznaˇcavamo
p
∨
q
.
Definicija 3.
Konjukcija redom iskaza
p, q
jeste iskaz ”
p
i
q
”. Konjuk-
cija je taˇcan iskaz samo ako su i iskaz
p
i iskaz
q
taˇcni. U svim ostalim
sluˇcajevima je netaˇcan iskaz. Konjukciju ”
p
i
q
” oznaˇcavamo
p
∧
q
.
Definicija 4.
Implikacija redom iskaza
p, q
jeste iskaz ”ako
p
, onda
q
”.
Implikacija je netaˇcan iskaz samo ako je iskaz
p
taˇcan i iskaz
q
netaˇcan.
U svim ostalim sluˇcajevima je taˇcan iskaz. Implikaciju ”ako
p
onda
q
”
oznaˇcavamo
p
⇒
q.
Definicija 5.
Ekvivalencija redom iskaza
p, q
jeste iskaz ”
p
ako i samo ako
q
”. Ekvivalencija je taˇcan iskaz samo ako su i iskaz
p
i iskaz
q
taˇcni ili
iskaz
p
i iskaz
q
netaˇcni. U svim ostalim sluˇcajevima je netaˇcan iskaz.
Ekvivalenciju ”
p
ako i samo ako
q
” oznaˇcavamo
p
⇔
q.
Definicija 6.
Negacija iskaza
p
jeste iskaz ”nije
p
”. Negacija iskaza
p
je
taˇcan iskaz ako je iskaz
p
netaˇcan, a netaˇcan iskaz ako je iskaz
p
taˇcan.
Negaciju ”nije
p
” oznaˇcavamo
¬
p.
1
1.1.
Teorija
3
Napomena 2.
Ako je formula
A
sagrad¯ena od slova
p
1
, p
2
, ...p
n
(ˇsto ´cemo
nadalje oznaˇcavati sa
A
(
p
1
, p
2
, ...p
n
) )
,
tada ona za svaki izbor pomenutih
slova dobija vrednost
>
ili
⊥
.
Poˇsto se radi o ured¯enim n-torkama, takvih
mogu´cnosti imamo
2
n
(varijacije sa ponavljanjem
n
-te klase od
2
elementa).
Na osnovu toga, svakoj formuli
A
(
p
1
, p
2
, ...p
n
)
odgovara jednoznaˇcno istini-
tosna funkcija:
f
(
A
) :
{>
,
⊥}
n
→ {>
,
⊥}
.
Na taj naˇcin dobijamo istinitosne tablice formule, u kojima ´cemo umesto
v
(
p
)
radi jednostavnosti pisati kratko
p.
Definicija 11.
Za formulu
A
kaˇzemo da je tautologija ako za sve vrednosti
svojih iskaznih slova formula
A
ima vrednost
>
(oznaˇcavamo sa
|
=
A
).
Formula koja za sve vrednosti iskaznih slova ima vrednost
⊥
se naziva kon-
tradikcija.
Teorema 1.
Ako je
|
=
A
i
|
=
A
⇒
B
onda je
|
=
B.
Teorema 2.
Ako je
|
=
A
(
p
1
, p
2
, ..., p
n
)
i
B
1
, B
2
, ..., B
n
su iskazne formule,
onda je
|
=
A
(
B
1
, B
2
, ..., B
n
)
.
Teorema 3.
Ako su
A
i
B
formule i
C
formula koja ima formulu
A
kao
podformulu (u oznaci
C
(
A
)
) tada vaˇzi
|
=
A
⇔
B
⇒
(
C
(
A
)
⇔
C
(
B
))
.
Napomena 3.
Da bismo dokazali da je neka formula tautologija moˇzemo
koristiti jedan od slede´ca tri metoda:
1. metod tablice istinitosti (ako u tablici istinitosti u stubcu te formule
imamo sve vrednosti
>
, formula je tautologija),
2. metod svod¯enja na protivreˇcnost (pogodna za formule oblika
A
⇒
B
)
,
3. metod dovod¯enja formule na konjuktivnu formu; opˇsti sluˇcaj se sastoji
u slede´cem:
ako formula
A
sadrˇzi znak
⇔
, taj znak otklanjamo pomo´cu tautologije
(
p
⇔
q
)
⇔
(
p
⇒
q
)
∧
(
q
⇒
p
)
,
zatim znak
⇒
otklanjamo pomo´cu
tautologije
(
p
⇒
q
)
⇔ ¬
p
∨
q.
Sada imamo formulu koja sadrˇzi znakove
∨
,
∧
,
¬
.
Pomo´cu tautologija
p
∨
(
q
∨
r
)
⇔
(
p
∨
q
)
∨
r
p
∧
(
q
∧
r
)
⇔
(
p
∧
q
)
∧
r
4
Glava 1.
Matematiˇ
cka logika
p
∨
(
q
∧
r
)
⇔
(
p
∨
q
)
∧
(
p
∨
r
)
p
∧
(
q
∨
r
)
⇔
(
p
∧
q
)
∨
(
p
∧
r
)
¬
(
p
∨
q
)
⇔ ¬
p
∧ ¬
q
¬
(
p
∧
q
)
⇔ ¬
p
∨ ¬
q
formulu
A
svodimo na formulu oblika
A
1
∧
A
2
∧
...
∧
A
n
(konjuktivna
forma), gde su formule
A
i
,
0
< i < n
+ 1
oblika
p
1
∨
p
2
∨
...
∨
p
k
,
i pri
tome su
p
j
slova ili negacije slova poˇcetne formule
A.
Definicija 12.
Reˇcenicu
”
x
ima svojstvo
B
”
,
gde je
x
objekat odred¯enog
skupa, a
B
je neko svojstvo (relacija) oznaˇcavamo sa
B
(
x
)
.
Uopˇste, ako
je
B
relacija duˇzine
n
nekog odred¯enog skupa, reˇcenicu
”(
x
1
, x
2
, ..., x
n
)
ima
svojstvo
B
”
oznaˇcavamo sa
B
(
x
1
, x
2
, ..., x
n
)
.
Definicija 13.
Reˇcenicu ”Za svaki
x
∈
A, B
(
x
)”
oznaˇcavamo sa
(
∀
x
)
B
(
x
)
,
gde
∀
nazivamo univerzalni kvantifikator.
Reˇcenicu ”Postoji
x
∈
A, B
(
x
)”
oznaˇcavamo sa
(
∃
x
)
B
(
x
)
,
gde
∃
nazivamo
egzistencijalni kvantifikator.
Teorema 4.
Navedeni kvantifikatori zadovoljavaju slede´ce formule:
¬
(
∀
x
)
B
(
x
)
⇔
(
∃
x
)
¬
B
(
x
)
¬
(
∃
x
)
B
(
x
)
⇔
(
∀
x
)
¬
B
(
x
)
(
∀
x
)(
B
(
x
)
∧
C
(
x
))
⇔
(
∀
x
)
B
(
x
)
∧
(
∀
x
)
C
(
x
)
(
∀
x
)(
B
(
x
)
∨
C
(
x
))
⇔
(
∀
x
)
B
(
x
)
∨
(
∀
x
)
C
(
x
)
(
∃
x
)(
B
(
x
)
∧
C
(
x
))
⇔
(
∃
x
)
B
(
x
)
∧
(
∃
x
)
C
(
x
)
(
∃
x
)(
B
(
x
)
∨
C
(
x
))
⇔
(
∃
x
)
B
(
x
)
∨
(
∃
x
)
C
(
x
)
6
Glava 1.
Matematiˇ
cka logika
5)
¬
p,
¬⊥
=
>
.
3.
Odrediti istinitosnu vrednost formula:
1)
(10 : 3
−
1
<
2 + 3
·
2)
∧
(
−
(
−
8
−
4) : 2 = 7)
⇔
(
−
3
−
4
·
4
>
2)
,
2)
(0
,
6 : 0
,
02 = 0
,
3)
⇒
((0
,
1 + 0
,
2
−
0
,
4
>
0
,
5)
∨
(0
,
1
·
0
,
2
<
0
,
3))
,
3)
¬
2
3
−
2
5
<
1
2
⇔
6
7
·
7
8
>
1
2
.
Reˇsenje:
1)
> ∧ ⊥ ⇔ ⊥
=
⊥ ⇔ ⊥
=
>
,
2)
⊥ ⇒
(
⊥ ∨ >
) =
⊥ ⇒ >
=
>
,
3)
¬> ⇔ >
=
⊥ ⇔ >
=
⊥
.
4.
Napisati istinitosnu tablicu za formulu
((
p
⇒
q
)
∨ ¬
r
)
⇔
(
p
⇒
r
)
.
Reˇsenje:
U opˇstem sluˇcaju, neka je broj razliˇcitih iskaznih slova u formuli
n
(Napomena 2). Tada zadatak za jedno, dva, tri ili ˇcetiri razliˇcita slova
poˇcinjemo da reˇsavamo na slede´ci naˇcin:
p
· · ·
> · · ·
⊥ · · ·
p
q
· · ·
> > · · ·
> ⊥ · · ·
⊥ > · · ·
⊥ ⊥ · · ·
p
q
r
· · ·
> > > · · ·
> > ⊥ · · ·
> ⊥ > · · ·
> ⊥ ⊥ · · ·
⊥ > > · · ·
⊥ > ⊥ · · ·
⊥ ⊥ > · · ·
⊥ ⊥ ⊥ · · ·
p
q
r
s
· · ·
> > > > · · ·
> > > ⊥ · · ·
> > ⊥ > · · ·
> > ⊥ ⊥ · · ·
> ⊥ > > · · ·
> ⊥ > ⊥ · · ·
> ⊥ ⊥ > · · ·
> ⊥ ⊥ ⊥ · · ·
⊥ > > > · · ·
⊥ > > ⊥ · · ·
⊥ > ⊥ > · · ·
⊥ > ⊥ ⊥ · · ·
⊥ ⊥ > > · · ·
⊥ ⊥ > ⊥ · · ·
⊥ ⊥ ⊥ > · · ·
⊥ ⊥ ⊥ ⊥ · · ·
