Discrete Mathematics Answers

List the members of the following sets.

1. {x| x is real numbers and x²=1}

2. {x| x is an integer and -4 < x ≤ 3}

Let Q(x, y) denote the statement “x is the capital of y.”

What are these truth values?

a) Q(Denver, Colorado)

b) Q(Detroit, Michigan)

c) Q(Massachusetts, Boston)

d) Q(New York, New York)

1.    a) Recursively define a₀ = 1, a₁ = 3, a₂ = 5 and a_n = 3a_n-2 + 2a_n-3 for n ³ 3. Calculate a_n for n = 3,4,5,6

(4 Marks)

b) Find f(2), f(3), f(4) and f(5) for the following recursive functions.

                 f(0) = 1

f(1) = 2

f(k) = (f(k -1))² - f(k -2) + k²

(4 Marks)

Use Huffman coding to encode these symbols with given frequencies:

a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30.

What is the average number of bits required to encode a character?

(12 Marks)

Write an algorithm to finds the largest of the number a, b and c.

Suppose that a statement of the form ∀xP(x) is false. How can this be proved?

Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people.

a) Someone in your class can speak Hindi.

b) Everyone in your class is friendly.

c) There is a person in your class who was not born in California.

d) A student in your class has been in a movie.

e) No student in your class has taken a course in logic programming.

Construct a combinatorial circuit using inverters, OR gates, and AND gates that produces the output

((¬p ∨¬r) ∧¬q) ∨ (¬p ∧ (q ∨ r)) from input bits p, q, and r.

Prove that for every positive integer ‘n’ : 1𝑋2𝑋3 + 2𝑋3𝑋4 + ⋯ + 𝑛(𝑛 + 1)(𝑛 + 2) =

𝑛(𝑛+1)(𝑛+2)(𝑛+3)

2. Determine the truth value of each of these statements if the domain consist of all integers.

A. ∀n (n+1>n)

B. Ǝn (n = -n)

C. Ǝn (2n = 3n)

D. ∀n (3n ≤ 4n)