Logic and Discrete Mathematics : A Concise Introduction.

Intro -- Title Page -- Copyright -- Table of Contents -- 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.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.