Classifying Formulas

Classifying a single formula

Consider a truth table for the formulas $P\vee Q$, $P\vee \neg P$, and $P\wedge\neg P$:

$P$	$Q$	$(P\vee Q)$	$(P\vee \neg P)$	$(P\wedge \neg P)$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$

These formulas can be placed in different categories:

1. Always true: The formula $P\vee \neg P$ is true in every row of the truth table.
2. Always false: The formula $P\wedge \neg P$ is false in every row of the truth table.
3. Sometimes true and sometimes false: The formula $(P\vee Q)$ is true in the first three rows and false in the last row.

In fact, any formula can be placed into one of the above three categories. The following terminology will be used to classify formulas.

Tautology

A formula $X$ is a tautology if every truth value assignment makes $X$ true.

Contradiction

A formula $X$ is a contradiction if every truth value assignment makes $X$ false.

Contingent

A formula $X$ is a contingent formula if there is a truth value assignment that makes $X$ true and a truth value assignment that makes $X$ false.

The following is a summary of the procedure to use a truth table to classify a formula $X$ as either a tautology, contingent or a contradiction:

Classifying collections of formulas

In addition to classifying formulas, we use truth tables to identify interesting relationships between formulas. To illustrate, consider a truth table for the formulas $P\wedge Q$, $\neg (P\wedge Q)$, $\neg P\vee \neg Q$ and $\neg P \wedge \neg Q$:

$P$	$Q$	$(P\wedge Q)$	$\neg (P\wedge Q)$	$(\neg P\vee \neg Q)$	$(\neg P\wedge \neg Q)$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

This truth table reveals the following realtionships between the four formulas:

1. In every row, $P\wedge Q$ and $\neg (P\wedge Q)$ have different truth values.
2. In every row, $\neg (P\wedge Q)$ and $\neg P\vee \neg Q$ have the same truth value.
3. The formulas $P\wedge Q$ and $\neg P \wedge \neg Q$ are never true in the same row, but there are rows in which they are both false (rows 2 and 3).
4. There is a row in which the formulas $\neg P\vee \neg Q$ and $\neg P \wedge \neg Q$ are both true (row 4).

We introduce the following terminology to classify the relationship between formulas.

Tautologically Equivalent

The formulas $X$ and $Y$ are tautologically equivalent if every truth value assignment gives the same truth value to $X$ and $Y$.

Contradcitory

The formulas $X$ and $Y$ are contradictory if every truth value assignment gives the different truth values to $X$ and $Y$.

Mutually Exclusive

The formulas $X$ and $Y$ are mutually exclusive, also called contraries, if there is no truth value assignment in which $X$ and $Y$ are both true.

Satisfiable

The formulas $X$ and $Y$ are satisfiable if there is a truth value assignment in which both $X$ and $Y$ are true.

The following is a summary of the procedure to use a truth table to classify two formulas $X$ and $Y$ as either tautologically equivalent, contradictory, satisfiable or mutually exclusive:

There are two important observations about classifying two formulas:

1. If $X$ and $Y$ are contradictory, then they are also mutually exclusive. But, if $X$ and $Y$ are mutually exclusive, then they may not be contradictory (since there may be a truth value assignment that makes both false).

2. If $X$ and $Y$ are tautologically equivalent, then they may or may not be satisfiable. For instance, if $X$ and $Y$ are both contradictions, then they are tautologically equivalent, but they are not satisfiable.

Practice Questions

I. Answer the following true/false questions.

1. There is a formula that is both contingent and a tautology.
   True

   False

   ​

   If $X$ is contingent, then you must be able to find two different truth value assignments. One that makes $X$ true and one that makes $X$ false. Since there must be at least one truth value assignment that makes $X$ false, $X$ is not a tautology.

2. For any formula $X$, if $X$ is contingent, then $\neg X$ is also contingent.

   True

   False

   ​

   If $X$ is contingent, then you must be able to find two different truth value assignments. One that makes $X$ true and one that makes $X$ false. The truth value assignment that makes $X$ true will make $\neg X$ false and the truth value assignment that makes $X$ false will make $\neg X$ true. So, $\neg X$ is contingent.

