WMAT1007 Discrete Mathematics Assignment Answer

Construct the Truth Table for the Proposition (p ↔ (¬(r ∨ q))) ?→ (r ← p), Include ALL Columns in Your Working.

To construct the truth table for the proposition (p ↔ (¬(r ∨ q))) ?→ (r ← p), we’ve 2^3 = 8 possible combinations:. Therefore, the truth table is:

p	q	r	¬(r ∨ q)	p ↔ ¬(r ∨ q)	r ← p	(p ↔ ¬(r ∨ q)) ↔ (r ← p)
T	T	T	F	F	T	T
T	T	F	F	F	F	T
T	F	T	F	F	T	T
T	F	F	T	T	F	T
F	T	T	F	F	T	T
F	T	F	F	F	F	T
F	F	T	F	F	T	T
F	F	F	T	F	T	F

Simplify the Proposition Below Using the Laws of Logic Seen in Class.

(x→y)→(x∧y), we can use logical equivalences and simplification rules.

Implication Simplification:

A→B is equivalent to ¬A∨B.

Using this equivalence, we can rewrite the original proposition as

(¬(x→y))∨(x∧y)

By  De Morgan's Law’s: (¬(¬x)∧¬y)∨(x∧y)

Or, x∧¬y)∨(x∧y) (¬(¬x) is equivalent to x.)).

By distributive law: x∧(¬y∨y)

Since ¬y∨y is always true, the final simplified proposition is:

x∧True (A∨¬A is always true (tautology).)

And, x∧True is simply x.

So, the simplified form of (x→y)→(x∧y) is x.

Given the sets A = Z5, B = {4n + 2 : n ∈ Z}, C = {x ∈ Z : −5 ≤ x ≤ 6} use correct set notation to find:

a). To create a subset of A × C with exactly 5 elements, we can choose 5 ordered pairs from the Cartesian product. The set would look like this: { (0, -5), (1, -4), (2, -3), (3, -2), (4, -1) }

b). To find A - B, we need to first determine the elements of A - B, which are the elements that are in A but not in B.

A = {0, 1, 2, 3, 4} B = {4n + 2 | n ∈ Z} = {..., -10, -2, 2, 6, 14, ...}

A - B = {0, 1, 2, 3, 4} - {2} = {0,1, 3,4}

Now, let's find the power set of A - B, which is all possible subsets of {1, 2, 3}: P(A - B) = { {}, {0} {1}, {3},  {4},{0, 1}, {1, 3}, {1, 4}, {0,4} , {0,3}  {3,4},  {0,1,3}, {0,3,4}, {1,3,4},  {1,0,4}, {0,1,3,4}}

c).  Since C is the set of integers from -5 to 6, inclusive, C has 12 elements. So, |P(C)| is the number of subsets of a 12-element set, which is 2^12 = 4096.

A^6 represents the Cartesian product of A with itself 6 times. Since A has 5 elements, A^6 will have 5^6 = 15625 elements.

|P(C) × A^6| is the cardinality of the Cartesian product of P(C) and A^6, which is 4096 * 15625 = 64,000,000.

d).  C¯=Z-C=Z-{-5,-4,-3,-2,-1,0,1,2,3,4,5,6}

  (B ∪ A).= {..., -10, -2, 0,1, 2, 3,4, 6, 14, ...}

Therefore, C¯ ∩ (B ∪ A) = Z-{-5,-4,-3,-2,-1,0,1,2,3,4,5,6}  ∩  {..., -10, -2, 0,1, 2, 3,4, 6, 14, ...}

C¯ ∩ (B ∪ A) =  {..., -18,-14 ,-10,14, 18, 22 ...}

e) Draw a Venn diagram using the sets A, B, and C shading the region corresponding to the set in part d.

Here, is the Required Venn Diagram:

 

For This Question Consider the Following Three Graphs

a). Provide the degree sequence for all three graphs.

Degree sequence of G1 is: 4,4,3,3,2,1,1

Degree sequence of G2 is: 4,4,3,3,3,2,1

Degree sequence of G1 is: 4,4,3,3,3,2,1

b). Prove G1 is not isomorphic to either G2 or G3

From the two graphs, it is clear that G1 has only one vertex of degree three while both G2 and G3 have three vertices of order 3. This shows that G1 is not isomorphic to either of G2 ORG3 as for two graphs to be isomorphic both need to have the same number of vertices with the same degrees.

c) Determine whether G2 is isomorphic to G3. Either describe a relabelling of G2 that demonstrates the isomorphism or give a justification for why the graphs are not isomorphic

