本书是海外优秀数学类教材系列丛书之一,是高等教育出版社从汤姆森学习出版集团原版引进,具有相当高的学术水平,适合高校使用.

Chapter 1 The Logic of Compound Statements  1

1．1 LogicalForm and LogicalEquivalence  1

Statements；CompoundStatements；TruthValues；EvaluatingtheTruthofMo

re General Compound Statements；Logical Equivalence；Tautologies

and Contradictions；Summary ofLogical Equivalences

1．2 Conditional Statements  17

  Logical Equivalences Involving→：Representation ofIf-Then

As Or；The Negadon of a Conditional Statement；The Contrapositive

of a Conditional Statement；The Converse and Inverse of a

Conditional Statement；Only If and the Biconditional；Necessary and

Sufficient Conditions；Remarks

l. 3 Valid andInvalid Arguments  29

  Modus Ponens and Modus Tollens；Additional Valid Argument

Forms：Rules of

  Inference；Fallacies；Contradictions and Valid

Arguments；Summary of Rules of

  Inference

1．4Application：Digital Logic Circuits 43

  Black Boxesand Gates；The Input／Output for a Circuit；The

Boolean Expression Cor-

  responding to a Circuit；The Circuit Corresponding to a

Boolean Expression；Finding

  a CircuitThatCorresponds to a

GivenInput／OutputTable；Simplifying Combinational

  Circuits；NAND and NOR Gares

1．5 Application：Number Systems and Circuits for Addition  

57

  Binary Representation of Numbers；Binary Addition and

Subtraction；Circuits for

Computer Addition；Two"s Complements and the Computer

Representation of Neg-

  ativeIntegers；8-Bit Representation of a

Number；ComputerAddition with Negative

  Integers；Hexadecimal Notation

Chapter 2 The Logic of Quantified Statements  75

2．1 Introduction to Predicates and Quantified Statements /  

75

  The Universal Quantifier：V：The Existential Quantifier：ョ

：Formal Versus Informal

  Language；Universal Conditional Statements；Equivalent

Forms ofthe Universal and

  Existential Statements；Implicit Quantification；Tarski"s

World

2．2 Introduction to Predicates and Quantified Statements II 88

  Negations of Quantified Statements；Negations of Universal

Conditional Statements；The Relation among V，ョ，∧，and V；Vacuous

Truth of Universal Statements；Variants

  0f Universal Conditional Statements；Necessal-y and

Sufficient Conditions，Only If

2．3 Statements Containing Multiple Quantifiers  97

  Translating from Informal to Formal Language；Ambiguous

Language；Negations of Multiply．Quantified Statements；Older of

Quantifiers；Formal Logical Notation；Prolog

2. 4 Arguments with Quantified Statements  111

  Universal MOdus Ponens；Use of Universal Modus Ponens in a

Proof；Universal Modus Tollens；proving Validity of Arguments with

Quantified Statements；Using Diagramsto

Test for Validity；Creating Additional Forms of Argument；Remark on

the Converse and Inverse Errors

Chapter 3 Elementary Number Theoryand Methods ofProof  125

3.1 Direct Proofand Counterexample h Introduction  126

  Definitions；Provlag Existential Statements；Disproving

Universal Statements by

  Counterexample；Proving Universal Statements；Directions

for Writing Proofs of

  Universal Statements；Common Mistakes；Getting Proofs

Started；Showing That an

  Existential Statement Is False；Conjecture，Proof,and

Disproof

  3．2 Direct Proofand Counterexample II Rational Numbers  141

  More on Generalizing from the Generic Particular；Proving

Properties of Rational

  Numbers；Deriving New Mathematics from Old

3．3 Direct Proof and Counterexample IIh Divisibility  148

  Pmving Properties of Divisibility；Counterexamples and

Divisibility；The Unique

  Factorization Theorem

3．4 Direct Proof and Counterexample IV: Division into Cases

and the Quotient-Remainder Theorem  156

  Discussion of the Quorient．Remainder Theorem and Examples

；d／v and mod；Alter-

  native Representations of Integers and Applications to

Number Theory

3．5 Direct Proofand Counterexample V:Floorand Ceiling  164

   Definition and Basic Properties；The Floor of n/2

3．6 Indirect Argument：Contradiction and Contraposition  171

  Proof by Contradiction；Argument by

Contraposition；Relation between Proof by

  ContradictionandProofbyContraposition；Proofas

aProblem-SolvingTool

3．7 Two Classica|Theorems  179

   TheI~ationality of√2：TheInfinitade ofthe set

ofPrimeNumbers；~VhcutoUse

   IndirectProof；OpenQuestionsinNumberTheory  

3．8 Application：Algorithms  186

  An Algorithmic Language；A Notation for Algorithms；Trace

Tables；The Division

  Algorithm；The Eudidean Algorithm

Chapter 4 Sequences and MathematicalInduction  199

4．1 Sequences  199

  Explicit Formulas for Sequences；Summation

