Discrete Mathematics Answers

⋃ 𝐴𝑖

∝

1 and ⋂ 𝐴𝑖

∞

1

a) 𝐴𝑖 = {𝑖, 𝑖 + 1,𝑖 + 2, … }

b) 𝐴𝑖 = {0,𝑖}

c) 𝐴𝑖 = {−𝑖, − 𝑖 + 1, … , −1, 0, 1, … , 𝑖 − 1, 𝑖}

d) 𝐴𝑖 = {−𝑖, 𝑖}

Prove that in a graph G, the sum of the degrees of the vertices is equal to twice the number of edges. Consequently, the number of vertices with odd degree is even

Let P: It is below freezing and Q: It is snowing. What the symbolic form of the "It is not snowing, it is below freezing".

A toy shop has 15 airplanes, 15 buses, 17 trains, and 20 bikes in the stock. a. How many ways are there for a person to take 15 toys home if all the airplanes are identical, all the buses are identical, all the trains are identical and all the bikes are identical? b. How many ways are there for a person to take 15 toys home if all the airplanes are distinct, all the buses are distinct, all the trains are distinct and all the bikes are distinct? c. How many ways are there for a person to take 25 toys home if all the airplanes are identical, all the buses are identical, all the trains are identical and all the bikes are identical?  

A weighted voting system for voters A, B, C, D, and E is given by {35: 29, 11, 8, 4, 2}. The weight of voter A is 29, the weight of voter B is 11, the weight of voter C is 8, the weight of voter D is 4, and the weight of voter E is 2.

a. What is the quota?

b. What is the weight of the coalition {A, D, E}?

c. Is {A, D, E} a winning coalition?

d. Which voters are critical voters in the coalition {A, C, D, E}?

e. How many coalitions can be formed?

f. How many coalitions consist of exactly two voters?

State the Pigeonhole Principle. Prove that if six integers are selected from the set

[3,4,5,6,7,8,9,10,11,12] there must be two integer whose sum is fifteen.

a particular algorithm increases in time as the number of operations n increases.

Suppose the time complexity of this algorithm is given by:

f(n)=4n²+5n²*log(n)

Show that f(n) is O(g(n)) for g(n) = n³

6. (a) Draw the logic circuit for the following expression: AB + A(B+C)

(b) Simplify the expression in 6(a) by using the rules of Boolean algebra provided in (5). (c) Draw the simplified logic gate circuit derived in (b)

Prove that if 10 points are placed in a 3cm by 3cm squre board than two points must be at least √2

cm apart.