Grade 10

Propositions and logical reasoning

A proposition is a statement that is either true or false, never both. Connectives such as $\neg P$ , $P \wedge Q$ , $P \vee Q$ , $P \to Q$ build compound statements, and truth tables let us verify equivalences such as $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ with certainty.

IntuitionStatements that are true or false

A light switch is either on or off — never in between. Mathematics uses the same idea: a proposition is a declarative sentence with exactly one truth value, $1$ (true) or $0$ (false). " $2+2=4$ " is a proposition ( $1$ ); " $x+1=5$ " is not a proposition until $x$ is fixed, because its truth depends on an unknown.

Truth table for

P

Q

, implication

P\to Q

, contrapositive

\neg Q\to\neg P

, and conjunction

P\wedge Q

: slide

n

to highlight each of the four truth assignments.

SchoolConnectives and truth tables

Definition: Logical connectives

Given propositions $P$ , $Q$ : negation $\neg P$ is true exactly when $P$ is false; conjunction $P \wedge Q$ (" $P$ and $Q$ ") is true exactly when both are true; disjunction $P \vee Q$ (" $P$ or $Q$ ") is true when at least one is true; the conditional $P \to Q$ ("if $P$ then $Q$ ") is false only when $P$ is true and $Q$ is false; the biconditional $P \leftrightarrow Q$ is true exactly when $P$ and $Q$ share the same truth value.

\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)

This is one of De Morgan's laws: negating "both $P$ and $Q$ " is the same as "not $P$ , or not $Q$ ". Its twin, $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ , negates a disjunction into a conjunction of negations.

(P \to Q) \equiv (\neg Q \to \neg P)

Truth table for the five connectives
$P$	$Q$	$\neg P$	$P \wedge Q$	$P \vee Q$	$P \to Q$	$P \leftrightarrow Q$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$1$

UndergraduateEquivalence laws and valid inference rules

Theorem: De Morgan's laws for propositions

For all propositions $P, Q$ : $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ and $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ .

Why is it true?

"Not both" always splits into two exhaustive cases — at least one fails — which is exactly disjunction of negations; this is the logical skeleton behind negating "for all" statements and behind digital circuits that convert AND-gates into OR-gates of inverted inputs (NAND/NOR equivalence).

Proof

We prove $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ by exhaustively checking all four combinations of truth values for $P$ and $Q$ , since a propositional formula is fully determined by its truth table.

Case $P=1, Q=1$ : $P \wedge Q = 1$ , so $\neg(P\wedge Q)=0$ . Also $\neg P=0$ and $\neg Q=0$ , so $(\neg P)\vee(\neg Q)=0$ . Both sides equal $0$ .

Case $P=1, Q=0$ : $P\wedge Q=0$ , so $\neg(P\wedge Q)=1$ . Also $\neg P=0$ , $\neg Q=1$ , so $(\neg P)\vee(\neg Q)=1$ . Both sides equal $1$ .

Case $P=0, Q=1$ : by symmetry with the previous case, $\neg(P\wedge Q)=1$ and $(\neg P)\vee(\neg Q)=1$ . Both sides agree.

Case $P=0, Q=0$ : $P\wedge Q=0$ , so $\neg(P\wedge Q)=1$ . Also $\neg P=1$ , $\neg Q=1$ , so $(\neg P)\vee(\neg Q)=1$ . Both sides agree.

All four rows of the truth table match, so $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ holds as a tautology (an identity true under every assignment). The second law $\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$ follows by an identical four-row check, or algebraically by substituting $\neg P, \neg Q$ for $P, Q$ in the first law and negating both sides using $\neg\neg X \equiv X$ .

Theorem: Contrapositive equivalence

For all propositions $P, Q$ : $(P \to Q) \equiv (\neg Q \to \neg P)$ .

Why is it true?

A conditional statement and its contrapositive always carry the same information — "if raining then wet ground" is exactly as true as "if the ground is not wet then it is not raining". This equivalence is the logical justification for proof by contraposition, one of the two most common indirect proof techniques (the other being proof by contradiction).

Proof

We prove $(P \to Q) \equiv (\neg Q \to \neg P)$ by comparing truth tables for $P\to Q$ and $\neg Q\to\neg P$ across all four assignments.

