6 min read

Properties of groups: Some of these properties will look very familiar, since they are similar to what we saw for rings. Uniqueness of identity element: The identity element of a group is unique. For suppose that there are two identity elements, say e1 and e2. (This means that g  e1 = e1  g = g for all g, and also g  e2 = e2  g = g for all g.) Then e1 = e1 . e2 = e2. Uniqueness of inverse: The inverse of a group element g is unique. For suppose that h and k are both additive inverses of g. (This means that gh = hg = e and gk = k g = e – we know now that there is a unique identity element e). Then h = h . e = h . (g . k) = (h . g) . k = e . k = k, where we use the associative law in the third step. We denote the inverse of g by g⁻¹.

4 min read

Matrix rings: In view of Proposition 2.6, the definition of the product of two n×n matrices now makes sense: AB = D, where So we are in the position to prove Proposition 2.1. A complete proof of this proposition involves verifying all the ring axioms. The arguments are somewhat repetitive; I will give proofs of two of the axioms. Axiom (A2): Let 0 be the zero element of the ring R, and let O be the zero matrix in Mn(R), satisfying Oi j = 0 for all i, j. Then O is the zero element of Mn(R): for, given any matrix A, (O A)i j = O_{i j} Ai j = 0 Ai j = Ai j, (A O)i j = Ai j Oi j = Ai j 0 = Ai j, using the properties of 0 2 R. So O A = A O = A. Axiom (D): the (i, j) entry of A(B C) is by the distributive law in R; and the (i, j) entry of AB AC is Why are these two expressions the same? Let us consider the case n = 2. The first expression is Ai1B1 j Ai1C1 j Ai2B2 j Ai2C2 j, while the second is Ai1B1 j Ai2B2 j Ai1C1 j Ai2C2 j. (By Proposition 2.6, the bracketing is not significant.) Now the commutative law for addition allows us to swap the second and third terms of the sum; so the two expressions are equal. Hence A(B C) = AB AC for any matrices A,B,C. For n>2, things are similar, but the rearrangement required is a bit more complicated. The proof of the other distributive law is similar. Observe what happens in this proof: we use properties of the ring R to deduce properties of Mn(R). To prove the distributive law for Mn(R), we needed the distributive law and the associative and commutative laws for addition in R. Similar things happen for the other axioms. Polynomial rings: What exactly is a polynomial? We deferred this question before, but now is the time to face it. A polynomial is completely determined by the sequence of its coefficients a0,a1, . . .. These have the property that only a finite number of terms in the sequence are non-zero, but we cannot say in advance how many. So we make the following definition: A polynomial over a ring R is an infinite sequence (ai)i0 = (a0,a1, . . .) of elements of R, having the property that only finitely many terms are non-zero; that is, there exists an n such that ai = 0 for all i > n. If an is the last non-zero term, we say that the degree of the polynomial is n. (Note that, according to this definition, the all-zero sequence does not have a degree.) Now the rules for addition and multiplication are Again, the sum in the definition of multiplication is justified by Proposition 2.6. We think of the polynomial (ai)i0 of degree n as what we usually write as ; the rules we gave agree with the usual ones. Now we can prove Proposition 2.2, asserting that the set of polynomials over a ring R is a ring. As for matrices, we have to check all the axioms, which involves a certain amount of tedium. The zero polynomial required by (A2) is the all-zero sequence. Here is a proof of (M1). You will see that it involves careful work with dummy subscripts! We have to prove the associative law for multiplication. So suppose that f = (ai), g = (bi) and h = (ci). Then the ith term of f g is j=0 ajbi−j, and so the ith term of ( f g)h is Similarly the ith term of f (gh) is . Each term on both sides has the form apbqcr, where p,q, r  0 and p q r = i. (In the first expression, p = j, q = k− j, r = i−k; in the second, p = s, q = t, r = i−s−t.) So the two expressions contain the same terms in a different order. By the associative and commutative laws for addition, they are equal.

2 min read

Algebra: Algebra is about operations on sets. You have met many operations; for example: • addition and multiplication of numbers; • modular arithmetic; • addition and multiplication of polynomials; • addition and multiplication of matrices; • union and intersection of sets; • composition of permutations. Many of these operations satisfy similar familiar laws. In all these cases, the “associative law” holds, while most (but not all!) also satisfy the “commutative law”.

6 min read

Definition of a ring: A ring has two operations: the first is called addition and is denoted by (with infix notation); the second is called multiplication, and is usually denoted by juxtaposition (but sometimes by · with infix notation). In order to be a ring, the structure must satisfy certain rules called axioms. We group these into three classes. The name of the ring is R. We define a ring to be a set R with two binary operations satisfying the following axioms: Axioms for addition: (A0) (Closure law) For any a,b 2 R, we have a b 2 R. (A1) (Associative law) For any a,b,c 2 R, we have (a b) c=a (b c). (A2) (Identity law) There is an element 0 2 R with the property that a 0 = 0 a = a for all a 2 R. (The element 0 is called the zero element of R.) (A3) (Inverse law) For any element a 2 R, there is an element b 2 R satisfying a b = b a = 0. (We denote this element b by −a, and call it the additive inverse or negative of a.)

3 min read

Lagrange’s Theorem: Lagrange’s Theorem states a very important relation between the orders of a finite group and any subgroup. Theorem 3.15 (Lagrange’s Theorem) Let H be a subgroup of a finite group G. Then the order of H divides the order of G. Proof We already know from the last section that the group G is partitioned into the right cosets of H. We show that every right coset Hg contains the same number of elements as H. To prove this, we construct a bijection f from H to H_g. The bijection is defined in the obvious way: Φ maps h to hg. • Φ is one-to-one: suppose that Φ(h₁) = Φ)h₂, that is, h₁g = h₂g. Cancelling the g (by the cancellation law, or by multiplying by g⁻¹), we get h₁ = h₂. • Φ is onto: by definition, every element in the coset Hg has the form hg for some h ∈ H, that is, it is Φ(h). So f is a bijection, and |H_g| = |H|. Now, if m is the number of right cosets of H in G, then m|H| = |G|, so |H| divides |G|. Remark We see that |G|/|H| is the number of right cosets of H in G. This number is called the index of H in G. We could have used left cosets instead, and we see that |G|/|H| is also the number of left cosets. So these numbers are the same. In fact, there is another reason for this: Exercise Show that the set of all inverses of the elements in the right coset Hg form the left coset g−1H. So there is a bijection between the set of right cosets and the set of left cosets of H. In the example in the preceding section, we had a group S3 with a subgroup having three right cosets and three left cosets; that is, a subgroup with index 3.

7 min read

Subrings Definition and test: Suppose that we are given a set S with operations of addition and multiplication, and we are asked to prove that it is a ring. In general, we have to check all the axioms. But there is a situation in which things are much simpler: this is when S is a subset of a set R which we already know to be a ring, and the addition and multiplication in S are just the restrictions of the operations in R (that is, to add two elements of S, we regard them as elements of R and use the addition in R). Definition Let R be a ring. A subring of R is a subset S of R which is a ring in its own right with respect to the restrictions of the operations in R. What do we have to do to show that S is a subring? • The associative law (A1) holds in S. For, if a,b,c ∈ S, then we have a,b,c ∈ R (since S ⊆ R), and so (a b) c = a (b c) since R satisfies (A1) (as we are given that it is a ring). • Exactly the same argument shows that the commutative law for addition (A4), the associative law for multiplication (M1), and the distributive laws (D), all hold in S. • This leaves only (A0), (A2), (A3) and (M0) to check. Even here we can make a simplification, if S ≠ 0. For suppose that (A0) and (A3) hold in S. Given a ∈ S, the additive inverse −a belongs to S (since we are assuming (A3)), and so 0 = a (−a) belongs to S (since we are assuming (A0)). Thus (A2) follows from (A0) and (A3). We state this as a theorem: Theorem 2.9 (First Subring Test) Let R be a ring, and let S be a non-empty subset of R. Then S is a subring of R if the following condition holds: for all a,b 2 S, we have a b,ab,−a ∈ S.

5 min read

Groups: In the remainder of the notes we will be talking about groups. A group is a structure with just one binary operation, satisfying four axioms. So groups are only half as complicated as rings! As well as being new material, this part will help you revise the first part of the course, since a lot of things work in almost exactly the same way as for rings. Definition of a group: A group is a set G with one binary operation (which we write for now as  in infix notation1) satisfying the following four axioms (G0)–(G3): (G0) (Closure law) For any g,h ∈ G, we have g . h ∈ G. (G1) (Associative law) For any g,h,k ∈ G, we have (g . h) . k = g . (h . k). (G2) (Identity law) There is an element e ∈ G with the property that ge=eg= g for all g ∈ G. (The element e is called the identity element of G.) (G3) (Inverse law) For any element g ∈ G, there is an element h ∈ G satisfying g . h = h . g = e. (We denote this element h by g−1, and call it the inverse of g.) If a group G also satisfies the condition (G4) (Commutative law) For any g,h ∈ G, we have g . h = h . g, then G is called a commutative group or (more often) an Abelian group. Examples of groups: Axioms (G0)–(G4) for a group are just axioms (A0)–(A4) for a ring but using slightly different notation (the set is G instead of R, the operation is  instead of , and so on). So we get our first class of examples: Proposition 3.1 Let R be a ring. Then R with the operation of addition is an Abelian group: the identity element is 0, and the inverse of a is −a. This group is called the additive group or R. This is not the only way to get groups from rings. Proposition 3.2 Let R be a ring with identity, andU(R) the set of units of R. Then U(R), with the operation of multiplication, is a group. If R is a commutative ring, then U(R) is an Abelian group. This group is called the group of units of R. Proof Look back to Lemma 2.20. Let U(R) be the set of units of R. (G0) if u and v are units, then so is uv. So U(R) is closed for multiplication. (G1) The associative law for multiplication holds for all elements of R (by Axiom (M1) for rings), and so in particular for units. (G2) 1 is a unit. It clearly plays the role of the identity element. (G3) if u is a unit, then so is u−1. (G4) For the last part of the Proposition, if R is a commutative ring, then (M4) holds, so that uv = vu for all u,v 2 R; in particular, this holds when u and v are units.

4 min read

Normal subgroups: A normal subgroup is a special kind of subgroup of a group. Recall from the last chapter taht any subgroup H has right and left cosets, which may not be the same. We say that H is a normal subgroup of G if the right and left cosets of H in G are the same; that is, if Hx = xH for any x 2 G. There are several equivalent ways of saying the same thing. We define x⁻¹Hx = {x⁻¹hx : h ∈H} for any element x ∈ G. Proposition 3.19 Let H be a subgroup of G. Then the following are equivalent: (a) H is a normal subgroup, that is, Hx = xH for all x ∈ G; (b) x⁻¹Hx = H for all x ∈ G; (c) x⁻¹hx 2 H, for all x ∈ G and h ∈ H. Proof If Hx = xH, then x⁻¹Hx = x⁻¹xH = H, and conversely. So (a) and (b) are equivalent. If (b) holds then every element x−1hx belongs to x⁻¹Hx, and so to H, so (c) holds. Conversely, suppose that (c) holds. Then every element of x−1Hx belongs to H, and we have to prove the reverse inclusion. So take h ∈ H. Putting y = x⁻¹, we have k = y⁻¹hy = xhx⁻¹ ∈ H, so h ∈ x⁻¹Hx, finishing the proof. Now the important thing about normal subgroups is that, like ideals, they are kernels of homomorphisms.

5 min read

Homomorphisms and quotient rings Isomorphism: Here are the addition and multiplication tables of a ring with two elements, which for now I will call o and i. You may recognise this ring in various guises: it is the Boolean ringP(X), where X = {x} is a set with just one element x; we have o = /0 and i = {x}. Alternatively it is the ring of integers mod 2, with o = [0]₂ and i = [1]₂. The fact that these two rings have the same addition and multiplication tables shows that, from an algebraic point of view, we cannot distinguish between them. We formalise this as follows. Let R1 and R2 be rings. Let θ : R1 ! R2 be a function which is one-to-one and onto, that is, a bijection between R1 and R2. Now we denote the result of applying the function q to an element r ∈ R1 by rθ or (r)θ rather than by θ(r); that is, we write the function on the right of its argument. Now we say that θ is an isomorphism from R1 to R2 if it is a bijection which satisfies (r1 r2)θ = r1θ r2θ, (r1r2)θ = (r1θ)(r2θ). (2.1) This means that we “match up” elements in R1 with elements in R2 so that addition and multiplication work in the same way in both rings.

