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.
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...
Homework Statement
http://puu.sh/1OfE2 Homework Equations
The Attempt at a Solution
I am not really sure about this one! :(
I think it's 1 because
http://puu.sh/1OfY0
http://puu.sh/1OfYE
I came up the number by working backwards (assuming the conclusion is true). However, for a proof, I...
I am new to manifolds and I read the fact that any discrete space is a 0 dimensional manifold. I am having a hard time understanding why and feel this is very basic.
So to be a manifold, each point in the space should have a neighborhood about it that is homeomorphic to R^n. (and n will...
Hi,
I'm trying to simulate a discrete time time markov chain in matlab. Unfortunately I am neither a markov chain expert or a good MATLAB coder.
My problem is simple, I have a transition probability matrix with 100 states (100x100) and I want to simulate a 1000 steps beginning from state 1...
Why does a discrete Fourier transform seems to produce two peaks for a single sine wave? It seems to be the case that the spectrum ends halfway through the transform and then reappears as a mirror image; why is that? And what is the use of this mirror image? If I want to recover the frequency...
Classify the following as discrete or continuous random variables.
(A) The number of people in India
(B) The time it takes to overhaul an engine
(C) The blood pressures of patients admitted to a hospital in one day
(D) The length of a centipede
Homework Statement
is there a continuous real valued variable X with mgf: (1/2)(1+e^t)
Homework Equations
The Attempt at a Solution
I've noticed that this is the mgf of a bernoulli distribution with p =1/2. But since bernoulli is a discrete distribution, does that disprove that...
I've been trying to figure out why it's standard to use complex discrete Fourier transforms instead of just the real version. It's discussed a bit here.
http://dsp.stackexchange.com/questions/1406/real-discrete-fourier-transform
As far as I can tell there's a hypothetical efficiency...
I'm having difficulties trying to establish the best approach to create a mathematical model of a process that has a combined continuous and discrete (batch) element to it. I explain as follows:
The system is a hopper (vessel), open to atmosphere, with dry granular material being fed in by...
Hi,
If X \LARGE is a metric space and E \subset X is a discrete set then is E \LARGE open or closed or both?
Here's my understanding:
E \LARGE is closed relative to X \LARGE.
proof: If p \subset E then by definition p \LARGE is an isolated point of E \LARGE, which implies that p...
Hello,
You can use a Q-Q plot to visually test if 2 continuous variables are from the same distribution and you get a straight line.
Is there a way to visually test if 2 discrete variables are from the same distribution? Also is there a way to test it mathematically?
Thanks
Homework Statement
Let \theta \in [0,1] and n \in \mathbb{Z} . Let n\theta mod(1) denote n\theta minus the integer part. Show n \theta mod(1) is a discrete subset of [0,1] if and only if theta is rational.The Attempt at a Solution
I'm having a bit of trouble with the "only if" part...
Here is the question:
Consider the experiment of rolling two tetrahedra that are unfair in the sense that each has the following probabilities for each of the four faces:
P{1 dot}=1/10
P{2 dots}=2/10
P{3 dots}=3/10
P{4 dots}=4/10
Let X be the total of the outcomes in the two...
Say you have some function that is periodic in a parameter k. The discrete Fourier transform from a sampling may be found in the usual way, giving the frequency spectrum in k. But what if I want to find the frequency spectrum in 1/k ?
I'm not really sure what this is called, and so I've had a...
I have a grid and on each point on the grid I have discrete velocity data. I however don't have anyalytical function. I need to integrate the points and check where in space they will be after some time. I know it very easy to do it with runge-kutta if i have the analytical function for velocity...
Hi!
I have an argument and I have to prove the validity of all possible ways.
I have proved by logical implication, tautology, contradiction and contrapositive, but the problem is reduced to prove the hypothesis by logical equivalences and implications.
The reasoning is as follows...
Hi,
I have 3 correlated variables that I wish to model with a copula function. 2 of the variables are continuous and 1 is discrete.
My question is, generally speaking can you model continuous and discrete variables within the same copula? Yes/No?
Thanks
Hello all !
Homework Statement
I have the following problem.
I have to calculate the DTFT of this : x(n)=u(n)-u(n-4).
Homework Equations
Fourier Transformations
The Attempt at a Solution
So far , from what I have studied I have understood, that a DTFT , is actually many...
Hi,
So I am trying to show the following:
##(A \cup B)\sqcup(A \cap B) \leftrightarrow A \sqcup B##
The proof that I am trying to understand starts with:
##A \leftrightarrow (A \backslash B) \sqcup (A\cup B) \qquad (1)##,
and
##A \cup B \leftrightarrow (A\backslash B)\sqcup B \qquad...
Homework Statement
I'm having trouble understanding PMF. We are given a number, say, 927189234.
We need to calculate the PMF of (0, 1, ..., 9) in this distribution.
Homework Equations
The Attempt at a Solution
Calculating the probabilities is easy,
P(9) = 2/9
P(8) = 1/9...
Homework Statement
Find the Impulse response of this system
3y[n]+4y[n-1]+y[n-2] = x[n] + x[n-1]
Homework Equations
Eigenvalues = -1/3 and -1
hc[n] = k1[-1/3]n+k2[-1]n
3h[n] +4h[n-1] +h[n-2] = δ[n] + δ[n+1]
The Attempt at a Solution
I know that normally we would plug in hc[n] for two...
Hello,
This semester I am taking my first discrete math course. I am thoroughly enjoying the material, but am dreading the professor and textbook. The consensus amongst my classmates is that the professor is excessively convoluted in his conveyance of the material, and that the textbook does...
Homework Statement
I attached the problem as a file.
Homework Equations
The Attempt at a Solution
I get stuck on how to properly represent the summation. How does k find it's way as one of the sub-scripts?
Homework Statement
I attached the problem as a fileHomework Equations
The Attempt at a Solution
The way I tried to solve this was to write out a few multiplications and find a pattern. I got the right answer, but I was wondering if there was more of a precise way of doing it; or would the...
Homework Statement
I attached the problem as file.
Homework Equations
The Attempt at a Solution
I honestly do not know how to solve this problem. I have a test tomorrow, and this is really the only question that I am having difficulty with. I don't really know what mod means...
Discrete Math: prove B intersection A = A, given A-B = null set
1. Problem Statement:
Prove B \cap A = A, given A-B = ∅ (empty set)
The Attempt at a Solution
xε(B\capA) => xεB and xεA => Logic given A-B = ∅ => xεA
I tried using A-B = A\cap!B for xε(A\cap!B)=∅ => xεA and x not in !B or...
Below I've listed the chapters from a Precalculus book as well as the author recommended Computer Science chapters from a Discrete Mathematics book.
Although these chapters are from two specific books on these subjects I believe the topics are generally the same between any Precalc or...
Homework Statement
Prove the complementation law in Table 1 by showing
that \stackrel{=}{A} = A
Homework Equations
The Attempt at a Solution
Well, first I assumed that x is an element of A, so that A = (x | x\in A)
by taking the complement, I got (x | \neg(x\in A)...
Hi everyone,
I've got a test tomorrow and while working through a practice test I got stuck. Here is the problem:
In the question below suppose P(x,y) is a predicate and the universe for the variables x and y is {1,2,3}. Suppose P(1,3), P(2,1), P(2,2), P(2,3), P(2,3), P(3,1), P(3,2) are...
Homework Statement
Find a compound proposition logically equivalent to p → q using only the logical operator ↓.
Homework Equations
The Attempt at a Solution
My book does not go into much detail about solving this problem other than providing the answer. I really want to know how to get the...
Feynman checkerboard as a model of discrete space-time
Back in 2006 Ed Hanna posted an interesting thread about this topic and I would really like to discuss it with him.
Are you out there Ed - or does anyone know how to contact him?
Thanks,
John Wellings
Homework Statement
A player of a video game is confronted with a series of opponents and has an 80% probability of defeating each one. Success with any opponent is independent of previous encounters. The player continues to contest opponents until defeated.
What is the probability...
Let A, B, and C be sets. Show that
a) (A-B) - C \subseteq A - C
b) (B-A) \cup (C-A) = (B \cup C) - A
I am using variable x to represent an element.
Part A)
I rewrote (A-B) - C as (x\inA ^ x\notinB) - C
I think this could be rewritten as
(x\inA ^ x\notinB) ^ x\notin C
A-C can...
The question is, "Find the dual of each of these compound propositions."
The propositions being: p∧¬q∧¬r, (p∧q∧r)∨s, and (p∨F)∧(q∨T)
I don't quite understand what they want me to do.
Hi all, I have a seemingly simple problem which is I'd like to efficiently evaluate the following sums:
Y_k = \sum_{j=0}^{n-1} c_j e^{\frac{i j k \alpha}{n}}
for k=0...n-1. Now if \alpha = 2\pi, then this reduces to a standard DFT and I can use a standard FFT library to compute the...
Do you think that matter, energy, space, time, etc. are discrete, or continuous?
If they are discrete, is continuous mathematics limited to a very, very good approximation for modeling physical phenomena?
Hi everybody !
I have a question about discrete integrals with contours. I want to integrate
the points that makes the contour of an image. When the contour is only one
curve it is easy I get the function in every point of the contour and I multiply
by the distance between two consecutive...
I'm planning on taking a computer science course this fall on Theory of Computation. However, one of the prereqs is "experience in formal mathematics at the level of [course on Discrete Mathematics]." I've done a little bit of discrete math before (The Art of Problem Solving covers some discrete...
Homework Statement
Hello.
Here is the question:
Determine whether or not R is some sort of order relation on the given set X.
X = {∅, {∅}, {{∅}} } and R ε ⊆.
I can't seem to figure out why the ordered pairs given are what they are.
Homework Equations
None.
The Attempt at...
is this true or false:
If a|b and a|c, then one (or both) of b|c or c|b holds.
if I want to disprove this, can I:
let a = 5, x = 2 and y = 3.
b=ax
c=ay
then c=bz
and c = bg doesn't hold.
I never used descrete math terms in english before, so I hope it sounds clear enough:
Formalize the following:
1) Between every two different real numbers there is a rational number
2) There exist real numbers x and y, such that x is smaller than y, yet x^2 is bigger than y^2
Now the solution...
Surely sets with the same cardinality are homeomorphic if we assign both of them the discrete topology. What's preventing us from doing that?
For example, (0,1) and (2,3) \cup (4,5) have the same cardinality. With the natural subspace topology they are not homeomorphic - as one is connected...
Homework Statement
For any given n, where n is an element of the natural number set, prove n^2 > n +1, for all n > 1.
Homework Equations
This week in lecture we defined the greater than relationship as:
Let S = Natural numbers
Let R = {(a,b): \exists c: a = b+c}
then aRb
The...
Couldn't decide where to post... Chemistry or quantum mechanics... But posted here cause I wanted to know a physicist's view...
We know that the electrons in the atom have discrete energy,I mean not just any energy... An electron can't have the energy between 2s and 2p orbitals... But after...
Homework Statement
c) Is 'g' a surjective function (onto) ? Justify your answer.
Homework Equations
Let 'f' be a relation on ℤ (the set of integers) , defined by the entrance requirement :
(x;y) ∊ ƒ iff y = x + 15
and let 'g' be the function on ℤ defined by the...
I apologize for the repost, but I had no replies to my previous post. I figured that I didn't put down a good enough attempt of a solution. I will try to explain what I did in more detail. I have read the rules for the forum, but if I'm still doing something wrong, please tell me. I want to...
Homework Statement
Determine the dom(g)
Homework Equations
Let 'f' be a relation on ℤ (the set of integers) , defined by the entrance requirement :
(x;y) ∊ ƒ iff y = x + 15
and let 'g' be the function on ℤ defined by the entrance requirement :
(x;y)...
Homework Statement
Question 1 :
a) Use Venn diagrams to determine whether or not, for all subnets A,B and C of a universal set U, (A-B) ∪ C = (A∪C) - (A∩B)
b) If the statement appears to hold, give a proof, if not, give a counter example.
Homework Equations
(A-B) ∪...
Question 2:
--------------------
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
A+D is the set : (Choose only one )
1. {1, 3}...
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 ...