04 · Precedence & Truth Tables
Operator precedence
| Operator | Name | Precedence |
|---|---|---|
| ¬ | Negation | 1 (highest) |
| ∧ | Conjunction | 2 |
| ∨ | Disjunction | 3 |
| → | Implication | 4 |
| ↔ | Biconditional | 5 (lowest) |
Mnemonic — " Not All Ostriches Imitate Birds"
NOT → AND → OR → IMPLIES → BICONDITIONAL
is parsed as . With p = T, q = F: , so F.
Associativity edge cases
- → is NOT associative. . Counter-example: p = F, r = F → left = = F, right = T.
- Convention (Rosen and most books): means (right-associative). GATE always uses brackets — don’t assume, read them.
- ↔ is associative: . So is ⊕.
- ¬ binds tightest: means , not .
Building a truth table
Rule: variables → rows. Add one column per sub-expression, innermost first.
Slide example: By precedence this is . Let , .
| p | q | ¬p | ¬q | r = ¬q∧¬p | s = p→r | s↔¬q |
|---|---|---|---|---|---|---|
| T | T | F | F | F | F | T |
| T | F | F | T | F | F | F |
| F | T | T | F | F | T | F |
| F | F | T | T | T | T | T |
GATE speed tip
You rarely need the full table. To show something is not a tautology, find one falsifying row. To show it is satisfiable, find one satisfying row. → 07 Tautology Contradiction Satisfiability
Prev ← 03 Implication Deep Dive · Next → 05 Translation and Consistency