Notation；Product Notation；Factorial

  Notation；Properties ofSummations and Products；Change of

Variable；Sequences in

  Computer Programming；Application：Algorithm to Convert

from Base 10 to Base 2

  Using Repeated Division by 2

4．2 Mathematical Induction，  215

  Principie of MathematicalInduction；SumoftheFi~tnIntegers；

Sum of a Geometric

  Sequence

4．3 Mathematical Induction II  227

ComparisonofMathematicalInductionandInductiveReasoning；Proving

Divisibility

  Properties；Proving Inequalities

4．4 Strong Mathematical Inductiopand the Well-Ordering

Principle  235

  The Principle of Strong Mathematical Induction；Binary

Representation of Integers；

  The Well-Ordering Principle for the Integers

4．5 Application：Correctness ofAlgorithms  244

  Assertions；Loop lnvariants；Correctness of the Division

Algorithm；Correctness of

  the Euclidean Algorithm

Chapter 5 Set Theory  255

5．1 Basic Definitions of Set Theory  255

  Subsets；Set Equality；Operations on Sets；Venn

Diagrams；The Empty Set；Partitions

  of Sets；Power Sets；Cartesian Products；An Algorithm to

Check Whether One Set Is

  a Subset ofAnother(Optional)

5．2 Properties of Sets  269

   Set Identities；Proving Set Identities；Proving That a Set

Is the Empty Set

5．3 Disproofs,AlgebraicProofs．andBooleanAlgebras  282

   DisprovinganAllegedSetProperty；Problem-Solving Strategy；

TheNumberofSub-

   sets of a Set；"Algebraic"Proofs of Set

Identities；Boolean Algebras  

5．4 Russell~Paradox and the Halting Problem  293

  Description of Russell"s Paradox；The Halting Problem

Chapter 6 Countingand Probability  297

6，1 Introduction  298

  Definition ofSample Space and Event；Probability in the

Equally Likely Case；Count

  -ing the Elements of Lists，Sublists，and One-Dimensional

Arrays

6．2 Possibility Trees and the Multiplication Rule  306

   Possibility Trees；The Multiplication Role；When the

Multiplication Rule ls Difficult

   or Impossible to Apply；Permutations；Permut~ions of

Selected Elements

6．3 Counting Elements of Disjoint Sets：The Addition Rule  

321

  The Addition Rule；The Difference Rule；The

Inclusion／Exclusion Rule

6．4 Counting Subsets of a Set：Combinations  334

   r-Combinations；Ordered and Unordered Selections；Relation

between Permutations

andCombinations；PermutationofaSetwithRepeatedElements；SomeAdvice

about

   Counting

6．5 r-Combinations with Repetition AIIowed  349

   Multisets and How to Count Them；Which Formula to Use?

6．6 The Algebra of Combinations  356

   Combinatorial Formulas；Pascal"s Triangle；Algebmic and

Combinatorial Proofs of

   Pascal"s Formula

6. 7 The Binomia|Theofem  362

   Statement of the Theorem；Algebraic and Combinatorial

Proof；Applications

6．8 Probability Axioms and Expected Value  370

  Probability Axioms；Deriving Additional Probability

Formulas；Expected Value

6．9 Conditional Probability,Bayes"Formula，and Independent

Even亡s  375

   Conditional Probability；Bayes"Theorem；Independent Events

 Chapter 7 Functions  389

7．1 Functions Defined on General Sets  389

DefinitionofFunction；ArrowDiagrams；FunctionMachines；ExamplesofFu

nctions；

  Boolean Functions；Checking Whether a Function Is Well

Defined  

7．2 One-to-One and Onto，Inverse Functions 402

  One-to-One Functions；One-to-One Functions on Infinite Sets

；Application：Hash

Functions；OntoFunctions；OntoFunctionsonInfiniteSets；PropertiesOf

Exponential

  and Logarithmic Functions；One-to-One

Correspondences；Inverse Function。

7．3 Application：The Pigeonhole Principle 420

  Statement and Discussion of the

Principle；Applications；Decimal Expansions 0f

  Fractions；Generalized Pigeonhole Principle；Proof of the

Pigeonhole Principle

7．4 Composition of Functions 431

   Definition and Examples；Composition of One．to．One

Functions：Composition 0f

   Onto Functions

7．5 Cardinality with Applications to Computability 443

   DefinitionofCardinalEquivalence；CountableSets；The Search

for Larger Infinities：

   The Cantor Diagonalization

Process；Application：Cardinality and Computabilitv

Chapter 8 Recursion 457

8．1 Recursively Defined Sequences 457

   Definition of Recurrence

Relation；ExamplesofRecursivelyDefinedSeauences：The

   NumberofPartitions ofaSetInto r Subsets

8．2 Solving Recurrence Relations by Iteration 475

  The

MethodofIteration；UsingFormulastoSimplifySolutionsObtainedbyIterat

