0
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.