Logic and Discrete Mathematics

Name: Logic and Discrete Mathematics | A Concise Introduction
Brand: Wiley
Price: 41.99 EUR
Availability: OnlineOnly

A Concise Introduction

Willem Conradie Valentin Goranko(Autor*in)

Wiley (Verlag)

Erschienen am 28. April 2015

456 Seiten

E-Book

ePUB mit Adobe-DRM

Systemvoraussetzungen

978-1-118-76109-0 (ISBN)

41,99 €inkl. 7% MwSt.

Systemvoraussetzungen

für ePUB mit Adobe-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Personen

Inhalt

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

Chapter 1
Preliminaries

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 . 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...

Systemvoraussetzungen

Als PDF speichern Als Link merken

Logic and Discrete Mathematics

Beschreibung

Rezensionen / Stimmen

Weitere Details

Weitere Ausgaben

Personen

Inhalt

Chapter 1 Preliminaries

Some notation

1.1 Sets

Sets and elements

Equality and containment of sets

The empty set

Sets and properties. Set-builder notation

Operations on sets

Universal sets and complements of sets

Definition 1.1.1

Powersets

Cartesian products of sets

Definition 1.1.2

Proposition 1.1.3

Definition 1.1.4

Relations

Definition 1.1.5

Systemvoraussetzungen

Chapter 1
Preliminaries