The graph G2 is not isomorphic to G3. As we can clearly see from the graphs, G2 has a vertex namely ”y” of degree 4 connected to three vertices of degree 3 each and one vertex of degree 4. But in G3 both the 4-degree vertices are directly connected to the vertex of degree 2 showing that G2 is not isomorphic to G3.

d). It is possible to obtain a graph isomorphic to G2 by adding a single edge to G1. Identify the two vertices this added edge must connect in G1. You do not need to provide justification for your answer.

No, it is not possible.

e). Do any of the graphs G1, G2 or G3 admit an Euler path? Either describe an Euler path for one of these three graphs, or explain why none of them admit an Euler path.

None of the graphs G1, G2, and G3 admit the Euler path because each graph has vertices of odd degrees and it creates a problem that when an incoming edge is an incident on odd degree vertex, the kit doesn’t have a path to leave that vertex.

f). Do any of the graphs G1, G2 or G3 admit a Hamiltonian cycle? Either describe a Hamiltonian cycle for one of these three graphs, or explain why none of them admit a Hamiltonian cycle.

None of the graphs G1, G2, and G3 admits Hamiltonian cycle because each graph has a pendent vertex i.e, a vertex of degree one and a pendent vertex can never form Hamiltonian cycle in a graph

Find a minimal spanning tree of the graph below using either Prim’s or Kruskal’s algorithm.

We find the minimal spanning tree of the given graph by Kruskul’s algorithm in which we sort all the edges in the graph in the non-decreasing order of their weights and then start with the smallest weight for iteration. For each edge, ff adding the edge does not create a cycle, we include it in the minimal spanning tree.

We list to make the form the minimal spanning tree in this way:

D→K with weight 10

A→B with weight 12

E→B with weight 13

G→D with weight 14

F→J with weight  15

G→L with weight 16

I→F with weight 17

B→C with weight 19

D→H with weight 22

J→G with weight 23

F→C with weight 29

Therefore, the total weight of the minimal spanning tree is: 190

The highlight of the resulting minimal spanning tree is:

Consider the numbers 531 and 411

a). We use the Euclidean algorithm to find the gcd of 531 and 411 as follows:

531 = 411 * 1 + 120

411 = 120 * 3 + 51

120 = 51 * 2 + 18

51 = 18 * 2 + 15

18 = 15 * 1 + 3

15 = 3 * 5 + 0

The gcd is 3. So, g = gcd(531, 411) = 3.

b). What is the condition that a number d must satisfy so that the equation below has integer solutions? 531x + 411y = d

For the equation 531x + 411y = d to have integer solutions, the gcd of 531 and 411 must be divided d. That is to say, that d must be a multiple of the greatest common divisor (gcd) found in part (a), which is 3. So, d must be a multiple of 3.

c). Completing the table from part 5.(a), use the extended Euclidean algorithm to find an integer solution (x, y) = (x0, y0) for the equation 531x + 411y = g, where g = gcd(531, 411).

Now, we'll use the extended Euclidean algorithm to find an integer solution (x0, y0) for the equation 531x + 411y = g, where g = 3.

Starting from the last non-zero remainder:

3 = 18 - 15 * 1

Now, work backward:

3 = 18 - (51 - 18 * 2) * 1 

3 = 3 * 18 - 51 

3 = 3 * (120-51*2) - 51 

3 = 3 * 120 - 51 * 7

3 = 3 * 120 -  (411 - 120 * 3) * 7

3 = (3 * 120)*8 - 411 *7

3 = -7 * 411 + 24* (531-411*1)

3=531*24+411*(-31)

So, we have found (x0, y0) = (24, -31) as a solution to 531x + 411y = 3.

d) Use your solution (x0, y0) for part 5.(c) to find a solution t = t0 to the modular equation below. 411t ≡ 9 (mod 531)

from part c), we’ve: (x0, y0) = (24, -31)

Now, given congruence is :

411 t ≡ 9 (mod 531) 

Or, 411t ≡ 3 * (531*24+411*(-31)) (mod 531)

Or,  411t ≡ 3 * 531+411*(-91)  (mod 531)

Since 531 * 3 is a multiple of 531, it is congruent to 0( mod 531)

Therefore, 411t ≡ -91* 411 (mod 531)

Now, we can find t0 by dividing both sides by 411 (which is coprime to 531):

t ≡ -91 (mod 531)

So, a solution to the modular equation 411t ≡ 9 (mod 531) is t0 = -91.

Q6

a). To convert the decimal number 95653810 to hexadecimal, we use the following steps:

