Applied Discrete Structures

The section begins by introducing the intuitive concept of a set as a collection of objects called elements. It acknowledges the inherent difficulty mathematicians face in formally defining 'set,' citing the circularity of defining a set using terms like 'collection.' The text emphasizes that while rigorous definitions exist and address issues like sets containing themselves, a formal treatment isn't necessary for the purposes of the book. The primary focus shifts to practical methods for describing sets and their elements.

The text details two primary methods for describing sets. Enumeration involves listing the elements within braces {}; examples provided include the set of binary digits {0, 1} and the set of decimal digits {0, 1, 2, ..., 9}. The use of ellipses (...) is introduced as a way to represent large sets without explicitly listing every element, illustrated with examples like the set of alphabet letters and integers from 1 to 100. The section stresses that while set names are arbitrary, logical choices improve clarity. Set-builder notation, another description method, is exemplified with {x ∈ R | x² − 5x + 6 = 0}, highlighting its ability to define sets based on conditions. The text emphasizes that multiple equivalent ways exist to describe a set, and selecting the most suitable notation depends on the context and personal preference.

This subsection uses the binary number system as an illustrative example to demonstrate set representation and notation. It contrasts the binary and decimal systems, explaining how binary groups units in powers of two (2, 4, 8, etc.), in contrast to the decimal system’s powers of ten. The conversion of the decimal number 23 to its binary equivalent (10111) is presented as a step-by-step process, showcasing how grouping by powers of two works. The introduction of pseudocode is briefly mentioned as a future tool for describing algorithms, hinting at the connection between set theory and computational concepts. A simple algorithm to convert a decimal number to binary is given, showcasing the practical application of the concepts discussed. The concluding question prompts the reader to consider identifying multiples of ten from their binary representations, prompting further thought about set manipulation and number systems.

This subsection initiates the discussion on summation notation by addressing the addition of more than two numbers. It starts by illustrating that adding multiple numbers, such as a1 + a2 + a3 + a4, can be done in different ways due to the associative property of addition, resulting in the same final sum. The concept of a series is introduced as a sum of numbers, with the example (a1 + a2) + (a3 + a4) illustrating an alternative grouping to achieve the same result. The text emphasizes that the associative nature of addition means there's no need for specifying the order of operations when adding multiple numbers, leading seamlessly into the introduction of summation notation as a more efficient way to represent series.

The core of this subsection is the introduction of summation notation (Σ) as a concise method for representing sums. The text explains that while addition is primarily introduced as a binary operation (adding two numbers), it's frequently necessary to represent sums of more than two numbers. The summation notation is presented as a tool to represent such sums compactly. The example of ∑4 i=1 ai is provided, demonstrating how the symbol neatly represents the sum a1 + a2 + a3 + a4. The discussion implicitly contrasts this efficient notation with the more lengthy and less manageable way of writing out the sum explicitly. It sets the stage for further generalizations and applications of this notation in subsequent sections, paving the way for more advanced mathematical concepts relying on efficient notation.

This section introduces fundamental combinatorics concepts through practical examples. A scenario of choosing lunches from five sandwiches and three beverages is used to illustrate the basic counting principle: if there are m ways to do one thing and n ways to do another, there are m*n ways to do both. A tree diagram visually represents all possible lunch combinations (15), demonstrating the method's effectiveness for visualizing possibilities and arriving at a total count. The text emphasizes that while this method is effective for smaller problems, it becomes impractical for larger-scale problems. It sets the stage for exploring more efficient enumeration techniques later in the text.

Moving beyond basic counting, this section introduces more complex combinatorial problems involving subsets and arrangements. The text poses questions that require understanding different counting strategies. For instance, one question asks how many ways a set with 'n' elements can be divided into two non-empty subsets, considering both ordered and unordered scenarios. This type of problem introduces the idea of choosing subsets (combinations) and arranging them (permutations). Another example uses the scenario of a gardener planting shrubs in a row and a circle to illustrate a situation requiring careful consideration of arrangement and constraints. These examples are designed to stimulate thought about various ways of organizing and counting possibilities in scenarios with inherent restrictions. The problems posed serve as a bridge to the introduction of more advanced techniques and formulas for efficiently solving such problems.