ion；

  Checking the Correctness ofa Formula by Mathematical

Induction；Discovering That

  an Explicit Formula Is Incorrect

8．3 Second-Order Linear Homogenous Recurrence Relations with

Constant Coefficients 487

  Derivation of Technique for Solving These Relations；The

Distinct．RoOts Case：The

  Single-Root Case

8．4 General Recursive Definitions 499

  Recursively Defined Sets；Proving Properties about

Recursively Defined Sets：Re．

  cursive Definitions of Sum，Product，Union，and

Intersection；Recursive Functions

Chapter 9 The EfficiencyofAlgorithms  510

9. 1 Real-Valued Functions ofa Real Variable and Their Graphs 

510

  Graph ofa Function；Power Functions；The Floor

Function；Graphing Functions De-

finedonSetsofIntegers；GraphofaMultipleofaFunction；IncreasingandDe

creasins  

9．2 Ο．Ω．and　ΘNotationS  518

  Definition and General Properties of

0一．Ω一．and@-Notations；Orders of Power

Functions；OrdersofPolynomialFunctions；OrdersofFunctionsofIntegerV

ariables；

  Extension to Functions Composed of Rational Power Functions

9．3 Application：Efficiency ofAlgorithms/  531

  Time Efficiency of an Algorithm；Computing"Orders of Simple

Algorithms；The

  Sequential Search Algorithm；The Insertion Sort Algorithm

9．4 Exponential and Logarithmic Functions：Graphs andOrders  

543

  Graphs of Exponential and Logarithmic

Functions；Application：Number of Bits

  Needed to Represent an Integer in Binary

Notation；Application：Using Logarithms

  to Solve Recurrence Relations；Exponential and Logarithmic

Orders

9．5 Application：Efficiency ofAlgorithms II  557

   Divide-and··Conquer Algorithms；The Efficiency of the

Binary Search Algorithm；

   Merge Sort；Tractable and Intractable Problems；A Final

Remark on Algorithm Effi-ciency

Chapter 10 Relations  571

10．1 Relations on Sets  571

   Definition of Binary Relation；An_0w Diagram of a Relation

；Relations and Func-

   tions；The Inverse of a Relation；Directed Graph of a

Relation；N-ary Relations and

   Relational Databases

10．2 Reflexivity,Symmetry,and Transitivity  584

Reflexive，Symmetric，andTransitiveProperties；TheTransitiveClosure

ofaRelation；

  Properties of Relations on Infinite Sets

10．3 Equivalence Relations  594

   The Relation Induced by a Partition；Definition of an

Equivalence Relation；Equiva-lence Classes of an Equivalence

Relation

10．4 Modular Arithmetic with Applications to Cryptography  

611

   Properties of Congruence Modulo n；Modular

Arithmetic；Finding an Inverse Modulo -n：Euclid"S Lemma；Fermat"S

Little Theorem and the Chinese Remainder Theorem；Why Does the RSA

Cipher Work?

10．5 Partia|Order Relations  632

   Antisymmetry；Partial Order Relations；Lexicographic Order

；Hasse Diagrams；Par-

   tially

andTotallyOrderedSets；TopologicalSorting；AnApplication；PERTandCP

M Chapter 11 Graphs and Trees  649

11．1 Graphs：An Introduction  649

   Basic Terminology and Examples；Special Graphs；The

Concept of Degree

1 1．3 Matrix Representations of Graphs  683

Matnces；MatricesandDirectedGraphs；Matricesand(Undirected)Graphs：

Matrices

    and Connected Components；MaRx Multiplication；Counting

walks of Length N

11.4 Isomorphism of Graphs  697

  Definition of Graph Isomorphism and Examples；Isomorphic

Invariants：Graph Is0一

  lnorphism for Simple Graph Definition and Examples ofTrees

；Characterizing Trees：Rooted Trees；Binary Trees

11. 6 Spanning Trees  723

  Definition of a Spanni g Tree；Minimum Spanning

Trees；Kruskal，s A1gorithm：P

   rim"s Algorithm  

Chapter 12 RegularExpressionsandFinite．StateAutomata  734

12．1 Forma|Languages and Regular Expressions  735

  Definitions and Exafnples 0f Formal Languages and Regular

Expressions：Practical

  Uses of Regular Expressions Defin-ition 0f a Finite-State

Automaton；The Language Accepted by an Automaton：The

Eventual-State Function；Designing a Finite-State

Automaton；Simulating a Finite-State Automaton Using

Software；Finite-State Automata and Regular Expres．Sions;Regular

Languages

12．3 Simplifying Finite-State Automata  763

  *-EquivalenceofStates；k一EquivalenceofStates；Finding

the*EquivalenceClasses：

   The Quotient Automaton；Constmcting the Quotient

Automa--tonn-；Equivalent Au-"

AppendixA Properties ofthe Real Numbers  A-1

Appendix B Solutions and Hints to Selected Exercises  A-4