5 min read

Symmetric groups and Cayley’s Theorem: Cayley’s Theorem is one of the reasons why the symmetric groups form such an important class of groups: in a sense, if we understand the symmetric groups completely, then we understand all groups! Theorem 3.29 Every group is isomorphic to a subgroup of some symmetric group. Before we give the proof, here is a small digression on the background. Group theory began in the late 18th century: Lagrange, for example, proved his theorem in 1770. Probably the first person to write down the axioms for a group in anything like the present form was Dyck in 1882. So what exactly were group theorists doing for a hundred years? The answer is that Lagrange, Galois, etc. regarded a group as a set G of permutations with the properties • G is closed under composition; • G contains the identity permutation; • G contains the inverse of each of its elements. In other words, G is a subgroup of the symmetric group. Thus, Cayley’s contribution was to show that every group (in the modern sense) could be regarded as a group of permutations; that is, every structure which satisfies the group axioms can indeed be thought of as a group in the sense that Lagrange and others would have understood. In general, systems of axioms in mathematics are usually not invented out of the blue, but are an attempt to capture some theory which already exists. Proof of Cayley’s Theorem: We begin with an example. Here is the Cayley table of a group we have met earlier: it is C2 ×C2, or the additive group of the field of four elements. its elements were called e,a,b,c; now I will call them g1,g2,g3,g4.

3 min read

Homomorphisms and normal subgroups: This section is similar to the corresponding one for rings. Homomorphisms are maps preserving the structure, while normal subgroups do the same job for groups as ideals do for rings: that is, they are kernels of homomorphisms. Isomorphism: Just as for rings, we say that groups are isomorphic if there is a bijection between them which preserves the algebraic structure. Formally, let G1 and G2 be groups. The map θ : G1 -> G2 is an isomorphism if it is a bijection from G1 to G2 and satisfies (gh)θ = (gθ)(hθ) for all g,h∈G1. Note that, as before, we write the map q to the right of its argument: that is, gq is the image of g under the map q. If there is an isomorphism from G1 to G2, we say that the groups G1 and G1 are isomorphic.

4 min read

Subgroups and subgroup tests: A subgroup of a group G is a subset of G which is a subgroup in its own right (with the same group operation). There are two subgroup tests, resembling the two subring tests. Proposition 3.9 (First Subgroup Test) A non-empty subset H of a group G is a subgroup of G if, for any h,k ∈ H, we have hk ∈ H and h⁻¹ ∈ H. Proof We have to show that H satisfies the group axioms. The conditions of the test show that it is closed under composition (G0) and inverses (G3). The associative law (G1) holds in H because it holds for all elements of G. We have only to prove (G2), the identity axiom. We are given that H is non-empty, so choose h ∈ H. Then by assumption, h⁻¹ ∈ H, and then (choosing k = h⁻¹) 1 = hh⁻¹ ∈ H. We can reduce the number of things to be checked from two to one:

3 min read

MATHEMATICAL INDUCTION: Here we discuss another proof technique. Suppose the statement to be proved can be put in the from  nn0. P(n), where n0 is some fixed integer. That is suppose we wish to show that P(n) is true for all integers n ≥ n₀. The following result shows how this can be done. Suppose that (a) P(n₀) is true and (b) If P(K) is true for some K ≥ n₀, then P(K 1) must also be true. The P(n) is true for all n ≥ n₀. This result is called the principle of Mathematical induction. Thus to prove the truth of statement ∀ n≥n0. P(n), using the principle of mathematical induction, we must begin by proving directly that the first proposition P(n0) is true. This is called the basis step of the induction and is generally very easy. Then we must prove that P(K) ∀ P(K 1) is a tautology for any choice of K ≥ n0. Since, the only case where an implication is false is if the antecedent is true and the consequent is false; this step is usually done by showing that if P(K) were true, then P(K 1) would also have to be true. This step is called induction step: In short we solve by following steps. 1. Show that P(1) is true. 2. Assume P(k) is true. 3. Prove that P(k 1) is true using P(k) Hence P(n) is true for every n. Example : Using principle of mathematical induction prove that…

3 min read

Singleton Definition : A set having only one element is called a singleton. Example: (i) A = {8}, (ii) {φ} Theorem 1: Two sets A and B are equal if and only if A ⊆ B and B ⊆ A. Proof: If A = B, every member of A is a member of B and every member of B is a member of A. Hence A ⊆ B and B ⊆ A Conversely let us suppose that A ≠ B, then there is either an element of A that is not in B or there is an element of B that is not in A. But A ⊆ B , therefore every element of A is in B and B ⊆ A , therefore every element of B is in A. Therefore, our assumption that A ≠ B leads to a contradiction, hence A = B. Theorem 2: If φ and φ ′ are empty sets, then φ = φ ′ . Proof: Suppose φ ≠ φ ′ . Then one of the following statements must be true: 1. There is an element x ∈φ such that x ∉φ ′ 2. There is an element x ∈φ ′ such that x ∉φ . But both these statements are false, since neither φ nor φ ′ has any elements. If follows that φ = φ Finite Sets Definition : A set is said to be finite, if it has finite number of elements. Example: (i) {1, 2, 3, 5} (ii) The letters of the English alphabet. Infinite Sets Definition : A set is infinite, if it is not finite. Example: (i) The set of all real numbers. (ii) The points on a line. Universal Sets Definition : In many discussions all the sets are considered to be subsets of one particular set. This set is called the universal set for that discussion. The Universal set is often designated by the script letter U (or by X). Universal set in not unique, and it may change from one discussion to another. Example: If A = {0, 2, 7}, B = {3, 5, 6}, C = {1, 8, 9, 10} then the universal set can be taken as the set. U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. The Power Set Definition : The set of all subsets of a set A is called the power set of A. The power set of A is denoted by P (A). Hence P(A) = {x| x ⊆ A}

3 min read

THEORY OF INFERENCE FOR THE PREDICATE CALCULAS If an implication P → Q is a tautology where P and Q may be compound statement involving any number of propositional variables we say that Q logically follows from P. Suppose (P1, P2 ....... Pn) P →Q. Then this implication is true regardless of the truth values of any of its components. In this case, we say that q logically follows from P1, P2…..,Pn. Proofs in mathematics are valid arguments that establish the truth of mathematical statements. To deduce new statements from statements we already have, we use rules of inference which are templates for constructing valid arguments. Rules of inference are our basic tools for establishing the truth of statements. The rules of inference for statements involving existential and universal quantifiers play an important role in proofs in Computer Science and Mathematics, although they are often used without being explicitly mentioned. Valid Argument :

7 min read

DEFINITION 1 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds. A conditional statement is also called an implication. The truth table for the conditional statement p → q is shown in Table 5. Note that the statement p → q is true when both p and q are true and when p is false (no matter what truth value q has). Because conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express p → q. You will encounter most if not all of the following ways to express this conditional statement:

2 min read

THE DECIMAL NUMBER SYSTEM The number systems are based on an ordered set of number of digits. The total number of digits used in a number system is called ‘base’ or ‘radix’ of the number system. The decimal number system used 10 digits - 0, 1, 2, ….. 9 and hence its base is 10. The base of binary number system is 2, base of octal number system is 8 and hexadecimal system has base 16. The decimal number system is the most popular system used not only by scientists and engineers but also by the common man. It is a positional number system as the value of any number depends on the position of digits. e.g. Consider number 638. Its representation is 638 = 600 30 8 i.e. 2 1 0 638₁₀ = 6x10 ² 3x10 ¹ 8x10⁰ Starting from left most digit, 6 is in the hundreds position. It is called t he Most Significant Digit (MSD). 3is in the tens position. The last digit 8 is in the unit position and is the least significant digit (LSD). The example shows that the value of each position is a power of base 10. The power can be either positive, negative or 0.

2 min read

THE COMPUTER REPRESENTATION OF SETS: There are various ways to represent sets using a computer. Modern programming languages, such as JAVA, have predefined collection class to represent the set. In such class, we need to insert the set elements and there are various class operations defined for the algebraic operations on the set. In this section, we shall present a method for storing elements using the arbitrary ordering of the elements of a universal set.

3 min read

binary number system: A computer stores numbers, letters and characters in a coded form which is a series of string of Os and 1s. The binary number system consists of only O and 1. The digits in binary system are called ‘bits’. A group of 4 bits is called nibble and a group of 8 bits is called a byte. A group of 16 bits is known as ‘word’ and a group of 32 bits is called a ‘double word’. This number system has base 2. Computers are designed to handle only binary numbers because computer circuits have to handle only two binary digits which simplifies the design of the circuits, reduces cost and improves reliability. In binary system, the value of each digit is based on 2 and powers of 2. Decimal to binary system conversion: Step 1) Divide the number by 2, the remainder is either O or 1. 2) Place the remainder to the right of number. 3) Subsequently divide the partial quotient by 2 and again place the remainder to the right of the partial quotient. 4) Repeat the steps till we get the partial quotient O. 5) The binary number is equal to the remainders arranged so that the first remainder is the LSD and last remainder is MSD. i.e. in order from bottom to top. Example 1. Convert 65₁₀ into binary.

4 min read

Predicates : A predicate is a statement containing one or more variables. Proposition : If values are assigned to all the variables in a predicate, the resulting statement is a proposition. e.g. 1. x < 9 is a predicate 2. 4 < 9 is a proposition Propositional Function : Let a be a given set. A propositional function (or : on open sentence or condition) defined on A is an expression P(x) which has the property that P(a) is true or false for each a ∈ A. The set A is called domain of P(x) and the set Tp of all elements of A for which P (a) is true is called the truth set of P(x). i.e. Another use of predicates is in programming Two common constructions are “if P(x), then execute certain steps” and “while Q(x), do specified actions.” The predicates P(x) and Q(x) are called the guards for the block of programming code often the guard for a block is a conjunction or disjunction. e.g. Let A = {x / x is an integer < 8} Here P(x) is the sentence “x is an integer less than 8”. The common property is “an integer less than 8”. P(1) is the statement “1 is an integer less than 8”. P(1) is true, 1 ∈ A etc

2 min read

INTRODUCTION: We are familiar with some problem solving techniques for counting, such as principles for addition, multiplication, permutations, combinations etc. But there are some problems which cannot be solved or very tedious to solve, using these techniques. In some such problems, the problems can be represented in the form of some relation and can be solved accordingly. We shall discuss some such examples before proceeding further. Example: The number of bacteria, double every hour, then what will be the population of the bacteria after 10 hours? Here we can represent number of bacteria at the nth hour be an. Then, we can say that an = 2an–1. Example : Our usual compound interest problems are examples of such representation. That is, , where P is principal, r is rate of interest, n is period in years and In is interest at the end of n^th year. Example : Towers of Hanoi is a popular puzzle. There are three pegs mounted on a board, together with disks of different sizes. Initially, these discs are placed on the first peg in order of different sizes, with the largest disc at the bottom and the smallest at the top. The task is to move the discs from the first peg to the third peg using the middle peg as auxiliary. The rules of the puzzle are:

5 min read

Introduction: A set is to be thought of as any collection of objects whatsoever. The objects can also be anything and they are called elements of the set. The elements contained in a given set need not have anything in common (other than the obvious common attribute that they all belong to the given set). Equally, there is no restriction on the number of elements allowed in a set; there may be an infinite number, a finite number or even no elements at all. There is, however, one restriction we insist upon: given a set and an object, we should be able to decide (in principle at least—it may be difficult in practice) whether or not the object belongs to the set. Clearly a concept as general as this has many familiar examples as well as many frivolous ones. Notation: We shall generally use upper-case letters to denote sets and lower-case letters to denote elements. (This convention will sometimes be violated, for example when the elements of a particular set are themselves sets.) The symbol ∈ denotes ‘belongs to’ or ‘is an element of’. Thus a ∈ A means (the element) a belongs to (the set) A and a / ∈ A means ¬(a ∈ A) or a does not belong to A. Defining Sets: Sets can be defined in various ways. The simplest is by listing the elements enclosed between curly brackets or ‘braces’ { }. The two (well defined) sets in examples 3.1 could be written: A = {Picasso, Eiffel Tower, π} B = {2, 4, 6, 8, . . .}.

1 min read

We can convert 56₈ to decimal number and then convert the decimal number to its binary equivalent. Binary to Octal Conversion: Steps: 1) Make a group of 3 bits, starting from binary point 2) For whole numbers make group of three from right to left (from binary point) 3) For fractional part, move left to right from binary point. 4) In case of one or two bits left, add zeroes to make a group of three. 5) Replace each group of 3 bits by equivalent octal numbers.

