If you want to make money online : Register now

Modelling 2 object situation with Propositional Logic

, , No Comments
Problem Detail: 

I'm reading up on propositional logic, and I'm completely stuck on this example - spent the past few hours trying to figure it out! Any pointers would be appreciated.

There's 2 trees, each with signs on.

Sign 1/Tree 1: There are leaves on this tree, and no leaves on the other

Sign 2/Tree 2: There are leaves on one of these trees, but none on the other.

Exactly one of the signs is true, and the other is false. Which tree has leaves on (without looking)?

I'm starting to doubt that it's possible to tell, but I'm sure there's some logic that says otherwise!

Asked By : sff
Answered By : Yuval Filmus

Let $P_1$ indicate that Tree 1 has leaves (i.e. $P_1$ is true if Tree 1 has leaves), and $P_2$ indicate that Tree 2 has leaves. Sign 1 states $S_1 = P_1 \land \lnot P_2$, and Sign 2 states $S_2 = (P_1 \land \lnot P_2) \lor (\lnot P_1 \land P_2)$. We are given that $R = (S_1 \land \lnot S_2) \lor (\lnot S_1 \land S_2)$.

In order to solve this, we simply calculate $S_1,S_2$ for each of the possible truth assignments of $P_1,P_2$: $$ \begin{array}{cc|cc|c} P_1 & P_2 & S_1 & S_2 & R \\\hline F & F & F & F & F \\ F & T & F & T & T \\ T & F & T & T & F \\ T & T & F & F & F \end{array} $$ The only truth assignment for which $R$ holds is $P_1 = F$, $P_2 = T$. We conclude that Tree 1 has no leaves and Tree 2 does have leaves.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22281

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback