Mathematical structures for computer science

discrete mathematics and its applications

7th edition.
  • 171 Want to read
  • 12 Currently reading
  • 2 Have read

My Reading Lists:

Create a new list

  • 171 Want to read
  • 12 Currently reading
  • 2 Have read

Buy this book

Last edited by ImportBot
December 19, 2023 | History

Mathematical structures for computer science

discrete mathematics and its applications

7th edition.
  • 171 Want to read
  • 12 Currently reading
  • 2 Have read

This work doesn't have a description yet. Can you add one?

Publish Date
Language
English
Pages
969

Buy this book

Previews available in: English

Edition Availability
Cover of: Mathematical structures for computer science
Mathematical structures for computer science: discrete mathematics and its applications
2014, W.H. Freeman and Company, a Macmillian Higher Education Company
in English - 7th edition.
Cover of: Mathematical structures for computer science
Mathematical structures for computer science
1987, W.H. Freeman
in English - 2nd ed.
Cover of: Mathematical structures for computer science
Mathematical structures for computer science
1982, W.H. Freeman
in English

Add another edition?

Book Details


Table of Contents

Chapter 1. Formal Logic
Page 1
1.1. Statements, Symbolic Representation, and Tautologies
Page 2
Connectives and Truth Values
Page 2
Tautologies
Page 8
Logical Connectives in the Real World
Page 10
An Algorithm
Page 12
Special Interest Page: Can "And" Ever Be "Or"?
Page 15
Section 1.1 Review
Page 16
Exercises 1.1
Page 16
1.2. Propositional Logic
Page 25
Valid Arguments
Page 25
Derivation Rules for Propositional Logic
Page 28
Deduction Method and Other Rules
Page 32
Verbal Arguments
Page 33
Section 1.2 Review
Page 35
Exercises 1.2
Page 35
1.3. Quantifiers, Predicates, and Validity
Page 39
Quantifiers and Predicates
Page 39
Translation
Page 42
Validity
Page 48
Section 1.3 Review
Page 50
Exercises 1.3
Page 50
1.4. Predicate Logic
Page 58
Derivation Rules for Predicate Logic
Page 58
Universal Instantiation
Page 59
Existential Instantiation
Page 60
Universal Generalization
Page 61
Existential Generalization
Page 62
More Work with Rules
Page 62
Verbal Arguments
Page 67
Conclusion
Page 68
Section 1.4 Review
Page 69
Exercises 1.4
Page 69
1.5. Logic Programming
Page 73
Prolog
Page 73
Horn Clauses and Resolution
Page 75
Recursion
Page 79
Expert Systems
Page 81
Section 1.5 Review
Page 82
Exercises 1.5
Page 82
1.6. Proof of Correctness
Page 84
Assertions
Page 85
Assignment Rule
Page 87
Conditional Rule
Page 90
Section 1.6 Review
Page 92
Exercises 1.6
Page 92
Chapter 1 Review
Page 95
On the Computer
Page 96
Chapter 2. Proofs, Induction, and Number Theory
Page 97
2.1. Proof Techniques
Page 98
Theorems and Informal Proofs
Page 98
To Prove or Not to Prove
Page 99
Exhaustive Proof
Page 100
Direct Proof
Page 101
Contraposition
Page 103
Contradiction
Page 104
Serendipity
Page 106
Common Definitions
Page 107
Section 2.1 Review
Page 107
Exercises 2.1
Page 107
2.2. Induction
Page 110
First Principle of Induction
Page 110
Proofs by Mathematical Induction
Page 112
Second Principle of Induction
Page 118
Section 2.2 Review
Page 122
Exercises 2.2
Page 122
2.3. More on Proof of Correctness
Page 129
Loop Rule
Page 129
Euclidean Algorithm
Page 133
Special Interest Page: Making Safer Software
Page 136
Section 2.3 Review
Page 137
Exercises 2.3
Page 137
2.4. Number Theory
Page 143
The Fundamental Theorem of Arithmetic
Page 144
More on Prime Numbers
Page 148
Euler Phi Function
Page 149
Section 2.4 Review
Page 152
Exercises 2.4
Page 152
Chapter 2 Review
Page 155
On the Computer
Page 156
Chapter 3. Recursion, Recurrence Relations, and Analysis of Algorithms
Page 157
3.1. Recursive Definitions
Page 158
Recursively Defined Sequences
Page 158
Recursively Defined Sets
Page 162
Recursively Defined Operations
Page 165
Recursively Defined Algorithms
Page 166
Section 3.1 Review
Page 171
Exercises 3.1
Page 171
3.2. Recurrence Relations
Page 180
Linear First-Order Recurrence Relations
Page 180
Expand, Guess, and Verify
Page 180
A Solution Formula
Page 182
Linear Second-Order Recurrence Relations
Page 188
Divide-and-Conquer Recurrence Relations
Page 193
Section 3.2 Review
Page 197
Exercises 3.2
Page 197
3.3. Analysis of Algorithms
Page 203
The General Idea
Page 203
Analysis Using Recurrence Relations
Page 206
Upper Bound (Euclidean Algorithm)
Page 210
Special Interest Page: Of Trees ... and Pancakes
Page 211
Section 3.3 Review
Page 212
Exercises 3.3
Page 212
Chapter 3 Review
Page 217
On the Computer
Page 218
Chapter 4. Sets, Combinatorics, and Probability
Page 221
4.1. Sets
Page 222
Notation
Page 222
Relationships Between Sets
Page 224
Sets of Sets
Page 227
Binary and Unary Operations
Page 228
Operations on Sets
Page 230
Set Identities
Page 233
Countable and Uncountable Sets
Page 236
Section 4.1 Review
Page 239
Exercises 4.1
Page 239
4.2. Counting
Page 252
Multiplication Principle
Page 252
Addition Principle
Page 254
Using the Principles Together
Page 255
Decision Trees
Page 257
Section 4.2 Review
Page 258
Exercises 4.2
Page 259
4.3. Principle of Inclusion and Exclusion; Pigeonhole Principle
Page 263
Principle of Inclusion and Exclusion
Page 264
Pigeonhole Principle
Page 269
Section 4.3 Review
Page 269
Exercises 4.3
Page 270
4.4. Permutations and Combinations
Page 272
Permutations
Page 272
Combinations
Page 274
Eliminating Duplicates
Page 277
Permutations and Combinations with Repetitions
Page 279
Generating Permutations and Combinations
Page 280
Special Interest Page: Archimedes and the Stomachion
Page 286
Section 4.4 Review
Page 288
Exercises 4.4
Page 288
4.5. Binomial Theorem
Page 294
Pascal's Triangle
Page 294
Binomial Theorem and Its Proof
Page 296
Applying the Binomial Theorem
Page 298
Section 4.5 Review
Page 299
Exercises 4.5
Page 299
4.6. Probability
Page 301
Introduction to Finite Probability
Page 301
Probability Distributions
Page 304
Conditional Probability
Page 306
Bayes' Theorem
Page 308
Expected Value
Page 310
Binomial Distributions
Page 313
Average Case Analysis of Algorithms
Page 314
Section 4.6 Review
Page 315
Exercises 4.6
Page 315
Chapter 4 Review
Page 323
On the Computer
Page 324
Chapter 5. Relations, Functions, and Matrices
Page 327
5.1. Relations
Page 328
Binary Relations
Page 328
Properties of Relations
Page 332
Closures of Relations
Page 334
Partial Orderings
Page 336
Equivalence Relations
Page 339
Section 5.1 Review
Page 344
Exercises 5.1
Page 345
5.2. Topological Sorting
Page 356
Section 5.2 Review
Page 361
Exercises 5.2
Page 362
5.3. Relations and Databases
Page 365
Entity-Relationship Model
Page 365
Relational Model
Page 366
Operations on Relations
Page 369
Null Values and Three-valued Logic
Page 373
Database Integrity
Page 375
Section 5.3 Review
Page 376
Exercises 5.3
Page 381
5.4. Functions
Page 381
Definition
Page 381
Properties of Functions
Page 388
Onto Functions
Page 388
One-to-One Functions
Page 389
Bijections
Page 390
Composition of Functions
Page 390
Inverse Functions
Page 392
Permutation Functions
Page 394
How Many Functions
Page 397
Equivalent Sets
Page 401
Section 5.4 Review
Page 402
Exercises 5.4
Page 402
5.5. Order of Magnitude
Page 412
Function Growth
Page 412
More on Analysis of Algorithms
Page 415
The Master Theorem
Page 417
Proof of the Master Theorem
Page 419
Section 5.5 Review
Page 421
Exercises 5.5
Page 421
5.6. The Mighty Mod Function
Page 423
Hashing
Page 424
Computer Security
Page 427
Cryptography
Page 427
Hashing for Password Encryption
Page 433
Miscellaneous Applications
Page 435
Identification Codes
Page 435
Generating and Decomposing Integers
Page 437
Modular Arithmetic Designs
Page 438
Section 5.6 Review
Page 440
Exercises 5.6
Page 440
5.7. Matrices
Page 446
Terminology
Page 446
Matrix Operations
Page 448
Gaussian Elimination
Page 453
Boolean Matrices
Page 458
Special Interest Page: Solve Millions of Equations, Faster than Gauss
Page 460
Section 5.7 Review
Page 461
Exercises 5.7
Page 461
Chapter 5 Review
Page 470
On the Computer
Page 472
Chapter 6. Graphs and Trees
Page 475
6.1. Graphs and Their Representations
Page 476
Definitions of a Graph
Page 476
Applications of Graphs
Page 479
Graph Terminology
Page 481
Isomorphic Graphs
Page 484
Planar Graphs
Page 487
Computer Representation of Graphs
Page 492
Adjacency Matrix
Page 492
Adjacency List
Page 494
Special Interest Page: Isomorphic Protein Graphs
Page 497
Section 6.1 Review
Page 498
Exercises 6.1
Page 498
6.2. Trees and Their Representations
Page 509
Tree Terminology
Page 509
Applications of Trees
Page 511
Binary Tree Representation
Page 513
Tree Traversal Algorithms
Page 514
Results about Trees
Page 519
Section 6.2 Review
Page 521
Exercises 6.2
Page 521
6.3. Decision Trees
Page 529
Searching
Page 529
Lower Bounds on Searching
Page 532
Binary Tree Search
Page 533
Sorting
Page 535
Section 6.3 Review
Page 536
Exercises 6.3
Page 536
6.4. Huffman Codes
Page 539
Problem and Trial Solution
Page 539
Huffman Encoding Algorithm
Page 542
Justification
Page 544
Application of Huffman Codes
Page 546
Section 6.4 Review
Page 547
Exercises 6.4
Page 548
Chapter 6 Review
Page 551
On the Computer
Page 552
Chapter 7. Graph Algorithms
Page 553
7.1. Directed Graphs and Binary Relations; Warshall's Algorithm
Page 554
Directed Graphs and Binary Relations
Page 555
Reachability
Page 557
Warshall's Algorithm
Page 562
Section 7.1 Review
Page 566
Exercises 7.1
Page 566
7.2. Euler Path and Hamiltonian Circuit
Page 571
Euler Path Problem
Page 571
Hamiltonian Circuit Problem
Page 576
Section 7.2 Review
Page 577
Exercises 7.2
Page 577
7.3. Shortest Path and Minimal Spanning Tree
Page 581
Shortest-Path Problem
Page 581
Minimal Spanning Tree Problem
Page 587
Special Interest Page: Pathfinding
Page 589
Section 7.3 Review
Page 591
Exercises 7.3
Page 591
7.4. Traversal Algorithms
Page 596
Depth-First Search
Page 596
Breadth-First Search
Page 598
Analysis
Page 601
Applications
Page 601
Section 7.4 Review
Page 604
Exercises 7.4
Page 604
7.5. Articulation Points and Computer Networks
Page 607
The Problem Statement
Page 607
The Idea behind the Algorithm
Page 608
The Algorithm Itself
Page 610
Section 7.5 Review
Page 612
Exercises 7.5
Page 612
Chapter 7 Review
Page 614
On the Computer
Page 615
Chapter 8. Boolean Algebra and Computer Logic
Page 617
8.1. Boolean Algebra Structure
Page 618
Models or Abstractions
Page 619
Definition and Properties
Page 620
Isomorphic Boolean Algebras
Page 626
What is Isomorphism?
Page 626
Isomorphism as Applied to Boolean Algebra
Page 628
Section 8.1 Review
Page 631
Exercises 8.1
Page 631
8.2. Logic Networks
Page 638
Combinational Networks
Page 638
Basic Logic Elements
Page 638
Boolean Expressions
Page 639
Truth Functions
Page 640
Networks and Expressions
Page 641
Canonical Form
Page 642
Minimization
Page 645
Programmable Logic Devices
Page 647
A Useful Network
Page 648
Other Logic Elements
Page 650
Constructing Truth Functions
Page 652
Special Interest. Pruning Chips and Programs
Page 654
Section 8.2 Review
Page 655
Exercises 8.2
Page 655
8.3. Minimization
Page 663
Minimization Process
Page 663
Karnaugh Map
Page 665
Maps for Three and Four Variables
Page 666
Using the Karnaugh Map
Page 668
Quine-McCluskey Procedure
Page 673
Section 8.3 Review
Page 677
Exercises 8.3
Page 678
Chapter 8 Review
Page 683
On the Computer
Page 684
Chapter 9. Modeling Arithmetic, Computation, and Languages
Page 685
9.1. Algebraic Structures
Page 686
Definitions and Examples
Page 686
Basic Results about Groups
Page 695
Subgroups
Page 698
Isomorphic Groups
Page 702
Section 9.1 Review
Page 708
Exercises 9.1
9.2. Coding Theory
Page 714
Introduction
Page 714
Background: Homomorphisms and Cosets
Page 715
Generating Group Codes
Page 717
Decoding Group Codes
Page 723
Section 9.2 Review
Page 727
Exercises 9.2
Page 727
9.3. Finite-State Machines
Page 728
Definition
Page 729
Examples of Finite-State Machines
Page 729
Recognition
Page 733
Regular Sets and Kleene's Theorem
Page 735
Machine Minimization
Page 737
Unreachable States
Page 737
Minimization Procedure
Page 739
Sequential Networks and Finite-State Machines
Page 744
Special Interest. FSMs Behind the Game
Page 749
Section 9.3 Review
Page 750
Exercises 9.3
Page 750
9.4. Turing Machines
Page 759
Definition
Page 760
Turing Machines as Set Recognizers
Page 764
Turing Machines as Function Computers
Page 767
Church-Turing Thesis
Page 769
Decision Problems and Uncomputability
Page 771
Examples of Decision Problems
Page 772
Halting Problem
Page 773
Computational Complexity
Page 776
Section 9.4 Review
Page 778
Exercises 9.4
Page 779
9.5. Formal Languages
Page 782
Classes of Grammars
Page 789
Formal Languages and Computational Devices
Page 792
Context-Free Grammars
Page 793
Section 9.5 Review
Page 795
Exercises 9.5
Page 795
Chapter 9 Review
Page 799
On the Computer
Page 800
Appendix A. Derivation Rules for Propositional and Predicate Logic
Page 803
Appendix B. Summation and Product Notation
Page 805
Appendix C. The Logarithm Function
Page 809
Answers to Practice Problems
Page 813
Answers to Odd-Numbered Exercises
Page 851
Answers to Self-Tests
Page 949
Index
Page 959

Edition Notes

Includes index.

Published in
New York, NY

Classifications

Library of Congress
QA39.3 .G47 2014, QA39.3.G47 2014

The Physical Object

Pagination
xvi, 969 pages
Number of pages
969

Edition Identifiers

Open Library
OL31014850M
ISBN 10
1429215100
ISBN 13
9781429215107
LCCN
2013951442

Work Identifiers

Work ID
OL1922611W

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Download catalog record: RDF / JSON