Conditional Expressions Using AND, OR, NOT

Overview

Logical operations combine Boolean (true/false) conditions to form compound expressions. They are fundamental to all conditional branching in algorithms.

KEY TAKEAWAY: Logical operations allow algorithms to express complex conditions precisely. Misusing AND vs OR is a common source of algorithmic errors.

AND

A AND B is true only when both A and B are true.

Truth table:
| A | B | A AND B |
|—|—|---------|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |

Example:

if age >= 18 AND hasLicence = true then
    print("Can drive")
end if

OR

A OR B is true when at least one of A, B is true.

Truth table:
| A | B | A OR B |
|—|—|--------|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |

Example:

if day = "Saturday" OR day = "Sunday" then
    print("Weekend")
end if

NOT

NOT A reverses the truth value of A.

Truth table:
| A | NOT A |
|—|-------|
| T | F |
| F | T |

Example:

if NOT isEmpty(stack) then
    top ← stack.top()
end if

Compound Expressions and Precedence

When combining multiple operations, precedence (order of evaluation) matters:

Precedence (highest to lowest):
1. NOT
2. AND
3. OR

Use parentheses to make precedence explicit and improve readability:

// Without parentheses (relying on precedence):
if A OR B AND C then ...

// Equivalent to:
if A OR (B AND C) then ...

// Better (use parentheses for clarity):
if (A OR B) AND C then ...

COMMON MISTAKE: A OR B AND C is evaluated as A OR (B AND C), NOT (A OR B) AND C. Always use parentheses to avoid ambiguity.

De Morgan’s Laws

De Morgan’s laws are essential for simplifying and rewriting conditions:

$$ ext{NOT}(A ext{ AND } B) \equiv ( ext{NOT } A) ext{ OR } ( ext{NOT } B)$$
$$ ext{NOT}(A ext{ OR } B) \equiv ( ext{NOT } A) ext{ AND } ( ext{NOT } B)$$

Example:

// Original (verbose):
if NOT (x < 0 OR x > 100) then
    print("Valid")
end if

// Equivalent (De Morgan's):
if x >= 0 AND x <= 100 then
    print("Valid")
end if

Practical Usage in Graph Algorithms

// In BFS: continue while queue is not empty
while NOT isEmpty(queue) do
    v ← queue.dequeue()
    for each neighbour w of v do
        if NOT visited[w] then
            visited[w] ← true
            queue.enqueue(w)
        end if
    end for
end while

EXAM TIP: Logical conditions appear in every algorithm. When tracing algorithms manually, evaluate compound conditions carefully — incorrect condition evaluation is a common exam mistake.