The book is mainly aimed at the bilingual curriculum design of discrete mathematics.It can meet the needs of the types of an introduction to the fundamental ideas of discrete mathematics,and as a foundation for the development of more advanced mathematical concepts.
The book includes four parts.The first part is mathematical logic which covers propositional logic in Chapter 1 and predicate logic in Chapter 2.It gives a method how to express natural language statements using symbols as the foundation to discrete mathematics,especially for sets.The logic parts include equivalent calculation and the discussion of proof.The second part is set theory with sets in Chapter 3,relations in Chapter 4,and functions in Chapter 5,which is the basics of the whole mathematics.Chapter 3 presents basic types of sets and their operations.Chapter 4 presents definition,properties and operations of relations,along with their representation as directed graphs and connections with matrices.Chapter 5 restates the function from the perspective of relations,including countable sets and uncountable sets.The third part is graph theory in Chapter 6 which is the sources for data structures and algorithms.It covers terminology,representation and special structure of graphs.The last part,that is a highly abstract part,is algebraic systems in Chapter 7,which covers semigroups,groups rings and fields.By algebraic systems we can find commonalities of many familiar rules.
This book can be used as a discrete mathematics courses reference for computer,mathematics,big data technology and some related disciplines in Institutions of Higher Learning,and can also provide useful help for other readers of discrete mathematics,especially for bilingual learning.
As an important branch of modern mathematics,discrete mathematics is the core course of basic theory in computer science and a specialized basic course of the whole computer discipline.Discrete mathematics is concerned with finite and countable infinite mathematical structures.It belongs to the discipline of mathematics,whereas,most areas within computer science or engineering concentrations make heavy use of concepts from discrete mathematics.Its applications range from algorithms (design and analysis) to databases,from operating systems to program verification.
Discrete mathematics is of central importance.Firstly,many objects studied in computer science and engineering concentrations are discrete mathematical objects,for example,an algebraic group used in cryptography or coding theory,and a graph which can model an engineering network.Secondly,discrete mathematics provides abstraction of many computer and engineering systems,which can teach us the art of abstraction.These systems can only be understood by considering a number of layers of abstraction,from application programs via the operating system layer down to the physical hardware.Thirdly,discrete mathematics tells us how to make mathematical reasoning and construct the formal of calculations in any engineering discipline,and especially in computer science.For example,we can understand a computer program as a welldefined discrete mathematical object.
This text is designed to meet the needs of the types of an introduction to the fundamental ideas of discrete mathematics,and as a foundation for the development of more advanced mathematical concepts.The text can provide a coherent development and common theme for computer science or electrical and computer engineering curriculum.Organization of the text is as follows.Chapter 1 and Chapter 2 cover materials which are fundamental to the course,compiled by Chen Ming(Shandong University of Science and Technology).This concludes propositional logic and predicate logic,which can turn a longwinded reasoning processes into a concise formulation,and are essential for serious academic papers.Chapter 3 contains set and their operations,compiled by Li Gang and Bi Xiao(Shandong University of Science and Technology).Sets are based on logic seen as a tool,and can represent and construct various mathematical objects.Chapter 4 deals with relations,including their operations and applications,compiled by Li Gang. Chapter 5 presents the notions of a function and cardinality of sets,and gives important examples of uncountable sets,compiled by Song Fengli(Nanjing University of Information Science and Technology).Chapter 6 introduces graph theory,compiled by Zou Jing(Tianjin University).Graphs are the sources of what is learned in data structures and algorithms.Chapter 7 contains algebraic systems,compiled by Dong Huanhe(Shandong University of Science and Technology),where we can answer why does multiplication and addition always seem similar.In addition,the exercises of the text are provided by Chen Ming and Duan Hua(Shandong University of Science and Technology).The corrections of the text are completed by Fang Yong(Shandong University of Science and Technology) and Chen Ming.
Chapter 1 Propositional Logic 1
1.1 The Basics of Propositional Logic 1
1.1.1 Propositions and Operators 1
1.1.2 Propositional Formulas 6
1.2 Propositional Equivalence 9
1.2.1 Equivalence and Some Basic Properties 9
1.2.2 Normal Form 12
1.3 Rules of Inference and Proof for Propositional Logic 19
1.3.1 Valid Arguments 19
1.3.2 Building Arguments and Proofs 23
Exercise 1 29
Chapter 2 Predicate Logic 33
2.1 The Basics of Predicate Logic 34
2.1.1 Language of Predicate Logic 34
2.1.2 Predicate Formulas 38
2.2 Predicate Equivalences 42
2.2.1 Equivalences 42
2.2.2 Prenex Normal Form 44
2.3 Rules of Inference for Predicate Logic 45
Exercise 2 48
Chapter 3 Sets 52
3.1 The Basics of Sets 52
3.1.1 The Set Concept and Set Description 52
3.1.2 Set Equality and Relationship between Sets 53
3.1.3 Some Special Sets 54
3.2 Operations on Sets 56
3.2.1 The Basic Operation 56
3.2.2 Set Identities 58
3.3 Principle of InclusionExclusion 60
Exercise 3 62
Chapter 4 Relations 66
4.1 The Basics of Relations 66
4.1.1 Order Pairs and Cartesian Product 66
4.1.2 Concept and Representations of Binary Relations 68
4.1.3 Operations on Relations 70
4.1.4 Properties of Relations 74
4.1.5 Closures of Relations 76
4.2 Equivalence Relations 82
4.2.1 Definition of Equivalence Relations 82
4.2.2 Partitions 84
4.3 Partial Order Relations 85
4.3.1 Definition of Partial Order 85
4.3.2 Hasse Diagrams 86
4.3.3 Special Elements in Posets 88
Exercise 4 89
Chapter 5 Functions 93
5.1 The Basics of Function 93
5.1.1 Concept and Properties of Functions 93
5.1.2 Inverse Function and Composition of Functions 96
5.2 Countability of Sets 97
5.2.1 Cardinality of Sets 97
5.2.2 Countable Sets and Uncountable Sets 99
Exercise 5 101
Chapter 6 Graphs 103
6.1 The Basics of Graphs 103
6.2 Graph Terminology 109
6.2.1 The Path 109
6.2.2 Connectivity 111
6.3 Representing Graph Using Matrices 113
6.3.1 Incidence Matrices 113
6.3.2 Adjacency Matrices 115
6.3.3 Reachability Matrices 116
6.4 Tree 117
6.5 Euler Graphs and Hamilton Graphs 119
6.5.1 Euler Graphs 119
6.5.2 Hamilton Graphs 123
6.6 Planar 125
6.6.1 The Concepts of Planar 126
6.6.2 Eulers Formulas 127
6.6.3 Kuratowskis Theorem 128
Exercise 6 129
Chapter 7 Algebra 132
7.1 Algebraic Structures 132
7.1.1 Binary Operations 132
7.1.2 Algebra 133
7.2 Groups 134
7.2.1 Concept of a Group 134
7.2.2 Subgroups 135
7.3 Rings and Fields 137
Exercise 7 138
References 140
书单推荐