1 min read

Division: Division for binary numbers can be carried out by following same rules as those of decimal system.

3 min read

RELATIONS: Relationship between elements of sets is represented using a mathematical structure called relation. The most intuitive way to describe the relationship is to represent in the form of ordered pair. In this section, we study the basic terminology and diagrammatic representation of relation. Definition : Let A and B be two sets. A binary relation from A to B is a subset of A X B. Let A and B be two sets. Suppose R is a relation from A to B (i.e. R is a subset of A X B). Then, R is a set of ordered pairs where each first element comes from A and each second element from B. Thus, we denote

2 min read

Functionally complete set of Connectives : We know that there are five logical connectives ∨,∧,¬,→and ⇔. But some of these can be expressed in terms of the other & we get a smaller set of connectives. The set containing minimum number of connectives which are sufficient to express any logical formula in symbolic form is called as the functionally complete set of connectives. There are following two functionally complete set of connectives. (1) {¬,∨} is complete set connectives. Here, the ∧ can be expressed using ¬ &∨ . P∧Q ≡ (¬ ¬ P ∧Q) ≡ ¬ (¬ P ∧ ¬ Q)

3 min read

MAXIMAL, MINIMAL ELEMENTS AND LATTICES: In this section, we discuss certain element types in the poset and hence a special kind of poset, Lattice. To understand these types, we shall refer to the following figures, i.e. Fig.4.6 and Fig.4.7.

2 min read

Binary to hexadecimal Conversion - 1) Group the binary bits into fours starting from binary point. 2) For whole number, make group of four form right to left from binary point. 3) For fractional part, make group of four from left to right from binary point. 4) In case you are left with only one or two or three bits, add zero or zeroes at appropriate places. 5) Replace each group by equivalent hexadecimal numbers (by multiplying by powers 23 to 20)

2 min read

Method for solving linear homogeneous recurrence relations with constant coefficients: In the previous subsection, we have seen a backtracking method for solving recurrence relation. However, not all the equations can be solved easily using this method . In this subsection, we shall discuss the method of solving a type of recurrence relation called linear homogeneous recurrence relation. Before that we shall define this class of recurrence relation. Definition : A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form: , where c1, c2, ..., ck are constant real numbers with ck ≠ 0. Example : Fibonacci sequence is also an example of a linear homogeneous recurrence relation of degree 2. Example : The recurrence relation is not linear (due to square term), whereas the relation H_n = 2H_n–1 1 is not homogeneous (due to constant 1). The basic approach for solving a linear homogeneous recurrence relation to look for the solution of the form a_n = rⁿ, where r is constant. Note that, rn is a solution to the linear homogeneous recurrence relation of degree k, if and only if; When both the sides of the equation are divided by r^n–k and right side is subtracted from the left side, we obtain an equation, known as characteristic equation of the recurrence relation as follows:

2 min read

THE ALGEBRA OF SETS: The following statements are basic consequences of the above definitions, with A, B, C, ... representing subsets of a universal set U. 1. A ∪ B = B ∪ A. (Union is commutative) 2. A ∩ B = B ∩ A. (Intersection is commutative) 3. (A ∪ B) ∪ C = A ∪ (B ∪ C). (Union is associative) 4. (A ∩ B) ∩ C = A ∩ (B ∩ C). (Intersection is associative) 5. A ∪ Φ = A. 6. A ∩ Φ = Φ. 7. A ∪ U = U. 8. A ∩ U = A. 9. A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C).(Union distributes over intersection) 10. A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C). (Intersection distributes over union) 11. A ∪ A^C = U. 12. A ∩ A^C = Φ. 13. (A ∪ B)^C = A^C ∩ B^C. (de’ Morgan’s law) 14. (A ∩ B)^C = A^C ∪ B^C. (de’ Morgan’s law) 15. A ∪ A = A ∩ A = A. 16. (A^C)^C = A. 17. A – B = A ∩ B^C. 18. (A – B) – C = A – (B ∪ C). 19. If A ∩ B = Φ, then (A ∪ B) – B = A. 20. A – (B ∪ C) = (A – B) ∩ (A – C). This algebra of sets is an example of a Boolean algebra, named after the 19th-century British mathematician George Boole, who applied the algebra to logic. The subject later found applications in electronics.

3 min read

METHODS OF SOLVING RECURRENCE RELATION: Now, in this section we shall discuss a few methods of solving recurrence relation and hence solve the relations that we have formulated in the Recurrence Relation section. Backtracking Method: This is the most intuitive way of solving a recurrence relation. In this method, we substitute for every term in the sequence in the form of previous term (i.e. an in the form of a_n–1, a_n–1 in the form of a_n–2 and so on) till we reach the initial condition and then substitute for the initial condition. To understand this better, we shall solve the recurrence relations that we have come across earlier. Example: Solve the recurrence relation in a_n = 1.06a_n–1, with a₀ = 0.5. Solution: Given recurrence relation is an = 1.06a_n–1, with a₀ = 0.5. From this equation, we have a_n = 1.06a_n–1 = 1.06 ≥ 1.06 an–2 = 1.06 ≥ 1.06 ≥ 1.06 an–3 Proceeding this way, we have a_n = (1.06)na₀. But, we know that a₀ = 0.5. Thus, explicit solution to the given recurrence relation is an = 0.5 ≥ (1.06)n for n ≥ 0. Example : Solve the Tower of Hanoi puzzle, using backtracking method. Solution: The recurrence relation, for the puzzle is: H_n = 1 if n = 1. H_n = 2H_n–1 1 otherwise. Thus, Hn = 2H_n–1 1 = H_n = 2 X (H_n–2 1) 1 = 2²H_n–2 2 1 = 2² (2H_n–3 1 ) 2 1 = 2³H_n–3 2² 2 1. Proceeding this way, we have

2 min read

FORMULATION OF RECURRENCE RELATION: Before we proceed with discussing various methods of solving recurrence relation, we shall formulate some recurrence relation. Example : With reference to Example 5.3, let Hn denote the number of moves required to solve the puzzle with n discs. Let us define Hn recursively. Solution: Clearly, H1 = 1. Consider top (n–1) discs. We can move these discs to the middle peg using H_n–1 moves. The nth disc on the first peg can then moved to the third peg. Finally, (n–1) discs from the middle peg can be moved to the third peg with first peg as auxiliary in Hn–1 moves. Thus, total number of moves needed to move n discs are: Hn = 2H_n–1 1. Hence the recurrence relation for the Tower of Hanoi is: Hn = 1 if n = 1. Hn = 2H_n–1 1 otherwise.

2 min read

INTRODUCTION: We often use relation to describe certain ordering on the sets. For example, lexicographical ordering is used for dictionary as well as phone directory. We schedule certain jobs as per certain ordering, such as priority. Ordering of numbers may be in the increasing order. In the previous chapter, we have discussed various properties (reflexive etc) of relation. In this chapter we use these to define ordering of the sets. Definition: A relation R on the set A is said to be partial order relation, if it is reflexive, anti-symmetric and transitive. Before we proceed further, we shall have a look at a few examples of partial order relations. Example : Let A = {a, b, c, d, e}. Relation R, represented using following matrix is a partial order relation.

2 min read

Subsets Definition: The set A is a subset of the set B, denoted A ⊆ B, if every element of A is also an element of B. Symbolically, A ⊆ B if ∀x[x ∈ A → x ∈ B] is true, and conversely. If A is a subset of B, we say that B is a superset of A, and write B ⊇ A. Clearly every set B is a subset of itself, B ⊆ B. (This is because, for any given x, x ∈ B → x ∈ B is ‘automatically’ true.) Any other subset of B is called a proper subset of B. The notation A ⊂ B is used to denote ‘A is a proper subset of B’. Thus A ⊂ B if and only if A ⊆ B and A = B. It should also be noted that φ ⊆ A for every set A. In this case definition 3.2 is satisfied in a vacuous way—the empty set has no elements, so certainly each of them belongs to A. Alternatively, for any object x, the proposition x ∈ φ is false so the conditional (x ∈ φ) →(x ∈ A) is true. To prove that two sets are equal, A = B, it is sufficient (and frequently very convenient) to show that each is a subset of the other, A ⊆ B and B ⊆ A. Essentially, this follows from the following logical equivalence of compound propositions: (P ↔ Q) ≡ [(P → Q) ∧ (Q → P)]. We know that A = B if ∀x(x ∈ A ↔ x ∈ B) is a true proposition. We noted that to prove that a biconditional P ↔ Q is true, it is sufficient to prove both conditionals P → Q and Q → P are true. It follows that to prove ∀x(x ∈ A ↔ x ∈ B) it is sufficient to prove both ∀x(x ∈ A → x ∈ B) and ∀x(x ∈ B → x ∈ A). But ∀x(x ∈ A → x ∈ B) is true precisely when A ⊆ B and similarly ∀x(x ∈ B → x ∈ A) is true precisely when B ⊆ A. In summary:

1 min read

DIAGRAMMATIC REPRESENTATION OF A SET: British mathematician, John Venn, devised a simple way to represent set theoretic operations diagrammatically. These diagrams are named after him as Venn Diagrams. Universal set is represented by a rectangle and its subsets using a circle within it. In the following figures, basic set theoretic operations are represented using Venn diagrams. Figure: A is a subset of universal set U.

3 min read

REPRESENTATION OF RELATIONS: Matrices and graphs are two very good tools to represent various algebraic structures. Matrices can be easily used to represent relation in any programming language in computer. Here we discuss the representation of relation on finite sets using these tools. Consider the relation in Example 3.1. Thus, if a R b, then we enter 1 in the cell (a, b) and 0 otherwise. Same relation can be represented pictorially as well, as follows:

1 min read

DIAGRAMMATIC REPRESENTATION OF PARTIAL ORDER RELATIONS AND POSETS: In the previous chapter, we have seen the diagraph of a relation. In this section, we use the diagraphs of the partial order relations, to represent the relations in a very suitable way known as Hasse diagram. We understand the Hasse diagrame, using following example. Example : Let A = {a, b, c, d, e} and the following diagram represents the diagraph of the partial order relation on A.

2 min read

Partial Order Relations on a Lattice A partial order relation on a lattice (L) follows as a consequence of the axioms for the binary operations ∨ and ∧ . We define a relation ≤ on L such that for a, b ∈ L , a ≤ b <-> a ∨ b = b or analogously, a ≤ b <-> a ∧ b = a . We note that (i) For any a ∈ L a ∨ a = a (idempotent law), therefore a ≤ a showing that ≤ is reflexive. (ii) Let a ≤ b and b ≤ a. Therefore a ∨ b = b b ∨ a = a But a ∨ b = b ∨ a (Commutative Law in lattice) Hence a = b , showing that ≤ is antisymmetric. (iii) Suppose that a ≤ b and b ≤ c. Therefore a ∨ b = b and b ∨ c = c . Then a ∨ c = a ∨ (b ∨ c) = (a ∨ b) ∨ c (Associativity in lattice) = b ∨ c = c , showing that a ≤ c and hence ≤ is transitive. This shows that a lattice is a partially ordered set

4 min read

