Discrete mathematics is an important branch of modern mathematics and the core course of basic theory of computer science. The main goal of discrete mathematics is to study the structure and relationship of discrete quantities, and its research object is generally finite or countable elements, so he fully describes the characteristics of discreteness in computer science. Because of the importance of discrete mathematics in computer science, many universities regard it as one of the specialized courses for postgraduate entrance examination, or as a part of it.

Discrete mathematics, as a course of computer department, has some similarities with other courses, and of course it has its own characteristics. Now we will simply analyze its characteristics as an examination content.

1, many definitions and theorems.

Discrete mathematics is a logical reasoning subject based on a large number of definitions. Therefore, understanding concepts is the core of our study of this subject. On the basis of these concepts, we should pay special attention to the relations between concepts, and the entities that describe these relations are a lot of theorems and properties.

Part of the examination is to examine the memory, understanding and application of definitions and theorems. For example, in the examination questions of Shanghai Jiaotong University in 2002, what was the compatibility relationship? If you know, it is easy to score; If you don't know, you won't get points anyway. This kind of topic is often ignored in review because of its low difficulty. In fact, this is a rather wrong understanding. In the examination questions of postgraduate courses, there are often questions that directly examine the memory of a certain knowledge point. For this kind of topic, candidates should be able to reproduce this knowledge point accurately, comprehensively and completely. Any ambiguity and omission will result in extremely regrettable loss of points. We suggest that readers, when reviewing, must take the above-mentioned "accuracy, comprehensiveness and completeness" as the standard to demand themselves. If they can't reach it, it means they still have to work hard. On this point, we will emphasize it in the later chapters, and let it run through the whole review process of discrete mathematics.

The definition of discrete mathematics is mainly distributed in the relations and functions of set theory, as well as in groups, rings, fields, lattices and Boolean algebras of algebraic systems. Be sure to learn by heart and understand well.

2. Strong methodology.

In the proof of discrete mathematics, the method is very strong. If you know how to prove a problem, you can prove it easily, otherwise you will get twice the result with half the effort. Therefore, in the usual review, we should be good at summing up, so that we can be comfortable with unfamiliar questions. In this book, we have summarized many problem-solving methods for readers. Readers should first be familiar with and know how to use these methods. At the same time, we also encourage readers to think hard and explore as many solutions to a problem as possible.

3. There is poverty.

Because discrete mathematics is "boring", it is difficult to come up with new questions. No matter what exam, many questions are old or slightly changed. "I am familiar with 300 Tang poems, and I can sing even if I can't write poems." If you get a problem set, do it from beginning to end, or even recite it. Then in the examination room, you will find that most of the questions are familiar or familiar. At this time, it is not too difficult to get better grades.

This book is specially written for the postgraduate entrance examination and is suitable for readers to review the postgraduate entrance examination. If you still have time, you can recommend two sets of problem sets. One is "Theory, Analysis and Solution of Discrete Mathematics" written by Zuo Xiaoling and others, and the other has three books, which is a set of discrete mathematics exercises written by Geng Suyun and others. Most of the questions in these two books are the same, but because of some differences in symbols and definitions, the setting and solution of questions are somewhat different.

Now let's analyze what types of problems there are in the postgraduate entrance examination and how we should deal with them.

1, basic question

The basic problem is to examine the memory of the definition, as well as simple proof and reasoning. The topic mainly revolves around mathematical logic and set theory. These topics don't need thinking, they are easy to get started.

The main problem of this sub-topic is to prevent carelessness and specious scores from being lost in the defined memory. People who don't pay attention to this will suffer big losses in the exam. For example, in the main conjunctive normal form, the assignment corresponding to the maximum term code is contrary to the assignment corresponding to the truth table, which will also make mistakes in many reference books; It is also necessary to prevent errors caused by not following certain methods. For example, when we do equivalent deduction in mathematical logic or set theory, we can omit some unimportant steps, as long as teachers and candidates are clear, but we can't omit any step in reasoning theory, otherwise it will be considered as a logical error.

In learning, we should also pay attention to mastery. For example, mathematical logic and set theory are interlinked, and we can combine them when memorizing or summarizing methods to facilitate comparison and understanding.

2. Theorem application questions

This part is the most "dead" part, which mainly embodies the strong methodological characteristics of discrete mathematics. Moreover, this part accounts for most of the exam content, so we must work hard on this part and remember various methods, and most of the scores of discrete mathematics will be obtained.

Here are some common applications:

● Prove equivalence relation: that is, prove that the relation is reflexive, symmetrical and transitive.

Prove the partial order relation: that is, prove that the relation is reflexive, antisymmetric and transitive. There are two kinds of proofs of special relationship, and the rest only need to be combined with definitions.

● Prove surjection: function f: x? Which means that for any y? Y, all have X? X, so f (x) = y.

● Prove correlation: function f: x? Y, which proves that for any x 1, x2? X, and x 1≠x2, then f (x1) ≠ f (x2); Or for any f(x 1)=f(x2), then x 1=x2.

● Prove set equipotential: that is, prove that there is bijection in two sets. There are three situations: first, it is proved that two specific sets are equipotential, and either a bijection is directly constructed or the correlation between the two sets is constructed by the construction method; Second, the cardinality of the set is known. What if it is? We assume that there is a bijection f between it and r, and then we deduce another bijection from the properties of f, so it is equipotential; What if it is? 0, then let there be bijection between and n; Third, the equipotential of two groups is known, and then the equipotential of the other two groups is proved. At this point, let the two known sets be bijective, and then prove that the two sets to be proved are bijective according to the residual conditions.

