Category: discrete Mathematics

Discuss Discrete Mathematics ”; Previous Next Discrete Mathematics is a branch of mathematics involving discrete elements that uses algebra and arithmetic. It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem-solving capabilities. This tutorial explains the fundamental concepts of Sets, Relations and Functions, Mathematical Logic, Group theory, Counting Theory, Probability, Mathematical Induction and Recurrence Relations, Graph Theory, Trees and Boolean Algebra. Print Page Previous Next Advertisements ”;

Discrete Mathematics – Group Theory ”; Previous Next Semigroup A finite or infinite set $‘S’$ with a binary operation $‘omicron’$ (Composition) is called semigroup if it holds following two conditions simultaneously − Closure − For every pair $(a, b) in S, :(a omicron b)$ has to be present in the set $S$. Associative − For every element $a, b, c in S, (a omicron b) omicron c = a omicron (b omicron c)$ must hold. Example The set of positive integers (excluding zero) with addition operation is a semigroup. For example, $ S = lbrace 1, 2, 3, dots rbrace $ Here closure property holds as for every pair $(a, b) in S, (a + b)$ is present in the set S. For example, $1 + 2 = 3 in S]$ Associative property also holds for every element $a, b, c in S, (a + b) + c = a + (b + c)$. For example, $(1 + 2) + 3 = 1 + (2 + 3) = 5$ Monoid A monoid is a semigroup with an identity element. The identity element (denoted by $e$ or E) of a set S is an element such that $(a omicron e) = a$, for every element $a in S$. An identity element is also called a unit element. So, a monoid holds three properties simultaneously − Closure, Associative, Identity element. Example The set of positive integers (excluding zero) with multiplication operation is a monoid. $S = lbrace 1, 2, 3, dots rbrace $ Here closure property holds as for every pair $(a, b) in S, (a times b)$ is present in the set S. [For example, $1 times 2 = 2 in S$ and so on] Associative property also holds for every element $a, b, c in S, (a times b) times c = a times (b times c)$ [For example, $(1 times 2) times 3 = 1 times (2 times 3) = 6$ and so on] Identity property also holds for every element $a in S, (a times e) = a$ [For example, $(2 times 1) = 2, (3 times 1) = 3$ and so on]. Here identity element is 1. Group A group is a monoid with an inverse element. The inverse element (denoted by I) of a set S is an element such that $(a omicron I) = (I omicron a) = a$, for each element $a in S$. So, a group holds four properties simultaneously – i) Closure, ii) Associative, iii) Identity element, iv) Inverse element. The order of a group G is the number of elements in G and the order of an element in a group is the least positive integer n such that an is the identity element of that group G. Examples The set of $N times N$ non-singular matrices form a group under matrix multiplication operation. The product of two $N times N$ non-singular matrices is also an $N times N$ non-singular matrix which holds closure property. Matrix multiplication itself is associative. Hence, associative property holds. The set of $N times N$ non-singular matrices contains the identity matrix holding the identity element property. As all the matrices are non-singular they all have inverse elements which are also nonsingular matrices. Hence, inverse property also holds. Abelian Group An abelian group G is a group for which the element pair $(a,b) in G$ always holds commutative law. So, a group holds five properties simultaneously – i) Closure, ii) Associative, iii) Identity element, iv) Inverse element, v) Commutative. Example The set of positive integers (including zero) with addition operation is an abelian group. $G = lbrace 0, 1, 2, 3, dots rbrace$ Here closure property holds as for every pair $(a, b) in S, (a + b)$ is present in the set S. [For example, $1 + 2 = 2 in S$ and so on] Associative property also holds for every element $a, b, c in S, (a + b) + c = a + (b + c)$ [For example, $(1 +2) + 3 = 1 + (2 + 3) = 6$ and so on] Identity property also holds for every element $a in S, (a times e) = a$ [For example, $(2 times 1) = 2, (3 times 1) = 3$ and so on]. Here, identity element is 1. Commutative property also holds for every element $a in S, (a times b) = (b times a)$ [For example, $(2 times 3) = (3 times 2) = 3$ and so on] Cyclic Group and Subgroup A cyclic group is a group that can be generated by a single element. Every element of a cyclic group is a power of some specific element which is called a generator. A cyclic group can be generated by a generator ‘g’, such that every other element of the group can be written as a power of the generator ‘g’. Example The set of complex numbers $lbrace 1,-1, i, -i rbrace$ under multiplication operation is a cyclic group. There are two generators − $i$ and $–i$ as $i^1 = i, i^2 = -1, i^3 = -i, i^4 = 1$ and also $(–i)^1 = -i, (–i)^2 = -1, (–i)^3 = i, (–i)^4 = 1$ which covers all the elements of the group. Hence, it is a cyclic group. Note − A cyclic group is always an abelian group but not every abelian group is a cyclic group. The rational numbers under addition is not cyclic but is abelian. A subgroup H is a subset of a group G (denoted by $H ≤ G$) if it satisfies the four properties simultaneously − Closure, Associative, Identity element, and Inverse. A subgroup H of a group G that does not include the whole group G is called a proper subgroup (Denoted by $H < G$). A subgroup of a cyclic group is cyclic and a abelian subgroup is also abelian. Example Let a group $G = lbrace 1, i, -1, -i rbrace$ Then some subgroups are $H_1 = lbrace 1 rbrace,

