Logic and Discrete Mathematics (eBook)
John Wiley & Sons (Verlag)
978-1-118-76109-0 (ISBN)
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:
|
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.
Willem Conradie, University of Johannesburg, South Africa
Valentin Goranko, University of Stockholm, Sweden
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.
Willem Conradie, University of Johannesburg, South Africa. Valentin Goranko, University of Stockholm, Sweden.
Preface xvii
Acknowledgements xxi
About the Companion Website xxiii
1. Preliminaries 1
1.1 Sets 2
1.1.1 Exercises 7
1.2 Basics of logical connectives and expressions 9
1.2.1 Propositions, logical connectives, truth tables, tautologies 9
1.2.2 Individual variables and quantifiers 12
1.2.3 Exercises 15
1.3 Mathematical induction 17
1.3.1 Exercises 18
2. Sets, Relations, Orders 20
2.1 Set inclusions and equalities 21
2.1.1 Properties of the set theoretic operations 22
2.1.2 Exercises 26
2.2 Functions 28
2.2.1 Functions and their inverses 28
2.2.2 Composition of mappings 31
2.2.3 Exercises 33
2.3 Binary relations and operations on them 35
2.3.1 Binary relations 35
2.3.2 Matrix and graphical representations of relations on finite sets 38
2.3.3 Boolean operations on binary relations 39
2.3.4 Inverse and composition of relations 41
2.3.5 Exercises 42
2.4 Special binary relations 45
2.4.1 Properties of binary relations 45
2.4.2 Functions as relations 47
2.4.3 Reflexive, symmetric and transitive closures of a relation 47
2.4.4 Exercises 49
2.5 Equivalence relations and partitions 51
2.5.1 Equivalence relations 51
2.5.2 Quotient sets and partitions 53
2.5.3 The kernel equivalence of a mapping 56
2.5.4 Exercises 57
2.6 Ordered sets 59
2.6.1 Pre-orders and partial orders 59
2.6.2 Graphical representing posets: Hasse diagrams 61
2.6.3 Lower and upper bounds. Minimal and maximal elements 63
2.6.4 Well-ordered sets 65
2.6.5 Exercises 67
2.7 An introduction to cardinality 69
2.7.1 Equinumerosity and cardinality 69
2.7.2 Exercises 73
2.8 Isomorphisms of ordered sets. Ordinal numbers 75
2.8.1 Exercises 79
2.9 Application: relational databases 80
2.9.1 Exercises 86
3. Propositional Logic 89
3.1 Propositions, logical connectives, truth tables, tautologies 90
3.1.1 Propositions and propositional connectives. Truth tables 90
3.1.2 Some remarks on the meaning of the connectives 90
3.1.3 Propositional formulae 91
3.1.4 Construction and parsing tree of a propositional formula 92
3.1.5 Truth tables of propositional formulae 93
3.1.6 Tautologies 95
3.1.7 A better idea: search for a falsifying truth assignment 96
3.1.8 Exercises 97
3.2 Propositional logical consequence. Valid and invalid propositional inferences 101
3.2.1 Propositional logical consequence 101
3.2.2 Logically sound rules of propositional inference. Logically correct propositional arguments 104
3.2.3 Fallacies of the implication 106
3.2.4 Exercises 107
3.3 The concept and use of deductive systems 109
3.4 Semantic tableaux 113
3.4.1 Exercises 117
3.5 Logical equivalences. Negating propositional formulae 121
3.5.1 Logically equivalent propositional formulae 121
3.5.2 Some important equivalences 123
3.5.3 Exercises 124
3.6 Normal forms. Propositional resolution 126
3.6.1 Conjunctive and disjunctive normal forms of propositional formulae 126
3.6.2 Clausal form. Clausal resolution 129
3.6.3 Resolution-based derivations 130
3.6.4 Optimizing the method of resolution 131
3.6.5 Exercises 132
4. First-Order Logic 135
4.1 Basic concepts of first-order logic 136
4.1.1 First-order structures 136
4.1.2 First-order languages 138
4.1.3 Terms and formulae 139
4.1.4 The semantics of first-order logic: an informal outline 143
4.1.5 Translating first-order formulae to natural language 146
4.1.6 Exercises 147
4.2 The formal semantics of first-order logic 152
4.2.1 Interpretations 152
4.2.2 Variable assignment and term evaluation 153
4.2.3 Truth evaluation games 156
4.2.4 Exercises 159
4.3 The language of first-order logic: a deeper look 161
4.3.1 Translations from natural language into first-order languages 161
4.3.2 Restricted quantification 163
4.3.3 Free and bound variables. Scope of a quantifier 164
4.3.4 Renaming of a bound variable in a formula. Clean formulae 165
4.3.5 Substitution of a term for a variable in a formula. Capture of a variable 166
4.3.6 Exercises 167
4.4 Truth, logical validity, equivalence and consequence in first-order logic 171
4.4.1 More on truth of sentences in structures. Models and countermodels 171
4.4.2 Satisfiability and validity of first-order formulae 172
4.4.3 Logical equivalence in first-order logic 173
4.4.4 Some logical equivalences involving quantifiers 174
4.4.5 Negating first-order formulae 175
4.4.6 Logical consequence in first-order logic 176
4.4.7 Exercises 180
4.5 Semantic tableaux for first-order logic 185
4.5.1 Some derivations using first-order semantic tableau 186
4.5.2 Semantic tableaux for first-order logic with equality 189
4.5.3 Discussion on the quantifier rules and on termination of semantic tableaux 189
4.5.4 Exercises 191
4.6 Prenex and clausal normal forms 195
4.6.1 Prenex normal forms 195
4.6.2 Skolemization 197
4.6.3 Clausal forms 198
4.6.4 Exercises 199
4.7 Resolution in first-order logic 201
4.7.1 Propositional resolution rule in first-order logic 201
4.7.2 Substitutions of terms for variables revisited 201
4.7.3 Unification of terms 202
4.7.4 Resolution with unification in first-order logic 204
4.7.5 Examples of resolution-based derivations 205
4.7.6 Resolution for first-order logic with equality 207
4.7.7 Optimizations of the resolution method for first-order logic 207
4.7.8 Exercises 207
4.8 Applications of first-order logic to mathematical reasoning and proofs 211
4.8.1 Proof strategies: direct and indirect proofs 211
4.8.2 Tactics for logical reasoning 215
4.8.3 Exercises 216
5. Number Theory 219
5.1 The principle of mathematical induction revisited 220
5.1.1 Exercises 222
5.2 Divisibility 224
5.2.1 Basic properties of divisibility 224
5.2.2 Division with a remainder 224
5.2.3 Greatest common divisor 225
5.2.4 Exercises 227
5.3 Computing greatest common divisors. Least common multiples 230
5.3.1 Euclid's algorithm for computing greatest common divisors 230
5.3.2 Least common multiple 232
5.3.3 Exercises 233
5.4 Prime numbers. The fundamental theorem of arithmetic 236
5.4.1 Relatively prime numbers 236
5.4.2 Prime numbers 237
5.4.3 The fundamental theorem of arithmetic 238
5.4.4 On the distribution of prime numbers 239
5.4.5 Exercises 240
5.5 Congruence relations 243
5.5.1 Exercises 246
5.6 Equivalence classes and residue systems modulo n 248
5.6.1 Equivalence relations and partitions 248
5.6.2 Equivalence classes modulo n. Modular arithmetic 249
5.6.3 Residue systems 250
5.6.4 Multiplicative inverses in Zn 251
5.6.5 Exercises 251
5.7 Linear Diophantine equations and linear congruences 253
5.7.1 Linear Diophantine equations 253
5.7.2 Linear congruences 254
5.7.3 Exercises 256
5.8 Chinese remainder theorem 257
5.8.1 Exercises 259
5.9 Euler's function. Theorems of Euler and Fermat 261
5.9.1 Theorems of Euler and Fermat 262
5.9.2 Exercises 264
5.10 Wilson's theorem. Order of an integer 266
5.10.1 Wilson's theorem 266
5.10.2 Order of an integer 266
5.10.3 Exercises 267
5.11 Application: public key cryptography 269
5.11.1 About cryptography 269
5.11.2 The idea of public key cryptography 269
5.11.3 The method RSA 270
5.11.4 Exercises 271
6. Combinatorics 274
6.1 Two basic counting principles 275
6.1.1 Exercises 281
6.2 Combinations. The binomial theorem 284
6.2.1 Counting sheep and combinations 284
6.2.2 Some important properties 286
6.2.3 Pascal's triangle 287
6.2.4 The binomial theorem 287
6.2.5 Exercises 289
6.3 The principle of inclusion-exclusion 293
6.3.1 Exercises 296
6.4 The Pigeonhole Principle 299
6.4.3 Exercises 302
6.5 Generalized permutations, distributions and the multinomial theorem 304
6.5.1 Arranging nondistinct objects 304
6.5.2 Distributions 306
6.5.3 The multinomial theorem 308
6.5.4 Summary 310
6.5.5 Exercises 311
6.6 Selections and arrangements with repetition; distributions of identical objects 312
6.6.1 Selections with repetition 312
6.6.2 Distributions of identical objects 314
6.6.3 Arrangements with repetition 315
6.6.4 Summary 316
6.6.5 Exercises 316
6.7 Recurrence relations and their solution 318
6.7.1 Recurrence relations. Fibonacci numbers 318
6.7.2 Catalan numbers 319
6.7.3 Solving homogeneous linear recurrence relations 322
6.7.4 Exercises 327
6.8 Generating functions 329
6.8.1 Introducing generating functions 329
6.8.2 Computing coefficients of generating functions 332
6.8.3 Exercises 335
6.9 Recurrence relations and generating functions 337
6.9.1 Exercises 341
6.10 Application: classical discrete probability 343
6.10.1 Common sense probability 343
6.10.2 Sample spaces 343
6.10.3 Discrete probability 345
6.10.4 Properties of probability measures 346
6.10.5 Conditional probability and independent events 348
6.10.6 Exercises 352
7. Graph Theory 356
7.1 Introduction to graphs and digraphs 357
7.1.1 Graphs 357
7.1.2 Digraphs 364
7.1.3 Exercises 367
7.2 Incidence and adjacency matrices 370
7.2.1 Exercises 374
7.3 Weighted graphs and path algorithms 377
7.3.1 Dijkstra's algorithm 378
7.3.2 The Floyd-Warshall algorithm 381
7.3.3 Exercises 383
7.4 Trees 385
7.4.1 Undirected trees 385
7.4.2 Computing spanning trees: Kruskal's algorithm 388
7.4.3 Rooted trees 390
7.4.4 Traversing rooted trees 392
7.4.5 Exercises 393
7.5 Eulerian graphs and Hamiltonian graphs 395
7.5.1 Eulerian graphs and digraphs 396
7.5.2 Hamiltonian graphs and digraphs 398
7.5.3 Exercises 400
7.6 Planar graphs 404
7.6.1 Exercises 408
7.7 Graph colourings 411
7.7.1 Colourings 411
7.7.2 The four- and five-colour theorems 413
7.7.3 Exercises 414
Index 419
"This is a very well-written brief introduction to discrete mathematics that emphasizes logic and set theory and has shorter sections on number theory, combinatorics, and graph theory." (MAA Reviews, 4 January 2016)
Chapter 1
Preliminaries
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 . In particular, no set is a proper subset of itself. If is not a proper subset of , we denote that by .
The empty set
Amongst all sets there is one that is particularly special. That is the empty set, i.e. the set that has no elements. By definition of equality of sets, there is only one empty set. One might think that the empty set is a useless abstraction. On the contrary, it is a very important set, and probably the most commonly used one in mathematics (like the number 0 is the most commonly used number). That is why it has a special notation: .
Sets and properties. Set-builder notation
We cannot always list the elements of a set, even if it is finite, so we need a more universal method for specifying sets. The commonly used method is to describe the property that determines membership of the set, e.g.:
“ is the set of all objects such that .”
where “” is a certain property (predicate) involving . We use the following convenient notation, called the set-builder notation for the set described above:
Here are some examples:
- defines the set of negative real numbers;
- defines the set of students in the MATH3029 class.
- defines the set .
- defines the set of rational numbers.
Sometimes, we use the set-builder notation more liberally and, for instance, describe the set of rational numbers as or the set of positive real numbers as .
Operations on sets
We describe below the basic operations on sets.
- Intersection. The intersection of two sets and is the set
consisting of all elements that are both in and in . If , then and are called disjoint.
- Union. The union of two sets and is the set
consisting of all elements that are in at least one of and .
- Difference. The difference of the sets and is the set
consisting of all elements that are in but not in . An alternative notation for is .
For example, if and then , , and .
Universal sets and complements of sets
Often, all sets that we consider are subsets of one set, called the domain of discourse. We also call that set the universe or the universal set. For example, in arithmetic, the universe is usually the set of natural numbers or the set of integers, while in algebra and calculus, the universe is the set of real numbers; talking about humans, the universe is the set of all humans, etc.
Definition 1.1.1
Let a universal set be fixed and . The complement of (with respect to ) is the set
The complement of a set is sometimes also denoted by .
Thus, the complement of consists of those objects from the universal set that do not belong to . For example, if the universal set is , then the complement of the interval is ; the complement of is the set of irrational numbers.
Powersets
The power set of a set is the set of all subsets of :
Here are some examples:
- ;
- , in particular, ;
- ;
- .
Cartesian products of sets
In order to introduce the next operation we need the notion of ordered pair. Let , be any objects. Intuitively, the ordered pair of and , denoted (do not confuse this with an open interval of real numbers!), is something like a set consisting of as a first element (or first component) and as a second element (or second component). Thus, if , then the ordered pair is different from the ordered pair and each of these is different from the set because the elements of a set are not ordered. In particular, the ordered pair is different from the set . Here is a formal definition of an ordered pair as a set that satisfies the intuition:
Definition 1.1.2
Given the objects and , the ordered pair is the set .
Here is the fundamental property of ordered pairs:
Proposition 1.1.3
The ordered pairs and are equal if and only if and .
Proof:
Exercise.
Definition 1.1.4
The Cartesian product of the sets and is the set
consisting of all ordered pairs where the first component comes from and the second component comes from . In particular, we denote by and call it the Cartesian square of .
For example, if , then
while
Note that if or is empty, then is empty too. Moreover, if has elements and has elements, then has elements (why?). This is one of the reasons for the term “product”.
The Cartesian coordinate system in the plane is a representation of the plane as the Cartesian1 square of the real line , where we associate a unique ordered pair of real numbers (its coordinates) with every point in the plane.
The notion of an ordered pair can be generalized to ordered -tuple-tuple, for any . An -tuple is an object of the type where the order of the components matters. We will not give a formal set theoretic definition in the style of Definition 1.2.1, but leave this as an exercise (Exercise 11).
Accordingly, the Cartesian product can be extended to sets:
As before, we will use the notation for .
Relations
Relations, also called predicates, are ubiquitous in mathematics. Relations between numbers like “being equal”, “being less than” and “being divisible by” come to mind at once. As these examples indicate, many of the relations we commonly encounter are binary, i.e., relations relating two objects at a time. It will be convenient for us to identify a binary relation with the set of all ordered pairs of elements that stand in that relation. We thus have the following definition:
Definition 1.1.5
A binary relation on a set is any subset of .
For example the relation on the...
| Erscheint lt. Verlag | 28.4.2015 |
|---|---|
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre |
| Technik | |
| Schlagworte | Computer Science • Discrete Mathematics • discrete mathematics, logic, first-order logic, propositional logic, predicate logic, set theory, combinatorics, counting techniques, graph theory, number theory, cryptography, probability, binomial theorem, cardinality, Chinese remainder theorem, deductive system, Diophantine equations, Euclidean algorithm, inclusion–exclusion principle, inference rule, algorithm, arithmetic, arrangement, axiom, bijection, Boolean, cardinal number, clausal form, combination, congruence, countable set, Deduction, logical, d • Diskrete Mathematik • Informatik • Logic & Foundations • Logik u. Grundlagen der Mathematik • Mathematics • Mathematik |
| ISBN-10 | 1-118-76109-X / 111876109X |
| ISBN-13 | 978-1-118-76109-0 / 9781118761090 |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
EPUB (Adobe DRM)Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: EPUB (Electronic Publication)
EPUB ist ein offener Standard für eBooks und eignet sich besonders zur Darstellung von Belletristik und Sachbüchern. Der Fließtext wird dynamisch an die Display- und Schriftgröße angepasst. Auch für mobile Lesegeräte ist EPUB daher gut geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
