Discrete Mathematics Foundations for Computer Science and Symbolic Artificial Intelligence

Table of Contents

• Preface — 11
• Chapter 1 - Computational and Mathematical Foundations of Symbolic Artificial Intelligence — 15
  • 1.1 Introduction — 15
  • 1.2 Computer Science as a Science of Representation, Formalization, and Processing — 16
    • 1.2.1 Nature and Object of Computer Science — 16
    • 1.2.2 Representation, Algorithms, and Formalization — 16
    • 1.2.3 Logical, Linguistic, and Structural Foundations — 17
    • 1.2.4 Computer Science, Systems, and Execution Environments — 17
    • 1.2.5 Computer Science and the Scope of Discrete Mathematics — 17
  • 1.3 Symbolic Artificial Intelligence as a Formal Extension of Computer Science — 18
    • 1.3.1 General Definition of Artificial Intelligence — 18
    • 1.3.2 Computational Anchoring of Artificial Intelligence — 18
    • 1.3.3 From Artificial Intelligence in General to Symbolic Artificial Intelligence — 18
    • 1.3.4 Knowledge Representation, Rules, and Reasoning — 19
    • 1.3.5 Transparency, Explainability, and Methodological Value — 19
    • 1.3.6 Brief Perspective on Other Paradigms — 19
  • 1.4 Discrete Mathematics: Nature, Object, and Specificity — 22
    • 1.4.1 General Definition — 22
    • 1.4.2 Difference Between Discrete Mathematics and Continuous Mathematics — 22
    • 1.4.3 Objects, Structures, and Modes of Reasoning — 22
    • 1.4.4 Major Domains of Discrete Mathematics — 23
    • 1.4.5 Intellectual Function and Formative Value — 23
  • 1.5 Discrete Mathematics at the Foundation of Computer Science — 23
  • 1.6 Discrete Mathematics at the Foundation of Symbolic Artificial Intelligence — 24
  • 1.7 Intersections, Complementarities, and the Guiding Line of the Book — 24
  • 1.8 Conclusion and Transition to Set Theory — 25
• Chapter 2 - Set Theory, Mappings, and Relations — 27
  • 2.1 Introduction — 27
  • 2.2 Sets — 27
    • 2.2.1 Definition and Notation — 27
    • 2.2.2 Representation — 28
    • 2.2.3 Subsets — 29
    • 2.2.4 Equal Sets — 29
    • 2.2.5 Fundamental Conventions — 30
    • 2.2.6 Power Set — 30
    • 2.2.7 Cartesian Product — 30
  • 2.3 Operations on Sets — 31
    • 2.3.1 Intersection — 31
    • 2.3.2 Union — 32
    • 2.3.3 Complements — 32
  • 2.4 Properties of ∪ and ∩ Operators — 33
    • 2.4.1 Idempotence — 34
    • 2.4.2 Commutativity — 34
    • 2.4.3 Associativity — 34
    • 2.4.4 Distributivity — 34
    • 2.4.5 Properties Involving ∅and U — 35
    • 2.4.6 De Morgan’s Laws — 35
  • 2.5 Mappings — 36
    • 2.5.1 Definition — 36
    • 2.5.2 Injection — 37
    • 2.5.3 Surjection — 37
    • 2.5.4 Bijection — 38
  • 2.6 Relations — 38
    • 2.6.1 Properties of Relations — 39
    • 2.6.2 Particular Types of Relations — 40
  • 2.7 Set Theory in Artificial Intelligence — 41
    • 2.7.1 Knowledge Representation Based on Sets — 42
    • 2.7.2 Equivalence Relations and Classification — 42
    • 2.7.3 Inference Systems and Rule Bases — 42
    • 2.7.4 Symbolic Learning and Induction — 43
  • 2.8 Conclusion of the Chapter — 43
  • 2.9 Exercises — 45
  • 2.10 Solutions — 48
• Chapter 3 - Cardinality and Combinatorics — 55
  • 3.1 Introduction — 55
  • 3.2 Cardinality of a Set — 56
    • 3.2.1 Definition and Notation — 56
    • 3.2.2 Cardinality of a Cartesian Product — 56
    • 3.2.3 Operations on Cardinalities — 57
  • 3.3 Finite and Countable Sets — 60
    • 3.3.1 Finite Sets — 60
    • 3.3.2 Countable Sets — 60
    • 3.3.3 Fundamental Theorems on Countable Sets — 61
  • 3.4 Combinatorics — 62
    • 3.4.1 Permutations — 62
    • 3.4.2 Arrangements — 62
    • 3.4.3 Combinations — 63
    • 3.4.4 Pascal’s Triangle — 65
    • 3.4.5 Newton’s Binomial Formula — 65
  • 3.5 Combinatorics in Artificial Intelligence — 67
    • 3.5.1 Combinatorial Search and Optimization — 67
  • 3.6 Conclusion of the Chapter — 67
  • 3.7 Exercises — 69
  • 3.8 Solutions — 72
