STUCOR MA3354 Discrete Mathematics HW PDF
Document Details
Uploaded by Deleted User
STUCOR
Tags
Summary
This document is a homework assignment for a Discrete Mathematics course, likely at the university level. It covers various topics in propositional and predicate logic, including tautology, logical equivalences, and proof methods. The assignment includes question and answer sections focusing on fundamental concepts.
Full Transcript
MA3354 DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 20. Define Universal quantification and Existential quantification. Ans: The Universal quantification of a predicate formula P(x) is the proposition, denoted by xP ( x ) that is true if P (a) is true for...
MA3354 DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 20. Define Universal quantification and Existential quantification. Ans: The Universal quantification of a predicate formula P(x) is the proposition, denoted by xP ( x ) that is true if P (a) is true for all subject a. The Existential quantification of a predicate formula P(x) is the proposition, denoted by xP ( x ) that is true if P(a) is true for some subject a. PART – B 1(a) What is meant by Tautology? Without using truth table, show that (( P Q ) ( P ( Q R ))) ( P Q ) ( P R ) is a tautology. Solution: A Statement formula which is true always irrespective of the truth values of the individual variables is called a tautology. Consider ( P ( Q R ) ( P ( Q R ) P ( Q R ) ( P Q ) ( P R ) (1) Consider ( P Q ) ( P R ) ( P Q ) ( P R ) (( P Q ) ( P R )) (2) P Using (1) and (2) (( P Q ) ( P Q ) ( P R )) (( P Q ) ( P R )) [( P Q ) ( P R )] [( P Q ) ( P R )] T AP 1(b) Prove the following equivalences by proving the equivalences of the dual (( P Q ) ( P Q )) ( P Q ) P Solution: It‟s dual is (( P Q ) ( P Q )) ( P Q ) P Consider, R (( P Q ) ( P Q )) ( P Q ) P Reasons (( P Q ) ( P Q )) ( P Q ) (Demorgan‟s law) CO ((Q P ) ( Q P )) ( P Q ) (Commutative law) (Distributive law) ((Q Q ) P ) ( P Q ) (P P T ) (T P ) ( P Q ) (P T P) P (P Q ) (Absorption law) U P 2(a) Prove that ( P Q ) ( R Q ) ( P R ) Q. Solution: ST (P Q ) (R Q ) Reasons ( P Q ) ( R Q ) Since P Q P Q ( P R ) Q ) Distribution law Demorgan‟s law (P R ) Q since P Q P Q P R Q 3 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 2(b) Obtain DNF of Q ( P R ) (( P R ) Q ). Solution: Q ( P R ) (( P R ) Q ) ( Q ( P R )) ( (( P R ) Q ) (D e m o rg a n la w ) ( Q ( P R )) (( P R ) Q ) (D e m o rg a n la w ) ( Q ( P R )) ( Q Q ) (( P R ) P R ) (( P R ) Q ) (E x te n d e d d is trib u te d la w ) ( P Q R ) F ( F R R ) ( P Q R ) (N e g a tio n la w ) ( P Q R ) ( P Q R ) (N e g a tio n la w ) 3(a) Obtain Pcnf and Pdnf of the formula ( P Q ) ( P Q ) Solution: P Let S = ( P Q ) ( P Q ) P Q P Q P Q P Q S Minterm Maxterm AP T T F F F F T P Q T F F T T T T P Q F T T F T T T P Q F F T T T F F P Q R PCNF: P Q and PDNF: ( P Q ) ( P Q ) ( P Q ) 3(b) Obtain PDNF of P P Q P . CO Solution: P P Q P ~ P ( P (~ Q P )) ~ P (P ~ Q ) (P P) (~ P T ) ( P ~ Q ) ( P P ) U (~ P (Q ~ Q ) ( P ~ Q )) ( P (Q ~ Q )) (~ P Q ) (~ P ~ Q ) ( P ~ Q ) ( P Q ) ( P ~ Q ) (~ P Q ) (~ P ~ Q ) ( P ~ Q ) ( P Q ) ST 4(a) Without constructing the truth table obtain the product-of-sums canonical form of the formula ( P R ) ( Q P ). Hence find the sum-of products canonical form. Solution: Let S ( P R ) (Q P ) ( ( P ) R ) ((Q P ) ( P Q )) ( P R ) ( Q P ) ( P Q ) [( P R ) F ] [( Q P ) F ] [( P Q ) F ] [( P R ) (Q Q ) [( Q P ) ( R R )] [( P Q ) ( R R )] ( P R Q ) ( P R Q ) ( Q P R ) ( Q P R ) ( P Q R ) ( P Q R ) S ( P R Q ) ( P R Q ) ( P Q R ) ( P Q R ) ( P Q R ) (Pcnf) 4 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics S The remaining maxterms of P,Q and R. S ( P Q R ) ( P Q R ) ( P Q R ). ( S ) Apply duality principle to S S ( P Q R ) ( P Q R ) ( P Q R ) (PDNF) 4(b) Obtain the PDNF and PCNF of P ( P ( Q ( Q R ))). Solution: P ( P (Q ( Q R ))) P ( P (Q (Q R ))) (P Q R ) S (P Q R ) S ( P Q R ) ( P Q R ) ( P Q R ) P ( P Q R ) ( P Q R ) ( P Q R ) ( P Q R ) S (( P Q R ) ( P Q R ) ( P Q R ) AP ( P Q R ) ( P Q R ) ( P Q R ) ( P Q R )) (P Q R ) (P Q R ) (P Q R ) ( P Q R ) ( P Q R ) ( P Q R ) ( P Q R ) 5(a) Using indirect method of proof, derive p ~s from the premises p ( q r), q ~p, s ~r and p. Solution: R Let ~ ( p ~s ) be an additional premise. ~( p ~s ) ~( ~p ~s ) (p s) CO 1) p ( q r) Rule P 2) p Rule P 3) ( q r) Rule T, 1,2 4) p s Rule AP 5) s Rule T,4 U 6) s ~r Rule P 7) ~r Rule T, 5, 6 ST 8) q Rule T3,7 9) q ~p Rule P 10) ~P Rule T, 8, 9 11) p ~p Rule T, 2,10 12) F Rule T, 11 5(b) Prove that the premises a ( b c ), d ( b c ), a n d ( a d ) are inconsistent. Solution: {1} a d Rule P {1} a, d Rule T {3} a (b c ) Rule P {1,3} b c Rule T 5 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics {1,3} b c Rule T {6} d (b c ) Rule P {6} (b c ) d Rule T {6} ( b c ) d Rule T {1,3,6} d Rule T {1,3,6} d d Rule T This is a false value. Hence the set of a premises are inconsistent 6(a) Use the indirect method to prove that the conclusion z Q ( z ) follows from the premises x ( P ( x ) Q ( x )) and y P (y ) Solution: P 1 zQ ( z ) P(assumed) 2 z Q ( z ) T, (1) AP 3 y P (y ) P 4 P (a ) ES, (3) 5 Q (a ) US, (2) 6 P (a ) Q (a ) T, (4),(5) 7 ( P (a ) Q (a )) T, (6) 8 x ( P ( x ) Q (x )) R P 9 P (a ) Q (a ) US, (8) 10 P (a ) Q (a ) ( P (a ) Q (a )) T,(7),(9) contradiction CO Hence the proof. 6(b) Show that R S can be derived from the premises P ( Q S ), R P & Q Solution: R Assumed premises R P Rule P U R P Rule T P Rule T P (Q S ) Rule P ST Q S Rule P Q Rule P S Rule T R S Rule CP 7(a) Prove that xPxQx, xRx QxxRxPx. Solution: Step Derivation Rule 1 xPxQx P 2 xRxQx P 3 RxQx US, (2) 4 Rx P ( assumed) 5 Qx T,(3),(4) 6 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 6 PxQx US, (1) 7 Px T, (5),(6) 8 RxPx CP, (4),(7) 9 xRxPx UG, (9) Hence the argument is valid 7(b) Show that ( x) (P(x) Q(x)) ( x) P(x) ( x) Q(x) Solution: 1) ( x) (P(x) Q(x)) Rule P 2) P(a) Q(a) ES, 1 3) P(a) Rule T, 2 P 4) Q(a) Rule T, 2 5) ( x) P(x) EG, 3 AP 6) ( x) Q(x) EG, 4 7) ( x) P(x) ( x) Q(x) Rule T, 5, 6 8(a) Show that the following statements constitute a valid argument. If there was rain, then traveling was difficult. If they had umbrella, then traveling was not difficult. R They had umbrella. Therefore there was no rain. Solution: CO Let P : There was rain Q : Traveling was difficult R : They had umbrella Then, the given statements are symbolized as (1) P Q (2) R ~Q (3) R Conclusion : ~P U 1) R Rule P 2) R ~Q Rule P ST 3) ~ Q Rule T,1,2 4) P Q Rule P 5) ~ P Rule T,3,4 Therefore, it is a valid conclusion. 8(b) Show that the following premises are inconsistent. (1) If Nirmala misses many classes through illness then he fails high school. (2) If Nirmala fails high school, then he is uneducated. (3) If Nirmala reads a lot of books then he is not uneducated. (4) Nirmala misses many classes through illness and reads a lot of books. 7 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics Solution: E : Nirmala misses many classes S: Nirmala fails high school A: Nirmala reads lot of books H: Nirmala is uneducated Statement: (1) E S (2) S H (3) A ~ H P (4) E A Premises are : E S , S H , A ~ H, E A AP 1) E S Rule P 2) S H Rule P 3) E H Rule T, 1,2 4) A ~ H Rule P 5) H ~A R Rule T,4 6) E ~A Rule T,3,5 7) ~ E ~ A CO Rule T,6 8) ~(E A) Rule T,7 9) E A Rule P 10) (E A) ~ (E A) Rule T,8,9 Which is nothing but false U Therefore given set of premises are inconsistent 9(a) Show that the hypotheses,”It is not sunny this afternoon and it is colder than yesterday,” ” We will ST go swimming only if it is sunny,” “If we do not go swimming then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset “lead to the conclusion “we will be home by sunset”. Solution: p – It is sunny this afternoon. q- It is colder than yesterday r- we will go swimming s- we will take a canoe trip t- we will be home by sunset The given premises are p q , r p , r s & s t Step Reason p q Hypothesis p step 1 r p Hypothesis r moduus tollens step 2 &3 8 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics r s Hypothesis s modus ponens step 4 &5 s t Hypothesis t modus ponens step 6&7 9(b) Prove that 2 is irrational by giving a proof using contradiction. Solution: Let P: 2 is irrational. Assume ~P is true, then 2 is rational, which leads to a contradiction. a By our assumption is 2 , where a and b have no common factors ---------------(1) b P 2 a 2 2 2b 2 a 2 a2 is even. a = 2c b AP 2b b 2 2c 2 2 4c 2 b 2 is even b is even as well. a and b have common factor 2 (since a and b are even) But it contradicts (1) This is a contradiction. Hence ~P is false. Thus P: 2 is irrational is true. 10(a) Let p, q, r be the following statements: R p: I will study discrete mathematics q: I will watch T.V. CO r: I am in a good mood. Write the following statements in terms of p, q, r and logical connectives. (1) If I do not study and I watch T.V., then I am in good mood. (2) If I am in good mood, then I will study or I will watch T.V. (3) If I am not in good mood, then I will not watch T.V. or I will study. (4) I will watch T.V. and I will not study if and only if I am in good mood. Solution: U (1) ( p q ) r (2) r ( p q ) ST (3) r ( q p ) (4) (q p ) r 10(b) Give a direct proof of the statement.”The square of an odd integer is an odd integer”. Solution: Given: The square of an odd integer is an odd integer”. P: n is an odd integer. Q:n2 is an odd integer Hypothesis: Assume that P is true Analysis : n=2k+1 where k is some integer. n2=(2k+1)2=2(2k2+2k)+1 Conclusion: n2 is not divisible by 2.Therefore n2 is an odd integer. P Q is true. 9 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics UNIT II COMBINATORICS PART – A 1. State pigeon hole principle. Ans: If (n+1) pigeons occupies n holes then at least one hole has more than 1 pigeon. 2. State the generalized pigeon hole principle. m 1 Ans: If m pigeons occupies n holes (m>n), then at least one hole has more than 1 pigeons. n 3. Show that, among 100 people, at least 9 of them were born in the same month. Ans: Here no.of pigeon =m= no. of people =100 No. of holes = n= no. of month =12 100 1 Then by generalized pigeon hole principle, 1 9 were born in the same month. P 12 4. In how many ways can 6 persons occupy 3 vacant seats? AP Ans: Total no of ways = 6 c 3 = 20 ways. 5. How many permutations of the letters in ABCDEFGH contain the string ABC. Ans: Because the letters ABC must occur as block, we can find the answer by finding no of permutation of six objects, namely the block ABC and individual letters D,E,F,G and H. Therefore, there are 6! =720 permutations of the letters in ABCDEFGH which contains the string ABC. 6. R How many different bit strings are there of length 7? Ans: By product rule, 27=128 ways 7. How many ways are there to form a committee, if the committee consists of 3 educationalists and 4 CO socialist, if there are 9 educationalists and 11 socialist? Ans: The 3 educationalist can be chosen from 9 educationalists in 9 c 3 ways. The 4 socialist can be chosen from 11 socialist in 11C 4 ways. By product rule, the no of ways to select, the committee is = 9C 3.11C4 = 27720 ways. 8. There are 5 questions in a question paper in how many ways can a boy solve one or more questions? U Ans: The boy can dispose of each question in two ways.He may either solve it or leave it. Thus the no. of ways of disposing all the questions= 2 5. But this includes the case in which he has left all the questions unsolved. ST The total no of ways of solving the paper = 2 5 1 = 31. 9. If the sequence a n 3.2 , n 1 n , then find the corresponding recurrence relation. n 2 an a n 1 2 a n 1 a n n 1 Ans: For n ≥ 1 a n 3.2 n , a n 1 3.2 3. 2 2 a n 2 a n 1 , for n≥1, with a 0 3. 10. If seven colours are used to paint 50 bicycles, then show that at least 8 bicycles will be the same colour. Ans: Here, No. of Pigeon = 𝑚 = No. of bicycle=50 No. of Holes = 𝑛 = No. of colours = 7 50 1 By generalized pigeon hole principle, we have 1 8 7 10 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 11. Find the recurrence relation whose solution is S ( k ) 5. 2 k 5 Ans: Given S ( k ) 5.2 k S ( k 1) 5.2 k 1 =.2 k 2 S ( k 1) 5.2 k S ( k ) 2 2 S ( k 1) S ( k ) 0 , w ith S ( 0 ) 5 is the required recurrence relation. 12. Find the associated homogeneous solution for a n 3 a n 1 2 n. Ans: Its associated homogeneous equation is a n 3 a n 1 0 Its characteristic equation is r-3 =0 r =3 a n A.3 n Now, the solution of associated homogeneous equation is 13. Solve S ( k ) 7 S ( k 1 ) 1 0 S ( k 2 ) 0 S ( k ) 7 S ( k 1) 1 0 S ( k 2 ) 0 P Ans: The associated homogeneous relation is Its characteristic equation is r 7 r 1 0 0 ( r 2 )( r 5 ) 0 r =2,5 2 AP S k A.2 B.5 k k The solution of associated homogeneous equation is 14. Define Generating function. Ans: The generating function for the sequence„s‟ with terms a 0 , a 1 ,......... a n …,of real numbers is the = an x. n a 0 a 1 x ......... a n x ..... n infinite sum. G(x) = G(s,x) = R n0 15. Find the generating function for the sequence „s‟ with terms 1,2,3,4…….. 2 1 CO Ans: G ( x) G (s, x) ( n 1) x n = 1 2 x 3 x 2 .......... = (1 x ) . (1 x ) 2 n0 16. How many permutations of (a, b, c, d, e, f, g) end with a? [November 2014] Ans: 6! 1!=720 17. Find the number of arrangements of the letters in MAPPANASSRR. U 1 1! 3991680 Ans: Number of arrangements 3!2 !2 ! 48 18. In how many ways can letters of the word “INDIA” be arranged? ST Ans: The word contains 5 letters of which 2 are I‟s. 5! The number of words possible = 60. 2! 19. How many students must be in a class to guarantee that atleast two students receive the same score on the final exam if the exam is graded on a scale from 0 to 100 points. Ans: There are 101 possible scores as 0, 1, 2, …,100. By Pigeon hole principle, we have among 102 students there must be atleast two students with the same score. The class should contain minimum 102 students. 20 Show that among any group of five (not necessarily consecutive) integers, there are two with same remainder when divided by 4. Ans: Take any group of five integers. When these are divided by 4 each have some remainder. Since there are five integers and four possible remainders when an integer is divided by 4, the pigeonhole principle implies that given five integers, atleast two have the same remainder. 11 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics PART – B 1(a) n n ( n 1) ( 2 n 1) 2 Using Mathematical induction prove that i i 1 6 Solution: n ( n 1) ( 2 n 1) Let P(n) : 12 + 22 + …..+ n2 = 6 1 (1 1 ) ( 2. 1 1 ) (1) Assume P(1) : 12 = is true 6 k ( k 1) ( 2 k 1) (2) Assume P(k) : 12 + 22 + …..+k2 = is true, where k is any integer. P 6 k ( k 1) ( 2 k 1) (3) P(k + 1) = 12 + 22 + …..+k2 + (k + 1)2 = ( k 1) 2 AP 6 ( k 1 ) [ ( k 1 ) 1 ] [( 2 ( k 1 ) 1 ] = 6 Therefore P(k + 1) is true. n ( n 1) ( 2 n 1) n R Hence, i 2 is true for all n. i 1 6 1(b) Use mathematical Induction to prove that 3n 7n 2 is divisible by 8, for n 1. CO Solution: Let Pn : 3n 7n 2 is divisible by 8. (i) P1 : 31 71 2 8 is divisible by 8, is true. (ii) Assume Pk : 3k 7k 2 is divisible by 8 is true ------(1) U Claim: Pk 1 is true Pk 1 3k+1 7k+1 2 ST 33k 7 7k 2 3.3k 37k 47k 6 4 3 3k 7k 2 4 7k 1 47k 1 is divisible by 8 and by (1) 33k 7k 2 is divisible by 8. Pk 1 33k 7k 2 47k 1 is divisible by 8 is true. 2(a) Prove by mathematical induction that 6 n 2 7 2 n 1 is divisible by 43 for each positive integer n. Solution: S(1): Inductive step: for 𝑛 = 1, 1 2 2 1 6 7 =559, which is divisible by 43 So S(1) is true. Assume S(k) is true (i.e) 6 k 2 7 2 k 1 4 3 m for some integer m. 12 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics To prove S(k+1) is true.Now k 3 2k 3 k 3 2 k 1 7 6 7 2 6.7 k2 2 k 1 2 k 1 6 (6 7 ) 4 3.7 2 k 1 6.4 3 m 4 3.7 2 k 1 4 3(6 m 7 ) Which is divisible by 43. So S(k+1) is true. By Mathematical Induction , S(n) is true for all integer n. 2(b) Using mathematical induction ,prove that 2 2 2 2 3 ......... 2 n 2 n 1 2 Let p (n) = 2 2 2 2 3 ......... 2 n. Assume p (1): 2 1 2 1 1 2 is true. Assume p(k) : 2 2 2 2 3 ......... 2 k 2 k 1 2 is true P Claim p(k+1) is true. P(k+1) : 2 2 2 2 3 ... 2 k 2 k 1 = 2 k 1 2 2 k 1 = 2.2 k 1 2 = 2 k 2 2 AP P(k+1) is true. Hence it is true for all n. 3(a) Suppose there are six boys and five girls, (1) In how many ways can they sit in a row. (2) In how many ways can they sit in a row, if the boys and girls each sit together. (3) In how many ways can they sit in a row, if the girls are to sit together and the boy don‟t sit together. R (4) How many seating arrangements are there with no two girls sitting together. Solution: 1. There are 6 + 5 = 11 persons and they can sit in 11P 11 ways. CO 11P11 = 11! ways 2. The boys among themselves can sit in 6! ways and girls among themselves can sit in 5! ways.They can be considered as 2 units and can be permuted in 2! ways. Thus the required seating arrangement can be done in = 2! x 6! x 5! ways = 172800 ways U 3. The boys can sit in 6! Ways and girls in 5! ways. Since girls have to sit together they are considered as one unit. Among the 6 boys either 0 or 1 or 2 or 3 or 4 or 5 or 6 have to sit to the left of the girls units. Of these seven ways 0 and 6 cases have to be omitted ST as the boys do not sit together.Thus the required number of arrangements = 5 x 6! x 5! = 432000 ways. 4. The boys can sit in 6 ! ways. There are seven places where the girls can be placed. Thus the total arrangements are 7P5 x 6! Ways = 1814400 ways. 3(b) A bit is either 0 or 1. A byte is a sequence of 8 bits. Find the number of bytes.Among these how many are (i) Starting with 11 and ending with 00 (ii) Starting with 11 but not ending with 00. Solution: (1) Consider a byte starting with 11 and ending with 00.Now the remaining 4 places can be filled with either 0 or 1 which can be done in 24.Hence there are 16 bytes starting with 00 and ending with11. (2) Consider a byte starting with 11 and not ended with 00 Now there are 3 bytes which is not ended with 00(ended with 01,10 and 11).Now the remaining 4 places can be filled with either 0 or 1 which can be done in 24ways.Hence there are 3×16=48 bytes starting with 00 but not ending with11 4(a) How many positive integers 'n ' can be formed using the digits 3,4,4,5,5,6,7 if 'n ' has to exceed 50,00,000 ? Solution: Consider a 7digit number p 1 , p 2 , p 3 , p 4 , p 5 , p 6 , p 7 , in order to be a number ≥ 5000000 , p 1 is filled with 13 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics either 5 or 6 or 7 (mutually exclusive) 6! Case(1): p 1 is filled with 5 and remaining 6 position are filled with 3, 4, 4(repeated),5,6,7 in = 360 2! Case(2): p 1 is filled with 6 and remaining 6 positions are filled with 3,4,4 (repeated) 5,5 (repeated), 7 in 6! = 180 2 !2 ! Case(3) p 1 is filled with 7 and remaining 6 position are filled with 3,4,4(repeated),5,5 (repeated), 6 in 6! = 180 2 !2 ! All above 3 cases are mutually exclusive in total 360+180+180=720 ways. 4(b) Prove that in any group of six people there must be atleast three mutual friends or three mutual P enemies. Proof: Let the six people be A, B, C, D, E and F. Fix A. The remaining five people can accommodate into two AP groups namely (1) Friends of A and (2) Enemies of A 5 1 Now by generalized Pigeon hole principle, at least one of the group must contain 1 3 people. 2 Let the friend of A contain 3 people.(Let it be B, C, D) Case(1) If any two of these three people (B, C, D) are friends, then these two together with A form three mutual friends. R Case(2) If no two of these three people are friends, then these three people (B, C, D) are mutual enemies. In either case, we get the required conclusion. CO If the group of enemies of A contains three people, by the above similar argument, we get the required conclusion. 5(a) A computer password consists of a letter of English alphabet followed by 2 or 3 digits. Find the following : (1) The total number of passwords that can be formed (2) The number of passwords that no digit repeats. U Sol: (1) Since there are 26 alphabets and 10 digits and the digits can be repeated by the product rule the number of 3-character password is 26.10.10=2600 Similarly the number of 4 character password is 26.10.10.10=26000 Hence the tool number of password is 2600+26000=28600. ST (2) Since the digits are not repeated, the first digit after alphabet can be taken from any one out of 10, the second digit from remaining 9 digits and so on. Thus the number of 3-character password is 26.10.9=2340 Similarly the number of 4- character password is 26.10.9.8=18720 Hence the total number of password is 2340+18720=21060. 5(b) Show that among (𝒏 + 𝟏) positive integers not exceeding 2n there must be an integer that divides one of the other integers. Solution: Let the (𝑛 + 1) integers be a 1 , a 2 ,... a n 1 Each of these numbers can be expressed as an odd multiple of a power of 2. i.e a i 2 k i m i Where k i non negative integer m i odd integer where i =1, 2,3,..., n +1. 14 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics Here, Pigeon=The odd positive integers m 1 , m 2 ,... m n 1 less than 2n Pigeon= 'n ' odd positive integer less than 2n. Hence by pigeon hole principle, 2 of the integers must be equal. and a j 2 m j kj ai 2 ki Now mi ki ai 2 kj ( m i m j ) aj 2 ki k Case-1: If ki k then 2 divides 2 and hence a i divides. j j a j Case-2: If ki k j then a j divides a i. 6(a) In A survey of 100 students, it was found that 30 studied Mathematics, 54 studied Statistics, 25 studied Operations Research, 1 studied all the three subjects, 20 studied Mathematics and Statistics, P 3 studied Mathematics and Operation Research and 15 studied Statistics and Operation Research. Find how many students studied none of these subjects and how many students studied only Mathematics? AP Solution. n(A) = 30; n(B) = 54;n(C) = 25; n(AB) = 20; n(AC) = 3; n(BC) = 15; n(ABC)=1 n(ABC) = n(A)+n(B)+n(C) – n(AB) – n(BC) – n(AC) + n(ABC) = 72 None of the subjects = 28. R Only mathematics = 8. 6(b) A total of 1232 students have taken a course in Spanish, 879 have taken a course in French, and 114 CO have taken a course in Russian. Further, 103 have taken courses in both Spanish and Russian, 23 have taken courses in both Spanish and French and 14 have taken courses in both French and Russian. If 2092 students have taken atleast one of Spanish, French and Russian, how many students have taken a course in all three languages? Solution: S-Spanish,F-French, R-Russian |S|=1232 |F|=879 |R|=114 |S∩R|=103 |S∩F|=23 |F∩R|=14 U |S∪F∪R|=2092 |S∪F∪R=|S|+|F|+|R|-|S∩F|- |S∩R|-|F∩R|+|S∩F∩R| |S∩F∩R|=7 Find all the solution of the recurrence relation an = 5an–1 – 6 an–2 + 7n ST 7(a) Solution: Given non-homogeneous equation can be written as an – 5an–1 + 6 an–2 – 7n = 0 Now, its associated homogeneous equation is an – 5an–1 + 6 an–2 = 0 Its characteristic equation is r2 – 5r + 6 = 0 Roots are r = 2,3 (h) n n Solution is a n c 1 2 c 2 3 To find particular solution Since F(n) = 7n, then the solution is of the form C.7n, where C is a constant. Therefore, the equation an = 5an–1 – 6 an–2 + 7n becomes C7n = 5C7n–1–6C7n–2+7n ……(1) Dividing the both sides of (1) by 7n–2. n n 1 n2 n C.7 5C 7 6C 7 7 49 (1) C n2 n2 n2 n2 7 7 7 7 20 15 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics ( p) 49 n Hence the particular solution is a n 7 20 49 n Therefore, a n c 1 ( 2 ) n c 2 ( 3 ) n 7 20 7(b) Find the number of integers between 1 and 250 that are not divisible by any of the integers 2, 3, 5 &7. Sol: Let A, B, C,D are the set of integers between 1 and 250 that are divisible by 2, 3, 5, 7 respectively. 250 250 | A | [ ] 125 , | B | [ ] 83 2 3 250 250 | C | [ ] 50 , | D | [ ] 35 5 7 250 250 250 P | A B | 41 LCM ( 2 , 3 ) 2 3 6 250 250 AP 250 | A C | 25 10 LCM ( 2 , 5 ) 25 250 250 250 | A D | 17 14 LCM ( 2 , 7 ) 2 7 250 250 250 | B C | 16 LCM ( 3 , 5 ) R 5 3 15 250 250 250 | B D | 11 CO L C M (7 , 3) 73 21 250 250 250 | C D | 7 L C M (5, 7 ) 5 7 35 250 250 | A B C | 8 LCM ( 2 , 3 , 5 ) 2 3 5 U 250 250 | A B D | 5 LCM ( 2 , 3 , 7 ) 2 3 7 ST 250 250 | A C D | 3 LCM ( 2 , 5 , 7 ) 2 5 7 250 250 | B C D | 2 LCM ( 3 , 5 , 7 ) 3 5 7 250 250 | A B C D | 1 LCM ( 2 , 3 , 5 , 7 ) 2 3 5 7 | A B C D | | A | | B | | C | | D | | A B | | A C | | A D | | B C | |B D | |C D | | A B C | | A B D | | A C D | |B C D | | A B C D | =125+83+50+35-41-25-17-16-11-7+8+5+3+2-1=193 The number of integers between 1 and 250 that is divisible by any of the integers 2, 3, 5 and 7=193 Therefore not divisible by any of the integers 2, 3, 5 and 7=250-193=57. 16 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 8(a) Solve the recurrence relation a n 2 ( a n 1 a n 2 ) where 𝒏 ≥ 𝟐 and a 0 1 , a 1 2 a n 2 ( a n 1 a n 2 ) a n 2 a n 1 2 a n 2 0 The characteristic equation is given by 2 2 0 2 2 4 4(2) 2 i2 1 i 2 2 1 i ,1 i Solution is a n A (1 i ) B (1 i ) n n Where A and B are arbitrary constants P Now, we have z x iy AP r [cos i sin ] 1 y tan x By Demoivre‟s theorem we have, n (1 i ) [ i sin n 2 cos ] 4 R 4 n n n [ 2 ] cos i sin 4 4 CO n n n and (1 i ) [ i sin n 2 ] cos 4 4 Now, n n n n n n a n A [[ 2 ] cos i s in ] B [[ 2 ] cos i s in ] U 4 4 4 4 n n n [ 2 ] ( A B ) cos i ( A B ) s in 4 4 ST n n n an [ 2 ] C1 cos C 2 s in ] (1) 4 4 Is the required solution. Let C 1 =𝐴 + 𝐵, C2 =𝑖(𝐴 − 𝐵) Since 𝑎0 = 1, 𝑎1 = 2 17 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics (1 ) a 0 ( 2 )[ C 1 cos 0 C 2 sin 0 ] 0 1 C1 1 a1 [ 2 ] C 1 cos C 2 sin ] 4 4 1 1 2 2C1 C 2 sin ] 2 2 2 C1 C 2 C2 1 n n n an [ 2 ] cos sin ] P 4 4 8(b) Solve the recurrence relation of the Fibonacci sequence of numbers f n f n 1 f n 2 , n 2 AP with initial conditions f 1 1, f 2 1. Sol: The sequence of Fibonacci numbers satisfies the recurrence relation f n f n 1 f n 2..... (1 ) and satisfies the initial conditions f 1 1, f 2 1. (1 ) f n f n 1 f n 2 0...( 2 ) Let 𝑓𝑛 = 𝑟 𝑛 be a solution of the given equation. R The characteristic equation is 𝑟 2 − 𝑟 − 1 = 0 1 1 4 r CO 2 1 5 1 5 Let r1 , r2 2 2 By theorem n n 1 5 1 5 1 2 ...( 3 ) U fn 2 2 1 5 1 5 f1 1 f1 1 1 ST 2 2 2 (1 5 ) 1 (1 5 ) 2 2...( 4 ) 2 2 1 5 1 5 f2 1 f2 1 2 1 2 2 (1 (1 2 2 5) 5) 1 2 1 4 4 (1 5 ) 1 (1 5) 4 2 2 2...( 5 ) 18 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics ( 4 ) (1 5) (1 (1 5 ) 1 (1 5) 2 (1 2 5) 2 5)...( 6 ) ( 6 ) ( 5 ) 1 (1 5 ) [1 5 1 5] 2 2 5 4 1 (1 5 )[ 2 5 ] 2 2 5 1 (1 5 )[ 2 5 ] 2 (1 5) 1 1 5 1 4 ) (1 5) (1 5 ) 2 2 5 P 1 1 (1 5 ) 2 2 5 AP 1 (1 5 ) 2 2 1 5 1 1 5 5 1 (1 5 ) 2 5 R 1 2 CO 5 n n 1 1 5 1 1 5 (3) f n 5 2 5 2 9(a) Solve the recurrence relation a n 6 a n 1 11 a n 2 6 a n 3 with a 0 2 , a 1 5 and a 2 15 U [November 2014] Solution: The unique Solution to this recurrence relation and the given initial condition is the sequence { a n } with ST a n 1 2 2.3 n n 9(b) A factory makes custom sports cars at an interesting rate. In the first month only one car is made, in the second month two cars are made and so on, with n cars made in the nth month. (1) Set up recurrence relation for the number of cars produced in the first n months by this factory. (2) How many cars are produced in the first year? Solution: (i) a n n a n 1 , a o 0 ( a 1 1, a 2 2 a 1 , e tc ) (ii) By recursively a 1 2 7 8 10(a) Solve 𝑺(𝒏 + 𝟏) − 𝟐𝑺(𝒏) = 𝟒𝒏 , with 𝑺(𝟎) = 𝟏 and 𝒏 ≥ 𝟏 Solution: Given 𝑎𝑛+1 − 2𝑎𝑛 − 4𝑛 = 0 Multiply by x n , and sum over all n 0 to . 19 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics n n n n a n 1 x 2 an x 4 x 0 n0 n0 n0 1 3x G (x) (1 2 x ) (1 4 x ) 1 1 By Applying Partial fractions we get A ,B 2 2 1 1 n n n n G (x) 2 x 4 x 2 n0 2 n0 hence w e get n 1 n 1 an 2 2(4) P 10(b) Find the generating function of Fibonacci sequence. Solution Fibonacci sequence : f n f n 1 f n 2 , n 2 with f o 0 , f 1 1 AP Multiply by z n , and sum over all n 2. f n 1 z n n n fn z fn2 z n2 n2 n2 G ( z ) f 0 f 1 z z ( G (z ) f 0 ) z ( G ( z )) 2 G (z) fn z n R n0 Where ( i.e ) G ( z ) z G ( z ) z G ( z ) f 0 f 1 z z f 0 2 CO z G (z) 1 z z 2 UNIT III GRAPH THEORY PART – A 01. Define Graph. U Ans: A graph G = (V,E) consists of a finite non empty set V, the element of which are the vertices of G, and a finite set E of unordered pairs of distinct elements of V called the edges of G. 02. Define complete graph. ST Ans: A graph of n vertices having each pair of distinct vertices joined by an edge is called a Complete graph and is denoted by Kn. 03. Define regular graph. Ans: A graph in which each vertex has the same degree is called a regular graph. A regular graph has k – regular if each vertex has degree k. 04. Define Bipartite Graph with example. Ans: Let G = (V,E) be a graph. G is bipartite graph if its vertex set V can be partitioned into two nonempty disjoint subsets V1 and V2 , called a bipartition, such that each edge has one end in V1 and in V2. For eg C6 V2 V3 V1 V4 V6 V5 20 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP P AP R CO U ST DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP P AP R CO U ST DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 1(b) In any graph show that the number of odd vertices is even. Let G = (V, E) be the undirected graph. Let 𝑣1 and 𝑣2 be the set of vertices of G of even and odd degrees respectively. Then by hand shaking theorem, 2e = d e g ( v i ) d e g ( v j ). Since each deg(vi) is even, d e g ( v i ) is even. Since LHS is even, we v i v1 v j v2 v i v1 get deg(v j ) is even. Since each deg(vj) is odd, the number of terms contain in deg(v j ) or v2 is v j v2 v j v2 even, that is, the number of vertices of odd degree is even. 2(a) Prove that a simple graph with at least two vertices has at least two vertices of same degree. Proof: Let G be a simple graph with n 2 vertices. The graph G has no loop and parallel edges. Hence the degree of each vertex is n-1. P Suppose that all the vertices of G are of different degrees. Following degrees 0, 1, 2, …, n-1 are possible for n vertices of G. AP Let u be the vertex with degree 0. Then u is an isolated vertex. Let v be the vertex with degree n-1 then v has n-1 adjacent vertices. Because v is not an adjacent vertex of itself, therefore every vertex of G other than u is an adjacent vertex of G. Hence u cannot be an isolated vertex, this contradiction proves that simple graph contains two vertices of same degree. 2(b) n ( n 1) Prove that the maximum number of edges in a simple graph with n vertices is n c R 2 2 Proof: We prove this theorem, by the method of mathematical induction. For 𝑛 = 1, a graph with 1 vertex has CO no edges. Therefore the result is true for n = 1. For n = 2, a graph with two vertices may have atmost one edge. Therefore 2 (2 –1) / 2 = 1. Hence for n = 2, the result is true. k ( k 1) Assume that the result is true for n = k, i.e, a graph with k vertices has atmost edges. 2 Then for n = k + 1, let G be a graph having n vertices and G be the graph obtained from G, by deleting one U vertex say, „v‟ V(G). k ( k 1) Since G has k vertices then by the hypothesis, G has atmost edges. Now add the vertex v to G. ST 2 „v‟ may be adjacent to all the k vertices of G. k ( k 1) k ( k 1) Therefore the total number of edges in G are +k=. 2 2 Therefore the result is true for n = k+1. n ( n 1) Hence, the maximum number of edges in a simple graph with „n‟ vertices is. 2 3(a) ( n 1 )(n 2 ) Show that a simple graph G with n vertices is connected if it has more than edges 2 Proof: Suppose G is not connected. Then it has a component of k vertices for some k, The most edges G could have is 23 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics k ( k 1) ( n k )( n k 1) C (k , 2) C (n k , 2) 2 2 2 n n k nk 2 This quadratic function of f is minimized at k = n/2 and maximized at k = 1 or k = n – 1 Hence, if G is not connected, then the number of edges does not exceed the value of this function at 1 and ( n 1)(n 2 ) at n-1, namely. 2 3(b) If a graph G has exactly two vertices of odd degree, then prove that there is a path joining these two vertices. Proof: Case (i): Let G be connected. P Let v1 and v2 be the only vertices of G with are of odd degree. But we know that number of odd vertices is even. So clearly there is a path connecting v1 and v2, because G is connected. Case (ii): Let G be disconnected AP Then the components of G are connected. Hence v1 and v2 should belong to the same component of G. Hence, there is a path between v1 and v2. 4(a) ( n k )( n k 1 ) Prove that a simple graph with n vertices and k components can have at most 2 edges. Let the number of vertices of the ith component of G be 𝑛𝑖 , 𝑛𝑖 ≥ 1.. k k R ni n ( n i 1) ( n k ) i 1 i 1 2 CO k 2 2 Then ( n i 1) n 2nk k i 1 k k 2 2 2 2 2 2 th a t is ( n i 1) n 2nk k ni n 2nk k 2n k i 1 i 1 n i ( n i 1) 1 k n 2 U Now the maximum number of edges in the ith component of G = ni 2 2 i 1 2 2 2 (n 2nk k 2n k ) n ( n k )( n k 1) ST 2 2 2 4(b) If all the vertices of an undirected graph are each of degree k, show that the number of edges of the graph is a multiple of k. Solution: Let 2n be the number of vertices of the given graph….(1) Let n e be the number of edges of the given graph. By Handshaking theorem, we have 2n d eg vi 2 ne i 1 2 nk 2 ne (1) ne nk Number of edges =multiple of 𝑘. Hence the number of edges of the graph is a multiple of k 24 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 5(a) Draw the graph with 3 vertices A,B,C, D & E such that the deg(A)=3,B is an odd vertex, deg(C)=2 and D and E are adjacent. Solution: d(E)=5 ,d(C)=2,d(D)=5 ,d(A)=3 d(B)=1 5(b) Draw the complete graph K 5 with vertices A,B,C,D,E. Draw all complete sub graph of K 5 with 4 P vertices. Solution: AP R CO complete sub graph with 4 vertices U ST 6(a) Prove that a given connected graph G is Euler graph if and only if all vertices of G are of even degree. Solution: Case (i) Prove If G is Euler graph→ Every vertex of G has even degree. Case (ii) Prove If Every vertex of G has even degree.→ G is Euler graph ( by Contradiction Method). 25 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 6(b) Find the adjacency matrix of the given directed graph. (i) (ii) P Answer: 0 2 0 0 0 0 AP 1 1 0 1 2 0 1 1 0 0 0 0 0 1 0 1 2 1 0 0 (i) ( ii ) 0 0 0 0 0 1 1 2 0 0 3 1 0 1 0 0 0 0 0 0 0 0 0 1 3 0 7(a) Show that isomorphism of simple graphs is an equivalence relation. [November 2014] R Solution: G is isomorphism to itself by the identity function, So isomorphism is reflexive. Suppose that G is CO isomorphic to H.Then there exists a one –to-one correspondence f from G to H that preserves adjacency 1 and nonadjacency.It follows that f is a one-to-one correspondence from H to G that preserves adjacency and non-adjacency.Hence isomorphism is symmetric.If G is isomorphic to H and H is isomorphic to K then there are ono-to-one correspondences f and g from G to H and from H to K that preserves adjacency and nonadjacency.It follows that g f is a one-to-one correspondencies from G to K that preserves adjacency U and non-adjacency.Hence isomorphism is transitive. 7(b) Find the incidence matrix for the following graph. ST (i) (ii) 26 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics Answer: 1 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 (i ) ( ii ) 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 8(a) Examine whether the following pair of graphs are isomorphic. If not isomorphic, give the reasons P u1 u2 v1 v2 AP v5 u3 u5 u4 v4 v3 Solution: Same number of vertices and edges. Also an equal number of vertices with a given degree. R The adjacency matrices of the two graphs are 0 1 0 1 1 CO 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 0 1 and 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 U 1 1 0 1 0 since the two adjacency matrices are the same, the two graphs are isomorphic. 8(b) ST Prove that if a graph G has not more than two vertices of odd degree, then there can be Euler path in G. Statement: Let the odd degree vertices be labeled as V and W in any arbitrary order. Add an edge to G between the vertex pair (V,W) to form a new graph G‟. Now every vertex of G‟ is of even degree and hence G‟ has an Eulerian Trail T. If the edge that we added to G is now removed from T, It will split into an open trail containing all edges of G which is nothing but an Euler path in G 9(a) Show that K 7 has Hamiltonian graph. How many edge disjoint Hamiltonian cycles are there in K 7 ? List all the edge-disjoint Hamiltonian cycles. Is it Eulerian graph ? 27 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP P AP R CO U ST DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics UNIT – IV GROUP THEORY PART – A 01. Define Algebraic system. Ans: A set together with one or more n-ary operations on it is called an algebraic system. Example (Z,+) is an algebraic system. 02. Define Semi Group. Ans: Let S be non empty set, * be a binary operation on S. The algebraic system (S, *) is called a semi group, if the operation is associative. In other words (S,*) is a semi group if for any x, y, z S, x* (y * z) = (x* y )* z. 03. Define Monoid. Ans: A semi group (M, *) with identity element with respect to the operation * is called a Monoid. In other words (M,*) is a semi group if for any x, y, z M, x* (y * z) = (x* y )* z and there exists an P element e M such that for any x M then e* x = x* e = x. 04. Define Group. AP Ans: An algebraic system (G,*) is called a group if it satisfies the following properties: (i) G is closed with respect to * (ii) * is associative. (iii) Identity element exists. (iv) Inverse element exists. 05. State any two properties of a group. R Ans: (i)The identity element of a group is unique. (ii) The inverse of each element is unique. CO 06. Define a Commutative ring. Ans: If the Ring (R, *) is commutative, then the ring (R, +, *) is called a commutative ring. 07. Show that the inverse of an element in a group (G, *) is unique. Ans: Let (G,*) be a group with identity element e. Let „b‟ and „c‟ be inverses of an element „a‟ a * b = b * a = e, a * c = c * a = e. U b = b * e = b * ( a * c) = ( b * a ) * c = e * c = c b = c. Hence inverse element is unique. 08. Give an example of semi group but not a Monoid. ST Ans: The set of all positive integers over addition form a semi-group but it is not a Monoid. 09. Prove that the semigroup homomorphism preserves idempotency. Ans: Let a S be an idempotent element. a*a a g (a * a ) g (a ) g (a ) g (a ) g (a ) This shows that g ( a ) is an idempotent element in T. Therefore the property of idempotency is preserved under semigroup homomorphism. 10. Define cyclic group. Ans: A group (G,*) is said to be cyclic if there exists an element a G such that every element of G can be written as some power of „a‟. 29 DOWNLOADED FROM STUCOR APP DOWNLOADED FROM STUCOR APP MA3354 Discrete Mathematics 11. Define group homomorphism. Ans: Let (G,*) and ( S , ) be two groups. A mapping f : G S is said to be a group homomorphism if for any a, b G f(a*b) = f(a) f(b). 12. Define Left Coset. Ans: Let (H,*) be a subgroup of (G,*). For any a G the set H is defined by aH = {a*h: h H} is called the right coset of H determined by a G. 13. State Lagrange‟s theorem. Ans: The order of the subgroup of a finite group G divides the order of the group. 14. Define Ring. Ans: An algebraic system (R, +, *) is called a ring if the binary operations + and R satisfies the following. (i) (R,+) is an abelian group P (ii) (R,*) is a semi group (iii) The operation is distributive over +. 15. Define field. AP Ans: A commutative ring (F, +, *) which has more than one element such that every nonzero element of F has a multiplicative inverse in F is called a field. 16. Define Integral Domain. Ans: A commutative ring R with a unit element is called an integral domain if R has no zero divisors. 17. Let T be the set of all even integers. Show that the semi groups (Z,+) and (T,+) are isomorphic. R Ans: Define a function f: Z T by f(n) = 2n where n1, n2 N. f is a homomorphism since f(n1+ n2 ) =f n1) +f( n2). f is one-one since f(n1) = f( n2). CO f is onto since f(a) = 2a. therefore f is an isomorphism. 18. Show that the semi group homomorphism preserves the property of idempotency. Ans: Let f : (M,*) → (H,Δ) be a semi group homomorphism. x is idempotent element in M. x*x = x. f(x*x) = f(x) Δ f(x). 19. Let be a Monoid and aM. If a is invertible, then show that its inverse is unique. U Ans: Let „b‟ and „c‟ be inverses of „a‟. Then a * b = b * a = e and a * c = c * a = e. Now b =
