Currently i have 3 situations as such:
B: You choose bibimbap
H: You choose haggis
M: You choose manakish
I'm required to write a proposition in Conjunctive Normal Form using B,H,M that is True when 'you choose either bibimbap or both of the other items'.
The proposition i came up with is:
(B Λ ¬H Λ ¬M) v (¬B Λ H Λ M)
and the help i need is the conversion process to CNF. I used Wolfram Alpha to produce a CNF as follows:
(¬B V ¬M) Λ (B Λ H) Λ (¬H V M)
but i want to convert the proposition on my own but I really don't fully understand how the conversion works. I'll appreciate if i get a detailed guide on converting to CNF as I'm very confused about the process.
You know the FOIL principle from high school algebra, right?
$$(a + b)(c + d) = ac+ad+bc+bd$$
Well, with larger terms it still works the same way: pick all different combinations. E.g:
$$(a + b + c)(d + e + f) = ad+ae+af+bd+be+bf+cd+ce+cf$$
Now, as it turns out, in boolean algebra the same distributive principles hold. So, applied to your statement, we get:
$$(B \land \neg H \land \neg M) \lor (\neg B \land H \land M) = \text{ (Distribution)}$$
$$ (B \lor \neg B) \land (B \lor H) \land (B \lor M) \land (\neg H \lor \neg B) \land (\neg H \lor H) \land (\neg H \lor M ) \land (\neg M \lor \neg B) \land (\neg M \lor H) \land (\neg M \lor M ) $$
Now, we can get rid of tautologies like $B \lor \neg B$:
$$ (B \lor \neg B) \land (B \lor H) \land (B \lor M) \land (\neg H \lor \neg B) \land (\neg H \lor H) \land (\neg H \lor M ) \land (\neg M \lor \neg B) \land (\neg M \lor H) \land (\neg M \lor M )= \text{ (Complement)}$$
$$ \top \land (B \lor H) \land (B \lor M) \land (\neg H \lor \neg B) \land \top \land (\neg H \lor M ) \land (\neg M \lor \neg B) \land (\neg M \lor H) \land \top = = \text{ (Identity)}$$
$$ (B \lor H) \land (B \lor M) \land (\neg H \lor \neg B) \land (\neg H \lor M ) \land (\neg M \lor \neg B) \land (\neg M \lor H)$$
OK, now you can apply something called the Consensus Theorem:
$(P \land Q) \lor (\neg Q \land R) \lor (P \land R) = (P \land Q) \lor (\neg Q \land R)$
And its dual principle is:
$(P \lor Q) \land (\neg Q \lor R) \land (P \lor R) = (P \lor Q) \land (\neg Q \lor R)$
Applied to your statement, we can see that $B \lor M$ is the consensus of $B \lor H$ and $\neg H \lor M$, and hence can be removed. Likewise, $\neg H \lor \neg B$ is the consensus of $\neg H \lor M $ and $\neg M \lor \neg B$, and $\neg M \lor H$ is the consensus of $\neg M \lor \neg B$ and $B \lor H$, so those can be removed as well, leaving us with:
$$ (B \lor H) \land (B \lor M) \land (\neg H \lor \neg B) \land (\neg H \lor M ) \land (\neg M \lor \neg B) \land (\neg M \lor H) = \text{ (Consensus x3)}$$
$$ (B \lor H) \land (\neg H \lor M ) \land (\neg M \lor \neg B) $$