Propositional Logic

Propositions

A proposition is a declarative statement that is either true (T) or false (F), but not both.

Examples

• "2 + 2 = 4" is a proposition (true)
• "The sky is green" is a proposition (false)
• "What time is it?" is NOT a proposition (question)
• "$x + 1 = 2$" is NOT a proposition (depends on $x$)

Logical Connectives

Symbol	Name	Meaning
$\neg$	Negation	NOT
$\land$	Conjunction	AND
$\lor$	Disjunction	OR
$\oplus$	Exclusive OR	XOR
$\rightarrow$	Implication	IF...THEN
$\leftrightarrow$	Biconditional	IF AND ONLY IF

Truth Tables

Negation ($\neg p$)

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

Conjunction ($p \land q$)

$p$	$q$	$p \land q$
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction ($p \lor q$)

$p$	$q$	$p \lor q$
T	T	T
T	F	T
F	T	T
F	F	F

Exclusive OR ($p \oplus q$)

$p$	$q$	$p \oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

Implication ($p \rightarrow q$)

$p$	$q$	$p \rightarrow q$
T	T	T
T	F	F
F	T	T
F	F	T

Note: An implication is false only when the hypothesis is true and the conclusion is false.

Biconditional ($p \leftrightarrow q$)

$p$	$q$	$p \leftrightarrow q$
T	T	T
T	F	F
F	T	F
F	F	T

Operator Precedence

From highest to lowest:

1. $\neg$ (negation)
2. $\land$ (conjunction)
3. $\lor$ (disjunction)
4. $\rightarrow$ (implication)
5. $\leftrightarrow$ (biconditional)

Compound Propositions

Example

Let $p$: "It is raining" and $q$: "I carry an umbrella"

• $p \land q$: "It is raining AND I carry an umbrella"
• $p \rightarrow q$: "IF it is raining, THEN I carry an umbrella"
• $\neg p \lor q$: "It is NOT raining OR I carry an umbrella"

Tautology, Contradiction, Contingency

• Tautology: Always true (e.g., $p \lor \neg p$)
• Contradiction: Always false (e.g., $p \land \neg p$)
• Contingency: Sometimes true, sometimes false

Logical Equivalence

Two propositions are logically equivalent ($\equiv$) if they have the same truth values:

$p \equiv q \text{ means } (p \leftrightarrow q) \text{ is a tautology}$

Key Equivalences

$p \rightarrow q \equiv \neg p \lor q$

$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$

Converse, Inverse, Contrapositive

For the implication $p \rightarrow q$:

Form	Statement	Equivalent to Original?
Original	$p \rightarrow q$	—
Converse	$q \rightarrow p$	No
Inverse	$\neg p \rightarrow \neg q$	No
Contrapositive	$\neg q \rightarrow \neg p$	Yes

$p \rightarrow q \equiv \neg q \rightarrow \neg p$