Discrete Mathematics – Propositional Logic ”; Previous Next The rules of mathematical logic specify methods of reasoning mathematical statements. Greek philosopher, Aristotle, was the pioneer of logical reasoning. Logical reasoning provides the theoretical base for many areas of mathematics and consequently computer science. It has many practical applications in computer science like design of computing machines, artificial intelligence, definition of data structures for programming languages etc. Propositional Logic is concerned with statements to which the truth values, “true” and “false”, can be assigned. The purpose is to analyze these statements either individually or in a composite manner. Prepositional Logic – Definition A proposition is a collection of declarative statements that has either a truth value “true” or a truth value “false”. A propositional consists of propositional variables and connectives. We denote the propositional variables by capital letters (A, B, etc). The connectives connect the propositional variables. Some examples of Propositions are given below − “Man is Mortal”, it returns truth value “TRUE” “12 + 9 = 3 – 2”, it returns truth value “FALSE” The following is not a Proposition − “A is less than 2”. It is because unless we give a specific value of A, we cannot say whether the statement is true or false. Connectives In propositional logic generally we use five connectives which are − OR ($lor$) AND ($land$) Negation/ NOT ($lnot$) Implication / if-then ($rightarrow$) If and only if ($Leftrightarrow$). OR ($lor$) − The OR operation of two propositions A and B (written as $A lor B$) is true if at least any of the propositional variable A or B is true. The truth table is as follows − A B A ∨ B True True True True False True False True True False False False AND ($land$) − The AND operation of two propositions A and B (written as $A land B$) is true if both the propositional variable A and B is true. The truth table is as follows − A B A ∧ B True True True True False False False True False False False False Negation ($lnot$) − The negation of a proposition A (written as $lnot A$) is false when A is true and is true when A is false. The truth table is as follows − A ¬ A True False False True Implication / if-then ($rightarrow$) − An implication $A rightarrow B$ is the proposition “if A, then B”. It is false if A is true and B is false. The rest cases are true. The truth table is as follows − A B A → B True True True True False False False True True False False True If and only if ($ Leftrightarrow $) − $A Leftrightarrow B$ is bi-conditional logical connective which is true when p and q are same, i.e. both are false or both are true. The truth table is as follows − A B A ⇔ B True True True True False False False True False False False True Tautologies A Tautology is a formula which is always true for every value of its propositional variables. Example − Prove $lbrack (A rightarrow B) land A rbrack rightarrow B$ is a tautology The truth table is as follows − A B A → B (A → B) ∧ A [( A → B ) ∧ A] → B True True True True True True False False False True False True True False True False False True False True As we can see every value of $lbrack (A rightarrow B) land A rbrack rightarrow B$ is “True”, it is a tautology. Contradictions A Contradiction is a formula which is always false for every value of its propositional variables. Example − Prove $(A lor B) land lbrack ( lnot A) land (lnot B) rbrack$ is a contradiction The truth table is as follows − A B A ∨ B ¬ A ¬ B (¬ A) ∧ ( ¬ B) (A ∨ B) ∧ [( ¬ A) ∧ (¬ B)] True True True False False False False True False True False True False False False True True True False False False False False False True True True False As we can see every value of $(A lor B) land lbrack ( lnot A) land (lnot B) rbrack$ is “False”, it is a contradiction. Contingency A Contingency is a formula which has both some true and some false values for every value of its propositional variables. Example − Prove $(A lor B) land (lnot A)$ a contingency The truth table is as follows − A B A ∨ B ¬ A (A ∨ B) ∧ (¬ A) True True True False False True False True False False False True True True True False False False True False As we can see every value of $(A lor B) land (lnot A)$ has both “True” and “False”, it is a contingency. Propositional Equivalences Two statements X and Y are logically equivalent if any of the following two conditions hold − The truth tables of each statement have the same truth values. The bi-conditional statement $X Leftrightarrow Y$ is a tautology. Example − Prove $lnot (A lor B) and lbrack (lnot A) land (lnot B) rbrack$ are equivalent Testing by 1st method (Matching truth table) A B A ∨ B ¬ (A ∨ B) ¬ A ¬ B [(¬ A) ∧ (¬ B)] True True True False False False False True False True False False True False False True True False True False False False False False True True True True Here, we can see the truth values of $lnot (A lor B) and lbrack (lnot A) land (lnot B) rbrack$ are same, hence the statements are equivalent. Testing by 2nd method (Bi-conditionality) A B ¬ (A ∨ B ) [(¬ A) ∧ (¬ B)] [¬ (A ∨ B)] ⇔ [(¬ A ) ∧ (¬ B)] True True False False True True False False False True False True False False True False False True True True

