MATEMANIJA

Pozdrav, ne razumem formulaciju zadatka kao ni šta se od mene traži , pa postavljam ovde:

"Odrediti formulu [inlmath]A(p,q,r)[/inlmath] takvu da važi:"
[dispmath]((p\lor A)\iff(q\Rightarrow(\lnot p\Rightarrow r)))\land((r\Rightarrow q)\land p\iff p\land A)[/dispmath] Šta tačno treba uraditi u ovakvom zadatku? Pretpostavljam da je [inlmath]A[/inlmath] neki parametar koji ima istinitosnu vrednost slova [inlmath]p[/inlmath], [inlmath]q[/inlmath] ili [inlmath]r[/inlmath]. Pravljenjem istinitosne tablice imam 3 grananja u formulama zavisnim od [inlmath]A[/inlmath] ([inlmath]A=p[/inlmath], [inlmath]A=q[/inlmath], [inlmath]A=r[/inlmath]), ali u sva 3 slučaja dobijam da krajnja formula nije ni tautologija ni kontradikcija ni za jedno od [inlmath]p[/inlmath], [inlmath]q[/inlmath] ili [inlmath]r[/inlmath].

Odrediti formulu [inlmath]A(p,q,r)[/inlmath] znači odrediti iskaz koji zavisi od [inlmath]p,q,r[/inlmath]. Npr: [inlmath]A(p,q,r)=(\lnot p \land (r\Rightarrow q)) \lor (q \Rightarrow r)[/inlmath]. Nakon zamene iskaza [inlmath]A[/inlmath] , početni iskaz treba da je tautologija. Prvo što mi pada na pamet je da analiziraš početni iskaz za različite vrednosti promenljive [inlmath]p[/inlmath],....

Pre svega hvala na odgovoru i srećni praznici!
Jeste, [inlmath]A[/inlmath] sam zapisao preko disjunktivne normalne forme (DNF) nakon rešavanja tablice u kojoj svaka kombinacija na kraju zavisi od [inlmath]A[/inlmath]. Problem je što se [inlmath]A[/inlmath] onda sastoji od 8 kombinacija konjunkcija [inlmath]p[/inlmath], [inlmath]q[/inlmath] i [inlmath]r[/inlmath], a izmedju njih disjunkcija prema formuli za DNF. Ovo znači da je formula [inlmath]A[/inlmath] tačna u svakom mogućem slučaju. E sada je problem ekvivalencija koja se pojavljuje na dva mesta, izrazi koji ne sadrže [inlmath]A[/inlmath] su u nekim slučajevima tačni, a u nekim netačni što automatski znači da krajnja formula neće biti tautologija (jer je izraz sa [inlmath]A[/inlmath] u prvoj zagradi uvek tačan, a sa druge strane ekvivalencije nije uvek tačno tj. u 3. slučaju za [inlmath]p=0[/inlmath], [inlmath]q=1[/inlmath], [inlmath]r=0[/inlmath] formula nije tačna, a samim tim nije ni ekvivalencija ([inlmath]1\Leftrightarrow0=0[/inlmath]) u prvoj zagradi)

Možeš li napisati šta si uzeo za [inlmath]A[/inlmath]? Pošto mi deluje da si uzeo da je [inlmath]A[/inlmath] tautologija, a to nije potrebno.

Evo jedan od načina da se uradi:
Napravi se tablica po [inlmath]A,p,q,r[/inlmath] za datu formulu, gde se [inlmath]A[/inlmath] posmatra kao nezavisna logička promenljiva. Zatim utvrdimo da u vrstama u kojima je formula netačna, možemo da promenimo samo vrednost slova [inlmath]A[/inlmath] tako da dobijemo tačnu formulu. Tj. utvrdimo da za svaku trojku [inlmath](p,q,r)[/inlmath], ili kombinacija [inlmath]\top,p,q,r[/inlmath] daje tačnu formulu ili [inlmath]\bot,p,q,r[/inlmath]. Od svake trojke [inlmath](p,q,r)[/inlmath] odaberemo vrednost za [inlmath]A[/inlmath] tako da je formula tačna (ako su moguća oba izbora, odaberemo bilo koji), tj nađemo funkciju [inlmath](p,q,r)\mapsto A[/inlmath] (dakle bukvalno odaberemo pola vrsta u tablici). Na kraju, ovu logičku funkciju predstavimo preko KNF/DNF (ili na neki treći način).

