# Forming a propositional formula from recursive statements

I'm having trouble combining/forming a single propositional formula from 3 recursively expressed statements. The original setting of the problem is something like:

There are three people $A$, $B$ and $C$.

• $A$ said: $B$ and $C$ told the truth if and only if $C$ told the truth.

• $B$ said: If $A$ and $C$ told the truth, then it is not the case that: if $B$ and $C$ told the truth, then $A$ told the truth.

• $C$ said: $B$ did not tell the truth if and only if $A$ or $C$ told the truth.

From the statements I was able to formulate 3 propositional formulas for each person. I used $T_A$, $T_B$ and $T_C$ to represent the variables for the statements of each candidate, if they were true. That is,

• for $A$: $T_A \Leftrightarrow ((T_B \land T_C) \Leftrightarrow T_C)$

• for $B$: $T_B \Leftrightarrow ((T_A \land T_C) \Rightarrow \lnot ((T_B \land T_C) \Rightarrow T_A))$

• for $C$: $T_C \Leftrightarrow ((T_A \lor T_C) \Leftrightarrow \lnot T_B)$

Now I am supposed to combine the 3 formulas above to a single one. My thought is after doing this, we could enumerate what would the value of the whole formula be for all the possible values of $T_A$, $T_B$ and $T_C$. If the whole formula turned out to be $true$ somewhen, then we could tell who actually lies judging from the value of $T_A$, $T_B$ and $T_C$.

I'm stuck here because the statements are recursive. I assume the 3 formulas I wrote above are correct. (Please correct me if I was wrong!) I was kind of always chasing my tail and didn't come up with a solution.

How should I combine the above 3 formulas correctly?

• The $T_B$ at the end of sentence 2 should be $T_A$. Also, since these are biconditionals, you can substitute. E.g. If you have $P \leftrightarrow Q$, and you have some other statement that involves $P$'s, then you can substitute $Q$ for those $P$'s in the other sentence. Since you have $T_A \leftrightarrow ...$ where the right side only involves further $T_B$s and $T_C$s, you can at least make that substitution in the other two sentences, and thus have only those $T_B$s and $T_C$s left ... And with a little luck you can sinplify once you make those substitutions. Dec 7, 2016 at 13:16
• Thanks for pointing out, was a typo ;) I'll have a look into substitutions right now. Dec 7, 2016 at 13:18

HINTS

1. Whenever you have $\varphi \leftrightarrow \psi$, and you have some other statement that involves $\varphi$'s, then you can substitute $\psi$'s for those $\varphi$'s in the other sentence. Or, as a general principle:

$(\varphi \leftrightarrow \psi) \land S(\varphi) \Leftrightarrow (\varphi \leftrightarrow \psi) \land S(\psi)$

where $S(\varphi)$ is a sentence containing any number of $\varphi$'s, and $S(\psi)$ is the result of substituting any number of those $\varphi$'s with $\psi$'s.

So in your case, you can go from:

$(T_A \Leftrightarrow ((T_B \land T_C) \Leftrightarrow T_C)) \land$

$(T_B \Leftrightarrow ((T_A \land T_C) \Rightarrow \lnot ((T_B \land T_C) \Rightarrow T_A))) \land$

$(T_C \Leftrightarrow ((T_A \lor T_C) \Leftrightarrow \lnot T_B))$

to:

$(T_A \Leftrightarrow ((T_B \land T_C) \Leftrightarrow T_C)) \land$

$(T_B \Leftrightarrow ((((T_B \land T_C) \Leftrightarrow T_C) \land T_C) \Rightarrow \lnot ((T_B \land T_C) \Rightarrow ((T_B \land T_C) \Leftrightarrow T_C)))) \land$

$(T_C \Leftrightarrow ((((T_B \land T_C) \Leftrightarrow T_C) \lor T_C) \Leftrightarrow \lnot T_B))$

1. You can do some simplifications (and I'll write $A$ for $T_A$ to save some typing):

$(B \land C) \leftrightarrow C \Leftrightarrow$ (rewrite $\leftrightarrow$)

$((B \land C) \land C) \lor (\neg (B \land C) \land \neg C)) \Leftrightarrow$ (Association, DeMorgan)

$(B \land (C \land C)) \lor ((\neg B \lor \neg C) \land \neg C))\Leftrightarrow$ (Idempotence, Absorption)

$(B \land C) \lor \neg C)\Leftrightarrow$ (Reduction)

$B \lor \neg C$

Also: $\neg ((B \land C) \rightarrow A) \Leftrightarrow (B \land C) \land \neg A$

• Just simplified $T_A$ and $T_B$. ;) But reading Reese's answer, I'm a bit confused. Is the 1st rule still supposed to work here? Perhaps I didn't quite understand the relationship among the three variables in this situation. What I thought is that in the end I shall make a truth table involving $T_A$, $T_B$ and $T_C$, as well as the final formula, and see when the final formula is true. Substituting/taking out $T_A$ is a bit weird, though it does make sense for me. Dec 7, 2016 at 14:36
• @KnownZeta Yeah, you can do the substitution within a conjunction. I'll add that to my Answer. And that way, you'll see that you don't really take out $T_A$. Dec 7, 2016 at 15:08
• Got it. One more question, so for the formula for $T_C$, we however cannot view it this way that $T_B$ can also be substituted with $\lnot (T_A \lor T_C)$, since it's not directly connected with others with $\land$, but rather within a bubble which is connected to $T_C$ with $\Leftrightarrow$. Am I right? Dec 7, 2016 at 15:39
• @KnownZeta Yeah, you are right: you indeed can not do that with that one. ... so were you able to simplify everything? Dec 7, 2016 at 15:59
• Yes, I simplified the formula to $(A \leftrightarrow (B \lor \lnot C)) \land (B \leftrightarrow (\lnot B \lor \lnot C)) \land (C \leftrightarrow \lnot B)$. Then I tried to turn it into a form with only $\land$, $\lor$ and $\lnot$ but it seems to be counterintuitive since the form seems to be much more complicated. Dec 7, 2016 at 16:46

Combining three formulas is surprisingly straightforward - you have three formulas that must simultaneously be true, so you want to put an $\wedge$ between them. So your final formula would be $(T_A \iff ((T_B \wedge T_C) \iff T_C)) \wedge (T_B \iff ((T_A \wedge T_C) \Rightarrow \neg((T_B \wedge T_C) \Rightarrow T_A))) \wedge (T_C \iff ((T_A \vee T_C) \iff \neg T_B))$.

• I'm a bit confused. This seem to have cleared my problems, but are substitutions suggested by Bram applicable in this situation? Dec 7, 2016 at 14:41
• @KnownZeta Of course - "substitution" means replacing parts of the sentence with parts that have the same truth values. It's legal no matter what. It looks to me like Bram has now covered this very well in his answer, so hopefully that was enough to get you going. Dec 8, 2016 at 1:05