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. C

    Integral arising in estimation of discrete series

    I'm trying to solve f(t;a,b)=\int_a^b\sqrt{t-x^3}dx or find a good estimate for it. The problem is 'nice', and so various niceness assumptions apply: 0\le a\le b\le t -- and if other assumptions are needed, they probably hold. :D An example of a bad estimate would be (b-a)\sqrt{t-a^3} --...
  2. L

    Discrete math venn diagram proof

    Prove for all sets A,B, and C : A complement UNION B complement = (A intercept B) complement help me out here please
  3. T

    Interchanging discrete summation signs

    When needed to do that, I found it much easier to pretend it's an integral summation and then draw the area diagram then work it out from the picture the new terminals for the integral. Then convert that back into the discrete sum. Is that how you would do it? However for three or more...
  4. H

    Action for a discrete potential

    Hello, I have a potential function given numerically at points evenly spaced. That is to say, I have the numerical values of V(0), V(\delta), V(2\delta), V(3\delta), ..., in some interval. I need to calculate the action integral in terms of initial and end-points: S(x_b, t_b; x_a, t_a). I...
  5. M

    Discrete spacetime means discrete momentum ?

    discrete spacetime means discrete momentum ?? the question is using De Broglie's Wavelength \lambda = h|p|^{-1} then in case space is discrete would mean that there is a minimum possible wavelength in nature , for example \lambda = k l_{p} for Planck's length this would mean that the...
  6. O

    Discrete Math: Sets/Functions/Proofs

    I apologize for the title, I really don't know how to describe these problems, so I just listed the categories that they fall under. Anyways... Homework Statement Let f: A->B be a function, where A and B are finite sets and |A| =|B| (they have the same size I believe). Prove that f is...
  7. K

    Are Linear Algebra and Discrete Math Essential for Aspiring Physicists?

    From experienece, are these two courses really important to someone looking to major in physics? I've read the "So you want to be a physicist" guide, but if I work with the book Mathematical Methods in the Physical Sciences, will it be enough to make it through the upper level physics courses...
  8. R

    Discrete random variables and PMF

    Homework Statement A discrete random variable X has the following PMF x | 1 | 2 | 3 | 4 | 5 | p(x)|1-a|1-2a|0.2| a | 0.5a| What are the values of "a" that are allowed in this PMF? For the allowed values, compute the expected value and the standard deviation of the variable...
  9. C

    Parallel discrete logs (continues: modular arithmetic)

    I'm working on a problem that involves calculating many discrete logarithms in GF(p): given n and an odd prime p, either find a k with 2^k\equiv n\pmod p or return "failure" if no such k exists. Now there are many algorithms for computing discrete logarithms, some of which are designed for many...
  10. qspeechc

    Discrete Structures: Worth Studying for Maths Majors?

    Hi. I would be terribly grateful for your help. I am a second year student, and I am pretty sure I will major in Mathematics, and will probably (if I'm smart enough), do maths post-grad. I was looking through the faculty handbook, and saw that for 2nd year math they offered a module on...
  11. Somefantastik

    Solving Discrete Distribution: P(X = 0 & 1)

    I need help getting started on this. Want to generate a random variable X, equally likely 0, 1, using biased coin (heads probability p). 1. Flip coin, result is labled 0_{1} 2. Flip coin, result is labeled 0_{2} 3. 0_{1} = 0_{2} => return to step 1 4. 0_{2} = heads => X = 0, 0_{2}...
  12. H

    Unit-Pulse Response for Discrete Time System

    The question is: Compute the unit-impulse response h[n] for n=0,1,2,3 for each of the following discrete-time systems. Equation: y[n+1] + y[n] = 2x[n] I am trying to figure out how to solve this equation. I understand the example in the book but I don't understand what to do when it...
  13. K

    Is Every Rational Number Always a Ratio of Two Integers?

    Rewrite the following statement formally. Use variables and include both quantifiers \forall and \exists in your answer. Statement: Every rational number can be written as a ratio of some two integers. If I didn't have to use \exists I'd write it as follows \forallrational numbers...
  14. S

    Impulse Response In A Discrete System

    Hey guys, this is my first post and I'm looking for a bit of help This is going to sound really easy (and I know it is) but I can't for the life of me remember how to work out the Impulse Response Function of this system. I've tried google for a few hours but nowhere that gives it in laymans...
  15. MathematicalPhysicist

    Discrete spacetime (Some contemplations of mine).

    Im reading 'three roads to quantum gravity', and it's written there that any theory trying to unify between QM and GR has as conclusion that space has a discrete quantity where you cannot divide space more than this. now how would you propose to verify this assertion? I mean assume you've...
  16. G

    What is a complete set of representatives for an equivalence relation on a set?

    Homework Statement Definition: let R be an equivalence relation on a set X. A subset of X containing exactly one element from each equivalence class is called a complete set of representatives. now define a relation R on RxR by (x,y)R(u,v) <---> x^2 + y^2 = u^2 + v^2. You don't have to...
  17. G

    What is the range of the function g: ZxZ --> ZxZ given by g(m,n)=(m-n,m+n)?

    Homework Statement Find the range of the function g: ZxZ --> ZxZ given by g(m,n)=(m-n,m+n). Hints: First recall that if f: A ---> B then Range (f)={b e B such that there exists an A in A with b=f(a). Second, if you claim that some set C is the range, then you must show that i) C is a subset...
  18. A

    Discrete Mathematics - Combinations/Factorials?

    Homework Statement An electronic switch bank consists of a row of six on - off switches. How many different settings are possible if exactly three of the switches are set to off? (a) 12 (b) 144 (c) 60 (d) 30 (e) 20 Homework Equations Factorial rule...
  19. A

    Discrete Math - Complete set of representatives

    [SOLVED] Discrete Math - Complete set of representatives Homework Statement At what temperature fahrenheit is it equal to celsius? Homework Equations (none) The Attempt at a Solution
  20. A

    Discrete Mathematics - Permutations/Combinations?

    Homework Statement A certain state issues a series of automobile license plates such that each license plate must have 2 letters followed by three digits. An example license plate would be AD 025 . If the letters and the digits cannot be repeated, how many different license plates can be...
  21. P

    How Is the Probability of the First Head on Odd Flips Calculated

    Can anyone explain to me how this problem is solved Determine the probability that the first head appears on an odd number of flips i.e. X contains {1,3,5..}. P[X] = summation starting at x = 1 to infinity (1/2)^(2x-1) = 1/2 / (1 - 1/4) = 2/3 Basically my question is, how is the...
  22. B

    Discrete Math: Counting Algorithm & Function Problems

    I have two problems that I am having a little trouble with. Thanks in advance. Homework Statement Count the number of times the following algorithm prints "Hello", then find the "best" big-oh approximation for the number of print statements in the algorithm. For i=1 to n Begin Print...
  23. J

    Lienard-Wiechert potential for 2 discrete Qs

    I've tried a simple derivation of the Lienard-Wiecher potential for 2 discrete charges separated by dr, but end up with a result which isn't the same as the theoretically correct version: Take two charges q1 @r1, q2 @r2 with r1 > r2, dr = r1 - r2, parallel and both traveling at velocity v...
  24. G

    Can we understand the laws of physics without infinitesimals and infinities?

    Has there been any attempts to formulate general laws of physics without involving infinitesimals and infinities? Would this be a better starting point? The continuous limit would of course be seen as an extremely useful approximation. The general personal impression of today's theories is...
  25. S

    Struggling with Discrete Math? Here's What to Do

    Rant Warning I am a computer science major and math is a major part of our curriculum. A year ago I took my first ever discrete math course, and it honestly fried my brain. Now I'm in a computer science course that uses discrete math to analyze algorithms, and my brain has simply shutdown...
  26. E

    MATLAB How to Represent Discrete Time Signals in Matlab

    Can anyone tell me how to represent signals in discrete time in Matlab? I had a lab assignment in my Linear Systems and Signals class, which said to plot the result of this: r[-k - 2] \ast u[k -2], where \ast represents convolution. Now, I know the answer, which is 0. I now need to plot...
  27. F

    Propositional logic Discrete Mathematics

    [SOLVED] Propositional logic Discrete Mathematics Homework Statement Assuming atleast one of the following statements is true, which one is it? why? a. Exactly one of these statements is true b. Exactly two of these statements are true c. Exactly three of these statements are true d...
  28. R

    What is the Equation for Calculating Uncertainty in Velocity and Acceleration?

    Homework Statement Hi. I need to prove that these 3 eqns are the same. p \rightarrow q \vee r p \wedge \neg q \rightarrow r p \wedge \neg r \rightarrow q Homework Equations p \rightarrow q \equiv \neg p \wedge q The Attempt at a Solution p \rightarrow q \vee r p...
  29. T

    Discrete Mathematics with possible Quotient Remainder Theorem

    Homework Statement For all integers m, m^{}2=5k, or m^{}2=5k+1, or m^{}2=5k+4 for some integer k. Relevant equations I'm pretty sure we have to use the Quotient Remainder THM, which is: Given any integer n and positive integer d, there exists unique integers q and r such that...
  30. T

    Discrete Mathematics Absolute Value Proof

    Homework Statement Prove the following statement: For all real numbers x and y, |x| times |y| = |xy| Homework Equations I really don't know how to start this as a formal proof. The Attempt at a Solution I was thinking I'd have to break it down into four cases and logically prove...
  31. T

    Discrete Mathematics: Solving for x in a System of Equations

    Homework Statement Suppose a, b, and c are integers and x, y, and z are nonzero real numbers that satisfy the following equations: xy/(x+y)=a xz/(x+z)=b yz/(y+z)=c Is x rational? If so, express it as a ratio of two integers. Homework Equations I substituted a lot of equations...
  32. qspeechc

    Request: Basic Discrete Dynamical Systems Tutorial

    I am so very sorry, but I did not know where to put this thread! I would like to request any helpful links and/or tutorials relating to basic discrete dynamical systems, or any help at all! It should cover: linear one dimension difference equations; non-linear one dimension difference...
  33. R

    Time scaing in discrete time variable?

    I wanted to know , if x(n) has DTFT X(e^jw) then can we define Y(e^jw) in terms of X(e^jw)? where Y(e^jw)is DTFT of y(n)=x(a*n)or y(n)=x(n/a). Because in these cases terms of x(n) are either missed or '0' is padded up, so i think it won't be possible to define Y(e^jw) in terms of X(e^jw)...
  34. B

    Discrete space <-> graph theory

    My complete layman's question. In two of Smolin's books as well as in popular science journals I read that there is the idea of a discrete space, i.e. space would not be completely continuous but rather have "smallest pieces". I wonder if this means that space can be modeled as a graph (the...
  35. P

    Discrete Topology: Definition & Explanation

    Defn: the discrete topology on X is defined by letting the topology consist of all open subsets of X. Why do they use the word discrete in the term discrete topology? Is it because there are subsets such that each subset contain only one point in the space. And these collection of subsets are...
  36. H

    Discrete and continuous problems

    Hi all, There are some dificult problems with discrete argument n that will be very easy if I can change it to continuous argument x. But I do not know what is the condition for that. For example: to calculate the sum of a1+a2 +a3+...an. when n goes to infinity, can I make it as S=integral...
  37. Pythagorean

    Band Pass Filtering / Discrete Fourier Tansform

    So, I'm trying to learn how to do a discrete Fourier transform, with an emphasis on band-pass filtering (for a simple audio wave) Can anyone suggest online resources for this? My boss let me borrow his Bracewell to study the subject but I'm already lost on convolution. I'm still an undergrad...
  38. P

    Make discrete multiplicity function continous?

    Homework Statement In stat physics, the multiplicity function is discrete but to find the max value, you can assume it is continuous around the max region hence use calculus. Why is it legimate to do that? That is approximate a discrete function as continous? The Attempt at a Solution Is...
  39. B

    What are the parametric equations of a line perpendicular to two given lines?

    Homework Statement find the parametric equations of the line through A(-3,2,5) and is perpendicular to both line 1 and line 1 where line 1: (x-4)/3=y-2=(z-3)/-2 line 2: (x,y,z)=(-1,1,5)+k(-1-2,3) 2. The attempt at a solution i think i need to find the normal for the line 1 and...
  40. mattmns

    Number Theory - Discrete Log (Index) - Equation

    Here is a silly question from our book, that seems to be a pain to solve: ------------ Solve the following equation: 59^x \equiv 63 \ \text{mod 71} ------------ The idea is to use the discrete log (or index). Note that 7 is a primitive root mod 71. The two books I have looked at...
  41. V

    DISCRETE MATH: Binomial Theorem proof (using Corollary 2)

    Homework Statement Show that if n is a positive integer, then 1\,=\,\binom{n}{0}\,<\,\binom{n}{1}\,<\,\cdots\,<\,\binom{n}{\lfloor\frac{n}{2}\rfloor}\,=\,\binom{n}{\lceil\frac{n}{2}\rceil}\,>\,\cdots\,>\binom{n}{n\,-\,1}\,>\,\,\binom{n}{n}\,=\,1 Homework Equations I think this proof involves...
  42. K

    Can a Sequence of Consecutive Positive Integers Not Contain Any Primes?

    Could someone help me with this induction proof. I know its true. given any integer m is greater than or equal to 2, is it possible to find a sequence of m-1 consecutive positive integers none of which is prime? explain any help is greatly appreciated thanks
  43. M

    Text on Discrete Fourier Analysis & FFT

    Does anyone know of any good texts that cover Discrete Fourier Analysis and the Fast Fourier Transform? *I don't know if this belongs here in the HW help or in General Math section.
  44. mattmns

    When is a Discrete Metric Space Compact?

    Here is the exercise: ---------- Let (X,d_{disc}) be a metric space with the discrete metric. (a) Show that X is always complete (b) When is X compact, and when is X not compact? Prove your claim. --------- Now (a) is pretty simple, but for (b) I am still not sure. Here is our definition of...
  45. V

    Prove That At Least 1 Integer Divides Another w/ Discrete Math

    Homework Statement Use mathematical induction to show that given a set of n\,+\,1 positive integers, none exceeding 2\,n, there is at least one integer in this set that divides another integer in the set. Homework Equations Mathematical induction, others, I am not sure The...
  46. V

    Mathematica Prove: Sets Union & Intersection Hypothesis

    DISCRETE MATH: Prove a "simple" hypothesis involving sets. Use mathematical induction Homework Statement Prove that if A_1,\,A_2,\,\dots,\,A_n and B are sets, then...
  47. S

    Which to Choose: Discrete Maths or Statistics for Chemistry/Physics Majors?

    Hi all, I was just wondering which would be the more beneficial first year uni subject to take given that I would like to major in either chemistry or physics - Discrete Mathematics or Statistics. The Discrete maths course "focuses on the enumeration of the Catalan Numbers" and is an...
  48. B

    Calculating Probability of Even Numbers with Loaded Die

    Homework Statement A die is loaded so that the numbers 2 through 6 are equally likely to appear but that 1 is 3 times as likely as any other number to appear. What is the probability of getting an even number?Homework Equations This is where I become lost - I'm not sure how to get the...
  49. C

    Discrete Math Help (sad story)

    Homework Statement 1. Let x and y be positive integers and assume that xy is odd. Prove the following statement using the method of proof by contradiction: Both x and y are odd. 2. Let A, B and C be the following sets: A = (x є N | x< 25) B=(x e N | x = 2m for some positive...
  50. M

    Discrete Math Help: Rewrite Statement with Logical Equivalences

    Homework Statement Use the logical equivalences p \rightarrow q \equiv \sim p \vee q and p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) to rewrite the statement form: (p \rightarrow (q \rightarrow r)) \leftrightarrow ((p \wedge q) \rightarrow r) Homework Equations...
Back
Top