Logical Equivalence Prove that p $\rightarrow$(q$\rightarrow$p) is logically equivalent to $\neg p$ $\rightarrow$(p$\rightarrow$q) without using truth table. It is easy to show that both the statements are tautologies. Can we prove the result directly?
 A: Use that $a\rightarrow b$ is equivalent to (or, in fact, defined to be) $(\neg a)\vee b$ and write out both sides.
A: $
\newcommand{\calc}{\begin{align} \quad &}
\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}
\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }
\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }
\newcommand{\endcalc}{\end{align}}
\newcommand{\ref}[1]{\text{(#1)}}
\newcommand{\then}{\rightarrow}
\newcommand{\followsfrom}{\leftarrow}
\newcommand{\true}{\text{true}}
\newcommand{\false}{\text{false}}
$Writing $\;\equiv\;$ for logical equivalence, the simplest approach is to use the rule that
$$
\tag{0}
A \then B \;\equiv\; \lnot A \lor B
$$
With this, the first expression can be rewritten as follows:
$$\calc
  p \then (q \then p)
\op\equiv\hints{the above rule $\ref 0$, twice}
          \hint{-- we can leave out the parentheses since $\;\lor\;$ is associative}
  \lnot p \lor \lnot q \lor p
\op\equiv\hints{symmetry, i.e., $\;A \lor B \;\equiv\; B \lor A\;$;}\hint{excluded middle, i.e., $\;\lnot A \lor A \;\equiv\; \true\;$}
  \true \lor \lnot q
\op\equiv\hint{$\;\true \lor A \;\equiv\; \true\;$}
  \true
\endcalc$$
In other words, the first expression is indeed a tautology.
Now do something similar with the second expression, et voilà.
A: I use Lukasiewicz/Polish notation.  
So, we know that CpCqp is a tautology.  Thus, CpCqp is logically equivalent to CpCNqp, since it qualifies as a special case of CpCqp (substitute 'q' with 'Nq' in CpCqp).  One equivalence says that CNxy == CNyx, where x and y are wffs.  Thus, since CpCNqp is logically equivalent to CpCNpq.  The law of commutation says that CxCyz == CyCxz.  Thus, CpCNpq is logically equivalent to CNpCpq.  Or in a different format:
axiom             1 CpCqp
special case of 1 2 CpCNqp
CNxy == CNyx, 2   3 CpCNpq
CxCyz == CyCxz    4 CNpCpq

The implicit meta-lemma which makes this reversible goes that if x and y are tautologies, then any given particular formula x is logically equivalent to any of it's generalizations y (this doesn't imply that all tautologies are logically equivalent so far as I can tell).  In other words, if x and y are tautologies, then if we can obtain x from y just by substitution, then x and y are logically equivalent.  Thus we can write:
axiom               1 CNpCpq
CxCyz == CyCxz      2 CpCNpq
CNxy == CNyx        3 CpCNqp
3 is a special case of CpCqp
                    4 CpCqp

