# Propositional logic: Finding a formula F with statement variables from truth table

I need to find a formula for $F$ with statement variables $H, M$ and $B$ such that the truth table for $F$ looks as follows:

Does anyone know a cool and/or easy way to solve problems like this? Would be much appreciated.

• see en.wikipedia.org/wiki/Karnaugh_map good luck – Willemien Sep 8 '13 at 20:58
• There is a systematic method for problems like this. It is called Karnaugh map or K-map. – qsp Sep 8 '13 at 21:51
• @Willemien At least if you only have a handful of variables around. – Doug Spoonwood Sep 8 '13 at 23:11

Layout: You want the first line to be true when $H,M$ and $B$ are all true. So your statement $F$ must look like $(H\land M\land B)\lor \text{Something}$.

But you also want it to be true when $H,M$ are true and $B$ is false, equivalently, when $H, M$ and $\neg B$ is true. So, using the information in the paragraph above, $F$ must look like $(H\land M\land B)\lor (H\land M\land \neg B)\lor \text{Something else}$.

Proceed in this fashion to find $F$.

Edit: Firstly note that we need only apply this technique for the true lines, because by exactly pinpointing the true lines, the falsehoods will be determined.

So inspecting the true lines you can find: $$(H\land M\land B)\lor (H\land M\land \neg B)\lor (H\land \neg M\land B)\lor (\neg H\land M\land B),$$ which has the expected truth table:

• This is what i've done so far:(H ∧ M ∧ B) ∨ (H ∧ M ∧ ¬B) ∨ (H ∧ ¬M ∧ B) ∨ (H ∨ ¬M ∨ ¬B) ∨ (¬H ∨ M ∨ B) ∨ (¬H ∨ M ∨ ¬B) ∨ (¬H ∧ ¬M ∧ B) ∨ (¬H ∧ ¬M ∧ ¬B) is this correct? Also im not sure what to do next.. also if you can help me out with the answer and explanation, i would appreciate it – Dabbish Sep 8 '13 at 21:12
• @Dabbish Inside the parentheses you're writing disjunctions. Is that your intention? If not, edit the comment while you can. – Git Gud Sep 8 '13 at 21:15
• This is my first post here, sorry for that. I'm not able to edit the post now, but no that's not my intention. – Dabbish Sep 8 '13 at 21:32
• @Dabbish I'm adding stuff to the answer, give me a few minutes. – Git Gud Sep 8 '13 at 21:32
• @Dabbish I added some stuff to the answer. Does it help? – Git Gud Sep 8 '13 at 21:54

Since $F$ is true if and only if at least two from the three variables $H$, $M$ and $B$ are true, $$F=(H\land M)\lor(M\land B)\lor(B\land H).$$

You can solve this by eyeballing it and reasoning it out.

First look at the true values in the F column. Those are your goal. Among the three premises, H has the most true values in common, 4 vs. 3, so start with a formula just containing $H$. That gives you 6 out of 8 correct values. Now there only two rows to fix.

For the first one, the fourth row, F is false when M and B are false, so F is true when H is true and either M is true or B is true. So we have $H \wedge (M \vee B)$, which covers the first four rows.

Now we need to get that last true value in the fifth row. We can just add an or clause to what we have so far. It's true when M and B are both true, so that makes $[H \wedge (M \vee B)] \vee (M \wedge B)$ and you're done.

That's how I do it, anyway. Hope that helps.