Main description:
Judith Gersting's Mathematical Structures for Computer Science has long been acclaimed for its clear presentation of essential concepts and its exceptional range of applications relevant to computer science majors. Now with this new edition, it is the first discrete mathematics textbook revised to meet the proposed new ACM/IEEE standards for the course.
Table of contents:
1. Formal Logic
1.1 Statements, Symbolic Representation, and Tautologies
Connectives and Truth Values
Tautologies
Logical Connectives in the Real World
An Algorithm
Special Interest Page – Can "And" Ever Be "Or"?
Section 1.1 Review
Exercises 1.1
1.2 Propositional Logic
Valid Arguments
Derivation Rules for Propositional Logic
Deduction Method and Other Rules
Verbal Arguments
Section 1.2 Review
Exercises 1.2
1.3 Quantifiers, Predicates, and Validity
Quantifiers and Predicates
Translation
Validity
Section 1.3 Review
Exercises 1.3
1.4 Predicate Logic
Derivation Rules for Predicate Logic
Universal Instantiation
Existential Instantiation
Universal Generalization
Existential Generalization
More Work with Rules
Verbal Arguments
Conclusion
Section 1.4 Review
Exercises 1.4
1.5 Logic Programming
Prolog
Horn Clauses and Resolution
Recursion
Expert Systems
Section 1.5 Review
Exercises 1.5
1.6 Proof of Correctness
Assertions
Assignment Rule
Conditional Rule
Section 1.6 Review
Exercises 1.6
Chapter 1 Review
On the Computer
2. Proofs, Induction, and Number Theory
2.1 Proof Techniques
Theorems and Informal Proofs
To Prove or Not to Prove
Exhaustive Proof
Direct Proof
Contraposition
Contradiction
Serendipity
Common Definitions
Section 2.1 Review
Exercises 2.1
2.2 Induction
First Principle of Induction
Proofs by Mathematical Induction
Second Principle of Induction
Section 2.2 Review
Exercises 2.2
2.3 More on Proof of Correctness
Loop Rule
Euclidean Algorithm
Special Interest Page – Making Safer Software
Section 2.3 Review
Exercises 2.3
2.4 Number Theory
The Fundamental Theorem of Arithmetic
More on Prime Numbers
Euler Phi Function
Section 2.4 Review
Exercises 2.4
Chapter 2 Review
On the Computer
3. Recursion, Recurrence Relations, and Analysis of Algorithms
3.1 Recursive Definitions
Recursively Defined Sequences
Recursively Defined Sets
Recursively Defined Operations
Recursively Defined Algorithms
Section 3.1 Review
Exercises 3.1
3.2 Recurrence Relations
Linear First-Order Recurrence Relations
Expand, Guess, and Verify
A Solution Formula
Linear Second-Order Recurrence Relations
Divide-and-Conquer Recurrence Relations
Section 3.2 Review
Exercises 3.2
3.3 Analysis of Algorithms
The General Idea
Analysis Using Recurrence Relations
Upper Bound (Euclidean Algorithm)
Special Interest Page - Of Trees … and Pancakes
Section 3.3 Review
Exercises 3.3
Chapter 3 Review
On the Computer
4. Sets, Combinatorics, and Probability
4.1 Sets
Notation
Relationships between Sets
Sets of Sets
Binary and Unary Operations
Operations on Sets
Set Identities
Countable and Uncountable Sets
Section 4.1 Review
Exercises 4.1
4.2 Counting
Multiplication Principle
Addition Principle
Using the Principles Together
Decision Trees
Section 4.2 Review
Exercises 4.2
4.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
Principle of Inclusion and Exclusion
Pigeonhole Principle
Section 4.3 Review
Exercises 4.3
4.4 Permutations and Combinations
Permutations
Combinations
Eliminating Duplicates
Permutations and Combinations with Repetitions
Generating Permutations and Combinations
Special Interest Page – Archimedes and the Stomachion
Section 4.4 Review
Exercises 4.4
4.5 Binomial Theorem
Pascal's Triangle
Binomial Theorem and Its Proof
Applying the Binomial Theorem
Section 4.5 Review
Exercises 4.5
4.6 Probability
Introduction to Finite Probability
Probability Distributions
Conditional Probability
Bayes' Theorem
Expected Value
Binomial Distribution
Average Case Analysis of Algorithms
Section 4.5 Review
Exercises 4.6
Chapter 4 Review
On the Computer
5. Relations, Functions, and Matrices
5.1 Relations
Binary Relations
Properties of
