Logic and Discrete Mathematics E-Book

Willem Conradie

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 718

Veröffentlichungsjahr: 2015

Beschreibung

A concise yet rigorous introduction to logic and discrete mathematics.

This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade.

The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the semantics of classical logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete solutions which are available in the accompanying solutions manual.

Key Features:

• Suitable for a variety of courses for students in both Mathematics and Computer Science.
• Extensive, in-depth coverage of classical logic, combined with a solid exposition of a selection  of the most important fields of discrete mathematics
• Concise, clear and uncluttered presentation with numerous examples.
• Covers some applications including cryptographic systems, discrete probability and network algorithms.

Logic and Discrete Mathematics: A Concise Introduction is aimed mainly at undergraduate courses for students in mathematics and computer science, but the book will also be a valuable resource for graduate modules and for self-study.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

List of Boxes

Preface

Acknowledgements

About the Companion Website

Chapter 1: Preliminaries

1.1 Sets

1.2 Basics of logical connectives and expressions

1.3 Mathematical induction

Chapter 2: Sets, Relations, Orders

2.1 Set inclusions and equalities

2.2 Functions

2.3 Binary relations and operations on them

2.4 Special binary relations

2.5 Equivalence relations and partitions

2.6 Ordered sets

2.7 An introduction to cardinality

2.8 Isomorphisms of ordered sets. Ordinal numbers

2.9 Application: relational databases

Chapter 3: Propositional Logic

3.1 Propositions, logical connectives, truth tables, tautologies

3.2 Propositional logical consequence. Valid and invalid propositional inferences

3.3 The concept and use of deductive systems

3.4 Semantic tableaux

3.5 Logical equivalences. Negating propositional formulae

3.6 Normal forms. Propositional resolution

Chapter 4: First-Order Logic

4.1 Basic concepts of first-order logic

4.2 The formal semantics of first–order logic

4.3 The language of first-order logic: a deeper look

4.4 Truth, logical validity, equivalence and consequence in first-order logic

4.5 Semantic tableaux for first-order logic

4.6 Prenex and clausal normal forms

4.7 Resolution in first-order logic

4.8 Applications of first-order logic to mathematical reasoning and proofs

Chapter 5: Number Theory

5.1 The principle of mathematical induction revisited

5.2 Divisibility

5.3 Computing greatest common divisors. Least common multiples

5.4 Prime numbers. The fundamental theorem of arithmetic

5.5 Congruence relations

5.6 Equivalence classes and residue systems modulo

n

5.7 Linear Diophantine equations and linear congruences

5.8 Chinese remainder theorem

5.9 Euler's function. Theorems of Euler and Fermat

5.10 Wilson's theorem. Order of an integer

5.11 Application: public key cryptography

Chapter 6: Combinatorics

6.1 Two basic counting principles

6.2 Combinations. The binomial theorem

6.3 The principle of inclusion–exclusion

6.4 The Pigeonhole Principle

6.5 Generalized permutations, distributions and the multinomial theorem

6.6 Selections and arrangements with repetition; distributions of identical objects

6.7 Recurrence relations and their solution

6.8 Generating functions

6.9 Recurrence relations and generating functions

6.10 Application: classical discrete probability

Chapter 7: Graph Theory

7.1 Introduction to graphs and digraphs

7.2 Incidence and adjacency matrices

7.3 Weighted graphs and path algorithms

7.4 Trees

7.5 Eulerian graphs and Hamiltonian graphs

7.6 Planar graphs

7.7 Graph colourings

Index

End User License Agreement

Pages

xvii

xviii

xix

xxi

xxiii

1

2

3

4

5

6

7

8

9

10

11

12

13

14

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

419

420

421

422

423

424

425

426

Guide

Cover

Table of Contents

Preface

Begin Reading

List of Illustrations

Figure 2.1

Figure 2.2

Figure 2.3

Figure 2.4