● Prove the group: that is, prove that the algebraic system is closed, combinable, unitary and inverse. Similarly, there are many concepts that can be used as proof questions in this part, so we should thoroughly understand them with definitions.

● Prove subgroups: Although subgroups have two proving theorems, if we prove subgroups, it is usually the second theorem, that is, let.

● Prove normal subgroups: If

● Proof Lattice and Sublattice: Sublattice has no conditions, so like proof lattice, it is proved that the largest and smallest elements of any two elements in the set are in the set.

Although the methodology of graph theory is not as strong as the previous parts, there are some methods, such as the longest path method, construction method and so on.

Step 3: Problems

The problem is that it is difficult to start the exam, and most candidates can't solve the questions used to open their grades. So, how do we analyze the problem?

There are four main problems, let's analyze them one by one:

① Comprehensive questions

The comprehensive problem is a problem that covers several chapters. Most of these problems are in coset, Lagrange theorem, normal subgroups and quotient groups in group theory. This part combines a lot of contents, which is both complicated and difficult to understand, and it is a difficult point in the whole discrete mathematics.

Firstly, Lagrange's theorem combines the group with equivalence relation and division, and relates it with the order of the group (some problems of order in subgroups are difficult, which is the basis of its solution); Then the quotient group combines the two groups, because the elements of the two groups are different, so the concepts must be clear at all times to avoid confusion; Then congruence relation combines group and relation, and defines a new relation. Natural homomorphism connects normal subgroups and quotient groups, which has also become the focus of some proof questions; The definition of kernel and group homomorphism theorem give another proof method of normal subgroup, because kernel is normal subgroup. ...

Of course, the comprehensive problem is not only here, but also discrete mathematics is a comprehensive subject, such as set theory and graph theory, which may become the proposition point of the comprehensive problem.

For the comprehensive problem, we can start from two aspects. First, no matter how the problem is set, we should look at the problem of proof, set the required format according to the type of theorem application, and then make further derivation; Secondly, we can look at the problem first, apply the property theorem of known conditions to push forward a few steps, and see which property is closer to the problem, and the problem will be solved.

② Exceptional problem

The exception question has two meanings. First, for theorem application questions, the judgment theorem and property theorem of a concept are not unique, while theorem application questions give the most frequently asked theorems, so some questions may test an uncommon theorem.

Secondly, there is another kind of problem that is contrary to our usual thinking. For example, some questions give a conclusion, saying that if they are right, please point them out, and if they are wrong, please prove them. Based on the experience of doing problems, we usually choose the idea of proof. In fact, we might as well take some time to see if we can point it out, so there is no need to prove it. Please look at the following example:

③ Off topic

Often some reference books will say that such chapters are not the focus and will not be tested, which is very wrong and harmful. In this way, these chapters have become a blind spot and another kind of problem for readers to review. These chapters usually have few concepts and theorems, so the topic itself is not difficult. But because I didn't review well or didn't review at all, there was something wrong with the exam, and it was very frustrating not to get the score. Therefore, we suggest that readers conduct a comprehensive review, unless it is the part that institutions explicitly indicate that they will not take the exam, the rest should be carefully reviewed. Even if you have little review time, at least you should understand the basic concepts and definitions. For discrete mathematics, the cardinal part in the chapter of function and the chapter of lattice and Boolean algebra are easily ignored.

When we review at ordinary times, no matter what courses, we must not leave dead ends, and the problems in these places are often very simple because of the limitations of their own content. It's a pity to lose it.

4 wrong questions

The topics of specialized courses are given to fewer teachers, unlike the basic courses, which have many arguments, so it is not surprising (though few) that there are mistakes. If we encounter a problem, we will get a contradictory answer through our judgment and deduction. Don't be overly superstitious about the authority of the topic, because it may be wrong.

Let's talk about the proof method of discrete proof questions:

1, direct proof method

Direct proof is the most common proof method, which is usually used to prove that something has the same properties, or that it must be something that satisfies certain properties.

Directly prove that there are two ways of thinking. The first way is to draw a conclusion from the known conditions, that is, to see the conditions and not know how to draw a conclusion. You can first draw some intermediate conditions from the known conditions according to the theorem (this step may be aimless, depending on what can be drawn from the known conditions), and then choose the conditions that can draw conclusions to continue the derivation; The other is to deduce the conditions from the conclusion, that is, when you see the conclusion, you can deduce it first to see from which conditions you can draw this conclusion (this step may also have no purpose, because you don't know which condition to use), and so on until you know the conditions. Usually these two ideas are carried out at the same time.

Step 2 reduce to absurdity

Reduction to absurdity is to prove that there is a certain example or property, and there is only one without a certain property.

The method is to assume the negative proposition of the proposed proposition first, and then deduce it according to the negative proposition and the known conditions, until the deduction contradicts the known conditions or theorems, then the hypothesis is considered untenable, and the proposition is proved.

3. Construction method

To prove the existence of an example or property, we can use the reduction to absurdity, assume that there is no such example or property, and then deduce the contradiction, or we can directly construct such an example. This is the construction method, and usually such a topic is more common in graph theory. It is worth noting that some topics are actually of this type, but they are relatively hidden. For example, proving that two sets are equipotential is actually proving that "there is a bijection in two sets", so we can assume that it does not exist, or we can directly construct this bijection through reduction to absurdity.

4. Mathematical induction

Mathematical induction is to prove the problems related to natural numbers, which can be recursive. When doing this kind of topic, we should pay attention to the content to be summarized.