Discrete Definition and 897 Threads

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets (finite sets or sets with the same cardinality as the natural numbers). However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
The set of objects studied in discrete mathematics can be finite or infinite. The term finite mathematics is sometimes applied to parts of the field of discrete mathematics that deals with finite sets, particularly those areas relevant to business.
Research in discrete mathematics increased in the latter half of the twentieth century partly due to the development of digital computers which operate in discrete steps and store data in discrete bits. Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages, cryptography, automated theorem proving, and software development. Conversely, computer implementations are significant in applying ideas from discrete mathematics to real-world problems, such as in operations research.
Although the main objects of study in discrete mathematics are discrete objects, analytic methods from continuous mathematics are often employed as well.
In university curricula, "Discrete Mathematics" appeared in the 1980s, initially as a computer science support course; its contents were somewhat haphazard at the time. The curriculum has thereafter developed in conjunction with efforts by ACM and MAA into a course that is basically intended to develop mathematical maturity in first-year students; therefore, it is nowadays a prerequisite for mathematics majors in some universities as well. Some high-school-level discrete mathematics textbooks have appeared as well. At this level, discrete mathematics is sometimes seen as a preparatory course, not unlike precalculus in this respect.The Fulkerson Prize is awarded for outstanding papers in discrete mathematics.