Figure 2.5

Figure 2.6

Figure 2.7

Figure 2.8

Figure 6.1

Figure 6.2

Figure 6.3

Figure 6.4

Figure 6.5

Figure 6.6

Figure 7.1

Figure 7.2

Figure 7.3

Figure 7.4

Figure 7.5

Figure 7.6

Figure 7.7

Figure 7.8

Figure 7.9

Figure 7.10

Figure 7.11

Figure 7.12

Figure 7.13

Figure 7.14

Figure 7.15

Figure 7.16

Figure 7.17

Figure 7.18

List of Tables

Table 1.1

Table 2.1

Table 2.2

Table 2.3

Table 2.4

Table 2.5

Table 2.6

Table 2.7

Table 2.8

Table 2.9

Table 2.10

Table 2.11

Table 2.12

Table 2.13

Table 6.1

Table 6.2

Table 6.3

Logic and Discrete Mathematics

A Concise Introduction

Willem Conradie

University of JohannesburgSouth Africa

Valentin Goranko

Stockholm University, Sweden

This edition first published 2015

© 2015 John Wiley and Sons Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought

Library of Congress Cataloging-in-Publication Data

Conradie, Willem, 1978- author.

Logic and discrete mathematics : a concise introduction / Willem Conradie, Valentin Goranko.

pages cm

Includes index.

ISBN 978-1-118-75127-5 (pbk.)

1. Logic, Symbolic and mathematical–Textbooks. 2. Computer science–Mathematics–Textbooks.

I. Goranko, Valentin, author. II. Title.

QA9.C7423 2015

511.3–dc23

2014035964

A catalogue record for this book is available from the British Library.

Front cover image: Narrow walkway inside the Great Enclosure at the Great Zimbabwe ruins. Reproduced by kind permission of Kenneth Meeks.

List of Boxes

1. Preliminaries

Paradoxes

2. Sets, Relations, Orders

Russell's paradox

Georg Cantor

The notation of set theory

Fuzzy sets

Zermelo–Fraenkel set theory

The axiom of choice

The continuum hypothesis

Hilbert's Hotel

Charles Sanders Peirce

3. Propositional Logic

Aristotle

George Boole

David Hilbert

Early proof theory

Augustus De Morgan

The Boolean satisfiability problem and NP-completeness

4. First-Order Logic

Gottlob Frege

Giuseppe Peano

Bertrand Russell

Alfred Tarski

Kurt Gödel

Thoralf Skolem

Alonzo Church

Alan Turing

5. Number Theory

Carl Friedrich Gauss

Pythagoras of Samos

Euclid of Alexandria

Primality testing

Richard Dedekind

Babylonian mathematics

Diophantus of Alexandria

Ancient Chinese mathematics

Pierre de Fermat

Ancient and Medieval Indian and Arabic mathematics

History of codes and ciphers

6. Combinatorics

Stirling's approximation of n!

Pascal's triangle

Venn diagrams

Lejeune Dirichlet

Braille

Blaise Pascal

Fibonacci

Combinatorial games: Nim

Fibonacci numbers and the golden ratio

Pierre-Simon de Laplace

7. Graph Theory

Leonhard Euler

Ramsey theory

Edsger Dijkstra

Paul Erdõs

William Hamilton

Graph theory and Sudoku

The four-colour problem

Preface

Discrete Mathematics1 refers to a range of mathematical disciplines that study discrete structures and phenomena, unlike other classical fields of mathematics, such as analysis, geometry and topology, which study continuous structures, processes and transformations. Intuitively put, discrete structures – such as the linear order of natural numbers or the set of cities and towns in a country together with the roads between them – consists of separable, discretely arranged objects, whereas continuous structures – such as the trajectory of a moving object, the real line, the Euclidian plane or a sphere – are densely filled, with no “gaps”. The more important distinction, however, is between the types of problems studied and solved in discrete and continuous mathematics and also between the main ideas and techniques that underly and characterize these two branches of mathematics. Nevertheless, this distinction is often blurred and many ideas, methods and results from each of these branches have been fruitfully applied to the other.

