Category: discrete Mathematics

Simplification Of Boolean Functions Simplification Using Algebraic Functions In this approach, one Boolean expression is minimized into an equivalent expression by applying Boolean identities. Problem 1 Minimize the following Boolean expression using Boolean identities − $$F (A, B, C) = A”B + BC”+ BC + AB”C”$$ Solution Given,$F (A, B, C) = A”B + BC”+ BC + AB”C”$ Or,$F (A, B, C) = A”B + (BC”+ BC”) + BC+ AB”C”$ [By idempotent law, BC’ = BC’ + BC’] Or,$F (A, B, C) = A”B + (BC”+ BC) + (BC”+ AB”C”)$ Or,$F (A, B, C) = A”B + B(C”+ C) + C”(B+ AB”)$ [By distributive laws] Or,$F (A, B, C) = A”B + B.1 + C”(B + A)$ [ (C” + C) = 1 and absorption law (B + AB”)= (B + A)] Or,$F (A, B, C) = A”B + B + C”(B + A)$ [ B.1 = B ] Or,$F (A, B, C) = B(A”+ 1) + C”(B + A)$ Or,$F (A, B, C) = B.1 + C”(B + A)$ [ (A” + 1) = 1 ] Or,$F (A, B, C) = B + C”(B + A)$ [ As, B.1 = B ] Or,$F (A, B, C) = B + BC” + AC”$ Or,$F (A, B, C) = B(1 + C”) + AC”$ Or,$F (A, B, C) = B.1 + AC”$ [As, (1 + C”) = 1] Or,$F (A, B, C) = B + AC”$ [As, B.1 = B] So,$F (A, B, C) = B + AC”$is the minimized form. Problem 2 Minimize the following Boolean expression using Boolean identities − $$F (A, B, C) = (A + B) (A + C)$$ Solution Given, $F (A, B, C) = (A + B) (A + C)$ Or, $F (A, B, C) = A.A + A.C + B.A + B.C$ [Applying distributive Rule] Or, $F (A, B, C) = A + A.C + B.A + B.C$ [Applying Idempotent Law] Or, $F (A, B, C) = A(1 + C) + B.A + B.C$ [Applying distributive Law] Or, $F (A, B, C) = A + B.A + B.C$ [Applying dominance Law] Or, $F (A, B, C) = (A + 1).A + B.C$ [Applying distributive Law] Or, $F (A, B, C) = 1.A + B.C$ [Applying dominance Law] Or, $F (A, B, C) = A + B.C$ [Applying dominance Law] So, $F (A, B, C) = A + BC$ is the minimized form. Karnaugh Maps The Karnaugh map (K–map), introduced by Maurice Karnaughin in 1953, is a grid-like representation of a truth table which is used to simplify boolean algebra expressions. A Karnaugh map has zero and one entries at different positions. It provides grouping together Boolean expressions with common factors and eliminates unwanted variables from the expression. In a K-map, crossing a vertical or horizontal cell boundary is always a change of only one variable. Example 1 An arbitrary truth table is taken below − A B A operation B 0 0 w 0 1 x 1 0 y 1 1 z Now we will make a k-map for the above truth table − Example 2 Now we will make a K-map for the expression − AB+ A’B’ Simplification Using K-map K-map uses some rules for the simplification of Boolean expressions by combining together adjacent cells into single term. The rules are described below − Rule 1 − Any cell containing a zero cannot be grouped. Wrong grouping Rule 2 − Groups must contain 2n cells (n starting from 1). Wrong grouping Rule 3 − Grouping must be horizontal or vertical, but must not be diagonal. Wrong diagonal grouping Proper vertical grouping Proper horizontal grouping Rule 4 − Groups must be covered as largely as possible. Insufficient grouping Proper grouping Rule 5 − If 1 of any cell cannot be grouped with any other cell, it will act as a group itself. Proper grouping Rule 6 − Groups may overlap but there should be as few groups as possible. Proper grouping Rule 7 − The leftmost cell/cells can be grouped with the rightmost cell/cells and the topmost cell/cells can be grouped with the bottommost cell/cells. Proper grouping Problem Minimize the following Boolean expression using K-map − $$F (A, B, C) = A”BC + A”BC” + AB”C”+ AB”C$$ Solution Each term is put into k-map and we get the following − K-map for F (A, B, C) Now we will group the cells of 1 according to the rules stated above − K-map for F (A, B, C) We have got two groups which are termed as $A’B$ and $AB’$. Hence, $F (A, B, C) = A’B+ AB’= A oplus B$. It is the minimized form. Learning working make money

