Converting an Expression to CNF (conjunctive normal form)

Question

I am trying to convert the following expression to CNF (conjunctive normal form): $$ (A \wedge B \wedge M) \vee ( \neg F \wedge B).$$

So I apply the distributive law and get: $$ \neg F \wedge B \vee (A \wedge B \wedge M).$$

Now, I feel I am stuck. How do I proceed?

Thanks, Bob

Answer 1

Apply the distributive laws as Graham Kemp enunciated to get $$(A \wedge B \wedge M) \vee (\neg F \wedge B) = ((A \wedge B \wedge M) \vee \neg F) \wedge ((A \wedge B \wedge M) \vee B)$$

Now from distributivity again, $$(A \wedge B \wedge M) \vee \neg F = (A \vee \neg F) \wedge (B \vee \neg F) \wedge (M \vee \neg F),$$ while absorption, commutativity and associativity yield $$(A \wedge B \wedge M) \vee B = B,$$ and so we get the expression $$(A \vee \neg F) \wedge (B \vee \neg F) \wedge (M \vee \neg F) \wedge B.$$

Again, by absorption, $$(B \vee \neg F) \wedge B = B,$$ and so the final expression, in CNF is $$(A \vee \neg F) \wedge (M \vee \neg F) \wedge B.$$

Answer 2

The distributive law is that $\phi\wedge(\psi\vee \rho)\equiv (\phi\wedge\psi)\vee(\phi\wedge\rho)$ and $\phi\vee(\psi\wedge\rho)\equiv (\phi\vee\psi)\wedge(\phi\vee\rho)$.

---

These are equivalences, so $(\phi\wedge\psi)\vee(\phi\wedge\rho)\equiv\phi\wedge(\psi\vee \rho)$ and $(\phi\vee\psi)\wedge(\phi\vee\rho)\equiv\phi\vee(\psi\wedge\rho)$ too.