Computer Mathematics HW 2

MathTextbook.pdf

Home >Mathematics homework help >Computer Mathematics HW 2

Binary, Logic, and More

Applied Math for Computing

Patricia R. Wrean

Department of Mathematics & Statistics

Camosun College wrean@camosun.bc.ca

This work is licensed under the Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/.

http://creativecommons.org/licenses/by-nc-sa/4.0/

Contents

1 Binary, Octal, and Hexadecimal 1 1.1 Decimal and Octal . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Review of the Decimal System . . . . . . . . . . . . . 1 1.1.2 Bases Other Than Ten – How They Work . . . . . . . 3 1.1.3 Octal . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Binary and Hexadecimal . . . . . . . . . . . . . . . . . . . . . 15 1.2.1 Binary . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.2 Hexadecimal . . . . . . . . . . . . . . . . . . . . . . . 17 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3 Converting from Decimal . . . . . . . . . . . . . . . . . . . . 25 1.3.1 Modular Arithmetic: Finding Quotient and Remainder 25 1.3.2 Using Quotient and Remainder to Convert from Dec-

imal Form . . . . . . . . . . . . . . . . . . . . . . . . . 27 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1.4 Converting between Binary, Octal, and Hexadecimal . . . . . 33 1.4.1 Converting Between Binary and Octal . . . . . . . . . 33 1.4.2 Converting Between Binary and Hexadecimal . . . . . 34 1.4.3 Converting Between Octal and Hexadecimal . . . . . . 36 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2 Logic 43 2.1 Introduction to Logic . . . . . . . . . . . . . . . . . . . . . . . 43

2.1.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.2 Operators . . . . . . . . . . . . . . . . . . . . . . . . . 44

iii

iv CONTENTS

2.1.3 Combining Two or More Propositions Using Connectives 45 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.2 Venn Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.1 Venn Diagrams with One Proposition . . . . . . . . . 55 2.2.2 Venn Diagrams with Two Propositions . . . . . . . . . 55 2.2.3 More complications . . . . . . . . . . . . . . . . . . . . 57 2.2.4 Negation and De Morgan’s Laws . . . . . . . . . . . . 59 2.2.5 Venn Diagrams with Three Propositions . . . . . . . . 60 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.3 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . 67 2.3.1 Truth Tables . . . . . . . . . . . . . . . . . . . . . . . 67 2.3.2 Logical Equivalence . . . . . . . . . . . . . . . . . . . 70 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

2.4 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . 83 2.4.1 Logic Circuits . . . . . . . . . . . . . . . . . . . . . . . 83 2.4.2 Gate Representations of Logic Circuits . . . . . . . . . 85 2.4.3 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . 85 2.4.4 Boolean Syntax in Python . . . . . . . . . . . . . . . . 87 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

2.5 Laws of Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 2.5.1 Identity Laws . . . . . . . . . . . . . . . . . . . . . . . 97 2.5.2 Idempotent Laws . . . . . . . . . . . . . . . . . . . . . 98 2.5.3 Complement Laws . . . . . . . . . . . . . . . . . . . . 98 2.5.4 Commutative Laws . . . . . . . . . . . . . . . . . . . . 99 2.5.5 Associative Laws . . . . . . . . . . . . . . . . . . . . . 99 2.5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 99 2.5.7 Simplifying Logical Expressions . . . . . . . . . . . . . 100 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

2.6 More Laws of Logic . . . . . . . . . . . . . . . . . . . . . . . . 107 2.6.1 De Morgan’s Laws . . . . . . . . . . . . . . . . . . . . 107 2.6.2 Distributive Laws . . . . . . . . . . . . . . . . . . . . . 107 2.6.3 Absorption Laws . . . . . . . . . . . . . . . . . . . . . 108 2.6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 108 2.6.5 Simplifying Logical Expressions . . . . . . . . . . . . . 109 2.6.6 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

CONTENTS v

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

2.7 The Conditional . . . . . . . . . . . . . . . . . . . . . . . . . 121 2.7.1 The Conditional Connective . . . . . . . . . . . . . . . 121 2.7.2 The Converse . . . . . . . . . . . . . . . . . . . . . . . 123 2.7.3 The Contrapositive . . . . . . . . . . . . . . . . . . . . 124 2.7.4 The Inverse . . . . . . . . . . . . . . . . . . . . . . . . 124 2.7.5 The “or” form of the conditional . . . . . . . . . . . . 125 2.7.6 De Morgan’s Law and the Contrapositive . . . . . . . 126 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

2.8 The Biconditional . . . . . . . . . . . . . . . . . . . . . . . . 135 2.8.1 The Biconditional Connective . . . . . . . . . . . . . . 135 2.8.2 Programming Applications . . . . . . . . . . . . . . . 137 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

3 Sequences and Series 145 3.1 Introduction to Sequences and Series . . . . . . . . . . . . . . 145

3.1.1 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . 145 3.1.2 Notation for Sequences . . . . . . . . . . . . . . . . . . 146 3.1.3 Counting the Terms in a Sequence . . . . . . . . . . . 147 3.1.4 Defining a Sequence . . . . . . . . . . . . . . . . . . . 149 3.1.5 General Formula . . . . . . . . . . . . . . . . . . . . . 149 3.1.6 Recursive Definition . . . . . . . . . . . . . . . . . . . 151 3.1.7 Fibonacci sequence . . . . . . . . . . . . . . . . . . . . 152 3.1.8 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.1.9 Notation for Series . . . . . . . . . . . . . . . . . . . . 153 3.1.10 Sigma Notation . . . . . . . . . . . . . . . . . . . . . . 153 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

3.2 Arithmetic Sequences and Series . . . . . . . . . . . . . . . . 163 3.2.1 Arithmetic Sequences . . . . . . . . . . . . . . . . . . 163 3.2.2 Recursive Definitions for Arithmetic Sequences . . . . 164 3.2.3 General Formulae for Arithmetic Sequences . . . . . . 164 3.2.4 Arithmetic Series . . . . . . . . . . . . . . . . . . . . . 166 3.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 170 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

3.3 Geometric Sequences and Series . . . . . . . . . . . . . . . . . 177

vi CONTENTS

3.3.1 Geometric Sequences . . . . . . . . . . . . . . . . . . . 177 3.3.2 Recursive Definitions for Geometric Sequences . . . . 178 3.3.3 General Formulae for Geometric Sequences . . . . . . 178 3.3.4 Geometric Series . . . . . . . . . . . . . . . . . . . . . 180 3.3.5 Sum of an Infinite Geometric Series . . . . . . . . . . 181 3.3.6 Repeating Decimals . . . . . . . . . . . . . . . . . . . 184 3.3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 185 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

List of Symbols 193

Index 194

Chapter 1

Binary, Octal, and Hexadecimal

1.1 Decimal and Octal

1.1.1 Review of the Decimal System

Before we look at the numbering systems commonly used by computers, it will likely be helpful to review the workings of the decimal system, the numbering system commonly used by humans. The decimal system (base 10) is based on ten digits, starting from zero, and uses a positional notation, so called because the magnitude of the number depends not only on what digits are used, but also where each digit is located within the number.

For example, if we start counting from zero upwards, we get

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Notice that in base ten, we don’t have a single digit to denote the number ten. Instead, we write a zero in the right column and then write a one in the column to the left. Similarly, when we continue counting up to twenty,

11, 12, 13, 14, 15, 16, 17, 18, 19, 20

once we have written the number nineteen as 19, the next number sets the right digit to zero while incrementing the left column by one to give the

2 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

number 20 (twenty).

This means that for the the decimal number 179, the digit 9 is in the “ones” place, the digit 7 is in the “tens” place, and the digit 1 is in the “hundreds” place, so we can write

179 = 1 × 100 + 7 × 10 + 9 × 1

179 = 1 × 102 + 7 × 101 + 9 × 100,

recalling that 100 = 1.

Example: In the decimal number 386, state which digit is in the

(a) ones place

(b) tens place

Answer:

(a) 6, since it’s the right-most digit

(b) 8

Example: In the decimal number 24680, in what place are the following digits?

(a) 8

(b) 6

(d) 2

(e) 4

Answer:

(a) the tens place

(b) the hundreds place

1.1. DECIMAL AND OCTAL 3

(d) the ten thousands place

(e) the thousands place

1.1.2 Bases Other Than Ten – How They Work

To put a number into a base other than ten, we use the same ideas as before:

� the number of digits available is equal to the base

� there is no single digit which represents the base, so in order to write the base in that system, set the right column to zero and increment the column to the left by one

The best way to understand this is to work through an example, so let us first look at numbers written in base 4. This base is not commonly used in computing, but it is a useful example nonetheless. We will use the same ideas as before:

� there are four digits in total: 0,1,2,3

� there is no single digit which represents the base, so when we want to write the number “four”, set the right column to zero and increment the column to the left by one

To make it clear which base we are using, any numbers written in a base other than ten will have the base as a subscript. So the number three in base 4 is 34.

Let’s contrast counting using base 10 versus base 4 by counting from one to twenty in both bases side-by-side. Notice that the default base is 10, so numbers in the decimal system are written without a subscript, but numbers in base 4 have the base as a subscript.

4 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

base 10 base 4

1 14

2 24

3 34

4 104

5 114

6 124

7 134

8 204

9 214

10 224

base 10 base 4

11 234

12 304

13 314

14 324

15 334

16 1004

17 1014

18 1024

19 1034

20 1104

Another thing to note is what happens when we try to write the decimal number 16 in base 4. The previous number, 15, is written as 334. When you add one to 334, the three in the right-hand column increments to four, but since that is the base, we write a zero and add one to the next column over. Since that is also a three, we set that column to zero and write a one in the next column, so that 16 = 1004.

So, looking at the number 14 in decimal, we can think of it as

14 = 1 × 10 + 4 × 1

but that same number written in base 4 is

324 = 3 × 4 + 2 × 1

and since 12 + 2 is 14, you can see that the two numerical representations are equivalent.

In the same way that we expanded 179 earlier as

179 = 1 × 102 + 7 × 101 + 9 × 100,

we can expand numbers in base 4 in the same way by replacing the base 10

1.1. DECIMAL AND OCTAL 5

with the base 4. So

1004 = 1 × 42 + 0 × 41 + 0 × 40

= 1 × 16 + 0 × 4 + 0 × 1 = 16 + 0 + 0

= 16

and we can conclude that 1004 = 1610, as we discussed.

Similarly,

3024 = 3 × 42 + 0 × 41 + 2 × 40

= 3 × 16 + 0 × 4 + 2 × 1 = 48 + 0 + 2

= 50

and we can conclude that 3024 = 5010.

Example: In the number 1324, state which digit is in the

(a) ones place

(b) fours place

Answer:

(a) 2

(b) 3

Example: The number 12304 can be expanded in base 10 as

12304 = 1 × 43 + 2 × 42 + 3 × 41 + 0 × 40

= 64 + 32 + 12 + 0

= 108

Expand the following numbers into base 10 in a similar fashion. Then perform that calculation to find the number when written in decimal form.

6 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

(a) 234

(b) 1214

(d) 21324

Answer:

(a) 234 = 2 × 41 + 3 × 40 = 8 + 3 = 11

(b) 1214 = 1 × 42 + 2 × 41 + 1 × 40 = 16 + 8 + 1 = 25

(d) 21324 = 2×43+1×42+3×41+2×40 = 128+16+12+2 = 158

1.1.3 Octal

Let us now look at numbers written in base 8, called octal. Octal is a base commonly used in computing. We will use the same ideas as before:

� there are eight digits in total: 0,1,2,3,4,5,6,7

� there is no single digit which represents the base, so when we want to write the number “eight”, set the right column to zero and increment the column to the left by one

So, in base 8, we can only count to seven using single digits:

0, 1, 2, 3, 4, 5, 6, 7

and then the number after that is 10 (in base 8). To make it clear which base we are using, any numbers written in a base other than ten will have the base as a subscript. So the number eight in base 8 is 108.

Let’s contrast counting using base 10 versus base 8 by counting from one to twenty in both bases side-by-side. Again, the numbers in octal will have the base as a subscript.

1.1. DECIMAL AND OCTAL 7

base 10 base 8

1 18

2 28

3 38

4 48

5 58

6 68

7 78

8 108

9 118

10 128

base 10 base 8

11 138

12 148

13 158

14 168

15 178

16 208

17 218

18 228

19 238

20 248

So, looking at the number 14 in decimal, we can think of it as

14 = 1 × 10 + 4 × 1

but that same number written in octal is

168 = 1 × 8 + 6 × 1

and since 8 + 6 is 14, you can see that the two numerical representations are equivalent.

In the same way that we expanded 179 earlier as

179 = 1 × 102 + 7 × 101 + 9 × 100,

we can expand numbers in octal in the same way by replacing the base 10 with the base 8.

2458 = 2 × 82 + 4 × 81 + 5 × 80

= 2 × 64 + 4 × 8 + 5 × 1 = 128 + 32 + 5

= 165

and we can conclude that 2458 = 16510.

8 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Example: In the number 1357248, state which digit is in the

(a) ones place

(b) eights place

(d) 85 place

Answer:

(a) 4

(b) 2

(d) 1

Example: The number 123458 can be expanded in base 10 as 1 × 84 + 2 × 83 + 3 × 82 + 4 × 81 + 5 × 80. Expand the following numbers into base 10 in a similar fashion. Then perform that calculation to find the number when written in decimal form.

(a) 418

(b) 7648

(d) 250738

Answer:

(a) 418 = 4 × 81 + 1 × 80 = 32 + 1 = 33

(b) 7648 = 7 × 82 + 6 × 81 + 4 × 80 = 448 + 48 + 4 = 500

(d) 250738 = 2 × 84 + 5 × 83 + 0 × 82 + 7 × 81 + 3 × 80 = 8192 + 2560 + 0 + 56 + 3 = 10811

Example: Use the technique of the previous example to expand the following numbers with different bases into base 10. Then perform that calculation to find the number when written in decimal form.

(a) 2103

1.1. DECIMAL AND OCTAL 9

(b) 110012

(d) 2667

Answer:

(a) 2103 = 2 × 32 + 1 × 31 + 0 × 30 = 18 + 3 + 0 = 21

(b) 110012 = 1 × 24 + 1 × 23 + 0 × 22 + 0 × 21 + 1 × 20 = 16 + 8 + 0 + 0 + 1 = 25

(d) 2667 = 2 × 72 + 6 × 71 + 6 × 70 = 98 + 42 + 6 = 146

10 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Exercises for Section 1.1

Consider the table below.

base 10 base 2 base 3 base 4 base 5 base 6 base 7 base 8

1 14

2 24

3 34

4 104

5 114

6 124

7 134

8 204

9 214

10 224

11 234

12 304

For the following exercises, complete the specified column in this table. The fourth column has been started as an example.

1. base 2

2. base 3

3. base 4

4. base 5

1.1. DECIMAL AND OCTAL 11

5. base 6

6. base 7

7. base 8

In the number 1234567810, in what place are the following digits?

8. 8

9. 6

10. 5

11. 7

12. 2

13. 1

In the number 12345678, which digit is in the

14. ones place?

15. eights place?

16. sixty-fours place?

17. 85 place?

The number 123458 can be expanded in base 10 as 1 × 84 + 2 × 83 + 3 × 82 + 4×81 + 5×80. Expand the following numbers into base 10 in a similar fashion.

18. 5238

19. 10111102

20. 220134

21. 41305

22. 98710

12 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Convert the following numbers to base 10:

23. 72318

24. 20314

25. 1008

26. 10058

27. 20348

1.1. DECIMAL AND OCTAL 13

Answers to Section 1.1 Exercises

Here is the table for questions 1-7:

base 10 base 2 base 3 base 4 base 5 base 6 base 7 base 8

1 12 13 14 15 16 17 18

2 102 23 24 25 26 27 28

3 112 103 34 35 36 37 38

4 1002 113 104 45 46 47 48

5 1012 123 114 105 56 57 58

6 1102 203 124 115 106 67 68

7 1112 213 134 125 116 107 78

8 10002 223 204 135 126 117 108

9 10012 1003 214 145 136 127 118

10 10102 1013 224 205 146 137 128

11 10112 1023 234 215 156 147 138

12 11002 1103 304 225 206 157 148

13 11012 1113 314 235 216 167 158

14 11102 1123 324 245 226 207 168

15 11112 1203 334 305 236 217 178

16 100002 1213 1004 315 246 227 208

17 100012 1223 1014 325 256 237 218

18 100102 2003 1024 335 306 247 228

19 100112 2013 1034 345 316 257 238

20 101002 2023 1104 405 326 267 248

8. ones

9. hundreds

10. thousands

11. tens

14 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

12. millions

13. ten millions

14. 7

15. 6

16. 5

17. 2

18. 5238 = 5 × 82 + 2 × 81 + 3 × 80

19. 10111102 = 1×26 + 0×25 + 1×24 + 1×23 + 1×22 + 1×21 + 0×20

20. 220134 = 2 × 44 + 2 × 43 + 0 × 42 + 1 × 41 + 3 × 40

21. 41305 = 4 × 53 + 1 × 52 + 3 × 51 + 05 × 50

22. 98710 = 9 × 102 + 8 × 101 + 7 × 100

23. 72318 = 3737

24. 20314 = 141

25. 1008 = 64

26. 10058 = 517

27. 20348 = 1052

1.2. BINARY AND HEXADECIMAL 15

1.2 Binary and Hexadecimal

1.2.1 Binary

Let us now look at base 2, called binary. We will use the same ideas as before:

� there are two digits in total: 0,1

� there is no single digit which represents the base, so when we want to write the number “two”, set the right column to zero and increment the column to the left by one

So, in base 2, we can only count to one using single digits:

0, 1

and then the number after that is 102. To make it clear which base we are using, any numbers written in a base other than ten will have the base as a subscript. Let’s contrast counting using base 10 versus base 2 by counting from one to twenty in both bases side-by-side.

base 10 base 2

1 12

2 103

3 112

4 1002

5 1012

6 1102

7 1112

8 10002

9 10012

10 10102

base 10 base 2

11 10112

12 11002

13 11012

14 11102

15 11112

16 100002

17 100012

18 100102

19 100112

20 101002

So, in order to convert the binary number 1102 to decimal, we can be expand

16 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

it as

1102 = 1 × 22 + 1 × 21 + 0 × 20

= 1 × 4 + 1 × 2 + 0 × 1 = 4 + 2

= 6

and so we can conclude that 1102 = 610. Similarly, the number 101002 can be expanded as

101002 = 1 × 24 + 0 × 23 + 1 × 22 + 0 × 21 + 0 × 20

= 1 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 0 × 1 = 16 + 4

= 20

and 101002 = 2010.

You can see that numbers in binary don’t have to be very large before they get quite difficult to read. That is why we generally write numbers in a computing context in bases that are powers of two, like octal, rather than in binary, even though computers themselves only use ones and zeros. We will see in Section 1.4 how to quickly convert back and forth between binary, octal, and hexadecimal.

Example: In the following binary numbers, in what place is the underlined number?

(a) 111001

(b) 111001

(d) 111001

Answer:

(a) the ones place

(b) the twos place

1.2. BINARY AND HEXADECIMAL 17

(d) the thirty-twos place (the 25s place)

Example: Convert the following numbers to base 10.

(a) 112

(b) 110102

Answer:

(a) 112 = 1 × 21 + 1 × 20

= 1 × 2 + 1 × 1 = 2 + 1

= 3

(b) 110102 = 1 × 24 + 1 × 23 + 0 × 22 + 1 × 21 + 0 × 20

= 1 × 16 + 1 × 8 + 0 × 4 + 1 × 2 + 0 × 1 = 16 + 8 + 0 + 2 + 0

= 26

= 1 × 64 + 0 × 32 + 1 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 × 1 = 64 + 0 + 16 + 0 + 4 + 0 + 1

= 85

1.2.2 Hexadecimal

Another common base used in computing is base 16, called hexadecimal. We will use the same ideas as before:

� there are sixteen digits in total

� there is no single digit which represents the base, so when we want to write the number “sixteen”, set the right column to zero and increment the column to the left by one

The problem arises that in base 10, we have ten digits to use, but we need another six in order to count in hexadecimal. Rather than going with new symbols that might be hard to remember, we use some familiar ones in a

18 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

very recognizable order:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,A,B,C,D,E,F

and then the number after that, corresponding to sixteen, is 1016.

Let’s contrast counting using base 10 versus base 16 by counting from one to twenty in both bases side-by-side.

base 10 base 16

1 116

2 216

3 316

4 416

5 516

6 616

7 716

8 816

9 916

10 A16

base 10 base 16

11 B16

12 C16

13 D16

14 E16

15 F16

16 1016

17 1116

18 1216

19 1316

20 1416

So the number 1416 can be expanded as

1416 = 1 × 161 + 4 × 20

= 1 × 16 + 4 × 1 = 16 + 4

= 20

and 1416 = 2010.

Example: In the number 13579BDF16, in what place are the following digits?

(a) 1

(b) D

1.2. BINARY AND HEXADECIMAL 19

(d) 5

Answer:

(a) the 167s place

(b) the sixteens place

(d) the 165s place

Example: The number 1234E16 can be expanded in base 10 as 1 × 164 + 2 × 163 + 3 × 162 + 4 × 161 + 14 × 160 (recall that in hexadecimal, the digit E16 = 1410). Expand the following numbers into base 10 in a similar fashion.

(a) A116

(b) BB816

(d) 1FFFFD16

Answer:

(a) A116 = 10 × 161 + 1 × 160

(b) BB816 = 11 × 162 + 11 × 161 + 8 × 160

(d) 1FFFFD16 = 1 × 165 + 15 × 164 + 15 × 163 + 15 × 162 + 15 × 161 + 13 × 160

Example: Convert the following numbers to base 10:

(a) 9F016

(b) DE4CD16

Answer:

(a) 9F016 = 9 × 162 + 15 × 161 + 0 × 160

= 2304 + 240

= 2544

20 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