• Chapter 4 - Combinatorial Probability — 79
  • 4.1 Introduction — 79
  • 4.2 Fundamental Definitions — 79
    • 4.2.1 Random Experiment — 80
    • 4.2.2 Elementary Event or Trial — 80
    • 4.2.3 Sample Space — 80
    • 4.2.4 Random Event — 81
    • 4.2.5 Inclusion — 82
    • 4.2.6 Complement — 82
    • 4.2.7 Intersection — 82
    • 4.2.8 Mutual Exclusion or Incompatibility — 83
    • 4.2.9 Union — 83
    • 4.2.10 Symmetric Difference — 84
  • 4.3 Boolean Algebra — 85
  • 4.4 Axioms and Fundamental Properties of Probability — 86
    • 4.4.1 Kolmogorov’s Axioms — 86
    • 4.4.2 Axiomatic Definition — 87
    • 4.4.3 Mathematical Scope of the Axioms — 90
    • 4.4.4 Equiprobability — 91
    • 4.4.5 Probability of an Event — 91
    • 4.4.6 Scope of Equiprobability — 92
  • 4.5 Conditional Probability and Independence — 93
  • 4.6 Independence of Two Events — 95
  • 4.7 Probability of a Cause: Bayes’ Formula — 96
    • 4.7.1 General Statement — 97
    • 4.7.2 Example: Probabilistic Identification of a Faulty Server Type — 97
    • 4.7.3 Special Case: Two Complementary Hypotheses — 98
    • 4.7.4 Scope of Bayes’ Formula — 100
  • 4.8 Combinatorial Probability and Artificial Intelligence — 100
    • 4.8.1 Modeling Uncertain Events — 101
    • 4.8.2 Reasoning Under Uncertainty and Bayes’ Formula — 101
    • 4.8.3 Probabilistic Models in Machine Learning — 102
    • 4.8.4 Representation and Processing of Random Sets — 103
    • 4.8.5 Scope of Combinatorial Probability for Artificial Intelligence — 103
  • 4.9 Conclusion of the Chapter — 104
  • 4.10 Exercises — 105
  • 4.11 Solutions — 108
• Chapter 5 - Arithmetic — 123
  • 5.1 Introduction — 123
  • 5.2 Euclidean Division — 124
    • 5.2.1 Euclidean Division Theorem — 124
    • 5.2.2 Theorem on Linear Combinations and Divisibility — 125
  • 5.3 Prime Numbers — 126
    • 5.3.1 Definition — 126
    • 5.3.2 Prime Factorization of a Number — 127
    • 5.3.3 Representing the Prime Factorization of a Number — 128
    • 5.3.4 Example: Factorization of the Number 54 — 128
    • 5.3.5 Mathematical and Computational Significance of Prime Numbers — 129
  • 5.4 Greatest Common Divisor — 130
    • 5.4.1 Definition — 130
    • 5.4.2 Computing the GCD by Prime Factorization — 130
    • 5.4.3 Arithmetic and Computational Scope of the GCD — 133
  • 5.5 Computing the GCD by Euclid’s Algorithm — 133
    • 5.5.1 Principle — 133
    • 5.5.2 Fundamental Remark — 134
    • 5.5.3 Algorithmic Scope — 135
    • 5.5.4 Properties of the GCD — 135
    • 5.5.5 Gauss’s theorem — 137
    • 5.5.6 Commentary — 137
  • 5.6 Least Common Multiple — 138
    • 5.6.1 Definition — 138
    • 5.6.2 Computing the LCM by Prime Factorization — 138
    • 5.6.3 Bézout’s Identity — 140
    • 5.6.4 Relation with the GCD — 144
  • 5.7 Arithmetic and Artificial Intelligence: Symbolic Foundations and Algorithmic Applications — 145
    • 5.7.1 Modular Arithmetic and Cryptography for Artificial Intelligence — 145
    • 5.7.2 GCD, LCM, and Logical Reasoning — 145
    • 5.7.3 Symbolic Learning, Divisibility, and Gauss’s Theorem — 146
    • 5.7.4 Algorithmic Programming in Artificial Intelligence — 147
    • 5.7.5 Synthesis — 147
  • 5.8 Conclusion of the Chapter — 147
  • 5.9 Exercises — 149
  • 5.10 Solutions — 151
• Chapter 6 - Information Encoding and Numeration — 163
  • 6.1 Introduction — 163
  • 6.2 Numeration Systems — 164
    • 6.2.1 Concept of a Digit — 164
    • 6.2.2 Format of a Word — 164
    • 6.2.3 Decimal System (Base 10) — 165
    • 6.2.4 Binary System (Base 2) — 165
    • 6.2.5 Octal System (Base 8) — 166
    • 6.2.6 Hexadecimal System (Base 16) — 166
    • 6.2.7 Mathematical and Computational Scope of Numeration Systems — 167
  • 6.3 Change of Base — 168
    • 6.3.1 Decomposing a Decimal Number in Base 10 — 168
    • 6.3.2 Determining the Number of Fractional Digits After the Decimal Point — 171
    • 6.3.3 Converting from Base 10 to an Arbitrary Base — 173
    • 6.3.4 Conversion from an Arbitrary Base to Base 10 — 176
    • 6.3.5 Mutual Conversion Among Binary, Octal, and Hexadecimal — 177
    • 6.3.6 Mathematical and Computational Scope of Base Conversion — 179
  • 6.4 Binary Arithmetic — 180
    • 6.4.1 General Considerations — 180
    • 6.4.2 Management of Carries and Overflows — 180
    • 6.4.3 Arithmetic Operations in Binary — 181
    • 6.4.4 Mathematical and Computational Scope of Binary Arithmetic — 185
    • 6.4.5 Information Encoding and Numerical Representation in Artificial Intelligence — 185
    • 6.4.6 Binary Representation and Symbolic Processing — 186
    • 6.4.7 Base Conversion and Compatibility Between Software Layers — 186
    • 6.4.8 Binary Arithmetic in Neural Networks and Machine Learning — 187
    • 6.4.9 Information Encoding and the Processing of Symbolic Strings — 187
    • 6.4.10 Numeration and Symbolic Artificial Intelligence: Toward Formal Cognition — 188
    • 6.4.11 Synthesis — 188
  • 6.5 Conclusion of the Chapter — 188
  • 6.6 Exercises — 190
  • 6.7 Solutions — 193
• About the Author — 201
• The Mathematics for Computer Science and Symbolic Artificial Intelligence Series — 202
• Author’s Publishing Collections — 203