Assignments are to be submitted electronically via a page on the DMTH137’s iLearn site.
Take clear scans or photographs of your hand-written work, combining these into a single PDF or Word file, to be submitted online. Alternatively, work done electronically in Word, or LATEX, may be submitted.
Be aware that work that is illegible, because of poor hand-writing say, or due to poor contrast within the scan or photograph, will not be marked.
- The logical connective “NOT OR”, denoted by ↓, is true only when neither p nor q are true.(a) Write down the truth table for p ↓ q.
(b) Write down the truth table for (p ↓ q) ↓ (p ↓ q). What do you notice?(c) Show that both negation, as well as AND, can be written using only ↓s. - Suppose we are considering all computers at Macquarie. Let P(x) be the statement “x is connected to the network” and let Q(x) be the statement “x has at least 100 Terabytes of storage”. Express each of the following sentences in terms of P (x), Q(x), quantifiers, and logical connectives.
- (a) No computer at Macquarie is connected to the network, and also has at least 100 Terabytes of storage.
- (b) There is a computer at Macquarie which is connected to the network, and has atleast 100 Terabytes of storage.
- (c) There is a computer at Macquarie which is either not connected to the network or has less than 100 Terabytes of storage.
- Let P (x, y) be the proposition x2 = y, where x and y are in the universe of integers. Determine the truth value of each of the following propositions.(a) ∃xP(6,x) (b) ∃xP(x,6) (c) ∀x∃yP(x,y) (d) ∃y∀xP(x,y)
- Prove or disprove each of the following propositions.(a) If n2 is a multiple of 4, then n is a multiple of 4. (b) If n3 is a multiple of 2, then n is a multiple of 2.
- Write down expressions for each of the shaded regions.
Hiden diagram.
- Suppose a relation is symmetric and transitive. Does that automatically make it reflexive? If so, explain why. If not, give a counterexample.
- The following adjacency table for an undirected graph G is missing some information. GExplain how you could detect that it cannot possibly be complete. Correct it by adding the minimal possible extra information, and then determine the number of connected components in the graph, and the vertices in each connected component.
- Determine the number of vertices for a simple graph which has 10 edges, two vertices of degree 4 and all the other vertices of degree 3. Sketch an example of such a graph. Is it planar?
(There may be several non-isomorphic solutions.) - Decide whether the two graphs G1 and G2 are equivalent, given their adjacency matrices as below.and
If not, explain why they cannot be equivalent. If so, draw the graph and label each vertex with the label of the row it corresponds to in the first matrix in blue and the label of the row it corresponds to in the second matrix in red.
