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!


1 Answer 1


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.


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.