Theorem: Let (L, ≤) be a lattice. If a, b, c ∈ L, then (1) a ∨ (b ∧ c) ≤ (a ∨ b) ∧ (a ∨ c) (2) a ∧ (b ∨ c) ≥ (a ∧ b) ∨ (a ∧ c) These inequalities are called “Distributive Inequalities”. Proof: We have a ≤ a ∨ b and a ≤ a ∨ c............... (i) Also, by the above theorem, if x ≤ y and x ≤ z in a lattice, then x ≤ y ∧ z. Therefore (i) yields a ≤ (a ∨ b ) ∧ (a ∨ c)................... (ii) Also b ∧ c ≤ b ≤ a ∨ b and b ∧ c ≤ c ≤ a ∨ c , that is, b ∧ c ≤ a ∨ b and b ∧ c ≤ a ∨ c and so, by the above argument, we have b ∧ c ≤ (a ∨ b) ∧ (a ∨ c).................. (iii) Also, again by the above theorem if x ≤ z and y ≤ z in a lattice, then x ∨ y ≤ z Hence, (ii) and (iii) yield a c (b ∨ c) ≤ ( a ∨ b) ∧ (a ∨ c) This proves......... (1). The second distributive inequality follows by using the principle of duality. Theorem: (Modular Inequality) : Let (L, ≤) be a lattice. If a, b, c ∈ L, then a ≤ c if and only if a ∨ (b ∧ c) ≤ (a ∨ b) ∧ c Proof: We know that a ≤ c <-> a ∨ c = c................ (1) Also, by distributive inequality, a ∨ (b ∧ c) ≤ (a ∨ b) ∧ (a ∨ c) Therefore using (1) a ≤ c if and only if a ∨ (b ∧ c) ≤ (a ∨ c) ∧Ù c, which proves the result. The modular inequalities can be expressed in the following way also: (a ∧ b) ∨ (a ∧ c) ≤ a ∧ [b ∨ (a ∧ c)] (a ∨ b) ∧ (a ∨ c) ≥ a ∨ [b ∧ (a ∨ c)] Example: Let (L, ≤) be a lattice and a, b, c ∈ L. If a ≤ b ≤ c, then (i) a ∨ b = b ∧ c, (ii) (a ∧ b ) ∨ (b ∧ c) = (a ∨ b) ∧ ( a ∨ c). Solution: (i) We know that a ≤ b <-> a ∨ b = b and b ≤ c <-> b ∧ c = b Hence a ≤ b ≤ c implies a ∨ b = b ∧ c. (ii) Since a ≤ b and b ≤ c, we have a ∨ b = a and b ∨ c = b Thus (a ∨ b) ∧ (b ∨ c) = a ∧ b = b, since a ≤ b <-> a ∨ b = b. Also, a ≤ b ≤ c
a ≤ c by transitivity. Then a ≤ b and a ≤ c
a ∨ b = b , a ∨ c = c and so (a ∨ b ) ∧ (a ∨ c) = b ∧ c = b since b ≤ c <-> b ∧ c = b. Hence (a ∧ b) ∨ (b ∧ c) = b = (a ∨ b) ∧ (a ∨ c), which proves (ii).

3 min read

Lattice Isomorphism Definition: Let (L1, ∨ 1, ∧ 1) and (L2, ∨ 2, ∧ 2) be two lattices. A mapping f : L1 -> L2 is called a lattice homomorphism from the lattice the lattice (L1, ∨ 1, ∧ 1) to (L2, ∨ 2, ∧ 2) if for any a, b ∈ L1, f(a ∨₁ b) = f(a) ∨₂ f(b) and f(a ∧₁ b) = f(a) ∧₂ f(b) Thus, here both the binary operations of join and meet are preserved. There may be mapping which preserve only one of the two operations. Such mapping are not lattice homomorphism. Let ≤₁ and ≤₂ be partial order relations on (L1, ∨₁, ∧₁) and (L2, ∨₂, ∧₂) respectively. Let f : L1 -> L2 be lattice homomorphism. If a, b ∈ L1, then a ≤1 b <-> a ∨₁ b = b

5 min read

Resolution: Computer programs have been developed to automate the task of reasoning and proving theorems. Many of these programs make use of a rule of inference known as resolution. This rule of inference is based on the tautology ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r). The final disjunction in the resolution rule, q ∨ r, is called the resolvent. When we let q = r in this tautology, we obtain (p ∨ q) ∧ (¬p ∨ q) → q. Furthermore, when we let r = F, we obtain (p ∨ q) ∧ (¬p) → q (because q ∨ F ≡ q), which is the tautology on which the rule of disjunctive syllogism is based. EXAMPLE 1 Use resolution to show that the hypotheses “Jasmine is skiing or it is not snowing” and “It is snowing or Bart is playing hockey” imply that “Jasmine is skiing or Bart is playing hockey.” Solution: Let p be the proposition “It is snowing,” q the proposition “Jasmine is skiing,” and r the proposition “Bart is playing hockey.”We can represent the hypotheses as ¬p ∨ q and p ∨ r, respectively. Using resolution, the proposition q ∨ r, “Jasmine is skiing or Bart is playing hockey,” follows. Resolution plays an important role in programming languages based on the rules of logic, such as Prolog (where resolution rules for quantified statements are applied). Furthermore, it can be used to build automatic theorem proving systems. To construct proofs in propositional logic using resolution as the only rule of inference, the hypotheses and the conclusion must be expressed as clauses, where a clause is a disjunction of variables or negations of these variables. We can replace a statement in propositional logic that is not a clause by one or more equivalent statements that are clauses. For example, suppose we have a statement of the form p ∨ (q ∧ r). Because p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), we can replace the single statement p ∨ (q ∧ r) by two statements p ∨ q and p ∨ r, each of which is a clause. We can replace a statement of the form ¬(p ∨ q) by the two statements ¬p and ¬q because De Morgan’s law tells us that ¬(p ∨ q) ≡ ¬p ∧¬q.We can also replace a conditional statement p → q with the equivalent disjunction ¬p ∨ q.

3 min read

The Transitive Closure of a Relation Definition: The Transitive closure of a relation R is the smallest transitive relation containing R. It is denoted by R^∞ . Example: Let A = {1, 2, 3, 4} and R = [(1, 2), (2, 3), (3, 4), (2, 1)] Find the transitive closure of R. Solution: The digraph of R is

2 min read

Least Upper Bounds and Latest Lower Bounds in a Lattice Let (L, ∨ , ∧ ) be a lattice and let a, b ∈ L. We now show that LUB of {a, b} ∈ L with respect to the partial order introduced above is a ∨ b and GLB of {a, b} is a ∧ b. From absorption law a ∧ (a ∨ b) = a b ∧ (a ∨ b) = b

3 min read

Example: Is the following lattice a distributive lattice ? Solution: The given lattice is not distributive since {0, a, d, e, I} is a sublattice which is isomorphic to the five-element lattice shown below :

2 min read

Sublattices Definition: Let (L, ≤) be a lattice. A non-empty subset S of L is called a sublattice of L if a Ú b ∈ S and a Ù b ∈ S whenever a ∈ S, b ∈ S. Or Let (L, ∨ , ∧ ) be a lattice and let S ⊆ L be a subset of L. Then (S, ∨ , ∧ ) is called a sublattice of (L, ∨ , ∧ ) if and only if S is closed under both operations of join(∨ ) and meet( ∧ ). From the definition it is clear that sublattice itself is a lattice. However, any subset of L which is a lattice need not be a sublattice. For example, consider the lattice shown in the diagram:

5 min read

Introduction: Boolean function can be represented by a Boolean sum of Boolean products of the variables and their complements. The solution of this problem shows that every Boolean function can be represented using the three Boolean operators ·, , and Boolean functions can be represented using only one operator. Both of these problems have practical importance in circuit design. Sum-of-Products Expansions: We will use examples to illustrate one importantway to find a Boolean expression that represents a Boolean function. DEFINITION 1 A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1, x2, . . . , xn is a Boolean product y1y2 · · · yn, where yi = xi or yi = xi . Hence, a minterm is a product of n literals, with one literal for each variable.

2 min read

Cartesian Product of Lattices Theorem: If (L1, ≤) and (L2, ≤) are lattices, then (L, ≤) is a lattice, where L = L1 X L2 and the partial order ≤ of L is the product partial order. Proof: We denote the join and meet in L1 by ∨1, and ∧1 and the join and meet in L2 by ∨2 and ∧2 respectively. We know that Cartesian product of two posets is a poset. Therefore L = L1 X L2 is a poset. Thus all we need to show is that if (a1, b1) and (a2, b2) Î L, then (a1, b1) Ú (a2, b2)and (a1, b1) ∈ (a2, b2) exist in L. Further, we know that

2 min read

The Abstract Definition of a Boolean Algebra: In this section we have focused on Boolean functions and expressions. However, the results we have established can be translated into results about propositions or results about sets. Because of this, it is useful to define Boolean algebras abstractly. Once it is shown that a particular structure is a Boolean algebra, then all results established about Boolean algebras in general apply to this particular structure. Boolean algebras can be defined in several ways. The most common way is to specify the properties that operations must satisfy, as is done in Definition 1. DEFINITION 1 A Boolean algebra is a set B with two binary operations ∨ and ∧, elements 0 and 1, and a unary operation such that these properties hold for all x, y, and z in B:

2 min read

Duality: The identities in Table 5 come in pairs (except for the law of the double complement and the unit and zero properties). To explain the relationship between the two identities in each pair we use the concept of a dual. The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean products and interchanging 0s and 1s. EXAMPLE 1 Find the duals of x(y 0) and x · 1 (y z). Solution: Interchanging · signs and signs and interchanging 0s and 1s in these expressions produces their duals. The duals are x (y · 1) and (x 0)(yz), respectively. The dual of a Boolean function F represented by a Boolean expression is the function represented by the dual of this expression. This dual function, denoted byFd , does not depend on the particular Boolean expression used to representF. An identity between functions represented by Boolean expressions remains valid when the duals of both sides of the identity are taken. (See Exercise 30 for the reason why this is true.) This result, called the duality principle, is useful for obtaining new identities. EXAMPLE 2 Construct an identity from the absorption law x(x y) = x by taking duals. Solution: Taking the duals of both sides of this identity produces the identity x xy = x, which is also called an absorption law and is shown in Table 5.

2 min read

A K-map in three variables is a rectangle divided into eight cells. The cells represent the eight possible minterms in three variables. Two cells are said to be adjacent if the minterms that they represent differ in exactly one literal. One of the ways to form a K-map in three variables is shown in Figure 5(a). This K-map can be thought of as lying on a cylinder, as shown in Figure 5(b). On the cylinder, two cells have a common border if and only if they are adjacent.

4 min read

Introduction: The efficiency of a combinational circuit depends on the number and arrangement of its gates.The process of designing a combinational circuit begins with the table specifying the output for each combination of input values. We can always use the sum-of-products expansion of a circuit to find a set of logic gates that will implement this circuit. However, the sum-of-products expansion may contain many more terms than are necessary. Terms in a sum-of-products expansion that differ in just one variable, so that in one term this variable occurs and in the other term the complement of this variable occurs, can be combined. For instance, consider the circuit that has output 1 if and only if x = y = z = 1 or x = z = 1 and y = 0. The sum-of-products expansion of this circuit is xyz xy¯z. The two products in this expansion differ in exactly one variable, namely, y. They can be combined as

4 min read

Boolean Functions Introduction: Boolean algebra provides the operations and the rules for working with the set {0, 1}. Electronic and optical switches can be studied using this set and the rules of Boolean algebra. The three operations in Boolean algebra that we will use most are complementation, the Boolean sum, and the Boolean product. The complement of an element, denoted with a bar, is defined by 0 = 1 and 1 = 0. The Boolean sum, denoted by or by OR, has the following values: 1 1 = 1, 1 0 = 1, 0 1 = 1, 0 0 = 0. The Boolean product, denoted by · or by AND, has the following values: 1 · 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 · 0 = 0. When there is no danger of confusion, the symbol · can be deleted, just as in writing algebraic products. Unless parentheses are used, the rules of precedence for Boolean operators are: first, all complements are computed, followed by all Boolean products, followed by all Boolean sums. This is illustrated in Example 1. EXAMPLE 1 Find the value of 1 · 0 (0 1). Solution: Using the definitions of complementation, the Boolean sum, and the Boolean product, it follows that

2 min read

Introduction: Reliability is the probability than an item can perform its intended function without failure for a specified interval under stated conditions.

2 min read

Identities of Boolean Algebra: There are many identities in Boolean algebra. The most important of these are displayed in Table 5. These identities are particularly useful in simplifying the design of circuits. Each of the identities in Table 5 can be proved using a table.We will prove one of the distributive laws in this way in Example 8. The proofs of the remaining properties are left as exercises for the reader. EXAMPLE 8 Show that the distributive law x(y z) = xy xz is valid. Solution: The verification of this identity is shown in Table 6. The identity holds because the last two columns of the table agree. The reader should compare the Boolean identities in Table 5 to the logical equivalences in Table 6. All are special cases of the same set of identities in a more abstract structure. Each collection of identities can be obtained by making the appropriate translations. For example, we can transform each of the identities in Table 5 into a logical equivalence by changing each Boolean variable into a propositional variable, each 0 into a F, each 1 into a T, each Boolean sum into a disjunction, each Boolean product into a conjunction, and each complementation into a negation, as we illustrate in Example 9.

4 min read