(b) DE4CD16 = 13 × 164 + 14 × 163 + 4 × 162 + 12 × 161 + 13 × 160

= 851968 + 57344 + 1024 + 192 + 13

= 910541

1.2. BINARY AND HEXADECIMAL 21

Exercises for Section 1.2

In the following binary numbers, in what place is the underlined number?

1. 100101011

2. 100101011

3. 100101011

4. 100101011

5. 100101011

The number 111102 can be expanded in base 10 as 1 × 24 + 1 × 23 + 1 × 22 + 1×21 + 0×20. Expand the following numbers into base 10 in a similar fashion.

6. 102

7. 1112

8. 10112

9. 11101112

Convert the following numbers to base 10.

10. 10012

11. 101100012

12. 101012

In the number 1C3D0216, in what place are the following digits?

13. 2

14. 0

15. D

16. 3

17. C

18. 1

22 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

The number 1234516 can be expanded in base 10 as 1 × 164 + 2 × 163 + 3 × 162 + 4 × 161 + 5 × 160. Expand the following numbers into base 10 in a similar fashion.

19. 52316

20. F216

21. 2A01316

22. BEAD16

23. 9C816

Convert the following numbers to base 10.

24. AC88216

25. 100016

26. 2CF16

27. BB816

28. 7AAA0116

29. 65ABF16

1.2. BINARY AND HEXADECIMAL 23

Answers to Section 1.2 Exercises

1. the twos place

2. the ones place

3. the 64s place (26)

4. the 256s place (28)

5. the sixteens (24) place

6. 102 = 1 × 21 + 0 × 20

= 2 + 0

= 2

7. 1112 = 1 × 22 + 1 × 21 + 1 × 20

= 4 + 2 + 1

= 7

8. 10112 = 1 × 23 + 0 × 22 + 1 × 21 + 1 × 20

= 8 + 0 + 2 + 1

= 11

9. 11101112 = 1 × 26 + 1 × 25 + 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20

= 64 + 32 + 16 + 0 + 4 + 2 + 1

= 119

10. 10012 = 9

11. 101100012 = 177

12. 101012 = 21

13. ones

14. sixteens

15. 162

16. 163

17. 164

18. 165

19. 52316 = 5 × 162 + 2 × 161 + 3 × 160

24 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

20. F216 = 15 × 161 + 2 × 160

21. 2A01316 = 2 × 164 + 10 × 163 + 0 × 162 + 1 × 161 + 3 × 160

22. BEAD16 = 11 × 163 + 14 × 162 + 10 × 161 + 13 × 160

23. 9C816 = 9 × 162 + 12 × 161 + 8 × 160

24. AC88216 = 706690

25. 100016 = 4096

26. 2CF16 = 719

27. BB816 = 3000

28. 7AAA0116 = 8038913

29. 65ABF16 = 416447

1.3. CONVERTING FROM DECIMAL 25

1.3 Converting from Decimal

As we’ve seen, converting from a different base back to decimal form can be done by expansion:

3168 = 3 × 82 + 1 × 81 + 6 × 80

= 3 × 64 + 1 × 8 + 6 × 1 = 192 + 8 + 6

= 206

but how do we go back the other way? In order to do that, we first need to look at some modular arithmetic.

1.3.1 Modular Arithmetic: Finding Quotient and Remain- der

Suppose we wish to divide one integer by another. If the second integer doesn’t divide into the first evenly, the result is a real number which we can report either in fraction or decimal form. For example, if we divide 13 by 5, we get

13 ÷ 5 = 13

5 = 2

5 = 2.6

However, if for some reason we wish to stay in the land of integers, we could also report the result by saying that 13 divided by 5 equals 2 plus 3 left over. In this example, the 2 is called the quotient and the 3 is called the remainder, and we can write this calculation in the following form:

13 = 2︸︷︷︸ quotient

×5 + 3︸︷︷︸ remainder

This sort of calculation is very helpful when doing unit conversions.1 For example, if we know that a certain length of time is 54 hours long and we

1The metric system has reduced the need for this type of calculation, but since we are still stuck with practical units that are not multiples of 10 (time given in days, hours, and minutes, for example), doing this type of conversion is still, alas, necessary.

26 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

would prefer to give it in terms of days and hours, then

52 hours = days︸︷︷︸ quotient

×24 + hours︸︷︷︸ remainder

= 2 × 24 + 6

so 52 hours = 2 days plus 6 hours.

But how can we find quotients and remainders with a standard scientific calculator?2 If we take the number 54 and divide it by 24, our calculator will tell us 2.25. There are then two ways to go:

1. Take the integer part of 2.25, which is 2. Then perform the following calculation:

remainder = 54 − 2︸︷︷︸ integer part

×24

= 54 − 48 = 6

2. Alternatively, you can take the decimal part of 2.25, which is 0.25. Multiply this number by 24, the number you are dividing by.

remainder = 0.25︸︷︷︸ decimal part

×24

= 6

Example: Find the quotient and remainder for the following.

(a) 25 ÷ 4

(b) 86 ÷ 3

(d) 91 ÷ 8

2To do this in code, you’d use the build-in functions trunc() and mod(): days = trunc(52,24)

hours = mod(52,24)

where trunc() comes from the word truncate, meaning “to shorten something by cutting off the end” and mod() comes from the mathematical word modulus

1.3. CONVERTING FROM DECIMAL 27

Answer:

(a) 25 ÷ 4 = 6.25 quotient = integer part of 6.25 = 6 remainder = 25 − 6︸︷︷︸

integer part

×4 = 1

or remainder = 0.25︸︷︷︸ decimal part

×4 = 1

(b) quotient = 28, remainder = 2

(d) quotient = 11, remainder = 3

1.3.2 Using Quotient and Remainder to Convert from Dec- imal Form

Now that we know how to find quotients and remainders, let’s look at some examples that convert from a decimal number into octal. Consider the number 3168. We earlier found that 3168 = 20610. Let’s now go back the other way, using repeated division and remainders.

Example: Convert the decimal number 206 to octal.

Answer: The procedure is to divide 206 by the base, which in this case is 8, and write down the quotient and remainder. Then divide the quotient by the base, and write down the new quotient and remainder. As you can see below, we first divide 206 by 8 to get a quotient of 25 with remainder 6. If we then divide 25 by 8, we get quotient 3 with remainder 1. We continue doing this until we get a quotient of zero, as in the table below.

quotient remainder

206 ÷ 8 = 25 6 25 ÷ 8 = 3 1 3 ÷ 8 = 0 3

Notice that if you write down the remainders in reverse order, you get the octal number 3168. Nifty!

Let’s do some more examples using this same procedure.

28 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Example: Convert the decimal number 41 to binary.

Answer: quotient remainder

41 ÷ 2 = 20 1 20 ÷ 2 = 10 0 10 ÷ 2 = 5 0 5 ÷ 2 = 2 1 2 ÷ 2 = 1 0 1 ÷ 2 = 0 1

and reading the remainders from bottom to top gives 4110 = 1010012.

Example: Convert the decimal number 24362 to hexadecimal.

Answer: quotient remainder remainder

(base 10) (base 16)

24362 ÷ 16 = 1522 10 A 1522 ÷ 16 = 95 2 2

95 ÷ 16 = 5 15 F 5 ÷ 16 = 0 5 5

and 2436210 = 5F2A16.

1.3. CONVERTING FROM DECIMAL 29

Exercises for Section 1.3

Convert the following decimal numbers to octal.

1. 23

2. 19

3. 49

4. 84

Convert the following decimal numbers to binary.

5. 7

6. 12

7. 23

8. 30

Convert the following decimal numbers to hexadecimal.

9. 19

10. 25

11. 48

12. 64

Convert the decimal number 27 to the following bases.

13. binary

14. octal

15. hexadecimal

16. base 7

Convert the following decimal numbers to octal.

17. 203

18. 1000

19. 2549

20. 56742

30 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Convert the following decimal numbers to binary.

21. 47

22. 123

23. 80

24. 35

Convert the following decimal numbers to hexadecimal.

25. 189

26. 3245

27. 11331

28. 100

Convert the decimal number 1234 to the following bases.

29. binary

30. octal

31. hexadecimal

32. base 7

1.3. CONVERTING FROM DECIMAL 31

Answers to Section 1.3 Exercises

1. 23 = 278

2. 19 = 238

3. 49 = 618

4. 84 = 1248

5. 7 = 1112

6. 12 = 11002

7. 23 = 101112

8. 30 = 111102

9. 19 = 1316

10. 25 = 1916

11. 48 = 3016

12. 64 = 4016

13. 27 = 110112

14. 27 = 338

15. 27 = 1B16

16. 27 = 367

17. 203 = 3138

18. 1000 = 17508

19. 2549 = 47658

20. 56742 = 1566468

21. 47 = 1011112

22. 123 = 11110112

23. 80 = 10100002

24. 35 = 1000112

25. 189 = BD16

32 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

26. 3245 = CAD16

27. 11331 = 2C4316

28. 100 = 6416

29. 1234 = 100110100102

30. 1234 = 23228

31. 1234 = 4D216

32. 1234 = 34127

1.4. CONVERTING BETWEEN BINARY, OCTAL, AND HEXADECIMAL33

1.4 Converting between Binary, Octal, and Hex- adecimal

1.4.1 Converting Between Binary and Octal

Let’s first count from zero to seven in both octal and binary.

octal binary

08 02

18 12

28 102

38 112

48 1002

58 1012

68 1102

78 1112

If we add leading zeros where necessary to bring all binary numbers to three digits, we can see that

68 = 1102

38 = 0112

48 = 1002

The reason we are doing this is that if we look at a number expressed both in octal and binary, such as 6348 = 1100111002, we can see an interesting pattern. If the binary number is split into groups of three, starting from the right-hand-side,

6348 = 1100111002

= 110 011 1002

6︷︸︸︷ 110

3︷︸︸︷ 011

4︷︸︸︷ 100

then we can see that each group of three digits is equal to the corresponding octal number in that place. Nifty, no?

34 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Let’s use this observation to convert from octal to binary.

Example: Convert the following octal numbers to binary:

(a) 238

(b) 6718

Answer:

(a) So for each digit in the octal number, write the corre- sponding 3-digit binary number. Then put the groups of three all together and, optionally, drop any leading zeros.

238 =

2︷︸︸︷ 010

3︷︸︸︷ 011

= 010 011

= 100112, dropping the leading zero

(b) 6718 =

6︷︸︸︷ 110

7︷︸︸︷ 111

1︷︸︸︷ 001

= 110 111 001

= 1101110012

And we can use a similar technique to convert from binary to octal.

Example: Convert the following binary numbers to octal:

(a) 111102

(b) 10100001002

Answer: First, group the binary digits into threes, starting from the right-hand side. Then rewrite each set of three into the corresponding digit in octal.

(a) 111102 = 11 110 =

3︷︸︸︷ 11

6︷︸︸︷ 110 = 368

(b) 10100001002 = 1 010 000 100 =

1︷︸︸︷ 1

2︷︸︸︷ 010

0︷︸︸︷ 000

4︷︸︸︷ 100 = 12048

1.4.2 Converting Between Binary and Hexadecimal

Similarly, let’s first count from zero to fifteen in both hexadecimal and bi- nary.

1.4. CONVERTING BETWEEN BINARY, OCTAL, AND HEXADECIMAL35

hexadecimal binary

016 02

116 12

216 102

316 112

416 1002

516 1012

616 1102

716 1112

hexadecimal binary

816 10002

916 10012

A16 10102

B16 10112

C16 11002

D16 11012

E16 11102

F16 11112

If we add leading zeros where necessary to bring all binary numbers to four digits, we can see that

916 = 10012

D16 = 11012

216 = 00102

Then if we look at the number 9D216 written in binary, and split the digits into groups of four,

9D216 =

9︷︸︸︷ 1001

D︷︸︸︷ 1101

2︷︸︸︷ 0010

= 1001110100102

Let’s work through more examples.

Example: Convert the following hexadecimal numbers to bi- nary.

(a) 3A16

(b) F02C16

Answer:

(a) 3A16 =

3︷︸︸︷ 0011

A︷︸︸︷ 1010

= 1110102 , dropping the leading zeros

36 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

(b) F02C16 =

F︷︸︸︷ 1111

0︷︸︸︷ 0000

2︷︸︸︷ 0010

C︷︸︸︷ 1100

= 11110000001011002

Example: Convert the following binary numbers to hexadeci- mal.

(a) 111102

(b) 10100011112

Answer: First, group the binary digits into fours, starting from the right-hand side. Then rewrite each set of four into the cor- responding digit in hexadecimal.

(a) 111102 = 1 1110 =

1︷︸︸︷ 1

14︷︸︸︷ 1110 = 1E16

(b) 10100011112 = 10 1000 1111 =

2︷︸︸︷ 10

8︷︸︸︷ 1000

15︷︸︸︷ 1111 = 28F16

1.4.3 Converting Between Octal and Hexadecimal

The fastest way to do this is to convert into binary first, then regroup the binary digits.

Example: Convert the following octal numbers to hexadecimal.

(a) 728

(b) 3338

Answer:

(a) 728 =

7︷︸︸︷ 111

2︷︸︸︷ 010

= 1110102

= 11 1010

3︷︸︸︷ 11

A︷︸︸︷ 1010

= 3A16

1.4. CONVERTING BETWEEN BINARY, OCTAL, AND HEXADECIMAL37

(b) 3338 =

3︷︸︸︷ 011

= 011 011 011

= 110110112

= 1101 1011

D︷︸︸︷ 1101

B︷︸︸︷ 1011

= DB16

Example: Convert the following hexadecimal numbers to octal.

(a) 9A16

(b) 4E5916

Answer:

(a) 9A16 =

9︷︸︸︷ 1001

A︷︸︸︷ 1010

= 100110102

= 10 011 010

2︷︸︸︷ 10

3︷︸︸︷ 011

2︷︸︸︷ 010

= 2328

(b) 4E5916 =

4︷︸︸︷ 0100

E︷︸︸︷ 1110

5︷︸︸︷ 0101

9︷︸︸︷ 1001

= 0100 1110 0101 1001

= 1001110010110012

= 100 111 001 011 001

4︷︸︸︷ 100

7︷︸︸︷ 111

1︷︸︸︷ 001

3︷︸︸︷ 011

1︷︸︸︷ 001

= 471318

38 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Exercises for Section 1.4

Convert the following octal numbers to binary:

1. 308

2. 218

3. 1138

4. 2018

5. 3408

6. 11048

Convert the following hexadecimal numbers to binary:

7. 1316

8. 2B16

9. 1B16

10. 5616

11. 9A16

12. 29A16

Convert the following binary numbers to octal:

13. 11002

14. 101002

15. 1000112

16. 1100102

17. 10011002

18. 11001102

Convert the following binary numbers to hexadecimal:

19. 100112

20. 110102

21. 1010012

1.4. CONVERTING BETWEEN BINARY, OCTAL, AND HEXADECIMAL39

22. 10000002

23. 11000112

24. 11011112

Convert the following octal numbers to hexadecimal:

25. 168

26. 538

27. 738

28. 1428

29. 24578

30. 50028

Convert the following hexadecimal numbers to octal:

31. F16

32. 3016

33. 5F16

34. C216

35. 1D0716

36. A2E616

40 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Answers to Section 1.4 Exercises

1. 308 = 110002

2. 218 = 100012

3. 1138 = 10010112

4. 2018 = 100000012

5. 3408 = 111000002

6. 11048 = 10010001002

7. 1316 = 100112

8. 2B16 = 1010112

9. 1B16 = 110112

10. 5616 = 10101102

11. 9A16 = 100110102

12. 29A16 = 10100110102

13. 11002 = 148

14. 101002 = 248

15. 1000112 = 438

16. 1100102 = 628

17. 10011002 = 1148

18. 11001102 = 1468

19. 100112 = 1316

20. 110102 = 1A16

21. 1010012 = 2916

22. 10000002 = 4016

23. 11000112 = 6316

24. 11011112 = 6F16

25. 168 = E16

1.4. CONVERTING BETWEEN BINARY, OCTAL, AND HEXADECIMAL41

26. 538 = 2B16

27. 738 = 3B16

28. 1428 = 6216

29. 24578 = 52F16

30. 50028 = A0216

31. F16 = 178

32. 3016 = 608

33. 5F16 = 1378

34. C216 = 3028

35. 1D0716 = 164078

36. A2E616 = 1213468

42 CHAPTER 1. BINARY, OCTAL, AND HEXADECIMAL

Chapter 2

Logic

2.1 Introduction to Logic

2.1.1 Propositions

In logic, a proposition is a statement that is either true or false but not both. The statement must also be unambiguous.

Examples of statements that are propositions:

(a) Jon Stewart is the host of the Daily Show on the Comedy Network.

(b) Lego Star Wars is a video game.

A proposition can clearly be false, as in the last statement, while still being a proposition. Examples of statements that are not propositions:

(a) Will you do your homework tonight?

(b) Please pass the butter.

The first is not a proposition because questions cannot be propositions. (Note that the answer to the question may very well be a proposition.) The second one is a command and cannot be said to be either true or false. The third of these examples is not a proposition because, taking the statement on its own, the truth value depends on who “she” is. If, however,

44 CHAPTER 2. LOGIC

that statement were expanded to become, “My roommate’s name is Laura and she was late for class this morning,” then “she” is clearly defined to be Laura and the whole sentence is a proposition.

Taking this idea one step further, we can consider “she” in the third example to behave like a variable, and whether the full statement “she was late” is true or false must depend on what the value of the variable “she” is. Sim- ilarly, in programming it is very common to evaluate the value (true/false) of propositions like “x = 3” or “y < 5” in statements like:

if x = 3 then print ‘‘Hello World’’

provided that, like she/Laura, the value of x has previously been defined.

Since writing propositions out using English sentences is unwieldy, we fre- quently use variables to denote propositions. In symbolic logic, we usually use the letters p, q, r, s, t, etc., for propositions. Each of these variables can then have one of two values, true or false. For example, let p = “Lego Star Wars is a video game” and q = “The number π is exactly equal to 3.” In this instance, the proposition p is true, since there is a video game called Lego Star Wars and the proposition q is false, since π is the irrational number 3.1415926 which does not repeat and does not terminate.

2.1.2 Operators

“not”

The negation of any proposition p is called “not p” and is written as p. You may also see it written using a tilde, ∼p, or using this symbol, ¬p. We will use the p notation because it uses the same convention as we will be using in Boolean algebra, so will be easier to remember.

Note that you should be a little careful when negating sentences. For ex- ample, the negative of “Pat is happy” is not “Pat is unhappy”. There are many other emotions that Pat could have (anger, fear, boredom, etc.). If the first statement is false, then its negation must be true, so between the two you need to cover all possible situations that could arise. It would be safe to say that the negation of “Pat is happy” is that “Pat is not happy”, though.

2.1. INTRODUCTION TO LOGIC 45

Example: Are these two sentences negatives of each other?

� “The number of students in Math 155 is even.”

� “The number of students in Math 155 is odd.”

Answer: Yes, these two are negatives of each other. Since we never have fractions of students in class, the number of students must be either zero or a natural number (in other words, a whole number). Since whole numbers and natural numbers are either even or odd, these two sentences cover all bases and are negatives of each other. (Yes, zero is an even number.)

Example: Are these two sentences negatives of each other?

� “Pat’s Visa account balance is positive.”

� “Pat’s Visa account balance is negative.”

Answer: No, these two statements are not negatives of each other. There is a third possible case, “Pat’s Visa account balance is zero”, since zero is an unsigned number. So the two statements above don’t cover all options. However, if the second statement read “Pat’s Visa account balance is negative or zero”, then the second statement would be the negation of the first one.

2.1.3 Combining Two or More Propositions Using Connec- tives

Propositions may be combined using logical operators called connectives, and the result is called a compound proposition. There are three basic connectives that we will study: “and”, “or”, and “exclusive or”. (Oddly enough, the “not” operator is also called a connective, even though it acts on only one entity rather than joining two.)

“and”

If we connect the propositions p and q with “and” (also called the con- junction), then “p and q” is true if both p and q are true. The symbol for “and” is ∧, so “p and q” is written p∧q.

46 CHAPTER 2. LOGIC

Example: Under what conditions is the statement “Pat does her marking and goes to a movie” true?

Answer: “Pat does her marking and goes to a movie” is true if and only if Pat both does her marking and goes to a movie. If she does one or the other but not both, then the statement “Pat does her marking and goes to a movie” is false. It’s also false if she does neither action.

“or”/“inclusive or”

If we connect the propositions p and q with “or” (also called the inclusive disjunction), then “p or q” is true if either p or q or both are true. The symbol for “or” is ∨, so “p or q” is written p∨q.

Example: Under what conditions is the statement “Pat does her marking or goes to a movie” true?

Answer: “Pat does her marking or goes to a movie” is true if and only if at least one of the conditions is true. If she does her marking, then the compound proposition is true whether or not she goes to a movie, and if she goes to a movie, then the statement is true whether or not she does her marking. To really spell it out, “Pat does her marking or goes to a movie” is true if any of the following are true:

� Pat does her marking and also goes to a movie

� Pat does her marking but does not go to a movie

� Pat does not do her marking but does go to a movie

The only way “Pat does her marking or goes to a movie” is false only when Pat does not do her marking and does not go to a movie.

“XOR”/“exclusive or”

If we connect the propositions p and q with “exclusive or” (also called the exclusive disjunction and frequently written as XOR), then “p XOR q” is true if either p or q but not both are true. The symbol for “exclusive or” is ⊕, so “p XOR q” is written p⊕q.

2.1. INTRODUCTION TO LOGIC 47

“or” vs. “XOR”

In ordinary English, the word “or” can mean either the “inclusive or” or the “exclusive or”, and it is usually up to the reader/listener to decide which one was meant from the context.

Example: Which “or” is meant in the following English sen- tences/phrases?

(a) “Would you like milk or sugar in your tea?”

(b) “Wanted dead or alive”

