Gates, Adders and Knights & Knaves

You received an email from GitHub at your university address (your-student-number@firat.edu.tr), titled “… invited you to join the FiratUniversity-IJDP-SoftEng organization”.

1. Open the email and click Join FiratUniversity-IJDP-SoftEng.
2. Sign in with your GitHub account (the one you used for Lab 1) and click Join.

That is all. You are now on the course roster.

1. Click the orange Accept lab lab02 button at the top of this page.
2. If asked, click Sign in with GitHub and authorize Classroom 50.
3. Click Accept assignment and wait for the checklist to finish (about 20 seconds).
4. Click Open repository.

You now have a private repository called discrete-mathematics-lab02-yourusername inside the course organization, with the starter code, the tests and the notebook. Only you and the instructor can see it.

On your repository page: green Code button → Codespaces tab → Create codespace on main. Exactly like Lab 1; the first start takes a minute or two.

$ python check.py:| the gate matches its truth table and returns 0/1  [AND]
  not implemented yet (still raises NotImplementedError)
...
0/34 checks passed

In circuits.py a bit is the integer 1 or 0, like a wire. In puzzles.py truth values are True and False. Keep that in mind; it is the most common source of surprises.

Write NOT, AND, OR, XOR and NAND in circuits.py. Each takes bits and must return 0 or 1, not True or False.

Two ways to think about it: with conditions (return 1 if a and b else 0) or with arithmetic on bits (1 - a is NOT). For NAND, reuse your own gates: NAND is NOT of AND.

counterexample(f, g, n) walks through every row of n bits and returns the first row where f and g disagree, or None. It is the equivalence checker from the notes, in eight lines.

from itertools import product
for row in product([1, 0], repeat=2):
    print(row)          # (1, 1), (1, 0), (0, 1), (0, 0)

Then equivalent(f, g, n) is one line: two formulas are equivalent exactly when there is no counterexample.

$ python circuits.py...
p→q ≡ ¬q→¬p ? True
p→q ≡ q→p   ? counterexample: (1, 0)

Use only your gate functions: the checks reject +, -, // and % in the adders.

1. half_adder(a, b) returns (sum, carry): sum is XOR, carry is AND. One line.
2. full_adder(a, b, cin) returns (sum, carry_out). Either use the two formulas in the docstring, or chain two half adders and one OR (the circuit on the week 3 page).
3. add_binary(x, y) adds two bit strings like a CPU does:
   • pad the shorter string with "0" on the left (str.zfill helps),
   • walk the columns from right to left with reversed(...), starting with carry 0,
   • each column: s, carry = full_adder(int(a), int(b), carry),
   • if a carry is left at the end, it becomes an extra leading "1".

$ python circuits.pyhalf_adder(1, 1) = (0, 1)
11 + 6 = 10001 (binary)

The checks add all 256 pairs of 4-bit numbers with your adder. If one pair fails, the message tells you which.

Rebuild NOT, AND, OR and XOR using only calls to NAND: no other gates, no and/or/not, no operators, no if. The checks read your code to make sure. The identities are in the notes:

For XOR, start with n = NAND(a, b); four NAND calls are enough.

Open puzzles.py. A world says who is a knight: {"A": True, "B": False}. A statement is a function of the world:

"A": lambda w: w["B"]                  # A says: "B is a knight"
"B": lambda w: w["A"] != w["B"]        # B says: "We are of opposite types"

solve(people, statements) tries every world and keeps the consistent ones. The one rule from the lecture: a speaker is a knight if and only if their statement is true, so for every speaker s, w[s] == statements[s](w) must hold.

1. Loop over product([True, False], repeat=len(people)).
2. Turn each tuple into a world with dict(zip(people, values)).
3. Keep the world if the rule holds for all speakers (all(...) is ∀ again).

Translate each puzzle into a statements dict. Then run python puzzles.py and check the answers make sense.

• Puzzle 1 is the one from the notes: both should be knaves.
• Puzzle 2: A says “at least one of us is a knave”. B says nothing, so B has no entry.
• Puzzle 3: A says “all three of us are knaves”, B says “exactly one of us is a knight”. Hint: [w["A"], w["B"], w["C"]].count(True) == 1.

satisfying_row(formulas, n) returns the first row that makes every formula true, or None. login_requirements() returns the four requirements from the week 3 notes as functions of (p, q, r).

Translate carefully: requirement 1 says access is granted only if the user is authenticated. Which way does the arrow point? (Week 2: “$p$ only if $q$” is $p \to q$.)

$ python puzzles.py...
requirements 1–3 consistent: (True, True, False)
requirements 1–4 consistent: None

Submitting is pushing. Every push is graded automatically.

$ git add -A$ git commit -m "Lab 2"$ git push

About two minutes later:

1. On your repository page, look at Releases on the right. The newest submit/… release shows your score and a table of passed and failed checks.
2. Or open our classroom on Classroom 50 → Lab 2 → My submission.

Push as often as you like before Friday 23:59; the last push before the deadline counts.