Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 2.7.2 Tautologies

Recall this truth table that we built for the expression \((p \wedge q) \vee p\) :

\(p \)	\(q \)	\(p \wedge q \)	\((p \wedge q) \vee p \)
T	T	T	T
T	F	F	T
F	T	F	F
F	F	F	F

Stare at it for a moment. Do you see that the \((p \wedge q) \vee p \) column is identical to the p column? Remembering the notion of is equivalent to, can we claim that \((p \wedge q) \vee p\) is equivalent to p? Let’s build a truth table for \(((p \wedge q) \vee p) = p\text{.}\) It begins, just like the one above:

\(p \)	\(q \)	\(p \wedge q \)	\((p \wedge q) \vee p \)	\(((p \wedge q) \vee p) = p \)
T	T	T	T
T	F	F	T
F	T	F	F
F	F	F	F

We obtain the four entries for the final column by consulting the truth table for is equivalent to:

\(p \)	\(q \)	\(p = q \)
T	T	T
T	F	F
F	T	F
F	F	T

So our final table is

\(p \)	\(q \)	\(p \wedge q \)	\((p \wedge q) \vee p \)	\(((p \wedge q) \vee p) = p \)
T	T	T	T	T
T	F	F	T	T
F	T	F	F	T
F	F	F	F	T

Now notice the final column has all T’s. That means that whatever the truth values for p and q, \(((p\wedge q)\vee p) = p \) must be true.

Recall that an expression that is true for all possible truth values of its variables is called a tautology. We’ll also say that such an expression is valid. Tautologies correspond to our everyday idea of “true statements”. In other words, they correspond to claims that are guaranteed to be true, in all cases.

((p ∧ q) ∨ p) ≡ p is the first expression that we have proved to be a tautology. We will soon prove many more.