#mathematics solved assignment

Course Code : MCS-013 Course Title : Discrete Mathematics

Assignment Number : MCA(1)/013/Assign/2013

Assignment Marks : 100 Weightage : 25% Last Dates for Submission : 15th October, 2013 (For July 2013 Session) 15th April, 2014 (For January 2014 Session) There are eight questions in this assignment, which carry 80 marks. Rest 20 marks are for viva-voce. Answer all the questions. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide for the format of presentation. Question 1: Marks (4 + 2 +4) a) Make truth table for i) p→(~q ~ r) ~p q T REPRESENTED 1 AND REVERCE T 0 ii) ~p→~r q ~p r

b) If A = {1, 2, 3, 4, 5,6,7,8, 9} B = {2, 3, 5, 6, 7} Then find A B . AB =(A union B)-(A intersect B) ={1, 2, 3, 4, 5,6,7,8, 9} union {2, 3, 5, 6, 7} – {1, 2, 3, 4, 5,6,7,8, 9} intersect {2, 3, 5, 6, 7} ={1,2,3,4,5,6,7,8,9} – {2,3,5,6,7) ={1,4,8,9} c) Write down suitable mathematical statement that can be represented by the following symbolic properties. i) ( x) ( y) ( z) P statement: (all of x)(all of y)(any one of z) ii) (x) ( y) ( z) P statement: all of [ (x)(any of y)(any of z) ] Question 2: Marks (4 + 3+3) a) What is proof? Explain how direct proof is different from indirect proof. Explain method of direct proof with theJUSThelpCHILLofoneANDexampleVISIT:WWW..VIJAYJOTANI.TK……..thanks to me VIJAYJOTANI(VJ) indirect Proof: Assume what you need to prove is false, and then show that something contradictory (absurd) happens. Direct Proofs Suppose that you want to prove the statement P –> Q you need to show “If P is true, then Q is true”. In a direct proof, you assume that P is true, then use inference rules and other that Q is true. “really, what you are doing is proving then following” (P ^ all the math facts that have ever been discovered to be always true) –> Q Now… “all the math facts…” should worry you. If you are ever stuck trying to prove something, you should look through the assigned readings and lecture notes and see if there is some math fact you are missing… or how to FORMALLY express some math fact. For instance (math fact #1): Let P(n) be the predicate “n is even”. How do∃you express this? P(n) = ( ) a, n = 2a Our First Proof: Prove∃ P(14). ( ) a, 2a = 14 definition of P. 1. choose a = 7, 2(7) = 14. math. 2. (exists) a, 2a = 14 existential generalization. Indirect Proof Sometimes, it is HARD to do a direct proof. In these cases, you can perhaps “apply a logical equivalence” to the formula you are trying to prove, then prove this equivalent formula. This is called an “indirect proof”, sometimes proof by contrapositive.. an indirect proof of P –> Q is: ~Q –> ~P so, assume Q is false, and show that then P is false. remember, that we always use other math facts in our proof so this is really: (P ^ math) –> Q <==> ~Q –> ~(P ^ math) ~Q –> (~P v ~math) so you can show that your assumption is violated, or some other contradiction with known math facts… ok, now an example of an indirect proof: If n is an integer and n2 is odd, then n is odd. try direct proof. try indirect proof. Another indirect proof: There are 41 Home Blues Hockey games. Prove that at least 6 of them must be on the same day of the week. c) Consider a set X = [2, 3, 4) and the Relation defined on X by. R = {(2, 2) (2, 3) (3, 3) (3, 4) (2, 4) (4, 4)}. Find whether R is : i) Reflexive ii) Symmetric iii) Transitive Also justify your answer. X={2,3,4) from this REFLEXIVE OF X ={(2,2)(3,3)(4,4) SYMMENTRIC OF X ={(2,3)(3,2)(2,4)(4,2)(3,4)(4,3)} TRANSATIVE OF X ={(2,3)(3,4)(2,4)} GIVE THAT R = {(2, 2) (2, 3) (3, 3) (3, 4) (2, 4) (4, 4)}. WHICH INCLUDED REFLACTIVE AND TRANSITIVE BOTH Question 3: Marks (5 + 5) a) A survey among the students of college. 60 Study Hindi, 40 study Spanish, and 45 study Japanese, Further 20 study Hindi and Spanish, 25 study Hindi and Japanese, 15 study Spanish and Japanese and 8 study all the languages. Find the followings: A=60 B=40 C=45 A intercept B =20 A intercept C =25 B intercept C =15 A intercept B Intercept C =5 i) How many students are studying at least one language? A union B union C = A +B+C-A intercept B -A intercept C - B intercept C +A intercept B Intercept C =60+40+45-20-25-15+8 =93 ii) How many students are studying only Hindi ? only hindi= A- A intercept B - A intercept C + A intercept B Intercept C =60-25-20+8 =23 iii) How many students are studying only Japanese ? only Japanese = C- A intercept C - B intercept C + A intercept B Intercept C =45-25-15+8 =13 b) If p and q are statements, show whether the statement [(~p→q) (~q)] → (~p ~q) is a tautology or not. No, It is not a tootology because as per tautology p v ~q is required when it it in Question 4: Marks (4 + 4 +2) a) Make logic circuit for the following Boolean expressions: i) (x′ y z) + (x y z)′ ii) ( x’ y) (y′ z) (y z′) iv) (x^y) v ( y v z ) b) Explain principle of duality. Find dual of Boolean expression of the output of the following logic circuit: Duality Principle In mathematics, a duality, generally speaking, translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often (but not always) by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues’ theorem in projective geometry is self-dual in this sense. In mathematical contexts, duality has numerous meanings[clarification needed] although it is “a very pervasive and important concept in (modern) mathematics”[1] and “an important general theme that has manifestations in almost every area of mathematics”.[2] Many mathematical dualities between objects of two types correspond to pairings, bilinear functions from an object of one type and another object of the second type to some family of scalars. For instance, linear algebra duality corresponds in this way to bilinear maps from pairs of vector spaces to scalars, the duality between distributions and the associated test functions corresponds to the pairing in which one integrates a distribution against a test function, and Poincaré duality corresponds similarly to intersection number, viewed as a pairing between submanifolds of a given manifold.[3] Duality can also be seen as a functor, at least in the realm of vector spaces. There it is allowed to assign to each space its dual space and the pullback construction allows to assign for each arrow f: V → W, its dual f*: W* → V*. . [ [(a’b)b’)’c]’ c) Set A, B and C are: A = {1, 2, 4, 5,6,19}, B = { 1,2,5,22, 44 } and C { 2, 5,11,19,25,40}, Find A BC and A BC. A BC ={1, 2, 4, 5,6,19}{ 1,2,5,22, 44 }{ 2, 5,11,19,25,40}, ={1,2,5,11,19,25,40} A BC. ={1, 2, 4, 5,6,19}{ 1,2,5,22, 44 }{ 2, 5,11,19,25,40}, ={1,2,4,5,6,19,22,25,40,44} Question 5: Marks (3+3 +4) a) Draw a Venn diagram to represent following: i) (A B) (C~B) (A B) = (C~B) = therefore, (A B) (C~B)= ii) (AB) (B C) yellow color= B delta C (AB) (AB) (B C) b) Define relation mathematically. Also give at least two example of relations. In mathematics, a relation is used to describe certain properties of things. That way, certain things may be connected in some way; this is called a relation. It is clear, that things are either related, or they are not, there are no in-betweens. Relations are classfied into four types based on mapping of elements. Formally, a relation is a set of n-tuples of equal degree. Thus a binary relation is a set of pairs, a ternary relation a set of 3-tuples, and so forth. A ternary relation however is always expressable as two binary relations. Specifically in the context of functions, this is known as currying. Particularly concerning binary relations, the set of all the starting point is called the domain and the sets of the ending points is the range. The domain is the x’s, and the range is the y’s. An example for such a relation might be a function. Functions associate keys with values. The set of all functions is a subset of the set of all relations – a function is a relation where the first value of every tuple is unique through the set. Other well-known relations are the Equivalence relation and the Order relation. That way, sets of things can be ordered: Take the first element of a set, it is either equal to the element looked for, or there is an order relation that can be used to classify it. That way, the whole set can be classified (compared to some arbitrarily chosen element). Relations can be transitive. One example of a transitive relation is “smaller-than”. If X “is smaller than” Y, and Y is “smaller than” Z, then X “is smaller than” Z Relations can be symmetric. One example of a symm etric relation is “is equal to”. If X “is equal to” Y, Y “is equal to” X. Relations can be reflexive. One example of a reflexive relation is “is equal to”. X “is equal to” X. Question 6: Marks (5+5) a) What is inclusion-exclusion principle? Explain one application of inclusion-exclusion principle.

b) If f : R R is a function such that f (x) = 3x + 5, prove that f is one – one onto. Also find the inverse of f. put in function x=1,2,3,…….. f (x) = 3x + 5, f (1) = 3(1) + 5,=8 f (2) = 3(2) + 5,=11 f (3) = 3(3) + 5, = 14 1 8 2 11 3 14 which show that all value A is connected with only one image of B = one one function and all value of B have there domain value means = onto function 8 1 11 2 14 3 inverse of F Question 7: Marks ( 3 + 3 + 4) a) Find how many 3 digit numbers are even? How many 3 digit numbers are composed of odd digits ? iv) How many different 15 persons committees can be formed each containing at least 4 Project Managers and at least 3 Programmers from a set of 10 Project Managers and 10 Programmers ? 5 project manager and 10 programmer = 10C5 * 10C10 = ___ + 6 project manager and 9 programmer = 10C6 * 10C9 = ___ + 7 project manager and 8 programmer = 10C7 * 10C8 = ___ + 8 project manager and 7 programmer = 10C8 * 10C7 = ___ + 9 project manager and 6 programmer = 10C9 * 10C6 = ___ + 10 project manager and 5 programmer = 10C10 * 10C5 = ___ =========================total=============___________ c) Suppose we have ten rooms and wan t to assign five of them to five programmers a s offices and use the remaining five rooms for computer ter minals. Explain in how many ways this can be done. Question 8: Marks ( 4 +3 +3) a) What is Demorgan’s Law? Exp lain use of Demorgan’s law with example. In propositional logic and boolean algebra, De Morga n’s laws[1][2][3] are a pair of transformation rules that are both valid rules of inference. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation. The rules can be expressed in English as: The negation of a conjunction is the disjunction of the negations. The negation of a disjunction is the conjunction of the negations. or informally as: “not (A and B)” is the same as “(not A) or (not B)” and also, “not (A or B)” is the same as “(not A) and (not B)” The rules can be expressed in formal language with tw o propositions P and Q as: where:  ¬ is the negation operator (NOT) is the conjunction operator (A ND) ⇔ is the disjunction operator (OR) is a metalogical symbol meaning “can be replaced in a logical proof with” Applications of the rules include simplification of logical expressions in computer programs and digital circuit designs. De Morgan’s laws are an example of a more general concept of mathematical duality. b) Two dice, one red and one white are rolled. What is the probability that the white die turns up a smaller number than the red die ? c) Explain pigeon hole principle. Using this principle show that in any group of 36 people, we can always find 6 people who were born on the same day of week.