IV i V dvoqas veжbi — Vladimir Balti
3. Predikatski raqun
Teorijski uvod
Od iskaza (predikata) mogu se formirati nove reqenice upotrebom kvantifikatora. Postoje 2 kvantifikatora:
∀ je univerzalni kvantifikator, koji se qita ,,svaki“ (ili ,,za svaki“ ili ,,bilo koji“ ili ,,proizvoƩni“);
∃ je egzistencijalni kvantifikator, koji se qita ,,postoji“ (ili ,,neki“ ili ,,za neki“ ili ,,bar jedan“).
Primetimo da je simbol ∀ u stvari naopako slovo A i to je direktno povezano sa poqetnim slovom
nemaqke reqi ”Alle”, odnosno engleske ”all” (svi).
Simbol ∃ u stvari naopako slovo E i to je direktno povezano sa poqetnim slovom nemaqkog izraza
”Es gibt”, odnosno engleske reqi ”exist” (postoji).
Sada emo dati nekoliko primera reqenica koje sadrжe kvantifikatore, kao i Ƭihove formule.
Primer 1. Napisati odgovrajuu formulu i odrediti istinitosnu vrednost za svaku od sledeih formula:
• ,,Postoji objekat jednak samom sebi.“
• ,,Svaki prirodan broj je i realan.“
• ,,Neki celi brojevi su vei od 8.“
• ,,Kvadrat proizvoƩnog realnog broja je negativan.“
• ,,Jednaqina x2 = 1 ima rexeƬa u skupu prirodnih brojeva.“
• ,,Razlika bilo koja dva prirodna broja je prirodan broj.“
• ,,Ne postoji najvei prirodan broj.“
• ,,Za svaki racionalan broj x postoji racionalan broj y takav da je x + y = 0.“
• ,,Realan niz (xn ) je konvergentan ako i samo ako postoji realan broj a takav da za svako ε > 0 postoji
prirodan broj N tako da je |xn − a| < ε kad god je n > N .“
RexeƬe.
,,Postoji objekat jednak samom sebi“ prevodimo kao (∃x) x = x. Ova formula je taqna.
,,Svaki prirodan broj je i realan“ prevodimo kao (∀x) (x ∈ N ⇒ x ∈ R). Skraeni zapis ove formule je
(∀x ∈ N) x ∈ R. I ova formula je taqna jer je N ⊆ R.
,,Neki celi brojevi su vei od 8“ prevodimo kao (∃x) (x ∈ Z ∧ x > 8). Skraeni zapis ove formule je
(∃x ∈ Z) x > 8. Kako postoji, npr. ceo broj x = 9 > 8, ova formula je taqna.
,,Kvadrat proizvoƩnog realnog broja je negativan“ prevodimo kao (∀x) (x ∈ R ⇒ x < 0). Skraeni zapis ove
formule je (∀x ∈ R) x < 0. Ova formula nije taqna jer za, npr. x = 1 ne vaжi x2 = 1 < 0.
,,Jednaqina x2 = 1 ima rexeƬa u skupu prirodnih brojeva“ prevodimo kao (∃x) (x ∈ N ∧ x2 = 1). Skraeni
zapis ove formule je (∃x ∈ N) x2 = 1. Ova formula je taqna, jer postoji rexeƬe x = 1 ∈ N (nema veze xto drugo
rexeƬe ove jednaqine, x = −1, nije prirodan broj, jer se nama traжi da jednaqina ima bar jedno rexeƬe u
skupu prirodnih brojeva).
,,Razlika bilo koja dva prirodna broja je prirodan broj“ prevodimo kao (∀x)(∀y) (x ∈ N ∧ y ∈ N ⇒ x − y ∈ N).
Skraeni zapis ove formule je (∀x, y ∈ N) x − y ∈ N. Ova formula nije taqna jer za, npr. x = 1 i y = 2 ne vaжi
x − y = −1 ∈ N.
,,Ne postoji najvei prirodan broj“ prevodimo kao q(∃x) x ∈ N ∧ (∀y)(y ∈ N ⇒ y 6 x) . Skraeni zapis ove
formule je q(∃x ∈ N)(∀y ∈ N) y 6 x. Kako za ma koliko veliko x uzeli, postoji vei prirodan broj, npr.
y = x + 1 ∈ N, to ne postoji najvei prirodan broj, pa je ova reqenica taqna.
,,Za svaki racionalan broj x postoji racionalan broj y takav da je x + y = 0“ prevodimo na sledei naqin
(∀x) x ∈ Q ⇒ (∃y) (y ∈ Q ∧ x + y = 0) . Skraeni zapis ove formule je (∀x ∈ Q)(∃y ∈ Q) x + y = 0. Ova formula je taqna jer za svaki racionalan broj x postoji suprotan broj y = −x ∈ Q za koji vaжi x+y = x+(−x) = 0.
Definiciju konvergentnog niza prevodimo
kao:
Niz (xn ) je konvergentan ⇔ (∃a) a ∈ R ∧ (∀ε) ε > 0 ⇒ (∃N ) N ∈ N ∧ (∀n) (n ∈ N ⇒ (n > N ⇒ |xn − a| < ε)
.
Skraeni zapis je: Niz (xn ) je konvergentan ⇔ (∃a ∈ R)(∀ε > 0)(∃N ∈ N)(∀n ∈ N) (n > N ⇒ |xn − a| < ε).
Ovo je definicija, dok za desnu stranu odreujemo istinitosnu vrednost u zavisnosti od niza (xn ).
1
Napomena. Kako biste preveli reqenicu ,,Jednaqina x2 = 1 ima rexeƬa u skupu prirodnih brojeva.“?
Negacija reqenica sa kvantifikatorima se vrxi na sledei naqin:
q(∀x) P (x) ⇔ (∃x) q P (x)
i
q(∃x) P (x) ⇔ (∀x) q P (x).
Primer 2. ,,Proterajmo“ negaciju kroz formulu za reqenicu ,,Ne postoji najvei prirodan broj“.
RexeƬe.
Koristiemo gorƬe formule i De Morganove zakone, kao i da je p ⇒ q = q p ∨ q. Sledee formule
su ekvivalentne:
q(∃x) x ∈ N ∧ (∀y)(y ∈ N ⇒ y 6 x)
(∀x) q x ∈ N ∧ (∀y)(y ∈ N ⇒ y 6 x)
(∀x) q(x ∈ N) ∨ q (∀y)(y ∈ N ⇒ y 6 x)
(∀x) q(x ∈ N) ∨ (∃y) q(y ∈ N ⇒ y 6 x)
(∀x) q(x ∈ N) ∨ (∃y) q q(y ∈ N) ∨ y 6 x
(∀x) q(x ∈ N) ∨ (∃y) (y ∈ N ∧ y > x)
(∀x) x ∈ N ⇒ (∃y) (y ∈ N ∧ y > x) .
Ovde smo formalno pokazali da je formula q(∃x ∈ N)(∀y ∈ N) y 6 x jednaka (∀x ∈ N)(∃y ∈ N) y > x, tj. da se i u
skraenom obliku prilikom negiraƬa kvantifikatori meƬaƬu.
Od sada emo formule sa kvantifikatorima uglavnom pisati u skraenom obliku (sem kad imamo uopxtenu
predikatsku formulu i treba ispitati Ƭenu isitinitosnu vrednost).
Primer 3. Napisati definiciju divergentnog niza (niz je divergentan ako nije konvergentan).
RexeƬe.
Ovde je potrebno negirati formulu (∃a ∈ R)(∀ε > 0)(∃N ∈ N)(∀n ∈ N) n > N ⇒ |xn − a| < ε. Znaqi,
Niz (xn ) je divergentan ⇔ (∀a ∈ R)(∃ε > 0)(∀N ∈ N)(∃n ∈ N) (n > N ∧ |xn − a| > ε).
Primer 4. 1. zadatak, decembarski rok 2008.
Odrediti istinitosnu vrednost predikatskih formula:
a) ∃x(x ∈ Z ∧ 3x = 8)
b) ∃x(x ∈ Q ∧ 3x = 8)
v) (∀x ∈ N)(∃y ∈ N)(x 6 y)
g) (∃y ∈ N)(∀x ∈ N)(x 6 y)
d) (∀x, y, z ∈ R)(x = y ⇒ xz = yz)
) (∀x, y, z ∈ R)(xz = yz ⇒ x = y).
RexeƬe.
a) Formula ∃x(x ∈ Z ∧ 3x = 8) nije taqna jer ne postoji vrednost x ∈ Z za koju je 3x = 8 (rexeƬe
ove jednaqine je x = 38 6∈ Z).
b) Formula ∃x(x ∈ Q ∧ 3x = 8) je taqna jer postoji vrednost x =
3
8
∈ Q za koju je 3x = 8.
v) Formula (∀x ∈ N)(∃y ∈ N)(x 6 y) je taqna jer za svaki prirodan broj x moжemo odabrati vei (ili jednak)
prirodan broj, npr. y = x + 1.
g) Formula (∃y ∈ N)(∀x ∈ N)(x 6 y) nije taqna jer ne postoji najvei prirodan broj. Ako bi pretpostavili je
formula taqna, onda bi postojao broj y0 , takav da za svaki prirodan broj x vaжi x 6 y0 (xto nije taqno, npr.
za x = 2 · y0 ).
d) Formula (∀x, y, z ∈ R)(x = y ⇒ xz = yz) je taqna jer ako jednakost x = y pomnoжimo istim realnim brojem
z dobijamo jednakost xz = yz.
) Formula (∀x, y, z ∈ R)(xz = yz ⇒ x = y) nije taqna jer ne vaжi za sve realne brojeve. Kontraprimer je
x = 3, y = 5 i z = 0; tada imamo da je xz = yz = 0, tj. v(xz = yz) = 1, dok je x 6= y, pa vaжi v(x = y) = 0, pa se
formula svodi na 1 ⇒ 0, xto nije taqno.
Napomena. Iz delova pod a) i b) vidimo da je bitno na kom skupu se dexava formula (ista formula, a
razliqit skup u ova 2 dela zadatka daje razliqite istinitosne vrednosti).
Iz delova pod v) i g) vidimo da je veoma bitan redosled kvantifikatora! DetaƩnije emo razmatrati
redosled kvantifikatora nakon ove napomene i uvoeƬa jox nekih pojmova.
Iz dela pod ) vidimo da ne smemo skratiti izraz sa z jer to z moжe biti jednako 0.
Primetimo da ako vaжi tvreƬe (∀x) P (x), da onda vaжi i tvreƬe (∃x) P (x) (ako vaжi za sve vrednosti
x onda vaжi i za bar jednu vrednost x!).
Sliqan rezon moжemo primeniti kada razmatramo meusobne odnose predikatskih formula koje imaju 2
kvantifikatora.
2
Definicija 1. Formula F je taqna pri interpretaciji I ako pri toj interpretaciji ima uvek vrednost 1
(nezavisno od parametara odgovarajueg predikata).
Meutim, postoje i formule koje su taqne pri svim interpretacijama. Tako, npr. ako u jednoj tautologiji
svako iskazno slovo zamenimo nekom formulom kvantifikatorskog raquna i novodobijena formula e biti
uvek taqna.
Definicija 2. Formula koja je taqna pri svim interpretacijama naziva se vaƩana formula.
Jedna promenƩiva moжe u nekoj formuli F da se javi vixe puta.
pojavƩivaƬa, uvexemo pojmove slobodnih i vezanih promenƩivih.
U zavisnosti od toga kakva su ta
Definicija 3. PojavƩivaƬe promenƩive x je vezano ako je ono neposredno posle kvantifikatora (koji
deluje na tu promenƩivu) ili je u zoni dejstva nekog kvantifikatora (zona dejstva se proxiruje ubacivaƬem
zagrada!). Svako pojavƩivaƬe promenƩive x u formuli F je slobodno ako nije vezano.
PromenƩive qija su sva pojavƩivaƬa vezana (tzv. vezane promenƩive) ne pojavƩuju se kao parametri predikata
koji predstavƩa interpretaciju formule. Formula u kojoj su sve promenƩive vezane naziva se zatvorena
formula.
Vratimo se sada na redosled kvantifikatora.
Redosled navoeƬa istorodnih kvantifikatora nije bitan. Tako, na primer, formula (∀x)(∀y) ϕ(x, y)
predstavƩa isto xto i formula (∀y)(∀x) ϕ(x, y), jer i u jednom i u drugom sluqaju moramo da proverimo
formulu ϕ(x, y) po svim parovima (x, y). Stoga je formula (∀x)(∀y) ϕ(x, y) ⇔ (∀y)(∀x) ϕ(x, y) vaƩana.
Potpuno analogno, imamo i da je formula (∃x)(∃y) ϕ(x, y) ⇔ (∃y)(∃x) ϕ(x, y) vaƩana.
U Primeru 4 smo dobili da je formula pod v) taqna, a pod g) nije (tu su dva kvantifikatora samo
promenila mesto!). Sada emo ovaj sluqaj i sve ostale objediniti u naredno razmatraƬe.
Posmatrajmo formule oblika
F = K1 K2 ϕ(x, y),
gde su K1 i K2 kvantifikatori (univerzalni i/ili egzistencijalni) spregnutih sa x ili y. Ovakvih formula
ima ukupno 8 i na narednoj slici predstavƩaju qvorove grafa1 . Za 2 formule F1 i F2 koje su ovog tipa imamo
da vaжi:
formula F1 ⇒ F2 je vaƩana akko u sledeem grafu postoji put (po strelicama) iz qvora F1 u qvor F2 .
(∃x)(∃y)
(∃y)(∃x)
(∀x)(∃y)
(∀y)(∃x)
(∃y)(∀x)
(∃x)(∀y)
(∀x)(∀y)
(∀y)(∀x)
Sada emo dati qemu su jednaki neki jednostavniji izrazi koji sadrжe jedan kvantifikator i jednakost sa
osnovnim skupovnim, odnosno brojevnim, operacijama. U tablici podrazumevamo da je A 6= ∅. Tako naprimer,
drugi izraz (∀x ∈ P(A)) x = y ∩ z = 0, u sluqaju A = ∅ postaje (∀x ∈ P(A)) x = y ∩ z = 1!
(∃x ∈ P(A)) x = y ∩ z
1
(∀x ∈ P(A)) x = y ∩ z
(∃y ∈ P(A)) x = y ∩ z
x⊆z
(∀y ∈ P(A)) x = y ∩ z
(∃x ∈ P(A)) x = y ∪ z
1
(∀x ∈ P(A)) x = y ∪ z
(∃y ∈ P(A)) x = y ∪ z
z⊆x
(∀y ∈ P(A)) x = y ∪ z
0
(
1,
0,
x=z=∅
= (x = ∅) ∧ (z = ∅)
inaqe
0
(
1,
0,
x=z=A
= (x = A) ∧ (z = A)
inaqe
1 Pojmovi Teorije grafova poput qvora i grane bie strogo matematiqki uvedeni kasnije, za sada qvorove moжemo zamixƩati
kao neke taqkice koje odgovaraju nekim elementima, a grane grafa kao strelice koje spajaju te taqkice.
3
(∃x ∈ N, N0 , Z, Q, R) x = y + z
(∃y ∈ N) x = y + z
(∃y ∈ N0 ) x = y + z
(∃y ∈ Z, Q, R) x = y + z
(∃x ∈ N) x = y − z
(∃x ∈ N0 ) x = y − z
(∃x ∈ Z, Q, R) x = y − z
(∃y ∈ N, N0 , Z, Q, R) x = y − z
(∃z ∈ N) x = y − z
(∃z ∈ N0 ) x = y − z
(∃z ∈ Z, Q, R) x = y − z
(∃x ∈ N, N0 , Z, Q, R) x = y · z
(∃y ∈ N, N0 , Z) x = y · z
(∃y ∈ Q, R) x = y · z
(∃x ∈ N) x = y : z
(∃x ∈ N0 , Z) x = y : z
(∃x ∈ Q, R) x = y : z
(∃y ∈ N) x = y : z
(∃y ∈ N0 , Z, Q, R) x = y : z
(∃z ∈ N) x = y : z
(∃z ∈ N0 , Z) x = y : z
(∃z ∈ Q, R) x = y : z
1
x>y
x>y
1
y>z
y>z
1
1
y>x
y>x
1
1
z|x
x = 0 ∨ z 6= 0
z|y
z | y ∧ z 6= 0
z 6= 0
1
z 6= 0
x|y
x | y ∧ q (x 6= 0 ∧ y = 0)
x=0 ⇔ y=0
(∀x ∈ N, N0 , Z, Q, R) x = y + z
(∀y ∈ N, N0 , Z, Q, R) x = y + z
0
0
(∀x ∈ N, N0 , Z, Q, R) x = y + z
0
(∀y ∈ N, N0 , Z, Q, R) x = y − z
(∀z ∈ N, N0 , Z, Q, R) x = y + z
0
0
(∀x ∈ N, N0 , Z, Q, R) x = y · z
(∀y ∈ N) x = y · z
(∀y ∈ N0 , Z, Q, R) x = y · z
(∀x ∈ N, N0 , Z, Q, R) x = y · z
0
0
(x = 0) ∧ (z = 0)
0
(∀y ∈ N, N0 , Z, Q, R) x = y : z
0
(∀z ∈ N, N0 , Z, Q, R) x = y : z
0
Ovde je relacija deƩivosti a | b uvedena kao
a|b
def
⇐⇒
(∃k ∈ Z) b = a · k.
Sa tako uvedenom relacijom deƩivosti imamo da i nula deli nulu, tj. 0 | 0.
Kada koristite prethodne jednakosti (ekvivalencije) na kolokvijumu ili ispitu TREBA DATI KRAE
OBRAZLOЖEƫE!
Npr. pokaжimo prve tri jednakosti sa brojevnim operacijama.
• (∃x ∈ N) x = y + z ⇔ 1
kako za svaka 2 prirodna broja y i z, postoji i Ƭihov zbir (i on je takoe prirodan broj), to e uvek
postojati prirodan broj x = y + z.
• (∀x ∈ N) x = y + z ⇔ 0
izraz y + z ima jednu fiksiranu vrednost, za unapred odreene prirodne brojeve y i z, dok na levoj
strani jednakosti x uzima vrednost svakog prirodnog broja, pa stoga data jednakost ne moжe biti taqna
za svako x.
• (∃y ∈ N) x = y + z ⇔ x > y
kako je y = x − z, to za unapred odreene prirodne brojeve x i z uvek moжemo odrediti y tako da vaжi
jednakost x = y + z, ali to y jox mora biti i prirodan broj, tj. y = x − z ∈ N. To je ispuƬeno ako i samo
ako je x > y.
4
Zadaci
1. 11. Domai zadaci 2009. Odrediti istinitosnu vrednost predikatskih formula:
a) ∃x(x ∈ Z ∧ x2 − 3x + 5 = 0);
b) ∃x(x ∈ C ∧ x2 − 3x + 5 = 0);
v) (∀x, y ∈ N)(∃z ∈ N)(x 6 y ⇒ x 6 z ∧ z 6 y);
g) (∀x, y ∈ N)(∃z ∈ N)(x < y ⇒ x < z ∧ z < y);
d) ∀X ∈ P(A) ∃Y ∈ P(A) (X ⊆ Y ) ∧ Y 6= ∅.
b) v(F
v) v(F ) = 1;
g) v(F ) = 0;
( ) = 1;
0, Y = ∅
d) Kada je A 6= ∅ imamo v(F ) =
, a za A = ∅ je v(F ) = 0.
1, Y 6= ∅
RexeƬe.
a) v(F ) = 0;
2. 1. zadatak, septembarski rok, 2008. Odrediti istinitosnu vrednost predikatske formule
(∀x) q α(z, a) ∧ (∃z) α f (x, y), z ⇒ (∃y) α x, f (y, z)
za interpretaciju
RexeƬe.
D = N, α : = , f : mnoжeƬe, a : 1.
Prebacimo datu predikatsku formulu na ”uobiqajeni” matematiqki jezik:
∃z ∈ N x · y = z
∀ x ∈ N z 6= 1 ∧
⇒
(∃y ∈ N x = y · z .
Kvantifikator ∃z ∈ N utiqe samo na prvo sledee z, dok je z na kraju formule slobodno.
Kvantifikator ∃y ∈ N utiqe
samo na posledƬe y, dok je y pre Ƭega slobodno.
Kako kvantifikator ∀ x ∈ N utiqe na sva pojavƩivaƬa x, to su ona vezana.
Na osnovu ovoga imamo 3 slobodna pojavƩivaƬa promenƩivih (oznaqena plavom bojom u prethodnoj formuli:
z, y i z), stoga ova formula zavisi od 2 promenƩive y i z, tj. ona je F (y, z).
Da bismo ovo boƩe istakli promeniemo slova kvantifikatorima uz z i y (u w i t):
∀ x ∈ N z 6= 1 ∧
∃w ∈ N x · y = w
⇒
(∃t ∈ N x = t · z .
Predikatska formula ∃w ∈ N x · y = w je uvek taqna (jer za prirodne brojeve x i y postoji prirodan broj
w = x · y). Predikatska formula (∃ t ∈ N x = t · z je ekvivalentna sa z | x (tj. z deli x, odnosno x je deƩivo sa
z), pa se polazna formula svodi na
∀ x ∈ N z 6= 1 ∧ 1
⇒
z|x .
Kako je iskaz p ∧ 1 ⇔ p, dobijamo da je polazna formula ekvivalentna sa
∀ x ∈ N z 6= 1
⇒
z|x .
Sada emo iskoristiti formulu p ⇒ q ⇔ q p ∨ q da se oslobodimo implikacije:
∀x ∈ N z = 1 ∨ z | x .
Vrednost izraza
z=1 ∨ z|x
(to je gorƬa formula, ali bez kvantifikatora) jednaka je


1, z = 1
v(z = 1 ∨ z | x) = 1, z | x


0, z ∤ x.
Ostaje jox da analiziramo celu formulu, sa sve kvantifikatorom ∀ x ∈ N . Ukoliko je z = 1 imamo da
je formula taqna. Ukoliko je z 6= 1 onda formula nee biti taqna za svako x jer bi trebalo da za svaki
prirodan broj x vaжi z | x (xto nije taqno ukoliko uzmemo npr. x = 1 ili npr. x = 2z + 1). Time smo dobili
da je instinitosna vrednost date predikatske formule jednaka
(
1, z = 1
v(F ) =
0, z 6= 1.
5
3. 1. zadatak, junski rok, 2009.
Odrediti istinitosnu vrednost formule
(∀x) q α(a, x) ∨ α(x, y) ⇒ α f (x, y), g(x, y) ,
gde je a simbol konstante, α binarni relacijski znak, f, g binarni funkcijski (operacijski) znaci, pri
interpretaciji D = R, a : 5, α : =, f : mnoжeƬe, g(x, y) = x + y − 1, u zavisnosti od valuacije slobodnih
promenƩivih.
Prebacimo datu predikatsku formulu na ,,uobiqajeni“ matematiqki jezik:
RexeƬe.
(∀ x ∈ R) (5 6= x ∨ x = y) ⇒ x · y = x + y − 1.
Kvantifikator (∀ x ∈ R) utiqe samo na prva dva pojavƩivaƬa promenƩive x (na levoj strani implikacije),
dok je x na desnoj strani implikacije slobodno. Zato ova formula zavisi i od x i od y, tj. to je F (x, y).
Desnu stranu implikacije x · y = x + y − 1, kada prebacimo sve qlanove nalevo, moжemo zapisati kao
xy − x − y + 1 = 0, xto je (x − 1) · (y − 1) = 0. Dakle istinitosna vrednost desne strane D je


1, x = 1
v(D) = 1, y = 1


0, x 6= 1, y 6= 1 (inaqe).
Formula ϕ = ”5 6= x ∨ x = y” sa leve strane ima istinitosnu vrednost


1, x 6= 5
v(ϕ) = 1, x = y


0, inaqe.
Leva strana implikacije L = ∀ x ∈ R (5 6= x ∨ x = y) e biti taqna ukoliko je za svako x iz R ispuƬeno da
je v(ϕ) = 1. Za sve x 6= 5 e ϕ biti taqno, zbog prvog sluqaja, ostaje da vidimo xta se dexava za x = 5. Tada
nije x 6= 5, a ako je i y 6= 5 nee biti ni drugi sluqaj kada je formula taqna, pa e za x = 5 biti v(ϕ) = 0.
Ako je y = 5 i za x = 5 e biti v(ϕ) = 1. Stoga imamo da je istinitosna vrednost leve strane L jednaka
(
1, y = 5
v(L) =
0, y 6= 5.
Implikacija F = L ⇒ D je netaqna samo ako je v(L) = 1 (xto je za y = 5) i v(D) = 0 (xto je za x 6= 1, jer kako
je y = 5 imamo da je y 6= 1), pa imamo da je istinitosna vrednost cele formule F jednaka

(
0, y = 5, x 6= 1
0, y = 5, x 6= 1 
= 1, y 6= 5
v(F ) =

1, inaqe

1, x = 1.
4. 3. zadatak, D grupa, II kolokvijum 2009. Odrediti istinitosnu vrednost formule
(∃ z) α f (x, z), f (y, z)
⇒ q α(x, y),
gde je f binarni funkcijski (operacijski) znak, α binarni relacijski znak, pri interpretaciji D = P(A)
α : =, f : ∩, u zavisnosti od valuacije slobodnih promenƩivih.
RexeƬe.
(
v(D) =
v(F ) =
(
v(L) = 1 (L je sa sve kvantifikatorom ∃z ⊆ A – postoji: z = ∅),
1
0
x 6= y
,
x=y
1
0
x 6= y
za A 6= ∅, dok za A = ∅ vaжi v(F ) = 0.
x=y
6
5. 1. zadatak, januarski rok, 2010.
za interpretaciju
RexeƬe.
Odrediti istinitosnu vrednost predikatske formule
(∃x) (∀y) α x, f (y, z) ⇒ q α x, a) ∧ q α(x, y)
D = N, α : = , f : mnoжeƬe, a : 8.
,,Prevedimo“ datu predikatsku formulu:
(∃x ∈ N) (∀y ∈ N) x = y · z ⇒ q x = 8 ∧ q(x = y) .
Proimo negacijom kroz konjunkciju na kraju formule:
(∃x ∈ N) (∀y ∈ N) x = y · z ⇒ x 6= 8 ∨ x = y .
Oznaqimo L = (∀y ∈ N) x = y · z i D = (x 6= 8 ∨ x = y). Ako je L taqno onda za svako y ∈ N vaжi x = y · z, pa i za
y = 0 vaжi x = 0 · z ⇒ x = 0. Ali onda za y = 1 imamo da je 0 = 1 · z ⇒ z = 0. Istinitosna vrednost D sledi
direktno, pa imamo da je




1, x = z = 0
1, x 6= 8
v(L) = 0, x 6= 0
i
v(D) = 1, x = y




0, z 6= 0
0, x = 8 6= y.
Tada je formula ϕ = L ⇒ D (tj. formula bez kvantifikatora ∃) uvek taqna (pretpostavimo suprotno
v(ϕ) = 0 ⇒ v(L) = 1 odakle je x = z = 0 i v(D) = 0 odakle je x = 8 6= y
jer x ne moжe istovremeno
biti i 0 i 8!). Stoga je i cela formula F = (∃x ∈ N)ϕ uvek taqna, tj. v(F ) = 1.
6. 1. zadatak, februarski rok, 2010. Odrediti istinitosnu vrednost predikatske formule
(∀y) (∃x) α x, f (y, z) ⇔ q α x, a) ∧ q α(x, y)
za interpretaciju
RexeƬe.
D = P(A), α : = , f : ∩ , a : ∅ .
Prebacimo datu predikatsku formulu na ,,uobiqajeni“ matematiqki jezik:
∀y ∈ P(A)
∃x ∈ P(A) x = y ∩ z ⇔ q(x = ∅ ∧ x 6= y) .
Kako su x, y, z ∈ P(A), to znaqi da su oni podskupovi od A. Proimo negacijom kroz konjunkciju na kraju
formule:
(∀y ⊆ A) (∃x ⊆ A) x = y ∩ z ⇔ (x 6= ∅ ∨ x = y) .
Leva strana L formule ϕ (bez kvantifikatora ∀) je uvek taqna jer uvek postoji element x, koji je jednak
preseku 2 zadata skupa y i z, x = y ∩ z, tj.
v(L) = v (∃x ⊆ A) x = y ∩ z = 1,
dok za desnu stranu D imamo
Kako je 1 ⇔ p = p, dobijamo i da je


1,
v(D) = v(x 6= ∅ ∨ x = y) = 1,


0,


1,
v(ϕ) = 1,


0,
x 6= ∅
x=y
inaqe.
x 6= ∅
x=y
inaqe.
Ostaje da vidimo istinitosnu vrednost cele formule F = (∀y ⊆ A)ϕ. Imamo 2 razliqita sluqaja u zavisnosti
od toga kakav je dati skup A:
1◦ A = ∅
U ovom sluqaju, svi skupovi mogu biti jednaki samo praznom skupu, x = y = z = ∅, pa je formula ϕ taqna
(zbog drugog uslova x = y), tj.
v(F ) = 1.
7
2◦ A 6= ∅
Ovde imamo 2 podsluqaja — ako je x 6= ∅ onda je formula ϕ taqna (zbog prvog uslova x 6= ∅); ako je x = ∅
onda prvi uslov nije zadovoƩen, a ni drugi nije taqan za svako y (npr. moжemo uzeti y = A i tad ne
vaжi ni drugi uslov), pa dobijamo da je u ovom sluqaju
(
1,
v(F ) =
0,
x 6= ∅
x = ∅.
Pored ovih zadataka imate mnoxtvo zadataka u zbirci, koji mogu
posluжiti za veжbu!
8
Download

3. Predikatski raqun