0

I have no idea how to start. really appreciate some help here.

Let P and Q be propositions. A statement S (involving P , Q ) is called a tautology iff for any truth-values of P and Q , the statement S is true. Show that the following statements are tautologies.

(a) (P∧(P⇒Q))⇒Q (Modus Ponen) (b) (¬Q∧(P⇒Q))⇒¬P (Modus Tollens). (c) (P∧(¬Q⇒¬P))⇒Q (Proof by Contradiction).

Malice Vidrine
  • 9,653
Jason Tan
  • 31

1 Answers1

1

To prove that $(P\wedge (P\Rightarrow Q))\Rightarrow Q$ is a tautology: $$ \begin{array} {|c|c|c|c|c|} \hline P & Q & P\Rightarrow Q & P\wedge (P\Rightarrow Q)& (P\wedge (P\Rightarrow Q))\Rightarrow Q\\ \hline 1 & 1 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 0 & 1\\ \hline 0 & 1 & 1 & 0 & 1\\ \hline 0 & 0 & 1 & 0 & 1\\ \hline \end{array} $$ To prove that $(\sim Q\wedge(P\Rightarrow Q))\Rightarrow (\sim P)$ is a tautology: $$ \begin{array} {|c|c|c|c|c|c|} \hline P & Q & P\Rightarrow Q & \sim Q& \sim Q\wedge(P\Rightarrow Q) & \sim P & (\sim Q\wedge(P\Rightarrow Q))\Rightarrow (\sim P)\\ \hline 1 & 1 & 1 & 0 & 0 & 0 & 1\\ \hline 1 & 0 & 0 & 1 & 0 & 0 & 1\\ \hline 0 & 1 & 1 & 0 & 0 & 1 & 1\\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1\\ \hline \end{array} $$ To prove that $(P\wedge(\sim Q\Rightarrow(\sim P)))\Rightarrow Q$ is a tautology: $$ \begin{array} {|c|c|c|c|c|c|c|} \hline P & Q & \sim P & \sim Q & \sim Q\Rightarrow(\sim P) & P\wedge(\sim Q\Rightarrow(\sim P) & (P\wedge(\sim Q\Rightarrow(\sim P)))\Rightarrow Q\\ \hline 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ \hline\end{array} $$ Here you are! I hope everything is clear now, but feel free to ask for additional clarification.