Discrete Mathematics – Useful Resources The following resources contain additional information on Discrete Mathematics. Please use them to get more in-depth knowledge on this. Useful Links on Discrete Mathematics − Wikipedia Reference for Discrete Mathematics. Useful Books on Discrete Mathematics To enlist your site on this page, please drop an email to [email protected] Learning working make money

Discrete Mathematics – Probability Closely related to the concepts of counting is Probability. We often try to guess the results of games of chance, like card games, slot machines, and lotteries; i.e. we try to find the likelihood or probability that a particular result with be obtained. Probability can be conceptualized as finding the chance of occurrence of an event. Mathematically, it is the study of random processes and their outcomes. The laws of probability have a wide applicability in a variety of fields like genetics, weather forecasting, opinion polls, stock markets etc. Basic Concepts Probability theory was invented in the 17th century by two French mathematicians, Blaise Pascal and Pierre de Fermat, who were dealing with mathematical problems regarding of chance. Before proceeding to details of probability, let us get the concept of some definitions. Random Experiment − An experiment in which all possible outcomes are known and the exact output cannot be predicted in advance is called a random experiment. Tossing a fair coin is an example of random experiment. Sample Space − When we perform an experiment, then the set S of all possible outcomes is called the sample space. If we toss a coin, the sample space $S = left { H, T right }$ Event − Any subset of a sample space is called an event. After tossing a coin, getting Head on the top is an event. The word “probability” means the chance of occurrence of a particular event. The best we can say is how likely they are to happen, using the idea of probability. $Probability:of:occurence:of:an:event = frac{Total:number:of:favourable : outcome}{Total:number:of:Outcomes}$ As the occurrence of any event varies between 0% and 100%, the probability varies between 0 and 1. Steps to find the probability Step 1 − Calculate all possible outcomes of the experiment. Step 2 − Calculate the number of favorable outcomes of the experiment. Step 3 − Apply the corresponding probability formula. Tossing a Coin If a coin is tossed, there are two possible outcomes − Heads $(H)$ or Tails $(T)$ So, Total number of outcomes = 2 Hence, the probability of getting a Head $(H)$ on top is 1/2 and the probability of getting a Tails $(T)$ on top is 1/2 Throwing a Dice When a dice is thrown, six possible outcomes can be on the top − $1, 2, 3, 4, 5, 6$. The probability of any one of the numbers is 1/6 The probability of getting even numbers is 3/6 = 1/2 The probability of getting odd numbers is 3/6 = 1/2 Taking Cards From a Deck From a deck of 52 cards, if one card is picked find the probability of an ace being drawn and also find the probability of a diamond being drawn. Total number of possible outcomes − 52 Outcomes of being an ace − 4 Probability of being an ace = 4/52 = 1/13 Probability of being a diamond = 13/52 = 1/4 Probability Axioms The probability of an event always varies from 0 to 1. $[0 leq P(x) leq 1]$ For an impossible event the probability is 0 and for a certain event the probability is 1. If the occurrence of one event is not influenced by another event, they are called mutually exclusive or disjoint. If $A_1, A_2….A_n$ are mutually exclusive/disjoint events, then $P(A_i cap A_j) = emptyset $ for $i ne j$ and $P(A_1 cup A_2 cup…. A_n) = P(A_1) + P(A_2)+….. P(A_n)$ Properties of Probability If there are two events $x$ and $overline{x}$which are complementary, then the probability of the complementary event is − $$p(overline{x}) = 1-p(x)$$ For two non-disjoint events A and B, the probability of the union of two events − $P(A cup B) = P(A) + P(B)$ If an event A is a subset of another event B (i.e. $A subset B$), then the probability of A is less than or equal to the probability of B. Hence, $A subset B$ implies $P(A) leq p(B)$ Conditional Probability The conditional probability of an event B is the probability that the event will occur given an event A has already occurred. This is written as $P(B|A)$. Mathematically − $ P(B|A) = P(A cap B)/ P(A)$ If event A and B are mutually exclusive, then the conditional probability of event B after the event A will be the probability of event B that is $P(B)$. Problem 1 In a country 50% of all teenagers own a cycle and 30% of all teenagers own a bike and cycle. What is the probability that a teenager owns bike given that the teenager owns a cycle? Solution Let us assume A is the event of teenagers owning only a cycle and B is the event of teenagers owning only a bike. So, $P(A) = 50/100 = 0.5$ and $P(A cap B) = 30/100 = 0.3$ from the given problem. $P(B|A) = P(A cap B)/ P(A) = 0.3/ 0.5 = 0.6$ Hence, the probability that a teenager owns bike given that the teenager owns a cycle is 60%. Problem 2 In a class, 50% of all students play cricket and 25% of all students play cricket and volleyball. What is the probability that a student plays volleyball given that the student plays cricket? Solution Let us assume A is the event of students playing only cricket and B is the event of students playing only volleyball. So, $P(A) = 50/100 =0.5$ and $P(A cap B) = 25/ 100 =0.25$ from the given problem. $Plgroup Brvert A rgroup= Plgroup Acap Brgroup/Plgroup A rgroup =0.25/0.5=0.5$ Hence, the probability that a student plays volleyball given that the student plays cricket is 50%. Problem 3 Six good laptops and three defective laptops are mixed up. To find the defective laptops all of them are tested one-by-one at random. What is the probability to find both of the defective laptops in the first two pick? Solution Let A be the event that we find a defective laptop in the first test and B be the event that we

