Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 01. 09. 2009 16:44 — Editoval Okaz (01. 09. 2009 16:46)

Okaz
Příspěvky: 51
Reputace:   
 

Převod DNF do KNF

Potreboval bych pomoct s vypoctem tohohle priklad a pokud mozna to jeste malinko priblizat jak na to. VIm, ze jeden zpusob je treba pres pravd. tabulku a pak demorganovy zakony, ale najek to na to nemuzu aplikovat

$(\neg x \wedge \neg y \wedge \neg z) \vee (\neg x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge \neg z) \vee (\neg x \wedge \neg y \wedge z)  \vee ( x \wedge \neg y \wedge z) $

Offline

 

#2 01. 09. 2009 17:06

twomi
Zelenáč
Příspěvky: 6
Reputace:   
 

Re: Převod DNF do KNF

z tehle formule vidis presne, pro ktere kombinace ohodnoceni x,y,z je formule pravdiva; jsou to presne ty uvedene v jednotlivych zavorkach
tedy formule je pravdiva kdyz x=0,y=0,z=0 nebo kdyz x=0,y=0,z=1 atd.

negace formule a & b je (not a) OR (not b) a naopak, tedy si staci vytvorit formuli F opacnou k te zadane ve stejnem tvaru (takovou formuli, ze je pravda kdyz puvodni ne, udelas proste disjunkci takovych kombinaci x,y,z pro ktere je puvodni formule 0) a F znegovat

Offline

 

#3 01. 09. 2009 17:22 — Editoval Okaz (01. 09. 2009 17:22)

Okaz
Příspěvky: 51
Reputace:   
 

Re: Převod DNF do KNF

Jo sem tam mel chybu, takhle je to spravne, ve 4 zavorkach neni y negovany

$(\neg x \wedge \neg y \wedge \neg z) \vee (\neg x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge \neg z) \vee (\neg x \wedge y \wedge z)  \vee ( x \wedge \neg y \wedge z) $

Ale na tom asi zas tak moc nezalezi, jen mi neni jasny, jak poznam kdy to je nulovy a kdy ne

Offline

 

#4 01. 09. 2009 17:32

Okaz
Příspěvky: 51
Reputace:   
 

Re: Převod DNF do KNF

Jo aha uz asi tusim, kdyz mam to x,y,z 0,0,0, tak mi vyjde 1 v ty prvni zavorce, protoze to jsou konjunkce a ty jsou dve jednicky rovny 1 a jelikoz to jsou negace, tak to je 1,1,1, v ty zavorce a tak dal, ale dal uz nejak nechapu co s tim, kdyz sem si zjistil, jaky ohodnoceni potrebuju aby byly pravdivy

Offline

 

#5 01. 09. 2009 17:40

twomi
Zelenáč
Příspěvky: 6
Reputace:   
 

Re: Převod DNF do KNF

No ted si zkonstruujes formuli v tomhle tvaru, ktera je presne opacna. Tedy vezmes vsechny ohodnoceni, pro ktere puvodni formule NENI pravdiva, a z nich si stejnym zpusobem postavis formuli. Tu pak klasickym zpusobem znegujes (vsechny disjunkce zmenis na konjunkce, vsechny konjuknce na disjunkce, a vsechny vyskyty x,y,z jen znegujes)

po krocich: tahle f je pravdiva pro 000 001 010 011 101. chces opacnou formuli, tedy takovou co je pravdiva pro 111,110,100; tzn $(x \wedge y \wedge z)\vee(x\wedge y\wedge \neg z)\vee (x\wedge \neg y\wedge \neg z)$. a tu znegujes -> $(\neg x \vee \neg y \vee \neg z)\wedge ... $ mozna jsem udelal chybku tak si to radsi prekontroluj

Offline

 

#6 01. 09. 2009 17:57

Okaz
Příspěvky: 51
Reputace:   
 

Re: Převod DNF do KNF

$(\neg x \vee \neg y \vee \neg z)\wedge (\neg x \vee y \vee z)\wedge (\neg x \vee \neg y \vee z)$

Tak ze uz sem to asi pochopil a vyslo mi tohle


A jeste bych se rad zeptal, kdyz to delam obracene z KNF do DNF, tak beru ty ohodnoceni, kde je to pravdivy a ty pak zneguju?

Offline

 

#7 01. 09. 2009 18:09

twomi
Zelenáč
Příspěvky: 6
Reputace:   
 

Re: Převod DNF do KNF

na druhou stranu ten postup funguje presne opacne -- znegujes knf formuli, dostanes nejakou dnf, podivas se kdy je ta pravdiva a zkonstruujes dnf ktera je jeji negaci. Ale nevim jestli neexistuje nejaky hezci postup, tohle me jen ted napadlo (tim myslim pro oba smery)

Offline

 

#8 01. 09. 2009 18:22

Okaz
Příspěvky: 51
Reputace:   
 

Re: Převod DNF do KNF

prave sem to zkusil a funguje to, zase sem to znegoval zpatky, udelal si pravdivostni tabulku, vybral ty ohodnoceni, kde to vyjde 0 a zapsal a vyslo to nazpatek, diky

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson