05 · Translating English & System Specifications
Why translate?
- Removes ambiguity 2. Easy manipulation 3. Lets you solve puzzles
Two-step method
- Find the connectives joining the propositions (and, or, if, only if, unless, …).
- Rename the atomic propositions (always as positive statements) and write the formula.
Slide example
“You are not allowed to watch adult movies if your age is less than 18 years or you have no age proof.” q = you are allowed to watch adult movies, r = age < 18, s = you have age proof. “X if Y” = Y → X, so:
Translation traps
- “if” vs “only if” — “X if Y” = ; “X only if Y” = .
- “unless” = ∨ → “X unless Y” = ≡ .
- “but / although / yet” = ∧.
- “neither p nor q” = = .
- “not both” = = .
- “at least one” = ∨. “exactly one” (of two) = ⊕.
- Define variables positively (“kernel is functioning”) and use ¬ for negatives — mixing them up is the #1 error.
System specification consistency
Definition
A set of specifications is consistent if there is at least one truth assignment that makes all of them TRUE simultaneously (i.e., their conjunction is satisfiable).
Slide problem
Are these consistent?
- The system is in multiuser state iff it is operating normally.
- If the system is operating normally, the kernel is functioning.
- The kernel is not functioning or the system is in interrupt mode.
- If the system is not in multiuser state, then it is in interrupt mode.
- The system is not in interrupt mode.
p = multiuser, q = operating normally, r = kernel functioning, s = interrupt mode.
| # | Formula |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
Solve (start with the fewest variables):
- (5) ⇒ s = F
- (3) must be T ⇒ r = F
- (2) must be T ⇒ q = F
- (4) must be T ⇒ p = T
- (1) = F ❌
Every value was forced, and spec 1 still fails ⇒ NOT consistent.
Strategy
Always start from the statement with the fewest variables (usually a single literal). Forced values cascade; if you reach a contradiction with no free choices left, the set is inconsistent.
Prev ← 04 Precedence and Truth Tables · Next → 06 Logic Puzzles