Boolean Expressions & Functions ”; Previous Next Boolean algebra is algebra of logic. It deals with variables that can have two discrete values, 0 (False) and 1 (True); and operations that have logical significance. The earliest method of manipulating symbolic logic was invented by George Boole and subsequently came to be known as Boolean Algebra. Boolean algebra has now become an indispensable tool in computer science for its wide applicability in switching theory, building basic electronic circuits and design of digital computers. Boolean Functions A Boolean function is a special kind of mathematical function $f: X^n rightarrow X$ of degree n, where $X = lbrace {0, 1} rbrace$ is a Boolean domain and n is a non-negative integer. It describes the way how to derive Boolean output from Boolean inputs. Example − Let, $F(A, B) = A’B’$. This is a function of degree 2 from the set of ordered pairs of Boolean variables to the set $lbrace {0, 1} rbrace$ where $F(0, 0) = 1, F(0, 1) = 0, F(1, 0) = 0$ and $F(1, 1) = 0$ Boolean Expressions A Boolean expression always produces a Boolean value. A Boolean expression is composed of a combination of the Boolean constants (True or False), Boolean variables and logical connectives. Each Boolean expression represents a Boolean function. Example − $AB’C$ is a Boolean expression. Boolean Identities Double Complement Law $sim(sim A) = A$ Complement Law $A + sim A = 1$ (OR Form) $A . sim A = 0$ (AND Form) Idempotent Law $A + A = A$ (OR Form) $A . A = A$ (AND Form) Identity Law $A + 0 = A$ (OR Form) $A . 1 = A$ (AND Form) Dominance Law $A + 1 = 1$ (OR Form) $A . 0 = 0$ (AND Form) Commutative Law $A + B = B + A$ (OR Form) $A. B = B . A$ (AND Form) Associative Law $A + (B + C) = (A + B) + C$ (OR Form) $A. (B . C) = (A . B) . C$ (AND Form) Absorption Law $A. (A + B) = A$ $A + (A . B) = A$ Simplification Law $A . (sim A + B) = A . B$ $A + (sim A . B) = A + B$ Distributive Law $A + (B . C) = (A + B) . (A + C)$ $A . (B + C) = (A . B) + (A . C)$ De-Morgan”s Law $sim (A . B) = sim A + sim B$ $sim (A+ B) = sim A . sim B$ Canonical Forms For a Boolean expression there are two kinds of canonical forms − The sum of minterms (SOM) form The product of maxterms (POM) form The Sum of Minterms (SOM) or Sum of Products (SOP) form A minterm is a product of all variables taken either in their direct or complemented form. Any Boolean function can be expressed as a sum of its 1-minterms and the inverse of the function can be expressed as a sum of its 0-minterms. Hence, F (list of variables) = ∑ (list of 1-minterm indices) and F” (list of variables) = ∑ (list of 0-minterm indices) A B C Term Minterm 0 0 0 x’y’z’ m0 0 0 1 x’y’z m1 0 1 0 x’yz’ m2 0 1 1 x’yz m3 1 0 0 xy’z’ m4 1 0 1 xy’z m5 1 1 0 xyz’ m6 1 1 1 xyz m7 Example Let, $F(x, y, z) = x” y” z” + x y” z + x y z” + x y z $ Or, $F(x, y, z) = m_0 + m_5 + m_6 + m_7$ Hence, $F(x, y, z) = sum (0, 5, 6, 7)$ Now we will find the complement of $F(x, y, z)$ $F” (x, y, z) = x” y z + x” y” z + x” y z” + x y” z”$ Or, $F”(x, y, z) = m_3 + m_1 + m_2 + m_4$ Hence, $F”(x, y, z) = sum (3, 1, 2, 4) = sum (1, 2, 3, 4)$ The Product of Maxterms (POM) or Product of Sums (POS) form A maxterm is addition of all variables taken either in their direct or complemented form. Any Boolean function can be expressed as a product of its 0-maxterms and the inverse of the function can be expressed as a product of its 1-maxterms. Hence, F(list of variables) = $pi$ (list of 0-maxterm indices). and F”(list of variables) = $pi$ (list of 1-maxterm indices). A B C Term Maxterm 0 0 0 x + y + z M0 0 0 1 x + y + z’ M1 0 1 0 x + y’ + z M2 0 1 1 x + y’ + z’ M3 1 0 0 x’ + y + z M4 1 0 1 x’ + y + z’ M5 1 1 0 x’ + y’ + z M6 1 1 1 x’ + y’ + z’ M7 Example Let $F(x, y, z) = (x + y + z) . (x+y+z”) . (x+y”+z) . (x”+y+z)$ Or, $F(x, y, z) = M_0 . M_1 . M_2 . M_4$ Hence, $F (x, y, z) = pi (0, 1, 2, 4)$ $F””(x, y, z) = (x+y”+z”) . (x”+y+z”) . (x”+y”+z) . (x”+y”+z”)$ Or, $F(x, y, z) = M_3 . M_5 . M_6 . M_7$ Hence, $F ”(x, y, z) = pi (3, 5, 6, 7)$ Logic Gates Boolean functions are implemented by using logic gates. The following are the logic gates − NOT Gate A NOT gate inverts a single bit input to a single bit of output. A ~A 0 1 1 0 AND Gate An AND gate is a logic gate that gives a high output only if all its inputs are high, otherwise it gives low output. A dot (.) is used to show the AND operation. A B A.B 0 0 0 0 1 0 1 0 0 1 1 1 OR Gate An OR