Answer: For (a), the answer could easily be “milk”, “sugar”, “both”, or “neither”. Since “both” is an option, “inclusive or” is clearly meant.

For (b), the person who is wanted in one of these two states will either be dead or alive but not both, so “exclusive or” is the best interpretation.1

To unambiguously state which “or” is meant in English, the word “or” can be replaced by slightly wordier constructions. The sentence “Would you like milk or sugar or both in your tea?” makes it clear that the “inclusive or” is meant. Replacing “or” by “and/or” has the same result. Using “either or” or the phrase “but not both” are signals that the “exclusive or” is meant.

In general, if a statement is ambiguous, it is best to seek clarification. If that is not possible, then assuming that “or” means the “inclusive or” is generally the safest bet. For the rest of this course, we will use “or” to mean the “inclusive or”.

Example: Under what conditions is the statement “Pat does her marking or goes to a movie but not both” true?

Answer: “Pat does her marking or goes to a movie but not both” is true if and only if only one of the conditions is true. If she does her marking, then she cannot also go to a movie. If she goes to a movie, then she cannot also do her marking. The exclusive or means that she cannot do both and she cannot do neither.

1Unless, of course, there is a zombie apocalypse.

48 CHAPTER 2. LOGIC

Negation of Compound Propositions

To negate a compound proposition, you put the negation bar over the en- tire expression. The negation of p ∧ q is then p∧q. The negation bar then behaves in the same way that brackets do. To determine whether the proposition p∧q is true, you first evaluate p∧q and then negate that value.

Logical Propositions and the Order of Operations

To evaluate the proposition p∨(q∧r), you do exactly as you would expect: evaluate q ∧r and then “or” that value with p. Similarly, p∨q ∧r requires that you evaluate q ∧r, negate the result, then “or” with p.

2.1. INTRODUCTION TO LOGIC 49

Exercises for Section 2.1

State whether the following sentences are propositions.

1. On September 6, 2006, mathematicians proved that 232582657 − 1 was a prime number.

2. Will you marry me?

3. Python is her favourite computing language.

4. What is your favourite computing language?

5. Please bring me a textbook.

6. The University of Victoria is located in Alberta.

Let p be “Rich is seven feet tall” and q be “Susan has brown hair.” Translate the following English sentences into logical notation.

7. Rich is seven feet tall or he is seven feet tall.

8. Either Rich is not seven feet tall or Susan does not have brown hair.

9. It is not true that Rich is seven feet tall or Susan has brown hair.

10. Rich is seven feet tall and Susan has brown hair.

11. Either Rich is seven feet tall or Susan does not have brown hair, but not both.

Which type of “or”, inclusive or exclusive, is meant in the following English sentences?

12. Do you want to sit inside or outside?

13. Have you seen the latest Harry Potter or Transformers movie?

14. I think I’ll get an A or a B in the course.

15. Is that the correct answer or not?

16. We need someone who speaks French or German.

50 CHAPTER 2. LOGIC

Let p be “The moon is made of green cheese” and q be “The earth is made of green cheese.” Translate the following English sentences into logical no- tation.

17. Either the moon is made of green cheese or both the moon and the earth are made of green cheese.

18. The earth is made of green cheese and either the earth or the moon is made of green cheese.

19. Either the earth is made of green cheese while the moon is not, or the moon is made of green cheese.

20. The earth is made of green cheese and either the moon is made of green cheese or the earth is not.

Let p = “Jane did her homework” and q = “Jane went for a jog.” Translate the following logical propositions into English sentences.

21. p∧q

22. p∧q

23. q ∧p

24. q ∨p

25. p (that’s “not(not p)”)

26. q ⊕q

For each pair of sentences below, is the second sentence the negation of the first?

27. Pat owes Peter money. Peter owes Pat money.

28. The number of students in Math 155 is greater than 25. The number of students in Math 155 is less than 25.

29. Pat, the math instructor, is rich. Pat, the math instructor, is poor.

Answer the questions given the following situations. If you cannot answer the question, state whether “the situation is not possible” or “there’s not enough information.”

30. Jane went for a jog and did her homework. Did she go for a jog?

31. Jane went for a jog or did her homework. Did she not do her home- work?

2.1. INTRODUCTION TO LOGIC 51

32. Jane went for a jog. Did she go for a jog and do her homework?

33. Jane did not go for a jog. Did she go for a jog and do her homework?

52 CHAPTER 2. LOGIC

Answers to Section 2.1 Exercises

1. Yes

2. No

3. No

4. No

5. No

6. Yes

7. p∨p

8. From the context, you could go with either p∨q or p⊕q.

9. p∨q

10. p∧q

11. p⊕q

12. exclusive (you usually don’t sit both inside and outside at the same time)

13. inclusive (you could have seen both)

14. exclusive (you can only get one mark for the course, so it’s one or the other but can’t be both)

15. exclusive (it can’t both be the correct answer and not the correct answer at the same time)

16. inclusive (it’s possible that someone speaks both languages)

17. p∨ (p∧q)

18. q ∧ (q ∨p)

19. (q ∧p) ∨p

20. q ∧ (p∨q)

21. Jane did her homework and went for a jog.

22. It is not true that Jane both did her homework and went for a jog.

23. Jane went for a jog and Jane did not do her homework.

2.1. INTRODUCTION TO LOGIC 53

24. Jane did not go for a jog or she didn’t do her homework.

25. It is not true that Jane didn’t do her homework.

26. Either Jane went for a jog or she didn’t, but not both.

27. No. (They could just be even, not owing each other anything.)

28. No. (What if there were exactly 25 students in the class?)

29. No. (Maybe Pat is middle class, so is neither rich nor poor?)

30. Yes.

31. Not enough info. Depends on whether she went for a jog. If she did go for a jog, she could have not done her homework. But if she didn’t go for a jog, she must have done her homework for sure.

32. Not enough info. Depends on whether she did her homework.

33. No.

54 CHAPTER 2. LOGIC

2.2. VENN DIAGRAMS 55

2.2 Venn Diagrams

2.2.1 Venn Diagrams with One Proposition

One way to visual operations on propositions is to use a Venn diagram. Although Venn diagrams are more commonly used with sets, there are many commonalities between the operations on sets and on logical propositions. The Venn diagram for a single logical proposition p is shown below.

In this diagram, the rectangle stands for the universe, while the circle de- notes the logical proposition p. We then shade in regions of the diagram to indicate the regions of interest. For example, when we want to indicate the proposition p, we shade the inside of the circle, as shown in the left diagram. If instead we want to show the proposition p, we shade outside of the circle, as in the diagram to the right.

shading for p shading for p

2.2.2 Venn Diagrams with Two Propositions

Venn diagrams with only one proposition don’t generally contain much in- formation, as it’s usually pretty easy to visualize what p and p mean when you only have the one proposition. Where it gets more interesting is when you have propositions p and q in the same diagram, as you can see in the next diagram.

56 CHAPTER 2. LOGIC

Let’s try doing some shading to represent operations on the propositions p and q. To begin with, let’s examine the shading for p, as shown in the left diagram below. It looks very similar to the shading for the one-proposition diagram, but you should notice that in order to shade in all of p, two regions have been shaded in: the crescent-moon shaped part which represents the part of p that does not overlap with q and the lozenge-shaped part which represents the part of p that does overlap with q. Similarly, q is shown in the diagram below on the right.

shading for p shading for q

Now, if you were to join p and q by an operator such as “and” or “or”, then the way to do it is to consider all four regions of the diagram:

� the left crescent-moon shape belonging to p but not q

� the right crescent-moon shape belonging to q but not p

� the lozenge shape which is the overlap of both p and q

� the remaining region which is neither in p nor q

For example, if you wished to show the Venn diagram for p∨ q, recall that “or” means “one or the other or both”. You would consider the diagrams for p and q above, and any regions that are shaded in either diagram or both diagrams will be shaded in for p ∨ q. So, the parts that would be shaded in the resulting diagram would be the left and right crescent-moon shapes plus the lozenge.

2.2. VENN DIAGRAMS 57

p∨q

To show p∧ q, you need to shade those regions that are shaded in both of the p and q diagrams. This means that you’d shade in the lozenge shaped region, as you can see below.

p∧q

2.2.3 More complications

Suppose you wished to shade in a Venn diagram to show p∧q. A straight- forward approach is to do it by steps:

p q

58 CHAPTER 2. LOGIC

And then to find what happens when we “and” the two diagrams we shade all the regions that are shaded in both of the above diagrams.

p∧q

To find p ∨ q, you’d take the diagrams for p and q, and then shade in the regions that are shaded in for either of the above diagrams.

p∨q

Example: Shade in the Venn diagram corresponding to p∨q.

Answer: Here’s p and q below.

p q

We need to shade in regions that are shaded in for either of the

2.2. VENN DIAGRAMS 59

above diagrams, to get the following.

p∨q

2.2.4 Negation and De Morgan’s Laws

Consider the proposition p∧q. The negation bar behaves like brackets, so we should find p ∧ q first, and then negate it. Let’s start by shading the diagrams for p and q:

shading for p shading for q

To show p∧ q, you need to shade those regions that are shaded in both of the p and q diagrams. This means that you’d shade in the lozenge shaped region, as you can see below.

p∧q

60 CHAPTER 2. LOGIC

Now to get p∧q from p ∧ q, we take the p ∧ q diagram and negate it. Essentially, we “reverse” the diagram by shading in all previously unshaded regions, and not shading in any previous shaded regions, resulting in the following.

p∧q

You can see that we get exactly the same result as when we found p ∨ q. This result, that p ∨ q is equivalent to p∧q, is true for all propositions p and q. You could, if you wish, show also that p∧q is equivalent to p∨q for all p and q. These two statements are called De Morgan’s theorems and we will be revisiting them later.

2.2.5 Venn Diagrams with Three Propositions

Similarly, we can do Venn diagrams with three propositions, as shown in the next diagram.

Notice that there is a circle for each set, and that there are regions where some or all of the sets overlap. To find out how to shade the diagram for combinations of sets such as (p ∨ q) ∧ r, do the shading process in steps. Here’s p, q, and r below.

2.2. VENN DIAGRAMS 61

p q r

Then p∨q gives

p∨q

and intersecting this with proposition r from above gives

(p∨q) ∧r

The diagrams for p ∨ q ∨ r and p ∧ q ∧ r are then given below. (Because the operations are all the same in each expression, I don’t need brackets to show the order of operations for these particular cases.)

62 CHAPTER 2. LOGIC

p∨q ∨r p∧q ∧r

2.2. VENN DIAGRAMS 63

Exercises for Section 2.2

Draw Venn diagrams using two propositions p and q, shading in the appro- priate regions for the following situations.

1. p∨q

2. p∧q

3. p∧q

4. p∧q (this would just be the negation of #2)

5. p∨q

6. p∧ (p∨q)

7. p∨ (p∧q)

Draw Venn diagrams using three propositions: p, q, and r. Shade in the appropriate regions for the following situations.

8. p∨q ∨r

9. (p∧q) ∨r)

10. p∧ (q ∨r)

11. p∨q ∨r

12. p∧q ∧r

13. (p∧q) ∨r

14. q ∧ (p∨r)

64 CHAPTER 2. LOGIC

Answers to Section 2.2 Exercises

2.2. VENN DIAGRAMS 65

10.

66 CHAPTER 2. LOGIC

11.

12.

13.

14.

2.3. LOGICAL EQUIVALENCE 67

2.3 Logical Equivalence

2.3.1 Truth Tables

Truth Tables with Two Variables

Let us consider the propositions p and q. Since they are propositions, p is either true or false and q is also either true or false. This leads us to four possible combinations of p and q:

1. p and q are both false

2. p is false and q is true

3. p is true and q is false

4. p and q are both true

We can combine these possibilities into a table called a truth table. We can add further columns to find out what the value of other compound propositions for each combination of p and q as well. Suppose we wished to find out what the truth table was for p∧ q. Then the table would look like the following.

p q p∧q F F F

F T F

T F F

T T T

For example, when p is false and q is true (the second row, where p = F and q = T), then p∧ q is false because one of them is false (they are not both true).

Similarly, the truth table for p∨q is

p q p∨q F F F

F T T

T F T

T T T

68 CHAPTER 2. LOGIC

And if we like, we can combine the two tables above into a single table like so:

p q p∧q p∨q F F F F

F T F T

T F F T

T T T T

However, we can also abbreviate the table, changing all Fs to 0s and Ts to 1s. We do this so that there is a good correspondence between these truth tables and the tables we will be learning for sets and Boolean algebra. So another equally correct truth table would be:

p q p∧q p∨q 0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 1

Truth Tables with One Variable

What if we were interested in the truth table for p∨p? Since this truth table contains only one variable p rather than two, it will only have two rows since p can either be true or false (and yes, you could omit the second column if you wish).

p p p∨p 0 0 0

1 1 1

Let’s now look at how to write the truth table for p ∧ 1, where 1 means a statement that is always true. (Be careful! The number 1 is a constant, not a variable! It never takes the value of zero.) The table would look like:

2.3. LOGICAL EQUIVALENCE 69

p 1 p∧ 1 0 1 0

1 1 1

We notice that the last column looks like the first, so p ∧ 1 has the same values as p. We say, then, that p ∧ 1 is logically equivalent to p. We’ll talk more about logical equivalence in a bit.

Negations in Truth Tables

To negate a variable, we simply switch the value of each entry in that column from its previous value. So if we were interested in the truth table for p∨p, we’d have to negate p. To do this, we’ll take every entry in the p column and switch all the zeros to ones and the ones to zeros. We’ll then “or” the first and second columns as before.

p p p∨p 0 1 1

1 0 1

Notice, then, that p∨p is always true. I hope that makes a certain amount of sense: the proposition “Pat’s hair is green or Pat’s hair is not green” is a statement that is always true independent of Pat’s hair colour.

To negate an expression, we use the same idea and switch the value of each entry in the column for that expression from its previous value. For example, here is the truth table for p∧ 1:

p 1 p∧ 1 p∧ 1 0 1 0 1

1 1 1 0

You can see that to get the fourth column (which is the negation of the third column), we’ve just switched the values of the expression in the third column.

70 CHAPTER 2. LOGIC

Truth Tables with Three Variables

What would the truth table for three propositions look like? We must have eight rows to display all possibilities for p, q, and r. The truth table for p∧ (q ∨r) would then be

p q r r q ∨r p p∧ (q ∨r) 0 0 0 1 1 1 1

0 0 1 0 0 1 0

0 1 0 1 1 1 1

0 1 1 0 1 1 1

1 0 0 1 1 0 0

1 0 1 0 0 0 0

1 1 0 1 1 0 0

1 1 1 0 1 0 0

It’s important to note that the actual order of the rows doesn’t matter for the truth table to be complete. However, if you write out the table with the rows in a random order, it’s very easy to duplicate one of the previous rows. The duplicate row in and of itself isn’t a mistake, but if you stop your table at the correct total number of rows, the duplicate means that one of the combinations of your variables is missing, which is an error.

Another common mistake is to take a shortcut and start the truth table with one of the columns being, for example, p. This is not correct, since truth tables must always start with unnegated variables.

2.3.2 Logical Equivalence

Two logical expressions are said to be logically equivalent if they have the same values in their columns in the truth table. We saw in our examples above that p∨p was logically equivalent to 1 and p∧1 was logically equivalent to p. The symbol for “logically equivalent to” is ⇔, so p∨p ⇔ 1 and p∧1 ⇔ p.

Example: Is p∧ (q ∨r) logically equivalent to (p∧q) ∨r?

Answer:

2.3. LOGICAL EQUIVALENCE 71

p q r q ∨r p∧ (q ∨r) p∧q (p∧q) ∨r 0 0 0 0 0 0 0

0 0 1 1 0 0 1

0 1 0 1 0 0 0

0 1 1 1 0 0 1

1 0 0 0 0 0 0

1 0 1 1 1 0 1

1 1 0 1 1 1 1

1 1 1 1 1 1 1

No, these two expressions are not logically equivalent because their columns in the truth table, columns 5 and 7, are not iden- tical. This example shows once more that order of operations is important!

Example: Simplify (p∧q) ∨ (p∧q).

Answer:

p q p p∧q p∧q (p∧q) ∨ (p∧q) 0 0 1 0 0 0

0 1 1 0 1 1

1 0 0 0 0 0

1 1 0 1 0 1

Notice that the last column is identical to the column for q. Therefore, (p∧ q) ∨ (p∧ q) is logically equivalent to q, which is the simplified logical expression.

Example: Is p⊕q logically equivalent to (p∧q) ∨ (p∧q)?

Answer:

p q p⊕q p q p∧q p∧q (p∧q) ∨ (p∧q) 0 0 0 1 1 0 0 0

0 1 1 1 0 0 1 1

1 0 1 0 1 1 0 1

1 1 0 0 0 0 0 0

72 CHAPTER 2. LOGIC

Yes, the two expressions are logically equivalent.

2.3. LOGICAL EQUIVALENCE 73

Exercises for Section 2.3

Give the truth tables for the following logical expressions.

1. p∧p

2. p∨ 1

3. p∧q

4. p∨q

5. p⊕q

6. p∨ (p∧q)

7. (p∨q) ∧r

8. p∨q ∨r

9. (p∧q) ∨p∨q

10. (p∨q) ∧ (p∨q)

Are the two expressions logically equivalent?

11. p∧q and p∧q

12. p∨q and p∧q

13. p⊕q and p⊕q

14. p∨ (q ∧r) and (p∨q) ∧r

15. p∨ (p∧q) and p

16. (p∨q) ∨r and p∨ (q ∨r)

17. p⊕q and (p∧q) ∨ (p∧q)

Simplify.

18. p∧p

19. p∨p

20. p∧ 0

21. p⊕p

22. (p⊕q) ∧ (p⊕q)

74 CHAPTER 2. LOGIC

23. p∨ (p∧q)

24. q ∧ (p∨q)

25. (tricksy) p∧ (p∨q)

26. (tricksy) p∨ (p∧q)

2.3. LOGICAL EQUIVALENCE 75

Answers to Section 2.3 Exercises

1. p p p∧p 0 1 0

1 0 0

2. p 1 p∨ 1 0 1 1

1 1 1

3. p q q p∧q 0 0 1 0

0 1 0 0

1 0 1 1

1 1 0 0

4. p q p∨q p∨q 0 0 0 1

0 1 1 0

1 0 1 0

1 1 1 0

5. p q q p⊕q 0 0 1 1

0 1 0 0

1 0 1 0

1 1 0 1

76 CHAPTER 2. LOGIC

6. p q p p∧q p∨ (p∧q) 0 0 1 0 0

0 1 1 1 1

1 0 0 0 1

1 1 0 0 1

7. p q r p∨q (p∨q) ∧r 0 0 0 0 0

0 0 1 0 0

0 1 0 1 0

0 1 1 1 1

1 0 0 1 0

1 0 1 1 1

1 1 0 1 0

1 1 1 1 1

8. p q r r p∨q ∨r 0 0 0 1 1

0 0 1 0 0

0 1 0 1 1

0 1 1 0 1

1 0 0 1 1

1 0 1 0 1

1 1 0 1 1

1 1 1 0 1

2.3. LOGICAL EQUIVALENCE 77

9. p q q p∧q p∨q p∨q (p∧q) ∨p∨q 0 0 1 0 1 0 0

0 1 0 0 0 1 1

1 0 1 0 1 0 0

1 1 0 1 1 0 1

10. p q p q p∨q p∨q (p∨q) ∧ (p∨q) 0 0 1 1 1 1 1

0 1 1 0 1 1 1

1 0 0 1 1 0 0

1 1 0 0 0 1 0

11. p q p∧q p∧q p q p∧q 0 0 0 1 1 1 1

0 1 0 1 1 0 0

1 0 0 1 0 1 0

1 1 1 0 0 0 0

No, because the 4th and 7th columns are not the same.

12. p q p∨q p∨q p q p∧q 0 0 0 1 1 1 1

0 1 1 0 1 0 0

1 0 1 0 0 1 0

1 1 1 0 0 0 0

Yes, because the 4th and 7th columns are identical.

78 CHAPTER 2. LOGIC

13. p q p⊕q p q p⊕q 0 0 0 1 1 0

0 1 1 1 0 1

1 0 1 0 1 1

1 1 0 0 0 0

Yes, because the 3rd and 6th columns are identical.

14. p q r q ∧r p∨ (q ∧r) p∨q (p∨q) ∧r 0 0 0 0 0 0 0

0 0 1 0 0 0 0

0 1 0 0 0 1 0

0 1 1 1 1 1 1

1 0 0 0 1 1 0

1 0 1 0 1 1 1

1 1 0 0 1 1 0

1 1 1 1 1 1 1

No, because the 5th and last columns are not identical.

15. p q p∧q p∨ (p∧q) 0 0 0 0

0 1 0 0

1 0 0 1

1 1 1 1

Yes, because the first and last columns are identical.

2.3. LOGICAL EQUIVALENCE 79

16. p q r p∨q (p∨q) ∨r q ∨r p∨ (q ∨r) 0 0 0 0 0 0 0

0 0 1 0 1 1 1

0 1 0 1 1 1 1

0 1 1 1 1 1 1

1 0 0 1 1 0 1

1 0 1 1 1 1 1

1 1 0 1 1 1 1

1 1 1 1 1 1 1

Yes, because the 5th and last columns are identical.

17. p q p⊕q p q p∧q p∧q (p∧q) ∨ (p∧q) 0 0 0 1 1 0 1 1

0 1 1 1 0 0 0 0

1 0 1 0 1 0 0 0

1 1 0 0 0 1 0 1

No, because the 3rd and last columns are not identical. (But I think you can see that the last expression is the negation of column 3.)

18. p p p∧p 0 0 0

1 1 1

This expression is logically equivalent to p. (You can omit the second column for p if you wish.)

19. p p p∨p 0 1 1

1 0 1

This expression is logically equivalent to 1.

80 CHAPTER 2. LOGIC

20. p 0 p∧ 0 0 0 0

1 0 0

This expression is logically equivalent to 0.

