What is Discrete: Definition and 895 Discussions

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

    MHB Exploring Random Graphs: Probability Model and Connected Components Analysis"

    Having a hard time with this problem. Can anyone guide me in the correct direction? Random graphs are a fascinating subject of applied and theoretical research. These can be generated with a fixed vertex set V and edges added to the edge set E based on some probability model, such as a coin...
  2. J

    MHB Truth Table in Discrete Mathematics

    Use a truth table to determine that "division into cases" rule of inference is valid.
  3. J

    MHB Discrete Mathematics Binary Search

    How many comparisons are performed to find 13 in the following list by using Binary Search? 7, 12, 5, 22, 13, 32 Is it true that there are 10 comparisons performed to find 13 in the following list by using Binary Search? If this isn't right, then can somebody please help explain this to me?
  4. J

    MHB Discrete Mathematics Vcomparisons

    How many vcomparisons did you actually need?
  5. T

    Discrete time system that is homogenous but not additive

    I have just started working with discrete time signals, more specifically various system properties. I am wondering if their is a discrete time system that is homogeneous but not additive? This is basically testing the linearity of a signal with the additive and homogeneous criteria.
  6. L

    Question about the rule of the Lazy Statistician - If Y is discrete, w

    Link to theorem: http://en.wikipedia.org/wiki/Law_of_the_unconscious_statistician Suppose Y is a discrete random variable related to X, a continuous random variable by some function r (so Y = r(X) ). Let A be the following set: A_y = {x ∈ R ; r(x) = y}. Since Y is discrete, f_Y (y) = P(Y = y)...
  7. Mandelbroth

    Plausibility of a Discrete Point Manifold

    Consider a discrete set of ##k## points. First, is it a manifold? I know that a manifold is a topological space that contains a neighborhood homeomorphic to Euclidean space for each point. Can we just consider each point's neighborhood to be a set containing only that point? Second, would the...
  8. Z

    Interpolating Data with the Discrete Fourier Transform

    Hello everyone: I have some question using the FFT in MATLAB for data interpolating. I don't know what the relation between the normal Fourier series and the real, image number. For example, given a set of measurement data, I can use the curve fitting toolbox to fit a curve. The general...
  9. marellasunny

    Testing for chaos in data(method by Doyne Farmer for 3D discrete data)

    Testing for chaos in data I have data for 3 variables ,each with respect to the discrete time values. How do I check for the existence of chaos for this discrete 3D system?(I don't have the analytic eqs.,just the data.) MY IDEAS ON CHECKING FOR CHAOS FROM DATA:(which of these are feasible...
  10. B

    Circulant linear systems and the Discrete Fourier Transform

    Homework Statement Hi, this is not a homework question per se, but something I'm wondering. Let C be a circulant n x n matrix, let x, b, be vectors such that C x = b. We would like to find a solution x. One way is to use the DFT: According to section 5, In Linear Equations, in the wikipedia...
  11. U

    Explanation of the discrete fourier transform

    Hi all, I'm a complete novice when it comes to describing images in frequency space and i understand that it is a way of representing images as being composed of a series of sinusoids. So a horizontal striped pattern with a single spatial frequency would have a magnitude image in frequency...
  12. L

    Two dimensional discrete Fourier transform units

    Homework Statement I have am doing a two dimensional discrete Fourier transform on an image (using MATLAB). What are the units associated with each pixel of the image in the frequency domain? Homework Equations The Attempt at a Solution I thought that the frequency should be...
  13. mishima

    Building comparator from discrete components?

    Hi, I'm interested in building a breadboard version of the simplest comparator using transistors and resistors. Ultimately I'd like to understand the LM393 but looking at the datasheet schematic, it seems quite complicated. I was hoping there was a simpler comparator I could mimic to start out...
  14. W

    What is Discrete Math (in layman's terms)?

    Wikipedia says it deals with distinct objects and is differentiated from continuous math, which has objects that "vary smoothly." For a layman, can someone explain what this means? And is all math discrete or continuous? No other options?
  15. P

    Statistics expectation of discrete variable.

    Hi, Homework Statement How may I find to what number Ʃ(m=1 to ∞) m/2m-1 converges? Further, suppose I know it converges to 4, why would then E(Y), given that P(Y) = 1/2m-1, be equal to 2 (thus asserted the answer) and not 4? Homework Equations The Attempt at a Solution I am...
  16. X

    How to reconstruct a signal using the Discrete Haar Wavelet transform?

    Homework Statement Hi, for a project for school, I need to implement the Discrete Haar Wavelet Transform to compress an audio signal. This would be fine and dandy, but I do not really understand how to use the the DHWT. Could anyone direct me towards some resources that would be very helpful...
  17. G

    Statistics - Discrete Markov Chains

    Homework Statement Homework Equations The Attempt at a Solution I'm not really sure if this belongs here or in the precalculus mathematics section. I had to take calculus before taking this class so I'm putting it here. I'm confused about part (b). I don't really...
  18. B

    Discrete Math Question Involving Congruence Modulus

    Solve for x: 4x=6(mod 5) Here is my solution: From the definition of modulus, we can write the above as \frac{4x−6}{5}=k, where k is the remainder resulting from 4x~mod~5=6~mod~5=k. Solving for x, x=\frac{5k+6}{4}⟹x(k)=\frac{5k+6}{4} Now, my teacher said that is incorrect, and that...
  19. T

    How Many Onto Functions and Symmetric Relations Exist in Given Sets?

    For the first question it deals with onto functions I was able to do a-e which deals with actal numbers. Then questions E stumped me. I have no idea what to do or even how to start. It reads: Let C (n,m) be the number of onto functions from a set of m elements to a set of n elements, where m >...
  20. J

    Discrete time spectrum, finding possible continuous-time signals.

    The discrete-time spectrum of a sampled continuous-time signal x(t) is shown in the figure above, where (A = 9.8exp(-j0.06π), B = 0.51π, C = -0.27π, and D = 1.9exp(-j0.41π) ). If the sampling frequency is 4928, which of the following continous-time signals is a possible solution for x(t)...
  21. M

    Discrete Time Fourier Transform

    Find the DTFT of: h[n]=(-1)^{n}\frac{sin(\frac{\pi}{2}n}{sin(\pi n} useful properties: x[n]y[n] --> X[Ω]*Y[Ω] \frac{sin(\frac{\pi}{2}n}{sin(\pi n} --> rect[\frac{2Ω}{\pi} I have no clue how to deal with the (-1)[itex]^{n}[\itex] the DTFT of that doesn't converge. . . any help...
  22. S

    MHB GCD Discrete Math: Proving GCD(a,b)=1

    Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+ a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2 Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b...
  23. S

    Advice on Linear Algebra and Discrete Math.

    Hello guys, I will be taking Linear Algebra (Intro.) and Discrete Math in the Fall. I heard that these two courses are different from the Calculus sequence. I am afraid since I am not good with proofs. Will I be able to do well as long as I put in the time? Can you guys give me an advice so I...
  24. M

    Comparing discrete data to a continuous model (1D)

    Say I have a model, y = f(x), and ten discrete data points to compare to this model, (x1, y1)...(x10,y10). The normal way would then be to take the residuals and square them to get a quality of fit, ie. average residuals squared = {[f(x1) - y1]^2 + ... + [f(x10) - y10]^2}/10 I also remember...
  25. R

    Discrete distribution taking only non-negative integer values

    I can't seem to wrap my head around the types of sums used in probability theory, and here is a classic example. Section 6.1 of this article: http://en.wikipedia.org/wiki/Expected_value#Discrete_distribution_taking_only_non-negative_integer_values The first line of the proof, what is going...
  26. B

    Is space-time discrete or continuum?

    Is there a way to know one way or another? If smallest possible scale is Planck scale, does it mean that space-time is discrete where smallest possible step is Planck's length (PL) and smallest possible time is Planck's time (PT)? If I move my hand from point A to point B, say 1m exactly in...
  27. K

    Discrete Fourier Transform question

    Hi, I am learning Fourier transformation by my own. I am reading a book "Fourier Transformation" by R. Bracewell. In chapter 11, in examples of discrete Fourier transforms, it gives for N =2, {1 0} transforms to 1/2{1 1}. I can do this in MATLAB but I can't figure it out how to do it by hand...
  28. M

    Discrete Time Convolution of Sums

    Evaluate the following discrete-time convolution: y[n] = cos(\frac{1}{2}\pin)*2^{n}u[-n+2] Here is my sloppy attempt: y[n] = \sumcos(\frac{1}{2}\pik)2^{n-k}u[-n-k+2] from k = -∞ to ∞ = \sumcos(\frac{1}{2}\pik)2^{n-k} from k = -∞ to 2 We can re-write the cos as...
  29. iVenky

    Capacity of a discrete channel

    Well I was reading this " A Mathematical Theory of Communication" paper by Claude Shannon. He says that the capacity of a discrete channel is given by [ tex ] C= \ \lim_{T \to +\infty} \ \frac{\log ( N(T) )} {T} [ \tex ] Here N(T) is the number of possible sequences in a duration of T...
  30. B

    Computer Science Discrete Mathematics Proof problem

    Hey guys, I'm taking Discrete Mathematics and am having a bit of trouble with one of my proofs. If any of you has any experience with that and could tell me where I'm going wrong, I'd appreciate it! Ok, here it is: Prove each statement in 8–23 by mathematical induction: 27. A...
  31. ShayanJ

    Discrete or continuous spectrum?

    Consider an unbounded self-adjoint operator defined in a hilbert space(its domain isn't the entire hilbert space,of course).Can its spectrum have discrete and continuous parts simultaneity?Does it have eigenvectors with finite norm? Thanks
  32. B

    Calculating vertical velocity from discrete horizontal velocities

    Hello, I'm working with a 2 x 3D arrays of fluid velocity values (east-west -> u and north-south -> v) and would like to properly calculate vertical velocities (w) from them (n.b. this is not homework). This ultimately needs to go into a processing algorithm, so while symbolic math is...
  33. B

    Discrete Convolutions, How to?

    How would you go about convolving two discrete distributions that look something like this: Number: 0, 1, 2 Probability: 0.1, 0.3, 0.6 Number: 0, 1, 2, 3, 4 Probability: 0.1, 0.3, 0.2, 0.1, 0.3
  34. G

    Discrete topology and discrete subspaces

    Homework Statement If A is a subspace of X and A has discrete topology does X have discrete topolgy?Also if X has discrete topology then does it imply that A must have discrete topology? The Attempt at a Solution My understanding of discrete topology suggests to me that if A is discrete it...
  35. tsuwal

    Solve Schrodinger equation for an eletron in a box. Why discrete?

    Homework Statement An eletron is moving along one axis between x=0 and x=L. It's mass is given by m. We want to know the energy and wave function of its possible states given by the quantic number n. Show that the solution to the above equation is En=n^2*h^2/(8*m*L^2)...
  36. M

    Discrete probability distributions

    Homework Statement A certain manufacture advertises batteries that will run under a 75 amp discharge test for an average of 100 minutes, with standard deviation of 5 minutes. a. find an interval that must contain at least 90% of the performance periods fr batteries of this type. b...
  37. R

    Are discrete transistors dead?

    ...outside integrated circuits? Can OpAmp's replace them?
  38. H

    Discrete math:Placing beads on a necklace

    Homework Statement There are 8 beads: 4 black, 3 white, and 1 red. How many ways can these be arranged on necklace? Homework Equations Just combinations nCm = (n-m)!/(m!). The Attempt at a Solution 8C4 = 70, 4C3 = 24, and 1C1 = 1, so the total number of combinations is 95? Or...
  39. B

    Quantify difference between discrete distributions

    Hello, I am trying to quantify the difference between two discrete distributions. I have been reading online and there seems to be a few different ways such as a Kolmogorov-Smirnov test and a chi squared test. My first question is which of these is the correct method for comparing the...
  40. G

    Discrete Optimization Question

    Homework Statement 9. This is a simplified inventory problem.Suppose that it costs c dollars to stock an item and that the item sells for s dollars. Suppose that the number of items that will be asked for by customers is a random variable with the frequency function p(k). Find a rule for...
  41. F

    Question regarding modular arithmetic from discrete math

    Homework Statement Homework Equations a. I know that x*a mod y should be the same as y*b mod x but I don't understand why b. I know that an inverse can be constructed because x and y are mutually prime and gcd(x,y) = 1 , but I have no clue at what pair x and m is possible c. I have no idea...
  42. M

    Discrete Fourier Transform and Hand-waving

    Hi all, I'm reading the following PDF about the DFT: http://www.analog.com/static/imported-files/tech_docs/dsp_book_Ch8.pdf Please see pages 152-153. So the inverse DFT (frequency to space, x[i] = ...) is given on page 152. Then it is claimed that the amplitudes for the space-domain...
  43. H

    Sketching discrete time signal

    Discrete signal x[n] is shown in the first picture. Sketch x[2n] Answer Can anyone ecplain why x[2n] is like that. I can understand how to plot it if i have a continuous time signal
  44. P

    Discrete Math. (Logically equivalent)

    See attachment for the question. ---------------- ∀x ∈ D, if P(x) then Q(x). this means ∀x P(x) -> Q(x). all you have to do is find a value for x ∀x this means for ALL x right so you can choose ANY element but for the E its only things in the domain so all you have to do is choose an x...
  45. ArcanaNoir

    Hausdorff topology on five-element set that is not the discrete top.

    Homework Statement The textbook exercise asks for a Hausdorff topology on \{a,b,c,d,e\} which is not the discrete topology (the power set). It is from "Introduction to Topology, Pure and Applied", by Adams and Franzosa. Homework Equations Let X be a set. Definition of topology...
  46. anemone

    MHB Problem involving discrete product

    Hi members of the forum, Please consider the following: Given $\displaystyle a_{n}=\frac{n^2+1}{\sqrt{n^2+4}}$ where $\displaystyle n\in\mathbb{N}$ and $\displaystyle b_n=\prod_{k=1}^n(a_k)$ prove that $\displaystyle \frac{b_{n}}{\sqrt{2}}=\frac{\sqrt{n^2+1}}{\sqrt{n^2+2n+2}}$. Therefore...
  47. A

    Cdf of a discrete random variable and convergence of distributions

    In the page that I attached, it says "...while at the continuity points x of F_x (i.e., x \not= 0), lim F_{X_n}(x) = F_X(x)." But we know that the graph of F_X(x) is a straight line y=0, with only x=0 at y=1, right? But then all the points to the right of zero should not be equal to the limit of...
  48. M

    Discrete Fourier Transform on even function

    The DCT of an even function is comprised of just cosine coefficients, correct? I'm playing around in MATLAB and I came up with a simple even function 1.0000 0.7500 0.5000 0.2500 0 0.2500 0.5000 0.7500 1.0000 0.7500 0.5000 0.2500 0 0 0 0...
  49. perplexabot

    Discrete convolution evalutation.

    Hello all. I have a homework question but since I have no idea how to go about solving it I have started with an exercise problem from the book (with the solution and vague steps provided). Here is my attempt of the exersize question. Homework Statement Compute the convolution y[n] = x[n]...
  50. L

    Problem with discrete and continuous random variables

    Homework Statement A binary information source produces 0 and 1 with equal probability. The output of the source, denoted as X, is transmitted via an additive white Gaussian noise (AWGN) channel. The output of the channel, denoted as Y, satisfies Y = X + N, where the random noise N has the...
Back
Top