Although not explicitly named, the section introduces problems hinting at the principle of inclusion-exclusion. Examples involving counting students enrolled in overlapping courses (non-disjoint sets) are presented. One example involves counting students taking at least one of three computer science courses, where some students are enrolled in multiple courses. The other example deals with disjoint sets (mutually exclusive). These examples implicitly highlight the need for methods beyond simple addition when counting elements in overlapping sets. The complexity of these scenarios implicitly leads to the need for a more systematic approach like the principle of inclusion-exclusion, which will likely be explored in later sections of the textbook. This builds a foundation for handling more intricate counting problems where direct enumeration is not feasible.

To solidify the understanding of counting techniques, the section presents examples based on five-card poker hands from a standard 52-card deck. The problems involve calculating the number of possible hands that satisfy specific conditions, such as containing exactly two aces or forming a full house (three-of-a-kind and a pair). These examples are directly relevant to students interested in probability or game theory. The use of binomial coefficients is suggested for solving these problems, indicating the connection between combinatorics and probability concepts. The reference to using SageMath, an open-source computer algebra system, for calculations showcases a practical application of the mathematical concepts covered. The problems presented serve to solidify the application of counting methods to real-world scenarios, highlighting the practical usefulness of the combinatorics principles discussed.

This section introduces the fundamental concepts of mathematical logic, emphasizing its relevance to understanding arguments and proofs within mathematics and beyond. It highlights the applicability of logical reasoning in various fields, drawing parallels between mathematical arguments and those used in law and medicine. The section also notes the significance of logic in the design of digital computer circuits, showing the close relationship between mathematical logic and practical computing. The text emphasizes that the principles of mathematical logic mirror the logic used in everyday life, using the example of compound sentences and connectives like 'and' and 'or' to illustrate the intuitive basis of logical propositions.

This section presents basic equivalences and implications within logic. It lists fundamental logical laws, many of which mirror algebraic laws, such as the associative law. The concept of duality is introduced as a principle to aid in memorizing logical laws; it states that exchanging specific symbols in a law yields a dual, often representing a second law. The text briefly touches on the use of truth tables for verifying these laws but cautions readers about the subtleties when applying duality to conditional statements and implications. The section serves to lay the groundwork for more complex logical arguments and proofs, providing a solid base of logical equivalences and rules of inference.

The section provides an overview of mathematical systems and the axiomatic method. It explains that a mathematical system is built upon basic assumptions or postulates and uses logical rules to derive theorems. The text uses propositional calculus as a model, showcasing how propositions and logical operators form a mathematical system. While the book won't formally use the axiomatic method throughout, understanding this method enhances comprehension of how mathematical facts are established and organized, providing a unifying framework for the concepts presented. The section also touches on the impracticality of using truth tables for very complex propositions, hinting at the need for alternative, more efficient methods of proof.

This section explores different methods of proof. It begins by noting that while truth tables can theoretically prove anything in propositional calculus, they become computationally infeasible for complex problems. Therefore, it introduces the concept of direct proof, where one starts with the hypothesis (P) and attempts to logically derive the conclusion (C). It also discusses indirect proof (proof by contradiction), where assuming the negation of the conclusion leads to a contradiction, thus proving the original statement. The text stresses that proof-solving, like solving algebraic equations, involves trial and error and working both forward from the hypothesis and backward from the conclusion. The section underscores the importance of active participation in learning proofs, emphasizing that practice is key to developing proficiency. The example of proving the irrationality of the square root of 2 is used to illustrate indirect proof.

This concluding section provides a reflective overview of the key concepts in mathematical proof. It re-emphasizes the significance of understanding the structure of statements (hypothesis and conclusion) in order to effectively create and follow proofs. The section addresses the common apprehension many students have toward proofs, stressing that mastering proofs is attainable with practice and that not every statement encountered requires formal proof. The main objective is to understand and apply core proof techniques. The section’s overall message encourages active engagement and a gradual approach to mastering mathematical proof methods.

This section defines relations in terms of Cartesian products. It begins by using the example of a person's clothing choices (shirts and slacks) to illustrate a Cartesian product A x B, representing all possible combinations. However, it points out that not all combinations might be considered 'related' (e.g., color-coordinated). A relation, therefore, is introduced as a subset of the Cartesian product that consists of only the related pairs. This definition connects the concept of relations to previously established concepts like sets and Cartesian products. This forms the foundation for understanding more specific types of relations which will be elaborated on further in the text.

