Category: discrete Mathematics

Discrete Mathematics – Relations ”; Previous Next Whenever sets are being discussed, the relationship between the elements of the sets is the next thing that comes up. Relations may exist between objects of the same set or between objects of two or more sets. Definition and Properties A binary relation R from set x to y (written as $xRy$ or $R(x,y)$) is a subset of the Cartesian product $x times y$. If the ordered pair of G is reversed, the relation also changes. Generally an n-ary relation R between sets $A_1, dots , and A_n$ is a subset of the n-ary product $A_1 times dots times A_n$. The minimum cardinality of a relation R is Zero and maximum is $n^2$ in this case. A binary relation R on a single set A is a subset of $A times A$. For two distinct sets, A and B, having cardinalities m and n respectively, the maximum cardinality of a relation R from A to B is mn. Domain and Range If there are two sets A and B, and relation R have order pair (x, y), then − The domain of R, Dom(R), is the set $lbrace x 😐 : (x, y) in R :for: some: y: in: B rbrace$ The range of R, Ran(R), is the set $lbrace y: |: (x, y) in R :for: some: x: in: Arbrace$ Examples Let, $A = lbrace 1, 2, 9 rbrace $ and $ B = lbrace 1, 3, 7 rbrace$ Case 1 − If relation R is ”equal to” then $R = lbrace (1, 1), (3, 3) rbrace$ Dom(R) = $lbrace 1, 3 rbrace , Ran(R) = lbrace 1, 3 rbrace$ Case 2 − If relation R is ”less than” then $R = lbrace (1, 3), (1, 7), (2, 3), (2, 7) rbrace$ Dom(R) = $lbrace 1, 2 rbrace , Ran(R) = lbrace 3, 7 rbrace$ Case 3 − If relation R is ”greater than” then $R = lbrace (2, 1), (9, 1), (9, 3), (9, 7) rbrace$ Dom(R) = $lbrace 2, 9 rbrace , Ran(R) = lbrace 1, 3, 7 rbrace$ Representation of Relations using Graph A relation can be represented using a directed graph. The number of vertices in the graph is equal to the number of elements in the set from which the relation has been defined. For each ordered pair (x, y) in the relation R, there will be a directed edge from the vertex ‘x’ to vertex ‘y’. If there is an ordered pair (x, x), there will be self- loop on vertex ‘x’. Suppose, there is a relation $R = lbrace (1, 1), (1,2), (3, 2) rbrace$ on set $S = lbrace 1, 2, 3 rbrace$, it can be represented by the following graph − Types of Relations The Empty Relation between sets X and Y, or on E, is the empty set $emptyset$ The Full Relation between sets X and Y is the set $X times Y$ The Identity Relation on set X is the set $lbrace (x, x) | x in X rbrace$ The Inverse Relation R” of a relation R is defined as − $R” = lbrace (b, a) | (a, b) in R rbrace$ Example − If $R = lbrace (1, 2), (2, 3) rbrace$ then $R” $ will be $lbrace (2, 1), (3, 2) rbrace$ A relation R on set A is called Reflexive if $forall a in A$ is related to a (aRa holds) Example − The relation $R = lbrace (a, a), (b, b) rbrace$ on set $X = lbrace a, b rbrace$ is reflexive. A relation R on set A is called Irreflexive if no $a in A$ is related to a (aRa does not hold). Example − The relation $R = lbrace (a, b), (b, a) rbrace$ on set $X = lbrace a, b rbrace$ is irreflexive. A relation R on set A is called Symmetric if $xRy$ implies $yRx$, $forall x in A$ and $forall y in A$. Example − The relation $R = lbrace (1, 2), (2, 1), (3, 2), (2, 3) rbrace$ on set $A = lbrace 1, 2, 3 rbrace$ is symmetric. A relation R on set A is called Anti-Symmetric if $xRy$ and $yRx$ implies $x = y : forall x in A$ and $forall y in A$. Example − The relation $R = lbrace (x, y)to N |:x leq y rbrace$ is anti-symmetric since $x leq y$ and $y leq x$ implies $x = y$. A relation R on set A is called Transitive if $xRy$ and $yRz$ implies $xRz, forall x,y,z in A$. Example − The relation $R = lbrace (1, 2), (2, 3), (1, 3) rbrace$ on set $A = lbrace 1, 2, 3 rbrace$ is transitive. A relation is an Equivalence Relation if it is reflexive, symmetric, and transitive. Example − The relation $R = lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) rbrace$ on set $A = lbrace 1, 2, 3 rbrace$ is an equivalence relation since it is reflexive, symmetric, and transitive. Print Page Previous Next Advertisements ”;

