Discrete Mathematics for Computing
Format: PDF / Kindle (mobi) / ePub
This new edition includes:
• An expanded section on encryption
• Additional examples of the ways in which theory can be applied to problems in computing
• Many more exercises covering a range of levels, from the basic to the more advanced
This book is ideal for students taking a one-semester introductory course in discrete mathematics - particularly for first year undergraduates studying Computing and Information Systems.
PETER GROSSMAN has worked in both academic and industrial roles as a mathematician and computing professional. As a lecturer in mathematics, he was responsible for coordinating and developing mathematics courses for Computing students. He has also applied his skills in areas as diverse as calculator design, irrigation systems and underground mine layouts. He lives and works in Melbourne, Australia.
logically equivalent to its 53 Discrete mathematics for computing converse, but that it is logically equivalent to its contrapositive. We can confirm that this is the case by constructing a truth table (Table 4.11). Table 4.11 p q p®q q® p Øq Øp Øq ®Øp T T T T F F T T F F T T F F F T T F F T T F F T T T T T The columns for p ® q andØq ®Øp are identical to each other, but they differ from the column for q ® p. Therefore an implication and its contrapositive
Therefore, x2 = (2n + 1)2 = 4n2 + 4n + 1 = 2(2n2 + 2n) + 1 = 2k + 1, where k = 2n2 + 2n. Since k is an integer, 2k + 1 is odd, so x2 is odd. This completes the proof. Example 4.8.4 Prove that, if xy = z2 and x < z then y > z, for any positive numbers x, y and z. Solution A direct proof of this result can be constructed, but we will illustrate another approach here. Suppose the conclusion is not true. In other words, suppose xy = z2 and x < z, but y is not greater than z. Then y £ z. Multiply
B. There are two possibilities for x1: either x 1 Î B or x 1 Ï B. Similarly, either x 2 Î B or x 2 Ï B (2 possibilities), so the total number of possibilities for x1 and x2 is 2 × 2. Continuing in this way with x3, x4, ..., xn, we conclude that the total number of possible subsets is 2 × 2 × ... × 2 (n times), which equals 2n. The technique used in the proof is an application of a result known as the Multiplication principle, which we will meet again in Chapter 9. We noted earlier that the
letters such as x and y), together with the Boolean operations +, × and ¢, and the Boolean constants 0 and 1. We will see in Section 8.3 how the techniques for simplifying Boolean expressions can be applied to the practical problem of designing digital circuits. A Boolean expression can be simplified by applying the laws of Boolean algebra until the simplest possible expression is obtained. Here are some examples showing how this is done. Example 8.2.1 Simplify the Boolean expression x ´(x ´ y
digits from 0 to 9 are shown below: A digit to be displayed is input in its 4-bit binary representation to seven digital circuits, corresponding to the seven segments. The output of each circuit is 0 if the corresponding segment is off for that digit, and 1 if it is on. For each segment, use a Karnaugh map (with ‘don’t care’ entries where appropriate) to obtain a simple Boolean expression for the corresponding digital circuit, and draw a diagram for that circuit. 20 A digital circuit for adding