A
A
I kolokvijum iz DMS-a
FON, 22.04.2014.
Prezime i ime studenta
br. indeksa
1. Na jednom ostrvu ive samo vile i vextice. One se po spoljnom izgledu ne mogu razlikovati. Vile
uvek govore istinu, dok vextice uvek lau. Tri od njih, Ana, Bana i Cana, su rekle sledee reqenice.
Ana:
Bana:
Cana:
Ako sam ja vila, onda je Cana vextica.
Ako od druge dve bar jedna govori istinu, onda ja i Cana pripadamo razliqitim vrstama.
Bana je vextica. Ako Ana ne lae, onda i ja ne laem.
Da li su ove reqenice neprotivreqne?
Za iskaznu formulu ϕ koja odgovara onome xto je rekla Cana odrediti jednu SKNF i jednu KNF.
Za iskaznu formulu F kojom ste ispitali (ne)protivreqnost odrediti jednu SDNF i jednu DNF.
Za koga od njih sa sigurnoxu moemo rei kojoj vrsti pripada?
2. Odrediti iskaznu formulu F koja odgovara datom kolu.
p
q
F
r
s
Ispitati da li je F tautologija ili kontradikcija.
Da li F predstavlja SKNF, SDNF, KNF ili DNF?
Predstaviti F u jednoj KNF i jednoj DNF.
3. Odrediti istinitosnu vrednost formule
³
¡
¢´
(∃y) (∀x) α(z, a) ⇒ (q α(x, y) ∧ α(y, z)) ⇒ (∃z) α(f (x, z), y) .
gde je α binarni relacijski simbol, pri interpretaciji D = P(A), α : =, f : ∪, a : ∅, u zavisnosti od
valuacije slobodnih promenljivih.
4. Neka je dat skup X = {dana, gana, grana, zana, mana, strana} i na njemu relacija % ⊆ X 2 data sa
%: x%y
def
⇐⇒
reqi x i y imaju jednak broj suglasnika
i
imaju isti troslovni zavrxetak.
a) Predstaviti datu relaciju tabliqno i preko grafa.
b) Da li je data relacija refleksivna, simetriqna, antisimetriqna, tranzitivna?
v) Ispitati da li je to relacija ekvivalencije i/ili relacija poretka.
g) Ukoliko je to relacija ekvivalencije odrediti sve klase ekvivalencije, a ukoliko je to relacija
poretka predstaviti je preko Haseovog dijagrama, ispitati da li je to relacija totalnog ili
parcijalnog poretka i odrediti minimalne, maksimalne, najmanje i najvee elemente skupa X.
B
B
I kolokvijum iz DMS-a
FON, 22.04.2014.
Prezime i ime studenta
br. indeksa
1. Na jednom ostrvu ive patuljci i gnomi. Po spoljnom izgledu oni se ne razlikuju. Patuljci uvek
govore istinu, a gnomi uvek lau. Tri od njih, Acko, Bucko i Cicko, su rekli sledee reqenice.
Acko: Ja i Cicko pripadamo razliqitim vrstama.
Bucko: Acko je patuljak. Ako Cicko ne lae, onda i ja ne laem.
Cicko: Ako od druge dvojice ne lau obojica, onda sam ja gnom.
Da li su ove reqenice neprotivreqne?
Za iskaznu formulu ϕ koja odgovara Buckovoj reqenici odrediti jednu SKNF i jednu KNF.
Za iskaznu formulu F kojom ste ispitali (ne)protivreqnost odrediti jednu SDNF i jednu DNF.
Za koga od njih sa sigurnoxu moemo rei kojoj vrsti pripada?
2. Odrediti iskaznu formulu F koja odgovara datom kolu.
a
b
c
F
d
Ispitati da li je F tautologija ili kontradikcija.
Da li F predstavlja SKNF, SDNF, KNF ili DNF?
Predstaviti F u jednoj KNF i jednoj DNF.
3. Odrediti istinitosnu vrednost formule
³¡
¢
¡
¢´
(∀x) (∃y) (α(x, a) ⇒ α(x, y)) ⇒ α(y, z) ⇒ (∃z) α f (y, z), x .
gde je α binarni relacijski simbol, a simbol konstante, pri interpretaciji D = N, α : =, f je sabiranje
prirodnih brojeva, a : 1, u zavisnosti od valuacije slobodnih promenljivih.
4. Neka je dat skup X = {2, 3, 4, 9, 16, 42} i na njemu relacija % ⊆ X 2 data sa
%: x%y
def
⇐⇒
x = y2
ili
brojevi x i y imaju isti zbir cifara.
a) Predstaviti datu relaciju tabliqno i preko grafa.
b) Da li je data relacija refleksivna, simetriqna, antisimetriqna, tranzitivna?
v) Ispitati da li je to relacija ekvivalencije i/ili relacija poretka.
g) Ukoliko je to relacija ekvivalencije odrediti sve klase ekvivalencije, a ukoliko je to relacija
poretka predstaviti je preko Haseovog dijagrama, ispitati da li je to relacija totalnog ili
parcijalnog poretka i odrediti minimalne, maksimalne, najmanje i najvee elemente skupa X.
G
G
I kolokvijum iz DMS-a
FON, 22.04.2014.
Prezime i ime studenta
br. indeksa
1. Na jednom ostrvu ive patuljci i gnomi. Po spoljnom izgledu oni se ne razlikuju. Patuljci uvek
govore istinu, a gnomi uvek lau. Tri od njih, Acko, Bucko i Cicko, su rekli sledee reqenice.
Acko: Cicko je gnom. Ako Bucko govori istinu, onda ja laem.
Bucko: Ako sam ja patuljak, onda je i Acko patuljak.
Cicko: Iz qinjenice da ako Acko ne lae onda i Bucko ne lae, sledi da ja i Acko pripadamo
istoj vrsti.
Da li su ove reqenice neprotivreqne?
Za iskaznu formulu ϕ koja odgovara Buckovoj reqenici odrediti jednu SKNF i jednu KNF.
Za iskaznu formulu F kojom ste ispitali (ne)protivreqnost odrediti jednu SDNF i jednu DNF.
Za koga od njih sa sigurnoxu moemo rei kojoj vrsti pripada?
2. Odrediti iskaznu formulu F koja odgovara datom kolu.
a
b
F
c
d
Ispitati da li je F tautologija ili kontradikcija.
Da li F predstavlja SKNF, SDNF, KNF ili DNF?
Predstaviti F u jednoj KNF i jednoj DNF.
3. Odrediti istinitosnu vrednost formule
³
¡
¢´
(∃y) (∀x) α(z, a) ⇒ (q α(x, y) ∧ α(y, z)) ⇒ (∃z) α(f (x, z), y) .
gde je α binarni relacijski simbol, a simbol konstante, pri interpretaciji D = N0 , α : =, f je oduzimanje celih brojeva, a : 5, u zavisnosti od valuacije slobodnih promenljivih.
4. Neka je dat skup X = {aca, buba, buca, cvet, da, relacija} i na njemu relacija % ⊆ X 2 data sa
%: x%y
def
⇐⇒
reqi x i y imaju jednak broj samoglasnika
i
req x nije dua od reqi y.
a) Predstaviti datu relaciju tabliqno i preko grafa.
b) Da li je data relacija refleksivna, simetriqna, antisimetriqna, tranzitivna?
v) Ispitati da li je to relacija ekvivalencije i/ili relacija poretka.
g) Ukoliko je to relacija ekvivalencije odrediti sve klase ekvivalencije, a ukoliko je to relacija
poretka predstaviti je preko Haseovog dijagrama, ispitati da li je to relacija totalnog ili
parcijalnog poretka i odrediti minimalne, maksimalne, najmanje i najvee elemente skupa X.
D
D
I kolokvijum iz DMS-a
FON, 22.04.2014.
Prezime i ime studenta
br. indeksa
1. Na jednom ostrvu ive samo vile i vextice. One se po spoljnom izgledu ne mogu razlikovati. Vile
uvek govore istinu, dok vextice uvek lau. Tri od njih, Ana, Bana i Cana, su rekle sledee reqenice.
Ana:
Bana:
Cana:
Ako od druge dve ne lau obe, onda sam ja vila.
Ja i Ana pripadamo istoj vrsti.
Bana je vila. Ako Ana lae, onda ja ne laem.
Da li su ove reqenice neprotivreqne?
Za iskaznu formulu ϕ koja odgovara onome xto je rekla Cana odrediti jednu SKNF i jednu KNF.
Za iskaznu formulu F kojom ste ispitali (ne)protivreqnost odrediti jednu SDNF i jednu DNF.
Za koga od njih sa sigurnoxu moemo rei kojoj vrsti pripada?
2. Odrediti iskaznu formulu F koja odgovara datom kolu.
p
q
r
F
s
Ispitati da li je F tautologija ili kontradikcija.
Da li F predstavlja SKNF, SDNF, KNF ili DNF?
Predstaviti F u jednoj KNF i jednoj DNF.
3. Odrediti istinitosnu vrednost formule
³¡
´
¢
¡
¢
(∀x) (∃y) (α(x, a) ⇒ α(x, y)) ⇒ α(y, z) ⇒ (∃z) α f (y, z), x ∧ q α(x, y) .
gde je α binarni relacijski simbol, pri interpretaciji D = P(A), α : =, f : ∪, a : ∅, u zavisnosti od
valuacije slobodnih promenljivih.
4. Neka je dat skup X = {3, 5, 9, 25, 44, 100} i na njemu relacija % ⊆ X 2 data sa
%: x%y
def
⇐⇒
x = y2
ili
brojevi x i y imaju isti zbir cifara.
a) Predstaviti datu relaciju tabliqno i preko grafa.
b) Da li je data relacija refleksivna, simetriqna, antisimetriqna, tranzitivna?
v) Ispitati da li je to relacija ekvivalencije i/ili relacija poretka.
g) Ukoliko je to relacija ekvivalencije odrediti sve klase ekvivalencije, a ukoliko je to relacija
poretka predstaviti je preko Haseovog dijagrama, ispitati da li je to relacija totalnog ili
parcijalnog poretka i odrediti minimalne, maksimalne, najmanje i najvee elemente skupa X.
1. Osnovni iskazi su:
a=
b=
c=
Iskazne formule koje odgovaraju datim reqenicama su:
A:
B:
C:
Da li su ove reqenice neprotivreqne (i postupak)?
Jedna SKNF i jedna KNF za ϕ:
Jedna SDNF i jedna DNF za F :
Za koga od njih sa sigurnoxu moemo rei kojoj vrsti pripada (i zaxto)?
grupa
Prezime i ime studenta
2. Iskazna formula F koja odgovara datom kolu:
Da li je F tautologija i/ili kontradikcija (i postupak)?
Da li F predstavlja SKNF, SDNF, KNF ili DNF (i obrazloenja)?
Predstaviti F u jednoj KNF i jednoj DNF:
br. indeksa
3. Xta su slobodne, a xta vezane promenljive?
pa je formula oblika
F(
).
Prevedena formula:
Istinitosna vrednost formule F (i postupak):
4. a) % tabliqno i preko grafa:
%
b) Da li je % refleksivna, simetriqna, antisimetriqna, tranzitivna (upisati jeste/nije i objasniti)?
R
S
AS
T
v)
rel. poretka
rel. ekvivalencije
g) Ukoliko je % relacija ekvivalencije odrediti sve klase ekvivalencije, a ukoliko je to relacija
poretka predstaviti je preko Haseovog dijagrama, ispitati da li je to relacija totalnog ili
parcijalnog poretka i odrediti minimalne, maksimalne, najmanje i najvee elemente skupa X.
Download

I kolokvijum iz DMS-a FON, 22.04.2014.