95653810 ÷ 16 = 5978363 with a remainder of 2 (2 in hexadecimal is also 2).

5978363 ÷ 16 = 373647 with a remainder of 11 (11 in hexadecimal is B).

373647 ÷ 16 = 23352 with a remainder of 15 (15 in hexadecimal is F).

23352 ÷ 16 = 1459 with a remainder of 8 (8 in hexadecimal is 8).

1459 ÷ 16 = 91 with a remainder of 3 (3 in hexadecimal is 3).

91 ÷ 16 = 5 with a remainder of 11 (11 in hexadecimal is B).

5 ÷ 16 = 0 with a remainder of 5 (5 in hexadecimal is 5).

Now, we have the remainders in reverse order, so the hexadecimal representation of 95653810 is 5B38F2.

b) To convert the decimal number 382410 to binary, we use the following steps:

382410 ÷ 2 = 191205 with a remainder of 0.

191205 ÷ 2 = 95602 with a remainder of 1.

95602 ÷ 2 = 47801 with a remainder of 0.

47801 ÷ 2 = 23900 with a remainder of 1.

23900 ÷ 2 = 11950 with a remainder of 0.

11950 ÷ 2 = 5975 with a remainder of 0.

5975 ÷ 2 = 2987 with a remainder of 1.

2987 ÷ 2 = 1493 with a remainder of 1.

1493 ÷ 2 = 746 with a remainder of 1.

746 ÷ 2 = 373 with a remainder of 0.

373 ÷ 2 = 186 with a remainder of 1.

186 ÷ 2 = 93 with a remainder of 0.

93 ÷ 2 = 46 with a remainder of 1.

46 ÷ 2 = 23 with a remainder of 0.

23 ÷ 2 = 11 with a remainder of 1.

11 ÷ 2 = 5 with a remainder of 1.

5 ÷ 2 = 2 with a remainder of 1.

2 ÷ 2 = 1 with a remainder of 0.

1 ÷ 2 = 0 with a remainder of 1.

Now, we have the remainders in reverse order, so the binary representation of 382410 is 1011110011000001010.

C)

To convert the octal number 354768 to binary without converting it to decimal first, we directly convert each octal digit to a group of three binary digits (bits). That is:

3 in octal is 011 in binary.

5 in octal is 101 in binary.

4 in octal is 100 in binary.

7 in octal is 111 in binary.

6 in octal is 110 in binary.

8 in octal is 1000 in binary.

Combine these binary groups together:  011 101 100 111 110 1000. So, the binary representation of the octal number 354768 is 0111011001111101000.

d) To multiply the binary numbers 110112 and 100102, we use binary multiplication just like we do with decimal numbers.

11011*10010= 100001110

Q7 Consider the following proposition: P = For all integers a and b, if 4 doesn’t divide abc, then a is odd or b is odd.

(a) Let's define the following predicates:

• p(x, y): "x divides y" (this is a primitive predicate).

• O(x): "x is odd."

Therefore , P = ∀a ∀b [A(a, b, c) → (O(a) ∨ O(b))]

(b) The contrapositive of proposition P, stated in natural language, is as follows:

For all integers a and b, if neither a is odd nor b is odd, then 4 divides abc.

(c) To prove that P is true by proving the contrapositive, we need to show that if neither a is odd nor b is odd, then 4 divides abc.

Assume ¬O(a) and ¬O(b). This means that both a and b are even integers. We can represent them as a = 2k and b = 2m, where k and m are also integers.

Now, let's look at the right-hand side of the contrapositive: p(4, abc). Since a = 2k and b = 2m, we can rewrite abc as (2k)(2m)c = 4(kmc). This clearly shows that 4 divides abc, as it can be factored out. Hence the result follows.

Q8 Consider the boolean function f(x, y, z) = (x + ¯y)(y + ¯z) + y(x + yz¯)

Table of values for the function f(x,y,z)

A).

X	Y	Z	f(x,y,z)
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

b).

Conjunctive Normal Form (CNF): A CNF expression is a product of sums where each sum term is a combination of literals (variables or their negations).

For f(x, y, z), we can represent it in CNF as follows:

f(x, y, z) = (x + ¬y)(¬y + ¬z)(y + xz)

Disjunctive Normal Form (DNF): A DNF expression is a sum of products where each product term is a combination of literals (variables or their negations).

For f(x, y, z), we can represent it in DNF as follows:

f(x, y, z) = (x + ¬y + ¬z)(¬y + x + z)(y + ¬x)(y + ¬z)

c). 

