Exercises

Level 1 — Understand

1. Classify each expression as a tautology, contradiction, or contingency. Justify with a truth table or by citing an applicable law.

   • P OR NOT P
   • P AND NOT P
   • (P AND Q) OR (NOT P AND Q) OR (P AND NOT Q) OR (NOT P AND NOT Q)
   • P AND (NOT P OR Q)

2. State the Distributive Law (both forms). Verify one form with a two-variable truth table where R = True.

3. What is the difference between CNF and DNF? Give an example of one expression in each form.

Level 2 — Apply

Show that these pairs of expressions are logically equivalent using the algebraic laws (cite each law you use). Do not use truth tables.

1. NOT (P AND Q) AND NOT (P AND NOT Q) simplifies to NOT P.

2. (P OR Q) AND (P OR NOT Q) simplifies to P.

3. Verify your answers by building truth tables.

Level 3 — Design

A permissions system has this rule:

def can_delete(is_owner: bool, is_admin: bool, is_archived: bool, is_locked: bool) -> bool:
    return (is_owner and not is_archived and not is_locked) or (is_admin and not is_locked)

1. A developer wants to simplify this to: (is_owner or is_admin) and not is_archived and not is_locked. Show by truth table that these are NOT equivalent. Identify the specific input combination that differs.

2. Derive the correct simplification. Hint: factor out not is_locked. Show each step using the equivalence laws, citing each law.

3. A precomputed field user.has_delete_rights is added to the database. It stores the value of can_delete at user object creation time. Identify the AT4 tradeoff. Under what conditions does has_delete_rights become stale (FM8)? Propose an invalidation strategy.

4. The precomputed field is added to a database index: WHERE has_delete_rights = TRUE. What performance benefit does this provide? What correctness risk does it introduce? Name both tradeoffs (AT4 and AT9).