Evo kako sam ga radio:
[dispmath]F=((p\lor A)\iff(q\Rightarrow(\lnot p\Rightarrow r)))\land((r\Rightarrow q)\land p\iff p\land A)[/dispmath]
[dispmath]\begin{array}{c|c|c|c|c|c|c|c|c|c|}
p & q & r & p \lor A & q\Rightarrow(\lnot p\Rightarrow r) & (r\Rightarrow q)\land p & p\land A & (p\lor A)\Leftrightarrow(q\Rightarrow(\lnot p\Rightarrow r)) & ((r\Rightarrow q)\land p\Leftrightarrow p\land A) & F\\ \hline
0 & 0 & 0 & A & 1 & 0 & 0 & A & 1 & A\\ \hline
0 & 0 & 1 & A & 1 & 0 & 0 & A & 1 & A\\ \hline
0 & 1 & 0 & A & 0 & 0 & 0 & \lnot A & 1 & \lnot A\\ \hline
0 & 1 & 1 & A & 1 & 0 & 0 & A & 1 & A\\ \hline
1 & 0 & 0 & 1 & 1 & 1 & A & 1 & A & A\\ \hline
1 & 0 & 1 & 1 & 1 & 0 & A & 1 & \lnot A & \lnot A\\ \hline
1 & 1 & 0 & 1 & 1 & 1 & A & 1 & A & A\\ \hline
1 & 1 & 1 & 1 & 1 & 1 & A & 1 & A & A\\ \hline
\end{array}[/dispmath]
I odavde je [inlmath]A=[(\lnot p\lor\lnot q\lor\lnot r)\land(\lnot p\lor\lnot q\lor r)\land(\lnot p\lor q\lor r)\land(p\lor\lnot q\lor\lnot r)\land(p\lor q\lor\lnot r)\land(p\lor q\lor r)][/inlmath] - preko DNF
tj. [inlmath]A=[(\lnot p\land q\land\lnot r)\lor(p\land q\land r)][/inlmath] - preko KNF

Mene zanima da li sam ja ovo uradio kako treba? Moguće je da sam neki bitan korak preskočio (izmedju tablice i odredjivanja KNF i DNF). Ovo je sve iz mog razumevanja KNF i DNF, nigde nisam uspeo da pronadjem makar sličan primer sa ovakvim 'parametrom'.

ubavic je napisao:utvrdimo da za svaku trojku [inlmath](p,q,r)[/inlmath], ili kombinacija [inlmath]\top,p,q,r[/inlmath] daje tačnu formulu ili [inlmath]\bot,p,q,r[/inlmath]. Od svake trojke [inlmath](p,q,r)[/inlmath] odaberemo vrednost za [inlmath]A[/inlmath] tako da je formula tačna (ako su moguća oba izbora, odaberemo bilo koji), tj nađemo funkciju [inlmath](p,q,r)\mapsto A[/inlmath] (dakle bukvalno odaberemo pola vrsta u tablici).

Ovaj postupak ne razumem najbolje.

DaniloJ je napisao:I odavde je [inlmath]A=[(\lnot p\lor\lnot q\lor\lnot r)\land(\lnot p\lor\lnot q\lor r)\land(\lnot p\lor q\lor r)\land(p\lor\lnot q\lor\lnot r)\land(p\lor q\lor\lnot r)\land(p\lor q\lor r)][/inlmath] - preko DNF
tj. [inlmath]A=[(\lnot p\land q\land\lnot r)\lor(p\land q\land r)][/inlmath] - preko KNF

Mene zanima da li sam ja ovo uradio kako treba? Moguće je da sam neki bitan korak preskočio (izmedju tablice i odredjivanja KNF i DNF).

Tablica ti je ispravna (uz malu napomenu da ovde nemamo nule i jedinice (što si, pretpostavljam, pisao radi jednostavnosti), već imamo [inlmath]\top[/inlmath] i [inlmath]\bot[/inlmath] – nule i jedinice bismo imali kod Bulove algebre, ali tada bismo kao operacije imali [inlmath]+[/inlmath] i [inlmath]\cdot[/inlmath], a ne bismo imali [inlmath]\land[/inlmath] i [inlmath]\lor[/inlmath] kao što je ovde slučaj).

DNF će ti biti u redu nakon što sve oznake [inlmath]\land[/inlmath] zameniš sa [inlmath]\lor[/inlmath], a sve oznake [inlmath]\lor[/inlmath] zameniš za [inlmath]\land[/inlmath].

Za KNF (koja je ovde očigledno jednostavnija od DNF) treba očitavanjem iz tablice da dobiješ [inlmath](p\lor\lnot q\lor r)\land(\lnot p\lor q\lor\lnot r)[/inlmath].

Uostalom, da li si dobio ispravnu DNF odnosno KNF vrlo lako možeš proveriti uvrštavanjem konkretnih istinitosnih vrednosti za [inlmath]p[/inlmath], [inlmath]q[/inlmath] i [inlmath]r[/inlmath]. Za DNF kako si je ti napisao, [inlmath]...\land(p\lor q\lor r)[/inlmath], odmah možeš videti da nije ispravna, jer kada su i [inlmath]p[/inlmath] i [inlmath]q[/inlmath] i [inlmath]r[/inlmath] netačni, tada bi ta poslednja zagrada bila netačna, a kako pre te zagrade imaš [inlmath]\land[/inlmath], jasno je da će tada i [inlmath]A[/inlmath] biti netačno, a pošto u tom slučaju cela formula [inlmath]F[/inlmath] ima istu istinitosnu vrednost kao i [inlmath]A[/inlmath], dobiće se da je formula [inlmath]F[/inlmath] netačna, iako treba da bude tautologija.