Formal Logic, Truth Tables, and De Morgan’s Laws

Problem Statement

Before we can prove complex theorems, we must understand the fundamental rules of reasoning. Formal Logic replaces English sentences with symbols to eliminate ambiguity.

We deal with statements (propositions) denoted by variables like $P$ and $Q$ , which can only be True (T) or False (F). We combine these using logical operators:

AND ( $\land$ ): $P \land Q$ is true only if both $P$ and $Q$ are true.
OR ( $\lor$ ): $P \lor Q$ is true if at least one of $P$ or $Q$ is true.
NOT ( $\neg$ ): $\neg P$ flips the truth value of $P$ .
IMPLIES ( $\implies$ ): $P \implies Q$ (If $P$ then $Q$ ) is only false when $P$ is true but $Q$ is false.

To evaluate complex logical expressions, we construct Truth Tables, which systematically map out every possible combination of True and False.

Two of the most important rules in formal logic are De Morgan's Laws, which explain how the NOT operator ( $\neg$ ) distributes across AND and OR statements.

Consider the logical statement: "It is not the case that both it is raining ( $R$ ) and I am wearing a coat ( $C$ )." Symbolically, this is: $\neg(R \land C)$ .

(a) Construct a truth table to evaluate the statement $\neg(R \land C)$ for all possible truth values of $R$ and $C$ .

(b) Construct a truth table for the statement $\neg R \lor \neg C$ ("It is not raining, OR I am not wearing a coat").

(c) Compare the final columns of both truth tables. What does this prove about the two statements? State the relevant De Morgan's Law.

Hints

Parts (a) and (b): A truth table with two variables ( $R, C$ ) needs 4 rows representing all combinations: (T, T), (T, F), (F, T), (F, F). Create intermediate columns for the parts inside the brackets (like $R \land C$ ) or the negated terms (like $\neg R$ ) before evaluating the final expression.
Part (c): If the final columns of two truth tables are identical row-for-row, the statements are logically equivalent. This means one can always be substituted for the other in a mathematical proof.

Solutions

Part (a): Truth Table for $\neg(R \land C)$

$R$	$C$	$R \land C$	$\neg(R \land C)$
T	T	T	F
T	F	F	T
F	T	F	T
F	F	F	T

First, evaluate the inner bracket $R \land C$ . It is only True when both $R$ and $C$ are True (Row 1).
Next, apply the NOT operator $\neg$ to the $(R \land C)$ column, flipping all T's to F's, and F's to T's.

Part (b): Truth Table for $\neg R \lor \neg C$

$R$	$C$	$\neg R$	$\neg C$	$\neg R \lor \neg C$
T	T	F	F	F
T	F	F	T	T
F	T	T	F	T
F	F	T	T	T

First, create columns for $\neg R$ (flip $R$ ) and $\neg C$ (flip $C$ ).
Next, apply the OR operator $\lor$ to the $\neg R$ and $\neg C$ columns. The result is True if at least one of the inputs is True (Rows 2, 3, 4).

Part (c): Comparison and De Morgan's Law

Comparing the final columns of both tables:
- $\neg(R \land C)$ yields: F, T, T, T.
- $\neg R \lor \neg C$ yields: F, T, T, T.
Because the outputs are identical for every possible input scenario, the two statements are logically equivalent. $\neg(R \land C) \equiv \neg R \lor \neg C$
This equivalence is the first of De Morgan's Laws. It states that the negation of an AND statement is logically equivalent to the OR statement of their individual negations.
- (In English: "It is not true that both A and B happened" is the exact same as saying "A didn't happen, OR B didn't happen").
(Note: The second of De Morgan's laws flips the operators the other way: $\neg(P \lor Q) \equiv \neg P \land \neg Q$ ).

Takeaways

Logic is Binary: In mathematics, a statement cannot be "kind of true." Truth tables force us to rigorously define the exact conditions under which a complex theorem holds.
The Anatomy of a Proof: Every theorem is an implication ( $P \implies Q$ ). To prove it by contrapositive, we prove $\neg Q \implies \neg P$ . If $Q$ is a complex statement with ANDs/ORs, we must use De Morgan's Laws to correctly formulate $\neg Q$ .
Computer Science Foundation: The logical operators ( $\land, \lor, \neg$ ) are the exact same AND, OR, and NOT logic gates used to build computer processors and write code.

Further Readings

HSC Proofs: https://vumaths.com/booklets/hsc-proofs/
HSC Collections: https://vumaths.com/booklets/hsc-collections/
HSC Inequalities: https://vumaths.com/booklets/hsc-inequalities/

Connect with me

If you want to master the formal logic required for Extension 2 proofs, check out the comprehensive guides on Vu's Maths Hub. I break down truth tables and logical implications in my booklets. Join my YouTube channel for video walkthroughs, follow my Instagram for daily logic puzzles, and subscribe to my Substack to see how this logic applies to computer programming!