Set Theory (SOB 1)
A = {1, 2, 4, 5, 6}
B = {2, 4, 7, 8}
C = {1, 2, 3, 4, 9}
D = {1, 2, 5, 8}
Question 1.1 Given that A, B, C, D are sets as defined above, draw Venn diagrams to illustrate the following set operations. Write down the set which represents the value of the expression, and shade in the appropriate area on
the diagram. Take note of the brackets, which have their usual meaning
1. (A ∩ B) \ C
2. D ∪ (A ∩ C)
3. B \ (C ∪ D)
Question 1.2 What is the cardinality of the following sets, given that A, B, C, D are the sets defined above:
1. (A ∩ B)
2. (A ∩ B) × (C ∩ D)
Question 1.3 Write out ℘(A ∩ D), where A and D are the sets defined above
Question 1.4 Given that A, B, C, D are sets as defined above, which of the following statements are true:
1. 5 ∈ B
2. {3, 4} ⊂ C
3. {1, 2, 4} ⊆ A
4. B ⊂ B
5. ∅ ⊆ D
2 Relations and Functions (SOB 9)
Question 2.1 For the following homogeneous relations:
• draw the digraph;
• state the domain and range of the relations;
• identify the relation as 1-1,1-many, many-1 or many-many. The signature in all cases is R : {1, 2, 3, 4} ↔ {1, 2, 3, 4}.
1. R = {(1, 1),(2, 1),(3, 2),(1, 2),(4, 1)}
2. R = {(3, 2),(2, 4),(3, 4)}
Question 2.2 In the following, assume that A = {a, b, c, d} and that R: A ↔ A. Determine whether each relation is reflexive, symmetric, and/or transitive (more than one property can apply to a relation). Are any total or onto?
1. R = {(a, b),(b, b),(b, c),(c, c)}
2. R = A × A
3. R = {(a, a),(b, b),(c, c)}
Question 2.3 Given the function f, g and h, all with source and target {1, 2, 3, 4}, defined as follows:
f = {(1, 2),(2, 4),(3, 1),(4, 3)}
g = {(1, 3),(2, 3),(3, 4)}
h = {(1, 1),(2, 2),(3, 3),(4, 4)}
1. Which of f, g, and h are total functions, and which are partial?
2. Evaluate
(a) f(2)
(b) g(3)
(c) f(f(3))
(d) h(g(2))
(e) g(f(2))
3. Is (g ◦ f)(2) = f(g(2))?
3 Regular expressions (SOB 13)
Question 3.1 Here are some informal descriptions of languages. Write down a regular expression to define each language formally. Make a note of any ambiguity in the informal descriptions. The alphabet for all the languages
below is {1, 2, 3}.
1. Any non-empty string that consists of only 3’s.
2. Any string that starts with 12 or 21, following by zero or more 1’s, 2’s, and 3’s in any order.
3. Any non-empty string that ends with a 2.
Propositional Logic (SOB 16)
Question 4.1 Draw up truth tables for each of the following sentences and classify them under the headings tautology, contingency, and contradiction.
1. (P ∧ ¬P) ∧ (Q ∨ R)
2. (¬P ∨ Q) ∧ (P =⇒ (Q ∨ R))
3. Q ⇐⇒ (P ∧ (¬P ∨ (R ∧ Q)))
Question 4.2 Given that P ∧¬P is an inconsistency, without using truth tables, show that ¬(¬P ∨Q)∧¬(¬Q∨P) is an inconsistency
Predicate Logic (SOB 17)
studies(x, Computing)
studies(x, Art)
f first ear(x)
learns(x, Racket)
learns(x, Java)
talks(x, y)
Question 5.1 Using quantifiers and the predicates above, define propositions to express the following:
1. All first-year students studying Computing learn Racket.
2. Some first-year students studying Computing learn Java.
3. First-year students that study Art, don’t learn Racket.
4. Those who learn Racket talk to others that learn Rack
Diagrams to explain simple data structures (SOB 23)
Question 6.1 Build each of the following lists using just cons and the empty list (for instance: ’(1 2 3) is (cons 1 (cons 2 (cons 3 ’()))). Provide a diagram for each of them:
1. (2 4 6 8)
2. ((2 4) (6 8))
3. ((2) 4 6)
4. (2 (4 (6 8)))
Graphs and Trees (SOB 31)
Question 7.1 Letting internal nodes be labelled +, −, ×, draw out the trees for the following expressions:
1. (5 − (2 × 3)) + ((11 + 9) − 17)
2. (110 − (23 − (11 + (14 − 7))))
Question 7.2 In Racket, a graph is represented as a list of pairs. Draw out the following graphs:
1. ’((0 2) (1 1) (1 2) (2 0) (3 2) (3 3))
2. ’((1 2) (3 2) (4 3) (4 1) (1 3))
A graph is strongly connected if from every vertex there is a path to reach every other vertex. For the graphs above, can you say whether they are strongly connected and if not, why not?
