Six short lessons on the ideas the course takes for granted: sets, strings and languages, functions and state, what a proof is, logic words and truth tables, and how to read the notation. Python examples check each claim by brute force on small cases.
What you need first
Nothing to install. Every example is Python and runs on this page: press Run under the code. You can also change the code and run it again.
School arithmetic: add, multiply, divide with a remainder, and know what even and odd numbers are.
No programming and no earlier logic. Every Python word and every symbol is explained the first time it appears.
Patience with symbols. Each symbol comes with its name and how to say it aloud, and lesson 6 is a reading guide you can return to.
01
Sets and membership
Goal After this you can read and write a set, say whether something is an element of it, and use union, intersection and subset.
A set is a collection of things, called its elements. Only two questions matter about a set: what is in it, and what is not. Order does not matter and repeats do not count. We write a set with curly braces: {1, 2, 3} is the set whose elements are 1, 2 and 3. The set {3, 1, 2, 2} is the very same set, because order and repeats are ignored.
The symbol ∈ means "is an element of", and ∉ means "is not an element of". So 2 ∈ {1, 2, 3} is true and 5 ∈ {1, 2, 3} is false. A set can have no elements at all. That is the empty set, written ∅. The size of a set S, written |S|, is the number of its elements. |{1, 2, 3}| is 3 and |∅| is 0.
A set A is a subset of a set B, written A ⊆ B, when every element of A is also an element of B. For example {1, 2} ⊆ {1, 2, 3}. Every set is a subset of itself, and ∅ is a subset of every set. Do not mix up ∈ and ⊆. The statement 1 ∈ {1, 2} says 1 is an element. The statement {1} ⊆ {1, 2} says the set that contains only 1 is a subset. A set can also be an element of another set. The set {∅} has exactly one element, and that element is the empty set. So |{∅}| is 1, while |∅| is 0. A box with an empty box inside it is not an empty box.
There are three ways to combine two sets. The union A ∪ B has every element that is in A or in B or in both. The intersection A ∩ B has the elements that are in both. The difference A − B has the elements of A that are not in B. With A = {1, 2, 3} and B = {3, 4}: A ∪ B = {1, 2, 3, 4}, A ∩ B = {3}, and A − B = {1, 2}.
Python has sets too. In Python a variable is a name for a value, and = puts the value on its right under the name on its left. print(...) shows values on the screen. A set has no order of its own, so the example prints sorted(...) of each set. That puts the elements in order and makes the output the same on every run. The example tests each claim on a tiny case. Trying small cases like this is called brute force. It is a good way to see an idea work, but it does not prove anything about all sets.
New words
set
A collection of distinct things. Only membership matters, not order or repeats.
element
One of the things in a set. We write x ∈ S for "x is an element of S".
subset (⊆)
A is a subset of B when every element of A is also in B.
union, intersection, difference
A ∪ B: in A or B. A ∩ B: in both. A − B: in A but not in B.
empty set (∅)
The set with no elements. Its size is 0.
brute force
Testing a claim on every case in a small range.
Worked example
Python 3
A={1,2,3}B={3,4}print("2 in A:",2inA)print("5 in A:",5inA)print("size of {3, 1, 2, 2}:",len({3,1,2,2}))print("A union B:",sorted(A|B))print("A intersect B:",sorted(A&B))print("A minus B:",sorted(A-B))print("{1, 2} subset of A:",{1,2}<=A)print("A subset of B:",A<=B)print("size of the empty set:",len(set()))print("size rule holds:",len(A|B)==len(A)+len(B)-len(A&B))
Predict the output first, then show it
Expected output
2 in A: True
5 in A: False
size of {3, 1, 2, 2}: 3
A union B: [1, 2, 3, 4]
A intersect B: [3]
A minus B: [1, 2]
{1, 2} subset of A: True
A subset of B: False
size of the empty set: 0
size rule holds: True
Step by step
A = {1, 2, 3} makes a set and gives it the name A. Curly braces make a set in Python, as on paper.
The word in asks the membership question and answers True or False. 2 in A is Python for 2 ∈ A.
len(...) gives the number of elements. In {3, 1, 2, 2} the repeated 2 counts once, so the answer is 3.
The signs |, & and - give the union, the intersection and the difference. The sorted(...) around them lists the result in order, so you see the same lines each time.
<= asks "is the left set a subset of the right set?" {1, 2} is a subset of A, but A is not a subset of B.
set() makes the empty set. Python also has {}, but that makes something else, as the mistakes below show.
The last line checks a rule by brute force on this one pair: the size of a union is the two sizes added, minus the size of the overlap, so the overlap is not counted twice. It prints True here.
Common mistakes
Wrong
empty = {}
print(empty | {1})
In Python, {} is an empty dictionary, which is a different kind of thing. It cannot be combined with a set, so the second line stops with TypeError. The empty set is written set().
Right
empty = set()
print(empty | {1})
Wrong
print({1} in {1, 2}) # prints False
The word in asks whether the thing on the left is an element of the set on the right. The elements of {1, 2} are 1 and 2. The set {1} is not one of them, so the answer is False. To ask whether {1} is a subset, use <=.
Right
print({1} <= {1, 2}) # prints True
Wrong
print({"cat", "ant", "bee"})
A set has no order, so Python may show the elements in a different order on different runs. Your output then does not match what you expected. Put sorted(...) around the set before printing it.
Right
print(sorted({"cat", "ant", "bee"}))
Check yourself
How many elements does {a, b, a, c} have? And how many does {∅} have, compared with ∅?
Try it first, then show the answer
3, because the repeated a counts once and the set is {a, b, c}. The set {∅} has 1 element, the empty set, while ∅ has 0 elements.
Are these true? (a) {1, 2} ⊆ {1, 2}. (b) ∅ ⊆ {1, 2}. (c) 1 ⊆ {1, 2}.
Try it first, then show the answer
(a) True: every set is a subset of itself. (b) True: ∅ has no elements, so none of them can be missing from {1, 2}. (c) It is not a valid statement, because 1 is an element, not a set. Write 1 ∈ {1, 2}, or {1} ⊆ {1, 2}.
Write the Python for A ∩ B with A = {1, 2, 3, 4} and B = {2, 4, 6}. What does it print?
Try it first, then show the answer
print(sorted({1, 2, 3, 4} & {2, 4, 6})) prints [2, 4]. Those are the elements that are in both sets.
02
Strings, alphabets and languages
Goal After this you can list the strings over a small alphabet, and say what a language is.
An alphabet is a finite set of symbols. We write it Σ, the Greek capital letter sigma. For example Σ = {a, b}, or Σ = {0, 1}. A symbol can be anything: a letter, a digit, a dot. The only rule is that the set is finite.
A string over Σ is a finite row of symbols from Σ, written one after another. The row abba is a string over {a, b}. Order matters: ab and ba are different strings. The length of a string w is written |w|, so |abba| is 4. There is also a string with no symbols at all, the empty string, written ε (Greek epsilon). Its length is 0. The empty string is a real string, even though it is invisible on the page. Joining two strings end to end is called concatenation: ab joined with ba gives abba. Joining ε to any string changes nothing.
Σ* (say "sigma star") is the set of all strings over Σ, of every length including 0. For Σ = {a, b} it begins ε, a, b, aa, ab, ba, bb, aaa, and it goes on for ever. There are 2 strings of length 1, 4 of length 2 and 8 of length 3. A string of length k has k positions with 2 choices each, so there are 2 × 2 × ... × 2 = 2^k strings of length k. The set Σ* is infinite, but every single string in it is finite.
A language is any set of strings over Σ. In other words, it is any subset of Σ*. This is not a spoken language, and it does not need a rule. For Σ = {a, b}, the strings that end in b form a language: b, ab, bb, aab, and so on. The set {ab, ba} is a language with two strings. The set ∅, with no strings, is a language. The set {ε}, with one string, the empty string, is another language. The two are different: ∅ has no strings, and {ε} has one string, which happens to be empty.
In Python a string is text in quotes, such as "abba". The empty string is two quotes with nothing between them: "". len(...) gives the length and + joins two strings. A list, written in square brackets, is an ordered row of values. A for loop runs its indented lines once for each item of a list. Python uses indentation, the spaces at the start of a line, to show which lines belong inside the loop. Two stars mean "to the power of", so 2 ** 3 is 8. The example builds the strings over {a, b} of length 0, 1, 2 and 3, one length at a time. Each string of length k gives two strings of length k + 1, by adding a or b at the end. Then a second loop picks out one language, the strings that end in b.
New words
alphabet (Σ)
A finite set of symbols.
string
A finite row of symbols from the alphabet. Order matters.
empty string (ε)
The string with no symbols. Its length is 0.
Σ*
The set of all strings over Σ, including ε. It is infinite.
language
Any set of strings over Σ, that is, any subset of Σ*.
concatenation
Joining two strings end to end. In Python, the + sign.
alphabet is a list of the two symbols. current starts as [""], a list holding one string, the empty string. That is the only string of length 0.
range(4) gives the numbers 0, 1, 2 and 3, so the outer for runs four times, with length equal to each of them in turn. Each time it prints the length, how many strings there are of that length, and the strings themselves.
everything = everything + current adds the strings of this length to the list of all strings so far. The + sign joins two lists, just as it joins two strings.
The two inner loops build the next length. For each string s and each symbol, s + symbol is a longer string, and append puts it at the end of the list longer. Then current = longer moves on to the next length.
The printed counts are 1, 2, 4, 8: that is 2^length, as the explanation says. The loop never lists all of Σ*, because that is infinite. It lists every string up to length 3.
.endswith("b") asks whether a string ends with b. The second loop keeps those strings. The empty string is in everything but not in ends_in_b, because it has no last symbol.
The last line shows 15 strings of length at most 3, of which 7 end in b. So the language "strings ending in b", cut off at length 3, has 7 strings.
Common mistakes
Wrong
print(len([""])) # expecting 0
The empty string "" has length 0, but a list that holds the empty string has one item, so its length is 1. This is the same difference as ε against {ε}, and ∅ is like the empty list [], which has length 0.
Right
print(len(""), len([""]), len([])) # 0 1 0
Wrong
empty = " " # a space
A space is a symbol like any other, so " " is a string of length 1. The empty string has no characters at all. Mixing them up makes counts off by one, and a language that contains ε no longer matches.
Right
empty = ""
Wrong
# "ab" and "ba" are the same string, just like {a, b} and {b, a}
A set ignores order but a string does not. {a, b} and {b, a} are one set, while ab and ba are two different strings. Python agrees: "ab" == "ba" is False.
Right
print("ab" == "ba") # False: a string is a row, order matters
Check yourself
How many strings of length 5 are there over Σ = {0, 1, 2}? Check your answer with Python.
Try it first, then show the answer
Each of the 5 positions has 3 choices, so 3 × 3 × 3 × 3 × 3 = 3^5 = 243. In Python, print(3 ** 5) prints 243.
Is ε in the language of all strings of length at most 2 over {a, b}? Is it in the language of strings that end in b?
Try it first, then show the answer
Yes for the first, because its length 0 is at most 2. No for the second, because ε has no last symbol, so it does not end in b.
Predict what len("ab" + "" + "ba") prints.
Try it first, then show the answer
4. Joining with the empty string changes nothing, so the string is "abba", and its length is 4.
03
Functions and what "state" means
Goal After this you can say what a function is, write one as a table, and explain what the state of a machine is.
A function is a rule that gives each allowed input exactly one output. The rule f(x) = x + 1 is a function: f(3) is 4. Two things must hold. Every allowed input has an output, so no input is left without an answer. And no input has two different outputs. The set of allowed inputs is called the domain.
When there are only a few inputs, a function can be written as a table with one row per input. A table is a function exactly when every input appears in exactly one row. If a row is missing, the function is not defined for that input. If one input appears in two rows with different outputs, the table is not a function.
A state is the information a process remembers right now. Think of a light switch. Its state is "on" or "off". It does not remember how many times it has been flipped, only what it is at this moment. A machine that reads a string one symbol at a time has to decide what to remember. Remembering the whole string works, but it needs more and more memory as the string grows. Often a tiny amount is enough. To answer "does this string have an even number of 1s?" only two things matter: the count so far is even, or the count so far is odd. Those are the two states.
Such a machine is described by its start state and a transition function. The transition function takes two inputs, the current state and the next symbol, and gives one output, the next state. Because it is a function, it needs a row for every pair of state and symbol. After the last symbol has been read, the state the machine is in gives its answer.
In Python a dictionary is a table. It pairs keys with values, and delta[key] looks up the value for a key. A pair written in round brackets, such as ("even", "1"), is called a tuple, and a tuple can be a key. The example stores the transition function as a dictionary. It runs the machine by updating a variable called state once for each symbol. The word if asks a question and runs its indented lines only when the answer is yes, and else covers the other case.
New words
function
A rule giving each allowed input exactly one output.
domain
The set of allowed inputs of a function.
state
What a process remembers right now. A machine with finitely many states can remember only finitely many things.
transition function
Takes the current state and the next symbol, and gives the next state. Often written δ.
dictionary
A Python table that pairs keys with values.
tuple
A fixed pair or row of values in round brackets, such as ("even", "1").
read 1 -> state odd
read 1 -> state even
read 0 -> state even
read 1 -> state odd
'' even True
'1' odd True
'11' even True
'0110' even True
'10101' odd True
Step by step
delta is a dictionary with four rows. Each key is a pair (state, symbol), and its value is the next state. This is the transition function written as a table, with a row for every pair.
def run(word): is a function that starts in state "even", reads the word one symbol at a time, and returns the state it ends in. The line state = delta[(state, symbol)] looks up the row and stores the answer back in state.
The first loop shows the machine on 1101, one step at a time: odd, even, even, odd. The word has three 1s, an odd number, and the machine ends in "odd".
The second loop tests the machine on five words. word.count("1") counts the 1s, and % 2 gives the remainder after dividing by 2, which is 0 for an even count and 1 for an odd count. expected is what the answer should be.
repr(word) prints the string with quotes, so the empty string shows up as two quotes instead of vanishing. Every line ends in True: the machine agrees with counting.
The machine never stores the word. It stores only one of two states. That is the whole point of a state.
There is no row for ("odd", "1"). The first time the machine is in state odd and reads a 1, Python stops with KeyError: ('odd', '1'). In maths words, the transition function is not defined on every input, so it is not a complete function.
The lookup finds the next state and then throws it away. state never changes, so the machine answers "even" for every word. The result of the lookup has to be stored back in state.
Right
for symbol in word:
state = delta[(state, symbol)]
Wrong
delta[[state, symbol]]
A dictionary key cannot be a list, because a list can change after it is stored. Python stops with TypeError: unhashable type: 'list'. Round brackets make a tuple, which cannot change, so it can be a key.
Right
delta[(state, symbol)]
Wrong
history = ""
for symbol in word:
history = history + symbol
This remembers every symbol read. It does give enough information to answer, but the memory grows with the word, so no fixed number of states could hold it. A machine with finitely many states must forget what does not matter. For parity, two states are enough.
Right
state = delta[(state, symbol)] # two states are enough
Check yourself
Trace the machine on 0110 by hand. Write the state after each symbol.
Try it first, then show the answer
Start in even. Read 0: even. Read 1: odd. Read 1: even. Read 0: even. The final state is even, which agrees with two 1s being an even number.
Is this table a function? (even,0) gives even; (even,0) gives odd; (even,1) gives odd; (odd,0) gives odd; (odd,1) gives even.
Try it first, then show the answer
No. The input (even,0) appears twice with different outputs. A function gives exactly one output for each input. A Python dictionary cannot even hold this table: a repeated key keeps only the last value.
Write the transition table for a machine that remembers only whether the last symbol it read was 0 or 1. Call the states "zero" and "one", and start in "zero".
Try it first, then show the answer
delta = {("zero", "0"): "zero", ("zero", "1"): "one", ("one", "0"): "zero", ("one", "1"): "one"}. Whatever state you are in, reading a symbol sends you to the state named after that symbol.
04
What a proof is: contradiction and induction
Goal After this you can say how a proof differs from testing, and follow a proof by contradiction and a proof by induction.
A proof is a chain of statements. Each statement is either given, or follows from earlier ones by a step that anyone can check. The last statement is the claim. A proof is different from testing. Testing tries some cases. If one case fails, you have a counterexample, and that disproves the claim. If every case passes, you have evidence, not a proof, because there are always cases you did not try. Python is good at finding counterexamples. It cannot prove a claim about all numbers.
Proof by contradiction works like this. To show that a claim is true, assume it is false. Follow the consequences until you reach something impossible, such as a number that is both even and odd. Correct reasoning cannot lead to something impossible, so the assumption must have been wrong, and the claim is true. If the claim has the form "if P then Q", the assumption is that P is true and Q is false.
Here is an example. Claim: if n × n is even, then n is even. Suppose, for contradiction, that n × n is even and n is not even. A whole number that is not even is odd, so n = 2m + 1 for some whole number m. Then n × n = 4m² + 4m + 1 = 2(2m² + 2m) + 1, which is odd. But we assumed n × n is even, and no number is both even and odd. That is a contradiction. So the assumption was wrong, and the claim holds.
Proof by induction proves a claim for every k = 0, 1, 2, ... with two parts. The base case shows the claim for k = 0. The step assumes the claim for some k and shows it for k + 1. Then the claim holds for 0, so for 1, so for 2, and so on, like a row of dominoes. Example claim: there are exactly 2^k strings of length k over {a, b}. Base case, k = 0: only the empty string has length 0, and 2^0 is 1. Step: every string of length k + 1 is a string of length k followed by one symbol, a or b. By assumption there are 2^k strings of length k, and each gives 2 strings of length k + 1. So there are 2 × 2^k = 2^(k+1).
The Python example looks for a counterexample to the first claim among the numbers below 1000. An empty list means none was found. That is evidence, and the proof above is what turns it into certainty. Next, it looks for a counterexample to a false claim, and it finds one at once. The word break ends the loop early. Last, it counts the strings of each length up to 6 and compares with 2^k.
New words
proof
A chain of statements, each given or following from earlier ones by a checkable step, ending in the claim.
counterexample
One case where a claim fails. One is enough to disprove the claim.
proof by contradiction
Assume the claim is false and derive something impossible.
proof by induction
Show the base case, then show that the claim for k gives the claim for k + 1.
even, odd
Even: 2m for some whole number m. Odd: 2m + 1 for some whole number m.
Worked example
Python 3
# Claim 1: if n * n is even, then n is even.counterexamples=[]forninrange(1000):if(n*n)%2==0andn%2==1:counterexamples.append(n)print("counterexamples to claim 1:",counterexamples)# A false claim: if n * n is even, then n is a multiple of 4.forninrange(1000):if(n*n)%2==0andn%4!=0:print("counterexample to the false claim:",n)break# Claim 2: there are 2 ** k strings of length k over {a, b}.strings=[""]forkinrange(7):print(k,len(strings),2**k)assertlen(strings)==2**klonger=[]forsinstrings:longer.append(s+"a")longer.append(s+"b")strings=longer
The first loop searches for a number n where n * n is even but n is odd. The condition has two parts joined by and, and both must hold. n % 2 is the remainder after dividing by 2, so n % 2 == 1 means n is odd.
The list is empty: the search found no counterexample below 1000. That agrees with the proof by contradiction, but only the proof covers every number.
The second loop tests a false claim. At n = 2, n * n is 4, which is even, but 2 is not a multiple of 4. A single counterexample is enough to disprove the claim, and break ends the loop at once.
The last part builds the strings of each length, as in the previous lesson. Each string becomes two longer strings, one with a added and one with b added. This is the induction step done with actual strings.
Each line shows k, the number of strings, and 2 ** k, which is 2 to the power k. The two numbers match. The assert would stop the program with AssertionError if they ever differed.
This checks lengths 0 to 6 only. The induction proof in the explanation covers every length.
Common mistakes
Wrong
# 2**n - 1 is prime for n = 2, 3, 5, 7
# so it is prime for every prime n
Four successes are not a proof. The next prime breaks it: at n = 11 the number is 2047, which is 23 times 89. A test can disprove a claim but cannot prove one for all cases.
Right
print(2 ** 11 - 1, 23 * 89) # 2047 2047
Wrong
Assume n is even. Then n * n is even. Done.
This proves the opposite direction: if n is even then n * n is even. The claim was: if n * n is even then n is even. To prove it by contradiction, start from n * n even together with n not even, and derive something impossible.
Right
Assume n * n is even and n is odd. Then n * n is odd. Contradiction.
Wrong
# Claim: a string of length k has k + 1 symbols.
# Step: if length k has k + 1 symbols, adding one symbol gives k + 2 symbols for length k + 1.
# So it is true for every k.
The step is correct, but the base case was never checked, and the claim is false. The empty string has length 0 and 0 symbols, not 1. A correct step cannot rescue a claim that fails at the start: nobody pushed the first domino.
Right
print(len("")) # 0, not 1: the base case fails, so the claim is false
Check yourself
Prove by contradiction that there is no largest even number.
Try it first, then show the answer
Suppose m is the largest even number. Then m + 2 is also even, and it is bigger than m. That contradicts the choice of m as the largest. So the supposition was wrong, and there is no largest even number.
Prove by induction that 1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1 for n = 1, 2, 3, ...
Try it first, then show the answer
Base case n = 1: the left side is 1 and the right side is 2^1 - 1 = 1. Step: assume 1 + 2 + ... + 2^(k-1) = 2^k - 1. Add the next term 2^k to both sides: 2^k - 1 + 2^k = 2 × 2^k - 1 = 2^(k+1) - 1. That is the claim for k + 1.
Python finds no counterexample to a claim for n from 1 to 1,000,000. Is the claim proved? Why or why not?
Try it first, then show the answer
No. It is evidence for one million cases, and there are infinitely many numbers. The 2^n - 1 example above passes four prime cases and fails at the fifth. Only a proof covers all cases.
05
Logic words and truth tables
Goal After this you can build and read a truth table for and, or, not and implies, and check by brute force that two statements are equivalent.
A statement that is either true or false is called a proposition. "7 is odd" is a proposition. "Close the door" is not. We use letters such as p and q for propositions. Logic builds bigger statements from smaller ones with a few joining words.
Here are the words. "not p", written ¬p, is true when p is false. "p and q", written p ∧ q, is true only when both are true. "p or q", written p ∨ q, is true when at least one is true, and that includes the case where both are. In everyday speech "or" often means one or the other but not both. In logic it never does. "p implies q", written p → q and also read "if p then q", is false in exactly one case: p is true and q is false. In every other case it is true.
The last one surprises people. Take the promise "if it rains, I will bring an umbrella". The promise is broken only if it rains and I bring no umbrella. If it does not rain, the promise is not broken, whatever I do. So p → q is true whenever p is false. Logicians call this vacuously true: nothing was tested, so nothing failed.
A truth table lists every combination of true and false for the letters, and gives the value of the statement in each row. With two letters there are 4 rows, with three letters 8 rows, and with k letters 2^k rows. Two statements are equivalent when their tables have the same value in every row. One example is De Morgan's rule: "not (p and q)" is equivalent to "(not p) or (not q)".
Python has and, or and not as ordinary words, and True and False as its two truth values. It has no word for implies. We write (not p) or q, which has the same table as p → q. Two loops, one inside the other, visit every row. Here, checking every row is a complete proof, because there are only four rows and the check covers all of them. Brute force is a proof exactly when it covers every case.
New words
proposition
A statement that is either true or false.
¬ ∧ ∨ →
not, and, or, implies. Python: not, and, or, and (not p) or q.
truth table
A table with one row for each combination of true and false for the letters, and the statement's value in each row.
equivalent
Two statements are equivalent when their truth tables agree in every row.
vacuously true
An implication with a false first part is true because nothing was promised.
Worked example
Python 3
defimplies(p,q):return(notp)orqprint("p q | p and q | p or q | not p | p implies q")forpin[True,False]:forqin[True,False]:print(p,q,"|",pandq,"|",porq,"|",notp,"|",implies(p,q))same=Trueforpin[True,False]:forqin[True,False]:if(not(pandq))!=((notp)or(notq)):same=Falseprint("not (p and q) equals (not p) or (not q):",same)
Predict the output first, then show it
Expected output
p q | p and q | p or q | not p | p implies q
True True | True | True | False | True
True False | False | True | False | False
False True | False | True | True | True
False False | False | False | True | True
not (p and q) equals (not p) or (not q): True
Step by step
def implies(p, q): makes a function from the rule: p implies q is the same as (not p) or q. Python has no word for implies, so we build it.
The two nested loops visit every row. The outer loop gives p each of True and False, and the inner loop gives q each of True and False, so print runs four times.
Each printed row shows p, q, and then p and q, p or q, not p and implies(p, q). Read the second row: p is True and q is False, so "p and q" is False, "p or q" is True, "not p" is False and "p implies q" is False. It is the only row where implies is False.
In the third and fourth rows p is False, and implies is True. That is the umbrella promise again: nothing was tested, so nothing failed.
The second part checks De Morgan's rule on all four rows. != means "is not equal to". If the two sides ever differ, same becomes False. It stays True, so the two statements are equivalent.
Because the four rows are all the rows there are, this brute-force check is a complete proof of the equivalence.
Common mistakes
Wrong
# "if p then q" is false whenever p is false
It is the other way round. A promise can be broken only when its condition happens. If p is false, nothing was promised, so p → q is true. The only row where p → q is false is p true and q false.
Right
# "if p then q" is true whenever p is false
Wrong
# p implies q means the same as q implies p
q → p is the converse, and it is a different statement. With p False and q True, p → q is True but q → p is False. The statement that is equivalent to p → q is (not q) → (not p), called the contrapositive.
Right
implies(p, q) == implies(not q, not p) # True in all four rows
Wrong
not p and q # meant: not (p and q)
In Python, not applies only to the thing right after it, so this means (not p) and q. With p True and q False it is False, while not (p and q) is True. Put in brackets whenever you mean "not of the whole thing".
Right
not (p and q)
Wrong
# True or True is False, because "or" means one or the other
In everyday speech "or" often excludes both. In logic p ∨ q is true when at least one is true, and when both are true as well. Python follows logic.
Right
print(True or True) # True
Check yourself
In which rows of the truth table is p → q false?
Try it first, then show the answer
Only the row where p is true and q is false. In the other three rows p → q is true.
Write a Python expression that is True exactly when p is True and q is False. How does it relate to p → q?
Try it first, then show the answer
p and (not q). It is True in the one row where p → q is False, and False in the other three. So it is the opposite of p → q: not (p → q) is equivalent to p ∧ ¬q.
Is p → q equivalent to (not q) → (not p)? Check by listing the four rows.
Try it first, then show the answer
Yes. For (p, q) = (T, T): both true. (T, F): both false. (F, T): both true. (F, F): both true. The tables agree in every row, so the two statements are equivalent.
06
Reading notation: Σ*, δ(q, a) and set-builder
Goal After this you can read a line of course notation aloud, say what it means in words, and write the same idea in Python.
Mathematical notation is shorthand for sentences. A line such as L = {w ∈ Σ* : |w| is even} looks hard, but it is a sentence squeezed into symbols. Reading it means unpacking it. The method has four steps. Say the name of every symbol aloud. Ask what kind of thing each one is: a set, a string, a state or a number. Say the whole line in plain words. Test it on a tiny case. Python can help with the last step, because most of this notation has a Python twin.
Σ and Σ*. The symbol Σ (sigma) is an alphabet, a finite set of symbols. Σ* is the set of all strings over Σ, including the empty string. Σ^k, read "sigma to the k", is the set of strings of length exactly k. So {0, 1}^2 is {00, 01, 10, 11}. A small number written below a letter is part of its name: q₀ is one state, the start state, and it is not "q minus 0".
Set-builder notation. {x ∈ S : P(x)} is read "the set of all x in S such that P(x) holds". The part before the colon says where x comes from. The part after it says which of those x are kept. Some books write a vertical bar | instead of the colon. For example {w ∈ {0, 1}^2 : w ends in 1} is {01, 11}. In Python this is a set built by a loop with a filter: {w for w in S if P(w)}.
δ(q, a). The symbol δ (delta) is the transition function of a machine. Read δ(q, a) as "the state you reach from state q on reading the symbol a". It takes one symbol. A Python dictionary such as {("q0", "1"): "q1", ...} is the same function, and δ(q, a) is delta[(q, a)]. For a whole string the books use a second function, written δ*(q, w), which applies δ once for each symbol of w.
Quantifiers. The symbol ∀ means "for all". "∀w ∈ S : P(w)" says P holds for every w in S. The symbol ∃ means "there exists". "∃w ∈ S : P(w)" says at least one w in S satisfies P. Python's all(...) and any(...) do the same on a finite set. Other symbols from the course: ε is the empty string, ∅ is the empty set, ∪ and ∩ are union and intersection, |w| is the length of a string, |S| is the size of a set, and ⊆ means subset.
New words
Σ^k
The set of strings of length exactly k over Σ.
set-builder notation
{x ∈ S : P(x)} is the set of all x in S for which P(x) holds. The colon means "such that".
δ(q, a)
The state reached from state q on reading the symbol a.
∀ and ∃
"For all" and "there exists". In Python on a finite set: all(...) and any(...).
subscript
A small number or letter below a symbol that is part of a name, as in q₀.
Worked example
Python 3
sigma={"0","1"}# Σ, the alphabet# Σ^2: all strings of length 2 over Σsigma_2=set()forainsigma:forbinsigma:sigma_2.add(a+b)print("sigma^2 =",sorted(sigma_2))# set-builder: {w in Σ^2 : w ends in 1}ends_in_1={wforwinsigma_2ifw.endswith("1")}print("ends in 1:",sorted(ends_in_1))# δ(q, a): a transition function stored as a tabledelta={("q0","0"):"q0",("q0","1"):"q1",("q1","0"):"q0",("q1","1"):"q1"}print("delta(q0, 1) =",delta[("q0","1")])print("delta(q1, 0) =",delta[("q1","0")])# for all, there existsprint("all have length 2:",all(len(w)==2forwinsigma_2))print("some w equals 11:",any(w=="11"forwinsigma_2))
Predict the output first, then show it
Expected output
sigma^2 = ['00', '01', '10', '11']
ends in 1: ['01', '11']
delta(q0, 1) = q1
delta(q1, 0) = q0
all have length 2: True
some w equals 11: True
Step by step
sigma is the alphabet Σ as a Python set. Text after a # on a line is a comment: Python ignores it, and people read it. The comments show the maths symbol next to its Python twin.
The two nested loops build Σ^2. For every symbol a and every symbol b, a + b is a string of length 2, and add puts it into the set. Because it is a set, nothing is added twice.
ends_in_1 is the set-builder line. Read {w for w in sigma_2 if w.endswith("1")} aloud as "the set of all w in sigma_2 such that w ends in 1". It matches {w ∈ Σ² : w ends in 1} part for part and gives {01, 11}.
delta is a table, and delta[("q0", "1")] is δ(q0, 1). Reading 1 in state q0 leads to q1, and reading 0 in state q1 leads to q0. Each lookup takes one state and one symbol.
all(len(w) == 2 for w in sigma_2) is ∀w ∈ Σ² : |w| = 2. It tests every w and answers True only if the test is True for all of them.
any(w == "11" for w in sigma_2) is ∃w ∈ Σ² : w = 11. It answers True if at least one w passes the test. Both answers are True here.
Common mistakes
Wrong
# Sigma* with Sigma = {0, 1} is {0, 00, 000, ...}
That is the set of strings made only of 0s. The star in Σ* means all strings over Σ, with any mix of the symbols, and it includes the empty string. It begins ε, 0, 1, 00, 01, 10, 11, and goes on.
δ takes one symbol, not a string. There is no row for the pair ("q0", "101"), so Python stops with KeyError. To run a whole string, apply δ once per symbol, which is what δ* does.
Right
state = "q0"
for symbol in "101":
state = delta[(state, symbol)]
Wrong
{w: w.endswith("1") for w in sigma_2}
In maths the colon means "such that". In Python a colon inside curly braces makes a dictionary, here with keys w and values True or False. That is a table, not the set you wanted. In Python the filter is written with if.
Right
{w for w in sigma_2 if w.endswith("1")}
Wrong
sigma_2 = {"00", "11"} # each symbol written twice
Σ² is not each symbol squared. It is every string of length 2, so all four combinations. A set with only 00 and 11 misses 01 and 10.
Right
sigma_2 = {"00", "01", "10", "11"}
Check yourself
Put L = {w ∈ {a, b}* : |w| is even} into plain words. Give three strings in L and one string that is not.
Try it first, then show the answer
L is the set of all strings of a's and b's whose length is an even number. In L: ε (length 0), ab (length 2) and bbaa (length 4). Not in L: a, which has length 1.
Write the Python for {w ∈ Σ³ : w starts with 0} with Σ = {0, 1}. How many elements does it have?
Try it first, then show the answer
Build sigma_3 with three nested loops, adding a + b + c each time, then write starts_0 = {w for w in sigma_3 if w.startswith("0")}. It has 4 elements: 000, 001, 010 and 011. That is half of the 8 strings in Σ³.
With the table in the example, what is δ(q1, 1)? Starting in q0 and reading 101 one symbol at a time, which state do you reach?
Try it first, then show the answer
δ(q1, 1) is q1. From q0: reading 1 gives q1, reading 0 gives q0, reading 1 gives q1. The final state is q1.