-1
$\begingroup$

I'm trying to solve a logic problem, and I'm wondering if it can be done using truth tables or propositional logic. The problem goes like this:

Who killed the mouse?

  • The owl said the hawk did it.
  • The sparrow said the hawk did it.
  • The hawk said the sparrow is lying.
  • The eagle said it wasn't me.

Only one is telling the truth.

I'm struggling to find a solution using a truth table, and I'm not sure if it's even possible. I know I could use propositional logic to represent the statements using logical operators and variables, but I am not sure more specifically how that's done. I'm not sure if that would be the most efficient approach.

How can I approach this problem using truth tables or propositional logic?

Here is where I found this puzzle: https://cdn.discordapp.com/attachments/869145673197580298/1083855309942030346/PIL_-_sammanfattning_av_fragor_oscar_bakhouch.doc

$\endgroup$
3
  • 2
    $\begingroup$ Does this answer your question? Which person is telling the truth? $\endgroup$ Commented Apr 6, 2023 at 14:53
  • 1
    $\begingroup$ I wrote that I wanted to solve it using propositional logic and with truth tables. That post doesn't address those two. $\endgroup$
    – cricket900
    Commented Apr 6, 2023 at 15:10
  • $\begingroup$ We require proper attribution of content you did not create yourself, as has been mentioned to you previously. Please do not forget to include this. Also, in situations like this one where you have already asked about this same puzzle here, and had it closed as a duplicate of Which person is telling the truth?, it's best to state explicitly what you are looking for and why none of the prior questions' answers helped, so people know you've already seen those posts and don't just keep trying to point you back to them. $\endgroup$
    – Rubio
    Commented Apr 6, 2023 at 20:57

2 Answers 2

1
$\begingroup$

Using truth tables (which is clearly not an efficient way of doing this) : We have 8 variables : for each bird (O for Owl, S for Sparrow, H for Hawk and E for eagle), the bird could have killed the mouse X_kill and the bird could say the truth X_truth. So for example, the two variables linked to the owl will be O_kill and O_truth.

We make a table with 256 row (2^^8) with every possibilities (even clearly wrong ones, like everyone is lying and everyone killed the mouse.) Then we evaluate the following for each row:

( // Only one bird is saying the truth
    (O_truth & ~(S_truth | H_truth | E_truth) 
  | (S_truth & ~(O_truth | H_truth | E_truth) 
  | (H_truth & ~(O_truth | S_truth | E_truth) 
  | (E_truth & ~(O_truth | S_truth | H_truth)
)
&
( // Take into account what every bird said
    ((O_truth & H_kill)   | (~O_truth & ~H_kill))
  & ((S_truth & H_kill)   | (~S_truth & ~H_kill))
  & ((H_truth & ~S_truth) | (~H_truth & S_truth))
  & ((E_truth & ~E_kill)  | (~E_truth & E_kill) )
)

Each row that's true for this evaluation is a solution (hopefully we only get one)

$\endgroup$
3
  • 1
    $\begingroup$ This yields a truth table with four true rows, all of which have E_kill true. To reduce to a single true row, you need to also impose that there is only one killer. $\endgroup$
    – RobPratt
    Commented Apr 6, 2023 at 15:56
  • $\begingroup$ @RobPratt nothing in the problem states that there is only one killer: "Who killed the mouse ?" could have multiple killers as a valid answer. But I agree that I should probably impose a single killer. $\endgroup$ Commented Apr 6, 2023 at 16:31
  • $\begingroup$ Alternatively, you can omit O_kill and S_kill because otherwise they don't appear anywhere. The resulting table then has $2^6$ rows instead of $2^8$, and then only one row is true. $\endgroup$
    – RobPratt
    Commented Apr 6, 2023 at 18:48
1
$\begingroup$

You can solve the problem via integer linear programming as follows. For each bird $b$, let binary decision variable $t_b$ indicate whether $b$ tells the truth and let binary decision variable $k_b$ indicate whether $b$ is the killer. The constraints are \begin{align} t_\text{owl} &= k_\text{hawk} \\ t_\text{sparrow} &= k_\text{hawk} \\ t_\text{hawk} &= 1 - t_\text{sparrow} \\ t_\text{eagle} &= 1 - k_\text{eagle} \\ \sum_b t_b &= 1 \\ \sum_b k_b &= 1 \end{align}

This system of linear equations and inequalities has exactly one solution:

$t_\text{hawk} = k_\text{eagle} = 1$ and all other $t_b = k_b = 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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