# Finding a truth function

I wanted to find a truth function $f$ if it exists that make the formula below true:

$((p\to \lnot(q \oplus \lnot p)) \to (\lnot r \oplus (q \to p)))$

Where the $\oplus$ operator is defined as:

$(A \oplus B) \equiv ((A \land \lnot B) \lor (B \land \lnot A))$

My understanding was that to find the truth function that makes this formula true I needed to construct a truth table and the write down all rows where the LHS $\to$ RHS e.g $f(1,0,1) = 1$ However with the $\oplus$ operator definition the truth table would get quite length so I tried to simplify it with logical laws to make the formulas shorter for the LHS I simplified it down to $p \to \lnot q$ but for the RHS I had a bit more trouble with the logical laws and only managed to get it down to:

$((\lnot r \land (q \land \lnot p)) \lor (r \land (\lnot q \lor p))$

Am I on the right track with how I've attempted this question? Is it necessary to simplify the RHS further before putting it in a truth table?

• I believe you're fine. Your reduction of the LHS is fine. As for reducing the RHS, I'm not sure you need to get too crazy. $\oplus$ has its own truth table, so evaluating $\lnot r \oplus (q \to p)$ shouldn't be particularly onerous. Another approach is to see where the formula is false; this gives you the values that won't be in your truth function. – Ken Jun 6 '15 at 6:39
• Perhaps observing that $\oplus$ is just exclusive or en.wikipedia.org/wiki/Exclusive_or i.e. $A \oplus B$ is true iff $A$ and $B$ have opposite values, would have made setting out the truth table easier. The table would have only 8 lines, and without converting the formula with $\oplus$ into its equivalent that uses only $\{ \lor , \land , \lnot \}$ would be quite manageable to evaluate, I'd say. Nice approach to make your work easier via syntactic means though. – prime4567 Jun 6 '15 at 15:07
• Which connectives can you use? – Doug Spoonwood Jun 6 '15 at 23:00
• There is no $f$ in your formula. – DanielV Feb 3 '16 at 15:21

I don't think that it would be necessary to simplify everything, in its current form one can derive the truth table of $\small\tt P$ without too much work, $$\begin{array}{|c|c|c|c|c|c|c|c|}\hline \small\color{green}{p} &\small \color{green}{q} &\small \color{green}{r} &\small \lnot p &\small (q\oplus\lnot p) &\small \lnot(q\oplus\lnot p) &\small ((p\to \lnot(q \oplus \lnot p)) &\small \lnot r &\small (q\to p)&\small (\lnot r \oplus (q \to p))) & \small\tt P \\ \hline \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} \\ \hline \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} \\ \hline \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} \\ \hline \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} \\ \hline \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{#C00}{0} \\ \hline \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} \\ \hline \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} \\ \hline \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{royalblue}{1} & \small\color{#C00}{0} & \small\color{#C00}{0} \\ \hline \end{array}$$