The intuitive explanation above is not meant to define what should be classified as Discrete Mathematics, as every such definition would be incomplete or debatable. A more useful description would be to list what we consider to be the basic mathematical disciplines traditionally classified as Discrete Mathematics and included in most university courses on that subject: the Theory of Sets and Relations, Mathematical Logic, Number Theory, Graph Theory and Combinatorics. These are the topics covered in this book. Sometimes textbooks and courses on Discrete Mathematics also include Abstract Algebra, Classical Probability Theory, Automata Theory, etc. These topics are not included here, mainly for practical reasons.

Logic was born in the works of Aristotle as a philosophical study of reasoning some 25 centuries ago. Over the past 150 years it has gradually developed as a fundamental mathematical discipline, which nowadays has deep and mature mathematical content and also applications spreading far beyond foundational and methodological issues. While the field of Mathematical Logic is often regarded as included in the broad scope of Discrete Mathematics, in this book it is treated essentially on a par with it.

As mathematical fields of their own importance, both Logic and Discrete Mathematics are relatively young and very dynamically developing disciplines, especially since the mid 20th century, when the computer era began. Many of the most exciting current developments in Logic and Discrete Mathematics are motivated and inspired by applications in Computer Science, Artificial Intelligence and Bioinformatics. We have accordingly included some such selected applications in the book.

About the book

The work on this book started more than a decade ago as a loose collection of lecture notes that we wrote and used to teach courses on Logic and Discrete Mathematics, partly because we could not find available suitable textbooks that would meet our needs and requirements. Eventually we decided to write a book of our own, which would best reflect the content and features we consider most important:

1.

Being logicians, we have provided a much more detailed and deeper treatment of Logic than is usual in textbooks on Discrete Mathematics. We believe that such a treatment is necessary for the proper understanding and use of Logic as a mathematical and general reasoning tool, and we consider it a distinguishing feature of the book.

2.

We included only what we consider to be the core disciplines within the field of Discrete Mathematics (without claiming that ours is the only good choice) but have treated these disciplines in considerable depth for an undergraduate text. That enabled us to keep the book within reasonable size limits without compromising on the content and exposition of the topics included.

3.

We have tried to keep the exposition clear and concise while still including the necessary technical detail and illustrating concepts and techniques with numerous examples.

4.

We have included comprehensive sets of exercises, most of them provided with answers or solutions in an accompanying solutions manual.

5.

We have also included “boxes” at the end of each section. Some contain mathematics titbits or applications of the content in the section. Others are short biographies of distinguished scientists who have made fundamental contributions to Discrete Mathematics. We hope the reader will find it inspiring to learn a little about their lives and their contributions to the fields covered in the book.

To the instructor

We have aimed this book to be suitable for a variety of courses for students in both Mathematics and Computer Science. Some parts of it are much more relevant to only one of these audiences and we have indicated them by introducing Mathematics Track and Computer Science Track markers in the text. We regard everything not explicitly on either of these tracks to be suitable for both groups.

In addition, the book can be used for designing courses on different undergraduate or lower graduate levels. Some material that could reasonably be omitted in courses at a lower undergraduate level is indicated with an Advances Track marker. These tracks are, of course, only suggestions, which should serve as our recommendations to the instructor.

The single stars shown in the exercises are deemed to be exercises that are more difficult, while the double stars are considered to be exercises that are challenging.

The whole book can be comfortably covered in two semester courses, or various selections can be made for a single semester course. Apart from assuming knowledge of the background material in the preliminary Chapter 1, the chapters are essentially independent and can be taught in any order. The only exception is Chapter 4 on first-order logic, which presupposes knowledge of the material on propositional logic covered in Chapter 3. Also, much of the content of Chapter 2 covers general mathematical background, useful for the rest of the book.

