1

Show that the next conditional statement is a tautology without using truth tables:

$$ \big((p \ \vee q) \wedge(p \ \rightarrow r) \wedge(q \rightarrow r)\big) \rightarrow r $$

How to show it without truth table?

amWhy
  • 209,954
Koki
  • 21
  • 1
    It depends on what sort of proof system you have available to use other than truth tables. For example, natural deduction, a Hilbert-style proof system, etc.? – Daniel Schepler Oct 31 '17 at 21:17
  • You should give more context. Asking Readers to do $X$ without using $Y$ is bad form without an explanation of why $X$ is important to you in a way that excludes the use of $Y$. – hardmath Oct 31 '17 at 21:22
  • Do you need to use logical equivalences? A truth tree? What? Most pressingly, did you try anything yourself? – Bram28 Oct 31 '17 at 21:44

1 Answers1

2

Use the fact that $$(A \implies B) \equiv (\neg A \vee B) $$ And $$A \wedge (B\vee A)\equiv A$$ $$ \eqalign{P &\equiv((p \vee q) \wedge (p \implies q) \wedge (q \implies r))\implies r \\ &\equiv ((p \vee q) \wedge (\neg p \vee q) \wedge (\neg q \vee r))\implies r \\ &\equiv ((((p \vee q) \wedge \neg p) \vee ((p \vee q) \wedge q) )\wedge (\neg q \vee r))\implies r \\ &\equiv (((q \wedge \neg p) \vee q)\wedge (\neg q \vee r))\implies r \\ &\equiv (q\wedge(\neg p\vee q)\wedge (\neg q \vee r))\implies r \\ &\equiv (q \wedge (\neg q \vee r) \implies r \\ &\equiv (q \wedge r) \implies r \\ &\equiv \neg(q \wedge r) \vee r \\ &\equiv \neg q \vee \neg r \vee r \\ }$$ which is a tautology

J. Sadek
  • 516