0

I need to prove that the formula

  1. $P \leftrightarrow Q$

is a logical consequence of, but not logically equivalent, to the conjunction of the following:

  1. $Q \rightarrow R$
  2. $R \rightarrow (P \land Q)$
  3. $P \rightarrow (Q \lor R)$

I've been able to compute through logical equivalences that the conjunction of $(1), (2), (3)$ is equivalent to $(R \leftrightarrow Q) \land (R \rightarrow P) \land (P \rightarrow (Q \lor R))$. How should I continue?

Note: the question relates to propositional logic, not predicate logic.

ryang
  • 38,879
  • 14
  • 81
  • 179
Uncle Sam
  • 39

2 Answers2

1

If you assume $P$ then you get $Q \lor R$. Now, in the case of assuming $Q$, you already get $P \rightarrow Q$ by conditional introduction. In the case of assuming $R$, you get $P \land Q$ and thus $Q$, so you get $P \rightarrow Q$ again by conditional introduction. Therefore using disjunction elimination you get $P \rightarrow Q$. On the other hand if you assume $Q$ then you must get $R$, and now you get $P \land Q$, thus $Q \rightarrow P$. Combining the two facts gives $P \longleftrightarrow Q$.

Math Simp
  • 124
  • Thanks. Do you think there's any way to get rid of $R$ through logical equivalences from the conjunction of $1, 2, 3$? Or to obtain some simple equivalent formula that can be easily put into a truth table? I have a feeling that this should simplify to $(P \leftrightarrow Q) \land (Q \leftrightarrow R)$ or something of the sort... – Uncle Sam Jul 11 '21 at 11:20
  • Yes, you can easily convince yourself why ${Q \rightarrow R, R\rightarrow (P\land Q), P\rightarrow (Q\lor R)} \models (P\leftrightarrow Q)\land(Q\leftrightarrow R)$ as in the latter. And this is fine, since you can also use conjunction elimination to get your goal formula. But if you set $P = Q = R$ to be false then all premises are satisfied so ${Q \rightarrow R, R\rightarrow (P\land Q), P\rightarrow (Q\lor R)} \not \models R$ like your former intuition – Math Simp Jul 11 '21 at 11:33
  • Thanks again. However, I can't seem to find a way to get to the simplified formula only through logical equivalences that can be used for simplification (edit: sorry, I'm a non-native English speaker. I'm referring to the distributive, associative, De Morgan laws etc.). Do you have any indication on this? I find $3$ really problematic because of the disjunction inside. – Uncle Sam Jul 11 '21 at 12:07
  • If you are trying to show entailment (i.e. a formal deduction of $P \leftrightarrow Q$ from your premises) then you can use the strategy from my first comment (have you heard of disjunction elimination, conditional elimination, etc. ?) By soundness this also shows it is a tautological consequence. To just show the latter you can simply use a truth table – Math Simp Jul 11 '21 at 12:51
1

Further to Math Simp's answer, to also show that $0$ is not logically equivalent to $(1\land2\land3),$ i.e., that $(0\rightarrow (1\land2\land3))$ is not a tautology, it suffices to show that $(0\rightarrow1),$ i.e. $((P\leftrightarrow Q)\rightarrow(Q \rightarrow R))$, is not a tautology.

This is evident from the truth assignment $(P,Q,R)=(1,1,0).$

ryang
  • 38,879
  • 14
  • 81
  • 179