Classifying and Testing Propositions with Truth Tables

Hello again. In the previous lesson, you translated statements using negation, conjunction, disjunction, implication, and biconditional. In particular, you saw that an implication $p\to q$ fails only when $p$ is true and $q$ is false.

Now we move from writing compound propositions to systematically evaluating them. Truth tables let you test every possible truth assignment, classify a proposition as a tautology, contradiction, or contingency, and decide whether two different-looking propositions are logically equivalent. These are standard short-answer and table-based questions in discrete mathematics exams.

---

1. Truth tables: testing every possible case

A truth table lists all possible truth values of the atomic propositions in an expression, then evaluates the compound expression one piece at a time.

If an expression has $n$ distinct atomic propositions, its truth table has:

$$2^n$$

rows.

So:

Atomic propositions	Number of rows
$1$	$2$
$2$	$4$
$3$	$8$
$4$	$16$

For two variables $p$ and $q$, always begin in this standard order:

$p$	$q$
T	T
T	F
F	T
F	F

For three variables, use eight rows:

$p$	$q$	$r$
T	T	T
T	T	F
T	F	T
T	F	F
F	T	T
F	T	F
F	F	T
F	F	F

The main technique is simple: create intermediate columns for meaningful inner parts of the expression. Do not try to evaluate a long expression mentally in one step.

For example, to evaluate

$$\neg p\vee q$$

first find $\neg p$, then combine that result with $q$ using “or.”

A compact reminder of the connective rules:

Expression	It is false when...
$\neg p$	$p$ is true
$p\wedge q$	at least one of $p,q$ is false
$p\vee q$	both $p,q$ are false
$p\to q$	$p$ is true and $q$ is false
$p\leftrightarrow q$	$p$ and $q$ have different values

The conditional is the usual source of errors. Remember:

$$p\to q$$

is true in three rows and false in only one:

$$p=\text{T},q=\text{F}$$

---

2. Tautology, contradiction, and contingency

Once the table is complete, look only at the final column.

• A tautology has T in every row. It is true because of its logical form, regardless of the truth values assigned to its variables.
• A contradiction has F in every row. It cannot be true under any assignment.
• A contingency has at least one T and at least one F. Its truth depends on the assignment.

Worked example: a tautology

Classify:

$$(p\wedge q)\to p$$

The expression says: “If both $p$ and $q$ are true, then $p$ is true.” Construct the inner conjunction first.

$p$	$q$	$p\wedge q$	$(p\wedge q)\to p$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

The last column is all T. Therefore,

$$(p\wedge q)\to p$$

is a tautology.

Notice that the last three rows are true because the antecedent $p\wedge q$ is false. An implication with a false antecedent is true.

Worked example: a contradiction

Consider:

$$p\wedge \neg p$$

$p$	$\neg p$	$p\wedge \neg p$
T	F	F
F	T	F

The final column is all F, so:

$$p\wedge \neg p$$

is a contradiction. It claims that a proposition is both true and false simultaneously.

Worked example: a contingency

Now consider:

$$p\to q$$

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
F	F	T

The final column has both T and F. Thus,

$$p\to q$$

is a contingency.

A proposition need not be a tautology merely because it has many T entries. For example, the conditional above is true in three of four rows, but one F is enough to make it a contingency.

---

3. Logical equivalence: same truth value in every case

Two compound propositions are logically equivalent if they have the same truth value in every possible row of their truth tables.

We write:

$$P\equiv Q$$

This notation does not mean that $P$ and $Q$ are identical expressions. It means that they always produce the same final truth value.

One of the most important equivalences is:

$$p\to q\equiv \neg p\vee q$$

Verify it by making columns for both expressions.

$p$	$q$	$p\to q$	$\neg p$	$\neg p\vee q$
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

The two final columns are identical:

$$\text{T, F, T, T}$$

Therefore,

$$p\to q\equiv \neg p\vee q$$

This explains the rule for implication: “If $p$, then $q$” is true whenever $p$ is false or $q$ is true.

Equivalence versus biconditional

These two symbols are related but used differently:

Symbol	Meaning
$P\leftrightarrow Q$	A compound proposition: “$P$ if and only if $Q$”
$P\equiv Q$	A conclusion: $P$ and $Q$ have identical truth-table columns

A useful fact is:

$$P\equiv Q$$

exactly when

$$P\leftrightarrow Q$$

is a tautology. For now, the easiest exam method is simply to compare the final columns directly.

Showing that two propositions are not equivalent

To show that propositions are not logically equivalent, you need only one row where their truth values differ.

Compare:

$$p\to q$$

and its converse:

$$q\to p$$

$p$	$q$	$p\to q$	$q\to p$
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

The final columns differ in the second and third rows. Therefore:

$$p\to q\not\equiv q\to p$$

This confirms a point from the previous lesson: reversing an implication changes its meaning.

---

4. An exam-ready procedure

For a question asking you to classify a compound proposition:

1. Count the atomic propositions and create $2^n$ rows.
2. List truth assignments systematically.
3. Make columns for inner expressions first, especially negations, bracketed expressions, conjunctions, and disjunctions.
4. Evaluate the outermost connective last.
5. Inspect the final column only.
   • All T: tautology
   • All F: contradiction
   • Mixture: contingency
6. Write a direct conclusion, such as:

Since the final column contains both T and F, the proposition is a contingency.

For a question asking whether two propositions are logically equivalent:

1. Use one truth table containing both expressions.
2. Include intermediate columns where necessary.
3. Compare the two final columns.
4. Conclude precisely:

Since the final columns are identical for all truth assignments, the propositions are logically equivalent.

Or:

Since the final columns differ when $p=\text{T}$ and $q=\text{F}$, the propositions are not logically equivalent.

Frequent errors to avoid

• Comparing intermediate columns instead of final columns. Only the completed expressions determine equivalence.
• Forgetting that an implication is false only in the T–F case.
• Classifying by looking at just one row. Every row matters.
• Writing $P=Q$ for logical equivalence. Prefer:

$$P\equiv Q$$

• Omitting columns for grouped subexpressions. For example, in

$$\neg (p\vee q)$$

first calculate $p\vee q$, then negate that whole column.

---

You now have a reliable truth-table method for two core tasks: classifying propositions as tautologies, contradictions, or contingencies, and verifying logical equivalence by matching final columns. The key exam habit is mechanical but powerful: list every assignment, evaluate from inner components outward, and make your conclusion from the final column.

Next, you will apply truth tables to propositional arguments: determining whether an argument is valid and finding a counterexample assignment when it is invalid.