21. p p p⊕p 0 1 1

1 0 1

This expression simplifies to 1.

22. p q p⊕q q p⊕q (p⊕q) ∧ (p⊕q) 0 0 0 1 1 0

0 1 1 0 0 0

1 0 1 1 0 0

1 1 0 0 1 0

This expression simplifies to 0.

23. p q p∧q p∨ (p∧q) 0 0 0 0

0 1 0 0

1 0 0 1

1 1 1 1

This expression is logically equivalent to p.

24. p q p∨q q ∧ (p∨q) 0 0 0 0

0 1 1 1

1 0 1 0

1 1 1 1

2.3. LOGICAL EQUIVALENCE 81

This expression simplifies to q.

25. p q p p∨q p∧ (p∨q) 0 0 1 1 0

0 1 1 1 0

1 0 0 0 0

1 1 0 1 1

This expression is logically equivalent to p∧q.

26. p q p p∧q p∨ (p∧q) 0 0 1 0 0

0 1 1 1 1

1 0 0 0 1

1 1 0 0 1

This expression simplifies to p∨q.

82 CHAPTER 2. LOGIC

2.4. BOOLEAN ALGEBRA 83

2.4 Boolean Algebra

2.4.1 Logic Circuits

A logic circuit or digital circuit is an electrical circuit based on a discrete number of voltage levels, usually two. Two-level circuits usually have one voltage set at zero volts, and the circuit then behaves like a switch, being either on or off. A nice diagram for a switch looks like this:

so that when the switch is open, as if the diagram, no current flows and the switch is off. When the switch closes and there’s a clear path from the left side to the right side, the switch is on.

A digital circuit then makes logical decisions, based on the input to the circuit. The simplest logic circuits are called gates. Physically, a gate is a transistor circuit which takes one or more voltage inputs and gives a single voltage output.

One way to represent the action of a gate is by using a truth table. As usual in a truth table, all possible combinations of the input voltages are given, as well as the output of the gate for each set of inputs. Each input voltage is given a symbol, such as A. When the input signal is off, the value of A is given as 0, and when it’s on, the value of A is 1. This then looks exactly like the truth tables we studied with logical propositions.

“and” gate

The switch representation of an “and” gate looks like this:

It is a series circuit, and both switches must be closed (on) for the circuit to be complete. You can see, then, that this is the same as “A and B”, since “A and B” is true when both A is true and B is true.

Another common representation is the gate representation, which looks like this:

84 CHAPTER 2. LOGIC

In symbols, we write “A and B” as A ·B or just AB.

“or” gate

The switch representation of an “or” gate looks like this:

It is a parallel circuit, and at least one switch must be closed (on) for the circuit to be complete from left to right. You can see, then, that this is the same as “A or B”, since “A or B” is true when either A is true or B is true or both.

Another common representation is the gate representation, which looks like this:

In symbols, we write “A or B” as A + B.

“not” gate

The “not” gate, or inverter, has the diagram

and we write (not-a) as A, just as in set notation. If the negation happens in combination with another gate, we usually omit the triangle and just have a little circle to show the negation, as in the next example.

2.4. BOOLEAN ALGEBRA 85

2.4.2 Gate Representations of Logic Circuits

The gate representation of the logic circuit for AB is then

with the round circle on the input B negating it, so that the two inputs to the “and” gate (the semicircle) are then A and B.

The gate representation for A + B is then

with the “or” gate giving A + B, which the little round circle then negates.

Example: What is the logic circuit expression for the following gate diagram?

Answer: AB

2.4.3 Boolean Algebra

The symbols used for circuits, AB, A + B, and A, are the same symbols as used in Boolean algebra. In this type of algebra, each variable (A, B, etc.) can only have two values, 0 and 1.

Truth tables in Boolean algebra then look very similar to the truth tables that we’ve studied in logic. For example, the truth table showing AB and A + B is:

86 CHAPTER 2. LOGIC

A B AB A + B

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 1

If you have more than one operation happening in a Boolean expression, the order of operations is very similar to the order of operations in arithmetic. For example, if you have the logical expression AB + C, in arithmetic you

multiply before you add. In Boolean algebra, you “and” before you “or”. And, as before, the negation sign behaves in the same way as brackets do.

For example, here is the order in which you would evaluate the following Boolean expressions.

AB + C First evaluate AB, then do the “+C”.

A + BC First evaluate BC, then “or” with A.

AB First evaluate A, then “and” with B.

6 A + B First evaluate A + B, then negate the result. A(B + C) First evaluate the expression in the brackets, then “and” with A.

Truth tables can then be used to demonstrate logical equivalence between Boolean expressions.

Example: Is AB + C logically equivalent to A(B + C)?

Answer:

A B C AB AB + C B + C A(B + C)

0 0 0 0 0 0 0

0 0 1 0 1 1 0

0 1 0 0 0 1 0

0 1 1 0 1 1 0

1 0 0 0 0 0 0

1 0 1 0 1 1 1

1 1 0 1 1 1 1

1 1 1 1 1 1 1

2.4. BOOLEAN ALGEBRA 87

And as the 5th and 7th columns aren’t identical, these two expres- sions aren’t logically equivalent. Once again, order of operations matters.

2.4.4 Boolean Syntax in Python

Python allows you to perform logical operations on Boolean variables in the way that you would expect, as you can see in the accompanying figure.

88 CHAPTER 2. LOGIC

Exercises for Section 2.4

Draw the gate representation for the following logical expressions.

1. A + B

2. A + B

3. AB

4. A B

5. A + B

6. AB + C

7. A(B + C)

8. ABC

9. A B + C

Write the Boolean expression which corresponds to the following gates.

10.

11.

12.

13.

14.

15.

2.4. BOOLEAN ALGEBRA 89

16.

17.

Give the truth tables for the following expressions.

18. AA

19. A + 1

20. AB

21. A + B

22. A + AB

23. (A + B)C

24. A + B + C

Are the two expressions logically equivalent? Justify your answer by giving a truth table.

25. AB and A B

26. A + B and A B

27. A + BC and (A + B)C

28. A + AB and A

29. (A + B) + C and A + (B + C)

Simplify the following logical expressions using truth tables.

30. AA

31. A + A

32. A + 0

33. A + AB

90 CHAPTER 2. LOGIC

34. A(A + B) – this one’s a bit trickier! If you’re stuck, try writing the truth tables for combinations of A and B, like (A + B) for example, to find one that fits.

2.4. BOOLEAN ALGEBRA 91

Answers to Section 2.4 Exercises

10. A B

11. A + B

12. A + B

13. AB

92 CHAPTER 2. LOGIC

14. (A + B) ·C

15. A + BC

16. A + B + C

17. A B C

18.

19.

20.

21.

2.4. BOOLEAN ALGEBRA 93

22.

23.

24.

94 CHAPTER 2. LOGIC

25. No

26. Yes

27.

2.4. BOOLEAN ALGEBRA 95

28.

29.

30.

31.

96 CHAPTER 2. LOGIC

32.

33.

34.

2.5. LAWS OF LOGIC 97

2.5 Laws of Logic

You may have noticed some common patterns running through some of the exercises by now. Let’s examine those patterns in more detail.

First, let us look at the connections between the two sets of symbols we’ve used so far.

Logic p∧q p∨q p F T Boolean Algebra AB A + B A 0 1

In each case, we have symbols for negation, “or”, and “and”. There are also equivalences with False/True for logic, and 0/1 (off/on) for Boolean algebra and logic circuits. Let’s see what else they have in common.

2.5.1 Identity Laws

Examining logical symbols first, let’s fill in the following truth table.

p 0 1 p∧ 0 p∨ 0 p∧ 1 p∨ 1 0 0 1 0 0 0 1

1 0 1 0 1 1 1

From this table, we can see that

p∧ 0 ⇔ 0

p∨ 0 ⇔ p

p∧ 1 ⇔ p p∨ 1 ⇔ 1

These are the identity laws, true for any proposition p. Notice that if we replaced all of the logic symbols in the table with Boolean algebra notation, we’d get

A · 0 = 0 A + 0 = A

A · 1 = A A + 1 = 1

98 CHAPTER 2. LOGIC

2.5.2 Idempotent Laws

Similarly, let’s examine the following truth table.

p p∧p p∨p 0 0 0

1 1 1

From this table, we can see that

p∧p ⇔ p p∨p ⇔ p

These are called the idempotent laws. Notice that if we replaced all of the logic symbols in the table with the equivalent set symbols and also by Boolean algebra notation, we’d get

A ·A = A

A + A = A

2.5.3 Complement Laws

If we wished, we could construct another truth table to show that

p ⇔ p

p∧p ⇔ 0

p∨p ⇔ 1

These are called the complement laws. Notice that if we replaced all of the logic symbols in the table with Boolean algebra notation, we’d get

A = A

A ·A = 0

A + A = 1

2.5. LAWS OF LOGIC 99

2.5.4 Commutative Laws

Similarly,

p∧q ⇔ q ∧p

p∨q ⇔ q ∨p

These are called the commutative laws. Notice that if we replaced all of the logic symbols in the table with Boolean algebra notation, we’d get

AB = BA

A + B = B + A

2.5.5 Associative Laws

Similarly, we could construct another truth table to find that

(p∧q) ∧r ⇔ p∧ (q ∧r)

(p∨q) ∨r ⇔ p∨ (q ∨r)

These are called the associative laws. Notice that if we replaced all of the logic symbols in the table by Boolean algebra notation, we’d get

(AB)C = A(BC)

(A + B) + C = A + (B + C)

2.5.6 Summary

We can then summarize these laws as follows.

100 CHAPTER 2. LOGIC

Law Logic Boolean Algebra

Identity p∧ 1 ⇔ p A · 1 = A p∨ 1 ⇔ 1 A + 1 = 1 p∧ 0 ⇔ 0 A · 0 = 0 p∨ 0 ⇔ p A + 0 = A

Idempotent p∧p ⇔ p AA = A p∨p ⇔ p A + A = A

Complement p ⇔ p A = A p∧p ⇔ 0 AA = 0 p∨p ⇔ 1 A + A = 1

Commutative p∧q ⇔ q ∧p AB = BA p∨q ⇔ q ∨p A + B = B + A

Associative (p∧q) ∧r ⇔ p∧ (q ∧r) (AB)C = A(BC) (p∨q) ∨r ⇔ p∨ (q ∨r) (A + B) + C = A + (B + C)

How, then, can we use these laws?

2.5.7 Simplifying Logical Expressions

We can now use these laws to simplify logical expressions or to prove logical equivalence without resorting to truth tables.

Suppose we wish to simplify (p∧1)∨(q∧0)∨(r∧r). Note that this would require a truth table with 8 rows to show all combinations of p, q, and r. However, to do so using the laws of logic will require fewer steps.

The procedure for simplifying an expression using the laws of logic is to simplify each piece of the expression using a single law, then write the name of the law you are using to one side (writing the name of the law is required, and not optional!). If you are using more than one law, then use a separate line for each law/step.

Simplifying (p∧ 1) ∨ (q ∧ 0) ∨ (r ∧r) would then give

2.5. LAWS OF LOGIC 101

(p∧ 1) ∨ (q ∧ 0) ∨ (r ∧r) p∨ 0 ∨ (r ∧r) identity

(p∨ 0) ∨ (r ∧r) associative p∨ (r ∧r) identity p∨ (r ∧r) commutative p∨ 0 complement p identity

Our conclusion is therefore that (p∧ 1) ∨ (q ∧ 0) ∨ (r ∧r) ⇔ p.

We could also do an alternate solution, using a different order of steps to get our answer.

(p∧ 1) ∨ (q ∧ 0) ∨ (r ∧r) p∨ 0 ∨ (r ∧r) identity p∨ 0 ∨ 0 complement p∨ 0 definition of “or” p identity

And we reach the same conclusion.

Example: Simplify (p∨p) ∧ (p∨p).

Answer:

(p∨p) ∧ (p∨p) 1 ∧ (p∨p) complement

1 ∧ (p) idempotent p identity

(And if you applied the laws correctly but in a different order or combination, you should still come to the same, correct conclu- sion.)

102 CHAPTER 2. LOGIC

Exercises for Section 2.5

1. Which of the following statements is always true?

(a) Darth Vader is both evil and not evil.

(b) Darth Vader is both evil and evil.

(d) Darth Vader is either evil or not evil.

2. Which of the following statements is always false?

(a) The roadrunner has escaped from the wily coyote and he has not escaped from the wily coyote.

(b) The roadrunner has escaped from the wily coyote and he has escaped from the wily coyote.

(d) The roadrunner has escaped from the wily coyote or he has es- caped from the wily coyote.

3. Use a truth table to prove that the two idempotent laws are true.

4. Use a truth table to prove that the four identity laws are true.

Name the law of logic used in the following. Note that the variables have changed, but that the law is still valid.

5. q ∨ 1 ⇔ 1

6. B = B

7. r ∧r ⇔ 0

8. q ∨ 0 ⇔ q

9. B · 1 = B

10. q ∨q ⇔ q

11. AB + AB = 1

12. (p∧q) ∧q ⇔ p∧ (q ∧q)

2.5. LAWS OF LOGIC 103

Simplify the given expression, and state the name of the law you used. You should be able to do these in one step.

13. r ∨ 0

14. C + C

15. r

16. A + A

17. B · 1

Use the laws of logic to simplify the following logical expressions. If you’re completely stuck, try using a truth table instead.

18. (p∧p) ∨ (q ∧q)

19. (p∨p) ∧ (q ∨ 0)

20. p∨ (q ∧q)

Use the laws of logic to simplify the following Boolean expressions. If you’re completely stuck, try using a truth table instead.

21. (A + A)(B + B)

22. B · 0 + AA

23. (B + B)(A + 1)

24. ABB

Prove the following Boolean expressions are equivalent using the laws of logic. If you’re completely stuck, try using a truth table.

25. (AA)B = A(BB)

26. B · 1 + AA = B · 1

27. (A + 0)(B + B) = A

28. AA + B B = A + B

104 CHAPTER 2. LOGIC

Answers to Section 2.5 Exercises

1. (d) is true because in logical symbols, p∨p ⇔ 1.

2. (a) is false because p∧p ⇔ 0.

3. The two idempotent laws are true because the last column in each table is the same as for p.

p p p∨p 0 0 0

1 1 1

p p p∧p 0 0 0

1 1 1

4. The four identity laws are true because the p∧0 column is the same as 0, the p∨0 and p∧1 columns are the same as p, and the p∨1 column is the same as 1.

p 0 1 p∧ 0 p∨ 0 p∧ 1 p∨ 1 0 0 1 0 0 0 1

1 0 1 0 1 1 1

5. identity

6. complement

7. complement

8. identity

9. identity

10. idempotent

11. complement

12. associative

13. r, using the identity law

14. 1, complement

15. r, complement

16. A, idempotent

17. B, identity

2.5. LAWS OF LOGIC 105

Note: for the following questions, there may be several different ways to get to the simplest answer. Also, you may take steps in a different order. If you are concerned about a different solution, please show your instructor. (Also, I haven’t explicitly written out any steps involving either the Commutative or Associative laws.)

18. (p∧p) ∨ (q ∧q) ⇔ p∨ (q ∧q) Idempotent ⇔ p∨ 0 Complement ⇔ p Identity

19. (p∨p) ∧ (q ∨ 0) ⇔ p∧ (q ∨ 0) Idempotent ⇔ p∧q Identity

20. p∨ (q ∧q) ⇔ p∨ 0 Complement ⇔ p Identity

21. (A + A)(B + B) = A(B + B) Idempotent

= A · 1 Complement = A Identity

22. B · 0 + AA = 0 + AA Identity = 0 + A Idempotent

= A Identity

23. (B + B)(A + 1) = 1 · (A + 1) Complement = 1 · 1 Identity = 1 Definition of “and”

24. ABB = A · 0 Complement = 0 Identity

25. (AA)B = A(BB)

0 ·B = A(BB) Complement 0 ·B = A · 0 Complement

0 = A · 0 Identity 0 = 0 Identity

106 CHAPTER 2. LOGIC

26. B · 1 + AA = B · 1 B + AA = B Identity

B + 0 = B Complement

B = B Identity

B = B Complement

27. (A + 0)(B + B) = A

A(B + B) = A Identity

A · 1 = A Complement A = A Identity

28. AA + B B = A + B

A + B = A + B Idempotent

2.6. MORE LAWS OF LOGIC 107

2.6 More Laws of Logic

2.6.1 De Morgan’s Laws

Let’s examine the following truth table.

p q p∧q p∧q p q p∨q 0 0 0 1 1 1 1

0 1 0 1 1 0 1

1 0 0 1 0 1 1

1 1 1 0 0 0 0

From this table, we can see that

p∧q ⇔ p∨q

We can draw a similar table to show that

p∨q ⇔ p∧q

These are called De Morgan’s laws. Notice that if we replaced all of the logic symbols in the table by Boolean algebra notation, we’d get

AB = A + B

A + B = A B

2.6.2 Distributive Laws

Similarly, we could use a truth table to show that

p∧ (q ∨r) ⇔ (p∧q) ∨ (p∧r) p∨ (q ∧r) ⇔ (p∨q) ∧ (p∨r)

These are called the distributive laws. Notice that if we replaced all of the logic symbols in the table with Boolean algebra notation, we’d get

A(B + C) = AB + AC

A + BC = (A + B)(A + C)

108 CHAPTER 2. LOGIC

2.6.3 Absorption Laws

Similarly,

p∧ (p∨q) ⇔ p p∧ (p∨q) ⇔ p∧q

We can draw a similar table to show that

p∨ (p∧q) ⇔ p p∨ (p∧q) ⇔ p∨q

These are called the absorption laws. Notice that if we replaced all of the logic symbols in the table with the equivalent set symbols and also by Boolean algebra notation, we’d get

A(A + B) = A

A(A + B) = AB

A + AB = A

A + AB = A + B

2.6.4 Summary

We can then summarize these laws as follows.

2.6. MORE LAWS OF LOGIC 109

Law Logic Boolean Algebra

Identity p∧ 1 ⇔ p A · 1 = A p∨ 1 ⇔ 1 A + 1 = 1 p∧ 0 ⇔ 0 A · 0 = 0 p∨ 0 ⇔ p A + 0 = A

Idempotent p∧p ⇔ p AA = A p∨p ⇔ p A + A = A

Complement p ⇔ p A = A p∧p ⇔ 0 AA = 0 p∨p ⇔ 1 A + A = 1

Commutative p∧q ⇔ q ∧p AB = BA p∨q ⇔ q ∨p A + B = B + A

Associative (p∧q) ∧r ⇔ p∧ (q ∧r) (AB)C = A(BC) (p∨q) ∨r ⇔ p∨ (q ∨r) (A + B) + C = A + (B + C)

De Morgan’s p∧q ⇔ p∨q AB = A + B p∨q ⇔ p∧q A + B = A B

Distributive p∧q ⇔ p∨q AB = A + B p∨q ⇔ p∧q A + B = A B

Absorption p∧ (p∨q) ⇔ p A(A + B) = A p∧ (p∨q) ⇔ p∧q A(A + B) = AB p∨ (p∧q) ⇔ p A + AB = A

p∨ (p∧q) ⇔ p∨q A + AB = A + B

2.6.5 Simplifying Logical Expressions

The real power of these laws lies in simplifying logical expressions and in proofs. (Remember – one law per line, must write name of law!)

Example: Simplify (p∧q) ∨ (p∧q).

Answer:

110 CHAPTER 2. LOGIC

(p∧q) ∨ (p∧q) p∧ (q ∨q) distributive p∧ 1 complement p identity

Example: Simplify AB(A + B).

Answer:

AB(A + B)

ABA + ABB distributive

AAB + ABB commutative

0 ·B + A · 0 complement 0 + 0 identity

0 definition of “or”

Note that for many of these exercises, there is more than one way to answer. Another equally valid simplification looks like the following.

AB(A + B)

ABAB De Morgan’s

0 complement

This is a much shorter answer, but does require a flash of insight at the (A + B) pattern.

2.6.6 Proofs

Example: Show that A + A B = AB.

Answer:

Let’s examine the left-hand side.

A + A B = AB

A + B = AB absorption

A B = AB De Morgan’s

AB = AB complement

2.6. MORE LAWS OF LOGIC 111

and the fact that the left-hand side is equivalent to the right- hand side completes our proof.

Example: Show that (A + C)(C + AB) = AB + C.

Answer:

Let’s examine the left-hand side.

(A + C)(C + AB) = AB + C

(C + A)(C + AB) = AB + C commutative

C + A(AB) = AB + C distributive

C + (AA)B = AB + C associative

C + AB = AB + C idempotent

AB + C = AB + C commutative

QED. (QED is short for the Latin phrase “quod erat demon- strandum”, which means “it has been demonstrated”.)

112 CHAPTER 2. LOGIC

Exercises for Section 2.6

(Note that these are the same exercises as at the beginning of section 1.5, but with a little twist.) Let p be “Rich is seven feet tall” and q be “Susan has brown hair.” Translate the following English sentences into logical notation. Then, use one of the laws of logic to write an equivalent logical expression. Finally, translate your new expression back into an English sentence.

1. Rich is seven feet tall or he is seven feet tall.

2. Susan has brown hair and she has brown hair.

3. Either Rich is not seven feet tall or Susan does not have brown hair.

4. It is not true that Rich is seven feet tall and Susan has brown hair.

5. It is not true that Rich is seven feet tall or Susan has brown hair.

6. Rich is not seven feet tall and Susan does not have brown hair.

7. Rich is seven feet tall and Susan has brown hair.

8. Susan has brown hair or Rich is seven feet tall.

Name the law of logic used in the following. Note that the variables have changed, but that the law is still valid.

9. q ∨r ⇔ q ∧r

10. B(B + A) = B A

11. (p∧q) ∨ (p∧q) ⇔ p∧ (q ∨q)

12. A + C = AC

13. B + AC = (B + A)(B + C)

14. p∨ (p∧r) ⇔ p∨r

