[Logica] Forma normale congiuntiva e disgiuntiva

[perplesso1]

Usando il metodo suggerito dalla dimostazione del teorema di Post, trovare una formula in forma normale disgiuntiva (DNF) e una in forma normale congiuntiva (CNF) equivalenti a $\phi = \neg (p \wedge q) \rightarrow (q \leftrightarrow r)$

Ho calcolato la tabella di verità


quindi la forma normale disgiuntiva $\phi^{DNF}$ è

$(p \wedge q \wedge r) \vee (p \wedge q \wedge \neg r) \vee (p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge q \wedge r) \vee (\neg p \wedge \neg q \wedge \neg r)$

La forma congiuntiva si ottiene applicando de Morgan alla formula equivalente $\neg ((\neg \phi)^{DNF})$

$(\neg \phi)^{DNF} = (p \wedge \neg q \wedge r ) \ vee (\neg p \wedge q \wedge \neg r) \vee (\neg p \wedge \neg q \wedge r)$

e applicando De Morgan

$\phi^{CNF} = \neg ((\neg \phi)^{DNF}) = (\neg p \vee q \vee \neg r ) \wedge ( p \vee \neg q \vee r) \wedge (p \vee q \vee \neg r)$

Fatto bene? Grazie.

[fields1]

Tutto esatto

[perplesso1]

Grande. Devo fare la stessa cosa anche con questa formula $\phi =((p \leftrightarrow q) \rightarrow r) \rightarrow q$

Tabella


Froma disqiuntiva

$\phi^{DNF} = (p \wedge q \wedge r) \vee (p \wedge q \wedge \neg r) \vee (\neg p \wedge q \wedge r) \vee (\neg p \wedge q \wedge \neg r) \vee (\neg p \wedge \neg q \wedge \neg r)$

Forma disgiuntiva della negazione

$(\neg \phi)^{DNF} = (p \wedge \neg q \wedge r) \vee (p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge \neg q \wedge r)$

Forma congiuntiva

$\phi^{CNF} = (\neg p \vee q \vee \neg r) \wedge (\neg p \vee q \vee r) \wedge (p \vee q \vee \neg r)$

Giusto anche questo?

[fields1]

Be', è uguale all'altro... giusto, a meno di sviste.

[perplesso1]

è che nel mio testo c'è una sfilza di esercizi tutti di questo tipo, pensavo di farmeli tutti ma effettivamente è un pò inutile xD passerò ad altro. Grazie 1000!