#### Find what you need to succeed.

- Home
- Mathematics
- Mathematical Structures for Computer Science

# Mathematical Structures for Computer Science

## Seventh Edition| ©2015 Judith L. Gersting

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

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

ISBN:9781429215107

Read and study old-school with our bound texts.

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.

Features

New to This Edition

**New Content**

New material guided by the Draft of the ACM/IEEE Computer Science Curriculum 2013. Content updates include:

- New section on probability
- New subsection on coding theory
- New subsection on order of magnitude
- New subsection on matrices

**New Feature! Special Interest**Each chapter features a special interest topic that highlights the practical relevance of a specific concept

New Examples and Exercises

New Examples and Exercises

- 30% new examples, practice problems, and exercises
- Examples updated to reflect current data and to demonstrate the role mathematics and computer science in a wide range of disciplines
- Answers to odd numbered exercises are now in the back of the book

**
Mathematical Structures for Computer Science**

Seventh Edition| ©2015

Judith L. Gersting

# Digital Options

**Mathematical Structures for Computer Science**

Seventh Edition| 2015

Judith L. Gersting

## 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 Relations

Closures of Relations

Partial Orderings

Equivalence Relations

Section 5.1 Review

Exercises 5.1

**5.2 Topological Sorting**

Section 5.2 Review

Exercises 5.2

**5.3 Relations and Databases **

Entity-Relationship Model

Relational Model

Operations on Relations

Null Values and Three-Valued Logic

Database Integrity

Section 5.3 Review

Exercises 5.3

**5.4 Functions **

Definition

Properties of Functions

Onto Functions

One-to-One Functions

Bijections

Composition of Functions

Inverse Functions

Permutation Functions

How Many Functions

Equivalent Sets

Section 5.4 Review

Exercises 5.4

**5.5 Order of Magnitude**Function Growth

More on Analysis of Algorithms

The Master Theorem

Proof of the Master Theorem

Section 5.5 Review

Exercises 5.5

**5.6 The Mighty Mod Function**

Hashing

Computer Security

Cryptography

Hashing for Password Encryption

Miscellaneous Applications

Identification Codes

Generating and Decomposing Integers

Modular Arithmetic Designs

Section 5.6 Review

Exercises 5.6

**5.7 Matrices**

Terminology

Matrix Operations

Gaussian Elimination

Boolean Matrices

Special Interest Page - Solve Millions of Equations, Faster than Gauss

Section 5.7 Review

Exercises 5.7

Chapter 5 Review

On the Computer

**6. Graphs and Trees **** 6.1 Graphs and their Representations**

Definitions of a Graph

Applications of Graphs

Graph Terminology

Isomorphic Graphs

Planar Graphs

Computer Representation of Graphs

Adjacency Matrix

Adjacency List

Special Interest Page - Isomorphic Protein Graphs

Section 6.1 Review

Exercises 6.1

**6.2 Trees and their Representations**

Tree Terminology

Applications of Trees

Binary Tree Representation

Tree Traversal Algorithms

Results About Trees

Section 6.2 Review

Exercises 6.2

**6.3 Decision Trees**

Searching

Lower Bounds on Searching

Binary Tree Search

Sorting

Section 6.3 Review

Exercises 6.3

**6.4 Huffman Codes**

Problem and Trial Solution

Huffman Encoding Algorithm

Justification

Application of Huffman Codes

Section 6.4 Review

Exercises 6.4

Chapter 6 Review

On the Computer

**7. Graph Algorithms **

**7.1 Directed Graphs and Binary Relations; Warshall's Algorithm**

Directed Graphs and Binary Relations

Reachability

Warshall's Algorithm

Section 7.1 Review

Exercises 7.1

**7.2 Euler Path and Hamiltonian Circuit**

Euler Path Problem

Hamiltonian Circuit Problem

Section 7.2 Review

Exercises 7.2

**7.3 Shortest Path and Minimal Spanning Tree**

Shortest-Path Problem

Minimal Spanning Tree Problem

Special Interest Page - Pathfinding

Section 7.3 Review

Exercises 7.3

**7.4 Traversal Algorithms **Depth-First Search

Breadth-First Search

Analysis

Applications

Section 7.4 Review

Exercises 7.4

**7.5 Articulation Points and Computer Networks**

The Problem Statement

The Idea Behind the Algorithm

The Algorithm Itself

Section 7.5 Review

Exercises 7.5

Chapter 7 Review

On the Computer

**8. Boolean Algebra and Computer Logic **

**8.1 Boolean Algebra Structure**

Models or Abstractions

Definition and Properties

Isomorphic Boolean Algebras

What is Isomorphism?

Isomorphism as Applied to Boolean Algebra

Section 8.1 Review

Exercises 8.1

**8.2 Logic Networks**

Combinational Networks

Basic Logic Elements

Boolean Expressions

Truth Functions

Networks and Expressions

Canonical Form

Minimization

Programmable Logic Devices

A Useful Network

Other Logic Elements

Constructing Truth Functions