Mathematical Induction Mathematical induction, is a technique for proving results or establishing statements for natural numbers. This part illustrates the method through a variety of examples. Definition Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. The technique involves two steps to prove a statement, as stated below − Step 1(Base step) − It proves that a statement is true for the initial value. Step 2(Inductive step) − It proves that if the statement is true for the nth iteration (or number n), then it is also true for (n+1)th iteration ( or number n+1). How to Do It Step 1 − Consider an initial value for which the statement is true. It is to be shown that the statement is true for n = initial value. Step 2 − Assume the statement is true for any value of n = k. Then prove the statement is true for n = k+1. We actually break n = k+1 into two parts, one part is n = k (which is already proved) and try to prove the other part. Problem 1 $3^n-1$ is a multiple of 2 for n = 1, 2, … Solution Step 1 − For $n = 1, 3^1-1 = 3-1 = 2$ which is a multiple of 2 Step 2 − Let us assume $3^n-1$ is true for $n=k$, Hence, $3^k -1$ is true (It is an assumption) We have to prove that $3^{k+1}-1$ is also a multiple of 2 $3^{k+1} – 1 = 3 times 3^k – 1 = (2 times 3^k) + (3^k – 1)$ The first part $(2 times 3k)$ is certain to be a multiple of 2 and the second part $(3k -1)$ is also true as our previous assumption. Hence, $3^{k+1} – 1$ is a multiple of 2. So, it is proved that $3^n – 1$ is a multiple of 2. Problem 2 $1 + 3 + 5 + … + (2n-1) = n^2$ for $n = 1, 2, dots $ Solution Step 1 − For $n=1, 1 = 1^2$, Hence, step 1 is satisfied. Step 2 − Let us assume the statement is true for $n=k$. Hence, $1 + 3 + 5 + dots + (2k-1) = k^2$ is true (It is an assumption) We have to prove that $1 + 3 + 5 + … + (2(k+1)-1) = (k+1)^2$ also holds $1 + 3 + 5 + dots + (2(k+1) – 1)$ $= 1 + 3 + 5 + dots + (2k+2 – 1)$ $= 1 + 3 + 5 + dots + (2k + 1)$ $= 1 + 3 + 5 + dots + (2k – 1) + (2k + 1)$ $= k^2 + (2k + 1)$ $= (k + 1)^2$ So, $1 + 3 + 5 + dots + (2(k+1) – 1) = (k+1)^2$ hold which satisfies the step 2. Hence, $1 + 3 + 5 + dots + (2n – 1) = n^2$ is proved. Problem 3 Prove that $(ab)^n = a^nb^n$ is true for every natural number $n$ Solution Step 1 − For $n=1, (ab)^1 = a^1b^1 = ab$, Hence, step 1 is satisfied. Step 2 − Let us assume the statement is true for $n=k$, Hence, $(ab)^k = a^kb^k$ is true (It is an assumption). We have to prove that $(ab)^{k+1} = a^{k+1}b^{k+1}$ also hold Given, $(ab)^k = a^k b^k$ Or, $(ab)^k (ab) = (a^k b^k ) (ab)$ [Multiplying both side by ”ab”] Or, $(ab)^{k+1} = (aa^k) ( bb^k)$ Or, $(ab)^{k+1} = (a^{k+1}b^{k+1})$ Hence, step 2 is proved. So, $(ab)^n = a^nb^n$ is true for every natural number n. Strong Induction Strong Induction is another form of mathematical induction. Through this induction technique, we can prove that a propositional function, $P(n)$ is true for all positive integers, $n$, using the following steps − Step 1(Base step) − It proves that the initial proposition $P(1)$ true. Step 2(Inductive step) − It proves that the conditional statement $[P(1) land P(2) land P(3) land dots land P(k)] → P(k + 1)$ is true for positive integers $k$. Learning working make money

