proof for a problem in propositional logic

Question

I cant find a proof for given problem:

$$p \to ( q \to p) ≡ \lnot p \to ( p \to q ) $$

Please give proof to prove above statement.

Answer 1

Just look at the possible truth values for (p,q) and check that the two formulas output the same value in the 4 cases.

If you want an axiomatic proof you can do this:

Since $a\to b$ is a notation for $\neg a\vee b$, we can unfold the first formula into $\neg p\vee (\neg q\vee p)$. This is actually equivalent to $true$, since $p\vee\neg p$ is always true. You can do the same with the other one, and so by showing they are both tautologic, you get that they are equivalent.

Answer 2

Hint: $A\implies B$ is equivalent to $\neg(A\wedge\neg B)$ and also to $\neg A\vee B$. Use De Moivre and transform both formulas in a disjunction of conjunctions.

Answer 3

$p\to q$ and $\sim p$ can be substituted with $1+p+pq$ respectively $1+p$, where $pq$ is short for $p\wedge q$ and $+$ is exclusive or. Therefore:

$(p\to(q\to p))\equiv 1+p+p(q\to p)\equiv 1+p+p(1+q+qp)\equiv 1+p+p+pq+pqp\equiv 1$, since $r+r\equiv 0$ for all $r$.

and

$(\sim p\to(p\to q))\equiv ((1+p)\to(1+p+pq))\equiv 1 +(1+p)+(1+p)(1+p+pq)\equiv$ $1+1+p+1+p+pq+p+pp+ppq\equiv 1$

Alternatively, prove that $p\to(q\to p)$ and $\sim p\to(p\to q)$ both are tautologies.

Answer 4

We have :

$$p → ( q → p) \equiv \lnot p \lor (\lnot q \lor p)$$

by Material Implication twice,

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

by Commutativity and Associativity,

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

by Negation laws : $p \lor \lnot p \equiv T$ and Identity laws : $T \lor p \equiv T$,

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

by Identity laws, Negation laws and Associativity again.

Finally :

$$\lnot p \rightarrow (p \rightarrow q)$$

by Material Implication twice.