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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Ken Jun 6 '15 at 6:39
  • $\begingroup$ 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. $\endgroup$ – prime4567 Jun 6 '15 at 15:07
  • $\begingroup$ Which connectives can you use? $\endgroup$ – Doug Spoonwood Jun 6 '15 at 23:00
  • $\begingroup$ There is no $f$ in your formula. $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.