First order logic, CNF

Question

What steps do I need to follow to convert the next statements into CNF? Wich are the resulting clauses?

1. $H \leftrightarrow C \vee D$
2. $R \rightarrow \neg D$
3. $R \wedge H$
4. $H \leftrightarrow C$

Thank you.

Answer 1

First, be clear what CNF: Conjunctive Normal Form means, and understand why the examples listed in the linked Wikipedia entry are in CNF. Then you'll see that your third expression:

$(3)\; R \land H\,$ is already in conjunctive normal form. Note that $R\lor H$ is also in conjunctive normal form.

One obvious mnemonic for remembering what CNF allows is to remember $C$ is for conjunction, and think of $N$ as "negation."

You want to end with an expression of the form $P$ or of the form $P \land Q$ or of the form $P \land Q \land R \land \cdots$ depending on the number of variables and clauses needed. But note that

• Each $P, Q, R$ can represent a literal or the negation of a literal (literals are simple propositions without connectives: in your first question, e.g. $H, C, D$ are each literals, and in your second question, $\lnot D$ is a negated literal.
• each $P, Q, R$, etc, may represent a propositional clause within which the only connective is the $\lor$ connective between literals and/or negated literals: e.g. $$A \land (\lnot B \lor C) \land (E \lor F \lor \lnot G) \land \lnot Z$$ is of the form $P \land Q \land R \land S$ where $P := A, \;Q:=(\lnot B \lor C),\;R = (E\lor F \lor \lnot G),\; S = \lnot Z$
• No literal appears more than once by itself or in a clause.

---

I'll leave the first expression to you, in hopes that you can learn from the following examples:

$(2)\quad R \rightarrow \lnot D\equiv (\lnot R \lor \lnot D)$

$(4)\quad H \leftrightarrow C \equiv (H\rightarrow C) \land (C\rightarrow H)\equiv (\lnot H \lor C) \land (\lnot C \lor H)$

The right-most propositions in $(2)$ and $(4)$ are now in conjunctive normal form.