Simplify Logic using One Connective: Solving ((q→p) ^ (p→r))→(r→q)

  • Context:
  • Thread starter Thread starter c4nn3t
  • Start date Start date
  • Tags Tags
    Logic
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
1 reply · 2K views
c4nn3t
Messages
3
Reaction score
0
So I've got

((q→p) ^ (p→r))→(r→q)

And I have to simplify it down as much as possible using only one logical connective for the end result (not one type, just one total). Here's been my workflow so far:

((¬q v p) ^ (¬p v r))→(¬r v q)
¬((¬q v p) ^ (¬p v r)) v (¬r v q)
¬(¬q v p) v ¬( ¬p v r)) v (¬r v q)
(q ^ ¬p) v (p ^ r) v (¬r v q)

From here, I'm not sure how to boil down this DNF form into a single 'x and/or/implies y'

Mucho thanks in advance ;)
 

Discussion

Physics news on Phys.org
c4nn3t said:
(q ^ ¬p) v (p ^ r) v (¬r v q)
The middle disjunct should be $p\land\neg r$.

Use the fact that $(x\land y)\lor x=x$. Indeed,
\[
(x\land y)\lor x=(x\land y)\lor (x\land 1)=x\land (y\lor 1)=x\land 1=x.
\]