Discrete Mathematics – Sets ”; Previous Next German mathematician G. Cantor introduced the concept of sets. He had defined a set as a collection of definite and distinguishable objects selected by the means of certain rules or description. Set theory forms the basis of several other fields of study like counting theory, relations, graph theory and finite state machines. In this chapter, we will cover the different aspects of Set Theory. Set – Definition A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set. Some Example of Sets A set of all positive integers A set of all the planets in the solar system A set of all the states in India A set of all the lowercase letters of the alphabet Representation of a Set Sets can be represented in two ways − Roster or Tabular Form Set Builder Notation Roster or Tabular Form The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas. Example 1 − Set of vowels in English alphabet, $A = lbrace a,e,i,o,u rbrace$ Example 2 − Set of odd numbers less than 10, $B = lbrace 1,3,5,7,9 rbrace$ Set Builder Notation The set is defined by specifying a property that elements of the set have in common. The set is described as $A = lbrace x : p(x) rbrace$ Example 1 − The set $lbrace a,e,i,o,u rbrace$ is written as − $A = lbrace x : text{x is a vowel in English alphabet} rbrace$ Example 2 − The set $lbrace 1,3,5,7,9 rbrace$ is written as − $B = lbrace x : 1 le x lt 10 and (x % 2) ne 0 rbrace$ If an element x is a member of any set S, it is denoted by $x in S$ and if an element y is not a member of set S, it is denoted by $y notin S$. Example − If $S = lbrace1, 1.2, 1.7, 2rbrace , 1 in S$ but $1.5 notin S$ Some Important Sets N − the set of all natural numbers = $lbrace1, 2, 3, 4, …..rbrace$ Z − the set of all integers = $lbrace….., -3, -2, -1, 0, 1, 2, 3, …..rbrace$ Z&plus; − the set of all positive integers Q − the set of all rational numbers R − the set of all real numbers W − the set of all whole numbers Cardinality of a Set Cardinality of a set S, denoted by $|S|$, is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is $infty$. Example − $|lbrace 1, 4, 3, 5 rbrace | = 4, | lbrace 1, 2, 3, 4, 5, dots rbrace | = infty$ If there are two sets X and Y, $|X| = |Y|$ denotes two sets X and Y having same cardinality. It occurs when the number of elements in X is exactly equal to the number of elements in Y. In this case, there exists a bijective function ‘f’ from X to Y. $|X| le |Y|$ denotes that set X’s cardinality is less than or equal to set Y’s cardinality. It occurs when number of elements in X is less than or equal to that of Y. Here, there exists an injective function ‘f’ from X to Y. $|X| lt |Y|$ denotes that set X’s cardinality is less than set Y’s cardinality. It occurs when number of elements in X is less than that of Y. Here, the function ‘f’ from X to Y is injective function but not bijective. $If |X| le |Y|$ and $|X| ge |Y|$ then $|X| = |Y|$. The sets X and Y are commonly referred as equivalent sets. Types of Sets Sets can be classified into many types. Some of which are finite, infinite, subset, universal, proper, singleton set, etc. Finite Set A set which contains a definite number of elements is called a finite set. Example − $S = lbrace x 😐 😡 in N$ and $70 gt x gt 50 rbrace$ Infinite Set A set which contains infinite number of elements is called an infinite set. Example − $S = lbrace x : | : x in N $ and $ x gt 10 rbrace$ Subset A set X is a subset of set Y (Written as $X subseteq Y$) if every element of X is an element of set Y. Example 1 − Let, $X = lbrace 1, 2, 3, 4, 5, 6 rbrace$ and $Y = lbrace 1, 2 rbrace$. Here set Y is a subset of set X as all the elements of set Y is in set X. Hence, we can write $Y subseteq X$. Example 2 − Let, $X = lbrace 1, 2, 3 rbrace$ and $Y = lbrace 1, 2, 3 rbrace$. Here set Y is a subset (Not a proper subset) of set X as all the elements of set Y is in set X. Hence, we can write $Y subseteq X$. Proper Subset The term “proper subset” can be defined as “subset of but not equal to”. A Set X is a proper subset of set Y (Written as $ X subset Y $) if every element of X is an element of set Y and $|X| lt |Y|$. Example − Let, $X = lbrace 1, 2, 3, 4, 5, 6 rbrace$ and $Y = lbrace 1, 2 rbrace$. Here set $Y subset X$ since all elements in $Y$ are contained in $X$ too and $X$ has at least one element is more than set $Y$. Universal Set It is a collection of all elements in a particular context or application. All the sets in that context or application are