Simplify the given expression, and state the name of the law you used. You should be able to do these in a single step.

15. A + AB

16. AB + AB

17. (A + B)(B + C)

18. q ∨ (q ∧r)

2.6. MORE LAWS OF LOGIC 113

19. C + C

20. A B

For the following exercises, let p be “The moon is made of green cheese” and q be “The earth is made of green cheese.” Translate the following English sentences into logical notation. Then, use one of the laws of logic to write an equivalent logical expression. Finally, translate your new expression back into an English sentence. (Note that these are the same exercises as at the beginning of section 2.1, but with a little twist.)

21. Either the moon is made of green cheese or both the moon and the earth are made of green cheese.

22. The earth is made of green cheese and either the earth or the moon is made of green cheese.

23. Either the earth is made of green cheese while the moon is not, or the moon is made of green cheese.

24. The earth is made of green cheese and either the moon is made of green cheese or the earth is not.

25. Remembering that ⊕ is “exclusive or”, show that A⊕B = AB + AB by using a truth table.

26. The NAND gate (not-AND) has the following truth table. Use DeMor- gan’s laws to find an equivalent Boolean expression using only OR and NOT, and show that your expression has the same truth table.

A B A NAND B = AB

0 0 1

0 1 1

1 0 1

1 1 0

Simplify the following Boolean expressions using the laws of logic. If you’re stuck, try using a truth table.

27. A + C + B + A + B

28. A + B + A + B + A

29. A B

114 CHAPTER 2. LOGIC

30. A + B

31. A + B + AB

32. AB C + ABC

33. ABC + ABC + ABD + ABD

34. AB + A + AB

35. A + BCD + B

36. A B(A + B)

37. (A + B)(A + B)

38. A + AB + BC

39. B(A + C) + ABC

40. (A + B + C)(A + B + C)

Prove that the following Boolean expressions are equivalent by using the laws of logic. If you’re stuck, try using a truth table.

41. BB + AA = A

42. A(B + B) = A

43. ABC + ABC = AB

44. AB + ABC = AB + C

45. A + AB + ABC = A

46. AC + ABC = AC + BC

47. AB(A + B) = AB + AB

48. ABC + D = ABCD

49. A B A C = A B

2.6. MORE LAWS OF LOGIC 115

Answers to Section 2.6 Exercises

1. p∨p ⇔ p. Rich is seven feet tall.

2. q ∧q ⇔ q. Susan has brown hair.

3. p∨q ⇔ p∧q. It is not the case that Rich is seven feet tall and Susan has brown hair.

4. p∧q ⇔ p∨q . Rich is not seven feet tall or Susan does not have brown hair.

5. p∨q ⇔ p ∧ q. Rich is not seven feet tall and Susan does not have brown hair.

6. p∧ q ⇔ p∨q . It is not the case that Rich is seven feet tall or Susan has brown hair.

7. p∧q ⇔ q ∧p. Susan has brown hair and Rich is seven feet tall.

8. q ∨p ⇔ p∨q. Rich is seven feet tall or Susan has brown hair.

9. De Morgan’s

10. absorption

11. distributive

12. De Morgan’s

13. distributive

14. absorption

15. A + B , absorption

16. AB, idempotent

17. B + AC, distributive

18. q, absorption

19. 1, complement

20. A + B , De Morgan’s

21. p∨ (p∧q) ⇔ p . The moon is made of green cheese.

22. q ∧ (q ∨p) ⇔ q. The earth is made of green cheese.

116 CHAPTER 2. LOGIC

23. (q∧p)∨p ⇔ p∨(p∧q) ⇔ p∨q. (note: I’m using the commutative laws to rearrange things) The moon or the earth is made of green cheese.

24. q∧(p∨q) ⇔ q∧p . The earth and the moon are made of green cheese.

25. A B A⊕B A B AB AB AB + AB 0 0 0 1 1 0 0 0

0 1 1 1 0 1 0 1

1 0 1 0 1 0 1 1

1 1 0 0 0 0 0 0

26. By DeMorgan’s law, AB = A + B

A B A NAND B = AB A B A + B

0 0 1 1 1 1

0 1 1 1 0 1

1 0 1 0 1 1

1 1 0 0 0 0

27. 1

28. 1

29. A + B

30. AB

31. 1

32. AB

33. AB

34. A + B

35. A + B

36. 0

37. AB + AB

38. A + B + C

39. B

2.6. MORE LAWS OF LOGIC 117

40. A + B

41.

42.

43.

44.

45.

118 CHAPTER 2. LOGIC

46.

47.

48.

2.6. MORE LAWS OF LOGIC 119

49.

120 CHAPTER 2. LOGIC

2.7. THE CONDITIONAL 121

2.7 The Conditional

2.7.1 The Conditional Connective

Suppose we have two propositions, p and q. Remembering that connectives are operations which join two or more propositions (like “and” and “or”), the conditional connective is

If p, then q.

In symbols, this is written as p → q, and when read aloud, you say “p implies q”. When using the conditional, the first proposition is called the hypothesis and the second is called the conclusion.

There are other ways to state the conditional. “If p, then q” is equivalent to

(a) p implies q

(b) q, if p

(d) q is necessary for p

(e) p only if q

We’ll only be using the “If p, then q” and “p implies q” conventions in this course.

But what does the conditional mean? Suppose you have an insurance con- tract2 which reads:

If your house burns down, then the insurance company will give you $1 000 000.

Let us further suppose your house burns down. Under the contract, the insurance company must give you one million dollars. If it doesn’t, the contract has been violated. But if your house doesn’t burn down and the company doesn’t give you any money, the contract still holds. If your house doesn’t burn down and out of boundless generosity the company give you one million dollars anyway, the contract still holds. The only circumstances under which the contract is violated is when your house does burn down but the company fails to give you one million dollars. This leads to the following truth table.

2My thanks go to my colleague Gilles Cazelais for providing the idea for this example.

122 CHAPTER 2. LOGIC

House burns down? You get $1 000 000? The contract holds

no no yes

no yes yes

yes no no

yes yes yes

To generalize to the propositions p and q,

p q p → q F F T

F T T

T F F

T T T

What does this mean? It means that if p is true and q is false, then the implication p → q cannot also be true. It also means that if p → q is true, then you cannot have p true and q false at the same time.

Let’s look at another example. Suppose that the following conditional is true: “If Barney is a dog, then Barney has four legs.” This means that if the first proposition, “Barney is a dog,” is true, then only one conclusion may be reached, that the second is true and Barney has four legs. However, if p is false and Barney is not a dog, then our conditional doesn’t have anything to say about the number of legs Barney may have. If Barney is not a dog (Barney is a snake, octopus, bug, person, or pond), then Barney may not have four legs. If Barney is not a dog (Barney is a cat, giraffe, woolly mammoth, or table), Barney may have four legs. Our conditional does not deal with what you may conclude when p is false.

Example: Suppose that the statement “If Pat sleeps in, she will be late for class” is true. Answer the following questions.

(a) Pat sleeps in. Is she late for class?

(b) Pat does not sleep in. Is she late for class?

(d) Pat is not late for class. Did she sleep in?

2.7. THE CONDITIONAL 123

Answer:

(a) Yes.

(b) Maybe. (Perhaps she ran into traffic or was eaten by bears. Remember that the conditional has nothing to say when the first proposition is false.)

(d) No.

2.7.2 The Converse

If p → q is true, is it also true that q → p? If p → q is called the conditional, then q → p is called the converse. Let’s use our previous example again, which was “If Barney is a dog, then Barney has four legs.” If this statement is true, is it also true that “If Barney has four legs, then Barney is a dog”?

Clearly this second statement is not also true, since Barney could be a four- legged creature that is not a dog, such as a cat, mouse, grizzly bear, or mountain goat.

Let’s write out the truth table for the conditional and the converse.

p q p → q q → p F F T T

F T T F

T F F T

T T T T

Here’s how to fill in the columns for any logical expression containing the conditional connective (→ ). Let’s call the propositions “first” and “second” so we don’t get confused with p and q. For the conditional first → second, it will be true for all cases except when the first is true and the second is false. So for q → p, look for the row in which q is true (rows 2 and 4) and p is false (1 and 2). Then q is true and p is false only for row 2. Therefore, all rows except for the second get True and the second row gets False. So you can also see from the truth table that the conditional p → q and the converse q → p are not logically equivalent.

124 CHAPTER 2. LOGIC

2.7.3 The Contrapositive

What about the contrapositive, q → p? For our familiar example, that would be asking whether “If Barney is a dog, then Barney has four legs” is equivalent to “If Barney does not have four legs, then Barney is not a dog”. This at least looks a little more promising. Let’s try the truth table, but this time using 1s and 0s instead of True and False.

p q p q p → q q → p 0 0 1 1 1 1

0 1 1 0 1 1

1 0 0 1 0 0

1 1 0 0 1 1

Remember, you’ll fill in all 1s except for the row where the first is true and the second is false. So look for the rows with q true (rows 1 and 3) and p false (rows 3 and 4). So the row with the zero will be the third row. As the last two columns are identical, then the conditional p → q is equivalent to the contrapositive q → p.

Example: Write the contrapositive for the statement, “If today is sunny, Pat will work in the garden.”

Answer: To get the contrapositive, negate each proposition and then reverse the order. So the contrapositive is “If Pat is not working in the garden, then today is not sunny.”

2.7.4 The Inverse

If p → q is the conditional, then the proposition p → q is called the inverse. So if the conditional is “If Barney is a dog, then Barney has four legs”, then the inverse of that would be “If Barney is not a dog, then Barney does not have four legs.” You can see directly from this example that the conditional and the inverse are not equivalent!

Here’s what the truth table looks like. (Remember that the → means that the value is 1 except when the first is true and the second is false.)

2.7. THE CONDITIONAL 125

p q p q p → q p → q 0 0 1 1 1 1

0 1 1 0 1 0

1 0 0 1 0 1

1 1 0 0 1 1

Example: Draw the truth tables for the conditional (p → q), the converse (q → p), the inverse (p → q), and the contrapositive (q → p). Are any of these propositions logically equivalent?

Answer: Here’s the big truth table.

p q p q p → q q → p p → q q → p 0 0 1 1 1 1 1 1

0 1 1 0 1 0 0 1

1 0 0 1 0 1 1 0

1 1 0 0 1 1 1 1

Since the 5th and 8th columns are identical, the conditional (p → q) is logically equivalent to the contrapositive (q → p). Since the 6th and 7th columns are identical, the converse (q → p) is logically equivalent to the inverse (p → q).

2.7.5 The “or” form of the conditional

Can the conditional p → q be rewritten using our basic connectives “and”, “or”, and “not”? Yes, it can, because you can see by the truth table below that p → q is logically equivalent to p∨q.

p q p p∨q p → q 0 0 1 1 1

0 1 1 1 1

1 0 0 0 0

1 1 0 1 1

This means that “If Barney is a dog, then Barney has four legs” is logically equivalent to “Either Barney is not a dog or he has four legs.”

126 CHAPTER 2. LOGIC

Example: Consider the conditional p → q . Is the converse (q → p) logically equivalent to p∨q, p∧q, p∨q, or p∧q?

Answer: Let’s write in the truth table and compare columns.

p q p q q → p p∨q p∧q p∨q p∧q 0 0 1 1 1 1 0 1 0

0 1 1 0 0 1 1 0 0

1 0 0 1 1 0 0 1 1

1 1 0 0 1 1 0 1 0

As can be seen from the table, the columns for q → p and p∨ q are identical, so these two expressions are logically equivalent.

2.7.6 De Morgan’s Law and the Contrapositive

Consider the conditional (p∧q) → r. The contrapositive would be r → p∧q. Applying De Morgan’s Law gives r → (p ∨ q). Notice the change from the “and” in the conditional to the “or” in the modified contrapositive. Forgetting to make that change is an easy trap to fall into.

Example: Consider the conditional “If Pat sleeps in or runs into traffic, she will be late for class.” What is the contrapositive? Use De Morgan’s Law to find your answer.

Answer: The conditional here is

(sleep or traffic) → late

The contrapositive is then

late → sleep or traffic → sleep and traffic

Therefore, the contrapositive is “If Pat is not late for class, then she didn’t sleep in and did not run into traffic.” The “or” changes into an “and” because of De Morgan’s Law.

2.7. THE CONDITIONAL 127

Exercises for Section 2.7

In the following exercises, let p denote “The movie was popular” and q denote “The movie will make a lot of money.” Translate the following propositions into English sentences.

1. p → q

2. p → q

3. q → p

4. q → p

5. p∨q

6. p∧q

In the following exercises, let p denote “Pat eats a burger for dinner” and q denote “Pat is too full for dessert.” Translate the following sentences into logical symbols.

7. If Pat eats a burger for dinner, she will be too full for dessert.

8. If Pat does not eat a burger for dinner, she will not be too full for dessert.

9. If Pat is too full for dessert, then she ate a burger for dinner.

10. If Pat is not too full for dessert, then she did not eat a burger for dinner.

11. If Pat is too full for dessert, then she did not eat a burger for dinner.

12. Pat being too full for dessert implies that she ate a burger for dinner.

13. Pat not being too full for dessert implies that she did not eat a burger for dinner.

14. Pat not eating a burger for dinner implies that she will not be too full for dessert.

15. Pat eating a burger for dinner implies that she will be too full for dessert.

16. Either Pat does not eat a burger for dinner or she will be too full for dessert.

128 CHAPTER 2. LOGIC

17. Either Pat is not too full for dessert or she ate a burger for dinner.

18. Either Pat is too full for dessert or she did not eat a burger for dinner.

19. The following conditional statement is true: If Pat is eaten by bears, she will not finish her marking. Given that, answer the following questions.

(a) Pat is eaten by bears. Did she finish her marking?

(b) Pat is not eaten by bears. Did she finish her marking?

(d) Pat did not finish her marking. Was she eaten by bears?

20. The following conditional statement is true: If Rich is asleep, then he is not playing ping-pong. Given that, answer the following questions.

(a) Rich is playing ping-pong. Is he asleep?

(b) Rich is asleep. Is he playing ping-pong?

(d) Rich is not playing ping-pong. Is he asleep?

Of course, for the previous questions, I chose situations in which you can use common sense to determine the answer. However, the true test of whether you understand the concept is to replace the above propositions by complete nonsense.

21. The following conditional statement is true: If ettercaps are green, then toves are slithy. Given that, answer the following questions.

(a) Toves are slithy. Are ettercaps green?

(b) Toves are not slithy. Are ettercaps green?

(d) Ettercaps are red. Are toves slithy?

22. The following conditional statement is true: If the hare reads the Times Colonist, the tortoise will take out the recycling. Given that, answer the following questions.

(a) The hare does not read the Times Colonist. Will the tortoise take out the

2.7. THE CONDITIONAL 129

(b) recycling?

(d) The tortoise takes out the recycling. Does the hare read the Times Colonist? The tortoise is not taking out the recycling. Does the hare read the Times Colonist?

Given the conditional statement, “If frattling is non-responsive, then the runges must be strunking”, write the corresponding English sentences for the following.

23. The contrapositive (q → p)

24. The converse (q → p)

25. The inverse (p → q)

26. The “or” form (p∨q)

27. Given the conditional statement, “If Bossy is mooing, she must be a cow,” which of the four following statements is the contrapositive (q → p)?

(a) If Bossy is not a cow, she is not mooing.

(b) If Bossy is a cow, then she is mooing.

(d) If Bossy is not mooing, then she must not be a cow.

28. Given the conditional statement, “If Bossy is mooing, she must be a cow,” which of the four following statements is the converse (q → p)?

(a) If Bossy is not a cow, she is not mooing.

(b) If Bossy is a cow, then she is mooing.

(d) If Bossy is not mooing, then she must not be a cow.

29. If the statement “If Bossy is mooing, then she must be a cow,” is a true statement, which of the four following statements is also true?

(a) If Bossy is not a cow, she is not mooing.

(b) If Bossy is a cow, then she is mooing.

130 CHAPTER 2. LOGIC

(d) If Bossy is not mooing, then she must not be a cow.

30. Which of the following is the correct “or” form for the conditional “If Bossy is mooing, then she must be a cow”?

(a) Bossy is a cow or she is not mooing.

(b) Bossy is not a cow or she is not mooing.

(d) Bossy is a cow or she is mooing.

31. If the statement “If Bossy is mooing, then she must be a cow” is a true statement, which of the following cannot occur?

(a) Bossy is mooing and she is a cow.

(b) Bossy is mooing and she is not a cow.

(d) Bossy is not mooing and she is a cow.

32. Consider the following “or” form statement, “Either Superman has a cape or he cannot fly.” Which of the following is the correct form of the corresponding conditional?

(a) If Superman does not have a cape, then he cannot fly.

(b) If Superman has a cape, then he can fly.

(d) If Superman cannot fly, then he doesn’t have a cape.

33. Consider the conditional “If John has the flu or misses the bus, he will be late for work”. Which of the following is the corresponding contrapositive statement (q → p)?

(a) If John is late for work, then he had the flu or missed the bus.

(b) If John is late for work, then he did not have the flu or did not miss the bus.

2.7. THE CONDITIONAL 131

(d) If John is not late for work, then he did not have the flu and did not miss the bus.

34. Consider the conditional “If Rich doesn’t show his work or makes a mistake, then he will not get full credit”. Which of the following is the corresponding contrapositive statement (q → p)?

(a) If Rich received full credit, then he showed his work and did not make a mistake.

(b) If Rich received full credit, then he showed his work or did not make a mistake.

(d) If Rich did not get full credit, then he didn’t show his work or made a mistake.

35. Consider the conditional “If Pat is late and has not called her hus- band, he will be worried”. Which of the following is the corresponding contrapositive statement (q → p)?

(a) If Pat’s husband is not worried, then she is not late and did call him.

(b) If Pat’s husband is not worried, then she is not late or did call him.

(d) If Pat’s husband is not worried, then she is late and did not call him.

36. Consider the conditional “If grunkles are circular, then runges are square and triptrops are blue”. Which of the following is the corre- sponding contrapositive statement (q → p)?

(a) If runges are not square and triptrops are not blue, then grunkles are not circular.

(b) If runges are not square or triptrops are not blue, then grunkles are circular.

132 CHAPTER 2. LOGIC

(d) If runges are not square and triptrops are not blue, then grunkles are circular.

2.7. THE CONDITIONAL 133

Answers to Section 2.7 Exercises

1. If the movie was popular, then it will make a lot of money. (Or: The movie’s popularity implies that it will make a lot of money.)

2. If the movie was not popular, then it will not make a lot of money.

3. If the movie did not make a lot of money, then the movie was not popular.

4. If the movie will make a lot of money, then it is popular.

5. The movie was not popular or it made a lot of money.

6. The movie was popular and it did not make a lot of money.

7. p → q

8. p → q

9. q → p

10. q → p

11. q → p

12. q → p

13. q → p

14. p → q

15. p → q

16. p∨q

17. q ∨p

18. q ∨p

19. a) No b) Maybe c) No d) Maybe

20. a) No b) No c) Maybe d) Maybe

21. a) Maybe b) No c) Yes d) Maybe

22. a) Maybe b) Yes c) Maybe d) No

23. If the runges are not strunking, then the frattling must be responsive.

24. If the runges are strunking, then the frattling is non-responsive.

134 CHAPTER 2. LOGIC

25. If the frattling is responsive, then the runges must not be strunking.

26. The frattling is responsive or the runges are strunking.

27. (a)

28. (b)

29. (a)

30. (a)

31. (b)

32. (a)

33. (d)

34. (a)

35. (b)

36. (c)

2.8. THE BICONDITIONAL 135

2.8 The Biconditional

2.8.1 The Biconditional Connective

Consider the conditional “If you live in Victoria, then you live in BC.” Remembering that the conditional has nothing to say if the first proposition is false, then it is possible for you to not live in Victoria but to still live in BC (Nanaimo, Vancouver, etc.). It is also possible for you to not live in Victoria and also not live in BC (Calgary, AB or Toronto, ON).

Let’s now consider the conditional “If the temperature outside is below 0◦C, then it is freezing outside.” If I were to use this sentence in everyday English, I probably mean “If the temperature outside is below 0◦C, then it is freezing outside AND if the temperature outside is not below 0◦C, then it’s not freezing outside.” So we could probably do with a new proposition that means “If p, then q and if p, then q.” This connective is called the biconditional, p ↔ q.

The truth table for the biconditional, then, is

p q p ↔ q 0 0 1

0 1 0

1 0 0

1 1 1

So if p and q have the same value, then the biconditional is true and otherwise it’s false. (In a sense, then, it’s the negation of “exclusive or”, p⊕q.) There are a number of ways to specify the biconditional in English:

(a) If and only if p, then q.

(b) p if and only if q.

(d) If p, then q, and if p, then q.

We’ll mostly be using the first construction, using “if and only if”.

Example: Draw the truth tables for p ↔ q and (p → q) ∧ (q → p). Are they logically equivalent? Also, are p ↔ q and (p → q) ∧ (p → q) logically equivalent?

136 CHAPTER 2. LOGIC

Answer: Let’s draw a big truth table:

p q p↔q p q p→q q→p p→q (p→q)∧(q→p) (p→q)∧(p→q) 0 0 1 1 1 1 1 1 1 1

0 1 0 1 0 1 0 0 0 0

1 0 0 0 1 0 1 1 0 0

1 1 1 0 0 1 1 1 1 1

So by looking at the relevant columns, we can see that all three logical expressions are equivalent. So (“if p, then q” AND “if q, then p”) is equivalent to the biconditional.3

Example: Consider the following conditional statements.

(a) “If two lines are perpendicular, then the angle between them is 90◦.”

(b) “If a polygon is a right triangle, then it has three sides.”

Which of these sentences would still be true if it were written in the form of the biconditional?

Answer:

(a) would still be true since if two lines are not perpendicular, then the angle between them is not 90◦.

(b) would not be true, since there are many triangles that aren’t right triangles.