Introduction: Boolean algebra is used to model the circuitry of electronic devices. Each input and each output of such a device can be thought of as a member of the set {0, 1}.A computer, or other electronic device, is made up of a number of circuits. Each circuit can be designed using the rules of Boolean algebra that were studied in Boolean algebra. The basic elements of circuits are called gates. Each type of gate implements a Boolean operation. In this section we define several types of gates. Using these gates, we will apply the rules of Boolean algebra to design circuits that perform a variety of tasks. The circuits that we will study in this chapter give output that depends only on the input, and not on the current state of the circuit. In other words, these circuits have no memory capabilities. Such circuits are called combinational circuits or gating networks.

6 min read

Quantifiers When the variables in a propositional function are assigned values, the resulting statement becomes a proposition with a certain truth value. However, there is another importantway, called quantification, to create a proposition from a propositional function. Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications. We will focus on two types of quantification here: universal quantification, which tells us that a predicate is true for every element under consideration, and existential quantification, which tells us that there is one or more element under consideration for which the predicate is true. The area of logic that deals with predicates and quantifiers is called the predicate calculus. THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain. Such a statement is expressed using universal quantification. The universal quantification of P(x) for a particular domain is the proposition that asserts that P(x) is true for all values of x in this domain. Note that the domain specifies the possible values of the variable x. The meaning of the universal quantification of P(x) changes when we change the domain. The domain must always be specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined. DEFINITION 1 The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier.We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x).

3 min read

Definition: A lattice is a partially ordered set (L, £) in which every subset {a, b} consisting of two element has a least upper bound and a greatest lower bound. We denote lub({a, b}) by a ∨ b and call it join or sum of a and b. Similarly, we denote GLB({a, b}) by a ∧ b and call it meet or product of a and b. Other symbol used are:

3 min read

Don’t Care Conditions In some circuits we care only about the output for some combinations of input values, because other combinations of input values are not possible or never occur. This gives us freedom in producing a simple circuit with the desired output because the output values for all those combinations that never occur can be arbitrarily chosen. The values of the function for these combinations are called don’t care conditions. A d is used in a K-map to mark those combinations of values of the variables for which the function can be arbitrarily assigned. In the minimization process we can assign 1s as values to those combinations of the input values that lead to the largest blocks in the K-map. This is illustrated in Example 1. EXAMPLE 1 One way to code decimal expansions using bits is to use the four bits of the binary expansion of each digit in the decimal expansion. For instance, 873 is encoded as 100001110011. This encoding of a decimal expansion is called a binary coded decimal expansion. Because there are 16 blocks of four bits and only 10 decimal digits, there are six combinations of four bits that are not used to encode digits. Suppose that a circuit is to be built that produces an output of 1 if the decimal digit is 5 or greater and an output of 0 if the decimal digit is less than 5. How can this circuit be simply built using OR gates, AND gates, and inverters? Solution: Let F(w, x, y, z) denote the output of the circuit, where wxyz is a binary expansion of a decimal digit. The values of F are shown in Table 1. The K-map for F, with ds in the don’t care positions, is shown in Figure 11(a). We can either include or exclude squares with ds from blocks. This gives us many possible choices for the blocks. For example, excluding all squares with ds and forming blocks, as shown in Figure 11(b), produces the expression . Including some of the ds and excluding others and forming blocks, as

1 min read

Lattices as Algebraic System Definition. A Lattice is an algebraic system (L, ∨ , ∧ ) with two binary operations ∨ and ∧ , called join and meet respectively, on a non-empty set L which satisfy the following axioms for a, b, c ∈ L : 1. Commutative Law : a ∨ b = b ∨ a and a ∧ b = b ∧ a .

3 min read

Using Rules of Inference to Build Arguments: When there are many premises, several rules of inference are often needed to show that an argument is valid. This is illustrated by Examples 1 and 2, where the steps of arguments are displayed on separate lines, with the reason for each step explicitly stated. These examples also show how arguments in English can be analyzed using rules of inference. EXAMPLE 1 Show that the premises “It is not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.” Solution: Let p be the proposition “It is sunny this afternoon,” q the proposition “It is colder than yesterday,” r the proposition “We will go swimming,” s the proposition “We will take a canoe trip,” and t the proposition “We will be home by sunset.” Then the premises become ¬p ∧ q, r → p,¬r → s, and s → t . The conclusion is simply t . We need to give a valid argument with premises ¬p ∧ q, r → p, ¬r → s, and s → t and conclusion t . We construct an argument to show that our premises lead to the desired conclusion as follows.

6 min read

Translating from Nested Quantifiers into English: Expressions with nested quantifiers expressing statements in English can be quite complicated. The first step in translating such an expression is to write out what the quantifiers and predicates in the expression mean. The next step is to express this meaning in a simpler sentence. EXAMPLE 1 Translate the statement ∀x(C(x) ∨ ∃y(C(y) ∧ F(x, y))) into English, where C(x) is “x has a computer,” F(x, y) is “x and y are friends,” and the domain for both x and y consists of all students in your school. Solution: The statement says that for every student x in your school, x has a computer or there is a student y such that y has a computer and x and y are friends. In other words, every student in your school has a computer or has a friend who has a computer. EXAMPLE 2 Translate the statement ∃x∀y∀z((F (x, y) ∧ F(x, z) ∧ (y = z))→¬F(y,z)) into English, where F(a,b) means a and b are friends and the domain for x, y, and z consists of all students in your school. Solution: We first examine the expression (F (x, y) ∧ F(x, z) ∧ (y = z))→¬F(y, z). This expression says that if students x and y are friends, and students x and z are friends, and furthermore, if y and z are not the same student, then y and z are not friends. It follows that the original statement, which is triply quantified, says that there is a student x such that for all students y and all students z other than y, if x and y are friends and x and z are friends, then y and z are not friends. In other words, there is a student none of whose friends are also friends with each other. Translating English Sentences into Logical Expressions Quantifiers can be used to translate sentences into logical expressions. However, we avoided sentences whose translation into logical expressions required the use of nested quantifiers.We now address the translation of such sentences. EXAMPLE 3 Express the statement “If a person is female and is a parent, then this person is someone’s mother” as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives. Solution: The statement “If a person is female and is a parent, then this person is someone’s mother” can be expressed as “For every person x, if person x is female and person x is a parent, then there exists a person y such that person x is the mother of person y.” We introduce the propositional functions F(x) to represent “x is female,” P(x) to represent “x is a parent,” and M(x, y) to represent “x is the mother of y.” The original statement can be represented as ∀x((F (x) ∧ P(x)) → ∃yM(x, y)). Using the null quantification rule in part (b) of Exercise 47 in Section 1.4, we can move ∃y to the left so that it appears just after ∀x, because y does not appear in F(x) ∧ P(x). We obtain the logically equivalent expression ∀x∃y((F (x) ∧ P(x)) → M(x, y)). EXAMPLE 4 Express the statement “Everyone has exactly one best friend” as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives. Solution: The statement “Everyone has exactly one best friend” can be expressed as “For every person x, person x has exactly one best friend.” Introducing the universal quantifier, we see that this statement is the same as “∀x(person x has exactly one best friend),” where the domain consists of all people.

4 min read

DEFINITION A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint). Such a drawing is called a planar representation of the graph. A graph may be planar even if it is usually drawn with crossings, because it may be possible to draw it in a different way without crossings. EXAMPLE 1 Is K4 (shown in Figure 2 with two edges crossing) planar? Solution: K4 is planar because it can be drawn without crossings, as shown in Figure 3. EXAMPLE 2 Is Q3, shown in Figure 4, planar? Solution: Q3 is planar, because it can be drawn without any edges crossing, as shown in Figure 5. We can show that a graph is planar by displaying a planar representation. It is harder to show that a graph is nonplanar.We will give an example to show how this can be done in an ad hoc fashion. Later we will develop some general results that can be used to do this.

2 min read

DEFINITION 3 Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. Table 3 displays the truth table for p ∨ q.

4 min read

Introduction: We have discussed rules of inference for propositions.We will nowdescribe some important rules of inference for statements involving quantifiers. These rules of inference are used extensively in mathematical arguments, often without being explicitly mentioned. Universal instantiation is the rule of inference used to conclude that P(c) is true, where c is a particular member of the domain, given the premise ∀xP(x). Universal instantiation is used when we conclude from the statement “All women are wise” that “Lisa is wise,” where Lisa is a member of the domain of all women.

6 min read

Nested Quantifiers Introduction: Nested quantifiers, are one quantifier is within the scope of another, such as ∀x∃y(x y = 0). Note that everything within the scope of a quantifier can be thought of as a propositional function. For example, ∀x∃y(x y = 0) is the same thing as ∀xQ(x), where Q(x) is ∃yP(x, y), where P(x, y) is x y = 0. Nested quantifiers commonly occur in mathematics and computer science. Although nested quantifiers can sometimes be difficult to understand, In this section we will gain experience working with nested quantifiers.We will see how to use nested quantifiers to express mathematical statements such as “The sum of two positive integers is always positive.” We will show how nested quantifiers can be used to translate English sentences such as “Everyone has exactly one best friend” into logical statements. Moreover, we will gain experience working with the negations of statements involving nested quantifiers. Understanding Statements Involving Nested Quantifiers: To understand statements involving nested quantifiers, we need to unravel what the quantifiers and predicates that appear mean. This is illustrated in Examples 1 and 2.

3 min read

Precedence of Logical Operators We can construct compound propositions using the negation operator and the logical operators defined so far.We will generally use parentheses to specify the order in which logical operators in a compound proposition are to be applied. For instance, (p ∨ q) ∧ (¬r) is the conjunction of p ∨ q and ¬r. However, to reduce the number of parentheses, we specify that the negation operator is applied before all other logical operators. This means that ¬p ∧ q is the conjunction of¬p and q, namely, (¬p) ∧ q, not the negation of the conjunction ofp and q, namely¬(p ∧ q). Another general rule of precedence is that the conjunction operator takes precedence over the disjunction operator, so that p ∧ q ∨ r means (p ∧ q) ∨ r rather than p ∧ (q ∨ r). Because this rule may be difficult to remember, we will continue to use parentheses so that the order of the disjunction and conjunction operators is clear. Finally, it is an accepted rule that the conditional and biconditional operators → and ↔ have lower precedence than the conjunction and disjunction operators, ∧ and ∨. Consequently, p ∨ q → r is the same as (p ∨ q) → r. We will use parentheses when the order of the conditional operator and biconditional operator is at issue, although the conditional operator has precedence over the biconditional operator. Table 8 displays the precedence levels of the logical operators, ¬, ∧, ∨,→, and↔. Logic and Bit Operations Computers represent information using bits.A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one). This meaning of the word bit comes from binary digit, because zeros and ones are the digits used in binary representations of numbers. The well-known statistician John Tukey introduced this terminology in 1946.A bit can be used to represent a truth value, because there are two truth values, namely, true and false. As is customarily done, we will use a 1 bit to represent true and a 0 bit to represent false. That is, 1 represents T (true), 0 represents F (false).A variable is called a Boolean variable if its value is either true or false. Consequently, a Boolean variable can be represented using a bit. Computer bit operations correspond to the logical connectives. By replacing true by a one and false by a zero in the truth tables for the operators ∧, ∨, and ⊕, the tables shown in Table 9 for the corresponding bit operations are obtained.We will also use the notation OR, AND, and XOR for the operators ∨,∧, and ⊕, as is done in various programming languages.

3 min read

INTRODUCTION : Mathematics is an exact science. Every statement in Mathematics must be precise. Also there can’t be Mathematics without proofs and each proof needs proper reasoning. Proper reasoning involves logic. The dictionary meaning of ‘Logic’ is the science of reasoning. The rules of logic gives precise meaning to mathematic statements. These rules are used to distinguished between valid & invalid mathematical arguments. In addition to its importance in mathematical reasoning, logic has numerous applications in computer science to verify the correctness of programs & to prove the theorems in natural & physical sciences to draw conclusion from experiments, in social sciences & in our daily lives to solve a multitude of problems. The area of logic that deals with propositions is called the propositional calculus or propositional logic. The mathematical approach to logic was first discussed by British mathematician George Boole; hence the mathematical logic is also called as Boolean logic.

1 min read

LOGICAL IMPLICATIONS: A proposition P (p, q, ……..) is said to logically imply a proposition Q (p, q,…….) written, P (p, q, ……..) → Q (p, q, …….) if Q (p, q, …….) is true whenever P (p, q, …….) is true. Example : P → (P ∨Q) Solution : Consider the truth table for this

1 min read

iv) The truth table is as follows. All the entries in the last column are ‘F’. Hence it is contradiction.

4 min read