Discrete Mathematics – Quick Guide ”; Previous Next Discrete Mathematics – Introduction Mathematics can be broadly classified into two categories − Continuous Mathematics − It is based upon continuous number line or the real numbers. It is characterized by the fact that between any two numbers, there are almost always an infinite set of numbers. For example, a function in continuous mathematics can be plotted in a smooth curve without breaks. Discrete Mathematics − It involves distinct values; i.e. between any two points, there are a countable number of points. For example, if we have a finite set of objects, the function can be defined as a list of ordered pairs having these objects, and can be presented as a complete list of those pairs. Topics in Discrete Mathematics Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter − Sets, Relations and Functions Mathematical Logic Group theory Counting Theory Probability Mathematical Induction and Recurrence Relations Graph Theory Trees Boolean Algebra We will discuss each of these concepts in the subsequent chapters of this tutorial. Discrete Mathematics – Sets German mathematician G. Cantor introduced the concept of sets. He had defined a set as a collection of definite and distinguishable objects selected by the means of certain rules or description. Set theory forms the basis of several other fields of study like counting theory, relations, graph theory and finite state machines. In this chapter, we will cover the different aspects of Set Theory. Set – Definition A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set. Some Example of Sets A set of all positive integers A set of all the planets in the solar system A set of all the states in India A set of all the lowercase letters of the alphabet Representation of a Set Sets can be represented in two ways − Roster or Tabular Form Set Builder Notation Roster or Tabular Form The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas. Example 1 − Set of vowels in English alphabet, $A = lbrace a,e,i,o,u rbrace$ Example 2 − Set of odd numbers less than 10, $B = lbrace 1,3,5,7,9 rbrace$ Set Builder Notation The set is defined by specifying a property that elements of the set have in common. The set is described as $A = lbrace x : p(x) rbrace$ Example 1 − The set $lbrace a,e,i,o,u rbrace$ is written as − $A = lbrace x : text{x is a vowel in English alphabet} rbrace$ Example 2 − The set $lbrace 1,3,5,7,9 rbrace$ is written as − $B = lbrace x : 1 le x lt 10 and (x % 2) ne 0 rbrace$ If an element x is a member of any set S, it is denoted by $x in S$ and if an element y is not a member of set S, it is denoted by $y notin S$. Example − If $S = lbrace1, 1.2, 1.7, 2rbrace , 1 in S$ but $1.5 notin S$ Some Important Sets N − the set of all natural numbers = $lbrace1, 2, 3, 4, …..rbrace$ Z − the set of all integers = $lbrace….., -3, -2, -1, 0, 1, 2, 3, …..rbrace$ Z&plus; − the set of all positive integers Q − the set of all rational numbers R − the set of all real numbers W − the set of all whole numbers Cardinality of a Set Cardinality of a set S, denoted by $|S|$, is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is $infty$. Example − $|lbrace 1, 4, 3, 5 rbrace | = 4, | lbrace 1, 2, 3, 4, 5, dots rbrace | = infty$ If there are two sets X and Y, $|X| = |Y|$ denotes two sets X and Y having same cardinality. It occurs when the number of elements in X is exactly equal to the number of elements in Y. In this case, there exists a bijective function ‘f’ from X to Y. $|X| le |Y|$ denotes that set X’s cardinality is less than or equal to set Y’s cardinality. It occurs when number of elements in X is less than or equal to that of Y. Here, there exists an injective function ‘f’ from X to Y. $|X| lt |Y|$ denotes that set X’s cardinality is less than set Y’s cardinality. It occurs when number of elements in X is less than that of Y. Here, the function ‘f’ from X to Y is injective function but not bijective. $If |X| le |Y|$ and $|X| ge |Y|$ then $|X| = |Y|$. The sets X and Y are commonly referred as equivalent sets. Types of Sets Sets can be classified into many types. Some of which are finite, infinite, subset, universal, proper, singleton set, etc. Finite Set A set which contains a definite number of elements is called a finite set. Example − $S = lbrace x 😐 😡 in N$ and $70 gt x gt 50 rbrace$ Infinite Set A set which contains infinite number of elements is called an infinite set. Example − $S = lbrace x : | : x in N $ and $ x gt 10 rbrace$ Subset A set X is a subset of set Y (Written as $X subseteq Y$) if every element of X is an element of set Y. Example 1 − Let, $X = lbrace 1, 2, 3, 4, 5, 6 rbrace$ and $Y = lbrace 1, 2 rbrace$. Here set Y is a subset of set X

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 ”;