The section introduces Hasse diagrams as a visual way to represent partially ordered sets (posets). It describes the properties of posets (reflexive, antisymmetric, and transitive) and how these properties are reflected in the structure of a Hasse diagram. The text explains that self-loops (a vertex related to itself) are implicitly assumed and not explicitly drawn. Similarly, the antisymmetric property means connections between distinct elements can only go one way, simplifying the diagram. The transitive property is implicit; for example, if a is related to b and b is related to c, then a is related to c. An example of a Hasse diagram for a pentagonal poset is given, providing a visual representation and illustrating how the properties of a poset are reflected in the visual structure. This visual representation method helps to understand the relationships between elements in a poset more intuitively.

This section introduces functions and their composition. It extends the concept of relations to functions by specifying that for every element in the domain, there is exactly one element in the codomain to which it maps. The concept of functions of two variables is introduced, explaining how a function's domain can be a Cartesian product of two sets, and how the notation changes to reflect this. The text then moves on to discuss the composition of functions, a process akin to performing operations (addition and multiplication) on real numbers or matrices. In this context, the notions of identity and inverse functions under composition are defined analogously to their counterparts in real numbers and matrices.

The section concludes by revisiting the binary search algorithm as a practical example of the concepts discussed. It highlights the recursive nature of the binary search and points out how the recursive step reduces the search space to a sublist of approximately half the original size. The text identifies the base cases where the search either finds the target element or determines that it's not present in the list. The section uses the algorithm to illustrate the importance and practical application of the theoretical concepts covered on relations and functions, showing how these concepts are directly applicable to efficient algorithm design. The concepts of discrete functions and sequences are also briefly reviewed.

This section introduces recurrence relations as a way to define sequences. It explains that while sequences can be defined explicitly (giving a formula for the nth term), they are often more easily defined recursively, stating a relationship between consecutive terms. The text points out that calculating terms directly from a recurrence relation can be time-consuming, motivating the need for finding a closed-form expression for the nth term. The concept of solving a recurrence relation is defined as the process of finding this closed-form expression. The section notes that not all recurrence relations can be solved analytically; however, finite-order linear recurrence relations with constant coefficients are a class that can often be solved, and this class is the focus of much of the chapter.

This section delves into techniques for solving recurrence relations, focusing on finite-order linear recurrence relations with constant coefficients. It observes that closed-form solutions often involve exponential and polynomial expressions. The concept of a characteristic equation is introduced as a method to find the solutions; the roots of the characteristic equation determine the form of the closed-form expression. The text illustrates this with examples of first-order and second-order homogeneous recurrence relations. The importance of initial conditions in uniquely determining the solution is highlighted, and the idea of a general solution (containing arbitrary constants) versus a specific solution (determined by initial conditions) is explained. The text also briefly mentions that the methods extend to cases with complex roots of the characteristic equation, although the representation of the solutions is different.

This section illustrates the applications of recurrence relations with several examples. One example models a savings account with an annual interest rate and varying deposits. The balance after k years is described by a recurrence relation that includes the interest and the deposit. The text introduces the concept of a simple annuity as a special case with constant deposits. Another example shows how small changes in a recurrence relation can drastically alter the form of its closed-form solution. This is illustrated by comparing a recurrence relation with closely spaced characteristic roots and its approximation with a double root, demonstrating how subtle changes can lead to vastly different behaviors. The implications for approximating such relations are also discussed, highlighting the importance of understanding the nature of characteristic roots.

This section applies recurrence relations to the analysis of sorting algorithms. The bubble sort algorithm's worst-case time complexity is modeled using a recurrence relation, which is then solved to obtain a closed-form expression (quadratic function). This demonstrates how recurrence relations provide a tool for analyzing an algorithm's efficiency. The section connects the concept of recurrence relations to the analysis of algorithm efficiency, highlighting the practicality of these methods in computer science. The text mentions the importance of sorted lists for efficient search algorithms like binary search, tying together different algorithmic concepts.

This section introduces generating functions as another tool for solving recurrence relations, particularly highlighting their ability to handle more complex situations. The text briefly introduces the basic properties of generating functions, including identities related to operations on sequences. The section explains that the generating function of the sum of two sequences is the sum of their generating functions, while other identities address scaling and shifting operations. The use of generating functions in counting problems is touched upon with an example where the number of strings of length n satisfying a given condition is determined using generating functions and convolution of sequences. This showcases a powerful technique applicable to advanced counting and combinatorial problems. This acts as an introduction to a more advanced topic that is likely to be further explored in later parts of the book.