# 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. – Bram28 Dec 7 '16 at 13:16
• Thanks for pointing out, was a typo ;) I'll have a look into substitutions right now. – Known Zeta Dec 7 '16 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. – Known Zeta Dec 7 '16 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$. – Bram28 Dec 7 '16 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? – Known Zeta Dec 7 '16 at 15:39
• @KnownZeta Yeah, you are right: you indeed can not do that with that one. ... so were you able to simplify everything? – Bram28 Dec 7 '16 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. – Known Zeta Dec 7 '16 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? – Known Zeta Dec 7 '16 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. – Reese Dec 8 '16 at 1:05