Conjunction and Disjunction

Conjunction (And)

The conjunction $P \land Q$ means ”$P$ and $Q$”.

Truth Table

$P$	$Q$	$P \land Q$
T	T	T
T	F	F
F	T	F
F	F	F

$P \land Q$ is true only when both $P$ and $Q$ are true.

Proof Strategy

To prove $P \land Q$:

1. Prove $P$
2. Prove $Q$

Both must be proved separately.

Disjunction (Or)

The disjunction $P \lor Q$ means ”$P$ or $Q$”.

In mathematics, “or” is inclusive: $P \lor Q$ is true if at least one of $P$, $Q$ is true.

Truth Table

$P$	$Q$	$P \lor Q$
T	T	T
T	F	T
F	T	T
F	F	F

Proof Strategies for Disjunction

Method 1: Prove One Disjunct

Prove $P$ (then $P \lor Q$ follows) or prove $Q$.

Method 2: Proof by Cases (Disjunction Elimination)

To prove $R$ from $P \lor Q$:

1. Case 1: Assume $P$, prove $R$
2. Case 2: Assume $Q$, prove $R$
3. Since $P \lor Q$ and $R$ follows in either case, conclude $R$

Method 3: Proof by Contradiction

To prove $P \lor Q$:

1. Assume $\neg(P \lor Q)$
2. By De Morgan, this means $\neg P \land \neg Q$
3. Derive a contradiction

Example: Proof by Cases

Statement: For all integers $n$, $n^2 \geq n$.

This is false. But let us prove: For all integers $n$, $n^2 \geq 0$.

Proof by cases on $n \geq 0$ or $n < 0$:

Case 1: $n \geq 0$.

Then $n^2 \geq 0 \cdot n = 0$.

Case 2: $n < 0$.

Then $n = -k$ for some $k > 0$. So $n^2 = (-k)^2 = k^2 > 0$.

In either case, $n^2 \geq 0$.

De Morgan’s Laws

For Statements

$\neg(P \land Q) \equiv \neg P \lor \neg Q$ $\neg(P \lor Q) \equiv \neg P \land \neg Q$

For Sets

$S \setminus (A \cap B) = (S \setminus A) \cup (S \setminus B)$ $S \setminus (A \cup B) = (S \setminus A) \cap (S \setminus B)$

Verification by Truth Table

$P$	$Q$	$\neg(P \land Q)$	$\neg P \lor \neg Q$
T	T	F	F
T	F	T	T
F	T	T	T
F	F	T	T

Distributivity

Conjunction over Disjunction

$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$

Disjunction over Conjunction

$P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

Associativity and Commutativity

Both $\land$ and $\lor$ are:

• Associative: $P \land (Q \land R) \equiv (P \land Q) \land R$
• Commutative: $P \land Q \equiv Q \land P$

This allows us to write $P_1 \land P_2 \land \cdots \land P_n$ and $P_1 \lor P_2 \lor \cdots \lor P_n$ without parentheses.

Absorption Laws

$P \land (P \lor Q) \equiv P$ $P \lor (P \land Q) \equiv P$

Idempotent Laws

$P \land P \equiv P$ $P \lor P \equiv P$

Identity Laws

$P \land \text{True} \equiv P$ $P \lor \text{False} \equiv P$

Domination Laws

$P \land \text{False} \equiv \text{False}$ $P \lor \text{True} \equiv \text{True}$

Using Logical Equivalences

These equivalences allow us to transform statements into simpler or more convenient forms.

Example

Simplify $\neg(P \land Q) \land P$.

$\neg(P \land Q) \land P \equiv (\neg P \lor \neg Q) \land P$ (De Morgan) $\equiv (\neg P \land P) \lor (\neg Q \land P)$ (Distributivity) $\equiv \text{False} \lor (\neg Q \land P)$ (Contradiction) $\equiv \neg Q \land P$ (Identity)

Common Pitfalls

Confusing And/Or

Trap: “P or Q” in mathematics includes the case where both are true.

This is different from everyday English where “or” often means “exactly one”.

Forgetting a Case

Trap: When using proof by cases, check you have covered all possibilities.

If your cases are $n > 0$ and $n < 0$, you forgot $n = 0$.

Overlapping Cases

Trap: Cases need not be disjoint, but each case must be proved.

Cases may overlap; what matters is each case individually leads to the conclusion.

---

Summary

• $P \land Q$ requires proving both $P$ and $Q$
• $P \lor Q$ can be proved by proving one, or by cases
• De Morgan’s laws: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ and $\neg(P \lor Q) \equiv \neg P \land \neg Q$
• Both connectives are associative, commutative, and distributive over each other