To obtain a minimal sum-of-products expression for f(x, y, z), we can use the Quine-McCluskey method or a Karnaugh map. Let's use the Quine-McCluskey method.

First, write down all the minterms where f(x, y, z) = 1 based on the given truth table: M(0,1,3,4)

Group these minterms to find the prime implicants:
Group 1: M0, M4 (These minterms only differ in the value of 'x' which is not a prime implicant) Group 2: M1, M3 (These minterms only differ in the value of 'z' which is not a prime implicant)

Write down the prime implicants:
P1: ¬y P2: x

Now, use these prime implicants to form the minimal sum-of-products expression:

f(x, y, z) = P1 * P2 f(x, y, z) = (¬y) * (x) f(x, y, z) = ¬yx

So, the minimal sum-of-products expression for f(x, y, z) is ¬yx.

This is the simplest expression for the given boolean function.

Q9): Consider the following weighted graph:

We use Dijkstra's algorithm to find shortest path as follows:

Selected vertex	A	B	C	D	E	F	G	H	I	J	K	L
	0	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	∞
A	0	12	∞	∞	18	∞	∞	∞	∞	∞	∞	∞
B	0	12	31	∞	18	37	∞	∞	∞	∞	∞	∞
E	0	12	31	∞	18	37	∞	∞	35	∞	∞	∞
C	0	12	31	45	18	37	34	∞	35	∞	∞	∞
G	0	12	31	45	18	37	34	∞	35	∞	54	∞
I	0	12	31	45	18	37	34	∞	35	59	54	∞
F	0	12	31	45	18	37	34	∞	35	52	54	∞
D	0	12	31	45	18	37	34	67	35	52	54	∞
J	0	12	31	45	18	37	34	67	35	52	54	∞
K	0	12	31	45	18	37	34	67	35	52	54	75
L	0	12	31	45	18	37	34	67	35	52	54	75

a). NOW, we,ve:

Vertex added	Previous vertex	Weight of Shortest path from A to vertex added
A	-	0
B	A	12
C	B	31
D	C	76
E	A	18
F	B	49
G	C	65
H	D	98
I	E	53
J	F	64
L	K	106

So the shortest path tree from A to L goes like this:

A→B→C→G→K→L

b). As from the previous part we’ve seen that shortest path from A to L is : A→B→C→G→K→L

And the minimum weight of this path is:106

Q10). Consider the function f : Z6 → Z8 given by f(x) = 3x − 4 (mod 8).

a). To create a table of values for f(x) for each x ∈ Z6, we will calculate f(x) for each value of x in Z6:

For x = 0: f(0) = 3(0) - 4 (mod 8) = -4 (mod 8) = 4

For x = 1: f(1) = 3(1) - 4 (mod 8) = -1 (mod 8) = 7

For x = 2: f(2) = 3(2) - 4 (mod 8) = 2 (mod 8) = 2

For x = 3: f(3) = 3(3) - 4 (mod 8) = 5 (mod 8) = 5

For x = 4: f(4) = 3(4) - 4 (mod 8) = 8 (mod 8) = 0

For x = 5: f(5) = 3(5) - 4 (mod 8) = 11 (mod 8) = 3

So, the table of values for f(x) for each x in Z6 is:

X	f(x)
0	4
1	7
2	2
3	5
4	0
5	3

b). From the table in part (a), we can see that for every distinct value of x in Z6, the corresponding values of f(x) in Z8 are also distinct,  which suffices to a function being injective Therefore, f(x) is injective.

c). From the table in part (a), we can see that every element of Z8 has a preimage in Z6, which suffices to a function being surjective. Therefore, f(x) is surjective.

d). We have already seen that f(x) is injective and surjective in parts (b) and (c). Therefore, f(x) is bijective.

e). Since f(x) is bijective, we can find its inverse, f?¹(x). The inverse function is defined such that f(f?¹(x)) = x for all x in the domain. To find the inverse, we'll proceed as follows:

f^(-1) : Z8 → Z6, i.e, f^(-1) is a function from  Z8 to Z6.

We can express the inverse function as follows:

f^(-1)(y) = (3^(-1) * (y + 4)) (mod 6); where, 3^(-1) represents the modular multiplicative inverse of 3 modulo 6. We find the  3^(-1) by following method:

3 * a ≡ 1 (mod 6)

We have a = 5 is the modular multiplicative inverse of 3 modulo 6.

So, the inverse function is:

f^(-1)(y) = (5 * (y + 4)) (mod 6).

You Might Also Like:- 

• Communication Science & Maths Assignment Sample
• Make Math Assignments Simple 
• Mathematics Assignment Help