Hints: Discrete Mathematics¶
The exercises are collapsed initially. Click on the title to expand.
Avoid looking at the hints too quickly. Allow at least 10 minutes of thinking before resorting to them.
Question 1¶
Q1
Give the truth table for the following propositions
| Expression | Meaning |
|---|---|
| \(a \land b\) | \(a\) and \(b\) |
| \(a \lor b\) | \(a\) or \(b\) |
| \(a \oplus b\) | \(a\) xor \(b\) |
| \(\lnot a\) (or \(\bar a\)) | not \(a\) |
| \(a\implies b\) | \(a\) implies \(b\), or: if \(a\) then \(b\) |
| \(a\iff b\) | \(a\) and \(b\) are equivalent, or: "\(a\) if and only if \(b\)" |
Info
It is usual to apply these "bit-wise" to the bits of integers, e.g. \(\texttt{0011} \oplus \texttt{0101} = \texttt{0110}\).
Think of and as multiplication, or as addition and x-or as subtraction.
For implication, it is only false if we have the premise but not the promise.
Equivalence is similar to equality.
Question 2¶
Q2
Recall that:
- \(\mathbb{N}=\{1,2,3,\ldots\}\) is the set of natural numbers
- \(\mathbb{Z} = \{\ldots, -3, -2, -1, 0 , 1 , 2, 3, \ldots \}\) is the set of integers.
Consider the following set definitions
- \(A = \{a\in\{1,2,3,4\} \mid (a<2) \lor (a>3)\}\)
- \(B = \{a\in\mathbb{N} \mid a<9\}\)
- \(C = \{a\in\mathbb{N} \mid a>2 \land a<7\}\)
-
\(D = \{i\in\mathbb{Z} \mid i^2\leq 9\}\)
-
Give an explicit enumeration for each set, i.e. write down the elements in the form \(\{x_1,x_2,\ldots\}\).
- What is the cardinality of each set?
- Which of these sets are subsets of at least one other set?
Think about the code that could generate the same sets.
For example, using Python for \(A = \{a\in\{1,2,3,4\} \mid (a<2) \lor (a>3)\}\):
for a in [1,2,3,4]:
if a<2 or a>3:
print(a)
[a for a in [1,2,3,4] if a<2 or a>3]
For the rest, try:
-
\(B = \{a\in\mathbb{N} \mid a<9\}\).
\(\mathbb{N}\) is infinite and we will just try some numbers smaller than 100:
[a for a in range(1,100) if a<9] -
\(C = \{a\in\mathbb{N} \mid a>2 \land a<7\}\)
[a for a in range(1,100) if a>2 and a<7] - \(D = \{i\in\mathbb{Z} \mid i^2\leq 9\}\)
[a for a in range(-100,101) if a**2<=9]
Question 3¶
Q3
Write formal descriptions of the following sets.
- The set containing all natural numbers that are less than 5.
- The set containing all integers that are greater than 5.
- The set containing the strings \(\texttt{a}\texttt{a}\) and \(\texttt{b}\texttt{a}\).
- The set containing the empty string.
- The set containing nothing at all.
- The set containing all the even integers.
- 1, ... ,4
- 6, 7, 8, ...
- \(\texttt{a}\texttt{a}, \texttt{b}\texttt{a}\).
- \(\varepsilon\)
- \(\{\}\)
- \(\ldots,-4,-2,0,2,4,\ldots\)
Question 4¶
Q4
If the set \(A\) is \(\{1,3,4\}\) and the set \(B\) is \(\{3,5\}\), write down:
| Expression | Meaning |
|---|---|
| \(A \cup B\) | union of \(A\) and \(B\) |
| \(A \cap B\) | intersection of \(A\) and \(B\) |
| \(A-B\) | \(A\) minus \(B\) |
| \(A \times B\) | Cartesian product of \(A\) and \(B\): set of all possible pairs \((a,b)\) where \(a\in A\) and \(b\in B\) |
| \(2^B\) (or \({\cal P} (B)\)) | power set of \(B\): set of all subsets of \(B\) |
Try some Python code:
A = [1,3,4]
B = [3,5]
intersection = [x for x in A if x in B] # or: [x for x in B if x in A]
difference = [x for x in A if x not in B]
product = [(x,y) for x in A for y in B]
For the union:
union = A
for x in B:
if x not in union:
union.append(x)
And for the power set we can use the bits of an index i to decide which elements to include:
powerB = []
sizeB = len(B)
for i in range(2**sizeB):
subset = []
for j in range(sizeB):
if i&(1<<j): # check if the j-th bit of x is set to 1
subset.append(B[j])
powerB.append(subset)
This can be written compactly as follows:
powerB = [[B[j] for j in range(sizeB) if i&(1<<j)] for i in range(2**sizeB)]
NB. You can use Python sets, but the above may help you understand the steps better...
Question 5¶
Q5
Let \(X\) be the set \(\{1,2,3,4,5\}\) and \(Y\) be the set \(\{6,7,8,9,10\}\).
The unary function \(f\colon X\to Y\) and the binary function \(g\colon (X\times Y) \to Y\) are described in the following tables:
- What are the range and domain of \(f\)?
- What are the range and domain of \(g\)?
- What is the value of \(f(2)\)?
- What is the value of \(g(2,10)\)?
- What is the value of \(g(4, f(4))\)
...
Question 6¶
Q6
Write a formal description of the following graph.
The vertices are the "circles", and edges are the "lines".
Some books call verties: nodes.
Question 7¶
Q7
Draw the (undirected) graph \(G = (V, E)\), where
-
Is the graph connected?
-
What about the graph \(G' = (V', E')\), where \(V' = \{1,2,3,4\}\) and \(E' = \{(1,3),(2,4)\}\)?
...
Question 8¶
Q8
Draw the graph \(G = (V, E)\), where \(V = \{1,\ldots,5\}\) and
Build an explicit list of edges: \(E = \{(a, b)\mid a,b \in V \land (a < b < a+3)\}\).
You can use a table to workout the list of edges:
If you still find \(\{(a, b)\mid a,b \in V \land (a < b < a+3)\}\) confusing then try:
V = [1,2,3,4,5]
[(a,b) for a in V for b in V if a<b<a+3]
Or:
V = [1,2,3,4,5]
for a in V:
for b in V:
if a<b<a+3:
print((a,b))
Question 9¶
Q9
The "Icosian Game" is a 19th century puzzle invented by the Irish mathematician Sir William Hamilton (1805--1865). The game was played on a wooden board with holes representing major world cities and grooves representing connections between them (see figure below).
The object is to find a cycle that would pass through all the cities exactly once before returning to the starting point. Can you find such routes?
...