Special Interest Page - Pruning Chips and Programs

Section 8.2 Review

Exercises 8.2

**8.3 Minimization**

Minimization Process

Karnaugh Map

Maps for Three and Four Variables

Using the Karnaugh Map

Quine-McCluskey Procedure

Section 8.3 Review

Exercises 8.3

Chapter 8 Review

On the Computer

**9. Modeling Arithmetic, Computation, and Languages** **9.1 Algebraic Structures **Definitions and Examples

Basic Results about Groups

Subgroups

Isomorphic Groups

Section 9.1 Review

Exercises 9.1

**9.2 Coding Theory**

Introduction

Background: Homomorphisms and Cosets

Generating Group Codes

Decoding Group Codes

Section 9.2 Review

Exercises 9.2

**9.3 Finite-State Machines**

Definition

Examples of Finite-State Machines

Recognition

Regular Sets and Kleene's Theorem

Machine Minimization

Unreachable States

Minimization Procedure

Sequential Networks and Finite-State Machines

Special Interest Page – FSMs Behind the Game

Section 9.3 Review

Exercises 9.3

**9.4 Turing Machines**

Definition

Turing Machines as Set Recognizers

Turing Machines as Function Computers

Church-Turing Thesis

Decision Problems and Uncomputability

Examples of Decision Problems

Halting Problem

Computational Complexity

Section 9.4 Review

Exercises 9.4

**9.5 Formal Languages**

Classes of Grammars

Formal Languages and Computational Devices

Context-Free Grammars

Section 9.5 Review

Exercises 9.5

Chapter 9 Review

On the Computer

Appendix A Derivation Rules for Propositional and Predicate Logic

Appendix B Summation and Product Notation

Appendix C The Logarithm Function

Appendix D The Binary Number System

Answers to Practice Problems

Answers to Odd-Numbered Exercises

Answers to Self-Tests

Index

## Authors

### Judith L. Gersting

**Judith Gersting**received her undergraduate degree in mathematics from Stetson University. Her master's and Ph.D. in mathematics are from Arizona State University. She taught mathematics and, later, computer science at Indiana University-Purdue University at Indianapolis, where she was the first chair of the newly formed Computer and Information Science Department. She was a Staff Scientist at the Indianapolis Center for Advanced Research for two years, and also spent a year as the Assistant Chair of the Department of Computer Science at the University of Central Florida. After many years at IUPUI, she and her husband, John Gersting, left IUPUI to go to the Computer Science and Engineering Department at the University of Hawaii at Hilo on the Big Island. Here Prof. Gersting served as department chair for many more years, and was awarded the University of Hawaii Regents Medal for Excellence in Teaching. She and her husband have recently retired from UHH and are back as Adjunct Professors at IUPUI teaching two classes per semester. Prof. Gersting has been active in SIGCSE (the ACM Special Interest Group in Computer Science Education), and she was the co-chair of the SIGCSE Technical Symposium in 2002. She has received NSF computer science education grants and has served on NSF grant review panels in computer science education. She is the author of several college-level textbooks in mathematics and computer science, including co-author with G. Michael Schneider of the introductory text

*Invitation to Computer Science*, published by Cengage Learning.

# Instructor Resources

## Need instructor resources for your course?

Unlock Your Resources# Instructor Resources

### Download Resources

You need to sign in to unlock your resources.

**We're sorry!**The server encountered an internal error and cannot complete your request. Please try again later.

You've selected:

Click the E-mail Download Link button and we'll send you an e-mail at with links to download your instructor resources. Please note there may be a delay in delivering your e-mail depending on the size of the files.

**Warning!** These materials are owned by Macmillan Learning or its licensors and are protected by copyright laws in the United States and other jurisdictions. Such materials may include a digital watermark that is linked to your name and email address in your Macmillan Learning account to identify the source of any materials used in an unauthorised way and prevent online piracy. These materials are being provided solely for instructional use by instructors who have adopted Macmillan Learningâ€™s accompanying textbooks or online products for use by students in their courses. These materials may not be copied, distributed, sold, shared, posted online, or used, in print or electronic format, except in the limited circumstances set forth in the Macmillan Learning Terms of Use
and any other reproduction or distribution is illegal. These materials may not be made publicly available under any circumstances. All other rights reserved. For more information about the use of your personal data including for the purposes of anti-piracy enforcement, please refer to Macmillan Learning's.Privacy Notice

### Thank you!

Your download request has been received and your download link will be sent to .

Please note you could wait up to **30 to 60 minutes** to receive your download e-mail depending on the number and size of the files. We appreciate your patience while we process your request.

Check your inbox, trash, and spam folders for an e-mail from **InstructorResources@macmillan.com**.

If you do not receive your e-mail, please visit macmillanlearning.com/support.

**We're sorry!**The server encountered an internal error and cannot complete your request. Please try again later.

**Mathematical Structures for Computer Science**

Seventh Edition| 2015

Judith L. Gersting

## Related Titles

Select a demo to view: