1Introduction to Mathematical Logic
1288.4.2.2. Breadth-First Search (BFS)
21.1. What is Mathematical Logic?: 1.2. The Importance of Mathematical Logic
129Solved Examples:: Additional Practice Problems:
31.3. Historical Overview
1308.5. Trees and Spanning Trees
41.4. Logical Reasoning and Proofs
1318.5.1. Properties of Trees
5Logical Reasoning:
1328.5.2. Binary Trees
6Proofs:
1338.5.3. Spanning Trees
7Types of Proofs:: Importance of Proofs:
1348.5.3.1. Minimum Spanning Tree
81.5. Propositional and Predicate Logic
135Kruskal’s Algorithm:
9Propositional Logic:
136Prim’s Algorithm:
10Key components of propositional logic:
137Solved Examples:: Additional Practice Problems:
11Predicate Logic:: Key components of predicate logic:
1388.6. Planar Graphs and Coloring
121.6. Applications of Mathematical Logic
1398.6.1. Properties of Planar Graphs
13Example: Boolean Algebra in Digital Electronics: Practice Problem: Hardware Verification
1408.6.2. Graph Coloring: 8.6.2.1. Greedy Coloring Algorithm
14Propositional Logic
141Boolean Algebra
152.1. Propositions and Logical Connectives
1429.1 Boolean Functions
16Propositions:: Logical Connectives:
143Solved Example:: Practice Problems:
172.2. Truth Tables
1449.2 Boolean Operators and Laws
18Construction of Truth Tables:: Importance of Truth Tables:
145Solved Example:: Practice Problems:
192.3. Tautologies and Contradictions
1469.3 Minimization of Boolean Functions
20Tautologies:
147Karnaugh Maps:
21Examples of Tautologies:
148Solved Example:: Practice Problems:
22Contradictions:
1499.4 Karnaugh Maps
23Examples of contradictions:: Identifying Tautologies and Contradictions:
150Construction of Karnaugh Maps:
242.4. Logical Equivalence
151Minimization using Karnaugh Maps:
252.5. Normal Forms
152Solved Example:: Practice Problems:
26Conjunctive Normal Form (CNF):
1539.5 Logic Gates and Circuits
27Disjunctive Normal Form (DNF):
154Solved Example:: Practice Problems:
28Conversion between CNF and DNF:: Importance of Normal Forms:
1559.6 Applications of Boolean Algebra
292.6. Propositional Calculus
1561. Digital Circuit Design:
30Axioms of Propositional Calculus:
1572. Computer Architecture:
31Rules of Inference:: Proofs in Propositional Calculus:
1583. Digital Communication Systems:
32Predicate Logic
1594. Artificial Intelligence and Machine Learning:
333.1. Predicates and Quantifiers
1605. Computer Programming:
34Predicates:
1616. Optimization and Scheduling:
35Quantifiers:: Practice Problems:
1627. Software Engineering:
363.2. Universe of Discourse
1638. Cryptography:: 9. Hardware Description Languages:
37Specifying the Universe of Discourse:: Examples of Universes of Discourse:
164Formal Languages and Automata
383.3. Interpreting Predicate Expressions
16510.1 Introduction to Formal Languages
39Practice Problems:: Practice Problems with Solutions:
166Solved Example:: Practice Problems:
403.4. Quantifier Negation and Equivalence
16710.2 Regular Expressions and Languages
41Negation of Quantified Statements:
168Basic Regular Expression Syntax:
42Quantifier Equivalence:
169Solved Example:: Practice Problems:
431. Prenex Normal Form:
17010.3 Finite Automata
442. Equivalences involving negation:
171Deterministic Finite Automata (DFA):
453. Equivalences involving quantifier exchange:
172DFAs have the following properties:
464. Equivalences involving quantifier distribution:: Practice Problems:
173Non-deterministic Finite Automata (NFA):: NFAs have the following properties:
473.5. Nested Quantifiers
17410.4 Non-deterministic Finite Automata
48Nested Universal and Existential Quantifiers:
175Conversion from NFA to DFA:
49Interpreting Nested Quantifiers:
176Solved Example:: Practice Problems:
50Practice Problems:: Practice Problems with Solutions:
17710.5 Regular Language Properties
513.6. Predicate Calculus
1781. Closure Properties:: 2. Decision Properties:
52Syntax of Predicate Calculus:
17910.6 Pumping Lemma for Regular Languages
53Well-Formed Formulas (WFFs):
180The Pumping Lemma for Regular Languages:
54Interpretations and Models:
181Proof by Contradiction:
55Reasoning in Predicate Calculus:: Practice Problems:
182Solved Example:: Practice Problems:
56Proofs and Deductive Reasoning
183Computability Theory
574.1. Introduction to Proofs
18411.1. Introduction to Computability
58Components of a Proof:
18511.2. Turing Machines
59Types of Proofs:: Importance of Proofs:
18611.3. Undecidability and the Halting Problem: Examples and Practice Problems:
604.2. Direct Proofs
18711.4. Recursive and Recursively Enumerable Sets
61Structure of a Direct Proof:: Practice Problems:
188Recursive Sets:
624.3. Proof by Contraposition
189Recursively Enumerable (r.e.) Sets:: Practice Problem:
63The Contrapositive:
19011.5. Reducibility and the Hierarchy of Undecidable Problems
64Structure of a Proof by Contraposition:: Practice Problems:
191Turing Reducibility:
654.4. Proof by Contradiction
192Hierarchy of Undecidable Problems:: Practice Problem:
66Structure of a Proof by Contradiction:: Practice Problems:
19311.6. Complexity Theory
674.5. Mathematical Induction
194Time Complexity:
68The Principle of Mathematical Induction:: Practice Problems:
195Space Complexity:
694.6. Recursive Definitions and Structural Induction
196Complexity Classes:: Examples and Practice Problems:
70Recursive Definitions:
197Discrete Probability
71Structural Induction:
19812.1. Basic Probability Concepts
72Structure of a Proof by Structural Induction:: Practice Problems:
199Sample Space and Events:
73Set Theory
200Probability of an Event:
745.1. Basic Set Concepts
201Axioms of Probability:
75Definition of a Set:
202Probability Rules and Theorems:: Practice Problem:
76Notation and Representation:
20312.2. Conditional Probability and Independence
77Set-Builder Notation:
204Conditional Probability:: Practice Problem:
78Elements and Membership:
20512.3. Bayes’ Theorem
79Empty Set and Universal Set:
20612.4. Random Variables and Probability Distributions
80Finite and Infinite Sets:
207Random Variables:
81Equal Sets:
208Discrete Random Variables:
82Proper Subsets:: Practice Problems:
209Probability Mass Function (PMF):
835.2. Set Operations
210Cumulative Distribution Function (CDF):: Practice Problem:
84Union of Sets:
21112.5. Expected Value and Variance
85Intersection of Sets:
212Expected Value:
86Set Difference:
213Variance and Standard Deviation:: Practice Problem:
87Complement of a Set:
21412.6. Discrete Probability Applications
88Cartesian Product:
2151. Reliability Theory:
89Properties of Set Operations:: Practice Problems:
2162. Queueing Theory:
905.3. Venn Diagrams
2173. Quality Control:
91Representing Sets with Venn Diagrams:
2184. Cryptography and Information Theory:
92Interpreting Venn Diagrams:: Practice Problems:
2195. Risk Analysis and Decision Theory:
935.4. Cartesian Products and Relations: Practice Problems:
2206. Machine Learning and Artificial Intelligence:
945.5. Functions and Cardinality: Practice Problems:
221Computational Complexity
955.6. Axioms of Set Theory: Practice Problems:
22213.1. Introduction to Computational Complexity
96Relations and Functions
22313.2. Time and Space Complexity
976.1. Binary Relations: Practice Problems:
224Time Complexity:: Space Complexity:
986.2. Properties of Relations: Practice Problems:
22513.3. Complexity Classes (P, NP, and NP-Completeness)
996.3. Equivalence Relations and Partitions: Practice Problems:
226P (Polynomial-time):
1006.4. Partial Orderings and Lattices: Practice Problems:
227NP (Non-deterministic Polynomial-time):
1016.5. Functions and Their Properties
228NP-Completeness:
102Functions have several important properties:: Practice Problems:
229Solved Examples:
1036.6. Surjective, Injective, and Bijective Functions
230Practice Problems with Solutions:
104Surjective (Onto) Functions:
231Practice Problems with Solutions:
105Injective (One-to-One) Functions:
23213.4. Polynomial-Time Reductions: Solved Example:
106Bijective Functions:
23313.5. NP-Complete Problems: Solved Example:
107Properties of Bijective Functions:: Practice Problems:
23413.6. Approximation Algorithms
108Combinatorics
235Solved Example:: Practice Problems with Solutions:
1097.1. The Multiplication Principle: Practice Problems:
236Modal Logic
1107.2. Permutations and Combinations
23714.1. Introduction to Modal Logic
111Permutations:
23814.2. Possible Worlds and Accessibility Relations
112Combinations:: Practice Problems:
23914.3. Axioms and Semantics
1137.3. The Pigeonhole Principle: Practice Problems:
240Solved Examples:: Practice Problems with Solutions:
1147.4. Inclusion-Exclusion Principle: Practice Problems:
24114.4. Temporal Logic
1157.5. Recurrence Relations: Practice Problems:
24214.5. Epistemic Logic
1167.6. Generating Functions
24314.6. Applications of Modal Logic
117Generating functions have several advantages:: Practice Problems:
2441. Program Verification:
118Graph Theory
2452. Formal Specification and Reasoning:
1198.1. Introduction to Graphs
2463. Multi-Agent Systems:
1208.2. Graph Representations
2474. Distributed Systems and Concurrency:
1218.2.1. Adjacency Matrix: 8.2.2. Adjacency List
2485. Knowledge Representation and Reasoning:
1228.3. Graph Isomorphism
2496. Game Theory and Economics:
123Solved Examples:: Additional Practice Problems:
2507. Linguistics and Natural Language Processing:
1248.4. Connectivity and Traversal
2518. Philosophy and Ethics:
1258.4.1. Connected Graphs
252Solved Examples:: Practice Problems with Solutions:
1268.4.2. Traversal Algorithms
253Glossary
1278.4.2.1. Depth-First Search (DFS)
254Index
