Discrete Mathematics Answers

b) Read Section 2.3.6 (on page 161) of the 8'th edition of Rosen's book on partial functions. Let A and B be finite sets, with |A| = m and |B| = n. Calculate the number of partial functions f: A -> B.

(a) We say that two positive integers a, b are relatively prime if the greatest common divisor of a and b is 1. Let p, q be distinct positive prime numbers such that n=pq. Calculate the number of positive integers not exceeding n that are relatively prime to n.

(b) Find a concise, explicit description for the set A, which is defined by 1 ∈ A, and if a and B are bit strings in A, then aB ∈ A, 0aB ∈ A, a0B ∈ A, and aB0 ∈ A.

(a) Define r(n, m) : N x Z+ ->N be the remainder obtained when dividing m into n. Define the function g: Z+ x Z+ ->Z+ as follows: g(a, b) = b if r(a, b) = 0, and g(a, b) = g(b, r(a,b)) otherwise. Describe what g is calculating, and justify your answer.

For all parts of this problem, let S be a finite set, with |S|=n.
(a) If f:S -> S is onto, does it necessarily follow that f is invertible? Why or why not?
(b) Compute the number of distinct functions g:S -> S that are onto.
(c) Find the number of functions f:S -> S that are not invertible.

Define r(n, m) : N x Z+ -> N be the remainder obtained when dividing m into n. Define a function fm: N x N -> N as follows: f(n, k) = k if r(n, m) = 0, and f(n, k) = f(n-m, k+ 1) otherwise. Describe in terms of a single well-known arithmetic operation what f(n, 0) is computing.

(a) Let S be a set, and define the set W as follows:
Basis: ∅ ϵ W.Recursive Definition: If x ϵ S and A ϵ W, then {x} U A ϵ W. Provide an explicit description of W, and justify your answer.

Determine the truth value of each of the quantified statements below if the domain consists of R.
(a)∃x(x^5 = -1)
(b)∃x(x^6< x^4)
(c)∀x((-x)4=x^4)
(d)∀x(2x > x)

Consider the scenario of Knights and Knaves. You visited that island and met five

people there. Suppose those were A, B, C, D, E [10]

 A: B is a knight.

 B: E is a knight.

 C: A is a knave.

 D: There are at most two knights among us.

 E: No more than...no no no. [then E Looks at C and] Are we not knights and do not

stand for things that are truth and based on jstice? [then E Turns back to you and

said] Welcome dear guest, A and B are the only two knaves among us.

Tell which is knight and which one is knave (Using truth table or rules).