Introduction to Trees Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree. Tree and its Properties Definition − A Tree is a connected acyclic undirected graph. There is a unique path between every pair of vertices in $G$. A tree with N number of vertices contains $(N-1)$ number of edges. The vertex which is of 0 degree is called root of the tree. The vertex which is of 1 degree is called leaf node of the tree and the degree of an internal node is at least 2. Example − The following is an example of a tree − Centers and Bi-Centers of a Tree The center of a tree is a vertex with minimal eccentricity. The eccentricity of a vertex $X$ in a tree $G$ is the maximum distance between the vertex $X$ and any other vertex of the tree. The maximum eccentricity is the tree diameter. If a tree has only one center, it is called Central Tree and if a tree has only more than one centers, it is called Bi-central Tree. Every tree is either central or bi-central. Algorithm to find centers and bi-centers of a tree Step 1 − Remove all the vertices of degree 1 from the given tree and also remove their incident edges. Step 2 − Repeat step 1 until either a single vertex or two vertices joined by an edge is left. If a single vertex is left then it is the center of the tree and if two vertices joined by an edge is left then it is the bi-center of the tree. Problem 1 Find out the center/bi-center of the following tree − Solution At first, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree − Again, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree − Finally we got a single vertex ‘c’ and we stop the algorithm. As there is single vertex, this tree has one center ‘c’ and the tree is a central tree. Problem 2 Find out the center/bi-center of the following tree − Solution At first, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree − Again, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree − Finally, we got two vertices ‘c’ and ‘d’ left, hence we stop the algorithm. As two vertices joined by an edge is left, this tree has bi-center ‘cd’ and the tree is bi-central. Labeled Trees Definition − A labeled tree is a tree the vertices of which are assigned unique numbers from 1 to n. We can count such trees for small values of n by hand so as to conjecture a general formula. The number of labeled trees of n number of vertices is $n^{n-2}$. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels. Example Unlabeled Trees Definition − An unlabeled tree is a tree the vertices of which are not assigned any numbers. The number of labeled trees of n number of vertices is $frac {(2n)!}{ (n+1)!n! }$ (nth Catalan number) Example Rooted Tree A rooted tree $G$ is a connected acyclic graph with a special node that is called the root of the tree and every edge directly or indirectly originates from the root. An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. If every internal vertex of a rooted tree has not more than m children, it is called an m-ary tree. If every internal vertex of a rooted tree has exactly m children, it is called a full m-ary tree. If $m = 2$, the rooted tree is called a binary tree. Binary Search Tree Binary Search tree is a binary tree which satisfies the following property − $X$ in left sub-tree of vertex $V, Value(X) le Value (V)$ $Y$ in right sub-tree of vertex $V, Value(Y) ge Value (V)$ So, the value of all the vertices of the left sub-tree of an internal node $V$ are less than or equal to $V$ and the value of all the vertices of the right sub-tree of the internal node $V$ are greater than or equal to $V$. The number of links from the root node to the deepest node is the height of the Binary Search Tree. Example Algorithm to search for a key in BST BST_Search(x, k) if ( x = NIL or k = Value[x] ) return x; if ( k < Value[x]) return BST_Search (left[x], k); else return BST_Search (right[x], k) Complexity of Binary search tree Average Case Worst case Space Complexity O(n) O(n) Search Complexity O(log n) O(n) Insertion Complexity O(log n) O(n) Deletion Complexity O(log n) O(n) Learning working make money

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. Learning working make money