View More On Wikipedia.org
Recent contents Top users
  1. S

    Discrete Mathematics - Basic Set Theory : Assignment review : Q1

    Question 1 : -------------------- Homework Statement Consider the following sets, where U represents a universal set : U = {1, 2, 3, 4, ∅, {1}} A = {1, 3} B = {{1}, 1} C = {2 , 4} D = { ∅ , 1, 2 } Homework Equations Choose the correct option : D - B is the set ...
  2. B

    MHB Sum of a discrete finite sequence

    Hii everyone, I have a sequence {ai,1<= i <=k} where i know the sum of this sequence(say x). I want to know the sum of another sequence {bi, 1<=i <=k}(at least a tight upper bound) where bi=ai*(1/2^i). Or in other words, if you know the sum of the ratio sequence and sum of 1 sequence, how to...
  3. S

    Set Theory : Discrete Mathematics

    Homework Statement The Question data is as follows : Consider the following sets, where U represents a universal set : U = {1, 2, 3, 4, ∅, {1}} A = {1, 3} B = {{1}, 1} C = {2 , 4} D = { ∅ , 1, 2 ) Homework Equations Which one of the following statements is true ? 1. The...
  4. S

    Probability: Discrete Random Variable

    Homework Statement Suppose X is a discrete random variable whose probability generating function is G(z) = z^2 * exp(4z-4) Homework Equations No idea The Attempt at a Solution I'm thinking that due to the exponent on the z term, that the exp(4z-4) would be the P[X=3] =...
  5. H

    Discrete Math: Proving p(x)|(p1(x)-p2(x)) is Equiv. Rel.

    Homework Statement Let p(x) be a polynomial in F[x]. Show that p1(x)≈p2(x) if and only if p(x)|(p1(x)-p2(x)) is an equivalence relation The Attempt at a Solution To be completely honest, I have no idea where to begin. This class has been a nightmare and this has been, by far, the worst...
  6. H

    Discrete Math - Modular Arithmetic

    Homework Statement For which values of n≥2 does the implication: axb=0 ⇔ a=0 or b=0 For some Zn (n should be a subscript) NOTE: For the a x b, the x should be the x that has a circle around it. I didn't see that symbol in the "quick symbols" :) Homework Equations I know that this...
  7. Hercuflea

    Schools Trouble in Discrete math will it affect my graduate school opportunities?

    Hello everyone, I'm a first time poster and I just want to say this forum is great. Every time I have a question Physics Forums is the first site to answer it. So lately I have been really struggling in my Discrete Mathematics I course at my university. This is one of the few times in...
  8. U

    MHB Functions of a Discrete Random Variable

    EDIT: Oh and I forgot that $p_Y(y) = 0$ otherwise.
  9. C

    Current density of discrete charges in 1D space

    Hi guys I am new here. I was asked by my professor a problem: a positron-electron pair is produced at the leftmost position of a 1D circular loop of radius R. e+ moves along the bottom hemisphere and e- moves along the upper one. They are confined in the circular loop and perform circular...
  10. B

    Discrete Math: What's the Best Way to Get Started?

    Would learning discrete math be more beneficial then diving into velleman's book right away? and what is a good book on discrete math?
  11. F

    How do you find the zeroes of a discrete function?

    Would Newton's method or some other method work? Consider the following problem: find the zeroes of the function: y = 40sin(2x) - floor(40sin(2x)) where Y,X \in R I don't exactly know how to handle this problem. My best insight so far is that it is only equal to zero whenever 40sin(2x)...
  12. M

    Question about discrete Monte Carlo Summation

    Hello all, I'm aware of the Monte Carlo Summation method in discrete spaces, where you can approximate a very long summation over the entire space by a shorter one with only a few randomly selected terms from the original summation (weighted by the inverse probability density of them being...
  13. M

    Question about discrete Monte Carlo Summation

    Hello all, I'm aware of the Monte Carlo Summation method in discrete spaces, where you can approximate a very long summation over the entire space by a shorter one with only a few randomly selected terms from the original summation (weighted by the inverse probability density of them being...
  14. A

    Help with a discrete math homework problem

    Homework Statement show that for positive r and s, with r<s, we always have: r<(r+s)/2<s and 2/[(1/r)+(1/s)]^2< 2rs< (r+s)^2 Homework Equations The Attempt at a Solution i have shown that r<s because r+r<s+r, 2r<s+r, r<(s+r)/2 and 2r< (2s+2r)/4 (r+s)^2= r^2+2rs+s^2...
  15. R

    Discrete Math - Pigeonhole Principle Problem

    Homework Statement Suppose that a menu consists of 4 main dishes, 9 choices of side dishes, and 6 desserts. A small meal consists of one main dish and two different side dishes and no dessert. A large meal consists of one main dish, two different side dishes and dessert. How many patrons must...
  16. S

    Finding Discrete Counterpart of Continuous Variable Energy Term

    Dear Sir… I am looking for a discrete counter part of a continuous variable. the continuous version of energy term in a liquid crystal is given by [\vec{n}\cdot(\nabla\times\vec{n})]^2. This is a square of a dot product between a vector 'n' and its curl field. My question is what is the exact...
  17. P

    Can a Discrete Random Variable's CDF Jump at Every Rational Number?

    I have seen the following "extension" of discrete random variables definition, from: pediaview.com/openpedia/Probability_distributions (Abstract) "... Equivalently to the above, a discrete random variable can be defined as a random variable whose cumulative distribution function (cdf)...
  18. P

    About the definition of discrete random variable

    About the definition of "discrete random variable" Hogg and Craig stated that a discrete random variable takes on at most a finite number of values in every finite interval (“Introduction to Mathematical Statistics”, McMillan 3rd Ed, 1970, page 22). This is in contrast with the assumption that...
  19. T

    Paradox of motion implies discrete space?

    Came across this video which says that a moving object has to cover infinitely many intervals in order to get from one point to another and because of this motion couldn't really take place and since it does take place, its a paradox. youtube.com/watch?v=u42Y3RbP7JE Since motion does take...
  20. R

    Discrete Math/Combinatorics Question

    Homework Statement This question has two parts: a) How many integers are there between 100 and 1,000,000 with the property that the sum of their digits is equal to 6? b) How many integers are there between 100 and 1,000,000 with the property that the sum of their digits is less than 6...
  21. C

    Recurrence relations discrete math problem

    Homework Statement Find the general solution to the following recurrence relations (defined n≥2). c) an=6an-1-9an-2+8n+4 Homework Equations The Attempt at a Solution an=6an-1-9an-2+8n+4 8n+4= an -6an-1+9an-2 R2-6R+9=0 R=3,3 So hn=A(3)n+B(3)n Assume pn=Cn+Cn2 → This is where I got...
  22. X

    Discrete time Derivative/Integration mechanisms in DSP.

    I was having a conversation with my brother, a mechanical engineer, about Digital Signals processing. I was trying to explain what I had recently done in my digital controls class, and how we would use the state space model \vec{x}(k+1) = {\bf{A_d}}\vec{x}(k) + {\bf{B_d}}u(k) in discrete time...
  23. A

    Discrete samples into continuous signal

    A) Let us say that we have some arbitrary sequence of natural numbers. e.g. 1, 2, 7, 3, 17, 19. Is it possible to convert every finite and infinite sequence into some continuous function model, such as in Fourier theory? I know that it is possible to extract some discrete samples from a...
  24. C

    Ambiguity about roots of unity in discrete Fourier transform

    Hi everyone, I have a question on the discrete Fourier transform. I already know its a change of basis operator on C^N between the usual orthonormal basis and the "Fourier" basis, which are vectors consisting of powers of the N roots of unity. But if i recall correctly from complex...
  25. T

    Is Impulse a Discrete Observable in Physics? Exploring Possible Models

    Hi there, I have a short thought that I want to share with all of you and see if there has been something written about it and, if not, why not?: A free particle spin is something that can take a discrete range of values, as it happens with electromagnetic or colour charge. However the other...
  26. X

    Conditional Probability for discrete random variables.

    Homework Statement Compute P(X=k l X+Y=p)Homework Equations The Attempt at a Solution No idea. Kind of understand page #1. Although it seems like there's a lot of unnecessary stuff. Could have gone straight from the top to the bottom. And I don't know why/if you even have to substitute the...
  27. P

    Discrete: Recurrence relation for sum of integer using only 2's and 3's.

    Homework Statement Find a recurrence relation for Tn, the number of ways to write an integer n as the sum of terms, each of which is 2 or 3, and the order matters. [So 2+3 and 3+2 are different sums for 5.]Homework Equations (if I had one, this would be easier) The Attempt at a Solution So I...
  28. sunrah

    Stochastics: discrete random variables

    Homework Statement X1 and X2 are two independent discrete random variables with P(X1 = k) = c3-k P(X2 = k) = d4-k for k in natural numbers and where X1, X2 in natural numbers is almost always valid. 0 is not include in N. Find constants c and d. Homework Equations The Attempt...
  29. C

    Is space currently thought of as discrete or continuous?

    I was wondering what the majority opinion was on this issue, among physicists and philosophers as well. I can't imagine zooming in a million times smaller than the plank length and still not being at a smallest length, however a discrete universe doesn't make much sense to me. Are there any...
  30. 7

    Ph.D. programs with discrete mathematics

    I've been having trouble finding many pure math Ph.D. programs with active research groups in the general field of discrete mathematics (perhaps due to its interdisciplinary nature). I'm only aware of the top schools in this field (e.g. Carnegie Mellon, Georgia Tech, UCSD, Rutgers); can anyone...
  31. E

    Non discrete metric space on infinite set

    Homework Statement let d be a metric on an infinite set m. Prove that there is an open set u in m such that both u amd its complements are infinite. Homework Equations If d is not a discrete metric, and M is an infinite set (uncountble), then we can always form an denumerable subset...
  32. R

    Discrete math, proving the absorption law

    Homework Statement Prove the second absorption law from Table 1 by showing that if A and B are sets, then A ∩ (A ∪ B) = A. Homework Equations Absorption laws A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A The Attempt at a Solution i will show A ∩ (A ∪ B) is a subset of A x is any element in A...
  33. Shackleford

    Discrete Math Exam Proofs: Senioritis & Graduation

    These are potential proofs for the discrete math exam on Tuesday. I haven't been able to find proofs online. I have senioritis, and I'm graduating in a few weeks. Is a proof by contraposition the best way to prove this? If you assume h is not a function or g is not a function, then that would...
  34. M

    Discrete Random Variables - Geometric Distribution

    Hi Guys, Long time reader first time poster... This simple question has stumped me all day and I think I've finally cracked it! I'm hoping someone can confirm that, or tell me how wrong I am - either is fine :) One in 1000 cows have a rare genetic disease. The disease is not contagious...
  35. R

    Discrete Fourier Transform of Even Function

    I'm confused about the DFT of the data, fn = cos(3\pin/N) for n=0,1,...,N. It is definitely an even function, and I read that the Fourier coefficients of an even function is real. But when I take the FFT of this in Matlab I get complex numbers, not real numbers. What am I missing? Thanks ...
  36. K

    Discrete Optimization - Genetic Algorithms

    Homework Statement I have a whole two courseworks on Genetic Algorithms, but we have been shown no examples. I am stumped! 1. A function f is set to depend on five variables x1, . . . , x5 where x1 can take 2 different values, x2 can take 8 different values and x3, x4, x5 each take 4 different...
  37. T

    Distribution of sum of discrete random variable

    Edit: I have to think more about this, I'll post later.
  38. G

    Discrete Math Question ( not really homework) about strong induction

    For some questions strong induction would test for cases n+1, n+2 and for other n+1,n+2,n+3, or other ways, why is that? Here's two examples Suppose that the only paper money consists of 3-dollar bills and 10-dollar bills. Find what dollar amounts can be made from a combination of these...
  39. S

    Discrete uniform distribution prrof

    Hello, I'm currently in high school and going over discrete uniform distribution, and we've come across this formula. I'm curious if anyone could show me how the formula is true, as when I asked my teacher he just said that it'll confuse the class and we don't need to know why it's true. If...
  40. C

    Discrete math set theory sum problem

    Homework Statement Prove that if k>1 then, 5/(k-1)-3/k-2/(k+2) = (9k+6)/(k-1)k(k+2) Hence simplify Ʃ of k=2 to n {(3k+2)/(k-1)k(k+2)} Homework Equations The Attempt at a Solution Ok so the first part is ok I just multiplied the denominators with the numerators and...
  41. A

    MATLAB 2D discrete function minimization if extreme points are known, using Matlab

    Hello everyone. I would like to hear some suggestions on minimizing a function. I have discrete 2D function (a grid, where each (x,y) point have some value), where I know only extreme points (more specifically - ridges. http://en.wikipedia.org/wiki/Ridge_detection). I want to reconstruct...
  42. B

    Understanding Discrete Math for the Confused

    I read the definition of discrete math and i read the definition of discrete. i just can't seem to figure out what discrete math is, can you guys show what it means?
  43. S

    MATLAB Discrete Fourier Transform in MATLAB

    Hello all, first time here and I have really silly problem... I am working on something in MATLAB, in which I have to make discrete Fourier transform of gaussian distributed variable. i.e. array of numbers which are taken from f(x)~exp(-x^2). I know that when you Fourier transform it with...
  44. S

    Discrete Math: Proving something is logically equivalent

    Homework Statement Show that (p ∧ q) → r and (p → r) ∧ (q → r) are not logically equivalent. Homework Equations a → b = \nega v b The Attempt at a Solution I'm sorry. I'm completely stumped on how to go about this problem. I'm not asking for the solution since I want to know how...
  45. T

    Discrete Wavelets - Question on decimation of high pass

    Hi, I'm trying to grasp the concept of discrete wavelets and can't seem to find an answer to my question. In the decomposition of a signal using wavelets filter banks, the signal goes through a low pass and high pass filter. The output of the low pass and high pass is decimated by 2. I can...
  46. S

    Discrete math, sets, power sets.

    Homework Statement If s (0,1), find |P(S)|, |P(P(S))|, |P(P(P(S)))| Homework Equations The Attempt at a Solution |P(S)| = {(0), (1), (0,1), ∅} = 4 |P(P(S))| = {...} = 16. |P (P(P(S)))| = {...} = 16 ^4 ...but how? as my lecturer explained it, it come from pascals...
  47. G

    Discrete Math Logic Defineing a function recursion-ish

    (3) De fine a function A(m,n) as follows. A(0,n) = 2n for every n. A(m,0) = 0 for every m >= 1 A(m,n) = 2 if m >= 1 and n = 1 A(m,n) = A(m -1,A(m, n - 1)) otherwise (i.e., if m >= 1 and n >= 2. (b) Prove A(m,2) = 4 for every m >= 2 (c) Prove A(1, n) = 2^n for every n >= 1. Proving...
  48. D

    MHB Does the Logistic Difference Equation Have an Exact Sinusoidal Solution?

    Verify that an exact solution exist for the logistic difference equation $$ u_{t+1}=ru_t(1-u_t),\quad r>0 $$ in the form $u_t=A\sin^2(\alpha^t)$ by determining values of r, A and alpha. Is the solution periodic? Oscillatory? I have yet to encounter a problem that says verify a solution...
  49. D

    MHB What is the process for finding the maximum and minimum of a discrete model?

    To find the max and min of a discrete model, I solve $$ \frac{df}{dN_t} =0\Rightarrow N_m $$ Then $N_{\text{max}} = f(N_m)$, correct? Because whenever I try to solve $$ N_{t+1} =\frac{(1+r)N_t}{1+rN_t} $$ It doesn't work. The derivative is $$ \frac{1+r}{(1+rN_t)^2}=0 $$
  50. M

    Fourier Transform of a discrete function

    I have a set of N data points defined over a periodic interval, 0\le x \le 1. I made a discrete fast Fourier transform of these data points and I get a discretized function in the Fuorier space. My question is what are the coordinate of these data points in the Fourier space? I mean, in the real...
Back
Top