Rules of Inference for Propositional Logic: We can always use a truth table to show that an argument form is valid.We do this by showing that whenever the premises are true, the conclusion must also be true. However, this can be a tedious approach. For example, when an argument form involves 10 different propositional variables, to use a truth table to show this argument form is valid requires 210 = 1024 different rows. Fortunately, we do not have to resort to truth tables. Instead, we can first establish the validity of some relatively simple argument forms, called rules of inference. These rules of inference can be used as building blocks to construct more complicated valid argument forms. We will now introduce the most important rules of inference in propositional logic. The tautology (p ∧ (p → q)) → q is the basis of the rule of inference called modus ponens, or the law of detachment. (Modus ponens is Latin for mode that affirms.) This tautology leads to the following valid argument form, which we have already seen in our initial discussion about arguments (where, as before, the symbol ∴ denotes “therefore”): p p → q ∴ q Using this notation, the hypotheses are written in a column, followed by a horizontal bar, followed by a line that begins with the therefore symbol and ends with the conclusion. In particular, modus ponens tells us that if a conditional statement and the hypothesis of this conditional statement are both true, then the conclusion must also be true. Example 1 illustrates the use of modus ponens. EXAMPLE 1 Suppose that the conditional statement “If it snows today, then we will go skiing” and its hypothesis, “It is snowing today,” are true. Then, by modus ponens, it follows that the conclusion of the conditional statement, “We will go skiing,” is true. As we mentioned earlier, a valid argument can lead to an incorrect conclusion if one or more of its premises is false.We illustrate this again in Example 2. EXAMPLE 2 Determine whether the argument given here is valid and determine whether its conclusion must be true because of the validity of the argument.

3 min read

Normal Form of a well formed formula : One of the main problem in logic is to determine whether the given statement is a tautology or a contradiction. One method to determine it is the method of truth tables. Other method is to reduce the statement form to, called normal form. If P & Q are two propositional variables we get various well formed formula. The number of distinct truth values for formulas in P and Q is 2⁴. Thus there are only 16 distinct formulae & any formula in P & Q is equivalent to one of these formulas. Here we give a method of reducing a given formula to an equivalent form called a ‘normal form’. We use ‘sum’ for disjunction, ‘product’ for conjunction and ‘literal’ either for P or for ¬ P , where P is any propositional variable. Elementary Sum & Elementary Product : An elementary sum is a sum of literals. An elementary product is a product of literals. e.g. P ∨ ¬ Q, P ∨ ¬ R are elementary sum P ∧ ¬ Q, ¬ P ∧ Q are elementary products.

2 min read

Principle Disjunctive Normal Form : A formula α is in principle disjunctive normal form if α is a sum of min terms. Steps to Construct Principle Disjunctive Normal Form of a given Formula : - 1. First obtain the disjunctive normal form for given formula. 2. Drop elementary products, which are contradiction such as (P∧ ¬ P) 3. If Pi & ¬ Pi are not present in an elementary product α , replace α by 4. Use the above step until all elementary products are reduced to sum of min terms.

4 min read

Introduction: Proofs in mathematics are valid arguments that establish the truth of mathematical statements. By an argument, we mean a sequence of statements that end with a conclusion. By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument. That is, an argument is valid if and only if it is impossible for all the premises to be true and the conclusion to be false. To deduce new statements from statements we already have, we use rules of inference which are templates for constructing valid arguments. Rules of inference are our basic tools for establishing the truth of statements. Valid Arguments in Propositional Logic: Consider the following argument involving propositions (which, by definition, is a sequence of propositions): “If you have a current password, then you can log onto the network.” “You have a current password.” Therefore, “You can log onto the network.” We would like to determine whether this is a valid argument. That is, we would like to determine whether the conclusion “You can log onto the network” must be true when the premises “If you have a current password, then you can log onto the network” and “You have a current password” are both true. Before we discuss the validity of this particular argument, we will look at its form. Use p to represent “You have a current password” and q to represent “You can log onto the network.” Then, the argument has the form p → q p ∴ q where ∴ is the symbol that denotes “therefore.” We know that when p and q are propositional variables, the statement ((p → q) ∧ p) → q is a tautology (see Exercise 10(c) in Section 1.3). In particular, when both p → q and p are true, we know that q must also be true.We say this form of argument is valid because whenever all its premises (all statements in the argument other than the final one, the conclusion) are true, the conclusion must also be true. Now suppose that both “If you have a current password, then you can log onto the network” and “You have a current password” are true statements. When we replace p by “You have a current password” and q by “You can log onto the network,” it necessarily follows that the conclusion “You can log onto the network” is true. This argument is valid because its form is valid. Note that whenever we replace p and q by propositions where p → q and p are both true, then q must also be true.

2 min read

Truth Tables of Compound Propositions We have now introduced four important logical connectives—conjunctions, disjunctions, conditional statements, and biconditional statements—as well as negations.We can use these connectives to build up complicated compound propositions involving any number of propositional variables.We can use truth tables to determine the truth values of these compound propositions, as Example 1 illustrates. We use a separate column to find the truth value of each compound expression that occurs in the compound proposition as it is built up. The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table. EXAMPLE 1 Construct the truth table of the compound proposition (p ∨¬q) → (p ∧ q). Solution: Because this truth table involves two propositional variables p and q, there are four rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF. The first two columns are used for the truth values of p and q, respectively. In the third column we find the truth value of ¬q, needed to find the truth value of p ∨¬q, found in the fourth column. The fifth column gives the truth value of p ∧ q. Finally, the truth value of (p ∨¬q) → (p ∧ q) is found in the last column. The resulting truth table is shown in Table 7.

2 min read

Logic Puzzles Puzzles that can be solved using logical reasoning are known as logic puzzles. Solving logic puzzles is an excellent way to practice working with the rules of logic. Also, computer programs designed to carry out logical reasoning often use well-known logic puzzles to illustrate their capabilities. Many people enjoy solving logic puzzles, published in periodicals, books, and on theWeb, as a recreational activity. Logic Circuits: Propositional logic can be applied to the design of computer hardware. This was first observed in 1938 by Claude Shannon in his MIT master’s thesis. In Chapter 12 we will study this topic in depth. (See that chapter for a biography of Shannon.) We give a brief introduction to this application here. A logic circuit (or digital circuit) receives input signals p1, p2, . . . , pn, each a bit [either 0 (off) or 1 (on)], and produces output signals s1, s2, . . . , sn, each a bit. In this section we will restrict our attention to logic circuits with a single output signal; in general, digital circuits may have multiple outputs.

1 min read

Principal Conjunctive Normal form : A formula α is in principle conjugate normal form if α is a product of max terms. For obtaining the principle conjunctive normal form of α we can construct the principle disjunctive normal form of α ¬ and apply negation. Example: Obtain a conjunctive normal form of 1) Consider

2 min read

LOGICAL OPERATIONS OR LOGICAL CONNECTIVES : The phrases or words which combine simple statements are called logical connectives. For example, ‘and’, ‘or’, ‘note’, ‘if……then’, ‘either…….or’ etc…. In the following table we list some possible connectives, their symbols & the nature of the compound statement formed by them.

7 min read

Propositional Satisfiability: Acompound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. Note that a compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variables, that is, if and only if its negation is a tautology. When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem. However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false. Although we can always use a truth table to determine whether a compound proposition is satisfiable, it is often more efficient not to, as Example 1 demonstrates. EXAMPLE 1 Determine whether each of the compound propositions (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p), (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r), and (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) is satisfiable.

2 min read

EXAMPLE 2 Determine whether the graphs G and H displayed in Figure 12 are isomorphic. Solution: BothGandH have six vertices and seven edges. Both have four vertices of degree two and two vertices of degree three. It is also easy to see that the subgraphs of G and H consisting of all vertices of degree two and the edges connecting them are isomorphic (as the reader should verify). Because G and H agree with respect to these invariants, it is reasonable to try to find an isomorphism f . We now will define a function f and then determine whether it is an isomorphism. Because deg(u1) = 2 and because u1 is not adjacent to any other vertex of degree two, the image of u1 must be either v4 or v6, the only vertices of degree two in H not adjacent to a vertex of degree two. We arbitrarily set f (u1) = v6. [If we found that this choice did not lead to isomorphism, we would then try f (u1) = v4.] Because u2 is adjacent to u1, the possible images of u2 are v3 and v5. We arbitrarily set f (u2) = v3. Continuing in this way, using adjacency of vertices and degrees as a guide, we set f (u3) = v4, f (u4) = v5, f (u5) = v1, and f (u6) = v2.We nowhave a one-to-one correspondence between the vertex set of G and the vertex set of H, namely, f (u1) = v6, f (u2) = v3, f (u3) = v4, f (u4) = v5, f (u5) = v1, f (u6) = v2. To see whether f preserves edges, we examine the adjacency matrix of G,

4 min read

Trees as Models: Trees are used as models in such diverse areas as computer science, chemistry, geology, botany, and psychology.We will describe a variety of such models based on trees. EXAMPLE 5 Saturated Hydrocarbons andTrees Graphs can be used to represent molecules, where atoms are represented by vertices and bonds between them by edges. The English mathematicianArthur Cayley discovered trees in 1857 when he was trying to enumerate the isomers of compounds of the form C_nH_{2n 2}, which are called saturated hydrocarbons.

5 min read

Introduction: When edges and vertices are removed from a graph, without removing endpoints of any remaining edges, a smaller graph is obtained. Such a graph is called a subgraph of the original graph. DEFINITION A subgraph of a graph G = (V ,E) is a graph H = (W, F), where W ⊆ V and F ⊆ E. A subgraph H of G is a proper subgraph of G if H = G. Given a set of vertices of a graph, we can form a subgraph of this graph with these vertices and the edges of the graph that connect them. DEFINITION Let G = (V ,E) be a simple graph. The subgraph induced by a subsetW of the vertex set V is the graph (W, F), where the edge set F contains an edge in E if and only if both endpoints of this edge are in W.

6 min read

Paths and Isomorphism: There are several ways that paths and circuits can help determine whether two graphs are isomorphic. For example, the existence of a simple circuit of a particular length is a useful invariant that can be used to show that two graphs are not isomorphic. In addition, paths can be used to construct mappings that may be isomorphisms. As we mentioned, a useful isomorphic invariant for simple graphs is the existence of a simple circuit of length k, where k is a positive integer greater than 2. Example 1 illustrates how this invariant can be used to show that two graphs are not isomorphic. EXAMPLE 1 Determine whether the graphs G and H shown in Figure 6 are isomorphic. Solution: Both G and H have six vertices and eight edges. Each has four vertices of degree three, and two vertices of degree two. So, the three invariants—number of vertices, number of edges, and degrees of vertices—all agree for the two graphs. However, H has a simple circuit of length three, namely, v1, v2, v6, v1, whereas G has no simple circuit of length three, as can be determined by inspection (all simple circuits in G have length at least four). Because the existence of a simple circuit of length three is an isomorphic invariant, G and H are not isomorphic.

8 min read

Introduction: A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph. As the path travels along its edges, it visits the vertices along this path, that is, the endpoints of these edges. DEFINITION 1 Let n be a nonnegative integer and G an undirected graph. A path of length n from u to v in G is a sequence of n edges e1, . . . , en of G for which there exists a sequence x0 = u, x1, . . . , xn−1, xn = v of vertices such that ei has, for i = 1, . . . , n, the endpoints xi−1 and xi . When the graph is simple, we denote this path by its vertex sequence x0, x1, . . . , xn (because listing these vertices uniquely determines the path). The path is a circuit if it begins and ends at the same vertex, that is, if u = v, and has length greater than zero. The path or circuit is said to pass through the vertices x1, x2, . . . , xn−1 or traverse the edges e1, e2, . . . , en. A path or circuit is simple if it does not contain the same edge more than once. When it is not necessary to distinguish between multiple edges, we will denote a path e1, e2, . . . , en, where ei is associated with {xi−1, xi } for i = 1, 2, . . . , n by its vertex sequence x0, x1, . . . , xn. This notation identifies a path only as far as which vertices it passes through. Consequently, it does not specify a unique path when there is more than one path that passes through this sequence of vertices, which will happen if and only if there are multiple edges between some successive vertices in the list. Note that a path of length zero consists of a single vertex.

7 min read

