Solved: Suppose T(n) and f(n) and two functions. Write asymptotic notations (Ο, Ω, Θ) using these two functions and explain the growth rate of these functions in each notation.

(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…

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.

How many ternary strings (i.e., the only allowable characters are 0, 1, and 2) of length 15 are there containing exactly four 0s, five 1s, and six 2s?

How many solutions are there to the inequality x1+x2+x3+x4≤15, where x1,x2,x3, and x4 are nonnegative integers? Hint: Introduce an extra variable x5 and consider x1+x2+x3+x4+x5 = 15.

Suppose a friend asks you to list out all relations on the set S = {n|n ∈ Z+ and n≤1000}. Find the number of number of relations on S. Is your friend making a reasonable request?

Let R be a relation from A to B. Both sets are finite, with |A|=n and |B|=m. Define the complementary relation "R bar" as follows: R bar={(a, b)|(a,b)∈R} Calculate |R bar|.

(a) If A={1,2,3,4}, calculate the number of reflexive relations on A. (b) If B={1,2,3,4,5}, calculate the number of symmetric relations on B.

Let S be a finite set, with |S|=n. If the bit matrix MR representing R contains exactly r entries that are 0, how many entries of MRbar are 0? Note: "MRbar" is supposed to be just like MR, which you should know has R as a s…

Let S be a finite non-empty set. How many relations on S are simultaneously an equivalence relation and a partial order? Justify your answer.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2 (a) Calculate the following: (i)A(1,0) (ii)A(0,1) (iii)A(1,1) (iv)A(2,2).

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2 Show that A(m, 2) = 4 whenever m≥1. Hint: Induct on m.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2 Show that A(1, n) = 2^n whenever n≥1. Hint: Induct on n.

(a) Is every total ordering a lattice? Why or why not?

(b) Let S={1,2,3}, and define the poset (P(S),⪯) by A⪯B if and only if A⊆B. Verify that this poset is a lattice. Is it a total ordering? (c) Using your work in part (b), is every lattice necessarily a total ordering?

Let P1={B0, B1, B2} be a partition of Z, where B0={3n|n ∈ Z}, B1={3n+ 1|n ∈ Z}, and B2={3n+ 2|n ∈ Z}. Describe the equivalence relation R1 corresponding to P1.

Let S be the set of ternary strings (i.e,. strings containing only the characters 0, 1,and 2), and let R be an equivalence relation on S. Suppose the collection of equivalence classes for R is P={Bi|i ∈ N}, where a typical representat…

Let R be an equivalence relation on Z, which has P={{±i}|i ∈ N} as its collection of equivalence classes. Describe the equivalence relation R.

If In= (-1/(5n),1/(5n)) where n≥1 is an integer and In represents an interval on the real number line, find U(n=1 to infinity) In and ∩(n=1 to infinity) In.

Let Bn={(x, y)|0≤x≤n and 0≤y≤n}, where n is a nonnegative integer. Find U(n=0 to infinity)Bn and ∩(n=0 to infinity)Bn.

Let C={A1, A2, ..., An} be a collection of finite sets that are pairwise disjoint. Further suppose that |Ai|=i. Compute |U(i=1 to n)Ai|, and write your answer in the simplest closed form possible.

a) Show that a subset of a countable set is countable.

If X,Y, and Z are sets and |X|=|Y| and |Y|=|Z|, show that |X|=|Z|. Note that we are not assuming that the given sets are finite.

Let A be a countable set, and B is another set. Assume further that there exists an onto function f:A->B. Is B necessarily countable? Provide a full justification for your answer.

Write following using summation n(n-1)+(n-2)++.....+1

Define a function fm: N x N ->N as follows: fm(n, k) =k if 0 ≤ n < m, and fm(n, k) =fm(n-m, k+1) otherwise. Describe in terms of a single well-known arithmetic operation what fm(n, 0) is computing.

Consider the statement: The art show was enjoyable but the room was hot. a) Use a variable to represent each basic statement in the given statement. b) Use the variables and logical operators to represent the statement in symbolic for…

Show that A=B A = {1,2,3} B ={n|n∈Z+ and n^2<10}

