World's most popular travel blog for travel bloggers.

# Modelling 2 object situation with Propositional Logic

, ,
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!

###### 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.