Introduction: Sometimes the removal from a graph of a vertex and all incident edges produces a subgraph with more connected components. Such vertices are called cut vertices (or articulation points). The removal of a cut vertex from a connected graph produces a subgraph that is not connected. Analogously, an edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge. Note that in a graph representing a computer network, a cut vertex and a cut edge represent an essential router and an essential link that cannot fail for all computers to be able to communicate. EXAMPLE 1 Find the cut vertices and cut edges in the graph G1 shown in Figure 4. Solution: The cut vertices of G1 are b, c, and e. The removal of one of these vertices (and its adjacent edges) disconnects the graph. The cut edges are {a, b} and {c, e}. Removing either one of these edges disconnects G1. VERTEX CONNECTIVITY Not all graphs have cut vertices. For example, the complete graph Kn, where n ≥ 3, has no cut vertices. When you remove a vertex from Kn and all edges incident to it, the resulting subgraph is the complete graph K_n−1, a connected graph. Connected graphs without cut vertices are called nonseparable graphs, and can be thought of as more connected than those with a cut vertex.We can extend this notion by defining a more granulated measure of graph connectivity based on the minimum number of vertices that can be removed to disconnect a graph.

1 min read

Representing Graphs: One way to represent a graph without multiple edges is to list all the edges of this graph. Another way to represent a graph with no multiple edges is to use adjacency lists, which specify the vertices that are adjacent to each vertex of the graph. EXAMPLE 1 Use adjacency lists to describe the simple graph given in Figure 1. Solution: Table 1 lists those vertices adjacent to each of the vertices of the graph.

4 min read

Connectedness in Undirected Graphs: When does a computer network have the property that every pair of computers can share information, if messages can be sent through one or more intermediate computers? When a graph is used to represent this computer network, where vertices represent the computers and edges represent the communication links, this question becomes: When is there always a path between two vertices in the graph? DEFINITION 1 An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph. An undirected graph that is not connected is called disconnected. We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph. Thus, any two computers in the network can communicate if and only if the graph of this network is connected. EXAMPLE 1 The graph G1 in Figure 2 is connected, because for every pair of distinct vertices there is a path between them (the reader should verify this). However, the graph G2 in Figure 2 is not connected. For instance, there is no path in G2 between vertices a and d.

3 min read

Applications of Graph Colorings: Graph coloring has a variety of applications to problems involving scheduling and assignments. (Note that because no efficient algorithm is known for graph coloring, this does not lead to efficient algorithms for scheduling and assignments.) Examples of such applications will be given here. The first application deals with the scheduling of final exams. EXAMPLE 1 Scheduling Final Exams How can the final exams at a university be scheduled so that no student has two exams at the same time? Solution: This scheduling problem can be solved using a graph model, with vertices representing courses and with an edge between two vertices if there is a common student in the courses they represent. Each time slot for a final exam is represented by a different color. A scheduling of the exams corresponds to a coloring of the associated graph. For instance, suppose there are seven finals to be scheduled. Suppose the courses are numbered 1 through 7. Suppose that the following pairs of courses have common students: 1 and 2, 1 and 3, 1 and 4, 1 and 7, 2 and 3, 2 and 4, 2 and 5, 2 and 7, 3 and 4, 3 and 6, 3 and 7, 4 and 5, 4 and 6, 5 and 6, 5 and 7, and 6 and 7. In Figure 8 the graph associated with this set of classes is shown. A scheduling consists of a coloring of this graph. Because the chromatic number of this graph is 4 (the reader should verify this), four time slots are needed.Acoloring of the graph using four colors and the associated schedule are shown in Figure 9.

2 min read

ABOUND FOR THE NUMBEROF LEAVES INANm-ARYTREE It is often useful to have an upper bound for the number of leaves in an m-ary tree. Theorem 5 provides such a bound in terms of the height of the m-ary tree. THEOREM 5 There are at most m^h leaves in an m-ary tree of height h. Proof: The proof uses mathematical induction on the height. First, consider m-ary trees of height 1. These trees consist of a root with no more than m children, each of which is a leaf. Hence, there are no more than m1 = m leaves in an m-ary tree of height 1. This is the basis step of the inductive argument. Nowassume that the result is true for allm-ary trees of height less than h; this is the inductive hypothesis. Let T be an m-ary tree of height h. The leaves of T are the leaves of the subtrees of T obtained by deleting the edges from the root to each of the vertices at level 1, as shown in Figure 15. Each of these subtrees has height less than or equal to h − 1. So by the inductive hypothesis, each of these rooted trees has at most mh−1 leaves. Because there are at most m such subtrees, each with a maximum of mh−1 leaves, there are at most m · mh−1 = mh leaves in the rooted tree. This finishes the inductive argument.

2 min read

Incidence Matrices: Another common way to represent graphs is to use incidence matrices. Let G = (V ,E) be an undirected graph. Suppose that v1, v2, . . . , vn are the vertices and e1, e2, . . . , em are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the n × m matrix M = [mij ], where EXAMPLE 1 Represent the graph shown in Figure 6 with an incidence matrix. Solution: The incidence matrix is

3 min read

Introduction: A graph G consists of a set of objects V = {v1, v2, v3, ......} called vertices (also called points or nodes) and other set E = {e1, e2, e3, .......} whose elements are called edges (also called lines or arcs). The set V(G) is called the vertex set of G and E(G) is the edge set. Usually the graph is denoted as G = (V, E) Let G be a graph and {u, v} an edge of G. Since {u, v} is 2-element set, we may write {v, u} instead of {u, v}. It is often more convenient to represent this edge by uv or vu. If e = uv is an edge of a graph G, then we say that u and v are adjacent in G and that e joins u and v. (We may also say that each that of u and v is adjacent to or with the other). For example : A graph G is defined by the sets V(G) = {u, v, w, x, y, z} and E(G) = {uv, uw, wx, xy, xz}.

3 min read

Applications of Trees Binary Search Trees: Searching for items in a list is one of the most important tasks that arises in computer science. Our primary goal is to implement a searching algorithm that finds items efficiently when the items are totally ordered. This can be accomplished through the use of a binary search tree, which is a binary tree in which each child of a vertex is designated as a right or left child, no vertex has more than one right child or left child, and each vertex is labeled with a key, which is one of the items. Furthermore, vertices are assigned keys so that the key of a vertex is both larger than the keys of all vertices in its left subtree and smaller than the keys of all vertices in its right subtree. This recursive procedure is used to form the binary search tree for a list of items. Start with a tree containing just one vertex, namely, the root. The first item in the list is assigned as the key of the root. To add a new item, first compare it with the keys of vertices already in the tree, starting at the root and moving to the left if the item is less than the key of the respective vertex if this vertex has a left child, or moving to the right if the item is greater than the key of the

5 min read

INFORMATION NETWORKS Graphs can be used to model various networks that link particular types of information. Here, we will describe how to model theWorldWideWeb using a graph. We will also describe how to use a graph to model the citations in different types of documents. TheWeb Graph TheWorldWideWeb can be modeled as a directed graph where eachWeb page is represented by a vertex and where an edge starts at the Web page a and ends at the Web page b if there is a link on a pointing to b. Because newWeb pages are created and others removed somewhere on the Web almost every second, the Web graph changes on an almost continual basis. Many people are studying the properties of theWeb graph to better understand the nature of theWeb.We will return toWeb graphs in Section 10.4, and in Chapter 11 we will explain how theWeb graph is used by theWeb crawlers that search engines use to create indexes ofWeb pages. EXAMPLE 6 Citation Graphs Graphs can be used to represent citations in different types of documents, including academic papers, patents, and legal opinions. In such graphs, each document is represented by a vertex, and there is an edge from one document to a second document if the

2 min read

TREE TRAVERSAL A traversal of a tree is a process to traverse a tree in a systematic way so that each vertex is visited exactly once. Three commonly used traversals are preorder, postorder and inorder. We describe here these three process that may be used to traverse a binary tree. Preorder traversal The preorder traversal of a binary tree is defined recursively as follows (i) Visit the root (ii) Traverse the left subtree in preorder. (iii) Traverse the right subtree in preorder Postorder traversal The postorder traversal of a binary tree is defined recursively as follows (i) Traverse the left subtree in postorder (ii) Traverse the right subtree in postorder (iii) Visit the root.

6 min read

Bipartite Graphs: Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets such that each edge connects a vertex in one of these subsets to a vertex in the other subset. For example, consider the graph representing marriages between men and women in a village, where each person is represented by a vertex and a marriage is represented by an edge. In this graph, each edge connects a vertex in the subset of vertices representing males and a vertex in the subset of vertices representing females. This leads us to Definition 5. DEFINITION 6 A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2). When this condition holds, we call the pair (V1, V2) a bipartition of the vertex set V of G. In Example1 we will show that C6 is bipartite, and in Example 10 we will show that K3 is not bipartite. EXAMPLE 1 C6 is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and every edge of C6 connects a vertex in V1 and a vertex in V2. EXAMPLE 2 K3 is not bipartite. To verify this, note that if we divide the vertex set of K3 into two disjoint sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices could not be connected by an edge, but in K3 each vertex is connected to every other vertex by an edge. EXAMPLE 3 Are the graphs G and H displayed in Figure 8 bipartite?

5 min read

Basic Terminology: First, we give some terminology that describes the vertices and edges of undirected graphs. DEFINITION 1 Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v. We will also find useful terminology describing the set of vertices adjacent to a particular vertex of a graph.

3 min read

Introduction: A directed graph (or digraph) (V ,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u, v) is said to start at u and end at v. When we depict a directed graph with a line drawing, we use an arrow pointing from u to v to indicate the direction of an edge that starts at u and ends at v.A directed graph may contain loops and it may contain multiple directed edges that start and end at the same vertices.Adirected graph may also contain directed edges that connect vertices u and v in both directions; that is, when a digraph contains an edge from u to v, it may also contain one or more edges from v to u. Note that we obtain a directed graph when we assign a direction to each edge in an undirected graph.When a directed graph has no loops and has no multiple directed edges, it is called a simple directed graph. Because a simple directed graph has at most one edge associated to each ordered pair of vertices (u, v), we call (u, v) an edge if there is an edge associated to it in the graph. In some computer networks, multiple communication links between two data centers may be present, as illustrated in Figure 5. Directed graphs that may have multiple directed edges from a vertex to a second (possibly the same) vertex are used to model such networks.We called such graphs directed multigraphs. When there are m directed edges, each associated to an ordered pair of vertices (u, v), we say that (u, v) is an edge of multiplicity m.

3 min read

Some Special Simple Graphs EXAMPLE 1 Complete Graphs A complete graph on n vertices, denoted by Kn, is a simple graph that contains exactly one edge between each pair of distinct vertices. The graphs Kn, for n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3. A simple graph for which there is at least one pair of distinct vertex not connected by an edge is called noncomplete.

4 min read

Introduction: A simple path in a graphGthat passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit. That is, the simple path x0, x1, . . . , xn−1, xn in the graph G = (V ,E) is a Hamilton path if V = {x0, x1, . . . , xn−1, xn} and xi = xj for 0 ≤ i < j ≤ n, and the simple circuit x0, x1, . . . , xn−1, xn, x0 (with n > 0) is a Hamilton circuit if x0, x1, . . . , xn−1, xn is a Hamilton path. This terminology comes from a game, called the Icosian puzzle, invented in 1857 by the Irish mathematician Sir William Rowan Hamilton. It consisted of a wooden dodecahedron a polyhedron with 12 regular pentagons as faces, as shown in Figure 8(a)], with a peg at each vertex of the dodecahedron, and string. The 20 vertices of the dodecahedron were labeled with different cities in the world. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the first city. The circuit traveled was marked off using the string and pegs.

6 min read

Some Applications of Special Types of Graphs: We conclude this section by introducing some additional graph models that involve the special types of graph we have discussed in this section. EXAMPLE 1 Local Area Networks The various computers in a building, such as minicomputers and personal computers, as well as peripheral devices such as printers and plotters, can be connected using a local area network. Some of these networks are based on a star topology, where all devices are connected to a central control device.A local area network can be represented using a complete bipartite graph K1,n, as shown in Figure 11(a). Messages are sent from device to device through the central control device.

4 min read

