Logical Connectives

Overview

Building Complex Statements

Logical connectives let us combine simple propositions into complex ones. There are five fundamental connectives you need to master: negation (NOT), conjunction (AND), disjunction (OR), conditional (IF-THEN), and biconditional (IF AND ONLY IF).

Definition

Negation (¬)

The negation of proposition p is written ¬p (read "not p"). It has the opposite truth value of p.

If p is true, ¬p is false. If p is false, ¬p is true.

Example: If p = "It is raining," then ¬p = "It is not raining."

Definition

Conjunction (∧)

The conjunction of p and q is written p ∧ q (read "p and q"). It is true only when BOTH p and q are true.

p ∧ q is true when p = T, q = T p ∧ q is false when p = T, q = F p ∧ q is false when p = F, q = T p ∧ q is false when p = F, q = F

Definition

Disjunction (∨)

The disjunction of p and q is written p ∨ q (read "p or q"). It is true when AT LEAST ONE of p or q is true. This is the inclusive-or.

p ∨ q is true when p = T, q = T p ∨ q is true when p = T, q = F p ∨ q is true when p = F, q = T p ∨ q is false when p = F, q = F

Definition

Conditional / Implication (→)

The conditional p → q (read "if p then q") is false ONLY when p is true and q is false. In all other cases it is true.

p → q is true when p = T, q = T p → q is false when p = T, q = F p → q is true when p = F, q = T p → q is true when p = F, q = F

Key insight: a conditional with a false hypothesis is always true (vacuously true). "If pigs can fly, then 2 + 2 = 5" is technically true in logic.

Definition

Biconditional (↔)

The biconditional p ↔ q (read "p if and only if q") is true when both p and q have the SAME truth value.

p ↔ q is true when p = T, q = T p ↔ q is false when p = T, q = F p ↔ q is false when p = F, q = T p ↔ q is true when p = F, q = F

It is equivalent to (p → q) ∧ (q → p).

Example

Translating English to Logic

Let p = "You study" and q = "You pass the exam."

"You study and you pass the exam" → p ∧ q "You study or you pass the exam" → p ∨ q "If you study, then you pass the exam" → p → q "You pass the exam if and only if you study" → p ↔ q "You do not study" → ¬p

Note

Operator Precedence

When multiple connectives appear without parentheses, the standard precedence is: 1. ¬ (highest - evaluated first) 2. ∧ 3. ∨ 4. → 5. ↔ (lowest - evaluated last)

So ¬p ∧ q → r means ((¬p) ∧ q) → r. When in doubt, use parentheses!