Formula level: A single propositional variable A is a formula of level 0.

If A is an N-level formula and B is an M-level formula, then _A is an n+ 1 level formula; C=A∧B，C=A∨B，C=A→B，C=A？ The level of b is: max(n, m)+ 1.

For example (_(p→_q)∧((r∨s))? _q) The grading calculation is:

0 100 1

2 1 1

32

four

Four-layer formula

Let p 1, p2, p3? Pn is all sum propositional variables in formula A, so assigning them a true value is an assignment/explanation of A. If A= 1, it is a true assignment, otherwise it is a false assignment.

Therefore, a formula with n(n≥ 1) propositional variables has 2n different assignments.

Truth table: a table that lists the values of propositional formula A under all assignments.

Example: Write the truth table of (_p∧q)→_r, and find its true assignment and false assignment.

Extended data:

Subject content

1. set theory: sets and their operations, binary relations and functions, natural numbers and natural number set, cardinality of sets.

2. Graph theory: basic concepts of graphs, Euler graphs and hamiltonian graph, matrix representation of trees and graphs, planar graphs, graph coloring, dominating sets, covering sets, independent sets and matching, weighted graphs and their applications.

3. Algebraic structure: the basic concepts of algebraic system, semigroup and singularity, group, ring and field, lattice and Boolean algebra.

4. Combinatorial mathematics: combinatorial existence theorem, basic counting formula, combinatorial counting method and combinatorial counting theorem.

5. Mathematical logic: propositional logic, first-order predicate calculus and resolution principle.

Discrete mathematics is a comprehensive subject which integrates traditional logic, set theory (including function), number theory, algorithm design, combinatorial analysis, discrete probability, relation theory, graph theory and tree, abstract algebra (including algebraic system, group, ring, field, etc.). ), Boolean algebra, computational models (languages and automata) and so on. The application of discrete mathematics covers many fields of modern science and technology.

Discrete mathematics can also be said to be the basic core discipline of computer science. There is a famous typical example in discrete mathematics-the four-color theorem, also known as the four-color conjecture, which is one of the three major mathematical problems in the modern world.

It was put forward by the British draftsman Fernandez guthrie in 1852. When he was coloring the map, he found a phenomenon: "Each map can only be colored in four colors, and countries with the same border can be colored in different colors." .

So can this be proved mathematically? 100 years later 1976, KennethAppel and WolfgangHaken used computer-aided calculation, which took 1200 hours and 1000 billion judgments, and finally proved the four-color theorem, causing a sensation in the world. This is discrete mathematics.

Discrete mathematics can be regarded as a bridge between mathematics and computer science, because discrete mathematics is not only inseparable from mathematical knowledge such as set theory and graph theory, but also related to database theory and data structure in computer science. It can lead people into the thinking field of computer science and promote the development of computer science.

References:

Baidu encyclopedia-discrete mathematics