Discrete Mathematics Answers

(a) Use Fermat’s little theorem to compute: 4101 mod 5, 4101 mod 7, 4101 mod 11.

(b) Use your results from part (a) and the Chinese Remainder Theorem to compute

4

101 mod 385. (note that 385 = 5 × 7 × 11).

(a) Find the inverse of 19 modulo 141, using the Extended Euclidean Algorithm.

Show your steps.

(b) Solve the congruence 19x ≡ 7 (mod 141), by specifying all the integer solutions x

that satisfy the congruence.

≡

Let R={1,1),(1,2),(2,1), (2,1), (3,3), (4,1), (5,1)} define on set A= {2,3,4,5,6}

1. Consider the K-Maps given below. For each K- Map

i. Write the appropriate standard form (SOP/POS) of Boolean expression.

ii. Design the circuit using AND, NOT and OR gates.

iii. Design the circuit only by using

• NAND gates if the standard form obtained in part (i) is SOP.

• NOR gates if the standard form obtained in pat (i) is POS.

AB/C

0

1

00

1

0

01

1

1

11

1

0

10

0

1

2. Produce truth tables for given Boolean expressions.

i. |A|.|B|.C + A.|B|.|C| + A.B.C + |A|.B.|C|

ii. (A+|B|+C).(A+B+C).(|A|+B+|C|)

Define a binary relation P from R to R as follows: for all real numbers x and y,

(𝑥, 𝑦) ∈ 𝑃 ⇔ 𝑥 = 𝑦^2

. Is P a function? Explain.

4. Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.

a) {(0, 0), (1, 1), (2, 2), (3, 3)}

b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}

e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}

5. Which relation on the set {1, 2, 3, 4} is an equivalence relation and contain {(1, 2), (2, 3), (2, 4), (3, 1)}.

6. Find the transitive closures of the relation {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)}

on the set {1, 2, 3,,4}.

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

3. Give an example of a predicate P(x,y) such that ∃x∀yP(x,y) and ∀y∃xP (x, y) have different truth values.

5. Let p be the proposition “I will solve every question in this assignment” and q be the proposition “I will be fully prepared for upcoming topics” Express each of these as a combination of p and q. a. I will be fully prepared for upcoming topics only if I will solve every question in this assignment. b. I will be fully prepared for upcoming topics and I will solve every question in this assignment. c. Either I will not be fully prepared for upcoming topics or I will notsolve every question in this assignment. d. For me to be fully prepared for upcoming topicsit is necessary and sufficient that I solve every question in this assignment