What is Discrete mathematics: Definition and 106 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.
I have a doubt about the notation and alternative ways to represent the terms involved in sums.
Suppose that we have the following multivariable function,
$$f(x,y)=\sum^{m}_{j=0}y^{j}\sum^{j-m}_{i=0}x^{i+j}$$.
Now, let ##\psi_{j}(x)=\sum^{j-m}_{i=0}x^{i+j}##. In the light of the foregoing, is...
I submitted this solution, and it was marked incorrect. Could I get some feedback on where I went wrong?
Let S represent the event that Party A wins the senate and H represent the event that Party A wins the house.
There are 4 cases: winning the senate and house (##S \cap H##), winning just...
What was the first textbook for the modern syllabus of precaclulus which had "precalculus" in the title or subtitle?
What was the first textbook for the modern syllabus of discrete mathematics which had "discrete," "discrete mathematics" in the title or subtitle?
If you have personal...
I think it is "True" because the hypothesis is true and the conclusion is False.
:cry::cry:But in the answer sheet, the answer is " This is False. The hypothesis is true, but the conclusion is false:## -1^2=-1## , not1."
Problem: Find the cardinality of the set ## A = \{f \in \Bbb N \to \Bbb N. \forall n\leq m .f(n) \geq f (m) \} ##.
I know that ## A \subseteq P(\Bbb N \times \Bbb N) ## implies ## |A| \leq |P(\Bbb N \times \Bbb N)| = | P(\Bbb N) | = \aleph ##. So I have a feeling that ## \aleph \leq |A| ##...
I hope someone can help me or point me in the right direction.
I am reading Discrete Mathematics with its Applications by Rosen. I am trying to self learn discrete math. I am actually able to do most questions but I have a question about a solution (not the question itself.)
The question is...
how to find upper bound height and lower bound height of 3-ary ordered tree that have leaves of 101? ( the tree don't have to be complete tree, but have to be have 3 children)
$$m^h \ge 101=3^h \ge 101$$
$$log \, m^h \ge 101=3^h \ge 101$$
$$h \ge 5$$
but how to know upper bound and lower...
N and k are positive integers satisfying $$ 1<=k < n$$
An undirected graph $$G_{n,k}= (V_{n,k} ,E_{n,k})$$ is defined as follows.
$$V_{n,k}={1,2,3,...n}$$
$$E_{n,k}={\{\{u,v\}|u-v \equiv k \, (mod \, n) \, or \, u-v \equiv -k \, mod \, n}$$
However, $$x \equiv y \, (mod \, n) $$ indicates...
I am finding it difficult to motivate students on why they should how to prove mathematical results. They learn them just to pass examinations but show no real interest or enthusiasm for this.
How can I inspire them to love essential kind of mathematics? They love doing mathematical techniques...
First, I don't know if this is the right place so if not, please direct me. Thank you.
As for the question, I am in a discrete mathematics class online. The instructor is practically non-existent when asking for help simply saying to "refer to the book for clarification". I have scoured google...
Homework Statement
a) I have to find and expression for sequence of $b_n$ in terms of generating functions of the sequence of $a_n$
$$b_n = (-1)^{n}(n+1)a_0 +(-1)^{n-1}n a_1+...+(-1)2a_{n-1}+a_n$$ with $$a_n = a_{n-1} +8a_{n-2} -12a_{n-3} +25(-3)^{n-2} + 32n^2 -64$$
b) I have to use the...
Homework Statement
The question is counting how many sequence length 10 with 1,2,3 if
a) increasing from left to right with repetition allowed
b) increase from left to right with each number appear at least once (still with repetition allowed)
Homework Equations
It is the stars and bars...
Homework Statement
Find the probability that a hand of five cards in poker contains four cards of one kind.
Homework EquationsThe Attempt at a Solution
Solution given in the book:[/B]
By the product rule, the number of hands of five cards with four cards of one kind is the product of the...
1. Suppose P(x) and Q(x) are propositional functions and D is their domain.
Let A = {x ∈ D: P(x) is true}, B = {x ∈ D: Q(x) is true}
(a) Give an example for a domain D and functions P(x) and Q(x) such that A∩B = {}
(b) Give an example for a domain D and functions P(x) and Q(x) such that A ⊆ B...
I am currently taking a course in discrete mathematics. The literature used is "Discrete Mathematics And Its Applications by Kenneth H. Rosen" 6th ed., or 7th ed. I have encountered most of the topics from that book. I.e. Logic, naive set theory, &c. What I have encountered also is the...
Homework Statement
1. Why is the statement: " Vicky is not clever" Not a mathematical proposition? Provide examples please
2. Why is the statement: "a^2+b^2=c^2 an indeterminate proposition?"
3. Why is the negation of " If a triangle has two equal angles it is isosceles" = "Not all triangles...
Theorem: Let ##A_1, A_2, ..., A_k## be finite, disjunct sets. Then ##|A_1 \cup A_2 \cup \dots \cup A_k| = |A_1| + |A_2| + \dots + |A_k|##
I will give the proof my book provides, I don't understand several parts of it.
Proof:
We have bijections ##f_i: [n_i] \rightarrow A_i## for ##i \in [k]##...
Homework Statement
Determine whether the following is valid:
p \rightarrow \neg q , r \rightarrow q , r, \vdash \neg p
Homework Equations
Modus Ponens, disjunctive syllogism, double negation.
The Attempt at a Solution
I've boiled it down to
p \rightarrow \neg q , q, \vdash \neg p...
Hi
All applications of discrete mathematics I know of seem to be in computer science. I want to know if there is somewhere discrete mathematics are applied outside of software.
What can I work as if I like discrete mathematics but do not want to program? (outside of academia, of course)
Homework Statement , relevant equations, and the attempt at a solution are all in the attached file.
I was reading through Invitation to Discrete Mathematics and attempted to solve an exercise that involved a proof. I've typeset everything in LaTeX and made a PDF out of it so that it does not...
There is a table tennis tournament consisted of 8 participants that is guided by the following rules:
1. Each player plays with every other player for exactly one party
2. If in the i-round there was a party between A and B and a party between C and D, and A and C play In i+1, then in i+1...
Homework Statement
http://puu.sh/nYQqE/2b0eaf2720.png
Homework Equations
http://puu.sh/nYSjQ/e48cad3a8b.png
The Attempt at a Solution
http://puu.sh/nYYjW/174ad8267c.png
My main issue is with part b) and part d). I think that part b) is mostly right, but part d) is definitely wrong and...
The problem statement:
How many five-letter strings of capital letters have a letter repeated twice in a row? For example, include ABCCA and AAABC and ABBCC but not ABCAD.
The attempt at a solution:
First, let's break down how we would perform the selection of a string that meets the...
Homework Statement
My task is to find out what is the lowest # of elements a poset can have with the following characteristics. If such a set exists I should show it and if it doesn't I must prove it.
1) has infimum of all its subsets, but there is a subset with no supremum
2) has two maximal...
Hi all,
Due to a scheduling conflict at my university I can't take Discrete Math, and it's a pre-requisite for all of the math courses I want to take next year. Any recommendations on which textbooks I ought to use to independently study the subject?
Thanks!
Are fundamental randomness and fundamental determinism inconsistent? Two such different mechanisms would imply a kind of dualism. (Does even the defeatist retreat into Many Worlds avoid this problem - if it is a problem.)
Homework Statement
Hey guys I am having a bit of a difficult time with this question, if some one could help me out it would be appreciated, thanks.
Consider the following argument. "If the weather is fine, and the train is early, then the dog will sit on the tuckerbox. The train will be...
Homework Statement
Let A = {1, 2, 3, 4} and let F be the set of all functions from A to A. Let R be the relation on F defined by:
For all functions f, g that are elements of F, (f, g) are only elements of R if and only if f(i) = g(i) for some i that is an element of A.
Let the functions α, β...
Homework Statement
I need to (computationally) solve the following linear elliptic problem for the function u(x,y):
\Delta u(x,y) = u_{x,x} + u_{y,y} = k u(x,y)
on the domain
\Omega = [0,1]\times[0,1] with u(x,y) = 1 at all points on the boundary.Homework Equations
[/B]
I know that I...
Homework Statement
The question is, simplify this equation:
(A ∪ B ∪ C) ∩ ((A ∩ B) ∪ C)
The correct answer is (A ∩ B) ∪ C
Homework Equations
We have been given the commulative, associative, distributive, identity, complement and idempotent laws and DeMorgan's laws, and I researched the...
Hey guys
here is the question i'd appreciate if you could help me with it:
it says that no one dies in planet X,some spies of planet Y were captured by planet X's police.They are so professional that won't say anything to police so their inspection will go on forever and their inspection has no...
Dear Physics Forum mentors,
I am an undergraduate sophomore with double majors in mathematics and microbiology. I wrote this email to seek your recommendation on the discrete mathematics textbook that is in-depth, theoretical, proof-based, and also comprehensive. I am currently taking a...
Homework Statement
The question asks me to prove inductively that 3n ≥ n2n for all n ≥ 0.
Homework EquationsThe Attempt at a Solution
I believe the base case is when n = 0, in which case this is true. However, I cannot for the life of me prove n = k+1 when n=k is true. I start with:
3^k ≥...
Hey guys,
I was reading Kenneth's Discrete Mathematics and I came across this definition in the function chapter:
Let f be a function from A to B and let S be a subset of A.The image of S under the function f is the subset of B that consists of the images of the elements of S.We denote...
Hey I was reading Susanna Discrete book and I came across her definition of One-to-One function:
Let F be a function from a set X to a set Y. F is one-to-one (or injective) if, and only if, for all elements x1 and x2 in X,
if F(x1 ) = F(x2 ),then x1 = x2 ,
or, equivalently, if x1 ≠...
Isn't it amusing ?What could be the probable explanation for this?Also when operated by division operator gives the rest of the number as the quotient
(Note only when the divisor is 10)
I am a math major and I need to take Methods of Discrete Mathematics. What is methods of discrete mathematics? Should I take it after My calculus series( including linear/ diff. equations)? Is it easy enough to take with Calculus 2? Thanks
To give you a sense of strong induction and the relationship between mathematical induction and recursion (next session), let's do the pile splitting problem: Take a bunch of beads, rocks, coins, or any kind of chips. Ten is a good number. Split the pile into 2 smaller piles and multiply their...
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?
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...
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,
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...
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?
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...