Unit 2 — Boolean Logic & Algebra

Slide 1 of 33

A contest problem often asks whether a gate should open, a proposal passes, or a warning fires. Boolean logic combines yes/no facts into one exact decision; careful code tracing predicts a program before running it. Each idea is a short ladder of executable demos with a Notice, then a full stdin solver.
- Build truth tables and combine facts with and, or and not.
- Trace an expression by precedence: not first, then and, then or.
- Check both of De Morgan's laws and use them to simplify a rule without changing its result.
- Predict short-circuit evaluation and turn contest rules into exact YES/NO decisions.
Lesson 1 — Boolean Algebra

A Boolean value is True or False. A truth table tries every combination so no case hides.

choices = [True, False]
print("a     b     a and b  a or b")
for a in choices:
    for b in choices:
        print(a, b, a and b, a or b)

Output

a     b     a and b  a or b
True True True True
True False False True
False True False True
False False False False

and is true only when BOTH are true; or is true when at least one is.

a and b needs both; a or b needs one; not a flips it. not binds before and, and before or; parentheses make grouping explicit.

has_key = True
knows_code = False
door_open = has_key or knows_code
alarm_on = not door_open
print(door_open)
print(alarm_on)
assert door_open == True
assert alarm_on == False

Output

True
False

door_open = has_key or knows_code; not door_open flips it.

Code-tracing warm-up 1 — predict, then run

What does each line print? and before or. Predict on paper first.

print(True or False and False)
print((True or False) and False)
print(not False and False or True)

Output

True
False
True

Precedence decides the answer — True or False and False is True (the and runs first).

De Morgan's Laws

not (a and b) == (not a) or (not b), and not (a or b) == (not a) and (not b). The table asserts both laws agree on every row.

choices = [True, False]
for a in choices:
    for b in choices:
        not_and = not (a and b)
        flipped_to_or = (not a) or (not b)
        not_or = not (a or b)
        flipped_to_and = (not a) and (not b)
        print(a, b, "not-and:", not_and, flipped_to_or, "not-or:", not_or, flipped_to_and)
        assert not_and == flipped_to_or
        assert not_or == flipped_to_and

Output

True True not-and: False False not-or: False False
True False not-and: True True not-or: False False
False True not-and: True True not-or: False False
False False not-and: True True not-or: True True

The asserts hold for ALL four rows — the equivalence is exhaustively verified (the boolean analog of a counterexample check).
Short-Circuit Evaluation

and stops as soon as its result must be false; or stops as soon as it must be true — the right side may never run.

def announce_check():
    print("The right side ran!")
    return True


print("First result:", False and announce_check())
print("Second result:", True or announce_check())
print("Third result:", True and announce_check())

Output

First result: False
Second result: True
The right side ran!
Third result: True

False and ... and True or ... never call the right side, so its message never prints.

Simplifying Boolean Expressions

A gate is closed when not (member or guest) or banned; it is OPEN when that is false: not (not (member or guest) or banned). De Morgan + the double negative simplify it to (member or guest) and not banned.

choices = [True, False]
for member in choices:
    for guest in choices:
        for banned in choices:
            original = not (not (member or guest) or banned)
            simpler = (member or guest) and not banned
            print(member, guest, banned, original, simpler)
            assert original == simpler

Output

True True True False False
True True False True True
True False True False False
True False False True True
False True True False False
False True False True True
False False True False False
False False False False False

The original and simplified forms agree on every one of the eight rows.
Put it together: the gate-access program reads member guest banned (each 0/1) from stdin and prints GRANTED/DENIED using the simplified rule.

Try it

import sys

data = sys.stdin.read()
values = data.split()
member = int(values[0]) == 1
guest = int(values[1]) == 1
banned = int(values[2]) == 1
if (member or guest) and not banned:
    print("GRANTED")
else:
    print("DENIED")

Run the full solver from this unit folder:
```
python assets/l1.py < assets/l1/1.in
```
Read three 0/1 flags from stdin, apply (member or guest) and not banned, print the decision.

Complexity: O(1) (fixed inputs).
Lesson 2 — Code Tracing & Deciding

Combine traced facts into a decision. Build the rule one step at a time on literal data, then read real input.
Code-tracing warm-up 2 — predict, then run

What does this gate checker print for each person? Trace the parentheses, then apply not banned.

people = [[True, False, False], [False, True, True], [False, False, False]]
for person in people:
    member = person[0]
    guest = person[1]
    banned = person[2]
    allowed = (member or guest) and not banned
    print(allowed)

Output

True
False
False

(member or guest) and not banned — the simplified rule from Lesson 1, now over a list of people.

Count how many answered yes over a literal list, with an accumulator.

answers = ["yes", "yes", "no", "yes", "yes"]
yes_count = 0
for answer in answers:
    if answer == "yes":
        yes_count = yes_count + 1
print(yes_count)

Output

One accumulator yes_count counts the yes answers (here 4 of 5).

Now GENERALIZE: a strict majority AND at least one dissenter. Combine the two facts with and.

answers = ["yes", "yes", "no", "yes", "yes"]
n = len(answers)
yes_count = 0
found_no = False
for answer in answers:
    if answer == "yes":
        yes_count = yes_count + 1
    else:
        found_no = True
print(yes_count * 2 > n and found_no)

Output

True

yes_count * 2 > n is a STRICT majority without fractions; and found_no requires a dissenter — True here (4 of 5 yes, one no).

Put it together: the program reads N then the N answers from stdin and prints YES only for a strict majority with at least one dissenter. Answers may be mixed-case (Yes/NO), so .lower() normalizes them.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
yes_count = 0
found_no = False
for position in range(n):
    answer = tokens[position + 1].lower()
    if answer == "yes":
        yes_count = yes_count + 1
    else:
        found_no = True
if yes_count * 2 > n and found_no:
    print("YES")
else:
    print("NO")

Run the full solver from this unit folder:
```
python assets/l2.py < assets/l2/1.in
```
Read N + the answers, count yes (case-insensitively) and detect a no, combine with and.

Complexity: O(N). The strict-majority * 2 avoids fractions; .lower() makes the check case-insensitive.
- A truth table tries every combination of True and False, so no case hides.
- and groups before or, so True or False and False is True; parentheses make grouping clear.
- not (a and b) equals (not a) or (not b), and not (a or b) equals (not a) and (not b).
- False and ... and True or ... never run their right side.
- Predict, then run: tracing code on paper before running it catches wrong decisions early.
You can now turn a contest rule into a precise Boolean decision and trace it by hand.

Unit 2 — Boolean Logic & Algebra

Lesson 1 — Boolean Algebra

Code-tracing warm-up 1 — predict, then run

De Morgan's Laws

Short-Circuit Evaluation

Simplifying Boolean Expressions

Lesson 2 — Code Tracing & Deciding

Code-tracing warm-up 2 — predict, then run