3. For all formulas $X$ and $Y$, if $X$ is a tautology and $Y$ is contingent, then $X\wedge Y$ is a tautology.

   True

   False

   ​

   For example, let $X$ be $P\vee \neg P$ and $Y$ be $Q$. The truth value function that assigns $\mathsf{T}$ to $P$ and $\mathsf{F}$ to $Q$, assigns $\mathsf{F}$ to $(P\vee\neg P) \wedge Q$. So, $(P\vee\neg P) \wedge Q$ is not a tautology.

4. For all formulas $X$ and $Y$, if $X$ is a tautology and $Y$ is contingent, then $X\vee Y$ is a tautology.

   True

   False

   ​

   For all formulas $X$ and $Y$, if $X$ is a tautology, then every truth value assignment makes $X$ true. This immediately implies that every truth value assignment will make $X\vee Y$ true.

5. For all formulas $X$ and $Y$, if $X$ is a contradiction and $Y$ is contingent, then $X\rightarrow Y$ is a tautology.

   True

   False

   ​

   Since conditionals are true when the antecedent is false and every truth value assignment makes $X$ false, every truth value assignment makes $X\rightarrow Y$ true.

6. For all formulas $X$ and $Y$, if $X$ is contingent and $Y$ is contingent, then $X\rightarrow Y$ is contingent.

   True

   False

   ​

   For example, let $X$ be $P\wedge Q$ and $Y$ be $P$. Both $P\wedge Q$ and $P$ are contingent, but $(P\wedge Q)\rightarrow P$ is a tautology.

7. For all formulas $X$ and $Y$, if $X$ and $Y$ are tautologically equivalent, then $\neg X$ and $\neg Y$ are tautologically equivalent.

   True

   False

   ​

   Suppose that $X$ and $Y$ are tautologically equivalent. Then every truth value function assigns the same truth value to $X$ and $Y$. This means that every truth value function assigns the same truth value to $\neg X$ and $\neg Y$. So, $\neg X$ and $\neg Y$ are tautologically equivalent.

II. Classify the following formulas as contingent, a contradiction or a tautology.

1. $(P\wedge Q)\rightarrow \neg (P\vee Q)$

2. $(P\rightarrow Q) \vee (Q\rightarrow P)$

3. $\neg (P\rightarrow Q) \rightarrow P$

4. $P\rightarrow (Q\vee R)$

5. $(\neg (Q\vee R) \wedge Q) \rightarrow P$

6. $(P\rightarrow Q) \wedge (Q\rightarrow P)$

7. $(P\wedge Q) \vee (P\wedge \neg Q)$

8. $\neg (P\wedge \neg P)$

9. $\neg (P\vee \neg P)$

10. $\neg (P\wedge Q) \vee (\neg P\vee \neg Q)$

11. $\neg(P\vee Q) \vee (\neg P\wedge \neg Q)$

12. $(P\vee Q) \vee (\neg P\wedge \neg Q)$

13. $\neg (P\vee (P\wedge Q))$

14. $((P\rightarrow Q) \rightarrow P)\rightarrow P$

15. $(P\vee Q) \rightarrow (P\wedge Q)$

III. Classify the following pairs of formulas as tautologically equivalent, contradictory, contraries, or satisfiable.

1. $P\wedge Q$ and $\neg P \vee \neg Q$

2. $P\vee Q$ and $\neg P \vee \neg Q$

3. $P\rightarrow Q$ and $\neg Q \rightarrow \neg P$

4. $P \wedge Q$ and $\neg P$

5. $P\vee\neg P$ and $Q\vee \neg Q$

6. $P\wedge\neg P$ and $Q\wedge \neg Q$

7. $(P\wedge Q)\rightarrow R$ and $\neg P\vee \neg Q \vee R$

8. $\neg P\rightarrow Q$ and $P\rightarrow R$

9. $R \rightarrow P$ and $R\rightarrow ~P$

10. $P\rightarrow \neg P$ and $~P$

11. $P\wedge Q$ and $P\rightarrow \neg Q$

12. $P\wedge (Q\vee R)$ and $(\neg P\wedge \neg Q \wedge \neg R)$

13. $P\rightarrow Q$ and $Q\rightarrow P$

14. $P\rightarrow Q$ and $P\wedge \neg Q$

15. $P\rightarrow R$ and $(P \wedge Q)\rightarrow R$