Skip to main content

Classifying Formulas

Classifying a single formula#

Consider a truth table for the formulas P∨QP\vee Q, P∨¬PP\vee \neg P, and P∧¬PP\wedge\neg P:

PPQQ(P∨Q)(P\vee Q)(P∨¬P)(P\vee \neg P)(P∧¬P)(P\wedge \neg P)
T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}
T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}
F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}

These formulas can be placed in different categories:

  1. Always true: The formula P∨¬PP\vee \neg P is true in every row of the truth table.
  2. Always false: The formula P∧¬PP\wedge \neg P is false in every row of the truth table.
  3. Sometimes true and sometimes false: The formula (P∨Q)(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 XX is a tautology if every truth value assignment makes XX true.

Contradiction

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

Contingent

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

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

classify formulas

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∧QP\wedge Q, ¬(P∧Q)\neg (P\wedge Q), ¬P∨¬Q\neg P\vee \neg Q and ¬P∧¬Q\neg P \wedge \neg Q:

PPQQ(P∧Q)(P\wedge Q)¬(P∧Q)\neg (P\wedge Q)(¬P∨¬Q)(\neg P\vee \neg Q)(¬P∧¬Q)(\neg P\wedge \neg Q)
T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}F\mathsf{F}
T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}

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

  1. In every row, P∧QP\wedge Q and ¬(P∧Q)\neg (P\wedge Q) have different truth values.
  2. In every row, ¬(P∧Q)\neg (P\wedge Q) and ¬P∨¬Q\neg P\vee \neg Q have the same truth value.
  3. The formulas P∧QP\wedge Q and ¬P∧¬Q\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 ¬P∨¬Q\neg P\vee \neg Q and ¬P∧¬Q\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 XX and YY are tautologically equivalent if every truth value assignment gives the same truth value to XX and YY.

Contradcitory

The formulas XX and YY are contradictory if every truth value assignment gives the different truth values to XX and YY.

Mutually Exclusive

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

Satisfiable

The formulas XX and YY are satisfiable if there is a truth value assignment in which both XX and YY are true.

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

classifying two formulas

There are two important observations about classifying two formulas:

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

  2. If XX and YY are tautologically equivalent, then they may or may not be satisfiable. For instance, if XX and YY 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.

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

  3. For all formulas XX and YY, if XX is a tautology and YY is contingent, then X∧YX\wedge Y is a tautology.

  4. For all formulas XX and YY, if XX is a tautology and YY is contingent, then X∨YX\vee Y is a tautology.

  5. For all formulas XX and YY, if XX is a contradiction and YY is contingent, then X→YX\rightarrow Y is a tautology.

  6. For all formulas XX and YY, if XX is contingent and YY is contingent, then X→YX\rightarrow Y is contingent.

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

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

  1. (P∧Q)→¬(P∨Q)(P\wedge Q)\rightarrow \neg (P\vee Q)
  1. (P→Q)∨(Q→P)(P\rightarrow Q) \vee (Q\rightarrow P)
  1. ¬(P→Q)→P\neg (P\rightarrow Q) \rightarrow P
  1. P→(Q∨R)P\rightarrow (Q\vee R)
  1. (¬(Q∨R)∧Q)→P(\neg (Q\vee R) \wedge Q) \rightarrow P
  1. (P→Q)∧(Q→P)(P\rightarrow Q) \wedge (Q\rightarrow P)
  1. (P∧Q)∨(P∧¬Q)(P\wedge Q) \vee (P\wedge \neg Q)
  1. ¬(P∧¬P)\neg (P\wedge \neg P)
  1. ¬(P∨¬P)\neg (P\vee \neg P)
  1. ¬(P∧Q)∨(¬P∨¬Q)\neg (P\wedge Q) \vee (\neg P\vee \neg Q)
  1. ¬(P∨Q)∨(¬P∧¬Q)\neg(P\vee Q) \vee (\neg P\wedge \neg Q)
  1. (P∨Q)∨(¬P∧¬Q)(P\vee Q) \vee (\neg P\wedge \neg Q)
  1. ¬(P∨(P∧Q))\neg (P\vee (P\wedge Q))
  1. ((P→Q)→P)→P((P\rightarrow Q) \rightarrow P)\rightarrow P
  1. (P∨Q)→(P∧Q)(P\vee Q) \rightarrow (P\wedge Q)

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

  1. P∧QP\wedge Q and ¬P∨¬Q\neg P \vee \neg Q
  1. P∨QP\vee Q and ¬P∨¬Q\neg P \vee \neg Q
  1. P→QP\rightarrow Q and ¬Q→¬P\neg Q \rightarrow \neg P
  1. P∧QP \wedge Q and ¬P\neg P
  1. P∨¬PP\vee\neg P and Q∨¬QQ\vee \neg Q
  1. P∧¬PP\wedge\neg P and Q∧¬QQ\wedge \neg Q
  1. (P∧Q)→R(P\wedge Q)\rightarrow R and ¬P∨¬Q∨R\neg P\vee \neg Q \vee R
  1. ¬P→Q\neg P\rightarrow Q and P→RP\rightarrow R
  1. R→PR \rightarrow P and R→ PR\rightarrow ~P
  1. P→¬PP\rightarrow \neg P and  P~P
  1. P∧QP\wedge Q and P→¬QP\rightarrow \neg Q
  1. P∧(Q∨R)P\wedge (Q\vee R) and (¬P∧¬Q∧¬R)(\neg P\wedge \neg Q \wedge \neg R)
  1. P→QP\rightarrow Q and Q→PQ\rightarrow P
  1. P→QP\rightarrow Q and P∧¬QP\wedge \neg Q
  1. P→RP\rightarrow R and (P∧Q)→R(P \wedge Q)\rightarrow R