Prove that $(p \to q) \lor (q \to p)$ is a tautology using natural deduction

Question

I have to prove that ' (p ⊃ q) ∨ ( q ⊃ p) ' is a tautology.I have to start by giving assumptions like a1 ⇒ p ⊃ q and then proceed by eliminating my assumptions and at the end i should have something like ⇒(p ⊃ q) ∨ ( q ⊃ p) but could not figure out how to start.

Answer 1

(p ⊃ q) ∨ ( q ⊃ p)

I assume that "⊃" means "implies". Actually, since your statement is symmetric in p and q, it doesn't matter if "a ⊃ b" means "a implies b" or "b implies a".

Since "a ⊃ b" is equivalent to "~a ∨ b", your statement is equivalent to "(~p ∨ q) ∨ ( ~q ∨ p)".

Since "∨" is commutative and associative, this is the same as "(p ∨ ~p)∨(q ∨ ~q)" which is always true.

Is this what you wanted?

Answer 2

If you are allowed to use the law of the exluded middle, then propositional logic proofs are straight forward. You have 2 variables, that means you have 4 cases. Then you combine the cases using LEE and Or-Elimination. It looks like:

Dedution 1: $$\begin{array} {r|l} (11) & p \land q \\ (12) & p \\ (13) & q \\ & \vdots \\ (1.) & p \implies q \\ (1.) & (p \implies q) \lor (q \implies p) \end{array}$$

Deduction 2: $$\begin{array} {r|l} (21) & p \land \lnot q \\ (22) & p \\ (23) & \lnot q \\ & \vdots \\ (2.) & q \implies p \\ (2.) & (p \implies q) \lor (q \implies p) \end{array}$$

Deduction 3: $$\begin{array} {r|l} (31) & \lnot p \land q \\ & \vdots \\ (3.) & p \implies q \\ (3.) & (p \implies q) \lor (q \implies p) \end{array}$$

Deduction 4: $$\begin{array} {r|l} (41) & \lnot p \land \lnot q \\ & \vdots \\ (4.) & p \implies q \quad \text{(You could also establish }q \implies p\text{ here.)} \\ (4.) & (p \implies q) \lor (q \implies p) \end{array}$$

Also, you can assume $p \lor \lnot p$ and $q \lor \lnot q$.

What's left is to fill in the $\vdots$, organize the deductions, and use Or-Eliminations to suck the $(p \implies q) \lor (q \implies p)$ out of all the deductions.

Answer 3

$(p\rightarrow q)\lor (q\rightarrow p)\equiv (\lnot p\lor q)\lor (\lnot q\lor p)\equiv \lnot p\lor (q\lor\lnot q)\lor p\equiv \lnot p\lor T\lor p\equiv \lnot p\lor p\equiv T$

Answer 4

Start off by showing the law of the excluded middle (p V $\lnot$ p).

Put the proof of law of excluded middle here such that it ends as follows:

(p V $\lnot$ p)

Hypothesize p
    Hypothesize r
     .
     .
     .
     p
(r -> p)
((p -> q) V (r -> p))

(p -> ((p -> q) V (r -> p)))

 Hypothesize ~p
     hypothesize p
     .
     .
     .
     q
 (p -> q)
 ((p -> q) V (r -> p))

(~p -> ((p -> q) V (r -> p)))

By disjunction elimination,

((p -> q) V (r -> p)).

Therefore,

((p -> q) V (q -> p)).

End of proof.

One might see that:

(q -> ((p -> q) V (r -> p)))

is a theorem also.

In Polish notation one can write:

CqACpqCrp. This is a special case of a more general tautology:

CpACqrCsq. If you did all of calculations involving CpACqrCsq and CpACpqCrp you would find that the calculations involving CpACqrCsq has all the instances of CqACpqCrp. Additionally, say we start with

1. CpACqrCsq.

Now, we'll put 'a' for every instance of 'p', 'b' for every instance of 'q', 'c' for every instance of 'r', and 'd' for every instance of 's' in CpACqrCsq. Doing that, we obtain:

2. CaACbcCdb.

Now we put 'q' for 'a', 'p' for every instance of 'b', 'q' for every instance of 'c', and 'r' for 'd' obtaining:

3. CqACpqCrp.

Thus, CqACpqCrp can get obtained from CpACqrCsq and using just a rule of substitution. But, we cannot obtain CpACqrCsq from CqACpqCrp, since CpACqrCsq has more distinct letters in it and they have the same length and the same pattern of big letters.

CpACqrCsp is also a tautology.

CpACpqCrp is also a tautology.

CNpACpqCrs is also a tautology.

CNpACqrCsq is also a tautology.

Answer 5

As a quick overview: You should be able to show $p\vdash q\supset p$ as well as $\neg p\vdash p\supset q$, and then by case distinction $p\lor\neg p\vdash (p\supset q)\lor (q\supset p)$.