Matematické Fórum

Daniela_H · 04. 05. 2009 23:27

Dobrý večer,
nemohl by jste mi prosím vás někdo poradit s tímto zadáním:

Napište úplnou disjunktivní formu a úplnou konjunktivní formu následující Booleovské funkce dané tabulkou.

Kondr · 05. 05. 2009 02:36

Zkus
http://kti.ms.mff.cuni.cz/teaching/file … Logika.pdf kolem strany 36
a když nepomůže tak seozvi.

Daniela_H · 05. 05. 2009 13:18

Popravdě se v tom vůbec neorientuji :(

Kondr · 05. 05. 2009 13:51 — Editoval Kondr (05. 05. 2009 18:47)

EDITováno na základě následujících příspěvků.

Oki. Tak co nám říká tabulka? Formule f je pravdívá, pokud (a,b,c) nabývá hodnot (0,0,0), (0,0,1), (0,1,1),(1,0,1). Předchozí větu pouze zapíšeme symbolicky:
$f(a,b,c)\equiv (\neg a\wedge \neg b \wedge \neg c)\vee (\neg a\wedge \neg b \wedge c)\vee (\neg a\wedge b \wedge c)\vee (a \wedge \neg b \wedge c)$ a hurá, máme úplnou disjunktivní formu. Každému řádku, kde je ve výsledku 1 odpovídá jedna kluzule (závorka) ve formuli. Je to jenom přepis té tabulky, nic se nepočítá. Použil jsem symbol $\equiv$ , stejně tak jsem mohl použít = nebo $\Leftrightarrow$ , to záleží na konvencích. Ten zobák $\neg$ značí negaci (možná se u vás používá ').

S konjununktivní formou je to trochu těžší. Sestavíme nejprve úplnou disjunktivní formu formule $\neg f(a,b,c)$ (tj. postupujeme stejně, akorát bereme řádky s nulama ve sloupci f).
$\neg f(a,b,c)\equiv (a\wedge \neg b \wedge \neg c)\vee (\neg a\wedge b \wedge \neg c)\vee (a\wedge b \wedge c)\vee (a \wedge b \wedge \neg c)$
Teď obě strany znegujeme:
$f(a,b,c)\equiv \neg (a\wedge \neg b \wedge \neg c)\wedge \neg (\neg a\wedge b \wedge \neg c)\wedge \neg(a\wedge b \wedge \neg c)\wedge \neg(a \wedge b \wedge c)$
přitom jsme použili tzv. de Morganovy zákony (návod jak negovat konjunkci a disjunkci, najdeš na webu). Když je teď použijeme ještě na každou klauzuli, dostaneme
$f(a,b,c)\equiv (\neg a\vee b \vee c)\wedge (a\vee \neg b \vee c)\wedge (\neg a\vee \neg b \vee c)\wedge (\neg a \vee \neg b \vee \neg c)$
a hurá, máme i úplnou konjunktivní formu.

Rumburak · 05. 05. 2009 14:47

↑ Kondr:
Zároveň s "roznásobením" závorek operátorem negace při poslední úpravě
měla být uvnitř těchto závorek změněna konjunkce na disjunkci:
$f(a,b,c)\equiv (\neg a\vee b \vee c)\wedge (a\vee \neg b \vee c)\wedge (\neg a\vee \neg b \vee c)\wedge (\neg a \vee \neg b \vee \neg c)$ .
Je mi samozřejmě jasné, že chyba vznikla jen přehlédnutím.

Daniela_H · 05. 05. 2009 15:18

↑ Kondr: V prvním odstavci říkáš, že dostáváme konjunktivní formu. Ve druhém však říkáš, že s konjunktivní formou je to těžší, tak teď nevím, jak to myslíš.

Kondr · 05. 05. 2009 19:27

↑ Daniela_H:V prvním odstavci mělo být samozřejmě disjunktivní, omlouvám se.

↑ Rumburak:Díky, taky spraveno.

Matematické Fórum

#1 04. 05. 2009 23:27

Booleovská funkce

#2 05. 05. 2009 02:36

Re: Booleovská funkce

#3 05. 05. 2009 13:18

Re: Booleovská funkce

#4 05. 05. 2009 13:51 — Editoval Kondr (05. 05. 2009 18:47)

Re: Booleovská funkce

#5 05. 05. 2009 14:47

Re: Booleovská funkce

#6 05. 05. 2009 15:18

Re: Booleovská funkce

#7 05. 05. 2009 19:27

Re: Booleovská funkce

Zápatí