1

 Not to be confused with discreetly done mathematics!

Acknowledgements

A number of people have contributed, one way or another, to our work on this book over the years.With the risk of inadvertently omitting some names, forwhich we apologize in advance, we would like to thank Gerhard Benadé, Thomas Bolander, Izak Broere, Ruaan Kellerman, Heidi Maartens, Chantel Marais and Claudette Robinson for helpful feedback, comments, technical or editorial corrections and some solutions to exercises. Besides them, thanks are due to many students at the University of Johannesburg, the University of theWitwatersrand and the Technical University of Denmark, who pointed out some errors in earlier versions of the manuscript.We thank Justin Southey for the use of the GraphScribe application authored by him, which greatly speeded up the drawing of some combinatorial graphs, and also for his suggestions on the applications of Graph Theory. Valentin is also grateful to Nina Ninova for her general support during the work on this book as well as help with collecting photos and references formany of the historical boxes.Willem would like to thank Dion Govender for his patience and support during the final months of intense work on the book. Last but not least, we wish to thank Richard Davies, Audrey Koh, Kathryn Sharples, Mark Styles and Jo Taylor from Wiley as well as Krupa Muthu from Laserwords for their kind support and technical advice during the work on this book.

About the Companion Website

This book is accompanied by a companion website:

www.wiley.com/go/conradie/logic

The website includes:

Lecture Slides

Quizzes

Chapter 1Preliminaries

1.1 Sets

1.2 Basics of logical connectives and expressions

1.3 Mathematical induction

Here we briefly review some minimal background knowledge that we will assume in the rest of the book. Besides a small amount of that nebulous quality called “mathematical maturity”, we only expect some basic concepts from set theory and mathematical indiction. The reader who is familiar with these concepts can safely skip on to the next chapter.

Some notation

We denote the set of natural numbers by . There is some inconsistency in the mathematical literature as to whether belongs to the natural numbers or not: some authors choose to include it, other do not. For our purposes it is convenient to include as a natural number. Other number sets which will be of importance to us include the sets of integers , positive integers , rational numbers , positive rational numbers , real numbers , and positive real numbers .

The product of the first positive integers turns up in many mathematical situations. It is therefore convenient to have a more compact notation for it. We accordingly define and , for . We read as ‘ factorial’. The definition of as is not supposed to carry any intuitive meaning: it is simply a useful convention.

1.1 Sets

Sets and elements

By a set we intuitively mean a collection of objects of any nature (numbers, people, concepts, sets themselves, etc.) that is considered as a single entity. The objects in that collection are called elements of the set. If an object is an element of a set , we denote that fact by

otherwise we write

We also say that is a member of the set or that belongs to. If a set has finitely many elements (here we rely on your intuition of what finite is), we can describe it precisely by listing all of them, for example:

We often rely on our common intuition and use ellipses, as in

We sometimes go further and use the same for infinite sets; for example, the set of natural numbers can be specified as

Further we will discuss a more universal method of describing sets.

Equality and containment of sets

Two sets are declared equal if and only if they have the same elements. In other words, the sets and are equal, denoted as usual by , if every element of is an element of and every element of is an element of . For example, the sets and are equal, and so are the sets , and .

A set is a subset of a set , denoted , if every element of is an element of . If , we also say that is included in, or that contains. For example, . Note that every set is a subset of itself.

The following facts are very useful. They are direct consequences of the definitions of equality and containment of sets.

Two sets

and

are equal if, and only if,

and

.

A set

is not a subset of a set

, denoted

, if, and only if, there is an element of

that is not an element of

.

A set

is not equal to a set

if

is not a subset of

or

if

is not a subset of

.

A set is a proper subset of a set , denoted or , if and . In other words, is a proper subset of if is a subset of and is not a subset of , i.e. if at least one element of is not in