# Converting an Expression to CNF (conjunctive normal form)

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

• You should apply the distributive law. That's not an application of the distributive law. – spaceisdarkgreen Sep 22 '19 at 1:27
• @spaceisdarkgreen am I right so far? – Bob Sep 22 '19 at 1:32
• No, as I said before, that’s not an application of the distributive law. – spaceisdarkgreen Sep 22 '19 at 2:10
• Do you know FOIL? – Bram28 Sep 22 '19 at 3:05

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.$$
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.