Discrete Mathematics – More On Graphs Graph Coloring Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no adjacent vertices get same color. The objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G is called its chromatic number of that graph. Graph coloring problem is a NP Complete problem. Method to Color a Graph The steps required to color a graph G with n number of vertices are as follows − Step 1 − Arrange the vertices of the graph in some order. Step 2 − Choose the first vertex and color it with the first color. Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored on any vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to it. Repeat this step until all the vertices are colored. Example In the above figure, at first vertex $a$ is colored red. As the adjacent vertices of vertex a are again adjacent, vertex $b$ and vertex $d$ are colored with different color, green and blue respectively. Then vertex $c$ is colored as red as no adjacent vertex of $c$ is colored red. Hence, we could color the graph by 3 colors. Hence, the chromatic number of the graph is 3. Applications of Graph Coloring Some applications of graph coloring include − Map Coloring Bipartite Graph Checking Making time table, etc. Graph Traversal Graph traversal is the problem of visiting all the vertices of a graph in some systematic order. There are mainly two ways to traverse a graph. Breadth First Search Depth First Search Breadth First Search Breadth First Search (BFS) starts at starting level-0 vertex $X$ of the graph $G$. Then we visit all the vertices that are the neighbors of $X$. After visiting, we mark the vertices as “visited,” and place them into level-1. Then we start from the level-1 vertices and apply the same method on every level-1 vertex and so on. The BFS traversal terminates when every vertex of the graph has been visited. BFS Algorithm The concept is to visit all the neighbor vertices before visiting other neighbor vertices of neighbor vertices. Initialize status of all nodes as “Ready”. Put source vertex in a queue and change its status to “Waiting”. Repeat the following two steps until queue is empty − Remove the first vertex from the queue and mark it as “Visited”. Add to the rear of queue all neighbors of the removed vertex whose status is “Ready”. Mark their status as “Waiting”. Problem Let us take a graph (Source vertex is ‘a’) and apply the BFS algorithm to find out the traversal order. Solution − Initialize status of all vertices to “Ready”. Put a in queue and change its status to “Waiting”. Remove a from queue, mark it as “Visited”. Add a’s neighbors in “Ready” state b, d and e to end of queue and mark them as “Waiting”. Remove b from queue, mark it as “Visited”, put its “Ready” neighbor c at end of queue and mark c as “Waiting”. Remove d from queue and mark it as “Visited”. It has no neighbor in “Ready” state. Remove e from queue and mark it as “Visited”. It has no neighbor in “Ready” state. Remove c from queue and mark it as “Visited”. It has no neighbor in “Ready” state. Queue is empty so stop. So the traversal order is − $a rightarrow b rightarrow d rightarrow e rightarrow c$ The alternate orders of traversal are − $a rightarrow b rightarrow e rightarrow d rightarrow c$ Or, $a rightarrow d rightarrow b rightarrow e rightarrow c$ Or, $a rightarrow e rightarrow b rightarrow d rightarrow c$ Or, $a rightarrow b rightarrow e rightarrow d rightarrow c$ Or, $a rightarrow d rightarrow e rightarrow b rightarrow c$ Application of BFS Finding the shortest path Minimum spanning tree for un-weighted graph GPS navigation system Detecting cycles in an undirected graph Finding all nodes within one connected component Complexity Analysis Let $G(V, E)$ be a graph with $|V|$ number of vertices and $|E|$ number of edges. If breadth first search algorithm visits every vertex in the graph and checks every edge, then its time complexity would be − $$O( | V | + | E | ). O( | E | )$$ It may vary between $O(1)$ and $O(|V2|)$ Depth First Search Depth First Search (DFS) algorithm starts from a vertex $v$, then it traverses to its adjacent vertex (say x) that has not been visited before and mark as “visited” and goes on with the adjacent vertex of $x$ and so on. If at any vertex, it encounters that all the adjacent vertices are visited, then it backtracks until it finds the first vertex having an adjacent vertex that has not been traversed before. Then, it traverses that vertex, continues with its adjacent vertices until it traverses all visited vertices and has to backtrack again. In this way, it will traverse all the vertices reachable from the initial vertex $v$. DFS Algorithm The concept is to visit all the neighbor vertices of a neighbor vertex before visiting the other neighbor vertices. Initialize status of all nodes as “Ready” Put source vertex in a stack and change its status to “Waiting” Repeat the following two steps until stack is empty − Pop the top vertex from the stack and mark it as “Visited” Push onto the top of the stack all neighbors of the removed vertex whose status is “Ready”. Mark their status as “Waiting”. Problem Let us take a graph (Source vertex is ‘a’) and apply the DFS algorithm to find out the traversal order. Solution Initialize status of all vertices to “Ready”. Push a in stack and change its status to “Waiting”. Pop a and mark it as “Visited”. Push a’s neighbors in