Example: The following biconditional statement is true: “If and only if Pat finishes her marking, she will not feel guilty.” Given that, answer the following questions.

(a) Pat feels guilty. Did she finish her marking?

(b) Pat does not feel guilty. Did she finish her marking?

(d) Pat did not finish her marking. Does she feel guilty?

3We could have also noted that since the converse (q → p) is logically equivalent to the inverse (p → q), then the last two columns should be identical to each other.

2.8. THE BICONDITIONAL 137

Answer: Let p = “Pat finishes her marking” and q = “Pat does not feel guilty.”

(a) So q is false, so p must also be false (the biconditional re- quires that p and q have the same values). So Pat did not finish her marking and the answer is “No.”

(b) q is true so p is true. Yes.

(d) p is false so q is false. And feeling “not-not guilty” is just “guilty”, so Yes.

2.8.2 Programming Applications

The if-then construction is very common in programming. In pseudocode, it usually takes the form

if x > 3 then print ‘‘Hello World’’

When you are debugging, it is tempting to think that this particular code fragment behaves more like the biconditional: if “Hello World” was output, was x > 3? It’s tempting to think so, but what if “Hello World” was printed because of some other command? What then can we conclude about x?

Let’s examine this in more detail. Recall that if p → q is true and q is true, we cannot conclude anything about p. Now consider the following piece of pseudocode.

x = 4

y = 0

if x > 3 then y = 5

print ‘‘y = ’’, y

The output will be “y = 5”.

But, won’t the following pseudocode have the same output?

x = 2

y = 5

138 CHAPTER 2. LOGIC

if x > 3 then y = 5

print ‘‘y = ‘’, y

It will. The conditional statement did not change the value of y, but the value was set to 5 initially, so the output is still be “y = 5”. Once again, knowing that q is true does not allow us to conclude anything about p from the conditional p → q. However, if the output was “y = 4” or any other value not equal to 5, we can draw the conclusion that x was not greater than 3. If p → q is true and q is false, we know with certainty that p is false also.

The if-then-else construction behaves in a similar fashion. Consider the following code fragment:

if x > 3 then y = 5

else z = 7

print ‘‘y = ‘’, y, ‘‘z = ’’, z

Only if the output tells you that y 6= 5 or z 6= 7 will you know with certainty something about x.

For special cases, the if-then-else construction can yield more information. Consider the following.

if x > 3 then y = 5

else y = 7

print ‘‘y = ’’, y

Since this piece of pseudocode assigns different values (5 or 7) to the same variable y, finding out the resulting value of y will determine whether x was greater than 3. In this special case, the if-then behaves like the biconditional: if y = 5 then you know that x > 3, and if y 6= 5, then x ≤ 3.

2.8. THE BICONDITIONAL 139

Exercises for Section 2.8

Write out the truth tables for the following logical expressions. (You might want to do it as just one or two really big tables.)

1. p → q

2. p → q

3. q → p

4. q → p

5. p∨q

6. p∧q

7. p ↔ q

8. p ↔ q

9. p⊕q

10. p∨q

11. p⊕q

12. (p → q) ∧ (q → p)

13. (p → q) ∨ (q → p)

14. (p → q) ∧ (p → q)

15. (p → q) ∨ (p → q)

16. Looking at your results questions 1-15, which expressions are logically equivalent to p ↔ q?

17. Looking at your results for questions 1-15, which expressions are logi- cally equivalent to p → q?

18. Looking at your results for questions 1-15, which expressions are logi- cally equivalent to q → p?

Consider the following conditional statements. I hope you agree that they all make a certain amount of sense. However, if they were rewritten as biconditional statements, would they continue to make sense? Answer True or False.

140 CHAPTER 2. LOGIC

19. If Barney is a dog, then he has four legs.

20. If Rich is asleep, then he is not playing ping-pong.

21. If Alycia gets 90% or better as her final mark, she will get an A+.

22. If Bossy is mooing, then she is a cow.

23. If Pat sleeps in, she is late for class.

24. If Frank does not pay his bill on time, he will be charged a late charge.

25. If Susan bought her computer less than a year ago, her warranty is still in effect.

26. If Raymond eats a burger for dinner, he will be too full for dessert.

In the following exercises, let p denote “Pat eats a burger for dinner” and let q denote “Pat is too full for dessert.” Translate the following sentences into logical symbols.

27. If and only if Pat eats a burger for dinner, she will be too full for dessert.

28. Pat will not be too full for dessert if and only if she did not eat a burger for dinner.

29. If Pat eats a burger for dinner, then she will be too full for dessert.

30. If Pat is not too full for dessert, then she did not eat a burger for dinner.

Are the following two sentences biconditional statements? (In other words, could you replace them by an equivalent “if and only if” construction?)

31. If Frank does not pay his bill on time, then he will be charged a late charge, and if he does pay his bill on time, he will not be charged a late charge.

32. If Alycia gets 90% or better as her final mark, she will get an A+, and if she gets an A+, then she got 90% or better as her final mark.

33. The following conditional statement is true: If and only if Pat is eaten by bears, she will not finish her marking. Given that, answer the following questions.

(a) Pat is eaten by bears. Did she finish her marking?

(b) Pat is not eaten by bears. Did she finish her marking?

2.8. THE BICONDITIONAL 141

(d) Pat did not finish her marking. Was she eaten by bears?

34. The following conditional statement is true: If Rich is asleep, then he is not playing ping-pong and vice versa. Given that, answer the following questions.

(a) Rich is playing ping-pong. Is he asleep?

(b) Rich is asleep. Is he playing ping-pong?

(d) Rich is not playing ping-pong. Is he asleep?

35. The following conditional statement is true: Ettercaps are green if and only if toves are slithy. Given that, answer the following questions.

(a) Toves are slithy. Are ettercaps green?

(b) Toves are not slithy. Are ettercaps green?

(d) Ettercaps are red. Are toves slithy?

36. If the statement “If and only if Superman has a cape, then he can fly” is a true statement, which of the following cannot occur? (You may choose more than one.)

(a) Superman has a cape and he can fly.

(b) Superman has a cape and he cannot fly.

(d) Superman does not have a cape and can fly.

142 CHAPTER 2. LOGIC

Answers to Section 2.8 Exercises

Here are the truth tables for the expressions in questions 1 through 15.

p q p q p → q p → q q → p q → p p∨q p∧q 0 0 1 1 1 1 1 1 1 0

0 1 1 0 1 0 1 0 1 0

1 0 0 1 0 1 0 1 0 1

1 1 0 0 1 1 1 1 1 0

p q p q p ↔ q p ↔ q p⊕q p∨q p⊕q 0 0 1 1 1 1 0 1 0

0 1 1 0 0 0 1 0 1

1 0 0 1 0 0 1 1 1

1 1 0 0 1 1 0 1 0

p q (p → q)∧(q → p) (p → q)∨(q → p) (p → q)∧(p → q) (p → q)∨(p → q) 0 0 1 1 1 1

0 1 0 1 0 1

1 0 0 1 0 1

1 1 1 1 1 1

16. By comparing columns, the following expressions are logically equiva- lent to p ↔ q:

(a) p ↔ q

(b) (p → q) ∧ (q → p)

17. By comparing columns, the following expressions are logically equiva- lent to p → q:

(a) q → p

(b) p∨q

2.8. THE BICONDITIONAL 143

18. By comparing columns, the following expressions are logically equiva- lent to q → p:

(a) p → q

(b) p∨q

19. False

20. False

21. True

22. False

23. False

24. True

25. True

26. False

27. p ↔ q

28. q ↔ p

29. p → q

30. q → p

31. Yes

32. Yes

33. a) No b) Yes c) No d) Yes

34. a) No b) No c) Yes d) Yes

35. a) Yes b) No c) Yes d) No

36. b) and d)

144 CHAPTER 2. LOGIC

Chapter 3

Sequences and Series

3.1 Introduction to Sequences and Series

3.1.1 Sequences

Let’s start out with the definition of a sequence:

sequence: an ordered list of numbers, often with a pattern

In a sequence, the number of terms can be finite or infinite. If a sequence is finite, then either the last term or the total number of terms must be specified so that it’s clear where the sequence stops.

Example: Which of the following sequences are infinite? Which are finite?

(a) 7, 11, 15, 19, . . .

(b) 1, 4, 9, 16, 25, 36, . . . 100

4 , 1

8 , 1

16 , ... 1

256

Answer: (b) and (c) are finite, because their last terms are given. (a), however, goes on forever so is infinite.

To begin with, let’s examine some sequences in detail. We will begin by looking at sequences that do have a pattern.

Example: What is the pattern for the following sequences? What is the next term for each sequence?

145

146 CHAPTER 3. SEQUENCES AND SERIES

(a) 7, 11, 15, 19, . . .

(b) 1, 4, 9, 16, 25, 36, . . . 100

4 , 1

8 , 1

16 , ... 1

256

(d) 3,−6, 12,−24, . . .

(e) 3,−6,−15,−24, . . .

Answer:

(a) The pattern is that you add 4 to the previous term to get the next term. The next term is then 23.

(b) The pattern is that if you say that“1” is the first term and “4” is the second term, then n2 will be the nth term. So the next term after 36 is 49.

(c) The pattern is to divide each term by two (or multiply by one-half) to get the next term. So the term after 1/16 will be 1/32.

(d) The pattern is to multiply each term by −2 to get the next term. The next term is then 48.

(e) The pattern is to subtract 9 from the previous term, so the next one is −33.

Note that in this previous example, the last two sequences looked very sim- ilar for three of their first four terms. However, the third term is different so the pattern for the two sequences is not the same and subsequent terms could look very different.

3.1.2 Notation for Sequences

For each term in a sequence, we will use the notation of a lower-case a followed by a subscript which is called the index. So, depending on what we want our starting index to be, our sequence can be written as

a0,a1,a2 . . . ,an

a1,a2,a3, . . . ,an

3.1. INTRODUCTION TO SEQUENCES AND SERIES 147

or even

a5,a6,a7, . . . ,an

In this textbook, we will use the convention that the starting index is m, so our sequences can be written as

am,am+1,am+2, . . . ,an

Because we are examining sequences from a computing perspective, we should be aware that computing languages don’t use a single convention: many start counting at m = 0, while others start at m = 1.1 In this text- book we will simply specify the start value of our index for each sequence instead of using any one convention.

3.1.3 Counting the Terms in a Sequence

Since it’s possible to start the index for a sequence at any value, we need to be careful when determining k, the total number of terms in a sequence. The rule is:

#terms = last − first + 1

and since we are using the convention that m is the first index and n is the final index (or, alternatively, the index of interest), then

k = n−m + 1

Starting with Index of One

Let us consider a sequence that starts with an index of one:

a1,a2,a3, . . . ,an

This convention has the advantage that if you label each term as follows:

first︷︸︸︷ a1 ,

second︷︸︸︷ a2 ,

third︷︸︸︷ a3 ,

fourth︷︸︸︷ a4 ,

fifth︷︸︸︷ a5 , . . . ,

final︷︸︸︷ an