Let A = {2,3,4} , B = {6,8,10} , and C = {a,b} True or False? (i) 4R6 (ii) 4R8 (iii) (3,8) ∈ R (iv) (2,10) ∈ R (v) (4,12) ∈ R

There are 18 mathematics majors and 325 computer science majors at a college. a) In how many ways can two representatives be picked so that one is a mathematics major and the other is a computer science major? b) In how many ways can …

Q 4: Find the Number of Mathematics students in a university taking at-least one of the language Mandarin, English and Japan Give the following data: 65 study Mandarin 45 study English 42 study Japanese 20 Study Mandarin and English …

Q. Construct the truth tables for (p & q here are not above statement) a) p V ~q b) ~p V ~q c) q -->p d) ~(p-->q)-->r

how propositional logic can be used in Boolean search? Give detail answer with an example of web page searching.

The generating function of the sequence {1,2,3...n..} is (1-z)².

6. Use truth tables to determine whether the argument form is valid. [5 Marks] a. There is an undeclared variable or there is a syntax error in the ﬁrst ﬁve lines. b. If there is a syntax error in the ﬁrst ﬁve lines, then there is a m…

∀x∃y(x + y = 2 ∧ 2x − y =1

A palindrome number is a number that is read similarly backwards. How many possible 5-digit palindromic numbers are there? A. 608 B. 648 C. 688 D. 728

A keyboard has its keys removed. If the last line of the letters were jumbled, how many ways can I rearrange it so that consecutive letters are beside each other? A.120 B. 144 C. 156 D.196

Five different colored flags can be hung in a row to make a coded signal. How many signals can be made if a signal consists of the display of one or more flags? A. 11 B. 13 C. 15 D. 17

Make negation of the following statements. I4) All students have taken a course in mathematics. 15) Some students are intelligent, but not hardworking

In an engineering class there are 15 students taking chemistry,20 students taking mathematics. Of these students,10 are taking both chemistry and mathematics.How many students are taking either chemistry or mathematics? Expert's answer

Alice decides to set up an RSA public key encryption using the two primes p= 31 and p= 41 and the encryption key e= 11.You must show all calculations, including MOD-calculations using the division algorithm! Bob decides to send the me…

1. Discuss two real world binary problems in two different fields using applications of Boolean Algebra.

Write the following sets in the roster/tabular form: a. G = {x : x ∈ N, 5 < x < 12} b. H = {x : x is a multiple of 3 and x < 21} c. I = {x : x is perfect cube 27 < x < 216} d. J = {x : x = 5n - 3,n ∈ W, and n < 3}

prove with inductions that n^2+n divisible by 2

Prove that (1 * 2) + (2 * 3) + (3 * 4) + (4 * 5) + ....+ n (n + 1) = n (n + 1) (n + 2) / 3 for n positive integers

In a survey, 2000 people were queried if they read India Today or Business Times. It was found 1200 read India Today, 900 read Business Times and 400 read both. How many read at least one magazine

Suppose that the statement p→ ¬q is false. Find all combinations of truth values of r and s for which (¬q→r)∧(¬p∨s) is true.

Let p and q be the propositions ”Swimming at the Sarıyer shore is allowed” and ”Sharks have been spotted near the shore”, respectively. Express each of these compound propositions as an English sentence. (a) ¬p ∨ q (b) p ⇒ ¬q (c) p ⇔ …

Determine the truth values of each proposition below. (a) 1 + 1 = 3 if and only if 2 + 2 = 3. (b) If 1 + 1 = 2 or 1 + 1 = 3, then 2 + 2 = 3 and 2 + 2 = 4. (c) If squirrels play badminton, then cats can’t fly.

If p is true, q, r, and s are false, find the truth value of the proposition. ¬(¬𝑝 ∨ 𝑞) ∨ ¬((𝑝 ∧ ¬𝑟) → ¬𝑠)

There are 7 groups in a picnic who has brought their own lunch box, and then the 7 lunch box are exchanged within those groups. Determine the number of ways that they can exchange the lunch box such that none of them can get their own.

How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of a particular suit are chosen

There are 7 groups in a picnic who have brought their own lunch box, and then the 7-lunch boxes are exchanged within those groups. Determine the number of ways that they can exchange the lunch box such that none of them can get their …

