Propositional Logic

Propositional Logic Basics

A proposition is a statement that is definitely true or false, like "7 is prime" (true) or " $3 > 5$ " (false). We build compound statements using connectives.

Connective	Symbol	Meaning	True When	DirectX
Negation	$\neg p$	not $p$	$p$ is false	-
Conjunction	$p \land q$	$p$ and $q$	both true	-
Disjunction	$p \lor q$	$p$ or $q$	at least one	-
Biconditional	$p \leftrightarrow q$	$p$ iff $q$	$p$ and $q$ match	-

A tautology is true under every assignment ( $p \lor \neg p$ ). A contradiction is false under every assignment. Two propositions are logically equivalent if they share the exact same truth table.

Connectives as one switch driving five lamps at once

Mastering Implication

The implication $p \to q$ ("if $p$ then $q$ ") is false in only one case: when $p$ is true and $q$ is false.

When $p$ is false, the implication is vacuously true regardless of $q$ . For example, "if the moon is cheese, $2+2=5$ " is a true implication.

Term	Definition / Rule	Pitfall
Implication ( $p \to q$ )	False only if $p$ is true and $q$ is false	Vacuously true when $p$ is false
Contrapositive ( $\neg q \to \neg p$ )	Logically equivalent to $p \to q$	Do not confuse with converse $q \to p$
Converse ( $q \to p$ )	Not equivalent to $p \to q$	Classic logical error to swap them

Propositional Logic Basics

Mastering Implication

Practise this lesson

Discrete Mathematics