Movatterモバイル変換

What Is Discrete Math?

Last Update: 29 June 2013

Note:or material is highlighted

"Discrete Math" is not the name of a branch of mathematics, likenumber theory, algebra, calculus, etc.
Rather, it's a description of aset of branches of math that all have in common the feature that theyare "discrete" rather than "continuous".
The members of this set include (certain aspects of):
- logic and Boolean algebra
- set theory
- relations and functions
- sequences and series (or "sums")
- algorithms and theory of computation
- number theory
- matrix theory
- induction and recursion
- counting and discrete probability
- graph theory (including trees)
To get a feel for what "discrete" means, here are some rough definitions thatyou might find useful:
1. A setiscountable =def its members can be put intoa 1-1 correspondence with the positive natural numbers (i.e.,1,2,3,…);
  i.e., a set is countable iff its members can be counted.
  - Note that the following sets are all countable:
    1. W: the positive natural numbers themselves!(1,2,3…)
    2. N: the natural numbers (0,1,2,3…)
    3. Z: the integers (…–3,–2,–1,0,1,2,3…)
    4. Q: the rational numbers (i.e., fractions,or repeating decimals)
  - However,R, the real numbers (i.e., the rationalsplus all the non-repeating decimals, such asπ,e, √2, etc.), isnotcountable!
  - So, one feature of being "discrete" is thatdiscrete objects are countable.
  - The study of the realsisnot part of discrete math.
    - But the studyof how torepresent reals by approximations,as computers do, could be considered part of discrete math).
2. A setis dense =def:
  1. it is "totally" (or "linearly")ordered
    (i.e., any two members of the set are comparable interms of an ordering, such as a less-than relation)
    and
  2. for any 2 members of the set, there is a third member that isbetween them.
  - Roughly, a totally-ordered set is dense iff,no matter how close two members are, you can alwaysfind another member squeezed in between them.
  - E.g., the reals and the rationals are dense.
    - However, the rational number line has"gaps":
      - No matter how closely you findtwo rationals "squeezed" together, you'llnever find π.
      - You can approximate πas closely as you want (because the rationalsare dense), but you'll never "hit" π.
  - But the integers are not dense.
  - Some people consider that the study of dense sets isnot part of discrete math
3. A setis continuous =def (and this is averyrough definition!!)
  1. it is dense
    and
  2. it has no "gaps".
  - So…
    - The real number line is continuous.
    - It is sometimes called "thecontinuum" (pronounced/con-tin-you-um/).
    - In fact, some mathematiciansdefine a continuous set as just the real numbers.
  - There are lots of formal ways to define thecontinuum; here's one:
    Here's what this means:
  - The reals are not countable.
  - The study of continuous sets isnotpart of discrete math.

The above can be summarized in a chart:

Set	Name	Members	Has gaps?	Countable?	Dense?	Continuous?	Discrete?
W	positive naturals	1,2,3…	yes	yes	no	no	yes
N	naturals	0,1,2,3…	yes	yes	no	no	yes
Z	integers	…–3,–2,–1,0,1,2,3…	yes	yes	no	no	yes
Q	rationals	fractions/repeating decimals	yes	yes	yes	no	???
R	reals	all decimals, including non-repeating	no	no	yes	yes	no

From this, we can see thatW,N, andZ are clearly"discrete" and thatR is clearly not discrete.

ButQstands somewhere in the middle:

It is countable and "gappy", but also dense.

There are some intuitive ways of thinking about the discrete-vs.-continuous distinction:
1. A piano makes music in a "discrete" way:
  But a violin makes music in a "continuous" way:
2. An analog clock (i.e., a clock with hands) is(at least in theory) continuous:
  But a digital clock is discrete:
  - Here is an interesting comment on the trade-off betweenthe discrete and the continuous (also called "analog[ue]"):
    - "A distinction is sometimes made between digital andanalogical signs. Indeed, Anthony Wilden declares that ‘no twocategories, and no two kinds of experience are more fundamental in humanlife and thought than continuity and discontinuity’(Wilden 1987, 222).Whilst we experience time as a continuum, we may represent it in eitheranalogue or digital form. A watch with an analogue display (with hour,minute and second hands) has the advantage of dividing an hour up like acake (so that, in a lecture, for instance, we can ‘see’how much time isleft). A watch with a digital display (displaying the current time as achanging number) has the advantage of precision, so that we can easilysee exactly what time it is ‘now’." (Chandler, Daniel (2009),Semiotics for Beginners,"Signs".)
3. Discrete math concerns sets of objects that are countable.
  Continuous math concerns sets of objects that are "measurable".
4. A film, with "frames", is discrete.
  The real eventsdepicted on the film are continuous.
To find other explanations, do a Google search on "discrete math","discrete vs. continuous", and "discrete math vs. continuous".
The following are especially good:
1. Introduction—Continuous vs. Discrete Data
  - An illustration of the film analogy mentioned above.
2. Math Forum—Ask Dr. Math
3. Discrete Mathematics—from Wolfram MathWorld
4. Continuous vs. Discrete Mathematics:
  - In case the above link disappears again, here's what itsays:
    "Continuous vs. Discrete Mathematics
    The world of mathematics can be divided roughly into two realms: thecontinuous and the discrete. The difference is nicely illustrated bywristwatches. Continuous mathematics corresponds to analog watches - thekind with separate hour, minute, and second hands. The hands movesmoothly over time. From an analog watch perspective, between 12:02 P.m.and 12:03 P.m. there are infinitely many possible different times as thesecond hand sweeps around the watch face. Continuous mathematics studiesconcepts that are infinite in scope, where one object can blend smoothlyinto the next. The real-number system lies at the core of continuousmathematics and - just like the watch - between any two real numbers,there is an infinity of real numbers. Continuous mathematics providesexcellent models and tools for analysing real-world phenomena thatchange smoothly over time, including the motion of planets around thesun or the flow of blood through the body.
    Discrete mathematics, on the other hand, is comparable to a digitalwatch. On a digital watch, there are only finitely many possibledifferent times between 12:02 P.m. and 12:03 P.m. A digital watch doesnot acknowledge split seconds! There is no time between 12:02:03 and12:02:04. The watch leaps from one time to the next. A digital watch canshow only finitely many different times, and the transition from onetime to the next is sharp and unambiguous. Just as the real-numbersystem plays a central role in continuous mathematics, integers are theprimary tool of discrete mathematics. Discrete mathematics providesexcellent models and tools for analysing real-world phenomena thatchange abruptly and that lie clearly in one state or another. Discretemathematics is the tool of choice in a host of applications, fromcomputers to telephone call routing and from personnel assignments togenetics.
    Edward R. Scheinerman,Mathematics, A Discrete Introduction(Brooks/Cole, Pacific Grove, CA, 2000): xvii–xviii."
5. On the differences between discrete/digital and analog, see:
  - Haugeland, John(1981),"Analog andAnalog",Philosophical Topics12(1) (Spring): 213–225.
  - Maley, Corey J. (2011),"Analog and Digital, Continuous and Discrete",Philosophical Studies155: 117–131 [DOI 10.1007/s11098-010-9562-8].
6. Bell, John L. (2005),The Continuous and the Infinitesimal inMathematics and Philosophy
  - See especially Chapter 1: "The Continuous and theDiscrete in Ancient Greece, the Orient, and the EuropeanMiddle Ages"
7. Bell, John L. (2005),"Oppositions and Paradoxes in Mathematics andPhilosophy",Axiomathes 15: 165–180.
  - Just read pp. 1–16 of the online version.

[8]ページ先頭