comment convertir (a ∧ b) ↔ c en forme CNF?

Question

Après avoir fait une table de vérité, ce que j'ai trouvé était:

(¬ (a ∧ b) ∨ c) ∧ ((a ∧ b) ∨ c) ∧ ((a ∧ b) ∨ ¬ c)

Mais maintenant, je trouve difficile de convertir cela en CNF. Je n'ai aucune idée de comment changer les ∧ pour qu'ils deviennent ∨ dans les clauses.

Ce que je fais, c'est utiliser (a ∧ b) et c pour former le CNF. Mais cela ne me mène nulle part.

J'ai consulté mes camarades de cours, qui ont dit que je devrais plutôt utiliser a, b et c pour former le CNF. Je pense qu'ils ont raison, mais je ne sais pas pourquoi je me trompe.

Dois-je utiliser uniquement les propositions atomiques, au lieu d'utiliser la proposition composée? Est-ce pour cela que je frappe un mur de briques ici?

Si j'utilise les propositions atomiques, ne serait-ce pas une signification différente de l'utilisation de la proposition composée (a ∧ b)?

Veuillez aider. Merci beaucoup.

Answer 1

$(a\land b)\leftrightarrow c$ devient $$(a\land b\land c)\lor(\neg a\land\neg c)\lor(\neg b\land\neg c)$$C'est le DNF. Pour obtenir le CNF, nous distribuons OU sur ET, en supprimant les combinaisons contenant des éléments tels que$a\lor\neg a$ et clauses contenues dans d'autres clauses: $$(a\lor\neg c)\land(b\lor\neg c)\land(c\lor\neg a\lor\neg b)$$