What is Discrete math: Definition and 214 Discussions

Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West (University of Illinois, Urbana).

View More On Wikipedia.org
Recent contents Top users
  1. L

    Combinations and Permutations in Briefcase and Coin Problems

    Hi all I need some assistance 1. Homework Statement with the attempt How many 5-digit briefcase combinations contain 1. Two pairs of distinct digits and 1 other distinct digit. (e.g 12215) I wasn't sure on which approach was correct. 10 * 9 * 8 (because there are three distinct...
  2. H

    How to have better discrete math insight

    How to have better discrete math "insight" Greetings: I came a cross a textbook example in a discrete math book that I have been reading on my own, and I thought this example in the book was a good example of what I want to be good at: Given integers from 0-9 arranged in a circle, is...
  3. S

    [Discrete math] Finding simple, nonisomorphic graphs with 4 nodes

    Homework Statement Draw all nonisomorphic, simple graphs with four nodes. (Hint: There are eleven such graphs!) Homework Equations N/A The Attempt at a Solution Well if you can imagine a square with the nodes as the vertices and no arcs connecting them, I figure that's isomorphic...
  4. M

    Direct Proof of gcd(a,b) Corollary: ax+by=d

    Corollary from book: if d= gcd(a,b), then there exists integers x and y such that ax + by = d. This is not an obvious statement to me. Are there any direct proofs to prove this statement? The book proves this by induction. My proof: Suppose d = gcd(a,b) and a and b are positive integers. a...
  5. M

    Determine Big O of a function (Discrete math)

    Question: Determine whether the function log(n2+1) is O(logn). Definition in paint document if needed. Solution: n2 + 1 < 2n2 whenever n>1 log(n2 + 1) < log( 2n2 ) = log(2) + 2log(n). Now, log(n)>log(2) whenever n>2. Therefore log(2) + 2log(n)<3log(n). log(n2 + 1) ≤ 3log(n)...
  6. C

    Discrete math sequence and inequality induction proof help

    Hello. I am reading an introduction to induction example, and I am having the hardest time trying to determine what exactly happened in the proof. Can somebody please help? How can ##3^{k-1}## + ##3^{k-2}## + ##3^{k-3}## all of a sudden become ##3^{k-1}##+##3^{k-1}##+##3^{k-1}## and how can be...
  7. B

    Discrete math : Induction proof

    Stuck on the induction step,please help
  8. M

    Problem from discrete math class

    How would I go about solving this? We are starting to learn about venn diagrams so would creating a venn diagram be helpful? This is what I tried so far, I created a set C consisting of all people who have taken calculus and a set D consisting of all people who have taken discrete math...
  9. A

    Discrete Math: How can I determine the consistency of the system?

    Homework Statement Are these system specifications consistent? "Whenever the system software is being upgraded, users cannot access the file system. If users can access the file system, then they can have new files, then the system software is not being upgraded." Homework Equations p...
  10. P

    Discrete Math, Intro Proof

    Homework Statement Using the rules of inference, prove that if ∀x(P(x) ∨ Q(x)) and ∀x((￢P(x) ∧ Q(x)) → R(x)) are true, then ∀x(￢R(x) → P(x)) is true as well. Homework Equations The Attempt at a Solution The problem arises step 5. I feel this is correct but the...
  11. R

    MHB Exploring Discrete Math Graph Theory Problems: A Scientist's Perspective

    I have these problems I need help with. Can anyone take a look at them? https://www.dropbox.com/s/vq8rk6z5ea5gpwd/Problems.docx
  12. 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...
  13. 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?
  14. 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...
  15. 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 >...
  16. 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...
  17. 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...
  18. 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...
  19. 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...
  20. P

    Discrete Math: Proving a Homework Statement

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

    Discrete Math Course: Conveying Material & Textbook Prep

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

    Discrete Math Proof: Solving Homework Equations

    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?
  23. B

    Finding a Solution to a Discrete Math Problem: Is Precise Necessary?

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

    Discrete Math Homework Question | Mod Explanation | Test Prep

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

    Discrete Math: prove an intersection from a given

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

    Precalculus knowledge for learning Discrete Math CS topics?

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

    How can the complementation law in Table 1 be proven for \stackrel{=}{A} = A?

    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)...
  28. N

    Discrete Math Question on Universal and Existential Quantifiers

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

    Discrete Math question on creating a logically equivalent compound proposition

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

    [Discrete math] Proving the form of a function

    I wasnt really sure where I was supposed to post this problem, so I figured this place is as good as any. Homework Statement x2 - the inversion of x2. (Yes, I was too dumb to figure out how to get "_" on it.) We are given that f(x1,x2,x3) = x1x2 v x2x3 v x1x3 = x1&x2 v x2&x3 v x1&x3 Prove...
  31. C

    Discrete Math Set Theory Question

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

    Discover the Dual of Compound Propositions - Discrete Math Question

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

    Discrete math - proof of divisibility question

    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.
  34. O

    Discrete math - simple formalism question

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

    Discrete Math Proof n^2 > n +1

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

    Discrete Math: Proving p(x)|(p1(x)-p2(x)) is Equiv. Rel.

    Homework Statement Let p(x) be a polynomial in F[x]. Show that p1(x)≈p2(x) if and only if p(x)|(p1(x)-p2(x)) is an equivalence relation The Attempt at a Solution To be completely honest, I have no idea where to begin. This class has been a nightmare and this has been, by far, the worst...
  37. H

    Discrete Math - Modular Arithmetic

    Homework Statement For which values of n≥2 does the implication: axb=0 ⇔ a=0 or b=0 For some Zn (n should be a subscript) NOTE: For the a x b, the x should be the x that has a circle around it. I didn't see that symbol in the "quick symbols" :) Homework Equations I know that this...
  38. Hercuflea

    Schools Trouble in Discrete math will it affect my graduate school opportunities?

    Hello everyone, I'm a first time poster and I just want to say this forum is great. Every time I have a question Physics Forums is the first site to answer it. So lately I have been really struggling in my Discrete Mathematics I course at my university. This is one of the few times in...
  39. B

    Discrete Math: What's the Best Way to Get Started?

    Would learning discrete math be more beneficial then diving into velleman's book right away? and what is a good book on discrete math?
  40. A

    Help with a discrete math homework problem

    Homework Statement show that for positive r and s, with r<s, we always have: r<(r+s)/2<s and 2/[(1/r)+(1/s)]^2< 2rs< (r+s)^2 Homework Equations The Attempt at a Solution i have shown that r<s because r+r<s+r, 2r<s+r, r<(s+r)/2 and 2r< (2s+2r)/4 (r+s)^2= r^2+2rs+s^2...
  41. R

    Discrete Math - Pigeonhole Principle Problem

    Homework Statement Suppose that a menu consists of 4 main dishes, 9 choices of side dishes, and 6 desserts. A small meal consists of one main dish and two different side dishes and no dessert. A large meal consists of one main dish, two different side dishes and dessert. How many patrons must...
  42. C

    Recurrence relations discrete math problem

    Homework Statement Find the general solution to the following recurrence relations (defined n≥2). c) an=6an-1-9an-2+8n+4 Homework Equations The Attempt at a Solution an=6an-1-9an-2+8n+4 8n+4= an -6an-1+9an-2 R2-6R+9=0 R=3,3 So hn=A(3)n+B(3)n Assume pn=Cn+Cn2 → This is where I got...
  43. R

    Discrete math, proving the absorption law

    Homework Statement Prove the second absorption law from Table 1 by showing that if A and B are sets, then A ∩ (A ∪ B) = A. Homework Equations Absorption laws A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A The Attempt at a Solution i will show A ∩ (A ∪ B) is a subset of A x is any element in A...
  44. Shackleford

    Discrete Math Exam Proofs: Senioritis & Graduation

    These are potential proofs for the discrete math exam on Tuesday. I haven't been able to find proofs online. I have senioritis, and I'm graduating in a few weeks. Is a proof by contraposition the best way to prove this? If you assume h is not a function or g is not a function, then that would...
  45. G

    Discrete Math Question ( not really homework) about strong induction

    For some questions strong induction would test for cases n+1, n+2 and for other n+1,n+2,n+3, or other ways, why is that? Here's two examples Suppose that the only paper money consists of 3-dollar bills and 10-dollar bills. Find what dollar amounts can be made from a combination of these...
  46. C

    Discrete math set theory sum problem

    Homework Statement Prove that if k>1 then, 5/(k-1)-3/k-2/(k+2) = (9k+6)/(k-1)k(k+2) Hence simplify Ʃ of k=2 to n {(3k+2)/(k-1)k(k+2)} Homework Equations The Attempt at a Solution Ok so the first part is ok I just multiplied the denominators with the numerators and...
  47. B

    Understanding Discrete Math for the Confused

    I read the definition of discrete math and i read the definition of discrete. i just can't seem to figure out what discrete math is, can you guys show what it means?
  48. S

    Discrete Math: Proving something is logically equivalent

    Homework Statement Show that (p ∧ q) → r and (p → r) ∧ (q → r) are not logically equivalent. Homework Equations a → b = \nega v b The Attempt at a Solution I'm sorry. I'm completely stumped on how to go about this problem. I'm not asking for the solution since I want to know how...
  49. S

    Discrete math, sets, power sets.

    Homework Statement If s (0,1), find |P(S)|, |P(P(S))|, |P(P(P(S)))| Homework Equations The Attempt at a Solution |P(S)| = {(0), (1), (0,1), ∅} = 4 |P(P(S))| = {...} = 16. |P (P(P(S)))| = {...} = 16 ^4 ...but how? as my lecturer explained it, it come from pascals...
  50. G

    Discrete Math Logic Defineing a function recursion-ish

    (3) De fine a function A(m,n) as follows. A(0,n) = 2n for every n. A(m,0) = 0 for every m >= 1 A(m,n) = 2 if m >= 1 and n = 1 A(m,n) = A(m -1,A(m, n - 1)) otherwise (i.e., if m >= 1 and n >= 2. (b) Prove A(m,2) = 4 for every m >= 2 (c) Prove A(1, n) = 2^n for every n >= 1. Proving...
Back
Top