Course contentsShow
← Computer Science
Lesson 2021 of 2,87245. Type Systems and SemanticsFree lesson

Semantics of Boolean Expressions

Formal rules for evaluating boolean expressions including short-circuit evaluation behavior.

Semantics of Boolean Expressions

You'll learn: How formal semantic rules define the evaluation of boolean expressions, including the special behavior of short-circuit operators.

What Are Boolean Expressions?

Boolean expressions evaluate to either true or false. Just as we saw operational semantics define how arithmetic expressions reduce to numeric values, we now need formal rules for boolean expressions. These include comparisons (x < 5), logical operators (and, or, not), and importantly, how these operators can skip evaluation of parts of the expression.

Core Semantic Rules

In operational semantics, we write judgments that describe evaluation:

  • Literal values: true ⇓ true and false ⇓ false (base cases)
  • Negation: If e ⇓ true then not e ⇓ false, and vice versa
  • Comparisons: If e₁ ⇓ n₁ and e₂ ⇓ n₂, then e₁ < e₂ ⇓ (n₁ < n₂)

Short-Circuit Evaluation

This is the crucial part! Boolean operators often don't evaluate both operands:

AND (conjunction):

  • If e₁ ⇓ false, then e₁ and e₂ ⇓ false without evaluating e₂
  • If e₁ ⇓ true and e₂ ⇓ v, then e₁ and e₂ ⇓ v

OR (disjunction):

  • If e₁ ⇓ true, then e₁ or e₂ ⇓ true without evaluating e₂
  • If e₁ ⇓ false and e₂ ⇓ v, then e₁ or e₂ ⇓ v

Think of it like a guard checking doors: if the first door reveals the answer, why check the second?

This matters for correctness (avoiding errors in x != 0 and 10/x > 2) and performance.

Key Takeaway: Operational semantics for boolean expressions define precise evaluation order and short-circuit rules, where logical operators may skip evaluating their second operand based on the first operand's value.