1. (5 %)
(a) Use the laws of logic to simplify the statement ((p → ¬q) ∧ p) ∨ q.
(b) Find the truth table for the statement (p ⊕ q) → (q ↑ r).
2. (5 %)
(a) Write the following English sentences in predicate logic. The domains are forms of transport (bus/car/train/walk/...) used to get to university and students who use them. Make sure you define the predicates you use.
i. Some students use the train to get to university.
ii. Some students need to use two forms of transport to get to university.
iii. Every student has some form of transport to get to university.
iv. Some students cannot walk to university.
(b) Given p(x, y) as ”x + y = 6” where x and y in the set {0,1,2,3,4,5,6}, determine whether the following are true or false.
i. p(3,2)
ii. ∀x, p(x, 1)
iii. ∀x, ?x ̸= 0 → ∃y, p(x,y)? iv. ∃y, ∀x, p(x, y)
3. (5 %)
Use a contrapositive proof to show, for integers a and b, that if ab is odd then a and b are odd.
4. (5 %)
GiventhesetsA=Z5 ={0,1,2,3,4},B={2n:n∈Z}andC={x∈Z:−4<x<4}find:
(a) A non-empty subset of B × (C − A) (b) P(C−B)
(c) |A3 ×(B∩C)×C| (d) A∩(B∪C)
5. (5 %)
Suppose that you had a simple connected graph with degree sequence 5,4,4,3,3,2,2,1
(a) Draw such a graph. Label the nodes A,B,C,D,E,F,G,H so that you can refer to them in later parts of this question.
(b) Is it possible to find an Euler path or cycle for your graph? If so write down the path or cycle. If not, can you, by adding a single edge to your graph, create a new graph that does have an Euler path? If so, state clearly the edge and the resulting Euler path. If this is also not possible, explain why.
(c) Is it possible to find a Hamiltonian cycle for your graph? If so write down the cycle. If not, can you, by adding a single edge to your graph, create a new graph that does have a Hamiltonian cycle? If so, state clearly the edge and the resulting Hamiltonian cycle. If this is also not possible, explain why.
6. (5 %)
For this question consider the following two adjacency matrices,
ABCDEFGH ABCDEFGH A00001110 A00110010 B00001110 B00011100 C00001111 C10001010 D00000001 D11001110 E11100000 E01110000 F11100010 F01010010 G11100101 G10110100 H00110010 H00000001
(a) Provide the associated graphs for both of these adjacency matrices. (b) Provide the degree sequences for both graphs.
(c) Prove that one of the graphs is not planar, whilst the other graph is planar. (d) Explain why the graphs are not isomorphic.
7. (5 %)
In this question we will look at a simple application of finding minimal spanning trees. Consider the graph below, which we will assume represents the distances between various towns. The government wants to lay wires to connect these towns in a network. However, digging trenches and laying wires is expensive, so the government wants to know the minimum cost of laying wire whilst still connecting all the places shown on the graph. The cost of laying wire (in thousands of dollars) between specific towns is shown next to each edge. Use Prim’s or Kruskal’s algorithm to construct a minimal spanning tree. State which algorithm you use, show the order in which edges are added, and state at the end what the minimum total cost is.
80 90 95
BCD
70 90 75 85 60 100 70 105
E F 90 G 90 H 85 65 70 85 55 85 105
150 65 90
IJKL
80 80 70 55 65
MN
A
8. (5 %)
Determine the chromatic numbers and chromatic polynomials for both of the graphs below. Hint: the graph on the right may require multiple steps for the chromatic polynomial.