Discrete mathematics Definition and 106 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. V9999

    I Discrete mathematics--An easy doubt on the notations of sums

    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...
  2. V

    Expected Value of Election Results

    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...
  3. The Bill

    Intro Math What were the first modern Discrete Mathematics and Precalculus texts?

    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...
  4. Magnetons

    False. The statement does not logically follow from the given information.

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

    I Cardinality of decreasing functions from N to N

    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| ##...
  6. V

    I Translate compound proposition p → q (implication) to p↓q question

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

    Upper bound height and lower bound height of a 3-ary ordered tree

    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...
  8. F

    I Classify the isomorphism of a graph

    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...
  9. matqkks

    How to motivate students to do proofs?

    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...
  10. H

    MHB Discrete Mathematics - Define a relation R on S of at least four order pairs

    Let S = {1,2,5,6 } Define a relation R on S of at least four order pairs, as (a,b)  R iff a*b is even (i.e. a multiply by b is even)
  11. Aaron Buckley

    I Help understanding Big O notation

    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...
  12. Sarina3003

    Generating functions, binomial coefficients

    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...
  13. Sarina3003

    Counting Sequences with Repetition Using Stars and Bars Method

    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...
  14. P

    Probability of drawing a kind from a deck of poker

    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...
  15. M

    Propositional function problems

    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...
  16. S

    I Discrete Mathematics Function Topic

    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...
  17. U

    Discrete Mathematics logic questions

    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...
  18. M

    I Is Discrete Mathematics Hard and Is It Pure or Applied?

    Is Discrete Mathematics hard? Is it pure or applied math?
  19. M

    I Sum principle proof: discrete mathematics

    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]##...
  20. Euler2718

    Is This Logical Argument Valid?

    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...
  21. Avatrin

    Math Applications of discrete mathematics minus software

    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)
  22. M

    Ordered set proof review request

    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...
  23. M

    MHB Combinatorics problem. Discrete Mathematics II

    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...
  24. a255c

    Show that a sample space is valid by verifying properties

    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...
  25. squelch

    Counting permutations of a string with repeating characters

    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...
  26. T

    Discrete Math: Poset Characteristics and Minimum Element Count

    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...
  27. Dewgale

    Discrete Independent Study of Discrete Mathematics

    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!
  28. logico

    Can randomness and determinism coexist?

    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.)
  29. G

    Is This Discrete Mathematics Argument Valid?

    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...
  30. K

    Question regarding counting in discrete mathematics

    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 α, β...
  31. B

    RHS of Laplace's Equation is f(u(x,y))

    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...
  32. M

    How Can You Simplify the Set Expression (A ∪ B ∪ C) ∩ ((A ∩ B) ∪ C)?

    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...
  33. S

    MHB Easy question regarding symbols in discrete mathematics

    is the set of symbols that make up strings denoted by the symbol Σ or Σ* , also what is this difference?
  34. S

    A discrete mathematics question about logic?

    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...
  35. B

    Discrete Seeking Recommendation on Discrete Mathematics textbook

    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...
  36. H

    Can Induction Prove 3^n ≥ n2^n for All n ≥ 0?

    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 ≥...
  37. N

    Understanding the Function of Set S in Discrete Mathematics

    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...
  38. N

    One-to-One Function: Definition & Examples

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

    Modulus & Division: Last Digit of Numbers Explained

    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)
  40. T

    MHB Learning calculus through discrete mathematics

    Hello, Are there any free online textbooks or resources that teach calculus through discrete mathematics or does that not exist?
  41. T

    Not sure to take Methods of Discrete Mathematics after Calculus 1

    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
  42. J

    MHB How Does Strong Induction Prove Consistency in the Pile Splitting Problem?

    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...
  43. J

    MHB Truth Table in Discrete Mathematics

    Use a truth table to determine that "division into cases" rule of inference is valid.
  44. 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?
  45. J

    MHB Discrete Mathematics Vcomparisons

    How many vcomparisons did you actually need?
  46. 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...
  47. C

    How to Prove the Validity of a Discrete Mathematics Argument?

    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...
  48. I

    Discrete mathematics, bijections between disjoint unions

    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...
  49. 1

    Physics and discrete mathematics

    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?
  50. P

    Overview of Discrete Mathematics

    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...
Back
Top