Case $P=1, Q=1$ : $P\to Q=1$ (a true hypothesis with a true conclusion). Also $\neg Q=0$ , so $\neg Q\to\neg P$ has a false hypothesis, which makes the whole conditional $1$ regardless of $\neg P$ . Both sides are $1$ .

Case $P=1, Q=0$ : $P\to Q=0$ (true hypothesis, false conclusion is the only case that makes a conditional false). Also $\neg Q=1$ and $\neg P=0$ , so $\neg Q\to\neg P$ has a true hypothesis and false conclusion, giving $0$ . Both sides are $0$ .

Case $P=0, Q=1$ : $P\to Q=1$ (false hypothesis makes any conditional true). Also $\neg Q=0$ , so $\neg Q\to\neg P=1$ automatically. Both sides are $1$ .

Case $P=0, Q=0$ : $P\to Q=1$ (false hypothesis). Also $\neg Q=1$ , $\neg P=1$ , so $\neg Q\to\neg P=1$ (true hypothesis, true conclusion). Both sides are $1$ .

All four rows agree, so $P\to Q$ and $\neg Q\to\neg P$ have identical truth tables and are logically equivalent. Note this differs from the converse $Q\to P$ and the inverse $\neg P\to\neg Q$ , which are equivalent to each other but generally NOT equivalent to the original conditional — a common source of invalid arguments.

UndergraduateReal-World Applications and Worked Examples

Digital circuits are physical realizations of propositional logic: an AND-gate computes $P \wedge Q$ , an OR-gate computes $P \vee Q$ , and an inverter computes $\neg P$ . Engineers use De Morgan's laws to redesign circuits using only NAND gates (cheaper to fabricate), and use Modus Ponens ( $P,\ P \to Q \vdash Q$ ) / Modus Tollens ( $\neg Q,\ P \to Q \vdash \neg P$ ) style reasoning to verify that a circuit's output matches its specification for every input combination. The same connectives underlie SQL `WHERE` clauses, spreadsheet formulas, and search-engine query syntax.

Example: Simplifying a circuit specification

An alarm should trigger unless (the door is closed AND the window is closed). Write the trigger condition without a leading negation over a conjunction, i.e. simplify $\neg(P \wedge Q)$ , and describe the equivalent gate layout.

Solution

Let $P$ = "door is closed" and $Q$ = "window is closed". The trigger condition is $\neg(P \wedge Q)$ .

By De Morgan's law, $\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)$ .

So the alarm triggers exactly when the door is NOT closed, OR the window is NOT closed — in circuit terms, feed the door and window sensors through inverters, then combine with an OR-gate; equivalently, a single NAND-gate applied directly to (door-closed, window-closed) computes the same output without separate inverters, which is why NAND is called a "universal gate".

Example: Modus Tollens in debugging

A programmer knows "if the cache is stale, then the page shows old data" ( $P \to Q$ ). She reloads and observes the page shows current data ( $\neg Q$ ). What can she conclude, and which inference rule justifies it?

Solution

Let $P$ = "cache is stale", $Q$ = "page shows old data". We are given $P \to Q$ and the observation $\neg Q$ (page shows current data).

Modus Tollens states $\neg Q,\ P \to Q \vdash \neg P$ : from $\neg Q$ and $P \to Q$ , we may validly infer $\neg P$ .

So she can conclude the cache is NOT stale. Note the trap she must avoid: seeing $Q$ true would NOT let her conclude $P$ (that would be the invalid "affirming the consequent" fallacy) — old-looking data could have many other causes.

If $P$ is true and $Q$ is false, what is the truth value of $P \to Q$ ?

Which statement is logically equivalent to $\neg(P \vee Q)$ ?

Given $P \to Q$ is true and $P$ is true, Modus Ponens ( $P,\ P \to Q \vdash Q$ ) lets us conclude:

A NAND gate directly implements which single connective applied to a conjunction?

References

Kenneth H. Rosen (2018). Discrete Mathematics and Its Applications
George Boole (1854). An Investigation of the Laws of Thought

$P$	$Q$	$\neg P$	$P \wedge Q$	$P \vee Q$	$P \to Q$	$P \leftrightarrow Q$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$1$

$P$	$Q$	$\neg P$	$P \wedge Q$	$P \vee Q$	$P \to Q$	$P \leftrightarrow Q$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$1$

$P$	$Q$	$\neg P$	$P \wedge Q$	$P \vee Q$	$P \to Q$	$P \leftrightarrow Q$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$1$