Answer to Question #275316 in Discrete Mathematics for fish

Question

 

Show that each of these conditional statements is a tautology by using truth tables.

 

a) (p ∧ q) → p                b) p → (p ∨ q)

c) ￢p → (p → q)                            d) (p ∧ q) → (p → q)

e) ￢(p → q) → p                        f) ￢(p → q) → ￢q

Answer 1

Let us show that each of these conditional statements is a tautology by using truth tables.

 

a) (p ∧ q) → p               

$\begin{array}{||c|c||c|c||} \hline\hline p & q &p ∧ q & (p ∧ q) → p \\ \hline\hline 0 & 0 & 0 & 1\\ \hline 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 0 & 1\\ \hline 1 & 1 & 1 & 1\\ \hline\hline \end{array}$

Since the last column contains only 1, we conclude that this formula is a tautology.

b) p → (p ∨ q)

$\begin{array}{||c|c||c|c||} \hline\hline p & q &p \lor q &p → (p ∨ q) \\ \hline\hline 0 & 0 & 0 & 1\\ \hline 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1\\ \hline 1 & 1 & 1 & 1\\ \hline\hline \end{array}$

Since the last column contains only 1, we conclude that this formula is a tautology.

c) ￢p → (p → q)                            

$\begin{array}{||c|c||c|c|c||} \hline\hline p & q &\neg p & p \to q &\neg p → (p \to q) \\ \hline\hline 0 & 0 & 1 & 1 & 1\\ \hline 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 1\\ \hline 1 & 1 & 0 & 1 &1\\ \hline\hline \end{array}$

Since the last column contains only 1, we conclude that this formula is a tautology.

d) (p ∧ q) → (p → q)

$\begin{array}{||c|c||c|c|c||} \hline\hline p & q &p ∧ q & p \to q &(p ∧ q) → (p → q)\\ \hline\hline 0 & 0 & 0 & 1 & 1\\ \hline 0 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 1\\ \hline 1 & 1 & 1 & 1 &1\\ \hline\hline \end{array}$

Since the last column contains only 1, we conclude that this formula is a tautology.

e) ￢(p → q) → p                        

$\begin{array}{||c|c||c|c|c||} \hline\hline p & q & p \to q& \neg (p → q) & \neg(p → q) → p \\ \hline\hline 0 & 0 & 1 & 0 & 1\\ \hline 0 & 1 & 1 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1\\ \hline 1 & 1 & 1 & 0 &1\\ \hline\hline \end{array}$

Since the last column contains only 1, we conclude that this formula is a tautology.

f) ￢(p → q) → ￢q

$\begin{array}{||c|c||c|c|c|c||} \hline\hline p & q & p \to q& \neg (p → q) & \neg q & \neg (p → q) \to \neg q\\ \hline\hline 0 & 0 & 1 & 0 & 1 & 1\\ \hline 0 & 1 & 1 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 & 1\\ \hline 1 & 1 & 1 & 0 & 0 & 1\\ \hline\hline \end{array}$

Since the last column contains only 1, we conclude that this formula is a tautology.