DNF

PostPoslato: Nedelja, 28. Januar 2018, 22:37
od kad
Koji je dnf od sledeceg izraza?
[dispmath]\lnot(x\lor\lnot y)\land\lnot z\lor\lnot(x\land\lnot y)\land z[/dispmath] ja krenem

[inlmath]\lnot x\land y\land\lnot z\lor\lnot x\lor y\land z[/inlmath]

ali sada kada treba da se spoji kako?
da spajam prva 3?
pa dobijem [inlmath](\lnot x\land y\land\lnot z)\lor(\lnot x)\lor(y\land z)[/inlmath]

Re: DNF

PostPoslato: Utorak, 30. Januar 2018, 17:47
od Daniel
Molio bih prvo za sledeće razjašnjenje. Neki autori smatraju da [inlmath]\land[/inlmath] ima prioritet nad [inlmath]\lor[/inlmath], tj. da se, kad nema zagrada, prvo izvršava konjunkcija pa zatim disjunkcija. Drugi autori, pak, smatraju da su [inlmath]\land[/inlmath] i [inlmath]\lor[/inlmath] međusobno ravnopravne po prioritetu. Od ovih drugih, jedni smatraju da se logičke operacije izvršavaju sleva nadesno, dok drugi ne priznaju to pravilo i smatraju da se zbog toga moraju koristiti zagrade radi otklanjanja neizvesnosti.

Dakle, kako su vama na predavanju rekli da radite? Kojim se redom izvršavaju konjunkcija i disjunkcija izvan zagrada u [inlmath]\lnot(x\lor\lnot y)\land\lnot z\lor\lnot(x\land\lnot y)\land z[/inlmath]?

Re: DNF

PostPoslato: Utorak, 30. Januar 2018, 20:54
od kad
Trebalo bi da konjukcija ima prednost kada nema zagrada.

Re: DNF

PostPoslato: Utorak, 30. Januar 2018, 22:37
od Daniel
Ispravno je konjunkcija.
Znači, da posmatramo dati izraz kao [inlmath]\bigl(\lnot(x\lor\lnot y)\land\lnot z\bigr)\lor\bigl(\lnot(x\land\lnot y)\land z\bigr)[/inlmath].

kad je napisao:ja krenem

[inlmath]\lnot x\land y\land\lnot z\lor{\color{#08F}\lnot x\lor y}\land z[/inlmath]

Plavi deo izraza treba da se nalazi unutar zagrade. Prilikom primene De Morgana ne smeš se tek tako osloboditi zagrada. Znači, nakon primene De Morgana imaš
[dispmath](\lnot x\land y)\land\lnot z\lor(\lnot x\lor y)\land z[/dispmath] pa u ovom prvom delu, [inlmath](\lnot x\land y)\land\lnot z[/inlmath], zbog asocijativnosti konjunkcije nije neophodno pisati zagradu, ali u drugom delu, [inlmath](\lnot x\lor y)\land z[/inlmath] imamo disjunkciju unutar zagrade i konjunkciju, pa kad ne bi bilo zagrade prvo bi se izvršavala konjunkcija, što bi bilo pogrešno. Zbog toga u tom delu zagrada mora da ostane:
[dispmath]\lnot x\land y\land\lnot z\lor(\lnot x\lor y)\land z[/dispmath]
kad je napisao:da spajam prva 3?
pa dobijem [inlmath](\lnot x\land y\land\lnot z)\lor(\lnot x)\lor(y\land z)[/inlmath]

Ti si ovde od ovog desnog dela, [inlmath](\lnot x\lor y)\land z[/inlmath], napravio [inlmath]\lnot x\lor(y\land z)[/inlmath], ali to je pogrešno, jer ne važi asocijacija kad imaš disjunkciju i konjunkciju. Znači, [inlmath](A\lor B)\land C[/inlmath] nije isto što i [inlmath]A\lor(B\land C)[/inlmath] (u šta se možeš i uveriti ako nacrtaš istinitosnu tabelu za jedan i za drugi izraz).
Umesto toga, na [inlmath](\lnot x\lor y)\land z[/inlmath] primeni distributivnost konjunkcije u odnosu na disjunkciju – i dobićeš disjunktivnu normalnu formu.

Re: DNF

PostPoslato: Sreda, 31. Januar 2018, 05:16
od kad
Ispravno je konjunkcija.

Da, greska pri kucanju

Ok, ako bih tako uradio, dobio bih
[inlmath](\lnot x\land y\land\lnot z)\lor(\lnot x\land z)\lor(y\land z)[/inlmath]

Jel ovako?

Mene buni sto npr boolean calculator daje drugaciji rezultat
on daje [inlmath](\lnot x\land y)\lor(\lnot x\land z)\lor(y\land z)[/inlmath]

Re: DNF

PostPoslato: Sreda, 31. Januar 2018, 11:44
od Daniel
To što ti Boolean calculator izbacuje to je minimalna DNF. Ukoliko se u zadatku traži minimalna DNF, onda je ispravno to što ti je prikazao Boolean calculator. A ako samo piše da se traži DNF, tada je tačno i tvoje rešenje, a i rešenje koje daje Boolean calc.

Ako nacrtaš istinitosne tabele za oba rezultata, videćeš da se poklapaju.

A možeš od svog rezultata vrlo lako doći i do minimalne DNF, ako u svom rezultatu iz prva dva člana izvučeš [inlmath]\lnot x[/inlmath] (po zakonu distribucije konjunkcije u odnosu na disjunkciju) pa ostane
[dispmath]\lnot x\land\bigl((y\land\lnot z)\lor z\bigr)\lor(y\land z)[/dispmath] zatim na izraz [inlmath](y\land\lnot z)\lor z[/inlmath] primeniš distribuciju disjunkcije u odnosu na konjunkciju,
[dispmath]\lnot x\land\bigl((y\lor z)\land(\underbrace{\lnot z\lor z}_\top)\bigr)\lor(y\land z)\\
\lnot x\land(y\lor z)\lor(y\land z)[/dispmath] i onda opet primeniš distributivnost konjunkcije u odnosu na disjunkciju:
[dispmath](\lnot x\land y)\lor(\lnot x\land z)\lor(y\land z)[/dispmath] i to je ta minimalna DNF koju ti je prikazao Boolean calculator.