Draw the Hasse diagram for (i) Pi = {1, 2, 3, 4, 12} and < is a relation such that x < y if x divides y.

Let P = {1,2,3,4} and R = {(1,1), (2,1), (1,2), (2,2), (3,2), (3,4), (4,3), (4,4)} which is a relation on P. Represent this relation as a directed graph. Check whether this relation is an equivalence relation or not.

For discrete structures there are n exams to check and there are k graders. To guarantee a high quality of grading, every exam may be checked by any number of graders (but always at least by one grader). This means that summed all tog…

An orientation of a graph G = (V,E) is any directed graph G'= (V,E) arising by replacing each edge {u, v} belonging to E, by the directed edge (u, v) or by the directed edge (v, u). Show that for every planar graph there is an orienta…

Draw the De Bruijn graph for 2-tuples with digits 0,1,2, and 3. Make sure to add matching labels to all vertices and edges.

A group of 21 students participates in a discrete mathematics competition. There are Q questions that have to be answered. For each question exactly 4 students are assigned to work together, while the others take a short break. The qu…

Find the sum of product expansion of the Boolean function f(x,y,z) = (x+z)y

For discrete structures there are n exams to check and there are k graders. To guarantee a high quality of grading every exam may be checked by any number of graders (but always at least by one grader). This means that summed all toge…

Let ρ be a relation on a set A. Define ρ −1 = { | ∈ ρ}. Also for two relations ρ, σ on A, define the composite relation ρ ◦ σ as (a, c) ∈ ρ ◦ σ if and only if there exists b ∈ A such that ∈ ρ and ∈ σ. Prove the following assertions (a…

the number of combinations of five objects taken two at a time is?

Show that the propositions pi, p2, p3, and p4 can be shown to be equivalent by showing that p1 ↔ p4, P2 ↔ P3, and p1 ↔ p3.

Show that ~ (p → q) and p ∧~q are logically equivalent. (Hint: you can use a truth table to prove it or you apply De Morgan law to show the ~(p → q) is p ∧~q.

The Mathclub, VIT-AP wants to conduct a group event for its members. So the club president has to fix the group size the event. When he tries to fix the size to be 5 members in each group, 4 members are left; when he tries to fix the …

Make a truth table for the given expression. 12. (~p∧q) ∨ (p∧~q) 13. (p∧~q) ∨ r 14. ~[(p∧~q) ∨ ~p] 15. (p∨q) ∧ ~(~q∧r) 16. (~p∧q) ∨ (~p∨q) 17. ~[(p∨q) ∧ ~q]

Show that among 2000 student in a school, at least six were born on the same day of the leap year

Using propositional-formula and logical connectives, convert these sentences into symbolic form. No doctors are enthusiastic; You are enthusiastic. Therefore, you are not a doctor Dictionaries are useful; Useful books a…

translate the statement "The product of any two positive integers is always positive"into logical expression(using Nested Quantifiers)

Check whether the relation defined by{(a,b)}| a is cousin of b}defined on the sets of all human being is an equivalence or not?

He relation (a,b) such that "a" and "b" have the same age ,is defined on the sets of all people.Is it equivalent relation?

Indian Cricket team was doing catching practice .The fielding coach informed then that they will throw ball to 4 other players done this ,but others did not throw any ball to catch.how many players received the ball including first pl…

If we have two graph G = (V, E) and G0 = (V, E0 ) on the same set V of vertices we call the union G ∪ G0 the graph (V, E ∪ E0 ). Next we have two claim about the chromatic number χ(G ∪ G0 ) of G ∪ G0 .Prove that χ(G∪G0 ) ≤ χ(G)∗χ(G0 )…

An orientation of a graph G = (V, E) is any directed graph G0 = (V, E0 ) arising by replacing each edge {u, v} ∈ E by the directed edge (u, v) or by the directed edge (v, u). Show that for every planar graph there is an orientation su…

Are these system specifications consistent? ”The file system is not locked only if new messages will be queued. If the file system is not locked, then the system is functioning normally, and conversely. For new messages are not queued…

USING MATHEMATICAL INDUCTION P(n)=1+22+2n+........+2n= 2n+1 - 1

A town has two type of people Knave always speak lie and knative always speak truth, you meet a group of six people A, B, C, D, E and F they communicate with you as following, A Said: All are the knative . B Said: Atleast three ar…

A binary operation € on three variables A, B and C define as return true if at least two true return us true then prove that OR operation on three variable is equivalent to which of the following ? A€(B€C) 2) A€(B€¬C) 3) A€(…

How many Combinations of bit strings length 9 have: a) exactly three 0s? b) at least seven 1s?

