How to form a CNF of following formula

Question

We got an exercise to make a CNF out of the following formula: $$G = ((A \vee \neg B \vee C) \wedge (C \vee D)) \vee ((A \vee \neg C) \wedge (B \wedge D))$$ I've tried to make an equivalent equation but only had more questions afterwards. I hope you could help me out.

Answer 1

To get a CNF of $G$ we apply the distributive law. Let: $$ M = A \vee \neg B \vee C$$ $$ N = C \vee D $$ $$ P = A \vee \neg C $$ $$ Q = B \wedge D $$

Then we have:

$$ G = (M \wedge N) \vee (P \wedge Q) $$

Now let $F = M \wedge N$ then applying the distributive law we get:

$$ G = (F \vee P) \wedge (F \vee Q)$$

And so we get:

$$ G = (P \vee M) \wedge (P \vee N) \wedge (F \vee Q) $$ $$ G = (P \vee M) \wedge (P \vee N) \wedge (Q \vee M) \wedge (Q \vee N) $$ $$ G = (P \vee M) \wedge (P \vee N) \wedge (M \vee B) \wedge (M \vee D) \wedge (N \vee B) \wedge (N \vee D)$$

Or:

$$ G = (A \vee \neg C \vee A \vee \neg B \vee C) \wedge (A \vee \neg C \vee C \vee D) \wedge (A \vee \neg B \vee C \vee B) \wedge (A \vee \neg B \vee C \vee D) \wedge (C \vee D \vee B) \wedge (C \vee D \vee D)$$

$$ G = (A \vee \neg B \vee C \vee D) \wedge (C \vee D \vee B) \wedge (C \vee D) $$

Which is in CNF. It can be verified that the final form given for $G$ is equivalent to the original by checking the truth table.

Answer 2

$$ ((A \lor \lnot B \lor C) \land (C \lor D)) \lor ((A \lor \lnot C) \land (B \land D)) \\ ((A \lor \lnot B \lor C) \lor (A \lor \lnot C)) \land ((A \lor \lnot B \lor C) \lor (B \land D)) \land ((C \lor D) \lor (A \lor \lnot C)) \land ((C \lor D) \lor (B \land D)) \\ (A \lor \lnot B \lor \color{blue}{C \lor \lnot C}) \land (A \lor \color{blue}{\lnot B} \lor C \color{blue}{\lor B}) \land (A \lor \lnot B \lor C \lor D) \land (\color{blue}{C} \lor D \lor A \color{blue}{\lor \lnot C}) \land (C \lor D \lor B) \land (C \lor D) \\ \color{blue}{T} \land \color{blue}{T} \land (A \lor \lnot B \lor C \lor D) \land \color{blue}{T} \land (C \lor D \lor B) \land (C \lor D) \\ (A \lor \lnot B \lor \color{red}{C \lor D}) \land (\color{red}{C \lor D} \lor B) \land (\color{red}{C \lor D}) \\ \color{red}{C \lor D} $$