Discrete Mathematics – Spanning Trees A spanning tree of a connected undirected graph $G$ is a tree that minimally includes all of the vertices of $G$. A graph may have many spanning trees. Example Minimum Spanning Tree A spanning tree with assigned weight less than or equal to the weight of every possible spanning tree of a weighted, connected and undirected graph $G$, it is called minimum spanning tree (MST). The weight of a spanning tree is the sum of all the weights assigned to each edge of the spanning tree. Example Kruskal”s Algorithm Kruskal”s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree. Algorithm Step 1 − Arrange all the edges of the given graph $G (V,E)$ in ascending order as per their edge weight. Step 2 − Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far. Step 3 − If there is no cycle, include this edge to the spanning tree else discard it. Step 4 − Repeat Step 2 and Step 3 until $(V-1)$ number of edges are left in the spanning tree. Problem Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s algorithm. Solution From the above graph we construct the following table − Edge No. Vertex Pair Edge Weight E1 (a, b) 20 E2 (a, c) 9 E3 (a, d) 13 E4 (b, c) 1 E5 (b, e) 4 E6 (b, f) 5 E7 (c, d) 2 E8 (d, e) 3 E9 (d, f) 14 Now we will rearrange the table in ascending order with respect to Edge weight − Edge No. Vertex Pair Edge Weight E4 (b, c) 1 E7 (c, d) 2 E8 (d, e) 3 E5 (b, e) 4 E6 (b, f) 5 E2 (a, c) 9 E3 (a, d) 13 E9 (d, f) 14 E1 (a, b) 20 Since we got all the 5 edges in the last figure, we stop the algorithm and this is the minimal spanning tree and its total weight is $(1 + 2 + 3 + 5 + 9) = 20$. Prim”s Algorithm Prim”s algorithm, discovered in 1930 by mathematicians, Vojtech Jarnik and Robert C. Prim, is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree. Prim’s algorithm is faster on dense graphs. Algorithm Initialize the minimal spanning tree with a single vertex, randomly chosen from the graph. Repeat steps 3 and 4 until all the vertices are included in the tree. Select an edge that connects the tree with a vertex not yet in the tree, so that the weight of the edge is minimal and inclusion of the edge does not form a cycle. Add the selected edge and the vertex that it connects to the tree. Problem Suppose we want to find minimum spanning tree for the following graph G using Prim’s algorithm. Solution Here we start with the vertex ‘a’ and proceed. This is the minimal spanning tree and its total weight is $(1 + 2 + 3 + 5 + 9) = 20$. Learning working make money