1Examples of languages that have a starting index of zero are Python and the C family (C, C++, C#). Languages which start their index values at one include Fortran, Smalltalk, and Lua. There are also languages such as Algol which start at a user-defined value.

148 CHAPTER 3. SEQUENCES AND SERIES

you can see that the term a5 has an index n = 5 and is also the fifth term, so the number of the term (fifth) and the index (5) are consistent with each other. This makes it more difficult to make a counting error. Also, the total number of terms in the sequence a1,a2,a3, . . . ,an is given by k = n−1 + 1, so k = n and is consistent with what we would expect.2

Starting with Index of Zero

However, let us now consider sequences that start with zero:

a0,a1,a2,a3, . . . ,an

Numbering the terms, we find that

first︷︸︸︷ a0 ,

second︷︸︸︷ a1 ,

third︷︸︸︷ a2 ,

fourth︷︸︸︷ a3 ,

fifth︷︸︸︷ a4 , . . . ,

final︷︸︸︷ an

and a5 is no longer the fifth term. In fact, a5 is the sixth term, which is why it is common in programming to separate the “count” of a term (first, second, third, etc.) from the index value (0 for a0, etc.).

Also, the total number of terms in a0,a1,a2,a3, . . . ,an is given by

k = n−m + 1 = n− 0 + 1 = n + 1

so k, the “count” of the term is no longer equal to n, the index of the final term. So be warned: if you are not careful with this convention, you are likely to make a type of mistake which programmers commonly call an “off-by-one” error.

Starting with Index of Two or More

As we have seen, a5 is only the fifth term in sequences that start with an index of one. If the sequence starts at some other value, then a5 could even be the first or second term. This does lead to a small problem in that the

2In mathematics, it is most common to start counting with a1 being the first term. Programming languages primarily designed for mathematics, such as Matlab, usually start with an index of one.

3.1. INTRODUCTION TO SEQUENCES AND SERIES 149

term an is commonly called the the n th term in a sequence, which is only

true for a starting index of one.3

3.1.4 Defining a Sequence

There are three ways to define a sequence:

1. List all of the terms, or enough terms to set up the pattern. If the sequence is finite, then either the final term or the total number of terms must be given.

2. Give a general formula for the nth term.

3. Give a recursive formula for the nth term.

We have already looked at sequences defined using the first method in the examples given earlier. Let’s now examine the two types of formula, general and recursive.

3.1.5 General Formula

A general formula is a formula that gives an as a function of n only. What this means is that the only variable on the right-hand-side of the general formula is the variable n, and all other values in the equations are constants.

Let’s look at the following examples to examine some sequences defined in this way.

Example: Give the first four terms of the sequence given by the general formula an = 4n + 7 for n ≥ 0.

Answer:

3This leads to the awkward convention of calling a0 the zeroth term.

150 CHAPTER 3. SEQUENCES AND SERIES

an = 4n + 7, so

a0 = 4 × 0 + 7 = 7 a1 = 4 × 1 + 7 = 11 a2 = 4 × 2 + 7 = 15 a3 = 4 × 3 + 7 = 19

The first four terms are then 7, 11, 15, and 19. This is the same sequence that was given as part (a) in the first example of this section.

Example: Give all terms of the sequence given by the formula an =

( 1 3

)n for 1 ≤ n ≤ 5.

Answer: This is a finite sequence, since restrictions have been placed on the values of n. The terms are then:

a1 =

( 1

)1 =

a2 =

( 1

)2 =

a3 =

( 1

)3 =

a4 =

( 1

)4 =

a5 =

( 1

)5 =

243

You can see from the previous examples that the general formula allows you to calculate an for any value of n. The very useful thing about the general formula is that you don’t need to know the previous term to cal- culate a particular term. For instance, if you want to know a50 for the sequence 7, 11, 15, 19, . . ., you can determine that the pattern is to add 4 to the previous term to get the next term. However, to get a50, you’d have to calculatea49 first, but a49 requires a48, and so on. But if you instead use the formula an = 4n + 7 for n ≥ 0, which gives the same sequence, then a50 is

3.1. INTRODUCTION TO SEQUENCES AND SERIES 151

just

an = 4n + 7

a50 = 4 · 50 + 3 = 207

and there’s no need to calculate preceding terms. Handy!4

3.1.6 Recursive Definition

A recursive formula gives a formula for the next term in terms of the previous one. For example, in our old friend 7, 11, 15, 19, . . . , the next term is found by adding 4 to the previous term: an = an−1 +4. However, that’s not enough information to uniquely define the series because you don’t know where to start. A complete definition must include the first term also. Therefore, the recursive definition for our old friend 7, 11, 15, 19, . . . would be{

a0 = 7

an = an−1 + 4 for n ≥ 1

Recursive definitions, then, must specify the first term (or terms, when necessary) and also the rule which allows you to calculate the next term from the previous term or terms.

Example: Calculate the first four terms of the sequence given by {

a0 = 3

an = (an−1 − 1)2 + 10 for n ≥ 1

Answer: The first term is already given, a0 = 3. Then

a1 = (3 − 1)2 + 10 = 22 + 10 = 14 a2 = (14 − 1)2 + 10 = 132 + 10 = 179 a3 = (179 − 1)2 + 10 = 1782 + 10 = 31694

So the first four terms are 3, 14, 179, 31694.

Example: Give a recursive formula for the sequence 2, 6, 18, 54, . . .

4It’s important to note, however, that a50 is not the fiftieth term. Because we are starting our index from zero, a50 is the fifty-first term since k = n−m+1 = 50−0+1 = 51.

152 CHAPTER 3. SEQUENCES AND SERIES

Answer: The pattern is that the next term equals the previous term times three. We can start our index at either 0 or 1, so let’s choose 1. Therefore,{

a1 = 2

an = 3an−1 for n ≥ 2

Recursive definitions have the same drawback that we’ve seen before: if we want to know the 200th term, we need to calculate the 199th first, and so on. Only the general formula allows us to calculate each term directly without knowing the previous one.

3.1.7 Fibonacci sequence

The Fibonacci sequence is the most famous example of a recursive sequence: 1, 1, 2, 3, 5, 8, 13, . . .

The pattern can be quite difficult to spot – you get the next term from the sum of the two previous terms. The recursive formula for this sequence is therefore 

 a1 = 1

a2 = 1

an = an−1 + an−2 for n ≥ 3

Here, the first two terms must be given to start off with so that you are then able to calculate the third term from the previous two.

3.1.8 Series

A series is the sum of the terms of a sequence, which can be finite or infinite. Here are two examples:

(a) 16 + 20 + 24 + 28 + . . . + 64

(b) 1 + 1 3

+ 1 9

+ 1 27

+ ...

You can see that the first example is a finite series, while the second one is infinite.

3.1. INTRODUCTION TO SEQUENCES AND SERIES 153

3.1.9 Notation for Series

The sum of the first k terms of a sequence is denoted by Sk (also sometimes called the kth partial sum). If the series is finite, it could be the sum of all of the terms. S∞ is how we write the sum of an infinite series, like the second example above.

Example: For the series 16 + 20 + 24 + 28 + . . . + 64, calculate S3 and S4.

Answer:

S3 = 16 + 20 + 24 = 60

S4 = 16 + 20 + 24 + 28 = 88

However, it’s easy to see that this method becomes very cumbersome for large values of k. We’ll develop some more efficient methods for particular types of series in the next two sections.

3.1.10 Sigma Notation

It’s easy to take a sequence in list form and transform it into a series by changing all of the commas to plus signs. However, what if you are given the general formula instead? For example, let’s take 7, 11, 15, 19, . . . which we know to be an = 4n + 3 for n ≥ 1. Since the general form is so useful for finding an when n is large, it would be nice if we could retain that information while writing our sum.

To do so, we’ll introduce a new notation called “sigma notation’. It uses the Greek letter sigma (the uppercase one): Σ, which is commonly used to mean “sum of’.

Let’s look at an example of sigma notation and discuss what all of the parts mean. Consider the following sum:

5∑ i=1

(4i + 3)

The letter i is an index here, and it runs from the value given at the bottom of the sigma to the number at the top of the sigma in steps of 1. Here, i

154 CHAPTER 3. SEQUENCES AND SERIES

runs from 1 to 5. We are summing, then, the value of 4i + 3 for each value of i as it runs from 1 to 5:

5∑ i=1

(4i + 3) =

i=1︷︸︸︷ (4 × 1 + 3) +

i=2︷︸︸︷ (4 × 2 + 3) +

i=3︷︸︸︷ (4 × 3 + 3) +

i=4︷︸︸︷ (4 × 4 + 3) +

i=5︷︸︸︷ (4 × 5 + 3)

= 7 + 11 + 15 + 19 + 23

= 75

Let’s look at more examples.

Example: Calculate 2∑

i=0 (2i− 5).

Answer:

2∑ i=0

(2i− 5) = i=0︷︸︸︷

(2 × 0 − 5) + i=1︷︸︸︷

(2 × 1 − 5) + i=2︷︸︸︷

(2 × 2 − 5)

= −5 + (−3) + (−1) = −9

Example: Calculate 9∑

j=6 (8 − j)2.

Answer:

9∑ j=6

(8 − j)2 =

j=6︷︸︸︷ (8 − 6)2 +

j=7︷︸︸︷ (8 − 7)2 +

j=8︷︸︸︷ (8 − 8)2 +

j=9︷︸︸︷ (8 − 9)2

= 4 + 1 + 0 + 1

= 6

Example: Calculate 16∑

k=12

3.1. INTRODUCTION TO SEQUENCES AND SERIES 155

Answer:

16∑ j=12

3 =

k=12︷︸︸︷ 3 +

k=13︷︸︸︷ 3 +

k=14︷︸︸︷ 3 +

k=15︷︸︸︷ 3 +

k=16︷︸︸︷ 3

= 15

The tricky thing about the last one is deciding how many terms there are. Recall that you can either write out all of the possible values of the index, or use the useful rule:

k = n−m + 1

and as the last example had the index running from 12 to 16, then the number of terms k is

k = 16 − 12 + 1

k = 5

Example: Write the following series in sigma notation:

4 + 9 + 16 + 25 + ...100

Answer: Let’s pick our index first. If we want to be lazy, instead of starting our index at 0 or 1, we could start at 2 and our series would be

10∑ k=2

Other acceptable answers would involve changing our starting point for the index to give

9∑ j=1

(j + 1) 2

or 8∑

i=0

(i + 2) 2

or even 165∑

l=157

(l− 155)2

if 157 happens to be your favourite number.

156 CHAPTER 3. SEQUENCES AND SERIES

Example: Write the following sequence in sigma notation:

3 +

4 +

5 +

6 + . . .

Answer: ∞∑ j=3

To write an infinite series in sigma notation, you just replace the final value of the index with ∞.

3.1. INTRODUCTION TO SEQUENCES AND SERIES 157

Exercises for Section 3.1

Predict the next three terms of the following sequences.

1. 18, 16, 14, . . .

2. 1, 4, 9, 16, . . .

3. 12, 24, 48, 96, . . .

4. 144, 36, 9, . . .

5. 1, √

2, √

3, 2, √

5, √

6, ...

6. 5,−10, 20, . . .

7. 13, 25, 37, 49, . . .

8. 1 2 , 1

3 , 1

4 , 1

5 , ...

Give a formula for the general term (the nth term an in terms of n) of the following sequences. Use n = 1 as your starting index.

9. 1, 4, 9, 16, . . .

10. 1, √

2, √

3, 2, √

5, √

6, ...

11. 2, 4, 6, 8, . . .

12. 1 2 , 1

3 , 1

4 , 1

5 , ...

Find the first four terms of the following recursively defined sequences.

13.

{ a1 = 2

an = an−1 + 5 for n ≥ 2

14.

{ a1 = 10

an = 3an−1 for n ≥ 2

15.

 

a1 = 2

a2 = 3

an = an−1 ×an−2 for n ≥ 2

16.

{ a1 = 2

an = 1

an−1 + 1 for n ≥ 2

158 CHAPTER 3. SEQUENCES AND SERIES

In each of the following, the general formula for the nth term of a sequence is given. Find the first four terms.

17. an = 3n− 5 for n ≥ 1

18. an = 3 n−2 for n ≥ 1

19. an = n! for n ≥ 1

20. an = 1 n2

for n ≥ 1

In each of the following, the general formula for the nth term of a sequence is given. Calculate the specified terms.

21. Find a7 for the sequence an = 5 ( 2n+1

) for n ≥ 1

22. Find a100 for the sequence an = 4n + 15 for n ≥ 1

23. Find a2500 for the sequence an = n+2 n+1

for n ≥ 1

24. Find a10 for the sequence an = 2n 3 for n ≥ 1

Calculate S3 and S6 for the following series.

25. 3 + 6 + 9 + . . .

26. 1 + 4 + 9 + 16 + . . .

27. 5 − 10 + 20 − 40 + . . .

28. 5 + 3 + 1 + . . .

Write out each sum in full and then evaluate.

29. 7∑

n=3 n

30. 10∑ j=4

(−1)j

31. 4∑

i=0 2i

32. 25∑

k=20

(3k − 10)

Write each series in sigma notation. (Answers may vary.)

33. 1 + 8 + 27 + 64 + . . . 1000

3.1. INTRODUCTION TO SEQUENCES AND SERIES 159

34. 1 2

+ 1 3

+ 1 4

+ 1 5

+ ...

35. 2 + 4 + 6 + 8 + . . .

36. 2 + 4 + 6 + 8

Evil alert!

37. (nasty) Write the sequence 1, 4, 9, 16, . . . using a recursive definition.

38. (thorny) Write the sequence 1, 2, 6, 24, . . . using a general formula.

39. (tricksy) Consider the following sequence:

4, 5, 20, 100, 2000

(a) What’s the next term in this sequence?

(b) What’s the recursive formula for this sequence?

160 CHAPTER 3. SEQUENCES AND SERIES

Answers to Section 3.1 Exercises

1. 12, 10, 8 (pattern is to subtract 2)

2. 25, 36, 49 (nth term is equal to n2

3. 192, 384, 768 (multiply by 2)

4. 9 4 , 9

16 , 9

64 (divide by 4)

5. √

7, 2 √

2, 3 (nth term is √ n)

6. −40, 80,−160 (multiply by −2)

7. 61, 73, 85 (add 12)

8. 1 6 , 1

7 , 1

9. an = n 2

10. an = √ n

11. an = 2n

12. an = 1

n+1

13. 2, 7, 12, 17

14. 10, 30, 90, 270

15. 2, 3, 6, 18

16. 2, 3 2 , 5

3 , 8

17. −2, 1, 4, 7

18. 1 3 , 1, 3, 9

19. 1, 2, 6, 24

20. 1, 1 4 , 1

9 , 1

21. a7 = 1280

22. a100 = 415

23. a2500 = 2502 2501

24. a10 = 2000

25. S3 = 18,S6 = 63

3.1. INTRODUCTION TO SEQUENCES AND SERIES 161

26. S3 = 14,S6 = 91

27. S3 = 15,S6 = −105

28. S3 = 9,S6 = 0

29. 7∑

n=3 n = 3 + 4 + 5 + 6 + 7 = 25

30. 10∑ j=4

(−1)j = 1 + (−1) + 1 + (−1) + 1 + (−1) + 1 = 1

31. 4∑

i=0 2i = 20 + 21 + 22 + 23 + 24 = 1 + 2 + 4 + 8 + 16 = 31

32. 25∑

k=20

3k − 10 = 50 + 53 + 56 + 59 + 62 + 65 = 345

33. 10∑ i=1

34. ∞∑ j=2

1 j

35. ∞∑ k=1

36. 4∑

k=1

37. You could either do{ a1 = 1

an = (√ an−1 + 1

)2 for n ≥ 2

or another possibility is{ a1 = 1

an = an−1 + 2n + 1 for n ≥ 2

38. an = n! for n ≥ 1

39. The next term is 200,000.

162 CHAPTER 3. SEQUENCES AND SERIES

 

a1 = 4

a2 = 5

an = an−1 ×an−2

3.2. ARITHMETIC SEQUENCES AND SERIES 163

3.2 Arithmetic Sequences and Series

3.2.1 Arithmetic Sequences

Let’s start out with a definition:

arithmetic sequence: a sequence in which the next term is found by adding a constant (the common difference d) to the previous term

Here are some examples of arithmetic sequences:

(a) 7, 11, 15, 19, . . .

(b) 11, 4,−3,−10, . . .− 59

The first one has a common difference of 4, the second −7, and the third 0.3. Note that in each of them, we can find the common difference d by taking any term and subtracting the previous term from it.

Example: For the following sequences, state whether each of them is arithmetic.

(a) −3,−10,−17,−24, . . .

(b) 4, 5, 7, 10, . . .

(d) 1 2 , 1

3 , 1

4 , 1

5 , . . . 1

Answer:

(a) Yes, because the common difference d is −7.

(b) No, because you’re not adding the same number each time.

(d) No, because the difference between each pair of terms is different.

Again, you can define an arithmetic sequence in one of three ways: by listing the terms, by giving a recursive definition, or by giving a general definition.

164 CHAPTER 3. SEQUENCES AND SERIES

3.2.2 Recursive Definitions for Arithmetic Sequences

Let’s look first at an example.

Example: Give a recursive definition for the sequence 2, 10, 18, 26, . . .

Answer: Recall that a recursive definition has two parts: listing the first term and giving the pattern. In this case, the pattern is adding d = 8 to the previous term to get the next term. We can start our index anywhere, so let’s choose zero for this example. The recursive definition is therefore{

a0 = 2

an = an−1 + 8 for n ≥ 1

To generalize, the recursive formula for any arithmetic sequence is{ am = < insert value here >

an = an−1 + d for n ≥ m + 1

3.2.3 General Formulae for Arithmetic Sequences

Let’s examine the previous example in more detail to see if we can recognize any patterns and come up with a general formula. Rewriting each term, we get

2, 10, 18, 26, . . .

2 2 + 8, 2 + 8 × 2, 2 + 8 × 3, . . .

So the 3rd term equals the first plus 8 times 2, the 4th term equals the first plus 8 times 3, and the nth term will equal the first plus 8 times (n−1). In other words,

2, 10, 18, 26, . . . an

2 2 + 8, 2 + 8 × 2, 2 + 8 × 3, . . . 2 + 8 × (n− 1)

and so we find for this particular sequence, an = 2 + 8 × (n − 1), which simplifies to an = 8n− 6.

We can generalize this formula: the nth term will equal the first plus d times (n−m), so

an = am + (n−m) d where n ≥ m

3.2. ARITHMETIC SEQUENCES AND SERIES 165

for any arithmetic sequence.

Example: Write a general formula for the sequence 3, 8, 13, 18, . . .

Answer: This sequence is arithmetic with the first term 3 and common difference 5. Let’s use a starting index of zero.

an = am + (n−m) d = a0 + (n− 0) d = 3 + (n) 5

= 3 + 5n

= 5n + 3

The general formula is then an = 5n + 3 for n ≥ 0.

Example: What is the 50th term in the sequence in the sequence 3, 8, 13, 18, . . .?

Answer: This is the same sequence from the previous example. We may then use the formula we derived, an = 5n + 3 for n ≥ 0. But we do have to be careful about our index n. Recalling that the number of terms k is given by

k = n−m + 1

where we used m = 0 as our starting index, then

50 = n− 0 + 1

n = 49

and so the 50th term will be a49.

an = 5n + 3

a49 = 5 × 49 + 3 = 245 + 3

= 248

The 50th term is 248.

Example: What is the common difference in the arithmetic sequence in which the first term is 18 and the twelfth term is −59?

166 CHAPTER 3. SEQUENCES AND SERIES

Answer: The easiest way to count these terms correctly is to have a starting index of one, and then the first term is a1 and the twelfth term is a12.

an = am + (n−m) d a12 = a1 + (12 − 1) d −59 = 18 + (12 − 1) d −77 = 11d d = −7

The common difference is −7.

Example: Which term has a value of 404 in the sequence −37,−28,−19, . . .?

Answer: Let’s use a starting index of one. So a1 is −37 and d is +9. Then we want to find the value of n for which an equals 404.

an = am + (n−m) d = a1 + (n− 1) d

404 = −37 + (n− 1) 9 441 = 9 (n− 1) 49 = n− 1 n = 50

The fiftieth term is 404.

3.2.4 Arithmetic Series

Recall that Sk is the sum of the first k terms of a series. Let’s look at a couple of examples of arithmetic series to see if we can identify any patterns.

Suppose we wish to take some partial sums of the series 2 + 10 + 18 + 26 +. . .. Let’s first calculate S6. We could just find the first six terms and add them up, but notice the following:

S6 = 2 + 10 + 18 + 26 + 34 + 42

The sum of the first and last numbers is 44. The sum of the second and second-to-last is also 44. So is the sum of the third and third-last. So when

3.2. ARITHMETIC SEQUENCES AND SERIES 167

you take the terms in pairs, each pair has the same sum, (am + an), and there are k/2 pairs in total. Then

Sk = k

2 (am + an)

What if, however, there are an odd number of terms? Let’s also calculate S7:

S7 = 2 + 10 + 18 + 26 + 34 + 42 + 50

The sum of the first and last is 52, as is the sum of the each “inner pair’. Notice that the middle, unpaired value, is 1

2 of 52. So in a sense, the middle

term is 1 2

of a pair, for a total of 3 1 2

pairs. But that’s just 7/2, which is our k/2 in the original formula! So we’re still good. The relationship

Sk = k

2 (am + an)

still works, for both odd and even values of k.

Generalizing, we find that

Sk = k

2 (am + an)

where k can be even or odd and

k = n−m + 1 for n ≥ m

Example: Find the sum of the first forty terms of the series 2 + 10 + 18 + 26 + . . ..

Answer: This is just the same sequence as before, with first term am = 2 and common difference d = 8. In order to use our previous formula, however, we need to calculate the last term an. If we start with an index of one, then the fortieth term will be a40, and we will need that value to calculate S40.

an = am + (n−m) d = a1 + (n− 1) d

a40 = 2 + 39 × 8 = 314

168 CHAPTER 3. SEQUENCES AND SERIES

So,

Sk = k

2 (am + an)

S40 = 40

2 (2 + 314)

= 20 × 316 = 6320

The sum of the first forty terms is 6320. (Much easier than writing out the first forty terms and adding them up!)

In the previous example, we used the formula for an to calculate the last term and put its value into the formula for Sk. We could do that in a more general way:

Sk = k

2 (am + an)

= k

2 [am + (am + (n−m) d)]

= k

2 [2am + (n−m) d]

and the last expression, which gives Sk as a function of the first term, the number of terms, and the common difference, can also be used to evaluate series.

Example: Find the sum of the first one hundred terms of the sequence 5,−6,−17,−26, . . . .

Answer: This sum will just be 5 + −6 + −17 + −26 + . . ., with am = 5, d = −11, and k = 40. If we start our index at one, then

k = n−m + 1

40 = n− 1 + 1

n = 40

and we can substitute this into the equation for Sk:

Sk = k

2 [2am + (n−m) d]

S100 = 100

2 [2 × 5 + 99 × (−11)]

= −53950

3.2. ARITHMETIC SEQUENCES AND SERIES 169

Example: Calculate 18∑ j=3

5n + 10.

Answer: The first term will be for j = 3 and will equal 5(3)+10 = 25. Next is j = 4 and will equal 5(4) + 10 = 30, j = 5 equaling 5(5) = 35, and so on. The last term will be for j = 18 and will equal 5(18) + 10 = 100.

In other words, our series is 25+30+35+. . . 100. Is it arithmetic? Yes, with common difference d = 5.

What else do we need for our calculation? The number of terms is

k = n−m + 1 k = 18 − 3 + 1

k = 16

Then

Sn = n

2 (a1 + an)

S16 = 16

2 (25 + 100) = 1000

Example: Pat the math instructor asks her students to do five word problems the first week, six the second week, seven the third week, and so on, increasing the number of word problems each week by one.

(a) How many word problems will diligent students be doing in the last week of classes (the nth11 week)?

(b) How many word problems will diligent students have com- pleted during the course of the term (11 weeks)?

Answer:

(a) The number of word problems is a sequence: 5, 6, 7, . . . . In fact, it’s an arithmetic sequence with am = 5 and d = 1. If we start our counting from one, then in the eleventh week,

an = am + (n−m) d an = a1 + (n− 1) d a11 = 5 + 10 × 1

= 15

170 CHAPTER 3. SEQUENCES AND SERIES

Diligent students will solve 15 word problems in the last week of classes.

(b) The total number of word problems solved is

Sk = k

2 (am + an)

S11 = 11

2 (5 + 15)

= 110

Diligent students will have solved 110 word problems in total.

3.2.5 Summary

For an arithmetic sequence, the nth term is given by

an = am + (n−m) d for n ≥ m

For an arithmetic series, the sum of the first k terms (kth partial sum) is

Sk = k

2 (am + an)

Sk = k

2 [2am + (n−m) d]

where k = n−m + 1 and n ≥ m.

3.2. ARITHMETIC SEQUENCES AND SERIES 171

Exercises for Section 3.2

State whether the following sequences are arithmetic or not. If they are, state the first term and common difference.

1. 8, 9, 11, 13, 16, . . .

2. −3,−10,−17,−24, . . .

3. 3, 6, 12, 24, . . .

4. 1, 2, 6, 24, . . .

5. 81, 72, 63, 54, . . .

6. 1, 5 4 , 3

2 , 7

4 , 2, 9

4 , ...

Give both the general formula and the recursive formula for the nth term an of the following arithmetic sequences. Assume that the first term of the sequence is a1. For the general formula, be sure to simplify your answer.

7. 1, 3, 5, 7, . . .

8. 5,−6,−17,−28, . . .

9. −40,−37,−34,−31, . . .

10. 24, 28, 32, 36, . . .

For the following arithmetic sequences, calculate a50 and a261, assuming that the first term is a1.

11. 18, 16, 14, 12, . . .

12. 12, 12.3, 12.6, 12.9, . . .

State whether the following recursively defined sequences are arithmetic or not. (Is there an easy way to tell?)

13.

{ a0 = 5

an = an−1 + 4 for n ≥ 1

14.

{ a1 = 12

an = 2an−1 for n ≥ 2

15.

{ a1 = 75

an = an−1 − 20 for n ≥ 2

172 CHAPTER 3. SEQUENCES AND SERIES

16.

{ a0 = 6

an = an−1 + 1 for n ≥ 1

17.

{ a0 = 7

an = 2 −an−1 for n ≥ 1

18.

{ a1 = 3

an = (an−1) 2

for n ≥ 2

19. For the following sequence, calculate the 201st term: 5, 15, 25, 35, . . .

20. For the following sequence, which term equals 137? 1, 9, 17, 25, . . .

21. What is the common difference for the arithmetic sequence with a1 = 200 and a12 = −240?

22. Calculate the first term for the arithmetic sequence with common dif- ference 7 whose sixteenth term is 102.

23. Calculate the first four terms of the arithmetic sequence in which the sixth term is 17 and the sixtieth term is 179.

24. Calculate the first four terms of the arithmetic sequence in which the one hundredth term is 403 and the sixty-fourth term is 259.

25. Give a general formula for the arithmetic sequence in which the twen- tieth term is −107 and the thirty-fifth term is −152.

26. Give a recursive formula for the arithmetic sequence in which the eleventh term is 44 and the fifty-second term is 290.

27. Calculate S20 for the series 100 + 97 + 94 + . . .

28. Evaluate the series 12 + 17 + 22 + . . . 82.

29. Evaluate the series 144 + 138 + 132 + . . . 78.

30. Calculate S100 for the series −20 − 16 − 12 − . . .

31. Calculate the sum of the odd numbers between 100 and 500.

32. Find the sum of the natural numbers from 50 to 125, inclusive.

Calculate the following sums.

33. 53∑ k=0

(5k − 1)

3.2. ARITHMETIC SEQUENCES AND SERIES 173

34. 92∑

j=10 6j

35. 140∑ i=30

(2i + 7)

36. 502∑ k=3

(17 − 3k)

37. In a supermarket display, there are 37 cans in the bottom layer, 35 in the next layer up, 33 in the next, and so on. How many layers are there if there are 7 cans in the top row?

38. In the previous problem, how many cans are there altogether?

39. In an old-fashioned theatre, there are 25 seats in the first row, 26 in the next, 27 in the one after, and so on. If there are 20 rows in total, how many seats are there altogether?

174 CHAPTER 3. SEQUENCES AND SERIES

Answers to Section 3.2 Exercises

1. not arithmetic

2. yes, d = −7

3. no

4. no

5. yes, d = −9

6. yes, d = 1 4

7. an = 2n− 1 and

{ a1 = 1

an = an−1 + 2

8. an = 16 − 11n and

{ a1 = 5

an = an−1 − 11

9. an = 3n− 43 and

{ a1 = −40 an = an−1 + 3

10. an = 4n + 20 and

{ a1 = 24

an = an−1 + 4

11. an = 20 − 2n, so a50 = −80 and a261 = −502

12. an = 11.7 + 0.3n, so a50 = 26.7 and a261 = 90

13. first four terms are 5, 9, 13, 17, so arithmetic with d = 4

14. first four terms are 12, 24, 48, 96, so not arithmetic

15. first four terms are 75, 55, 35, 15, so arithmetic with d = −20

16. first four terms are 6, 7, 8, 9, so arithmetic with d = 1

17. first four terms are 7,−5, 7,−5, so not arithmetic

18. first four terms are 3, 9, 81, 6561, so not arithmetic

19. an = 10n− 5, so a201 = 2005

20. an = 8n− 7, so n = 18

21. d = −40

3.2. ARITHMETIC SEQUENCES AND SERIES 175

22. a1 = −3

23. a1 = 2 and d = 3, so the first four terms are 2, 5, 8, 11

24. a1 = 7 and d = 4, so the first four terms are 7, 11, 15, 19

25. an = −3n− 47

26.

{ a1 = −16 an = an−1 + 6

27. S20 = 1430

28. S15 = 705

29. S12 = 1332

30. S100 = 17800

31. S200 = 60000

32. S76 = 6650

33. S53 = 7101

34. S83 = 25398

35. S111 = 19647

36. S500 = −370, 250

37. n = 16

38. S16 = 352

39. S20 = 690

176 CHAPTER 3. SEQUENCES AND SERIES

3.3. GEOMETRIC SEQUENCES AND SERIES 177

3.3 Geometric Sequences and Series

3.3.1 Geometric Sequences

Let’s start out with a definition:

geometric sequence: a sequence in which the next term is found by multiplying the previous term by a constant (the com- mon ratio r)

Here are some examples of geometric sequences:

(a) 9, 18, 36, 72, . . .

(b) 12, 18, 27, 81 2 , . . .

(d) −3,−12,−48,−192, . . .

(e) 48,−36, 27, . . .

The common ratios of each of these sequences, in order from a) to e), is 2, 3 2 ,

−3, 4, −3 4 , respectively. Note that in each of them, we can find the common

ratio r by taking any term and dividing it by the previous term.

Like any other sequences, geometric sequences can be finite or infinite. Ex- ample c) above is finite, as the last term is specified. The others are infinite sequences.

Example: For each of the following sequences, state whether it is arithmetic, geometric, or neither.

(a) 45, 15, 5, . . .

(b) 5, 3, 1,−1, . . .

(d) −1, 1,−1, 1,−1, 1, . . .

Answer:

(a) Geometric, because the common ratio r is 1 3 .

(b) Arithmetic, because the common difference d is −2.

178 CHAPTER 3. SEQUENCES AND SERIES

for n ≥ 1.)

(d) Geometric, because the common ratio r is −1.

Again, you can define a geometric sequence in one of three ways: by listing the terms, by giving a recursive definition, or by giving a general definition.

3.3.2 Recursive Definitions for Geometric Sequences

Let’s look at an example.

Example: Give a recursive definition for the sequence 2, 10, 50, 250, . . .

Answer: Recall that a recursive definition has two parts: listing the first term and giving the pattern. In this case, the pattern is multiplying the previous term by r = 5 to get the next term. Let’s use 0 as our starting index. The recursive definition is therefore {

a0 = 2

an = 5an−1 for n ≥ 1

Generally, the recursive definition for any geometric sequence is{ am =< insert value here >

an = an−1 ×r for n ≥ m + 1

3.3.3 General Formulae for Geometric Sequences

Let’s examine the previous example in more detail to see if we can recognize any patterns and come up with a general formula. Rewriting each term, we get

2, 10, 50, 250, . . .

2, 2 × 5, 2 × 52, 2 × 53, . . .

So the 3rd term equals the first times 5 squared, the 4th term equals the first times 5 cubed, and the nth term will equal the first times 5 raised to the

3.3. GEOMETRIC SEQUENCES AND SERIES 179

(n − 1) power. In general, for sequences with first term am, the nth term equals the first term times r raised to the (n−m) power, namely

an = amr n−m

for all geometric sequences.

Example: Write a general formula for the sequence 3, 6, 12, . . .

Answer: This sequence is geometric with the first term 3 and common ratio 2. If we choose n = 1 for our first term, then

an = amr n−m

= a1r n−1

= 3 × (2)n−1

The general formula is then an = 3 × 2n−1 for n ≥ 2.

Example: What is the 20th term in the sequence in the sequence 3, 6, 12, . . .?

Answer: This is the same sequence from the previous example. We may then use the formula we derived above with n = 20.

an = amr n−m

= a1r n−1

a20 = 3 × 220−1

a20 = 3 × 219

a20 = 1, 572, 864

The 20th term is 1,572,864, which provides a nice example for how fast geometric sequences can grow, even for small values of r.

Example: Write a general formula for the sequence 8, 12, 18, 27, . . . What is the fifteenth term in this sequence? The fiftieth?

Answer: If we start our counting at n = 1, then the fifteenth

180 CHAPTER 3. SEQUENCES AND SERIES

term is a15 and the fiftieth term is a50.

an = amr n−m

= a1r n−1

an = 8

( 3

)n−1 a15 = 8

( 3

)14 ≈ 2335.43

a50 = 8

( 3

)49 ≈ 3.40065 × 109

So the general formula is an = 8 (

3 2

)n−1 for n ≥ 1 and the fif-

teenth and fiftieth terms are approximately 2335.43 and 3.4×109, respectively.

3.3.4 Geometric Series

Recall that Sk is the sum of the first k terms of a series. Let’s look at how a formula for Sk is derived, using a series that starts with n = 1.

Sk = a1 + a2 + a3 + a4 + . . . + an−2 + an−1 + ak

Sk = a1 + a1r + a1r 2 + a1r

3 + . . . + a1r k−3 + a1r

k−2 + a1r k−1

Let’s take that last expression for Sk and multiply it by −r to get

−rSk = −a1r −a1r2 −a1r3 −a1r4 − ...−a1rk−2 −a1rk−1 −a1rk

Then if we add the rows for Sk and −rSk, we get

Sk = a1 +a1r +a1r 2 +a1r

3 + . . . +a1r k−3 +a1r

k−2 +a1r k−1

−rSk = −a1r −a1r2 −a1r3 −a1r4 − . . . −a1rk−2 −a1rk−1 −a1rk

Sk −rSk = a1 −a1rk

since all of the terms in between these two (a1 and a1r k) will cancel. Then

Sk −rSk = a1 (

1 −rk )

Sk (1 −r) = a1 (

1 −rk )

3.3. GEOMETRIC SEQUENCES AND SERIES 181

and

Sk = a1 ( 1 −rk

) (1 −r)

To generalize, the formula for the sum of the first n terms for any geometric series that starts with first term am is

Sk = am ( 1 −rk

) (1 −r)

Example: Find the sum of the first 20 terms of the series 3 + 6 + 12 + . . .

Answer: This is a geometric series with am = 3 and r = 2. We want to find S20.

Sk = am ( 1 −rk

) (1 −r)

S20 = 3 ( 1 − 220

) (1 − 2)

= 3, 145, 725

The sum of the first 20 terms is 3,145,725.

Example: Find the sum of the first forty terms of the series 8 − 12 + 18 − 27 . . ..

Answer: This is a geometric series with am = 8 and r = −32 . We want to find S40.

Sk = am ( 1 −rk

) (1 −r)

S20 = 8 (

1 − (−1.5)40 )

(1 − (−1.5)) = −3.53835 × 107

The sum of the first forty terms is −3.54 × 107.

3.3.5 Sum of an Infinite Geometric Series

Let’s take a look at the infinite series 1 2

+ 1 4

+ 1 8

+ 1 16

+ ... What happens when we try to evaluate this sum using the Sk formula? We can put am =

1 2 ,

r = 1 2 , and n = ∞ into the formula, but we will run into a roadblock when

we try to evaluate ( 1 2 )∞.

182 CHAPTER 3. SEQUENCES AND SERIES

Let’s take a closer look at the behaviour of ( 1 2 )n for large values of n. As n

gets larger, the fraction (

1 2

)n = 1

2n gets ever smaller. In fact, as n approaches

∞, ( 1 2 )n will approach zero.

This is true for any r provided that |r| < 1. (If you’re not familiar with the absolute value bars, an equivalent expression is that −1 < r < 1.)

Recalling that

Sk = am ( 1 −rk

) (1 −r)

and letting the rn term go to zero, then

S∞ = am

1 −r for − 1 < r < 1

for any infinite geometric series with am the first term, provided that r meets the restriction above.

Let’s now revisit the series that started this discussion and evaluate it in the following example.

Example: Evaluate 1 2

+ 1 4

+ 1 8

+ 1 16

+ ...

Answer: This series is geometric with am = 1 2

and r = 1 2 . Then

S∞ = am

1 −r =

1/2

1 − 1/2 =

1/2

1/2 = 1

The sum of this series is 1.

Example: Evaluate 24 + 16 + 32 3

+ . . .

Answer: This series is geometric with am = 24 and r = 2 3 .

S∞ = am

1 −r =

1 − 2 3

= 24 1 3

= 24 × 3

1 = 72

Example: Evaluate 24 − 16 + 32 3

+ . . .

Answer: This series is identical to the previous one except that r is now negative: am = 24 and r = −23 .

S∞ = am

1 −r =

1 − ( −2

) = 24 1 + 2

= 24 5 3

= 24 × 3

5 =

5 = 14.4

Example: Evaluate 12 + 18 + 27 + . . .

3.3. GEOMETRIC SEQUENCES AND SERIES 183

Answer: This series is geometric with am = 12 and r = 3 2 . You

may already realize what’s going on, but in case you don’t, let’s naively put the values into the formula and see what we get:

S∞ = am

1 −r =

1 − 3 2

= 12

−1 2

= 12 ×− 2

1 = −24

Wait! How can the sum of a bunch of positive number be nega- tive? The answer is that our restriction for r is that it must be between −1 and 1, but r = 1.5. Because r does not satisfy the restriction, we cannot use the above formula for S∞. Indeed, if you add up a bunch of positive numbers that are increasing as you go up, you can see that the sum just keeps getting bigger as we add more terms. You could then either say that the sum is infinite (dicey) or “does not exist” (safer).

But why is it safer to say “does not exist” in the last example? Let’s look at three sums:

(a) 12 + 18 + 27 + . . .

(b) −12 − 18 − 27 − . . .

Each term in (a) is getting more positive, so the sum of that sequence will be +∞. Each term in (b) is getting more and more negative, so the sum of that sequence will be −∞. But in the last term, the sum oscillates back and forth: S1 = 12, S2 = −6, S3 = 21, S4 = −19.5, and so on. The sign of Sk is either positive or negative depending on whether the number of terms you’ve added is even or odd. Rather than debating whether infinity is odd or even (?!), we will just say that the sum “does not exist”.

Example: Evaluate ∞∑ j=0

27 (

1 3

)j .

Answer: Ick! The best place to start is to figure out the first few terms to determine the pattern:

when j = 0, 27 (

1 3

)0 = 27 × 1 = 27

when j = 1, 27 (

1 3

)1 = 27 × 1

3 = 9

when j = 2, 27 (

1 3

)2 = 27 × 1

32 = 3

184 CHAPTER 3. SEQUENCES AND SERIES

so our sequence is 27, 9, 3, . . . This is geometric with am = 27 and r = 1

3 . Then

S∞ = am

1 −r =

1 − 1 3

= 27 2 3

= 27 × 3

2 =

2 = 40.5

Example: Evaluate ∞∑ k=5

1 2 k.

Answer: Once again, let’s figure out the first few terms to deter- mine the pattern:

when k = 5, 1 2 k = 1

2 5 = 2.5

when k = 6, 1 2 k = 1

2 6 = 3

when k = 7, 1 2 k = 1

2 7 = 3.5

so our sequence is 2.5, 3, 3.5, . . .. Wait! This is arithmetic! Not only that, but the numbers are increasing. So the sum will be infinite, or if you prefer, the sum “does not exist”.

3.3.6 Repeating Decimals

Let’s examine 0.7 in some detail to see what we find:

0.7 = 0.777777777...

= 0.7 + 0.07 + 0.007 + 0.0007 + . . .

But this is just the sum of an infinite series with am = 0.7 and r = 0.1. Rewriting a1 and r in fraction form (you’ll see why in a minute) gives am = 7 10

and r = 1 10

. Then

S∞ = am

1 −r =

7 10

1 − 1 10

= 7 10 9 10

= 7

10 ×

9 =

So 0.7 = 7/9. Interesting!

Example: Find an exact fraction for 0.6.

Answer:

0.6 = 0.66666666...

= 0.6 + 0.06 + 0.006 + 0.0006 + ...

3.3. GEOMETRIC SEQUENCES AND SERIES 185

But this is just the sum of an infinite series with am = 6 10

and r = 1

10 . Then

S∞ = am

1 −r =

6 10

1 − 1 10

= 6 10 9 10

= 6

10 ×

9 =

So 0.6 = 2/3.

Example: Find an exact fraction for 0.18.

Answer: 0.18 = 0.1818181818...

= 0.18 + 0.0018 + 0.000018 + ...

But this is just the sum of an infinite series with am = 18 100

and r = 1

100 . Then

S∞ = am

1 −r =

18 100

1 − 1 100

= 18 100 90 100

= 18

100 ×

100

99 =

So 0.18 = 2/11.

3.3.7 Summary

For a geometric sequence, the nth term is given by

an = amr n−m

for n ≥ m

For a geometric series, the sum of the first k terms (kth partial sum) is

Sk = am ( 1 −rk

) (1 −r)

where am is the first term

For an infinite geometric series, the sum is

S∞ = am

1 −r

provided that −1 < r < 1 and am is the first term.

186 CHAPTER 3. SEQUENCES AND SERIES

Exercises for Section 3.3

State whether the following sequences are geometric or not. If they are, state the first term and common ratio.

1. 8, 9, 11, 13, 16, . . .

2. −3,−10,−17,−24, . . .

3. 3, 6, 12, 24, . . .

4. 1, 2, 6, 24, . . .

5. 81, 72, 63, 54, . . .

6. 72, 48, 32, ...

Give both the general formula and the recursive formula for the nth term an of the following sequences. Use the convention n ≥ 1.

7. 1, 3, 9, 27, . . .

8. 64, 16, 4, 1, . . .

9. 3,−6, 12,−24, . . .

10. 24, 2.4, 0.24, . . .

For the following sequences, calculate a50 and a261, assuming that the first term is a1.

11. 12, 18, 27, . . .

12. 12, 8, 16 3 , . . .

State whether the following recursively defined sequences are geometric or not. (Is there an easy way to tell?)

13.

{ a1 = 5

an = an−1 + 4 for n ≥ 2

14.

{ a0 = 12

an = 2an−1 for n ≥ 1

15.

{ a0 = 75

an = 10an−1 for n ≥ 1

3.3. GEOMETRIC SEQUENCES AND SERIES 187

16.

{ a1 = 7

an = 2 −an−1 for n ≥ 2

17.

{ a1 = 8

an = −an−1 for n ≥ 2

18.

{ a0 = 3

an = (an−1) 2

for n ≥ 1

19. For the following sequence, calculate the 201st term: 5, 15, 45, . . .

20. For the following sequence, calculate the 20th term: 7,−14, 28, . . .

21. Calculate S20 for the series 100 + 50 + 25 + . . .

22. Calculate S20 for the series 100 + 200 + 400 + . . .

Calculate the sum, if it exists, for the following series.

23. −6 + 4 − 8 3

+ ...

24. 100 + 50 + 25 + . . .

25. 100 + 200 + 400 + . . .

26. 12 + 3 + 3 4

+ . . .

Calculate the following sums, if they exist.

27. 10∑ k=0

2k+2

28. ∞∑ j=1

15 (

3 5

)j 29.

∞∑ i=2

25(0.1) j

30. ∞∑ i=0

4(−3)i

31. If the number of vampires in Transylvania doubles every month, then how many vampires will be in Transylvania in 3 years, starting from one individual? Comment on your result if the total population of Transylvania is 2 million people.

188 CHAPTER 3. SEQUENCES AND SERIES

32. As I was going to St. Ives, I met a man with seven wives. Each wife had seven sacks. Each sack had seven cats. Each sack had seven kits. Kits, cats, sacks, wives: does this form a geometric sequence?

33. The paper used in the photocopier by Pat’s office is said to be 0.097 mm thick. If it is folded over repeatedly, doubling its thickness each time, how thick will the paper be if it’s folded 7 times? Bonus: why, then, were the Mythbusters having so many problems trying to fold the paper this many times?

3.3. GEOMETRIC SEQUENCES AND SERIES 189

Answers to Section 3.3 Exercises

1. no

2. no

3. yes, r = 2

4. no

5. no

6. yes, r = 2 3

7. an = (3) n−1

and

{ a1 = 1

an = 3an−1

8. an = 64 (

1 4

)n−1 and

{ a1 = 64

an = an−1

9. an = 3(−2)n−1 and

{ a1 = 3

an = −2an−1

10. an = 24(0.1) n−1

and

{ a1 = 24

an = 0.1 ×an−1

11. an = 12 (

3 2

)n−1 , so a50 ≈ 5.1 × 109 and a261 ≈ 7.3 × 1046

12. an = 12 (

2 3

)n−1 , so a50 ≈ 2.8 × 10−8 and a261 ≈ 1.97 × 10−45

13. no

14. yes, with r = 2

15. yes, with r = 10

16. no

17. yes, with r = −1

18. no

19. an = 5(3) n−1

, so a201 = 5(3) 200 = 1.33 × 1096

20. an = 7(−2)n−1, so a20 = 7(−2)19 = −3, 670, 016

190 CHAPTER 3. SEQUENCES AND SERIES

21. S20 = 200 (the exact answer is 26214375 131072

or 1.99980926513671875, but if you round to three decimals, the answer is 200.000)

22. S20 = 104, 857, 500

23. S∞ = a1

1−r = −6

1−(−2/3) = − 18 5

= −3.6

24. S∞ = 200

25. S∞ does not exist (r > 1)

26. S∞ = 16

27. S11 = 2 2 + 23 + 24 + ... + 212 =

a1(1−rn) 1−r =

22(1−211) 1−2 = 8188

28. S∞ = 22.5

29. S∞ = 5 18

= 0.27

30. S∞ does not exist (r < −1)

31. 3 years is 36 months, so we have a 36-term sequence starting with 1, 2, 4, 8, . . . The nth term will be an = 1(2)

n−1 , so the 36th term will

be a36 = 1(2) 35

= 34, 359, 738, 368, which is a tad larger than the total population of Transylvania.

32. 1 man

7 wives

#sacks = #wives × #sacks/wife = 7 × 7 = 49

#cats = #sacks × #cats/sack = 49 × 7 = 343

#kits = #cats × #kits/cat = 343 × 7 = 2401

So kits, cats, sacks, and wives is the sequence 2401, 373, 49, 7, which is geometric with four terms: a1 = 2401 and r =

1 7 .

33. The paper is initially 0.097 mm thick with no folds. After one fold, the thickness will be 0.097×2, after two folds 0.097×2×2, etc. So our starting term (zero folds) will be a0 = 0.097 and then will double with r = 2 thereafter, where n is not only the index but also the number of folds made. So an = 0.097(2)

n , and the term with seven folds will be

a7 = 0.097(2) 7

= 12.416, so we can conclude that the paper thickness will be 12.4 mm, or just over 1 cm thick. (The Mythbusters realized that the problems with paperfolding lie with the fold itself, and making

3.3. GEOMETRIC SEQUENCES AND SERIES 191

the fold lie as flat as possible. If I remember correctly, they resorted to C-clamps and hitting the fold with a hammer to flatten it.)

192 CHAPTER 3. SEQUENCES AND SERIES

List of Symbols

p,q,r logical propositions

p negation of p

∧ and

∨ inclusive or

⊕ exclusive or

⇔ logically equivalent

→ conditional

↔ biconditional

A negation of A (Boolean)

· and (Boolean)

+ inclusive or (Boolean)

an n th term of a sequence

193

Index

absorption laws, 108

and, 45

associative laws, 99

base

2, 15

4, 3

8, 6

10, 1

16, 17

other than 10, 3

subscript notation, 3

biconditional, 135

binary, 15

Boolean algebra, 85

order of operations, 86

truth table for, 85

commutative laws, 99

complement laws, 98

conclusion, 121

conditional, 121

“or” form, 125

conjunction, 45

contrapositive, 124

and De Morgan’s laws, 126

converse, 123

conversion

from base 4

to decimal, 5

from binary

to decimal, 16

to hexadecimal, 36 to octal, 34

from decimal to binary, 28 to hexadecimal, 28 to octal, 27

from hexadecimal to binary, 35 to decimal, 18 to octal, 37

from octal to binary, 34 to decimal, 7 to hexadecimal, 36

De Morgan’s laws, 107 and contrapositive, 126

decimal system, 1 digital circuit, 83 disjunction

exclusive, 46 inclusive, 46

distributive laws, 107

equivalence, logical of propositions, 70

exclusive disjunction, 46 exclusive or, 46

gate, 83 gate representation

and, 83 not, 84

194

INDEX 195

or, 84 general formula, 149

hexadecimal, 17 hypothesis, 121

idempotent laws, 98 identity laws, 97 implies, 121 inclusive disjunction, 46 inclusive or, 46 inverse, 124

laws of logic, 97 absorption laws, 108 associative laws, 99 commutative laws, 99 complement laws, 98 De Morgan’s laws, 107 distributive laws, 107 idempotent laws, 98 identity laws, 97 proofs, 110 summary, 108

logic circuit, 83 logical equivalence

of propositions, 69, 70 using laws of logic, 100, 109

logical proposition, 43 simplifying with laws of logic, 100,

109

negation, 44 negative, 44 not, 44

octal, 6 or

exclusive, 46 inclusive, 46 vs. XOR, 47

or form of conditional, 125 order of operations

Boolean algebra, 86 propositions, 48

proofs using laws of logic, 110

proposition, 43 order of operations, 48 proofs, 110 truth table for, 67

quotient, 25

recursive formula, 151 remainder, 25

sequence, 145 defining, 149 general formula, 149 notation, 146 recursive formula, 151

switch, 83 switch representation

and, 83 or, 84

truth table for Boolean algebra, 85 for propositions, 67

XOR, 46 vs. or, 47

zero as unsigned number, 45

1 Binary, Octal, and Hexadecimal

1.1 Decimal and Octal

1.1.1 Review of the Decimal System
1.1.2 Bases Other Than Ten – How They Work
1.1.3 Octal
Exercises
Answers

1.2 Binary and Hexadecimal

1.2.1 Binary
1.2.2 Hexadecimal
Exercises
Answers

1.3 Converting from Decimal

1.3.1 Modular Arithmetic: Finding Quotient and Remainder
1.3.2 Using Quotient and Remainder to Convert from Decimal Form
Exercises
Answers

1.4 Converting between Binary, Octal, and Hexadecimal

1.4.1 Converting Between Binary and Octal
1.4.2 Converting Between Binary and Hexadecimal
1.4.3 Converting Between Octal and Hexadecimal
Exercises
Answers

2 Logic

2.1 Introduction to Logic

2.1.1 Propositions
2.1.2 Operators
2.1.3 Combining Two or More Propositions Using Connectives
Exercises
Answers

2.2 Venn Diagrams

2.2.1 Venn Diagrams with One Proposition
2.2.2 Venn Diagrams with Two Propositions
2.2.3 More complications
2.2.4 Negation and De Morgan's Laws
2.2.5 Venn Diagrams with Three Propositions
Exercises
Answers

2.3 Logical Equivalence

2.3.1 Truth Tables
2.3.2 Logical Equivalence
Exercises
Answers

2.4 Boolean Algebra

2.4.1 Logic Circuits
2.4.2 Gate Representations of Logic Circuits
2.4.3 Boolean Algebra
2.4.4 Boolean Syntax in Python
Exercises
Answers

2.5 Laws of Logic

2.5.1 Identity Laws
2.5.2 Idempotent Laws
2.5.3 Complement Laws
2.5.4 Commutative Laws
2.5.5 Associative Laws
2.5.6 Summary
2.5.7 Simplifying Logical Expressions
Exercises
Answers

2.6 More Laws of Logic

2.6.1 De Morgan's Laws
2.6.2 Distributive Laws
2.6.3 Absorption Laws
2.6.4 Summary
2.6.5 Simplifying Logical Expressions
2.6.6 Proofs
Exercises
Answers

2.7 The Conditional

2.7.1 The Conditional Connective
2.7.2 The Converse
2.7.3 The Contrapositive
2.7.4 The Inverse
2.7.5 The ``or'' form of the conditional
2.7.6 De Morgan's Law and the Contrapositive
Exercises
Answers

2.8 The Biconditional

2.8.1 The Biconditional Connective
2.8.2 Programming Applications
Exercises
Answers

3 Sequences and Series

3.1 Introduction to Sequences and Series

3.1.1 Sequences
3.1.2 Notation for Sequences
3.1.3 Counting the Terms in a Sequence
3.1.4 Defining a Sequence
3.1.5 General Formula
3.1.6 Recursive Definition
3.1.7 Fibonacci sequence
3.1.8 Series
3.1.9 Notation for Series
3.1.10 Sigma Notation
Exercises
Answers

3.2 Arithmetic Sequences and Series

3.2.1 Arithmetic Sequences
3.2.2 Recursive Definitions for Arithmetic Sequences
3.2.3 General Formulae for Arithmetic Sequences
3.2.4 Arithmetic Series
3.2.5 Summary
Exercises
Answers

3.3 Geometric Sequences and Series

3.3.1 Geometric Sequences
3.3.2 Recursive Definitions for Geometric Sequences
3.3.3 General Formulae for Geometric Sequences
3.3.4 Geometric Series
3.3.5 Sum of an Infinite Geometric Series
3.3.6 Repeating Decimals
3.3.7 Summary
Exercises
Answers

List of Symbols
Index