Introductory Discrete Mathematics (Dover Books on Computer Science) PDF

Introductory Discrete Mathematics Introductory Discrete Mathematics V. K. Balakrishnan DOVER PGBUCATIONS, INC. New York Copyright Copyright © 1991 by V. K. Balakrishnan. All rights reserved. Bibliographical Note This Dover edition, first published in 1996, is an unabridged, corrected republication of the work first published by Prentice Hall, Englewood Cliffs, N.J., 1991. Library of Congress Cataloging-in-Publication Data Balakrishnan, V.K., date. Introductory discrete mathematics / V. K. Balakrishnan. p. cm. “An unabridged, corrected republication of the work first published by Prentice Hall, Englewood Cliffs, N.J., 1991”—T.p. verso. Includes bibliographical references (p. - ) and index. eISBN-13: 978-0-486-14038-4 1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.2.B357 1996 511—dc20 95-52384 CIP Manufactured in the United States by Courier Corporation 69115205 www.doverpublications.com To Geeta Contents Preface Set Theory and Logic 0.1 Introduction to Set Theory 0.2 Functions and Relations 0.3 Inductive Proofs and Recursive Definitions 0.4 The Language of Logic 0.5 Notes and References 0.6 Exercises Combinatorics 1.1 Two Basic Counting Rules 1.2 Permutations 1.3 Combinations 1.4 More on Permutations and Combinations 1.5 The Pigeonhole Principle 1.6 The Inclusion-Exclusion Principle 1.7 Summary of Results in Combinatorics 1.8 Notes and References 1.9 Exercises Generating Functions 2.1 Introduction 2.2 Ordinary Generating Functions 2.3 Exponential Generating Functions 2.4 Notes and References 2.5 Exercises Recurrence Relations 3.1 Introduction 3.2 Homogeneous Recurrence Relations 3.3 Inhomogeneous Recurrence Relations 3.4 Recurrence Relations and Generating Functions 3.5 Analysis of Algorithms 3.6 Notes and References 3.7 Exercises Graphs and Digraphs 4.1 Introduction 4.2 Adjacency Matrices and Incidence Matrices 4.3 Joining in Graphs 4.4 Reaching in Digraphs 4.5 Testing Connectedness 4.6 Strong Orientation of Graphs 4.7 Notes and References 4.8 Exercises More on Graphs and Digraphs 5.1 Eulerian Paths and Eulerian Circuits 5.2 Coding and de Bruijn Digraphs 5.3 Hamiltonian Paths and Hamiltonian Cycles 5.4 Applications of Hamiltonian Cycles 5.5 Vertex Coloring and Planarity of Graphs 5.6 Notes and References 5.7 Exercises Trees and Their Applications 6.1 Definitions and Properties 6.2 Spanning Trees 6.3 Binary Trees 6.4 Notes and References 6.5 Exercises Spanning Tree Problems 7.1 More on Spanning Trees 7.2 Kruskal’s Greedy Algorithm 7.3 Prim’s Greedy Algorithm 7.4 Comparison of the Two Algorithms 7.5 Notes and References 7.6 Exercises Shortest Path Problems 8.1 Introduction 8.2 Dijkstra’s Algorithm 8.3 Floyd-Warshall Algorithm 8.4 Comparison of the Two Algorithms 8.5 Notes and References 8.6 Exercises What Is NP-Completeness? A.1 Problems and Their Instances A.2 The Size of an Instance A.3 Algorithm to Solve a Problem A.4 Complexity of an Algorithm A.5 The “Big Oh” or the O(·) Notation A.6 Easy Problems and Difficult Problems A.7 The Class P and the Class NP A.8 Polynomial Transformations and NP-Completeness A.9 Coping with Hard Problems Bibliography Answers to Selected Exercises Index Preface Introductory Discrete Mathematics is a concise text for a discrete mathematics course at an introductory level for undergraduate students in computer science and mathematics. The essential components of any beginning level discrete mathematics curriculum are combinatorics, graph theory with applications to some standard network optimization problems, and algorithms to solve these problems. In this book the stress is on these core components. Both the Association for Computing Machinery and the Committee for the Undergraduate Program in Mathematics recognize the vital role of an undergraduate course in discrete methods that introduces the student to combinatorial mathematics and to algebraic and logical structures focusing on the interplay between computer science and mathematics. The material in Chapter 0 serves as an introduction to the fundamental operations involving sets and the principle of mathematical induction. For those students familiar with the topics discussed here, this is essentially a chapter for review. The standard topics in combinatorics in any course on discrete mathematics are covered in Chapters 1, 2, and 3. These topics include basic counting principles, permutations, combinations, the inclusion-exclusion principle, generating functions, recurrence relations, and an introduction to the analysis of algorithms. The role of applications is emphasized wherever possible. There are more than 200 exercises at the end of these chapters. Each counting problem requires its own special insight, and it is advantageous for the student to work out several of these problems. In the next three chapters is a survey of graphs and digraphs. We begin with treating graphs and digraphs as models of real-world phenomena by giving several examples. The connectedness properties of graphs and digraphs are studied. Basic results and applications of graph coloring and of Eulerian and Hamiltonian graphs are presented with a stress on applications to coding and other related problems. Two important problems in network optimization are the minimal spanning tree problem and the shortest distance problem; they are covered in the last two chapters. The approach to compute the complexity of algorithms in these chapters is more or less informal. A very brief nontechnical exposition of the theory of computational complexity and NP-completeness is outlined in the appendix. It is possible to cover the topics presented in this book as a one-semester course by skipping some sections if necessary. Of course it is for the instructor to decide which sections she or he may skip. My chief acknowledgment is to the students who have studied discrete mathematics with me at the University of Maine during the past decade. They taught me how to teach. Their contributions and encouragement are implicit on every page. In particular, I would like to mention the names of Rajesh and Thananchayan. My scientific indebtedness in this project encompasses many sources including the articles and books listed in the bibliography. If there are errors or misleading results, the blame of course falls entirely on my shoulders. Finally, it goes without saying that I owe a great deal to the interest and encouragement my family has shown at every stage of this work. V. K. Balakrishnan Set Theory and Logic 0.1 INTRODUCTION TO SET THEORY The concept of a set plays a very significant role in all branches of modern mathematics. In recent years set theory has become an important area of investigation because of the way in which it permeates so much of contemporary mathematical thought. A genuine understanding of any branch of modern mathematics requires a knowledge of the theory of sets for it is the common foundation of the diverse areas of mathematics. Sets are used to group distinct objects together. It is necessary that the objects which belong to a set are well-defined in the sense that there should be no ambiguity in deciding whether a particular object belongs to a set or not. Thus, given an object, either it belongs to a given set or it does not belong to it. For example, the first five letters of the English alphabet constitute a set which may be represented symbolically as the set {a, b, c, d, e}. An arbitrary object belongs to this set if and only if it is one of these five letters. These five distinct objects can appear in any order in this representation. In other words, this set can also be represented by {d, b, a, e, c}. The objects that belong to a set need not possess a common property. Thus the number 4, the letter x, and the word “book” can constitute a set S which may be represented as S = {x, book, 4}. A particular day may be cold for one person and not cold for another, so the “collection of cold days in a month” is not a clearly defined set. Similarly, “the collection of large numbers” and “the collection of tall men” are also not sets. The term object has been used here without specifying exactly what an object is. From a mathematical point of view, set is a technical term that takes its meaning from the properties we assume that sets possess. This informal description of a set, based on the intuitive notion of an object, was first given by the German mathematician Georg Cantor (1845–1918) toward the end of the nineteenth century and the theory of sets based on his version is known as naive set theory. In Cantor’s own words, “a set is bringing together into a whole of definite well-defined objects of our perception and these objects are the elements of the set.” The sets considered in this book can all be viewed in this framework of Cantor’s theory. Thus a set is a collection of distinct objects. The objects in a set are called the elements or members of the set. If x is an element of a set A, we say that x belongs to A, and this is expressed symbolically as x A. The notation denotes that y is not an element of the set A. Finite and Infinite Sets A set is finite if the number of elements in it is finite. Otherwise, it is an infinite set. The set of positive integers less than 100 is a finite set, whereas the set of all positive integers is an infinite set. If X is a finite set, the cardinality of X is the number of elements that belong to X, and this nonnegative integer is denoted by N(X). A set of cardinality 1 is called a singleton set. If a set is finite and if its cardinality is not too large, we can describe it by enumerating all its elements. For example, the representation S = {a, e, i, o, u} describes the set of all vowels of the English alphabet. If the cardinality is too large, this enumerative method is not very convenient. In some cases, if there is no ambiguity we make this enumerative description more concise. For example, the set D of positive integers between 25 and 123 can be represented as D = {25, 26, 27, · · · , 121, 122, 123}. A better way of representing D is by stating the property for its membership. An object n is an element of this set D if and only if n is a positive integer that is at least 25 and at most 123. In other words, we write D = {n : n is a positive integer, 24 < n < 124} The infinite set N of all natural numbers can be represented unambiguously as N = {1, 2, 3,...} or as N = {n : n is a natural number} by stating its membership criterion. The notation of representing a set by stating the criteria of its membership as described above is called the set-builder notation. Subsets of a Set and the Empty Set A set P is a subset of a set Q if every element of P is an element of Q. We use the notation P ⊂ Q to denote that P is a subset of Q. A subset of a subset is no doubt a subset. When P is a subset of Q, we may say that Q contains P and that P is contained in Q. By our definition every set is a subset of itself. The set P is a proper subset of Q if (1) P is a subset of Q and (2) there is at least one element of Q that is not an element of P. The set of positive integers is a proper subset of the set of all real numbers. If A is a subset of B, the relative complement of A in B is the set of elements in B that are not elements of A. The relative complement of A in B is denoted by B – A and it can be described by its membership criterion as Two sets are disjoint if they have no elements in common. On the other hand, two sets are equal if they have the same elements. We write X = Y when the sets X and Y are equal. Obviously, two sets are equal if and only if each is a subset of the other. For instance, if X = {r : r is a root of the x 2 – 5x + 6 = 0} and Y = {2, 3}, then X = Y. A set is empty if it has no elements. A fact emerges that some people find surprising: there is only one empty set. (Suppose that E and F are two empty sets. If they are not the same, they are not equal. So one of them should have at least one element that does not belong to the other. So one of the two sets is not empty. This contradicts the assumption that both E and F are empty.) The unique empty set (or null set) is denoted by ϕ. The fact that the empty set is a subset of any set is established by “vacuous reasoning”: If it were not a subset of a given set S, there should be at least one element in the empty set that is not in S. In particular, there should be at least one element in the empty set that is a contradiction. Of course, a set is empty if and only if its cardinality is zero. In some cases we will be considering sets that are all subsets of a set U which is called the universal set. For example, if the sets under consideration are A, B, and C, where A = {3, 8, 6, 7, x}, B = {8, 4, y, t, 5}, and C = {3, 4, x, t, 9}, then any set containing the set D = {3, 8, 6, 7, x, 4, y, t, 5, 9} can be considered as a universal set as far as A, B, C, and D are concerned. Once the universal set U is fixed, the relative complement of a subset A in U is called the absolute complement of A and is denoted by Ac. Thus if the universe is the set of all nonnegative integers and E is the set of all even numbers, then Ec is the set of all odd numbers. Observe that the absolute complement of the absolute complement of any set A is the set A itself. The Power Set of a Set A set can have other sets as its elements. For instance, the set S consisting of the letter x, the set {a, b} and the number 4 is represented as S = {x, {a, b}, 4}. A set of subsets is also known as a class or family of sets. The class of all subsets of a given set X is called the power set of X and is denoted by P(X). For example, if X = {1, 2}, the elements of P(X) are the empty set, the singleton set {1}, the singleton set {2}, and the set X. Thus P(X) = {ϕ, {1}, {2}, {1, 2}}. Cartesian Products of Sets The ordered n-tuple (a1, a2, a3,... , an ) is a collection of the n objects a1, a2,... , an in which a1 is the first element, a2 is the second element,... , and an is the nth element. In an ordered n-tuple, the elements need not be distinct. A set with n elements is thus an unordered n-tuple of n distinct elements, since in a set the order in which the elements are considered is irrelevant. An ordered 2-tuple is called an ordered pair. Two ordered n-tuples (a1, a2,... , an ) and (b1, b2,... , bn ) are said to be equal if ai = bi for i = 1, 2,... , n. The set of all ordered pairs (a, b), where a is an element of a set A and b is an element of a set B, is called the cartesian product of A and B and is denoted by A × B. In other words, A × B = {(a, b) : a A and b B} For example, if A = {1, 2} and B = {1, 3}, then the cartesian product A × B is the set {(1, 1), (1, 3), (2, 1), (2, 3)}. More generally, the cartesian product of the sets A1, A2,... , An denoted by A1 × A2 × · · · × An is the set of all ordered n-tuples of the form (a1, a2,... , an ), where ai is any element of Ai (i = 1, 2,... , n). Intersections and Unions of Sets There are two important constructions that can be applied to subsets of a set to yield new subsets. Suppose that A and B are two subsets of a set X. The set consisting of all elements common to both A and B is called the intersection of A and B and is denoted by A ∩ B. Obviously, the intersection of a set and the empty set is the empty set and the intersection of any set A and A is A. Also, the intersection of a set and its absolute complement is empty since no element can be simultaneously in A and not in A. Moreover, it follows from the definition that set intersection has the commutative property: The intersection of A and B is equal to the intersection of B and A. The set consisting of all elements that belong to either A or to B or to both A and B is called the union of A and B and is denoted by A ∪ B. The union of a set A and the empty set is the set A and the union of A and A is also A. Set union also is commutative: A ∪ B = B ∪ A. More generally, the intersection of a class of sets is the set of elements (if any) that belong to every set of the class. The union of a class of sets is the set of those elements that belong to at least one set in the class. It is an immediate consequence of the definition that both set intersection and set union possess the associative property: (1) A ∩ (B ∩ C) = (A ∩ B) ∩ C and (2) A ∪ (B ∪ C) = (A ∪ B) ∪ C. So the former can be written as A ∩ B ∩ C and the latter as A ∪ B ∪ C unambiguously. Two sets are disjoint if and only if their intersection is empty. A class of sets is pairwise disjoint if the intersection of any two sets in the class is empty. A class C(X) of subsets of a set X is called a partition of X if (1) C(X) is pairwise disjoint, and (2) the union of the sets in C(X) is the set X. For instance, the class {{2, 4}, (1, 3, 5}, {6}} is a partition of the set {1, 2, 3, 4, 5, 6}. Venn Diagrams of Sets A very useful and simple device to represent sets graphically for illustrating relationship between them is the Venn diagram, named after the English logician John Venn (1834–1923). In a Venn diagram, the universal set U that contains all the objects under consideration is usually represented by a rectangle, and inside this rectangle subsets of the universal set are represented by circles, rectangles, or some other geometrical figures. In the Venn diagram shown in Figure 0.1.1, we have three sets A, B, and C which are subsets of the universal set U. The drawing of the ellipse that represents the set A inside the ellipse that represents the set B indicates that A is a subset of B. The fact that A and C are disjoint is made clear by representing them by two nonintersecting ellipses. The fact that the intersection of B and C is nonempty is made obvious by showing that the two ellipses which represent these two sets overlap each other. The region in the rectangle (which represents the universal set) that is outside the ellipses that represent the three sets is the absolute complement of the union of these three sets. FIGURE 0.1.1 Distributive Laws and De Morgan’s Laws We conclude this section on sets with the following two theorems related to set operations involving intersections, unions, and taking absolute complements. These theorems can easily be established by drawing Venn diagrams. However, it is instructive to prove them without the aid of Venn diagrams, for in many cases it may not be possible to represent the sets under consideration by such diagrams, as we will see later in the book. THEOREM 0.1.1 (Distributive Laws) (a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). (b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Proof: (a) One way of showing that two sets are equal is by establishing that each is contained in the other. Let t be an element of A ∩ (B ∪ C). Then t is an element of A and t is either an element of B or an element of C. In either case, t is an element of A ∩ B or A ∩ C. In other words, A ∩ (B ∪ C) is a subset of (A ∩ B) ∪ (A ∩ C). Next, suppose that t is an element of (A ∩ B) ∪ (A ∩ C). This implies that t is either in A ∩ B or in A ∩ C. So t is necessarily in A and it is in at least one of the two sets B or C. Thus t is in A and also in either B or in C. In other words, t belongs to the intersection of A and to B ∪ C. Thus (A ∩ B) ∪ (A ∩ C) is a subset of A ∩ (B ∪ C). (b) This is left as an exercise. THEOREM 0.1.2 (De Morgan’s Laws) (a) (A ∩ B)c = Ac ∪ Bc. (b) (A ∪ B)c = Ac ∩ Bc. Proof: (a) Let t be an element of (A ∪ B)c. Then t belongs to neither A nor B. So t is necessarily in both Ac and Bc. Thus (A ∪ B)c is a subset of the intersection of Ac and Bc. On the other hand, if t is in the intersection of Ac and Bc, it is neither in A nor in B. This implies that t is not in the union of A and B. Hence the intersection of Ac and Bc is contained in the complement of A ∪ B. (b) This is left as an exercise. 0.2 FUNCTIONS AND RELATIONS In this section a brief review of the basic ideas involving functions and relations is presented. The concept of a function is pivotal in mathematics. The Domain and the Range of a Function Let X and Y be two nonempty sets. A function f from X into Y, denoted by f: X → Y, is a rule that assigns to every element in X a unique element in Y. The set X is the domain of the function and the set Y is its codomain. If y is the unique element in Y assigned by the function f to the element x, we say that y is the image of x and x is a preimage of y and we write y = f(x). The set f(A) of all images of the elements of a subset A of X is called the image of the set A. The set f(X) is called the range of the function. The range of a function is a subset of its codomain. If y is an element in the range of f, the set of all the preimages of y is denoted by f –1 (y). If A is a subset of the range f(X), the inverse image of the set A is the set {x : x is in X and f(x) is in A}, which is denoted by f –1(A). If f is a function from X to Y, it is customary to say that f maps the set X into Y. Example 0.2.1 Let R be the set of all real numbers. (a) Let f: R → R be the function that assigns the real number x + 1 to each real number x. In other words, f(x) = x + 1. Here the domain, codomain, and range of f is R. (b) Let f: R → R be the function defined by f(x) = x 2. So every real number is assigned to its square. Here the domain and codomain of f are R and its range is the set of all nonnegative numbers. Example 0.2.2 Let A = {a, b, c} and B = {1, 2, 3, 4}. Then the rule f defined by f(a) = 1, f(b) = 1, f(c) = 4, and f(d) = 2 is a function f from A to B. The range of f is {1, 2, 4}, which is a proper subset of its codomain B. Surjections, Injections, and Bijections A function f: X → Y is called a surjection if f(X) = Y and we say that f is function from X onto Y. A function f: X → Y is called an injection (or a one-to-one mapping) if two different elements in X have two different images in Y. A function f: X → Y is a bijection if it is both a surjection and an injection. The bijection from a set X onto itself that maps every element in the set into itself is called the identity mapping ix on X. Two sets are equivalent if there is a bijection from one to the other. It is evident that two finite sets are equivalent if and only if they both have the same cardinality. Example 0.2.3 (a) Let X = {a, b, c}, Y = {p, q}, and f: X → Y, where f(a) = p, f(b) = q, and f(c) = p. Then f is a surjection and f maps X onto Y. Here f is not an injection. (b) If X = {a, b, c}, Y = {p, q, r, s} and if g(a) = p, g(b) = q, g(c) = r, then g is an injection but not a surjection. The range g(X) = {p, q, r} is a proper subset of the codomain Y. (c) If X = {a, b, c}, Y = {p, q, r} and if h(a) = p, h(b) = q, and h(c) = r, then h is a bijection. (d) If R is the set of real numbers and f: R → R the function defined by f(x) = x 2, then f is neither a surjection, because no negative number has a preimage, nor an injection, because the image of x and the image of –x are both equal. The Inverse of a Function Let f: X → Y be a bijection. The inverse function of f is the bijection f –1: Y → X defined as follows: For each y in Y, we find that unique element x in X such that f(x) = y. Then we define x = f –1(y). A function f: X → Y is said to be invertible whenever its inverse exists. Example 0.2.4 If X = {1, 2}, Y = {p, q}, f(1) = p, and f(2) = q, then f is a bijection from X onto Y and its inverse f –1 is the bijection from Y onto X that maps p into 1 and q into 2. A function f whose domain X and codomain Y are subsets of the set R of real numbers is strictly increasing if f(x) < f(y) whenever x < y and strictly decreasing if f(x) > f(y) whenever x < y. It follows from the definition that both strictly increasing functions and strictly decreasing functions are injections. Compositions of Functions Let g : X → Y and f: Y → Z. The composition of f and g, defined by f ○ g, is a function from X to Z defined by (f ○ g)(x) = f(g(x)). In other words, the function f ○ g assigns to an element x in X that unique element assigned by f to g(x). Example 0.2.5 (a) Let X = {a, b, c}, Y = {p, q, r, s}, and Z = {1, 2, 3}. Let g(a) = p, g(b) = q, and g(c) = r, so that g(X) = {p, q, r}. Then if f: g(X) → Z is defined by f(p) = 1, f(q) = 2, and f(r) = 3, we have (b) Let f and g be functions from the set of integers to the set of integers. If f(x) = 4x + 3 and g(x) = 2x + 5, then (f ○ g)(x) = f(g(x)) = f(2x + 5) = 4(2x + 5) + 3 = 8x + 23 (g ○ f)(x) = g(f(x)) = g(4x + 3) = 2(4x + 3) + 5 = 8x + 11 If f is a bijection from X onto Y, its inverse is a bijection from Y to X. If y = f(x), then f –1(y) = x. Thus f –1(f(x) = f –1(y) = x and f(f –1(y)) = f(x) = y. In other words, the composition of a bijection from X onto Y and its inverse is the identity mapping from Y onto itself. Sequences, Strings, and Languages A sequence is a function whose domain is a set of consecutive integers. If the domain X is a finite set of n integers, we may take X = {1, 2, 3,... , n} or {0, 1, 2,... , n – 1}. Otherwise, we may take X as the set of natural numbers or as the set of nonnegative integers. If f: X → Y is a sequence, the image f(i) of the integer i is sometimes written as f i and is called the ith term of the sequence. Notice that in representing a sequence s, the order in which the images under s appear is important. This is not so in the case of a function. For example, if f is the function from X = {1, 2, 3} to Y = {p, q}, where f(1) = f(2) = p and f(3) = q, the collection of the images of the three elements of X under f can be represented as p, p, q in any order. But the sequence f is represented as (f(1)f(2)f(3)) or as (ppq). A sequence whose domain is finite consisting of n consecutive integers and whose codomain is Y defines a string of length n in Y or word of length n in Y. In fact, any such sequence is an n-tuple. Example 0.2.6 (a) Let X = {1, 2, 3,...} and R the set of real numbers. Consider the sequence f: X → R defined by f(n) = 1/n. Then the nth term of the sequence denoted by f n is the image f(n) of the element n in X. This sequence is also denoted by {1/n : n = 1, 2, 3,...}. (b) Let X = {1, 2, 3, 4, 5} and Y = {a, b, c, d} and consider the sequence f: X → Y defined by f(1) = a, f(2) = b, f(3) = a, f(4) = c, and f(5) = b. Then this sequence is the string abacb of length 5 in Y which is also the 5-tuple (abacb). Any mapping f from A × A into A is called a binary operator on A. For instance, if R is the set of real numbers, the mapping f: R × R → R defined by f(a, b) = a + b (which is, in fact, the addition operator) is an example of a binary operator on R. If S is any nonempty set, we denote by Sn the set of all strings of length n in S and S* the set of all strings (including the null string with no elements). Any subset of S* is called a language over the alphabet S. The union and intersection of two languages over an alphabet are also languages over the same alphabet. If u = (u1u2u3 · · · um) and v = (v 1v 2 · · · v n ) are two strings of lengths m and n, respectively in S* then the concatenation of u and v is the string uv in S* of length m + n defined as uv = (u1u2u3 · · · umv 1v 2 · · · v n ). The mapping c: S* × S* → S* defined by c(u, v) = uv where uv is the concatenation of u and v is a binary operator on S*. Relations We conclude this section with a brief comment on the concept of a “relation,” which is more general than that of a function. If A and B are two sets, any subset of A × B is called a relation from A to B. For example, if A = {a, b, c} and B = {1, 2, 3, 4}, then R = {(a, 2), (a, 3), (b, 4), (c, 3)} is a relation from A to B. By definition, in each ordered pair in a relation from A to B, the first element is an element in A and the second element is an element in B. A function from A to B therefore defines a special kind of relation R from A to B such that whenever (a, b) and (a, b′) are in the relation R, then b = b′. In other words, f: A → B defines the cartesian product {(x, f(x)) : x is in A}, which is a subset of A × B. A relation R from a finite set A with m elements to a finite set with n elements can be represented pictorially by a bipartite graph G with m vertices on the left side (corresponding to the m elements of A) and n vertices on the right side (corresponding to the n elements of B) as in Figure 0.2.1. If (a, p) is an element in the relation R, an arrow is drawn from the vertex a on the left side to the vertex p on the right side. For example, the graph in Figure 0.2.1 represents the relation R = {(a, p), (b, p), (c, r)} from the set A = {a, b, c} to the set B = {p, q, r}. A relation from a set A to itself is called a relation on A. An informative and useful way to represent a relation R on a finite set A with n elements is by drawing a directed graph with n vertices representing the n elements of the set and drawing an arrow from vertex u to vertex v if and only if the ordered pair (u, v) is in the relation. If (u, u) is in the relation, a loop from u to u is drawn. For example, if R = {(a, a), (a, b), (b, c), (c, b)} is a relation on the set A = {a, b, c}, this relation R can be represented by the directed graph shown in Figure 0.2.2. FIGURE 0.2.1 FIGURE 0.2.2 A relation R on A is reflexive if (a, a) is an element of R for every a in A, it is symmetric if (a, b) is in R whenever (b, a) is in R and it is transitive if (a, c) is in R whenever (a, b) and (b, c) are in R. A relation R on a set is antisymmetric if whenever a and b are distinct, then (a, b) is in the relation R only when (b, a) is not in the relation R. Finally, the relation R is said to have the comparison property if either (a, b) or (b, a) is in R for all a and b in A. Suppose that R is a relation on a finite set A and let G be the directed graph that represents this relation. Then R is reflexive if and only if there is a loop at every vertex of G and R is symmetric if and only if whenever there is an arrow from a to b, there is an arrow from b to a. Furthermore, R is transitive if and only if whenever there is an arrow from a to b and an arrow from b to c there is an arrow from a to c. Example 0.2.7 Let A = {a, b, c} and let R be a relation on A. (a) R = {(a, b), (b, a), (a, a), (b, b), (b, c), (c, c)} is reflexive because (u, u) is in R for all u in A. Here (a, a), (b, b), and (c, c) are in R. These three elements will represent loops at the three vertices of the corresponding digraph. (b) R = {(a, b), (b, a), (c, c)} is symmetric because whenever (u, v) is in R for any u and any v in A, then (v, u) also is in R. Here both (a, b) and (b, a) as well as (c, c) are in R. In the digraph that represents this relation there will be arrows from a and b and from b to a. There will be a loop at the vertex c. (c) R = {(a, b), (b, c), (a, c), (b, b)} is transitive. (d) R = {(a, c), (b, b), (a, b), (a, a)} is antisymmetric. (e) If R = {(a, c), (b, b), (c, c), (a, b), (c, b)}, then R has the comparison property. Equivalence Relations A relation S on a set is called an equivalence relation on A if S is reflexive, symmetric, and transitive. For example, if S = {(a, b) : a, b are real, a = b}, then S is obviously an equivalence relation on the set of real numbers. Example 0.2.8 (a) Let A = {a, b, c, d, e} and C(A) be a partition of A defined by the class {{a, b}, {c, d, e}}. Let R be the set of ordered pairs (x, y) in A × A such that whenever x is in one of the sets in the partition, then y is also in the same set. Thus in this case R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, b), (b, a), (c, d), (d, c), (c, e), (e, c), (d, d), (d, e)}. It is easily verified that R is an equivalence relation. Every partition of a set defines a unique equivalence relation on it. (b) Conversely, it can easily be established that every equivalence relation on a set defines a partition on the set. If the ordered pair (a, b) belongs to an equivalence relation on a set A, we take both a and b belong to the same subset of A. The class of subsets thus formed constitutes a partition of X. For instance the equivalence relation R = {(p, p), (q, q), (p, q), (q, p), (r, r)} defines the partition {{p, q}, {r}} of the set {p, q, r}. Equivalence Sets and the Equivalence Class Let R be an equivalence relation on a set A and let x be any element of A. The equivalence set [x] of the element x is the set {y : (y, x) R}. Observe that if [u] and [v] are two distinct equivalent sets, their intersection is empty. For if x is in both [u] and in [v], then because of transitivity (u, v) is in the relation R that implies [u] = [v]. The class of distinct equivalent sets of the elements in X is called the equivalence class of the relation. An equivalence class of a set is a partition of a set, and vice versa. Thus there is no real distinction between partitions of a set and equivalence classes in the set. In practice, it is almost invariably the case that we use equivalence relations to obtain partitions because it is usually easy to define an equivalence relation on a set. Partial Orders and Linear Orders A relation R on A is a partial order if it is reflexive, antisymmetric, and transitive. A partial order R that has the comparison property is called a total (or linear) order. A nonempty set A together with a partial order relation P defined on it is called a partially ordered set (PO set) and is denoted by (A, P). A partially ordered set (A, P) is called a totally (linearly) ordered set or a chain if P has the comparison property. Example 0.2.9 (a) Let A be nonempty set and P(A) its power set. Let R be a relation on P(A) × P(A) defined by the “set- inclusion” property; that is, if E and F are subsets of A, then (E, F) is in the relation R if E is subset of F. Then R is a partial order on P(A) and (P(A), R) is a partially ordered set. But it is not a linearly ordered set for an arbitrary subset of A need not contain another arbitrary subset of A. (b) If x and y are two real numbers, we say that (x, y) is an element in the relation S on the set R of real numbers whenever x is less than or equal to y. Then the relation S is a linear order on R. Example 0.2.10 Let X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and S be the relation on X defined as S = {(m, n) : m divides n}. Then S is a partial order on S. The set A = {2, 4, 8} is a chain in X, whereas the set B = {2, 5, 10} is not a chain since the elements 2 and 5 are not comparable. Hasse Diagrams of Partially Ordered Sets Consider the directed graph G that represents a partial order R on a finite set A. Since R is reflexive, there is a loop at each vertex of the graph. Since R is transitive, there is an arc from the vertex u to the vertex v whenever there is an arc from u to w and an arc from w to v. So we can have a simplified pictorial representation of the partial order if we ignore the loops and delete all arrows that are present due to transitivity. Furthermore, if the graphical representation is so oriented that all arrows point in one direction (upward, downward, left to right, or right to left), we can ignore the direction of the arrows as well. The resulting diagram is called a Hasse diagram of the partially ordered set. Example 0.2.11 Let X = {1, 2, 3, 4, 5} and S = {(1, 1), (1, 2), (1, 3), (1,4), (1, 5), (2, 2), (2, 3), (2, 5), (3, 3), (3, 5), (4, 4), (4, 5), (5, 5)}. It can be easily verified that S is a partial order on X. The Hasse diagram that represents S is shown in Figure 0.2.3. Maximal and Minimal Elements An element u in a partially ordered set A with a partial order R is called a maximal element in the set if whenever (u, x) is in R, then x = u. Similarly, an element v in A is a minimal element if whenever (x, v) is in R, then x = v. Example 0.2.12 Let X = {2, 3, 4, 5, 8, 12, 24, 25} and let R be the partial order on X defined by R = {(m, n) : m divides n}. Then 2 is a minimal element of R because no element in X divides 2. Similarly, 3 and 5 are also minimal elements of R. Similarly, 24 is a maximal element because there is no number in X that is divisible by 24. Another maximal element in X is 25. The minimal and maximal elements of a partial order can easily be spotted using its Hasse diagram, in which the minimal elements will be on the bottom and the maximal elements will be at the top if all the arrows are drawn upward. See Figure 0.2.4, representing the Hasse diagram of Example 0.2.12, in which the vertices representing 24 and 25 are at the top and the vertices representing 2, 3, and 5 are at the bottom. FIGURE 0.2.3 FIGURE 0.2.4 Example 0.2.13 P(A) is the partially ordered set of all subsets of A with the partial order defined by set inclusion, and in this PO set, A is the only maximal element and the empty set is the only minimal element. A partially ordered set may have more than one maximal (or minimal), as we saw in Example 0.2.12. There are partially ordered sets with no maximal or minimal elements. Consider the relation S = {(x, y) : x, y are integers, x ≤ y}. Then S is no doubt a partial order on the set Z of integers, but this PO set has no maximal or minimal element. Maximum (Greatest) and Minimum (Least) Elements An element M in a partially ordered set A with a partial order S is called a maximum (or greatest element) in A if (x, M) S for every x in the set A. Similarly, an element m is a minimum (or least element) if (m, x) S for every x the set A. [One should be very careful in distinguishing (1) between a maximal element and a maximum element and (2) between a minimal element and a minimum element. If an element is a maximum or a minimum, all elements in the set must be comparable to it. Of course, if a maximum element exists, it is no doubt a maximal element. Similarly, if a minimum element exists, it is a minimal element. The converse implications are not necessarily true, as can be seen from the Hasse diagrams in Example 0.2.14. In a multiparty government, each party leader can be considered as a maximal element, whereas in a single-party system the unique party leader is both maximum and maximal.] Example 0.2.14 Let A = {1, 2, 3, 4} and consider the four partial orders on A with Hasse diagrams as in Figure 0.2.5. In part (a), 4 is the greatest element and 1 is the least element. In (b), 4 is the greatest element and the minimal elements are 1 and 2. There is no least element in (b). In (c), 1 is a least element. There is no greatest element here; but 2, 3, and 4 are maximal elements. There are no greatest or least elements in (d). The elements 1 and 2 are minimal and the elements 3 and 4 are maximal. FIGURE 0.2.5 Example 0.2.15 In each of the following sets of positive integers, the ordered pair (m, n) is in a relation S if m divides n. (a) A = {2, 4, 6, 8}. Here 2 is the least element. There is no greatest element. The maximal elements are 6 and 8. (b) A = {2, 3, 4, 12}. The greatest element is 12. There is no least element. The minimal elements are 2 and 3. (c) A = {2, 4, 8, 16}. The greatest is 16 and the least is 2. (d) A = {2, 3, 4, 6}. Here 2 and 3 are minimal; 4 and 6 are maximal. Well-Ordered Sets A partially ordered set A in which every subset B has a least element m in B is called a well-ordered set. For example, if N is the set of all positive integers, and if we say that (a, b) is in S whenever a is less than or equal to b, then S is a partial order on N. Let B be any subset of N. Obviously, the smallest integer in B is the least element of B. Thus every subset of N has a least element in it. So N is a well-ordered set. The set A of real numbers in an interval is not a well-ordered set under the relation S, where (x, y) in S means that x is less than or equal to y. A subset of a well-ordered set is well-ordered. A well-ordered set A is linearly ordered because any set of two elements in A has a first element and therefore the relation has the comparison property. Zorn’s Lemma Let B be a subset of a partially ordered set A with the partial order relation S. An element u in A is called an upper bound of B if (x, u) is in S for all x in B. Observe that u need not be in B. If there exists an upper bound for B, we say that B has an upper bound. An arbitrary subset of a PO set need not have an upper bound. One of the most important and exceedingly powerful tools of mathematics is Zorn’s lemma, which asserts that if A is a partially ordered set in which every chain has an upper bound, then A has a maximal element. This lemma cannot be “proved” in the usual sense of the term. However, it can be shown that it is logically equivalent to the celebrated axiom of choice, which lies at the very foundation of set theory. Thus Zorn’s lemma is assumed as an axiom of logic and set theory. Many important existence theorems are proved by invoking Zorn’s lemma. The axiom of choice is also logically equivalent to the well-ordering theorem of Zermelo: Every set can be well-ordered. For a proof of Zorn’s lemma, using the axiom of choice, see the book Naive Set Theory by P. R. Halmos. 0.3 INDUCTIVE PROOFS AND RECURSIVE DEFINITIONS One of the most useful, elegant, and simple proof techniques in mathematics in general and in discrete mathematics in particular is the technique known as mathematical induction, which is essentially an “algorithmic proof procedure.” The origins of this technique can be traced to the days of the classical Greek period. But the term induction was coined by De Morgan only in the nineteenth century. The Principle of Mathematical Induction (Weak Form) This principle is stated as follows: Suppose that P(n) is a statement about the natural number n and q is a fixed natural number. Then an induction proof that P(n) is true for all n ≥ q requires two steps: 1. Basis step: Verify that P(q) is true. 2. Induction step: Verify that if k is any positive integer greater than or equal to q, then P(k + 1) is true whenever P(k) is true. Here P(n) is called the inductive hypothesis. When we complete both steps of a proof by mathematical induction, it is obvious that we have proved that the statement P(n) is true for all positive integers n ≥ q. [A formal proof is along the following lines: Suppose that P(n) is not true for all n ≥ q. Then there is at least one positive integer k ≥ q such that P(k) is not true. So the set D of positive integers r for which P(r) is not true is nonempty, and therefore this set has a unique least element because any set of positive integers is well-ordered. Let t be the first element of this set. Of course, t > q. Since t is an integer, t – 1 also is an integer which is not in D. So P(t – 1) is true, which implies by the induction step that P(t) is true. This is a contradiction.] This version of induction given above is called the weak form because the induction step assumes that P(n) is true in exactly one case. A strong form of induction is discussed later in this section. Example 0.3.1 Prove that 1 + 2 + 3 + · · · + n = n(n + 1)/2 for all natural numbers. Proof (By Mathematical Induction). Let P(n) be the statement that (1 + 2 + 3 + · · · + n) is equal to n(n + 1)/2. The aim is to prove that P(n) is true for all n. The basis step: We have to verify that P(1) is true. Here P(1) is the statement that 1 is equal to 1(1 + 1)/2. This is true. So P(1) is true. The induction step: We have to verify that if P(k) is true, then P(k + 1) is true. Now P(k) is the statement that 1 + 2 + · · · + k is equal to k(k + 1)/2 and P(k + 1) is the statement that 1 + 2 + · · · + (k + 1) is equal to (k + 1)(k + 2)/2. If P(k) is true, 1 + 2 + · · · + k = k(k + 1)/2. Thus 1 + 2 + · · · + k + (k + 1) = k(k + 1)/2 + (k + 1), which implies that 1 + 2 + · · · + (k + 1) = (k + 1) · (k + 2)/2. So P(k + 1) is true whenever P(k) is true. [One has to be very careful in using the induction method to prove theorems. The meaning of the induction step is very precise: If P(q) is true, P(q + 1) is true. If P(q + 1) is true, then P(q + 2) is true, and so on. In other words, the induction should hold for every k greater than or equal to q. An erroneous “proof” justifying the statement that all roses are of the same color is as follows. P(n) is the proposition that all roses in any collection of n roses are of the same color. Our aim is to show that P(n) is true for all n. Obviously, P(1) is true. Suppose that P(k) is true for some positive integer k. So all the roses in any collection of k roses are of the same colors. Now consider any arbitrary collection C of (k + 1) roses. Label these roses as ri (i = 1, 2, 3,... , k + 1). Let A be the set {ri : i = 1, 2,... , k} and B be the set {ri : i = 2, 3,... , k, k + 1}. Both A and B have exactly k roses. So the roses in A are all of the same color. Similarly, the roses in B also are of the same color. The rose labeled rk is in both A and B. So all the k + 1 roses under consideration are of the same color. So if P(k) is true, then P(k + 1) is true. Can we therefore conclude that P(n) is true for all n? The answer is “no” because when the set C has two elements, the sets A and B are disjoint. So if P(1) is true, P(2) need not be true.] Example 0.3.2 Use induction to prove that the sum of the first n odd positive integers is n2. Proof. Let P(n) be the statement that the sum of the first n odd positive integers is n2. The aim is to prove that P(n) is true for every n. The basis step: P(1) is true because 1 = 12. The induction step: We have to verify that P(k + 1) is true whenever P(k) is true for any positive integer k. Since P(k) is true, 1 + 3 + 5 + · · · + (2k – 1) = k 2. Consequently, 1 + 3 + 5 + · · · + (2k – 1) + (2k + 1) = k 2 + (2k + 1) = (k + 1)2 So P(k + 1) is true. Thus P(n) is true for every n. Example 0.3.3 Use induction to prove that n < 2n for any positive integer n. Proof. Let P(n) be the statement that n < 2n for the positive integer n. We have to prove that P(n) is true for any positive integer. The basis step: P(1) is true since 1 < 2. The induction step: Suppose that P(k) is true for an arbitrary positive integer, implying that k < 2k. Then k + 1 < 2k + 1 < 2k + 2k. Hence k + 1 < 2k + 1, which implies that P(k + 1) is true. So P(n) is true for all positive integers n. The Principle of Mathematical Induction (Strong Form) Suppose that P(n) is a statement about the natural number n and q is a fixed natural number. Then an induction proof that P(n) is true for all n ≥ q requires two steps: 1. Basis step: Verify that P(q) is true. 2. Induction step: Verify that if k ≥ q and if P(q), P(q + 1), P(q + 2),... , P(k) are true, then P(k + 1) is true. (This version of the induction principle is “strong” in the sense that the induction step here has more information than that of the induction step in the “weak” version. As in the previous case, it can easily be shown that the strong version is also a consequence of the fact that any set of natural numbers is well-ordered. So to prove a theorem using mathematical induction, one can use either version of mathematical induction. In some cases it is more convenient to use the strong form, as seen in the next example. The strong form of induction is also known as complete induction.) Example 0.3.4 Prove that any natural number greater than 1 can be factored as a product of prime numbers. Proof (By Complete Mathematical Induction). Let P(n) be the statement that when n is a natural number greater than 1, then n can be factored as a product of prime numbers. The aim is to prove that P(n) is true for all n. The basis step: P(2) is the statement that 2 can be factored as a product of primes. Obviously, P(2) is true. The induction step: Suppose that P(2), P(3),... , P(k) is true. We have to verify that P(k + 1) is true. Now P(k + 1) is certainly true when k + 1 is a prime number. If k + 1 is not a prime number, we can always find two positive integers m and n such that k + 1 = mn, where both m and n are less than k. By the induction step, both m and n can be expressed as the product of prime numbers. So k + 1 also can be factored as a product of prime numbers. Thus P(k + 1) is true. Recursive Definitions of Sets The basic idea underlying the principle of induction is as follows. Once we describe the initial stage in some process and if we are able to describe any subsequent stage in terms of the previous stages, we are in a position to describe the entire process completely at all stages. The parallel concept in computer science is recursion, where we tend to think of the process in the opposite direction. Informally, this is the process of solving a large problem by decomposing it into one or more subproblems such that each such subproblem is identical in structure to the original problem but more or less simpler to solve. So in both situations, one must (1) decide a set of simple cases for which the proof or computation is easily handled, and (2) obtain an appropriate rule that can be applied repeatedly until the end. This concept underlying both induction and recursion can be used to justify the definition of some collection of objects in stages. Such a description is called aptly an inductive or recursive definition. A recursive definition of a set consists of three parts: 1. Basis part: This part tells us that certain elements belong to the set we are going to define. 2. Inductive (recursive) part: This part tells us to use the elements currently in the set to obtain more objects that can be included in the set. 3. Closure part: This part tells that the only elements in the set are those obtained by (1) and (2). Example 0.3.5 To define the set A of positive integers divisible by the number 5 recursively, we have the recursive definition consisting of the following three parts: (a) 5 is an element of A. (b) If n is an element of A, then n + 5 also is an element of A. (c) An object is in A if and only if it is obtained by a repeated application of (a) and (b). Recursive Definitions of Functions Suppose that (1) each element i in the set S = {0, 1, 2,... , k} of the first k + 1 consecutive integers is assigned a real number ri, and (2) if n is any integer greater than k, there is a rule f for defining a real number f(n) which can be expressed uniquely in terms of some or all the terms from the set {f(n – 1), f(n – 2),... , f(n – k), f(n – k – 1)}. If we now define f(i) = ri for each i in S, the rule f is a function whose domain is the set of nonnegative integers. A function defined by this method is called a recursively defined function. The rule that defines f(n) in terms of the preceding values f(i) is called a recurrence relation. The values f(0), f(1), f(2),... , f(k) are called the initial values of the recurrence relation. We use the induction principle (strong form) to show that this definition does not violate the true definition of a function, [i.e., f(n) is unique for every nonnegative integer n]. THEOREM 0.3.1 If f is recursively defined, then f(n) is unique for every positive integer n. Proof: P(n) is the proposition that f(n) is unique for every n. The basis step: We assume that f(i) = ri is unique when i = 0, 1, 2,... , k. So P(0), P(1),... , P(k) is true. The induction step: f(k + 1) is expressed uniquely in terms of these k + 1 numbers. So P(k + 1) is true. Example 0.3.6 Suppose that N is the set of 11 nonnegative integers and R is the set of all real numbers. (a) The function f: N → R that defines the sequence f(n) = 3n can be recursively defined as f(0) = 1 and f(n) = 3f(n – 1) when n > 0. (b) The (factorial) function f: N → R, where f(n) = n!, can be recursively defined as f(0) = 1 and f(n) = nf(n – 1) when n > 0. (c) The Fibonacci sequence f: N → R defined recursively by the relation f(n) = f(n – 1) + f(n – 2) when n > 1, with the initial values f(0) = 0 and f(1) = 1 gives the sequence {0, 1, 1, 2, 3, 5, 8, 13,...}. It is important that in a recursive definition, the set of integers in the basis step constituting the initial conditions is a consecutive set of integers. Otherwise, the function may not be well-defined. Here is a counterexample: f(n) = 9f(n – 2), with the nonconsecutive initial values f(0) = 6 and f(2) = 54, will yield f(n) = 2 · 3n + 1 as well as f(n) = 3 · 3n + 3 · (–3)n. 0.4 THE LANGUAGE OF LOGIC At an introductory level, mathematical logic is very similar to set theory. Instead of sets, in logic we have propositions. A proposition is a statement that is either true or false but not both. The truth value of a proposition p is T (or 1) if p is true; otherwise, the truth value is F (or 0). Consider the following five sentences: 1. p: 3 + 2 = 5 2. q: 3 + 2 = 6 3. r: Is it 3 or 2? 4. s: Take 3 5. t: x + 2 = 5 Here p is a true proposition and q is a false proposition. Both r and s are not propositions, t is a proposition, but it is neither true nor false since x is unknown. In set theory we have the intersection and union of two sets and the complement of a set in a certain universal set. The analogous concepts in logic are the three logical operations: the conjunction of two propositions, the disjunction of two propositions, and the negation of a proposition. The conjunction of two propositions p and q is a proposition that is true if and only if both p and q are true propositions. The conjunction of p and q is called “p and q” and is denoted by p ∧ q. The disjunction of two propositions p and q is a proposition that is false if and only if both p and q are false propositions. The disjunction of p and q is called “p or q” and is denoted by p ∨ q. The exclusive disjunction of two propositions p and q is a proposition that is true if and only exactly one of the two is true and is denoted by p ⊕ q. Finally, the negation of a proposition p is a proposition p′ which is true if and only if p is false. A truth table displays the relationships between the truth values of propositions. The following table displays the truth values of conjunction, disjunction, exclusive disjunction, and negation of two propositions p and q: Propositions that can be obtained by the combination of other propositions are known as compound propositions. For example, if p, q, and r are three propositions, then “(p′ and q) or (q)” is a compound proposition. A proposition that is not a combination of other propositions is called an atomic proposition. The Implication Operation There is another important way to construct a compound proposition from two propositions p and q. This is the implication proposition: “if p, then q” (or “p implies q”) which is denoted by p → q. We define this compound proposition to be false if and only when p is true and q is false. In all other cases the compound proposition p → q is true. In this case we say that the proposition p is a sufficient condition for the proposition q and q is a necessary condition for p. Here p is called the hypothesis (or antecedent or premise) and q is called the consequence (or conclusion). Obviously, the compound proposition p → q and the compound proposition q → p both cannot be false at the same time. So irrespective of the truth values of p and q, it is always the case that at least one of these two compound propositions p → q and q → p is always true. Observe that the mathematical concept of implication is more general than the concept of implication regarding statements in the languages we use to communicate in our daily lives. In a general mathematical setting there is no cause- and-effect relationship between the truth value of the hypothesis and the truth value of the conclusion. For example, if p is the proposition that “it is raining today” and q is the proposition that “London is the capital of England,” then the implication proposition p → q is true whether or not p is true. The implication that “if it rains today, then 3 + 4 = 8” is a true proposition if it does not rain today. On the other hand, when I make the statement that “if it rains like this, I will not go fishing this afternoon,” this statement is an implication proposition in which there is a definite causal relation between the hypothesis and the conclusion. It is also important to mention in this context that the implication proposition in many programming languages has a different truth value. If a line in a program says “if n < 30 then S,” then when the execution of the program reaches this line, the segment S is executed if n < 30 and not executed otherwise. The compound proposition “p if and only if q,” which is denoted by p ↔ q, is the conjunction of the compound proposition p → q and the compound proposition q → p. The compound proposition p ↔ q is true when both p → q and q → p are true. In this case we say that p is both necessary and sufficient for q, and vice versa. Here is the truth table of these implication operations involving two operations p and q: If r is the proposition p → q, the proposition q → p is the converse of r, the proposition p′ → q′ is the inverse of r, and the proposition q′ → p′ is the contrapositive of r. If two propositions p and q are such that p is true if and only if q is true, the two propositions p and q are said to be equivalent. We write p = q when p and q are equivalent. In other words, two propositions are equivalent if they have the same truth value. For example, the proposition that “Jane will be 18 years old in 1993” is equivalent to the proposition that “Jane was born in 1975.” The compound proposition p → q is equivalent to its contrapositive proposition q′ → p′ since they both have the same truth value, as can be seen from the following truth table. A compound proposition that is always true irrespective of the truth values of its component propositions is called a tautology. A compound proposition that is always false is called a contradiction. As a simple example, the disjunction of a proposition p and its negation is a tautology, whereas the conjunction of p and its negation is a contradiction. From the table given above we notice that the proposition p ↔ q is a tautology if and only if p = q. The commutative, associative, and distributive laws involving the conjunction and disjunction operation can easily be verified by constructing the appropriate truth tables. These laws are: 1. The commutative laws: p ∧ q = q ∧ p and p∨q=q∨p 2. The associative laws: p ∧ (q ∧ r) = (p ∧ q) ∧ r and p ∨ (q ∨ r) = (p ∨ q) ∨ r 3. The distributive laws: p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∨ r) and p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) The truth value of a compound proposition depends on the truth values of its component propositions. The subject of constructing and simplifying compound propositions built from other propositions and obtaining their truth values is called propositional calculus. This combination of propositions to yield new propositions bears a strong resemblance to the combination of sets to form new sets. The following theorem is analogous to De Morgan’s laws on set theory. THEOREM 0.4.1 (a) (p ∧ q)′ = (p′) ∨ (q′). (b) (p ∨ q)′ = (p′) ∧ (q′). Proof: This is left as an exercise. The Satisfiability Problem in Logic The truth table of a compound proposition with n atomic propositions as its components will have 2n rows. The satisfiability problem of a compound proposition p is the problem of (1) finding out whether there exist truth values for the atomic components of p such that p is true, and (2) obtaining the true atomic propositions and the false atomic propositions if they exist which make the compound proposition true. The only known procedure for testing the satisfiability of a proposition with n atomic propositions is building a truth table enumerating all the 2n possibilities of truth values, and this is a formidable task indeed when n is large. 0.5 NOTES AND REFERENCES A systematic investigation of the theory of sets began with the contributions of Georg Cantor (1848–1918) in the nineteenth century. Prior to that, set theory and more generally nonnumerical mathematics were not investigated in a formal manner apart from the contributions of George Peacock (1791–1858), Augustus De Morgan (1806–1871), and George Boole (1815–1864). Peacock and De Morgan generalized the usual algebraic operations beyond the realm of numerical mathematics and Boole extended and formalized their contributions in his seminal work entitled “Investigation of the Laws of Thought” in 1854. According to the great twentieth-century philosopher and mathematician Bertrand Russell (1872–1970), it was George Boole who “discovered” pure mathematics. More on the history and development of set theory can be found in Boyer (1968). For a detailed treatment of set theory, including functions and relations, the books by Halmos (1960) and Stoll (1963) are highly recommended. The technique of proof by induction was explicitly stated and used by Francesco Maurolycus in the sixteenth century when he proved that the sum of the first n odd positive integers is n2. However, this technique was known to mathematicians as early as the third century B.C. For example, in Euclid’s proof that there are an infinite number of primes, this technique was used implicitly. In the seventeenth century, both Pascal and Fermat used the induction method extensively. The term mathematical induction was coined by De Morgan. In the nineteenth century, the principle of induction was investigated in detail by Gottlieb Frege (1848–1925), Giuseppe Peano (1858–1932), and Richard Dedekind (1831–1916). The role of induction in the formal development of mathematics became a primary focus of many mathematical logicians at the beginning of the twentieth century, and two names worth mentioning in this regard are those of Bertrand Russell and Thoralf Skolem (1887– 1963). For an interesting survey on the topic of mathematical induction, see the article by Bussey (1917). Golovina and Yaglom (1963), Poly a (1954), and Sominskii (1963) are three excellent references in this area. The article by Henkin (1960) is also highly recommended. The origins of a systematic study of logical reasoning can be traced to Aristotle, who lived in the fourth century B.C. It was not until the seventeenth century, however, that symbols were used in the study of logic. The pioneering work in symbolic logic was done by Gottfried Leibniz (1646–1716). No major developments took place until George Boole published his outstanding work mentioned earlier. Since then Bertrand Russell and Alfred North Whitehead (1861–1947) contributed considerably to the development of logic and the field of mathematical logic emerged when the discovery of certain paradoxes led to an extensive examination of the place of logic, proof, and set theory in the foundations of mathematics. 0.6 EXERCISES 0.1. Let A = {3, 5, 7, 9}, B = {2, 3, 5, 6, 7}, and C = {2, 4, 6, 8} be all subsets of the universe X = {2, 3, 4, 5, 6, 7, 8, 9}. Find (a) the union of A and B, (b) the intersection of B and C, (c) B – A, (d) A – B, (e) the absolute complement C′ of the set C, (f) the absolute complement of X, (g) the absolute complement of the empty set. 0.2. Let A, B, C be as in Problem 0.1. Find the following sets: (a) (A ∪ B) – C, (b) the intersection of (A ∪ B)′ and (B ∪ C)′, (c) (A ∪ C) – (C – A)′ 0.3. Which of the following sets are equal? (a) {a, b, c, c}, (b) {a, b, a, b, c}, (c) {a, b, b, c, d} 0.4. Which of the following sets are equal? (a) {t : t is a root of x 2 – 6x + 8 = 0} (b) {y : y is a real number in the closed interval [2, 3]} (c) {4, 2, 5, 4} (d) {4, 5, 7, 2} – {5, 7} (e) {q : q is either the number of sides of a rectangle or the number of digits in any integer between 11 and 99} 0.5. If A = {3, 4} and B = {p, q, r}, list all the elements of (a) A × A, (b) A × B, (c) B × A and (d) B × B. 0.6. Let A and B be as in Problem 0.5. List all the elements of (a) A × A × A and (b) A × A × B. 0.7. Let A and B be as in Problem 0.5. List all the elements of (a) A ∪ (B × A) and (b) (A × A) ∪ (B × A). 0.8. List all the sets in the power set of the following sets: (a) {a, b}, (b) {a, b, c}, (c) {ϕ, 0, {0}} 0.9. List all partitions of the following sets: (a) {a}, (b) {a, b}, (c) {a, b, c} 0.10. Determine whether each of the following statements is true in the case of three arbitrary sets P, Q, R. (a) If P is an element of Q and if Q is a subset of R, then P is an element of R. (b) If P is an element of Q and if Q is a subset of R, then P also is a subset of R. (c) If P is a subset of Q and Q is an element of R, then P is an element of R. (d) If P is a subset of Q and Q is an element of R, then P is a subset of R. 0.11. Prove the following assertions involving three arbitrary sets P, Q, and R. (a) (P – Q) – R = P – (Q ∪ R) (b) (P – Q) – R = (P – R) – Q (c) (P – Q) – R = (P – R) – (Q – R) 0.12. Two sets A and B are such that their union and their intersection are equal. What can we say about A and B? 0.13. Suppose that A is a subset of B and C is a subset of D. (a) Is it true that (A ∪ C) is a subset of (B ∪ D)? (b) Is it true that the intersection of A and C is a subset of the intersection of B and D? 0.14. What can we say about two sets P and Q if P – Q is equal to Q – P? 0.15. Prove that A and B are nonempty sets such that if A × B and B × A are equal, then A = B. 0.16. What is the cardinality of P × Q if the cardinality of P is p and the cardinality of Q is q? 0.17. Prove that the intersection of the powerset of A and the powerset of B is the powerset of the intersection of A and B, where A and B are two arbitrary sets. 0.18. What can we say if the operation “intersection” is replaced by the operation “union” in Problem 0.17? 0.19. What is the cardinality of the powerset of the empty set? 0.20. If the powerset of A is equal to the powerset of B, does it follow that A and B are equal? 0.21. The symmetric difference of two sets A and B is the set containing those elements of either A or B but not both A and B and is denoted by A ⊕ B. Prove: A ⊕ B = (A – B) ∪ (B – A) = (A ∪ B) – (A ∩ B). 0.22. Draw a Venn diagram to represent the symmetric difference of two sets. 0.23. How many distinct regions are there in a Venn diagram that represents three sets in a universal set such that no intersection is empty? 0.24. If the symmetric difference of two sets A and B is equal to the set A, what can we say about A and B? 0.25. If A and B are two arbitrary sets, under what conditions can we conclude that the symmetric difference of (A – B) and (B – A) is the empty set? 0.26. Using Venn diagrams, investigate whether the following statements are true or false. (a) A ⊕ (B ∩ C) = (A ⊕ B) ∩ (A ⊕ C) (b) A ⊕ (B ∪ C) = (A ⊕ B) ∪ (A ⊕ C) (c) A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C (d) A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C) (e) A ∪ (B ⊕ C) = (A ∪ B) ⊕ (A ∪ C) 0.27. If the symmetric difference of A and B is equal to the symmetric difference of A and C, is it necessary that B = C? 0.28. Prove the following assertions involving three arbitrary sets A, B, and C: (a) A × (B ∩ C) = (A × B) ∩ (A × C) (b) A × (B ∪ C) = (A × B) ∪ (A × C) (c) (A ∩ B) × C = (A × C) ∩ (B × C) (d) (A ∪ B) × C = (A × C) ∪ (B × C) 0.29. Let R be the set of all real numbers and f: R → R defined by f(x) = x 2. (a) What are the domain, codomain, and range of this function? (b) Is f an injection? (c) Is f a surjection? (d) Find the set of all preimages of 4. (e) Find the inverse image of the set {t : 1 ≤ t ≤ 4}. 0.30. If R is the set of all real numbers, explain why F(x) = 1/(x – 2) and F(x) = (the square root of x) are not functions from R to R. 0.31. If N is the set of all natural numbers and if f: N → N is defined by f(n) = 2n + 5, show that f is an injection and find the inverse function. Is f a surjection? Is the inverse function a surjection? 0.32. Suppose that f(x) = x 2 – 4, where x is a real number. Find the images of the following sets: (a) {–4, 4, 5}, (b) {4, 5} (c) {t : t is a real number greater than or equal to zero}. 0.33. Let A = {a, b, c, d} and B = {p, q, r}. (a) Find the number of functions from A to B. (b) Find the number of injections from A to B. (c) Find the number of surjections from A to B. (d) Find the number of functions such that a is mapped into p and b is mapped into q. 0.34. If N is the set of all natural numbers, give an example of a function from N to N that is (a) an injection but not a surjection, (b) a surjection but not an injection. 0.35. Find the domain and range of the function that assigns (a) each integer its last digit, (b) each integer the number of digits in it. 0.36. Give an example of a function f from the set of real numbers to the set of real numbers such that (a) f is both an injection as well as a surjection, (b) f is neither an injection nor a surjection. 0.37. Suppose that X = {p, q, r}, Y = {a, b, c, d}, and Z = {1, 2, 3, 4}. Let g: X → Y be defined by the set of ordered pairs {(p, a), (q, b), (r, c)} and f: Y → Z be defined by the set of ordered pairs {(a, 1), (b, 1), (c, 2), (d, 3)}. Write the composite function f ○ g as a set of ordered pairs. 0.38. If A = {p, q, r} and f: A → A is defined by f(p) = q, f(q) = p, and f(r) = q, describe f and f ○ f as sets of ordered pairs. 0.39. Let A and f be as in Problem 0.38. Define f n = f ○ f ○ f ○ · · · ○ f as the n-fold composition of f with itself. Describe f n as a set of ordered pairs when n is odd and when n is even. 0.40. Show that the set of all positive integers is equivalent to the set of all positive even integers. 0.41. Let f: B → C and g: A → B. Prove the following: (a) If f and g are injections, then f ○ g is an injection. (b) If f and g are surjections, then f ○ g is a surjection. 0.42. Let f and g be as in Problem 0.41. (a) Suppose that f ○ g is an injection. Is it necessary that f be an injection? Is it necessary that g be an injection? (b) Suppose that f ○ g is a surjection. Is it necessary that f be a surjection? Is it necessary that g be a surjection? 0.43. If f(x) = ax + b and g(x) = cx + d and f ○ g = g ○ f, find an equation relating a, b, c, and d. 0.44. Suppose that f: X → Y and A and B are subsets of X. Then prove: (a) f(A ∪ B) = f(A) ∪ f(B) and (b) f(A ∩ B) is a subset of the intersection of f(A) and f(B). 0.45. Show that if f: X → Y is an injection, then f(A ∩ B) = f(A) ∩ (B) for all subsets A and B of X. 0.46. Show that there is an injection from A to B if and only if there is a surjection from B to A. 0.47. Suppose that f: A → B where A and B are two finite sets with the same cardinality. Prove that f is an injection if and only if f is a surjection. 0.48. Let A be a subset of a universal set X. The characteristic function f A of A is the function from X to the set {0, 1} such that the image of every element in A is 1 and the image of every element not in A is 0. Suppose that A and B are two subsets of X. Prove the following for all x in X. (a) f A∩B(x) = f A(x) · f B(x) for all x in X (b) f A∪B(x) = f A(x) + f B(x) – f A(x) · f B(x) (c) f A(x) + f A′(x) = 1 (d) If C is the symmetric difference of A and B, then f C(x) = f A(x) + f B(x) – 2f A(x) · f B(x). 0.49. Let S = {0, 1} and let Sn be the set of all strings of length in S. If u and v are two strings in Sn , we compare them place by place and define the Hamming distance H(u, v) between u and v to be the number of places where they differ. Find the Hamming distance between u and v if (a) u = 101100 and v = 111011 (b) u = 01010 and v = 11001. 0.50. Suppose that S, Sn , and H(u, v) are as in Problem 0.49. The function H: Sn × Sn → N (where N is the set of all nonnegative integers) which maps the ordered pair (u, v) into H(u, v) is the Hamming distance function. Show that for all u, v, and w in Sn , the function H satisfies the following metric axioms: (a) H(u, v) is nonnegative, (b) H(u, v) = 0 if and only if u = v, (c) H(u, v) = H(v, u), and (d) H(u, v) ≤ H(u, w) + H(w, v). 0.51. Let A = {1, 2, 3, 4, 5}, B = {a, b, c, d}, and R be the relation {(1, a), (1, b), (3, c), (4, d), (5, d), (5, c)}. Represent this relation by a bipartite graph and draw the appropriate arrows. 0.52. Give an example of a relation on a set that is (a) both symmetric and antisymmetric, (b) neither symmetric nor antisymmetric. 0.53. Let A = {a, b, c, d}. Draw the diagraph corresponding to each of the following relations on A and decide whether each relation is reflexive, symmetric, transitive, and antisymmetric. Examine whether the comparison property holds in any of these relations. (a) R = {(b, b), (b, c), (b, d), (c, b), (c, c), (c, d)} (b) R = {(a, b), (b, a)} (c) R = {(a, a), (b, b), (c, c), (d, d)} (d) R = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)} (e) R = {(a, c), (a, d), (b, c), (b, d), (c, a), (c, d)} (f) R = {(a, b), (b, c), (c, d)} 0.54. Let R be a relation from A to B and S be a relation from B to C. Then the composite relation S ○ R of R and S is the relation consisting of all ordered pairs of the form (a, c), where (a, b) is in R and (b, c) is in S. If A = {p, q, r, s}, B = {a, b}, C = {1, 2, 3, 4}, R = {(p, a), (p, b), (q, b), (r, a) (s, a)} and S = {(a, 1), (a, 2), (b, 4)}, find S ○ R. 0.55. Let R be a relation on the set A. The relation R2 on A is defined as R ○ R. Show that R2 ○ R is equal R ○ R2. Thus R3 is the composite of R2 and R. More generally, the nth power Rn of the relation is the composite of Rn–1 and R. If R = {(a, a), (a, b), (b, a), (c, b), (c, d)}, find the second and third powers of R. 0.56. Prove that if a relation on a set is reflexive, then any power of that relation is reflexive. 0.57. Prove that if a relation R on a set is reflexive and transitive, then Rn = R for all positive integers n. 0.58. Let R be a relation from A to B. The inverse relation R–1 from B to A is the set of all ordered pairs of the form (b, a), where (a, b) is in R. Show that a relation R on a set is symmetric if and only if R and its inverse are equal. 0.59. Show that a relation on a set is reflexive if and only if its inverse relation is reflexive. 0.60. Prove that a relation R on a set A is antisymmetric if and only if the intersection of R and its inverse is a subset of the diagonal relation D = {(x, x) : x A}. 0.61. Let R be the relation on the set A = {1, 2, 3, 4, 5, 6, 7} defined by the rule (a, b) R if the integer (a – b) is divisible by 4. List the elements of R and its inverse. 0.62. Let R be the relation on the set N of all positive integers defined by (a, b) R if b is divisible by a. Determine whether R is reflexive, symmetric, antisymmetric, or transitive. 0.63. Let N be the set of all positive integers and let R be the relation on N × N defined by ((a, b), (c, d)) is in R if a ≤ c and b ≤ d. Determine whether R is reflexive, symmetric, antisymmetric, or transitive. 0.64. Which of the following relations on the set {1, 2, 3, 4} are equivalence relations? If the relation is an equivalence relation, list the corresponding partition (equivalence class). (a) {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1)} (b) {(1, 0), (2, 2), (3, 3), (4, 4)} (c) {(1, 1), (2, 2), (1, 2), (2, 1), (3, 3), (4, 4)} 0.65. Let R = {(x, y) : x and y are real numbers and x – y is an integer}. Show that R is an equivalence relation on the set of real numbers. 0.66. Let a be an integer and m be a positive integer. We denote by a (mod m) the remainder when a is divided by m. If a and b are two integers, we say that a is congruent to b modulo m if m divides a – b. The notation a ≡ b (mod m) is used to indicate that a is congruent to b modulo m. Of course, if a is congruent to b modulo m, then b is congruent to a modulo m. Prove that: (a) a (mod m) = b (mod m) if and only if a ≡ b (mod m). (b) a ≡ b (mod m) if and only if there exists an integer k such that a = b + km. (c) If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ (b + d) (mod m) and ac ≡ bd (mod m). 0.67. Let Z be the set of all integers and let m be any positive integer greater than 1. Show that the relation R on Z defined by the set {(a, b) : a ≡ b (mod m)} is an equivalence relation. This relation is called the congruence modulo m relation on the set of integers. The equivalence classes of this relation are called congruence classes modulo m. The congruence class of an integer x modulo m is dented by [x]m. 0.68. Find the congruent classes modulo 5: (a) 5, (b) 5, and (c) 5. 0.69. Prove that {[i]m : i = 0, 1, 2,... , (m – 1)} is a partition of the set of integers. 0.70. Let f be a function from A to A. Let R be the relation on A defined by {(x, y) : f(x) = f(y)}. Prove that R is an equivalence relation on A. What is the equivalence class? 0.71. Suppose that R is an equivalence relation on a nonempty set A. Show that there is a function f with A as domain such that (x, y) is in R if and only if f(x) = f(y). 0.72. Suppose that {(a, b), (c, d)} is in R whenever a, b, c, d are positive integers and ad = bc. Show that R is an equivalence relation on the set of positive integers. 0.73. Let X = {1, 2, 3, 4, 5,... , 15}. Let R be the relation on X defined by (x, y) R if (x – y) is divisible by 3. Prove that R is an equivalence relation on X. Find the equivalence class. 0.74. Let R be a transitive and reflexive relation on a set A. If S is a relation on A such that (x, y) is in S if and only if both (x, y) and (y, x) are in R, prove that S is an equivalence relation on A. 0.75. Prove that a reflexive relation R on a set A is an equivalence relation on A if and only if (x, y) and (x, z) in R implies that (y, z) is in R. 0.76. If S is the relation defined on the set of real numbers as S = {(x, y) : x ≤ y}, show that S is a partial order on the set of real numbers. 0.77. If S is the relation defined on the set of positive integers as S = {(x, y) : x divides y}, show that S is a partial order on the set of positive integers. 0.78. Let X = {a, b, c} and S be the partial order defined on the powerset P(X) defined as S = {(A, B) : A is a subset of B}. List the elements of S. 0.79. Draw the Hasse diagram of the partial order S of Problem 0.78. 0.80. Let X = {1, 2, 3, 4, 5, 6, 7, 8, 9} and S = {(m, n), where m divides n} be a partial order on X. Draw the Hasse diagram that represents S. Locate a chain in X. 0.81. Prove that if R is a partial order on the set A, its inverse R–1 also is a partial order on A. The partially ordered set (A, R–1) is called the dual of the partially ordered set (A, R). 0.82. Let A = {2, 3, 4, 6, 8, 12, 16, 24} and S be the partial order relation on A defined by S = {(a, b) : a divides b}. Find (a) the minimal elements in A, (b) the maximal elements in A, and (c) the upper bounds of the set B = {4, 6, 12}. 0.83. Draw the Hasse diagram of the PO set in Problem 0.82. 0.84. Prove that (a) every finite partially ordered set has a maximal element and a minimal element, and (b) every finite linearly ordered set has a greatest element and a least element. 0.85. Prove by induction that 1k + 2k + 3k + · · · + nk is equal to (a) n(n + 1) (2n + 1)/6 when k = 2, and (b) [n(n + 1)/2]2 when k = 3. 0.86. Prove by induction that 1.2 + 2.3 + 3.4 + · · · + n(n + 1) is equal to n(n + 1)(n + 2)/3. 0.87. Prove by induction that 1/1.2 + 1/2.3 + 1/3.4 + · · · + 1/n(n + 1) is equal to n/(n + 1). 0.88. Show that n3 + 2n is divisible by 3 for all positive integers n. 0.89. Prove that 1.2.3 + 2.3.4 + 3.4.5 + · · · + n(n + 1)(n + 2) is equal to n(n + 1)(n + 2) (n + 3)/4. 0.90. Prove that 12/1.3 + 22/3.5 + · · · + n2/(2n – 1)(2n + 1) is equal to [n(n + 1)]/2(2n + 1). 0.91. Show that the sum of the cubes of any three consecutive positive integers is divisible by 9. 0.92. Show that for any positive integer n greater than 1, the sum is greater than. 0.93. Prove: (1 – 1/2)(1 – 1/3) · · · (1 – 1/n) = 1/n. 0.94. Prove: 2n > n2 whenever n > 4. 0.95. Show that 1/(n + 1) + 1/(n + 2) + · · · + 1/(2n) is greater than 13/24 whenever n is greater than 1. 0.96. Prove that 7n – 1 is divisible by 6. 0.97. Prove that 11n – 6 is divisible by 5. 0.98. Show that 6.7n – 2.3n is divisible by 4. 0.99. Prove: 3n + 7n – 2 is divisible by 8. 0.100. Prove De Morgan’s laws: (a) The absolute complement of the intersection of n subsets of a universal set is equal to the union of the absolute complements of these n sets. (b) The absolute complement of the union of these n sets is the intersection of their absolute complements. 0.101. Show that the cardinality of the powerset of a set with n elements is 2n. 0.102. Prove that if S is a transitive relation on a set A, then Sn is a subset of S for n = 1, 2, 3,.... 0.103. Suppose that f is recursively defined as f(0) = 1 and f(n + 1) = 3f(n) + 5. Find f(1), f(2), and f(3). 0.104. Give a recursive definition of x n when x is a real number and n is a nonnegative integer. 0.105. Give a recursive definition of f where f(n) is the sum of the first n positive integers. 0.106. Give a recursive definition of the set of (a) all integers, (b) all positive odd integers, (c) all negative even integers and (d) all even integers. 0.107. Construct the truth table of the statement p → (p ∨ q) and determine whether it is a tautology or a contradiction or neither. 0.108. Show that (p′ ∨ q) ∧ (p ∧ (p ∧ q)) is equivalent to (p ∧ q). 0.109. Examine whether (p → q) → r is a tautology or a contradiction. 0.110. Construct the truth table of the statement [(p → q) ∧ (q → p)] ↔ (p ↔ q) and determine whether it is a contradiction. 0.111. Construct the truth table of q ↔ (p′ ∨ q′). 0.112. Suppose that p and r are false statements and q and s are true statements. Find the truth values of (a) (p → q) → r (b) (s → (p ∧ r′)) ∧ ((p → (r ∨ q)) ∧ s) 0.113. Find the truth assignments of p, q, r, s, and t such that the following are satisfiable: (a) (p ∧ q ∧ r) → (s ∨ t) (b) (p′ ∧ q′) ∨ r′ 0.114. Show that (p → q) → (p′ ∨ q) is a tautology. 0.115. Prove: (p ∧ q) ∧ (p ∨ q)′ is a contradiction. 0.116. Show that ((p → q) → q) ((p – q)′ ∨ q) is a tautology. Combinatorics 1.1 TWO BASIC COUNTING RULES Combinatorics is one of the fastest-growing areas of modern mathematics. It has many applications to several areas of mathematics and is concerned primarily with the study of finite or discrete sets (much as the set of integers) and various structures on these sets, such as arrangements, combinations, assignments, and configurations. Broadly speaking, three kinds of problems arise while studying these sets and structures on them: (1) the existence problem, (2) the counting problem, and (3) the optimization problem. The existence problem is concerned with the following question: Does there exist at least one arrangement of a given kind? The counting problem, on the other hand, seeks to find the number of possible arrangements or configurations of a certain pattern. The problem of finding the most efficient arrangement of a given pattern is the optimization problem. In this chapter we study techniques for solving problems that involve counting. These techniques form a basis for the study of enumerative combinatorics, which is really the theory of counting where results involving counting are obtained without carrying out the exact counting process, which could be tedious. Suppose that there are 10 mathematics majors and 15 computer science majors in a class of 25 and we are required to choose a student from the class to represent mathematics and another student to represent computer science. Now there are 10 ways of choosing a mathematics major and 15 ways of choosing a computer science major from the class. Furthermore, the act of choosing a student from one area in no way depends on the act of choosing a student from the other. So it is intuitively obvious that there are 10 × 15 = 150 ways of selecting a representative from mathematics and a representative from computer science. On the other hand, if we are required to select one representative from mathematics or from computer science, we have only 10 + 15 = 25 ways of accomplishing this. In the former case we used the multiplication rule of counting and in the latter the addition rule. These two rules can be stated formally as follows. MULTIPLICATION RULE (The Rule of Sequential Counting) Suppose that there is a sequence of r events E1, E2,... , Er such that (1) there are ni ways in which Ei(i = 1, 2,... , r) can occur, and (2) the number of ways an event in the sequence can occur does not depend on how the events in the sequence prior to that event occurred. Then there are (n1) · (n2) ·... · (nr) ways in which all the events in the sequence can occur. ADDITION RULE (The Rule of Disjunctive Counting) Suppose that there are r events E1, E2,... , Er such that (1) there are ni outcomes for Ei(i = 1, 2,... , r), and (2) no two events can occur simultaneously. Then there are (n1) + (n2) + · · · + (nr) ways in which one of these r events can take place. These two elementary rules are very useful in solving counting problems without carrying out explicit enumeration. However, if one is not careful, they are likely to be misused, producing erroneous results, as may be seen from some of the examples we discuss in what follows. Example 1.1.1 There are five characters—two letters of the alphabet followed by three digits—which appear on the back of one series of a microcomputer made by an electronics company. The number of possible computers manufactured in this series is (1) 26 × 26 × 10 × 10 × 10 = 676,000 if characters can repeat, (2) 26 × 25 × 10 × 10 × 10 = 650,000 if letters cannot repeat, and (3) 26 × 25 × 10 × 9 × 8 = 468,000 if no characters can repeat. We use the multiplication rule here. Example 1.1.2 A professor has 25 students in her advanced calculus course and 31 students in her statistics course. Thirteen students have signed up for both the courses. There are three events here, no two of which can occur simultaneously: (1) The event that a student chosen at random has signed up for advanced calculus but not for statistics, and this can happen in 12 ways; (2) the event that a student chosen at random has signed up for statistics but not for advanced calculus, and this can happen in 18 ways; and (3) the event that a student chosen at random has signed up for both the courses and this can happen in 13 ways. By the addition rule one of these events can occur in 12 + 18 + 13 = 43 ways. In other words, the professor has 43 students in both the courses together. Notice that the event that a student chosen at random takes advanced calculus and the event that a student chosen at random takes statistics can occur simultaneously. So we cannot apply the addition rule to the two events to conclude that the professor has a total of 25 + 31 = 56 students. Example 1.1.3 In a sightseeing group there are 8 Austrians, 5 Brazilians, and 6 Canadians. So by the multiplication rule there are 40 ways of choosing an Austrian and a Brazilian, 48 ways of choosing an Austrian and a Canadian, and 30 ways of choosing a Brazilian and a Canadian. Next, by the addition principle, there are 40 + 48 + 30 = 118 ways of selecting a pair of individuals of distinct nationalities from this group of tourists. A team of 3 tourists of distinct nationalities can be chosen in 8 × 5 × 6 ways, whereas a typical representative can be chosen in 8 + 5 + 6 ways. Example 1.1.4 The number of odd integers between 0 and 99 is obviously 50. We may invoke the multiplication rule to get this result. Any integer between 0 and 99 has a unit digit and a tens digit if we write 0, 1, 2,... , 9 as 00, 01, 02,... , 09. Let E be the event of choosing a digit for the unit digit. This can be done in 5 ways. Next, let F be the event of choosing a digit for the tens digit. This can be done in 10 ways. Notice that the number of ways that E can occur does not depend on how F can occur, and vice versa. So the sequence E, F (or for that matter, the sequence F, E) can occur in 50 ways. Example 1.1.5 Suppose that we are interested in finding the number of odd integers between 0 and 100 with distinct digits. Let E and F be as in Example 1.1.4. E can be done in 5 ways as before. After that F can occur in 9 ways. The number of ways that F can occur does not depend on how E occurs. So by the multiplication rule the sequence E, F can occur in 45 ways, and consequently, there are 45 such integers. On the other hand, if F is the first event, it can occur in 10 ways. Subsequently, the second event E can be done in 5 ways if the tens digit is even, and in 4 ways if the tens digit is odd. In other words, the number of ways in which E occurs depends on how the event F occurs. So we cannot apply the multiplication rule to the sequence F, E in this case. Example 1.1.6 Suppose that X is a set with n elements. List the elements of X as 1, 2,... , n and consider the following sequence of n events: The first event is to decide whether or not to pick the first element, the second event is to decide whether or not to pick the second elment, and so on. Each event can occur in 2 ways and the number of ways that any of these events in the sequence can occur does not depend on how the previous events in the sequence occurred. Thus any set with n elements has 2n subsets, by the multiplication rule. The class of all subsets of the set X is the power set of X and is denoted by P(X) as mentioned in Chapter 0. 1.2 PERMUTATIONS Consider a collection X of n distinct objects. An r-permutation of X is an arrangement in a row of any r objects from X. Of course, r is at most n. Thus if X is the collection of the first 5 letters a, b, c, d, and e, then edcb, dbea, and bdca are some of the several 4-permutations of X. The total number of r-permutations of a collection of n distinct objects is denoted by P(n, r). Any r-permutation here can be considered as a sequence of r events in which the number of ways an event can occur does not depend on how the events prior to that event occur. So we use the multiplication rule of counting to conclude that P(n, r) is equal to n(n – 1)(n – 2) · · · (n – r + 1) since any arbitrary object from X can be chosen in n ways and having chosen that, a second arbitrary object can be chosen in (n – 1) ways, and so on, until all r objects are chosen. Permutations and the Allocation Problem We can approach this process of making arrangements of objects from a different point of view. Consider a set of n distinct locations arranged in a definite order and we are required to allocate r distinct objects to these locations such that no location can receive more than one object. Then the number of ways of allocating these r objects to the n locations is also P(n, r) by the multiplication rule since any arbitrary object can be sent to one of the locations in n ways, and subsequently another one can be sent in (n – 1) ways, and so on. Example 1.2.1 If X = {1, 2, 3, 4, 5, 6, 7} and r = 3, the number of r-permutations of X is 7 × 6 × 5 = 210. Any n-permutation of a set X with n elements is simply called a permutation of X and the number P(n, n) of permutations of X is n(n – 1)(n – 2) ·... · 3 · 2 · 1, which is denoted by the factorial function n!. It is easy to see that P(n, r) = n!/(n – r)!. (We define 0! = 1.) [The positive integer n! can be extremely large even when n is a small two-digit number. It is more than 3.6 million when n = 10 and it is approximately equal to (2.433)(1018) when n = 20.] Circular and Ring Permutations Example 1.2.2 Consider a collection of 5 stones of different colors: blue (B), green (G), red (R), pink (P), and white (W). (a) The number of ways of making a tiepin on which these 5 stones are to be placed horizontally is, of course, 5!. (b) In how many ways can we make a tiepin on which these stones are placed in a circular pattern? The answer has to be less than 5! because some of the permutations considered in (a) are now not distinct. For example, if we rotate the permutation BGRPW once in the clockwise direction, we get the permutation GRPWB, and these two permutations are not distinct in a circular arrangement. If we fix one of the colors and then consider the permutations formed by the remaining 4 colors, these permutations are all distinct. For example, if we fix B and consider RGPW and RGWP, we get two permutations, BRGPW and BRGWP, which are distinct. Thus there are only (4!) such circular permutations. (c) In how ways can we make a ring in which these stones are mounted? In a ring, there is no difference between a permutation and its “mirror image.” For example, BGRPW and BWPRG are the same. For every permutation in (b), there is a mirror image. So the answer now is (4!)/2. Thus the number of circular permutations of a set of n elements is (n – 1)! and the number of ring permutations is ((n – 1)!)/2. Generalized Permutations Let us now consider a collection X of n objects (not necessarily distinct) belonging to k different nonempty groups such that (1) all the objects in a group are identical, and (2) an object in a group is not identical to an object in another group. (For example, the letters in the collection a, b, a, b, b, d, e, e, d can be formed into four groups: one for a, one for b, one for d, and one for e.) Assume that there are ni objects in group i where i = 1, 2,... , k. Any arrangement in a row of these n objects is called a generalized permutation of X. (For example, LINISOIL is a generalized permutation of the letters that appear in the word ILLINOIS.) The number of such generalized permutations is denoted by P(n; n1, n2,... , nk ), which will be n! if all the objects in X are distinct. THEOREM 1.2.1 If the collection X of n objects consists of k distinct nonempty groups such that group i has ni identical objects (where i = 1, 2,... , k), then the number of generalized permutations of X is (n!)/(n1!)(n2!) · · · (nk !). Proof: If the objects belonging to group i were all distinct, there would have been ni! permutations for the elements in this group. So each generalized permutation gives rise to N = (n1!)(n2!) · · · (nk !) permutations of X if X had distinct objects. If t is the total number of generalized permutations, we have (t)(N) = n!, from which the conclusion of the theorem follows. [Observe that if k = n, each group has exactly one element that is equivalent to the statement that the objects in X are distinct verifying that P(n; 1, 1,... , 1), where 1 is repeated n times, is equal to n!, as it should.] Example 1.2.3 The 9 letters that appear in the word CONSENSUS can be grouped into 6 groups: the group consisting of three S’s, the group con

Introductory Discrete Mathematics (Dover Books on Computer Science) PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue