Matematické Fórum

bbeni · 11. 06. 2009 18:35

trebA najst minimalny konjuktivny a minimalny disjunktuvny tvar z boolovskej funkcie (x implikuje y) a sucasne (negovane y alebo z)

Johny · 11. 06. 2009 18:50 — Editoval Johny (11. 06. 2009 18:51)

↑ bbeni:

Nazdar pro konjunkci stací upravit podle mě jen tu implikaci (neg. x v y). A v druhém případě disjunktivní upravíš implikaci a pak roznásobíš ty závorky, jako klasické násobení. Ale nejsem si stoprocentně jistý , určitě ti to ještě někdo na to koukne :)

Kondr · 12. 06. 2009 00:15

Nejprve se zbavíme implikace
$(\neg x \vee y) \wedge (\neg y \vee z)$
To je konjunktivní tvar a je minimální (kdyby měl jen jednu klauzuli, musel by mít 4 nebo více splňujících přiřazení. Má sice 4, ale neodpovídají žádné klauzuli s jediným literálem).
Teď bychom to měli převést do disjunktivní formy (stejně jako se roznásobují závorky) a pak "podobné" závorky spojovat a nadbytečné zahazovat:
1) roznásobení
$(\neg x \wedge \neg y) \vee (y\wedge \neg y) \vee (\neg x \wedge z) \vee (y\wedge z)$
2) druhá závorka není splněna
$(\neg x \wedge \neg y) \vee (\neg x \wedge z) \vee (y\wedge z)$
3) pokud je splněna prostřední závorka, je vždy splněna alespoň jedna ze zbylých dvou
$(\neg x \wedge \neg y) \vee (y\wedge z)$
Důkaz minimality lze opět udělat přes počet splňujících přiřazení.

Matematické Fórum

#1 11. 06. 2009 18:35

minimalizacia boolovskej funkcie

#2 11. 06. 2009 18:50 — Editoval Johny (11. 06. 2009 18:51)

Re: minimalizacia boolovskej funkcie

#3 12. 06. 2009 00:15

Re: minimalizacia boolovskej funkcie

Zápatí