Discrete Mathematics – Counting Theory ”; Previous Next In daily lives, many a times one needs to find out the number of all possible outcomes for a series of events. For instance, in how many ways can a panel of judges comprising of 6 men and 4 women be chosen from among 50 men and 38 women? How many different 10 lettered PAN numbers can be generated such that the first five letters are capital alphabets, the next four are digits and the last is again a capital letter. For solving these problems, mathematical theory of counting are used. Counting mainly encompasses fundamental counting rule, the permutation rule, and the combination rule. The Rules of Sum and Product The Rule of Sum and Rule of Product are used to decompose difficult counting problems into simple problems. The Rule of Sum − If a sequence of tasks $T_1, T_2, dots, T_m$ can be done in $w_1, w_2, dots w_m$ ways respectively (the condition is that no tasks can be performed simultaneously), then the number of ways to do one of these tasks is $w_1 + w_2 + dots +w_m$. If we consider two tasks A and B which are disjoint (i.e. $A cap B = emptyset$), then mathematically $|A cup B| = |A| + |B|$ The Rule of Product − If a sequence of tasks $T_1, T_2, dots, T_m$ can be done in $w_1, w_2, dots w_m$ ways respectively and every task arrives after the occurrence of the previous task, then there are $w_1 times w_2 times dots times w_m$ ways to perform the tasks. Mathematically, if a task B arrives after a task A, then $|A times B| = |A|times|B|$ Example Question − A boy lives at X and wants to go to School at Z. From his home X he has to first reach Y and then Y to Z. He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z. How many ways are there to go from X to Z? Solution − From X to Y, he can go in $3 + 2 = 5$ ways (Rule of Sum). Thereafter, he can go Y to Z in $4 + 5 = 9$ ways (Rule of Sum). Hence from X to Z he can go in $5 times 9 = 45$ ways (Rule of Product). Permutations A permutation is an arrangement of some elements in which order matters. In other words a Permutation is an ordered Combination of elements. Examples From a set S ={x, y, z} by taking two at a time, all permutations are − $ xy, yx, xz, zx, yz, zy $. We have to form a permutation of three digit numbers from a set of numbers $S = lbrace 1, 2, 3 rbrace$. Different three digit numbers will be formed when we arrange the digits. The permutation will be = 123, 132, 213, 231, 312, 321 Number of Permutations The number of permutations of ‘n’ different things taken ‘r’ at a time is denoted by $n_{P_{r}}$ $$n_{P_{r}} = frac{n!}{(n – r)!}$$ where $n! = 1.2.3. dots (n – 1).n$ Proof − Let there be ‘n’ different elements. There are n number of ways to fill up the first place. After filling the first place (n-1) number of elements is left. Hence, there are (n-1) ways to fill up the second place. After filling the first and second place, (n-2) number of elements is left. Hence, there are (n-2) ways to fill up the third place. We can now generalize the number of ways to fill up r-th place as [n – (r–1)] = n–r+1 So, the total no. of ways to fill up from first place up to r-th-place − $n_{ P_{ r } } = n (n-1) (n-2)….. (n-r + 1)$ $= [n(n-1)(n-2) … (n-r + 1)] [(n-r)(n-r-1) dots 3.2.1] / [(n-r)(n-r-1) dots 3.2.1]$ Hence, $n_{ P_{ r } } = n! / (n-r)!$ Some important formulas of permutation If there are n elements of which $a_1$ are alike of some kind, $a_2$ are alike of another kind; $a_3$ are alike of third kind and so on and $a_r$ are of $r^{th}$ kind, where $(a_1 + a_2 + … a_r) = n$. Then, number of permutations of these n objects is = $n! / [(a_1!(a_2!) dots (a_r!)]$. Number of permutations of n distinct elements taking n elements at a time = $n_{P_n} = n!$ The number of permutations of n dissimilar elements taking r elements at a time, when x particular things always occupy definite places = $n-x_{p_{r-x}}$ The number of permutations of n dissimilar elements when r specified things always come together is − $r! (n−r+1)!$ The number of permutations of n dissimilar elements when r specified things never come together is − $n!–[r! (n−r+1)!]$ The number of circular permutations of n different elements taken x elements at time = $^np_{x}/x$ The number of circular permutations of n different things = $^np_{n}/n$ Some Problems Problem 1 − From a bunch of 6 different cards, how many ways we can permute it? Solution − As we are taking 6 cards at a time from a deck of 6 cards, the permutation will be $^6P_{6} = 6! = 720$ Problem 2 − In how many ways can the letters of the word ”READER” be arranged? Solution − There are 6 letters word (2 E, 1 A, 1D and 2R.) in the word ”READER”. The permutation will be $= 6! /: [(2!) (1!)(1!)(2!)] = 180.$ Problem 3 − In how ways can the letters of the word ”ORANGE” be arranged so that the consonants occupy only the even positions? Solution − There are 3 vowels and 3 consonants in the word ”ORANGE”. Number of ways of arranging the consonants among themselves $= ^3P_{3} = 3! = 6$. The remaining 3 vacant places will be filled up by 3 vowels in $^3P_{3}

Discrete Mathematics – Rules of Inference ”; Previous Next To deduce new statements from the statements whose truth that we already know, Rules of Inference are used. What are Rules of Inference for? Mathematical logic is often used for logical proofs. Proofs are valid arguments that determine the truth values of mathematical statements. An argument is a sequence of statements. The last statement is the conclusion and all its preceding statements are called premises (or hypothesis). The symbol “$therefore$”, (read therefore) is placed before the conclusion. A valid argument is one where the conclusion follows from the truth values of the premises. Rules of Inference provide the templates or guidelines for constructing valid arguments from the statements that we already have. Table of Rules of Inference Rule of Inference Name Rule of Inference Name $$begin{matrix} P \ hline therefore P lor Q end{matrix}$$ Addition $$begin{matrix} P lor Q \ lnot P \ hline therefore Q end{matrix}$$ Disjunctive Syllogism $$begin{matrix} P \ Q \ hline therefore P land Q end{matrix}$$ Conjunction $$begin{matrix} P rightarrow Q \ Q rightarrow R \ hline therefore P rightarrow R end{matrix}$$ Hypothetical Syllogism $$begin{matrix} P land Q\ hline therefore P end{matrix}$$ Simplification $$begin{matrix} ( P rightarrow Q ) land (R rightarrow S) \ P lor R \ hline therefore Q lor S end{matrix}$$ Constructive Dilemma $$begin{matrix} P rightarrow Q \ P \ hline therefore Q end{matrix}$$ Modus Ponens $$begin{matrix} (P rightarrow Q) land (R rightarrow S) \ lnot Q lor lnot S \ hline therefore lnot P lor lnot R end{matrix}$$ Destructive Dilemma $$begin{matrix} P rightarrow Q \ lnot Q \ hline therefore lnot P end{matrix}$$ Modus Tollens Addition If P is a premise, we can use Addition rule to derive $ P lor Q $. $$begin{matrix} P \ hline therefore P lor Q end{matrix}$$ Example Let P be the proposition, “He studies very hard” is true Therefore − “Either he studies very hard Or he is a very bad student.” Here Q is the proposition “he is a very bad student”. Conjunction If P and Q are two premises, we can use Conjunction rule to derive $ P land Q $. $$begin{matrix} P \ Q \ hline therefore P land Q end{matrix}$$ Example Let P − “He studies very hard” Let Q − “He is the best boy in the class” Therefore − “He studies very hard and he is the best boy in the class” Simplification If $P land Q$ is a premise, we can use Simplification rule to derive P. $$begin{matrix} P land Q\ hline therefore P end{matrix}$$ Example “He studies very hard and he is the best boy in the class”, $P land Q$ Therefore − “He studies very hard” Modus Ponens If P and $P rightarrow Q$ are two premises, we can use Modus Ponens to derive Q. $$begin{matrix} P rightarrow Q \ P \ hline therefore Q end{matrix}$$ Example “If you have a password, then you can log on to facebook”, $P rightarrow Q$ “You have a password”, P Therefore − “You can log on to facebook” Modus Tollens If $P rightarrow Q$ and $lnot Q$ are two premises, we can use Modus Tollens to derive $lnot P$. $$begin{matrix} P rightarrow Q \ lnot Q \ hline therefore lnot P end{matrix}$$ Example “If you have a password, then you can log on to facebook”, $P rightarrow Q$ “You cannot log on to facebook”, $lnot Q$ Therefore − “You do not have a password “ Disjunctive Syllogism If $lnot P$ and $P lor Q$ are two premises, we can use Disjunctive Syllogism to derive Q. $$begin{matrix} lnot P \ P lor Q \ hline therefore Q end{matrix}$$ Example “The ice cream is not vanilla flavored”, $lnot P$ “The ice cream is either vanilla flavored or chocolate flavored”, $P lor Q$ Therefore − “The ice cream is chocolate flavored” Hypothetical Syllogism If $P rightarrow Q$ and $Q rightarrow R$ are two premises, we can use Hypothetical Syllogism to derive $P rightarrow R$ $$begin{matrix} P rightarrow Q \ Q rightarrow R \ hline therefore P rightarrow R end{matrix}$$ Example “If it rains, I shall not go to school”, $P rightarrow Q$ “If I don”t go to school, I won”t need to do homework”, $Q rightarrow R$ Therefore − “If it rains, I won”t need to do homework” Constructive Dilemma If $( P rightarrow Q ) land (R rightarrow S)$ and $P lor R$ are two premises, we can use constructive dilemma to derive $Q lor S$. $$begin{matrix} ( P rightarrow Q ) land (R rightarrow S) \ P lor R \ hline therefore Q lor S end{matrix}$$ Example “If it rains, I will take a leave”, $( P rightarrow Q )$ “If it is hot outside, I will go for a shower”, $(R rightarrow S)$ “Either it will rain or it is hot outside”, $P lor R$ Therefore − “I will take a leave or I will go for a shower” Destructive Dilemma If $(P rightarrow Q) land (R rightarrow S)$ and $ lnot Q lor lnot S $ are two premises, we can use destructive dilemma to derive $lnot P lor lnot R$. $$begin{matrix} (P rightarrow Q) land (R rightarrow S) \ lnot Q lor lnot S \ hline therefore lnot P lor lnot R end{matrix}$$ Example “If it rains, I will take a leave”, $(P rightarrow Q )$ “If it is hot outside, I will go for a shower”, $(R rightarrow S)$ “Either I will not take a leave or I will not go for a shower”, $lnot Q lor lnot S$ Therefore − “Either it does not rain or it is not hot outside” Print Page Previous Next Advertisements ”;