how many three letter words can be formed by the word letter EQUATION

In a class of 200 students,70 offered physics,90 chemistry,100 mathematics while 24 did not offer any of the three subject,23 student offered physics and chemistry,41 chemistry and mathematics while 8 offered all the three subjects.Ho…

d)Out of 300 students taking discrete mathematics ,60 take coffee, 27take cocoa,36 take tea,17 take tea only,47 take chocolate only,7 take chocolate and cocoa,3 take chocolate, tea and cocoa,20 take cocoa only ,2 take tea, coffee and …

Construct the switching network of the given compound statements. Then, construct another switching network of the equivalent statement by applying the laws of logic: 1. p v (~p v q) v (p v ~q) ] ^ ~q 2. (p → q) ^ (p ↔ q)

Simplify the following expressions using laws of logic and put what law of logic did you use or apply. p v ~(~p --> q) [(p --> q)^ ~q] --> ~p [(p v q) ^ (p --> ~r) ^ r ] --> q (p v ~q) ^ (p v q) 5. ~[p --> ~(p ^ q)]

Let S be the following statement. “If it is raining, then the ground is wet.” Translate the S into symbol State in English the converse of S State in English the contrapositive of S

Simplify the following expressions using laws of logic: p v ~(~p --> q) [(p --> q)^ ~q] --> ~p [(p v q) ^ (p --> ~r) ^ r ] --> q (p v ~q) ^ (p v q) 5. ~[p --> ~(p ^ q)]

Construct two different assignments that are functions. The functions should be represented by means of ordered pairs graphically. Construct domain, codomain and range(image) of each function.

Writing set into a form of {x | P(x) } 1. {2,4,6,8,10} 2. {a,e,i,o,u} 3. {1,8,27,64,125} 4. {-2,-1,0,1,2} If A = {3,7,12} Find: 5. |A| 6. P(A) 7. | P(A) |

Yesterday, Allan, Berto, and Carlo are playing guess that day. Berto and Carlo gives Allan clues and fake clues. Berto said today is Friday, but Carlo said its Saturday. Allan asked what day is it tomorrow? Carlo said its Monday while…

Determine whether each of these functions is a bijection from R to R. f(x)=2x+1 f(x)=x^2+1

Write the set in the form { x | P(x) } 1. {2, 4, 6, 8, 10}

. Identify the contrapositive of the following statement. If x = 5, then x + 8 = 13

Prove the validity of the arguments using rules of inference. { (p→q) ^ [ q → (r ^ s) ] ^ (p ^ w) ^ [~r v (~w v u) ] } → u

List the members of these sets: (a) A={ x∣x is a real number ∋ x2=1} (b) B={ x∣x is a positive integer less than 100 } (c) C={ x∣x is the square of an integer and x <100 } (d) D={ x∣x is an integer ∋ x2=2 }

Show that {1, 2, 3, 4, . . .} and {2, 4, 6, 8, . . .} have the same cardinality. Hint: find a mapping and show it is 1–1 and onto.

1. A. (20p) Give a Big-O estimate that is as good as possible for each of the following functions. i. (n^3 + n)(logn + n) ii. (n + 1000)(logn + 1) B. (15p) If these are complexities of algorithms that solve the same problem, which …

2. Following algorithm calculates the sum of first n nonnegative integers. Prove the algorithm to be correct using mathematical induction. procedure sum(n: nonnegative integer) if n = 0 then return 0 else return n + sum(n - 1) {o…

Suppose T(n) and f(n) and two functions. Write asymptotic notations (Ο, Ω, Θ) using these two functions and explain the growth rate of these functions in each notation.

Here's the Solution to this Question

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Question ID: mtid-5-stid-8-sqid-843-qpid-728