Discrete Mathematics – Functions A Function assigns to each element of a set, exactly one element of a related set. Functions find their application in various fields like representation of the computational complexity of algorithms, counting objects, study of sequences and strings, to name a few. The third and final chapter of this part highlights the important aspects of functions. Function – Definition A function or mapping (Defined as $f: X rightarrow Y$) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function ‘f’. Function ‘f’ is a relation on X and Y such that for each $x in X$, there exists a unique $y in Y$ such that $(x,y) in R$. ‘x’ is called pre-image and ‘y’ is called image of function f. A function can be one to one or many to one but not one to many. Injective / One-to-one function A function $f: A rightarrow B$ is injective or one-to-one function if for every $b in B$, there exists at most one $a in A$ such that $f(s) = t$. This means a function f is injective if $a_1 ne a_2$ implies $f(a1) ne f(a2)$. Example $f: N rightarrow N, f(x) = 5x$ is injective. $f: N rightarrow N, f(x) = x^2$ is injective. $f: Rrightarrow R, f(x) = x^2$ is not injective as $(-x)^2 = x^2$ Surjective / Onto function A function $f: A rightarrow B$ is surjective (onto) if the image of f equals its range. Equivalently, for every $b in B$, there exists some $a in A$ such that $f(a) = b$. This means that for any y in B, there exists some x in A such that $y = f(x)$. Example $f : N rightarrow N, f(x) = x + 2$ is surjective. $f : R rightarrow R, f(x) = x^2$ is not surjective since we cannot find a real number whose square is negative. Bijective / One-to-one Correspondent A function $f: A rightarrow B$ is bijective or one-to-one correspondent if and only if f is both injective and surjective. Problem Prove that a function $f: R rightarrow R$ defined by $f(x) = 2x – 3$ is a bijective function. Explanation − We have to prove this function is both injective and surjective. If $f(x_1) = f(x_2)$, then $2x_1 – 3 = 2x_2 – 3 $ and it implies that $x_1 = x_2$. Hence, f is injective. Here, $2x – 3= y$ So, $x = (y+5)/3$ which belongs to R and $f(x) = y$. Hence, f is surjective. Since f is both surjective and injective, we can say f is bijective. Inverse of a Function The inverse of a one-to-one corresponding function $f : A rightarrow B$, is the function $g : B rightarrow A$, holding the following property − $f(x) = y Leftrightarrow g(y) = x$ The function f is called invertible, if its inverse function g exists. Example A Function $f : Z rightarrow Z, f(x)=x+5$, is invertible since it has the inverse function $ g : Z rightarrow Z, g(x)= x-5$. A Function $f : Z rightarrow Z, f(x)=x^2$ is not invertiable since this is not one-to-one as $(-x)^2=x^2$. Composition of Functions Two functions $f: A rightarrow B$ and $g: B rightarrow C$ can be composed to give a composition $g o f$. This is a function from A to C defined by $(gof)(x) = g(f(x))$ Example Let $f(x) = x + 2$ and $g(x) = 2x + 1$, find $( f o g)(x)$ and $( g o f)(x)$. Solution $(f o g)(x) = f (g(x)) = f(2x + 1) = 2x + 1 + 2 = 2x + 3$ $(g o f)(x) = g (f(x)) = g(x + 2) = 2 (x+2) + 1 = 2x + 5$ Hence, $(f o g)(x) neq (g o f)(x)$ Some Facts about Composition If f and g are one-to-one then the function $(g o f)$ is also one-to-one. If f and g are onto then the function $(g o f)$ is also onto. Composition always holds associative property but does not hold commutative property. Learning working make money

Discrete Mathematics – Predicate Logic ”; Previous Next Predicate Logic deals with predicates, which are propositions containing variables. Predicate Logic – Definition A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable. The following are some examples of predicates − Let E(x, y) denote “x = y” Let X(a, b, c) denote “a &plus; b &plus; c = 0” Let M(x, y) denote “x is married to y” Well Formed Formula Well Formed Formula (wff) is a predicate holding any of the following − All propositional constants and propositional variables are wffs If x is a variable and Y is a wff, $forall x Y$ and $exists x Y$ are also wff Truth value and false values are wffs Each atomic formula is a wff All connectives connecting wffs are wffs Quantifiers The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic − Universal Quantifier and Existential Quantifier. Universal Quantifier Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol $forall$. $forall x P(x)$ is read as for every value of x, P(x) is true. Example − “Man is mortal” can be transformed into the propositional form $forall x P(x)$ where P(x) is the predicate which denotes x is mortal and the universe of discourse is all men. Existential Quantifier Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol $exists $. $exists x P(x)$ is read as for some values of x, P(x) is true. Example − “Some people are dishonest” can be transformed into the propositional form $exists x P(x)$ where P(x) is the predicate which denotes x is dishonest and the universe of discourse is some people. Nested Quantifiers If we use a quantifier that appears within the scope of another quantifier, it is called nested quantifier. Example $forall a: exists b: P (x, y)$ where $P (a, b)$ denotes $a + b = 0$ $forall a: forall: b: forall: c: P (a, b, c)$ where $P (a, b)$ denotes $a + (b + c) = (a + b) + c$ Note − $forall: a: exists b: P (x, y) ne exists a: forall b: P (x, y)$ Print Page Previous Next Advertisements ”;