0
$\begingroup$

I am still a bit confused by how to convert into CNF even though I have the rules written down.

How do I convert the following sentence into CNF?

$(I \lor M) \Rightarrow H$

I know I need to get rid of the implication symbol and when its in the form $(I \Rightarrow H)$ or $(M \Rightarrow H)$ then I can see how to do it, but when its one sentence like this how do I factor out the implication?

The reason I am stuck is because I do not know how to get rid of the resulting or:

$(\neg I \lor H) \lor (\neg M \lor H) \Rightarrow I$ think the OR here needs to be an AND to be CNF

Thanks

$\endgroup$
1
$\begingroup$

We have that $A \Rightarrow B$ is same with $\neg A \lor B$. This gives, that $(I \lor M)\Rightarrow H$ is same with $\neg(I \lor M)\lor H$.

And we have that $\neg(I \lor M)$ is same with $\neg I \land \neg M$

Putting together we have that $(I \lor M)\Rightarrow H $ is same with $\neg I \land \neg M \lor H = (\neg I \land \neg M) \lor H = (\neg I \lor H) \land (\neg M \lor H )$.

$\endgroup$
7
  • $\begingroup$ Ok I think my problem runs deeper then unless I am misunderstanding something because it is not possible for I and M to both be true at the same time but one of them has to be true so I do not think (-I ^ -M) can ever result in true, which would mean H could never be proved? $\endgroup$ – pac234 Feb 7 at 8:53
  • $\begingroup$ It makes sense with the brackets e.g (-I ^ -M) V H as both cannot be true so in that instance H is going to be true (I think), but without the brackets, I am not sure how to interpret it $\endgroup$ – pac234 Feb 7 at 9:01
  • $\begingroup$ For first comment (about CNF) I added to answer last equality. For last: $(I \lor M)\Rightarrow H$ is false if and only if when $I \lor M$ is true and $H$ is false. All other combinations gives implication true. $\endgroup$ – zkutch Feb 7 at 9:01
  • $\begingroup$ Can I ask something else related to your answer. When saying (I V M) is same as -(I ^ M) how does that work? If I = TV ON, M = LIGHTS ON, H = ELECTRICITY BEING USED then I V M => H means that if the lights or the tv are on electricity is being used. The OR is not exclusive so if both are true then electricity is still being used right? But if we now say -(I ^ M) does that not equate to saying if the lights are on and the tv is on on then electricity is not being used? $\endgroup$ – pac234 Feb 7 at 10:51
  • $\begingroup$ Let be little more careful: $\neg(I \land M)$ is not same with $I \lor M$, but with $(\neg I) \lor (\neg M)$. And $\neg(I \lor M)$ is same with $(\neg I) \land (\neg M)$. So sentence "TV ON or LIGHTS ON, then ELECTRICITY BEING USED" is same with "(TV NOT ON and LIGHTS NOT ON) or ELECTRICITY BEING USED" $\endgroup$ – zkutch Feb 7 at 11:02

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.