maths.free › Discrete Math & Logic › Introduction and Preliminaries › What is Discrete Mathematics?
What is Discrete Mathematics?
discrete / dis'krët. Adjective: Individually separate and distinct. Synonyms: separate - detached - distinct - abstract. Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics?
What is Discrete Mathematics?
discrete / dis'krët.
Adjective: Individually separate and distinct.
Synonyms: separate - detached - distinct - abstract.
Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics? The study of numbers? In part yes, but you also study functions and lines and triangles and parallelepipeds and vectors and . Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Well, those that involve numbers, functions, lines, triangles, . Whatever your conception of what mathematics is, try applying the concept of discrete to it, as defined above. Some math fundamentally deals with stuff that is individually separate and distinct.
In an algebra or calculus class, you might have found a particular set of numbers (perhaps they constitute the range of a function). You would represent this set as an interval: \([0,\infty)\) is the range of \(f(x) = x^2\) since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them that are also in the set.
Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function that gives the number of children of each person reading this. What is the range? I'm guessing it is something like \(\{0, 1, 2, 3, 4\}\). Maybe 5 or 6 is in there too.Even larger natural numbers for old ladies who live in shoes. But certainly nobody reading this has 1.32419 children. This output set is discrete because the elements are separate. The inputs to the function also form a discrete set because each input is an individual person.
There are many discrete mathematical objects besides sets of numbers; we will introduce some of these in . Studying these discrete structures is the main focus of discrete mathematics and this book. However, the reason we want to study these structures is because they provide a way to model real-world problems.Many of the problems discussed in this book are admittedly contrived and clearly fictional, but hopefully you will see how these toy problems can be generalized to actually represent problems that people would care about in reality.
To get a feel for the subject, let's consider the types of problems you solve in discrete math. Here are a few simple examples:
Condensed: the full section is in Levin, Discrete Mathematics: An Open Introduction.
今度はあなたの番 計算機では解けませんが、計算可能です。下の一つを試してみましょう。もしくは自分で入力してください。
練習 (2)
まず紙で解いてみてください。答えを表示して確認できます。検証済みの問題は、ソルバーで全ステップを開けます。
-
Right now, how would you describe what discrete mathematics is about, if you were telling your friends about the class you are in? Write one or two sentences.
-
What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
ここで使用された記号
どの記号をタップしても、定義、画像、それぞれの文字の意味が表示されます。
よくある質問
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). ここでは要約して説明し直しています。誤りは私たちの責任です。
More in Discrete Math & Logic
Truth tablesSums and inductionProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsGraphs: degrees, paths and connectivityTrees and spanning trees