Graph & Graph Models ”; Previous Next The previous part brought forth the different tools for reasoning, proofing and problem solving. In this part, we will study the discrete structures that form the basis of formulating many a real-life problem. The two discrete structures that we will cover are graphs and trees. A graph is a set of points, called nodes or vertices, which are interconnected by a set of lines called edges. The study of graphs, or graph theory is an important part of a number of disciplines in the fields of mathematics, engineering and computer science. What is a Graph? Definition − A graph (denoted as $G = (V, E)$) consists of a non-empty set of vertices or nodes V and a set of edges E. Example − Let us consider, a Graph is $G = (V, E)$ where $V = lbrace a, b, c, d rbrace $ and $E = lbrace lbrace a, b rbrace, lbrace a, c rbrace, lbrace b, c rbrace, lbrace c, d rbrace rbrace$ Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the number of edges incident with the vertex V. Vertex Degree Even / Odd a 2 even b 2 even c 3 odd d 1 odd Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex and if the degree of a vertex is odd, the vertex is called an odd vertex. Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the above graph the degree of the graph is 3. The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal to twice the number of edges. Types of Graphs There are different types of graphs, which we will learn in the following section. Null Graph A null graph has no edges. The null graph of $n$ vertices is denoted by $N_n$ Simple Graph A graph is called simple graph/strict graph if the graph is undirected and does not contain any loops or multiple edges. Multi-Graph If in a graph multiple edges between the same set of vertices are allowed, it is called Multigraph. In other words, it is a graph having at least one loop or multiple edges. Directed and Undirected Graph A graph $G = (V, E)$ is called a directed graph if the edge set is made of ordered vertex pair and a graph is called undirected if the edge set is made of unordered vertex pair. Connected and Disconnected Graph A graph is connected if any two vertices of the graph are connected by a path; while a graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph G is disconnected, then every maximal connected subgraph of $G$ is called a connected component of the graph $G$. Regular Graph A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of degree $r$, the degree of each vertex of $G$ is r. Complete Graph A graph is called complete graph if every two vertices pair are joined by exactly one edge. The complete graph with n vertices is denoted by $K_n$ Cycle Graph If a graph consists of a single cycle, it is called cycle graph. The cycle graph with n vertices is denoted by $C_n$ Bipartite Graph If the vertex-set of a graph G can be split into two disjoint sets, $V_1$ and $V_2$, in such a way that each edge in the graph joins a vertex in $V_1$ to a vertex in $V_2$, and there are no edges in G that connect two vertices in $V_1$ or two vertices in $V_2$, then the graph $G$ is called a bipartite graph. Complete Bipartite Graph A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to every single vertex in the second set. The complete bipartite graph is denoted by $K_{x,y}$ where the graph $G$ contains $x$ vertices in the first set and $y$ vertices in the second set. Representation of Graphs There are mainly two ways to represent a graph − Adjacency Matrix Adjacency List Adjacency Matrix An Adjacency Matrix $A[V][V]$ is a 2D array of size $V times V$ where $V$ is the number of vertices in a undirected graph. If there is an edge between $V_x$ to $V_y$ then the value of $A[V_x][V_y]=1$ and $A[V_y][V_x]=1$, otherwise the value will be zero. And for a directed graph, if there is an edge between $V_x$ to $V_y$, then the value of $A[V_x][V_y]=1$, otherwise the value will be zero. Adjacency Matrix of an Undirected Graph Let us consider the following undirected graph and construct the adjacency matrix − Adjacency matrix of the above undirected graph will be − a b c d a 0 1 1 0 b 1 0 1 0 c 1 1 0 1 d 0 0 1 0 Adjacency Matrix of a Directed Graph Let us consider the following directed graph and construct its adjacency matrix − Adjacency matrix of the above directed graph will be − a b c d a 0 1 1 0 b 0 0 1 0 c 0 0 0 1 d 0 0 0 0 Adjacency List In adjacency list, an array $(A[V])$ of linked lists is used to represent the graph G with $V$ number of vertices. An entry $A[V_x]$ represents the linked list of vertices adjacent to the $Vx-th$ vertex. The adjacency list of the undirected graph is as shown in the figure below − Planar vs. Non-planar graph Planar graph − A graph $G$ is called a planar graph if it can be drawn in a plane without any edges crossed. If we draw graph in the plane without edge crossing, it