Quantifiers over Real Data

1. Click the orange Accept lab lab03 button at the top of this page, then Accept assignment.
2. When the checklist finishes, click Open repository.
3. Green Code button → Codespaces → Create codespace on main.

First time with Classroom 50, or you missed Lab 2? Do Lab 2, step 1 first: you must have joined the course organization.

Prefer your own computer or another editor? That is fine too, see Other ways to work and submit.

Open data.py. It holds ten fictional students. Each student is a Python dictionary:

{"name": "Ada", "year": 2, "langs": {"Python", "C"}, "github": True, "math": 92}

Now run the checks once, before writing anything:

$ python check.py:| for_all: [2, 4, 6] all even → True, [2, 3, 6] → False, [] → True
  not implemented yet (still raises NotImplementedError)
...
0/17 checks passed

One more idea before you start. In this lab a predicate is a small function that takes one element and returns True or False. Python’s lambda writes it in one line:

is_even = lambda n: n % 2 == 0           # P(n): "n is even"
has_github = lambda s: s["github"]       # G(s): "s has a GitHub account"
is_even(4)                               # True

What: for_all(domain, P) answers “is P(x) true for every x in the domain?”

How: go through the domain with a for loop. The moment you find an x where P(x) is false, you have a counterexample: return False immediately. If the loop ends without finding one, return True.

for_all([2, 4, 6], lambda n: n % 2 == 0)    # True
for_all([2, 3, 6], lambda n: n % 2 == 0)    # False: 3 is a counterexample
for_all([], lambda n: False)                # True: nothing to break it

What: exists(domain, P) answers “is there at least one x with P(x) true?”

How: the mirror image of for_all. Return True at the first witness; if the loop ends, return False. Again, no any().

exists([1, 3, 4], lambda n: n % 2 == 0)     # True: 4 is a witness
exists([1, 3, 5], lambda n: n % 2 == 0)     # False
exists([], lambda n: True)                  # False: no witness in an empty domain

What: the same two loops, but instead of True/False they return the element they stopped at.

• counterexample(domain, P): the first x with P(x) false, or None.
• witness(domain, P): the first x with P(x) true, or None.

counterexample([2, 3, 5], lambda n: n % 2 == 0)   # 3
witness([1, 3, 4, 6], lambda n: n % 2 == 0)       # 4
witness([1, 3], lambda n: n % 2 == 0)             # None

These are what a real program needs: not only “false”, but who made it false.

What: sentences like “every second-year knows Python” have a filter (A: is a second-year) and a property (B: knows Python). From the notes:

• “Every A is B” is ∀x (A(x) → B(x)).
• “Some A is B” is ∃x (A(x) ∧ B(x)).

How: build a new predicate and pass it to your own for_all or exists:

• for every_such_that: the predicate lambda x: (not A(x)) or B(x) (that is A → B),
• for some_such_that: the predicate lambda x: A(x) and B(x).

big  = lambda n: n > 2
even = lambda n: n % 2 == 0
every_such_that([1, 2, 3, 4], big, even)   # False: 3 is big but odd
every_such_that([1, 2, 4], big, even)      # True: the only big number, 4, is even
some_such_that([1, 2, 3], big, even)       # False: no big even number

Now the real data. Each question is one function with a parameter students (it defaults to the class in data.py). Answer each with one line that uses your functions from steps 3–6.

An example of the style, for Q1:

def everyone_has_github(students=STUDENTS):
    return for_all(students, lambda s: s["github"])

For Q5, find the counterexample student first, then return s["name"] (or None if there is none). Use students inside your functions, never STUDENTS directly: the checks also ask your functions about other classes to make sure the answers are computed, not typed in.

$ python quantifiers.pyQ1 everyone has GitHub          : False
Q2 someone knows Java           : True
Q3 every 2nd-year knows Python  : False
Q4 no 1st-year failed Math I    : True
Q5 who breaks Q3                : Fırat

Look at data.py and confirm each answer by eye: who has no GitHub account? Which second-year does not know Python?

What: the two laws from the notes,

How: write the right-hand side.

• not_all(domain, P): call exists with a predicate that is the opposite of P: lambda x: not P(x).
• not_any(domain, P): call for_all with that opposite predicate.

The checks compare your answers with Python’s not all(...) and not any(...) on 60 random lists, and read your code to make sure not_all really uses exists and not_any really uses for_all. Writing not for_all(domain, P) gives the right value but skips the law, so it does not pass.

When python check.py shows 17/17 checks passed (or you have done what you can), push. Every push is graded, out of 100.

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

About two minutes later your score appears under Releases on your repository page. The last push before Friday 23:59 counts.