海外优秀数学类教材系列丛书：离散数学及其应用（第3版）（影印版）
目 录内容简介
~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
查看完整
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
查看完整
目 录内容简介
本书从Thomson Learning出版公司引进。本书内容包括：复合陈述中的逻辑，定量陈述中的逻辑，基础数论及证明方法，数理推断及序列，集合论，计算和概率，函数，递归，运算法则及效率，关系，图和树，常规表达式和自动控制。
本书可作为高等院校理工科专业学生作为离散数学双语教材使用，与其同类教材相比；本书有以下几个突出的特点：1．着重逻辑推理；2．以螺旋前进的方式介绍并运用概念，便于学生了解及进一步掌握；3．大量的图表便于学生直观理解；4．习题配置合理，书后给出了习题答案．5．有与本书配套的网络资源。
本书叙述详尽、语言表达流畅，适合于理工科各专业学生作为双语教材使用，也可供教师教学参考。
本书可作为高等院校理工科专业学生作为离散数学双语教材使用，与其同类教材相比；本书有以下几个突出的特点：1．着重逻辑推理；2．以螺旋前进的方式介绍并运用概念，便于学生了解及进一步掌握；3．大量的图表便于学生直观理解；4．习题配置合理，书后给出了习题答案．5．有与本书配套的网络资源。
本书叙述详尽、语言表达流畅，适合于理工科各专业学生作为双语教材使用，也可供教师教学参考。
目 录内容简介
~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~
^ 收 起
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~
^ 收 起
目 录内容简介
本书从Thomson Learning出版公司引进。本书内容包括：复合陈述中的逻辑，定量陈述中的逻辑，基础数论及证明方法，数理推断及序列，集合论，计算和概率，函数，递归，运算法则及效率，关系，图和树，常规表达式和自动控制。
本书可作为高等院校理工科专业学生作为离散数学双语教材使用，与其同类教材相比；本书有以下几个突出的特点：1．着重逻辑推理；2．以螺旋前进的方式介绍并运用概念，便于学生了解及进一步掌握；3．大量的图表便于学生直观理解；4．习题配置合理，书后给出了习题答案．5．有与本书配套的网络资源。
本书叙述详尽、语言表达流畅，适合于理工科各专业学生作为双语教材使用，也可供教师教学参考。
本书可作为高等院校理工科专业学生作为离散数学双语教材使用，与其同类教材相比；本书有以下几个突出的特点：1．着重逻辑推理；2．以螺旋前进的方式介绍并运用概念，便于学生了解及进一步掌握；3．大量的图表便于学生直观理解；4．习题配置合理，书后给出了习题答案．5．有与本书配套的网络资源。
本书叙述详尽、语言表达流畅，适合于理工科各专业学生作为双语教材使用，也可供教师教学参考。
比价列表