HUFFMAN CODING We now introduce an algorithm that takes as input the frequencies (which are the probabilities of occurrences) of symbols in a string and produces as output a prefix code that encodes the string using the fewest possible bits, among all possible binary prefix codes for these symbols. This algorithm, known as Huffman coding, was developed by David Huffman in a term paper he wrote in 1951 while a graduate student at MIT. (Note that this algorithm assumes that we already knowhowmany times each symbol occurs in the string, so we can compute the frequency of each symbol by dividing the number of times this symbol occurs by the length of the string.) Huffman coding is a fundamental algorithm in data compression, the subject devoted to reducing the number of bits required to represent information. Huffman coding is extensively used to compress bit strings representing text and it also plays an important role in compressing audio and image files. Algorithm 2 presents the Huffman coding algorithm. Given symbols and their frequencies, our goal is to construct a rooted binary tree where the symbols are the labels of the leaves. The algorithm begins with a forest of trees each consisting of one vertex, where each vertex has a symbol as its label and where the weight of this vertex equals the frequency of the symbol that is its label. At each step, we combine two trees having the least total weight into a single tree by introducing a new root and placing the tree with larger weight as its left subtree and the tree with smaller weight as its right subtree. Furthermore, we assign the sum of the weights of the two subtrees of this tree as the total weight of the tree. (Although procedures for breaking ties by choosing between trees with equal weights can be specified, we will not specify such procedures here.) The algorithm is finished when it has constructed a tree, that is, when the forest is reduced to a single tree. ALGORITHM 2 Huffman Coding. procedure Huffman(C: symbols ai with frequencies wi , i = 1, . . . , n) F := forest of n rooted trees, each consisting of the single vertex ai and assigned weight w_i while F is not a tree Replace the rooted trees T and T' of least weights from F with w(T ) ≥ w(T') with a tree having a new root that has T as its left subtree and T' as its right subtree. Label the new edge to T with 0 and the new edge to T' with 1. Assign w(T ) w(T') as the weight of the new tree. {the Huffman coding for the symbol ai is the concatenation of the labels of the edges in the unique path from the root to the vertex ai}

2 min read

ORDERED ROOTED TREES An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. Ordered rooted trees are drawn so that the children of each internal vertex are shown in order from left to right. Note that a representation of a rooted tree in the conventional way determines an ordering for its edges.We will use such orderings of edges in drawings without explicitly mentioning that we are considering a rooted tree to be ordered. In an ordered binary tree (usually called just a binary tree), if an internal vertex has two children, the first child is called the left child and the second child is called the right child. The tree rooted at the left child of a vertex is called the left subtree of this vertex, and the tree rooted at the right child of a vertex is called the right subtree of the vertex. The reader should note that for some applications every vertex of a binary tree, other than the root, is designated as a right or a left child of its parent. This is done even when some vertices have only one child. EXAMPLE 4 What are the left and right children of d in the binary tree T shown in Figure 8(a) (where the order is that implied by the drawing)? What are the left and right subtrees of c? Solution: The left child of d is f and the right child is g. We show the left and right subtrees of c in Figures 8(b) and 8(c), respectively.

4 min read

Adjacency Matrices: Carrying out graph algorithms using the representation of graphs by lists of edges, or by adjacency lists, can be cumbersome if there are many edges in the graph. To simplify computation, graphs can be represented using matrices. Two types of matrices commonly used to represent graphs will be presented here. One is based on the adjacency of vertices, and the other is based on incidence of vertices and edges. Suppose that G = (V ,E) is a simple graph where |V| = n. Suppose that the vertices of G are listed arbitrarily as v1, v2, . . . , vn. The adjacency matrix A (or AG) of G, with respect to this listing of the vertices, is the n x n zero–one matrix with 1 as its (i, j )th entry when vi and vj are adjacent, and 0 as its (i, j )th entry when they are not adjacent. In other words, if its adjacency matrix is A = [aij ], then

2 min read

Returning to eighteenth-century Königsberg, is it possible to start at some point in the town, travel across all the bridges, and end up at some other point in town? This question can be answered by determining whether there is an Euler path in the multigraph representing the bridges in Königsberg. Because there are four vertices of odd degree in this multigraph, there is no Euler path, so such a trip is impossible.

4 min read

Decision Trees Rooted trees can be used to model problems in which a series of decisions leads to a solution. For instance, a binary search tree can be used to locate items based on a series of comparisons, where each comparison tells us whether we have located the item, or whether we should go right or left in a subtree. A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these vertices for each possible outcome of the decision, is called a decision tree. The possible solutions of the problem correspond to the paths to the leaves of this rooted tree. Example 1 illustrates an application of decision trees. EXAMPLE 1 Suppose there are seven coins, all with the same weight, and a counterfeit coin that weighs less than the others. How many weighings are necessary using a balance scale to determine which of the eight coins is the counterfeit one? Give an algorithm for finding this counterfeit coin. Solution: There are three possibilities for each weighing on a balance scale. The two pans can have equal weight, the first pan can be heavier, or the second pan can be heavier. Consequently, the decision tree for the sequence of weighings is a 3-ary tree. There are at least eight leaves in the decision tree because there are eight possible outcomes (because each of the eight coins can be the counterfeit lighter coin), and each possible outcome must be represented by at least one leaf. The largest number of weighings needed to determine the counterfeit coin is the height of the decision tree. From Corollary 1 of Section 11.1 it follows that the height of the decision tree is at least log3 8 = 2. Hence, at least two weighings are needed. It is possible to determine the counterfeit coin using two weighings. The decision tree that illustrates how this is done is shown in Figure 3. THE COMPLEXITY OF COMPARISON-BASED SORTING ALGORITHMS Many different sorting algorithms have been developed. To decide whether a particular sorting algorithm is efficient, its complexity is determined. Using decision trees as models, a lower bound for the worst-case complexity of sorting algorithms that are based on binary comparisons can be found. We can use decision trees to model sorting algorithms and to determine an estimate for the worst-case complexity of these algorithms. Note that given n elements, there are n! possible orderings of these elements, because each of the n! permutations of these elements can be the correct order. The sorting algorithms studied in this book, and most commonly used sorting algorithms, are based on binary comparisons, that is, the comparison of two elements at a time. The result of each such comparison narrows down the set of possible orderings. Thus, a sorting algorithm based on binary comparisons can be represented by a binary decision tree in which each internal vertex represents a comparison of two elements. Each leaf represents one of the n! permutations of n elements.

3 min read

Assume that the inductive hypothesis holds for the kth iteration. Let v be the vertex added to S at the (k 1)st iteration, so v is a vertex not in S at the end of the kth iteration with the smallest label (in the case of ties, any vertex with smallest label may be used). From the inductive hypothesis we see that the vertices in S before the (k 1)st iteration are labeled with the length of a shortest path from a. Also, v must be labeled with the length of a shortest path to it from a. If this were not the case, at the end of the kth iteration there would be a path of length less than Lk(v) containing a vertex not in S [because Lk(v) is the length of a shortest path from a to v containing only vertices in S after the kth iteration]. Let u be the first vertex not in S in such a path. There is a path with length less than Lk(v) from a to u containing only vertices of S. This contradicts the choice of v. Hence, (i) holds at the end of the (k 1)st iteration.

3 min read

DEFINITION A tree is a connected undirected graph with no simple circuits. Because a tree cannot have a simple circuit, a tree cannot contain multiple edges or loops. Therefore any tree must be a simple graph. EXAMPLE 1 Which of the graphs shown in Figure 2 are trees? Solution: G1 and G2 are trees, because both are connected graphs with no simple circuits. G3 is not a tree because e, b, a, d, e is a simple circuit in this graph. Finally, G4 is not a tree because it is not connected. Any connected graph that contains no simple circuits is a tree. What about graphs containing no simple circuits that are not necessarily connected? These graphs are called forests and have the property that each of their connected components is a tree. Figure 3 displays a forest. Trees are often defined as undirected graphs with the property that there is a unique simple path between every pair of vertices. Theorem 1 shows that this alternative definition is equivalent to our definition.

4 min read

Introduction: A traveling salesperson wants to visit each of n cities exactly once and return to his starting point. For example, suppose that the salesperson wants to visit Detroit, Toledo, Saginaw, Grand Rapids, and Kalamazoo (see Figure 5). In which order should he visit these cities to travel the minimum total distance? To solve this problem we can assume the salesperson starts in Detroit (because this must be part of the circuit) and examine all possible ways for him to visit the other four cities and then return to Detroit (starting elsewhere will produce the same circuits). There are a total of 24 such circuits, but because we travel the same distance when we travel a circuit in reverse order, we need only consider 12 different circuits to find the minimum total distance he must travel.We list these 12 different circuits and the total distance traveled for each circuit. As can be seen from the list, the minimum total distance of 458 miles is traveled using the circuit Detroit–Toledo–Kalamazoo–Grand Rapids–Saginaw–Detroit (or its reverse). We just described an instance of the traveling salesperson problem. The traveling salesperson problem asks for the circuit of minimum total weight in a weighted, complete, undirected graph that visits each vertex exactly once and returns to its starting point. This is equivalent to asking for a Hamilton circuit with minimum total weight in the complete graph, because each vertex is visited exactly once in the circuit.

2 min read

Game Trees: Trees can be used to analyze certain types of games such as tic-tac-toe, nim, checkers, and chess. In each of these games, two players take turns making moves. Each player knows the moves made by the other player and no element of chance enters into the game.We model such games using game trees; the vertices of these trees represent the positions that a game can be in as it progresses; the edges represent legal moves between these positions. Because game trees are usually large, we simplify game trees by representing all symmetric positions of a game by the same vertex. However, the same position of a game may be represented by different vertices FIGURE 6 Huffman Coding of Symbols in Example 4. if different sequences of moves lead to this position. The root represents the starting position. The usual convention is to represent vertices at even levels by boxes and vertices at odd levels by circles. When the game is in a position represented by a vertex at an even level, it is the first player’s move; when the game is in a position represented by a vertex at an odd level, it is the second player’s move. Game trees may be infinite when the games they represent never end, such as games that can enter infinite loops, but for most games there are rules that lead to finite game trees.

4 min read

HALL’S MARRIAGE THEOREM The bipartite graph G = (V ,E) with bipartition (V1, V2) has a complete matching from V1 to V2 if and only if |N(A)| ≥ |A| for all subsets A of V1. Proof:We first prove the only if part of the theorem. To do so, suppose that there is a complete matching M from V1 to V2. Then, if A ⊆ V1, for every vertex v ∈ A, there is an edge in M connecting v to a vertex in V2. Consequently, there are at least as many vertices in V2 that are neighbors of vertices in V1 as there are vertices in V1. It follows that |N(A)| ≥ |A|. To prove the if part of the theorem, the more difficult part, we need to show that if |N(A)| ≥ |A| for all A ⊆ V1, then there is a complete matching M from V1 to V2. We will use strong induction on |V1| to prove this. Basis step: If |V1| = 1, then V1 contains a single vertex v0. Because |N({v0})| ≥ |{v0}| = 1, there is at least one edge connecting v0 and a vertex w0 ∈ V2. Any such edge forms a complete matching from V1 to V2.

3 min read

Introduction: Many problems can be modeled using graphs with weights assigned to their edges. As an illustration, consider how an airline system can be modeled. We set up the basic graph model by representing cities by vertices and flights by edges. Problems involving distances can be modeled by assigning distances between cities to the edges. Problems involving flight time can be modeled by assigning flight times to edges. Problems involving fares can be modeled by assigning fares to the edges. Figure 1 displays three different assignments of weights to the edges of a graph representing distances, flight times, and fares, respectively.

4 min read

GRAPH COLORING Coloring problem Suppose that you are given a graph G with n vertices and are asked to paint its vertices such that no two adjacent vertices have the same color. What is the minimum number of colors that you would require. This constitutes a coloring problem. Partitioning problem Having painted the vertices, you can group them into different sets—one set consisting of all red vertices, another of blue, and so forth. This is a partitioning problem. For example, finding a spanning tree in a connected graph is equivalent to partitioning the edges into two sets—one set consisting of the edges included in the spanning tree, and the other consisting of the remaining edges. Identification of a Hamiltonian circuit (if it exists) is another partitioning of set of edges in a given graph.

4 min read

Prefix Codes: Consider the problem of using bit strings to encode the letters of the English alphabet (where no distinction is made between lowercase and uppercase letters). We can represent each letter with a bit string of length five, because there are only 26 letters and there are 32 bit strings of length five. The total number of bits used to encode data is five times the number of characters in the text when each character is encoded with five bits. Is it possible to find a coding scheme of these letters such that, when data are coded, fewer bits are used? We can save memory and reduce transmittal time if this can be done. Consider using bit strings of different lengths to encode letters. Letters that occur more frequently should be encoded using short bit strings, and longer bit strings should be used to encode rarely occurring letters. When letters are encoded using varying numbers of bits, some method must be used to determine where the bits for each character start and end. For instance, if e were encoded with 0, a with 1, and t with 01, then the bit string 0101 could correspond to eat, tea, eaea, or tt.