Python Boolean Algebra in Practice: Practice Problems & Exercises
Practice: Boolean Algebra in Practice
← Back to lessonEasy
Build a complete truth table that shows the result of AND, OR, and NOT for every combination of two boolean inputs A and B. Print it with aligned columns.
print(f"{'A':5s} | {'B':5s} | {'A AND B':7s} | {'A OR B':6s} | {'NOT A':5s} | {'NOT B':5s}")
for a in [False, True]:
for b in [False, True]:
print(f"{str(a):5s} | {str(b):5s} | {str(a and b):7s} | {str(a or b):6s} | {str(not a):5s} | {str(not b):5s}")Solution
A | B | A AND B | A OR B | NOT A | NOT B
False | False | False | False | True | True
False | True | False | True | True | False
True | False | False | True | False | True
True | True | True | True | False | False
Reading the truth table:
AND — only True when BOTH inputs are True (all other rows are False)
OR — only False when BOTH inputs are False (all other rows are True)
NOT — simply flips the value
Key pattern to internalize: AND is the "strict" gate (both must agree), OR is the "lenient" gate (only one needs to be true). This mental model is the foundation for every conditional you will ever write. In real code, if user.is_admin and request.is_authenticated requires both conditions — that is AND logic. if cache_hit or db_available needs only one — that is OR logic.
Expected Output
A | B | A AND B | A OR B | NOT A | NOT B
False | False | False | False | True | True
False | True | False | True | True | False
True | False | False | True | False | True
True | True | True | True | False | FalseHints
Hint 1: There are exactly 4 rows for two boolean variables — iterate over all combinations of True and False.
Hint 2: Use Python's built-in `and`, `or`, and `not` operators. Format each column with consistent widths using f-string padding.
Prove De Morgan's laws by evaluating both the original and simplified forms for every combination of A and B. Show that they produce identical results in all cases.
print("Expression 1: not (A and B) == (not A) or (not B)")
for a in [False, True]:
for b in [False, True]:
original = not (a and b)
simplified = (not a) or (not b)
status = "MATCH" if original == simplified else "MISMATCH"
print(f" A={str(a):5s}, B={str(b):5s} -> {str(original):5s} == {str(simplified):5s} {status}")
print(f"\nExpression 2: not (A or B) == (not A) and (not B)")
for a in [False, True]:
for b in [False, True]:
original = not (a or b)
simplified = (not a) and (not b)
status = "MATCH" if original == simplified else "MISMATCH"
print(f" A={str(a):5s}, B={str(b):5s} -> {str(original):5s} == {str(simplified):5s} {status}")Solution
Expression 1: not (A and B) == (not A) or (not B)
A=False, B=False -> True == True MATCH
A=False, B=True -> True == True MATCH
A=True, B=False -> True == True MATCH
A=True, B=True -> False == False MATCH
Expression 2: not (A or B) == (not A) and (not B)
A=False, B=False -> True == True MATCH
A=False, B=True -> False == False MATCH
A=True, B=False -> False == False MATCH
A=True, B=True -> False == False MATCH
De Morgan's Laws in plain English:
Law 1: "not (A and B)" = "(not A) or (not B)"
"It's NOT the case that both are true"
is the same as
"At least one of them is false"
Law 2: "not (A or B)" = "(not A) and (not B)"
"It's NOT the case that either is true"
is the same as
"Both of them are false"
Practical refactoring example:
# Before — hard to read with negated AND
if not (user.is_active and user.has_permission):
deny_access()
# After — De Morgan's applied, much clearer
if not user.is_active or not user.has_permission:
deny_access()
De Morgan's laws are the single most useful tool for simplifying conditions in real code. Whenever you see not applied to a compound expression, apply the law to push the negation inward and flip the operator.
Expected Output
Expression 1: not (A and B) == (not A) or (not B)
A=False, B=False -> True == True MATCH
A=False, B=True -> True == True MATCH
A=True, B=False -> True == True MATCH
A=True, B=True -> False == False MATCH
Expression 2: not (A or B) == (not A) and (not B)
A=False, B=False -> True == True MATCH
A=False, B=True -> False == False MATCH
A=True, B=False -> False == False MATCH
A=True, B=True -> False == False MATCHHints
Hint 1: De Morgan's two laws: not (A and B) = (not A) or (not B), and not (A or B) = (not A) and (not B). The key: flip the operator AND<->OR and negate each operand.
Hint 2: Test all 4 input combinations to prove the equivalence exhaustively. If every row matches, the two expressions are logically identical.
Predict the output of each expression before running. Pay careful attention to operator precedence — not binds tightest, then and, then or.
expr1 = True or False and False
print(f"expr1: {expr1}")
expr2 = not True or True
print(f"expr2: {expr2}")
expr3 = not (True or True)
print(f"expr3: {expr3}")
expr4 = (False or True) and (True or False)
print(f"expr4: {expr4}")
expr5 = not False and not False
print(f"expr5: {expr5}")
expr6 = not (not False and not False)
print(f"expr6: {expr6}")Solution
expr1: True
expr2: True
expr3: False
expr4: True
expr5: True
expr6: False
Step-by-step breakdown:
expr1: True or False and False
→ True or (False and False) # and binds tighter than or
→ True or False
→ True
expr2: not True or True
→ (not True) or True # not binds tightest
→ False or True
→ True
expr3: not (True or True)
→ not (True) # parentheses evaluated first
→ False
expr4: (False or True) and (True or False)
→ True and True # both parenthesized groups
→ True
expr5: not False and not False
→ (not False) and (not False) # both nots bind first
→ True and True
→ True
expr6: not (not False and not False)
→ not (True and True) # inner expression first
→ not True
→ False
The critical precedence rule: not > and > or. This is the single biggest source of boolean bugs. When in doubt, add explicit parentheses. The expression not a or b means (not a) or b, not not (a or b). Getting this wrong causes subtle logic errors that pass tests on some inputs but fail on others.
Expected Output
expr1: True
expr2: True
expr3: False
expr4: True
expr5: True
expr6: FalseHints
Hint 1: Python operator precedence for booleans: `not` binds tightest, then `and`, then `or`. So `True or False and False` is `True or (False and False)` = True.
Hint 2: Trace each expression step by step, applying precedence. Parentheses override precedence. `not True or True` is `(not True) or True` = `False or True` = True.
Medium
The function check_original contains a deeply nested boolean expression. Simplify it step by step using De Morgan's laws and boolean algebra identities. Write the simplified version in check_simplified and prove equivalence across all 8 input combinations.
print("Testing all 8 combinations of (a, b, c):")
all_match = True
for a in [False, True]:
for b in [False, True]:
for c in [False, True]:
o = check_original(a, b, c)
s = check_simplified(a, b, c)
match = "MATCH" if o == s else "MISMATCH"
if o != s:
all_match = False
af, bf, cf = str(a)[0], str(b)[0], str(c)[0]
print(f"({af}, {bf}, {cf}): original={str(o):5s}, simplified={str(s):5s} {match}")
print("All 8 combinations match!" if all_match else "MISMATCH FOUND — check your simplification")
Solution
def check_simplified(a, b, c):
return a and (b or not c)
Step-by-step simplification:
Original:
not (not a or (not b and c)) and (a or not c)
Step 1 — Apply De Morgan's to the outer not:
not (not a or (not b and c))
= not (not a) and not (not b and c) # De Morgan: not(X or Y) = not X and not Y
= a and not (not b and c) # Double negation: not(not a) = a
Step 2 — Apply De Morgan's to the remaining not:
not (not b and c)
= not (not b) or not c # De Morgan: not(X and Y) = not X or not Y
= b or not c # Double negation
Step 3 — Substitute back:
a and (b or not c) and (a or not c)
Step 4 — Simplify redundancy:
When a=True: a and (b or not c) and (True or not c) = a and (b or not c)
When a=False: False and (...) = False
Since the expression is already False when a=False, and (a or not c)
adds no information when a=True, it is redundant.
Final simplified form:
a and (b or not c)
Verification table:
a b c | a and (b or not c) | original
F F F | F and (F or T) = F | F
F F T | F and (F or F) = F | F
F T F | F and (T or T) = F | F
F T T | F and (T or F) = F | F
T F F | T and (F or T) = T | T
T F T | T and (F or F) = F | F
T T F | T and (T or T) = T | T
T T T | T and (T or F) = T | T
This is a common refactoring pattern. Complex negated conditions in production code should always be simplified before code review. Fewer operators mean fewer chances for logic bugs and easier reasoning during debugging.
def check_original(a, b, c):
"""The original complex condition — DO NOT MODIFY."""
return not (not a or (not b and c)) and (a or not c)
def check_simplified(a, b, c):
"""Write the simplified equivalent.
Apply De Morgan's laws and boolean algebra to reduce
the expression to its simplest form.
"""
passExpected Output
Testing all 8 combinations of (a, b, c):
(F, F, F): original=False, simplified=False MATCH
(F, F, T): original=False, simplified=False MATCH
(F, T, F): original=False, simplified=False MATCH
(F, T, T): original=False, simplified=False MATCH
(T, F, F): original=True, simplified=True MATCH
(T, F, T): original=False, simplified=False MATCH
(T, T, F): original=True, simplified=True MATCH
(T, T, T): original=True, simplified=True MATCH
All 8 combinations match!Hints
Hint 1: Start by applying De Morgan's to the inner negation: not (not a or (not b and c)) becomes (a and not (not b and c)) which becomes (a and (b or not c)).
Hint 2: After simplification: (a and (b or not c)) and (a or not c). Since the first term already requires a=True, the (a or not c) is redundant when a=True. Simplify to: a and (b or not c).
Implement bool_xor(a, b) that returns True when exactly one of the inputs is truthy. You must not use the ^ operator or any bitwise operations. Only use and, or, not, ==, !=.
tests = [
(False, False, False), (False, True, True),
(True, False, True), (True, True, False),
(0, 0, False), (0, 1, True),
(1, 0, True), (1, 1, False),
]
for a, b, expected in tests:
result = bool_xor(a, b)
status = "PASS" if result == expected else "FAIL"
print(f"bool_xor({a!r:5s}, {b!r:5s}) = {str(result):5s} (expected {str(expected):5s}) {status}")
Solution
There are multiple correct approaches:
# Approach 1: Classical boolean definition
def bool_xor(a, b):
return (a or b) and not (a and b)
# Approach 2: Symmetric difference
def bool_xor(a, b):
return (a and not b) or (not a and b)
# Approach 3: Inequality (simplest)
def bool_xor(a, b):
return bool(a) != bool(b)
Why each works:
Approach 1: (a or b) and not (a and b)
"At least one is true" AND "not both are true"
This is literally the definition of exclusive-or.
T,T -> (T) and not (T) -> T and F -> F
T,F -> (T) and not (F) -> T and T -> T
F,T -> (T) and not (F) -> T and T -> T
F,F -> (F) and not (F) -> F and T -> F
Approach 2: (a and not b) or (not a and b)
"a is true and b is false" OR "a is false and b is true"
Exactly one is true — the two mutually exclusive cases.
Approach 3: bool(a) != bool(b)
Convert to booleans, then check if they differ.
The bool() call handles truthy/falsy values like 0 and 1.
Why bool() is needed in approach 3: Without it, 1 != 1 works fine, but "hello" != "world" would return True (they are different strings, both truthy). Casting to bool first ensures we compare truthiness, not value.
Real-world note: XOR appears in toggle logic (click to toggle on/off), parity checks, simple checksums, and the classic "one or the other but not both" business rules.
def bool_xor(a, b):
"""Return True if exactly one of a, b is truthy.
Do NOT use the ^ operator or any bitwise operations.
Use only: and, or, not, ==, !=
"""
passExpected Output
bool_xor(False, False) = False (expected False) PASS
bool_xor(False, True) = True (expected True) PASS
bool_xor(True, False) = True (expected True) PASS
bool_xor(True, True) = False (expected False) PASS
bool_xor(0, 0) = False (expected False) PASS
bool_xor(0, 1) = True (expected True) PASS
bool_xor(1, 0) = True (expected True) PASS
bool_xor(1, 1) = False (expected False) PASSHints
Hint 1: XOR is true when the inputs differ. The simplest definition: (a or b) and not (a and b) — "at least one is true, but not both."
Hint 2: Alternatively, XOR is equivalent to (a and not b) or (not a and b) — "exactly one of them." Or even simpler: bool(a) != bool(b).
Build a function that evaluates boolean expression strings. The expressions use T/F for true/false, AND/OR/NOT for operators, and parentheses for grouping. Standard precedence: NOT > AND > OR.
tests = [
("T AND F", False),
("T OR F", True),
("NOT T", False),
("NOT F", True),
("T AND T OR F", True),
("T AND (T OR F)", True),
("NOT (T AND F)", True),
("NOT T OR T", True),
("NOT (T OR T)", False),
("(T OR F) AND (NOT F)", True),
]
for expr, expected in tests:
result = eval_bool_expr(expr)
status = "PASS" if result == expected else "FAIL"
print(f'"{expr}"{" " * (24 - len(expr))}-> {str(result):5s} {status}')
Solution
Approach 1 — Token replacement (simple and effective):
def eval_bool_expr(expr):
# Replace tokens with Python equivalents (longest first to avoid partial matches)
py_expr = expr
py_expr = py_expr.replace("AND", "and")
py_expr = py_expr.replace("OR", "or")
py_expr = py_expr.replace("NOT", "not")
py_expr = py_expr.replace("T", "True")
py_expr = py_expr.replace("F", "False")
return eval(py_expr)
Wait — there is a bug! If we replace T before AND, the T inside True from a previous replacement could cause issues. And replacing T first would turn NOT into NoTrue. The fix: replace operators first (they contain T and F as substrings), then replace standalone T and F.
Actually, a cleaner fix — use word boundaries:
import re
def eval_bool_expr(expr):
replacements = [
(r'\bAND\b', 'and'),
(r'\bOR\b', 'or'),
(r'\bNOT\b', 'not'),
(r'\bT\b', 'True'),
(r'\bF\b', 'False'),
]
py_expr = expr
for pattern, replacement in replacements:
py_expr = re.sub(pattern, replacement, py_expr)
return eval(py_expr)
Approach 2 — Recursive descent parser (no eval, production-safe):
def eval_bool_expr(expr):
tokens = expr.replace('(', ' ( ').replace(')', ' ) ').split()
pos = [0] # mutable index
def parse_or():
left = parse_and()
while pos[0] < len(tokens) and tokens[pos[0]] == 'OR':
pos[0] += 1
right = parse_and()
left = left or right
return left
def parse_and():
left = parse_not()
while pos[0] < len(tokens) and tokens[pos[0]] == 'AND':
pos[0] += 1
right = parse_not()
left = left and right
return left
def parse_not():
if pos[0] < len(tokens) and tokens[pos[0]] == 'NOT':
pos[0] += 1
return not parse_not()
return parse_atom()
def parse_atom():
token = tokens[pos[0]]
if token == '(':
pos[0] += 1
result = parse_or()
pos[0] += 1 # skip ')'
return result
pos[0] += 1
return token == 'T'
return parse_or()
Why the recursive descent parser matters:
parse_or — handles lowest precedence (OR)
calls parse_and
parse_and — handles middle precedence (AND)
calls parse_not
parse_not — handles highest precedence (NOT)
calls parse_atom
parse_atom — handles T, F, and parenthesized sub-expressions
calls parse_or for sub-expressions (recursion!)
Each function handles one precedence level and delegates to the next-tighter level. This is the exact same technique used by real programming language parsers (Python's own parser works this way). The eval approach is fine for learning, but in production, eval on user input is a critical security vulnerability.
def eval_bool_expr(expr):
"""Evaluate a simple boolean expression given as a string.
Supported tokens:
- Values: 'T' (True), 'F' (False)
- Operators: 'AND', 'OR', 'NOT'
- Parentheses: '(' and ')'
Precedence: NOT > AND > OR (standard boolean precedence).
Parentheses override precedence.
Returns: True or False
Hint: Replace tokens with Python equivalents and use eval()
for a simple approach — or build a recursive parser for the
robust approach.
"""
passExpected Output
"T AND F" -> False PASS
"T OR F" -> True PASS
"NOT T" -> False PASS
"NOT F" -> True PASS
"T AND T OR F" -> True PASS
"T AND (T OR F)" -> True PASS
"NOT (T AND F)" -> True PASS
"NOT T OR T" -> True PASS
"NOT (T OR T)" -> False PASS
"(T OR F) AND (NOT F)" -> True PASSHints
Hint 1: The simplest approach: replace "T" with "True", "F" with "False", "AND" with "and", "OR" with "or", "NOT" with "not", then use Python's eval(). Be careful with replacement order — replace longer tokens first.
Hint 2: For a safer approach without eval, tokenize the string and build a recursive descent parser: parse_or() calls parse_and() which calls parse_not() which calls parse_atom().
Implement an access control function that evaluates multiple boolean conditions in a realistic authorization scenario. The function must return both the decision and a human-readable reason.
users = {
"admin_user": {
"authenticated": True, "suspended": False,
"role": "admin", "subscription": "free", "sub_expired": False, "explicit_grant": False,
},
"premium_user": {
"authenticated": True, "suspended": False,
"role": "user", "subscription": "premium", "sub_expired": False, "explicit_grant": False,
},
"granted_user": {
"authenticated": True, "suspended": False,
"role": "user", "subscription": "free", "sub_expired": False, "explicit_grant": True,
},
"expired_user": {
"authenticated": True, "suspended": False,
"role": "user", "subscription": "premium", "sub_expired": True, "explicit_grant": False,
},
"suspended_user": {
"authenticated": True, "suspended": True,
"role": "admin", "subscription": "premium", "sub_expired": False, "explicit_grant": True,
},
"anon_user": {
"authenticated": False, "suspended": False,
"role": "user", "subscription": "free", "sub_expired": False, "explicit_grant": False,
},
"free_user": {
"authenticated": True, "suspended": False,
"role": "user", "subscription": "free", "sub_expired": False, "explicit_grant": False,
},
}
for name, user in users.items():
allowed, reason = check_access(user)
status = "ALLOWED" if allowed else "DENIED "
print(f"{name:18s}: {status} - {reason}")
Solution
def check_access(user):
# Guard clause 1: Must be authenticated
if not user['authenticated']:
return (False, "User not authenticated")
# Guard clause 2: Must not be suspended
if user['suspended']:
return (False, "Account is suspended")
# Access path A: Admin role
if user['role'] == 'admin':
return (True, "Access via admin role")
# Access path B: Premium subscription (not expired)
if user['subscription'] == 'premium':
if user['sub_expired']:
return (False, "Premium subscription expired")
return (True, "Access via premium subscription")
# Access path C: Explicit grant
if user['explicit_grant']:
return (True, "Access via explicit grant")
# No access path matched
return (False, "No access path: not admin, not premium, no explicit grant")
The boolean logic flattened into a single expression would be:
allowed = (
user['authenticated']
and not user['suspended']
and (
user['role'] == 'admin'
or (user['subscription'] == 'premium' and not user['sub_expired'])
or user['explicit_grant']
)
)
But the guard-clause version is far superior because:
1. Each denial has a specific reason — no "access denied" mystery
2. Early returns make the logic tree obvious
3. New access paths can be added without touching existing code
4. The suspended check catches everything — even admins cannot bypass it
Critical design pattern: Notice that suspended_user has role='admin' and subscription='premium' and explicit_grant=True — but suspension overrides everything. This is the "deny takes precedence" pattern used in every real authorization system (AWS IAM, RBAC, ABAC). Always check deny conditions first.
def check_access(user):
"""Determine if a user can access a premium resource.
Access rules (ALL must be satisfied):
1. User must be authenticated (user['authenticated'] is True)
2. Account must not be suspended (user['suspended'] is False)
3. User must meet ONE of these:
a. Has 'admin' role
b. Has 'premium' subscription AND subscription is not expired
c. Has been explicitly granted access (user['explicit_grant'] is True)
Return a tuple: (allowed: bool, reason: str)
- If denied, reason explains which rule failed (check in order above)
- If allowed, reason explains which path granted access
"""
passExpected Output
admin_user : ALLOWED - Access via admin role
premium_user : ALLOWED - Access via premium subscription
granted_user : ALLOWED - Access via explicit grant
expired_user : DENIED - Premium subscription expired
suspended_user : DENIED - Account is suspended
anon_user : DENIED - User not authenticated
free_user : DENIED - No access path: not admin, not premium, no explicit grantHints
Hint 1: Check the "must-fail" conditions first (not authenticated, suspended) — these are guard clauses. Then check each access path in order (admin, premium+not expired, explicit grant).
Hint 2: For the reason string, be specific about WHY access was denied. "Premium subscription expired" is more useful than "access denied". This mirrors real authorization system logging.
Hard
Build a function that generates a complete truth table for any boolean expression with any number of variables. The expression uses Python-style and, or, not syntax.
import itertools
# --- paste your generate_truth_table function here ---
print("Expression: a and b")
generate_truth_table("a and b", ['a', 'b'])
print("\nExpression: a and (b or not c)")
generate_truth_table("a and (b or not c)", ['a', 'b', 'c'])
print("\nExpression: (a or b) and (not a or not b)")
generate_truth_table("(a or b) and (not a or not b)", ['a', 'b'])Solution
import itertools
def generate_truth_table(expr_str, variables):
rows = []
header = " | ".join(f"{v:5s}" for v in variables) + " | result"
print(header)
for values in itertools.product([False, True], repeat=len(variables)):
val_dict = dict(zip(variables, values))
# Evaluate the expression with variable values substituted
result = eval(expr_str, {"__builtins__": {}}, val_dict)
rows.append((val_dict, result))
row_str = " | ".join(f"{str(v):5s}" for v in values)
print(f"{row_str} | {result}")
return rows
How it works:
1. itertools.product([False, True], repeat=N) generates all 2^N combinations:
For N=2: (F,F), (F,T), (T,F), (T,T)
For N=3: (F,F,F), (F,F,T), ..., (T,T,T) — 8 rows
2. dict(zip(variables, values)) creates the variable binding:
{'a': False, 'b': True, 'c': False}
3. eval() with restricted builtins evaluates the expression safely:
eval("a and (b or not c)", {"__builtins__": {}}, {'a': True, 'b': False, 'c': True})
→ True and (False or not True) → True and False → False
Why {"__builtins__": {}} matters: Passing an empty __builtins__ dict prevents the expression from accessing dangerous functions like __import__, open, or exec. This is not truly sandboxed (determined attackers can still escape), but it prevents accidental misuse and is the standard minimal safety measure when using eval.
Production-safe alternative without eval:
import ast
import operator
def safe_eval_bool(expr_str, variables, values):
"""Evaluate using AST parsing — no eval needed."""
val_dict = dict(zip(variables, values))
tree = ast.parse(expr_str, mode='eval')
def visit(node):
if isinstance(node, ast.Expression):
return visit(node.body)
elif isinstance(node, ast.BoolOp):
if isinstance(node.op, ast.And):
return all(visit(v) for v in node.values)
elif isinstance(node.op, ast.Or):
return any(visit(v) for v in node.values)
elif isinstance(node, ast.UnaryOp) and isinstance(node.op, ast.Not):
return not visit(node.operand)
elif isinstance(node, ast.Name):
return val_dict[node.id]
raise ValueError(f"Unsupported node: {ast.dump(node)}")
return visit(tree)
Scaling note: A truth table for N variables has 2^N rows. At N=10, that is 1,024 rows. At N=20, over 1 million. At N=30, over 1 billion. This exponential growth is why the boolean satisfiability problem (SAT) is NP-complete — there is no known shortcut to avoid checking exponentially many combinations in the worst case. Every constraint solver, compiler optimizer, and circuit verifier deals with this fundamental limit.
def generate_truth_table(expr_str, variables):
"""Generate a truth table for an arbitrary boolean expression.
Args:
expr_str: A boolean expression string using variable names,
'and', 'or', 'not', and parentheses.
Example: "a and (b or not c)"
variables: List of variable names in order.
Example: ['a', 'b', 'c']
Returns:
A list of tuples: [(val_dict, result), ...]
where val_dict maps variable names to True/False,
and result is the boolean output.
Also prints the formatted truth table.
"""
passExpected Output
Expression: a and b
a | b | result
False | False | False
False | True | False
True | False | False
True | True | True
Expression: a and (b or not c)
a | b | c | result
False | False | False | False
False | False | True | False
False | True | False | False
False | True | True | False
True | False | False | True
True | False | True | False
True | True | False | True
True | True | True | True
Expression: (a or b) and (not a or not b)
a | b | result
False | False | False
False | True | True
True | False | True
True | True | FalseHints
Hint 1: Use itertools.product([False, True], repeat=len(variables)) to generate all input combinations. For each combination, create a dict mapping variable names to values and evaluate the expression.
Hint 2: For evaluation, you can substitute values into the expression string and use eval() with a restricted namespace. Or build a proper expression tree. The key insight: 2^N rows for N variables.
Implement a boolean expression simplifier that takes an expression tree and applies algebraic identities to reduce it to a simpler form. The expression is represented as nested tuples.
# --- paste your simplify and expr_to_str functions here ---
tests = [
# (input_expression, description)
(('NOT', ('NOT', ('VAR', 'a'))), "NOT (NOT a)"),
(('AND', ('VAR', 'a'), ('CONST', True)), "a AND True"),
(('OR', ('VAR', 'a'), ('CONST', False)), "a OR False"),
(('AND', ('VAR', 'a'), ('CONST', False)), "a AND False"),
(('OR', ('VAR', 'a'), ('CONST', True)), "a OR True"),
(('AND', ('VAR', 'a'), ('VAR', 'a')), "a AND a"),
(('OR', ('VAR', 'a'), ('VAR', 'a')), "a OR a"),
(('AND', ('VAR', 'a'), ('NOT', ('VAR', 'a'))), "a AND NOT a"),
(('OR', ('VAR', 'a'), ('NOT', ('VAR', 'a'))), "a OR NOT a"),
(('NOT', ('AND', ('VAR', 'a'), ('VAR', 'b'))), "NOT (a AND b)"),
(('NOT', ('OR', ('VAR', 'a'), ('VAR', 'b'))), "NOT (a OR b)"),
# Nested: NOT(NOT a AND NOT b) should simplify to a OR b via De Morgan's
(('NOT', ('AND', ('NOT', ('VAR', 'a')), ('NOT', ('VAR', 'b')))),
"NOT (NOT a AND NOT b)"),
# Complex: (a AND True) OR (b AND False)
(('OR', ('AND', ('VAR', 'a'), ('CONST', True)),
('AND', ('VAR', 'b'), ('CONST', False))),
"a AND True OR b AND False"),
]
for expr, desc in tests:
result = simplify(expr)
result_str = expr_to_str(result)
print(f"{desc:40s} -> {result_str}")Solution
def simplify(expr):
# Base cases
if expr[0] in ('VAR', 'CONST'):
return expr
# Recursively simplify children first
if expr[0] == 'NOT':
inner = simplify(expr[1])
# Double negation: NOT (NOT x) -> x
if inner[0] == 'NOT':
return simplify(inner[1])
# NOT on constants
if inner[0] == 'CONST':
return ('CONST', not inner[1])
# De Morgan's: NOT (a AND b) -> (NOT a) OR (NOT b)
if inner[0] == 'AND':
return simplify(('OR', ('NOT', inner[1]), ('NOT', inner[2])))
# De Morgan's: NOT (a OR b) -> (NOT a) AND (NOT b)
if inner[0] == 'OR':
return simplify(('AND', ('NOT', inner[1]), ('NOT', inner[2])))
return ('NOT', inner)
if expr[0] == 'AND':
left = simplify(expr[1])
right = simplify(expr[2])
# Identity: x AND True -> x
if right == ('CONST', True):
return left
if left == ('CONST', True):
return right
# Annihilation: x AND False -> False
if right == ('CONST', False) or left == ('CONST', False):
return ('CONST', False)
# Idempotence: x AND x -> x
if left == right:
return left
# Complement: x AND (NOT x) -> False
if right == ('NOT', left) or left == ('NOT', right):
return ('CONST', False)
return ('AND', left, right)
if expr[0] == 'OR':
left = simplify(expr[1])
right = simplify(expr[2])
# Identity: x OR False -> x
if right == ('CONST', False):
return left
if left == ('CONST', False):
return right
# Annihilation: x OR True -> True
if right == ('CONST', True) or left == ('CONST', True):
return ('CONST', True)
# Idempotence: x OR x -> x
if left == right:
return left
# Complement: x OR (NOT x) -> True
if right == ('NOT', left) or left == ('NOT', right):
return ('CONST', True)
return ('OR', left, right)
return expr
Trace through the complex case:
Input: (a AND True) OR (b AND False)
Step 1: Simplify left child: (a AND True)
→ left = a, right = CONST(True)
→ Identity rule: a AND True -> a
Step 2: Simplify right child: (b AND False)
→ left = b, right = CONST(False)
→ Annihilation rule: b AND False -> False
Step 3: Simplify the OR: a OR False
→ Identity rule: a OR False -> a
Result: a
Trace through the nested De Morgan's case:
Input: NOT (NOT a AND NOT b)
Step 1: Simplify inner: (NOT a AND NOT b)
→ No simplification possible (different variables)
Step 2: Apply De Morgan's to NOT (X AND Y):
→ (NOT (NOT a)) OR (NOT (NOT b))
Step 3: Double negation on each:
→ a OR b
Result: a OR b
Why this matters: This is a simplified version of what happens inside compiler optimizers, circuit design tools, and static analyzers. Real-world simplifiers also handle absorption (a AND (a OR b) = a), consensus, and Karnaugh map minimization. The recursive "simplify children first, then apply local rules" pattern is the core of every term-rewriting system.
def simplify(expr):
"""Simplify a boolean expression using algebraic identities.
Input: a nested tuple representing a boolean expression:
('AND', left, right) — conjunction
('OR', left, right) — disjunction
('NOT', operand) — negation
('VAR', 'name') — variable
('CONST', True/False) — constant
Apply these simplification rules:
1. Double negation: NOT (NOT x) -> x
2. Identity: x AND True -> x, x OR False -> x
3. Annihilation: x AND False -> False, x OR True -> True
4. Idempotence: x AND x -> x, x OR x -> x
5. Complement: x AND (NOT x) -> False, x OR (NOT x) -> True
6. De Morgan's: NOT (x AND y) -> (NOT x) OR (NOT y)
NOT (x OR y) -> (NOT x) AND (NOT y)
Apply rules recursively until no more simplifications are possible.
Return the simplified expression tree.
"""
pass
def expr_to_str(expr):
"""Convert expression tree to readable string."""
if expr[0] == 'CONST':
return str(expr[1])
elif expr[0] == 'VAR':
return expr[1]
elif expr[0] == 'NOT':
inner = expr_to_str(expr[1])
return f"NOT {inner}" if expr[1][0] in ('VAR', 'CONST') else f"NOT ({inner})"
elif expr[0] == 'AND':
left = expr_to_str(expr[1])
right = expr_to_str(expr[2])
return f"{left} AND {right}"
elif expr[0] == 'OR':
left = expr_to_str(expr[1])
right = expr_to_str(expr[2])
return f"{left} OR {right}"
return str(expr)Expected Output
NOT (NOT a) -> a
a AND True -> a
a OR False -> a
a AND False -> False
a OR True -> True
a AND a -> a
a OR a -> a
a AND NOT a -> False
a OR NOT a -> True
NOT (a AND b) -> NOT a OR NOT b
NOT (a OR b) -> NOT a AND NOT b
NOT (NOT a AND NOT b) -> a OR b
a AND True OR b AND False -> a OR False -> aHints
Hint 1: Build a recursive simplify function that first simplifies child nodes, then applies rules to the current node. Keep applying until the expression stops changing (fixed point).
Hint 2: For complement detection (x AND NOT x), check if one child is the NOT of the other. For De Morgan's, when you see NOT applied to AND or OR, distribute the NOT inward and flip the operator.
Build a feature flag system using a tree of boolean conditions. Each feature flag has a condition tree that determines whether the feature is enabled for a given user context. This models real-world systems like LaunchDarkly, Unleash, and AWS AppConfig.
# --- paste your classes here ---
# Define feature flags with complex condition trees
new_checkout = FeatureFlag("new_checkout",
AllOf(
Equals("country", "US"),
AnyOf(
Equals("plan", "premium"),
Equals("beta_tester", True),
),
GreaterThan("app_version", 2.0),
)
)
dark_mode = FeatureFlag("dark_mode",
AnyOf(
AllOf(
Equals("plan", "premium"),
Not(Equals("platform", "legacy")),
),
Equals("platform", "mobile"),
Equals("internal_tester", True),
)
)
maintenance_banner = FeatureFlag("maintenance_banner",
AllOf(
Equals("maintenance_mode", True),
Not(Equals("suspended", True)),
),
default=False,
)
# Test contexts
contexts = {
"US premium user, v2.5": {
"country": "US", "plan": "premium", "app_version": 2.5,
"platform": "web", "beta_tester": False, "internal_tester": False,
"maintenance_mode": False, "suspended": False,
},
"US free user, v2.5": {
"country": "US", "plan": "free", "app_version": 2.5,
"platform": "web", "beta_tester": False, "internal_tester": False,
},
"EU premium user, v2.5": {
"country": "DE", "plan": "premium", "app_version": 2.5,
"platform": "web", "beta_tester": False,
},
"US premium user, v1.9": {
"country": "US", "plan": "premium", "app_version": 1.9,
"platform": "web", "beta_tester": False,
},
"US premium, v2.5, beta": {
"country": "US", "plan": "free", "app_version": 2.5,
"platform": "web", "beta_tester": True,
},
"Mobile user, v2.5": {
"country": "US", "plan": "free", "app_version": 2.5,
"platform": "mobile", "beta_tester": False, "internal_tester": False,
},
"Desktop free user": {
"country": "US", "plan": "free", "app_version": 2.5,
"platform": "desktop", "beta_tester": False, "internal_tester": False,
},
"Internal tester": {
"country": "JP", "plan": "free", "app_version": 1.0,
"platform": "web", "internal_tester": True,
},
"Suspended user": {
"country": "US", "plan": "premium", "app_version": 2.5,
"maintenance_mode": True, "suspended": True,
},
}
flags_tests = [
(new_checkout, ["US premium user, v2.5", "US free user, v2.5",
"EU premium user, v2.5", "US premium user, v1.9",
"US premium, v2.5, beta"]),
(dark_mode, ["US premium user, v2.5", "Mobile user, v2.5",
"Desktop free user", "Internal tester"]),
(maintenance_banner, ["US premium user, v2.5", "Suspended user"]),
]
for flag, test_names in flags_tests:
print(f"\n=== Feature: {flag.name} ===")
for name in test_names:
ctx = contexts[name]
enabled = flag.is_enabled(ctx)
status = "ENABLED" if enabled else "DISABLED"
print(f"{name:25s} : {status}")Solution
class Condition:
def evaluate(self, context):
raise NotImplementedError
class AllOf(Condition):
def __init__(self, *conditions):
self.conditions = conditions
def evaluate(self, context):
return all(c.evaluate(context) for c in self.conditions)
def __repr__(self):
return f"AllOf({', '.join(repr(c) for c in self.conditions)})"
class AnyOf(Condition):
def __init__(self, *conditions):
self.conditions = conditions
def evaluate(self, context):
return any(c.evaluate(context) for c in self.conditions)
def __repr__(self):
return f"AnyOf({', '.join(repr(c) for c in self.conditions)})"
class Not(Condition):
def __init__(self, condition):
self.condition = condition
def evaluate(self, context):
return not self.condition.evaluate(context)
def __repr__(self):
return f"Not({self.condition!r})"
class Equals(Condition):
def __init__(self, key, value):
self.key = key
self.value = value
def evaluate(self, context):
return context.get(self.key) == self.value
def __repr__(self):
return f"Equals({self.key!r}, {self.value!r})"
class GreaterThan(Condition):
def __init__(self, key, value):
self.key = key
self.value = value
def evaluate(self, context):
return context.get(self.key, 0) > self.value
def __repr__(self):
return f"GreaterThan({self.key!r}, {self.value!r})"
class InList(Condition):
def __init__(self, key, values):
self.key = key
self.values = values
def evaluate(self, context):
return context.get(self.key) in self.values
def __repr__(self):
return f"InList({self.key!r}, {self.values!r})"
class FeatureFlag:
def __init__(self, name, condition, default=False):
self.name = name
self.condition = condition
self.default = default
def is_enabled(self, context):
try:
return self.condition.evaluate(context)
except Exception:
return self.default
def __repr__(self):
return f"FeatureFlag({self.name!r}, {self.condition!r})"
How the condition tree maps to boolean algebra:
new_checkout condition tree:
AllOf (AND)
├── Equals("country", "US") → country == "US"
├── AnyOf (OR) → plan == "premium" OR beta_tester
│ ├── Equals("plan", "premium")
│ └── Equals("beta_tester", True)
└── GreaterThan("app_version", 2.0) → app_version > 2.0
Boolean equivalent:
country == "US"
AND (plan == "premium" OR beta_tester == True)
AND app_version > 2.0
Trace for "US free user, v2.5":
AllOf evaluates:
1. Equals("country", "US") → "US" == "US" → True
2. AnyOf:
a. Equals("plan", "premium") → "free" == "premium" → False
b. Equals("beta_tester", True) → False == True → False
AnyOf result: False
3. all() short-circuits — already have False → False
Result: DISABLED (the user has the right country and version but no premium/beta access)
Why try/except in is_enabled:
If a context dict is missing a key that a condition checks, context.get()
returns None. For Equals, None == "US" is False — harmless. But for
GreaterThan, None > 2.0 raises TypeError. The try/except catches this
and returns the default value, preventing the entire flag system from
crashing due to incomplete context data.
In production, you would also log the exception for debugging.
Architecture notes:
This is the Composite design pattern — AllOf, AnyOf, and Not are composite nodes that contain other conditions, while Equals, GreaterThan, and InList are leaf nodes. This makes the system:
- Composable — build arbitrarily deep condition trees by nesting
- Extensible — add new condition types (RegexMatch, DateRange, PercentRollout) without changing existing code
- Serializable — the tree structure maps directly to JSON for storage and API transport
- Testable — each condition node can be unit-tested in isolation
Real feature flag systems like LaunchDarkly use exactly this pattern, with additional condition types for percentage rollouts, user segments, and time-based activation.
class Condition:
"""Base class for conditions in a feature flag rule."""
def evaluate(self, context):
raise NotImplementedError
class AllOf(Condition):
"""True if ALL child conditions are true (AND)."""
def __init__(self, *conditions):
self.conditions = conditions
def evaluate(self, context):
pass
def __repr__(self):
return f"AllOf({', '.join(repr(c) for c in self.conditions)})"
class AnyOf(Condition):
"""True if ANY child condition is true (OR)."""
def __init__(self, *conditions):
self.conditions = conditions
def evaluate(self, context):
pass
def __repr__(self):
return f"AnyOf({', '.join(repr(c) for c in self.conditions)})"
class Not(Condition):
"""True if the child condition is false (NOT)."""
def __init__(self, condition):
self.condition = condition
def evaluate(self, context):
pass
def __repr__(self):
return f"Not({self.condition!r})"
class Equals(Condition):
"""True if context[key] == value."""
def __init__(self, key, value):
self.key = key
self.value = value
def evaluate(self, context):
pass
def __repr__(self):
return f"Equals({self.key!r}, {self.value!r})"
class GreaterThan(Condition):
"""True if context[key] > value."""
def __init__(self, key, value):
self.key = key
self.value = value
def evaluate(self, context):
pass
def __repr__(self):
return f"GreaterThan({self.key!r}, {self.value!r})"
class InList(Condition):
"""True if context[key] is in the given list."""
def __init__(self, key, values):
self.key = key
self.values = values
def evaluate(self, context):
pass
def __repr__(self):
return f"InList({self.key!r}, {self.values!r})"
class FeatureFlag:
"""A feature flag with a name, condition tree, and default value."""
def __init__(self, name, condition, default=False):
self.name = name
self.condition = condition
self.default = default
def is_enabled(self, context):
"""Evaluate the flag. Return default if evaluation fails."""
pass
def __repr__(self):
return f"FeatureFlag({self.name!r}, {self.condition!r})"Expected Output
=== Feature: new_checkout ===
US premium user, v2.5 : ENABLED
US free user, v2.5 : DISABLED
EU premium user, v2.5 : DISABLED
US premium user, v1.9 : DISABLED
US premium, v2.5, beta : ENABLED
=== Feature: dark_mode ===
US premium user, v2.5 : ENABLED
Mobile user, v2.5 : ENABLED
Desktop free user : DISABLED
Internal tester : ENABLED
=== Feature: maintenance_banner ===
US premium user, v2.5 : DISABLED
Suspended user : DISABLEDHints
Hint 1: Each Condition subclass needs a one-line evaluate method. AllOf: all(c.evaluate(context) for c in self.conditions). AnyOf: any(). Not: not self.condition.evaluate(context). Equals: context.get(key) == value.
Hint 2: For FeatureFlag.is_enabled, wrap the condition evaluation in a try/except to handle missing context keys gracefully — return self.default if evaluation raises any exception.