Truth-Table Engine

1. Sign in to github.com. No account yet? Create one first (2 minutes).
2. Click the orange Create your copy button at the top of this page. It opens GitHub’s “Create a new repository” form, already set to the Lab 1 template.
3. Fill in the form exactly like this:

4. Click Create repository. You now have your-username/dm-2026-lab01.

In your new repository:

1. Click Settings (top right of the repository page), then Collaborators in the left menu.
2. Click Add people, type drferhatu, choose drferhatu and click Add to repository.

The instructor can only grade repositories shared with him. Your repository stays private: nobody else can see it.

Still on the repository page, open README.md, click the pencil icon ✎ and fill in the two lines:

- Name: Ada Lovelace
- Student ID: 23xxxxxxx

Click Commit changes… and then Commit changes. This is how your GitHub username is matched to you in the grade list.

On your repository page:

1. Click the green Code button.
2. Choose the Codespaces tab.
3. Click Create codespace on main.

A VS Code editor opens in your browser. The first start takes a minute or two while Python and the tests are installed; watch the terminal at the bottom until it is ready.

In the file explorer on the left you see:

In the terminal, run the checks before writing any code:

$ python check.py:| implies(p, q) matches the truth table of p → q
  not implemented yet (still raises NotImplementedError)
...
0/21 checks passed

Every check shows :| because nothing is implemented yet. Your job is to turn them all into :).

Open truth.py. Python has not, and and or. Write implies, iff and xor. Replace each raise NotImplementedError with a return statement.

Use the lecture: $p \to q$ is false only when $p$ is true and $q$ is false, so it equals $\neg p \lor q$. For booleans, $p \leftrightarrow q$ is “same value” and $p \oplus q$ is “different value”.

$ python check.py:) implies(p, q) matches the truth table of p → q
:) iff(p, q) matches the truth table of p ↔ q
:) xor(p, q) matches the truth table of p ⊕ q

rows(n) returns every assignment of n variables as a list of tuples, True before False, the last variable changing fastest. For two variables:

rows(2) == [(True, True), (True, False), (False, True), (False, False)]

itertools.product (already imported) does exactly this. Try it in the terminal first:

$ python -c "from itertools import product; print(list(product([True, False], repeat=2)))"

Watch out: product returns an iterator, and the function must return a list. And what should rows(0) be? One row with no variables, [()]. Check that product agrees.

A formula is a Python function. For example lambda p, q: implies(p, q) takes two booleans and returns one. To evaluate it on a row (a tuple), unpack the tuple: f(*row).

Write, in this order, reusing each function in the next:

1. truth_table(f, n): a list of (row, f(*row)) pairs, for every row of rows(n).
2. is_tautology: true in every row. Python’s all() is ∀.
3. is_satisfiable: true in at least one row. Python’s any() is ∃. (You will meet ∀ and ∃ again in week 4.)
4. is_contradiction: true in no row.
5. equivalent(f, g, n): same value in every row.
6. count_true(f, n): how many rows are true.

format_table(f, names, label) returns the table as one string. The format must match exactly, because the autograder compares strings:

p q | p∧q
1 1 | 1
1 0 | 0
0 1 | 0
0 0 | 0

Values separated by one space, the result after " | ", lines joined with "\n", no trailing newline. Tips: " ".join(...), and "1" if v else "0".

Then run the demo at the bottom of the file:

$ python truth.pyp q | p→q
1 1 | 1
1 0 | 0
0 1 | 1
0 0 | 1

(p → q) ↔ (¬q → ¬p) is a tautology: True
(p → q) ↔ (q → p)   is a tautology: False

You just proved, by exhaustion, that the contrapositive is equivalent and the converse is not.

Let $p$: “the server is overloaded”, $q$: “the request is served from cache”, $r$: “the response is slow”. Translate each sentence into a Python expression over p, q, r. You may use your own implies.

1. spec1: The response is slow only if the server is overloaded and the request is not served from cache.
2. spec2: The request is served from cache unless the server is overloaded.
3. spec3: Neither is the server overloaded nor is the response slow.

These are the translation exercises from the lecture. If a check fails, look at the week 2 notes on “only if” and “unless”.

Submitting = pushing your work to GitHub. Type these three lines in the terminal:

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

Prefer buttons? Use the Source Control icon on the left of VS Code: type a message, click Commit, then Sync Changes.

Then check that it arrived:

1. Open your repository on github.com. Your latest commit message (“Lab 1”) is shown at the top of the file list.
2. Next to it, after about a minute, a ✅ (all checks passed) or ❌ (some failed) appears. Click it, then Details, to see the same :) / :( list as python check.py.