Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
2
votes
1 answer

Hierarchy of Mathematics Breakdown

Can you provide me with a hierarchical breakdown on Discrete Math as it applies to computer science? By this I mean a breakdown on topics that fall under the study of discrete numbers, specifically those that apply to computer science. I understand…
P0LYmath
  • 123
2
votes
1 answer

language generated by a grammar

I was wondering if someone could look over this problem set and tell me if my answers are wrong and if so how. Thanks in advance Let V = {S,A,B,a,b} and T = {a,b}. Find the language generated by the grammar (V,T,S,P) when the set of productions…
Eric Rangil
  • 41
2
votes
1 answer

Defining the domains that verify and falsefy a proposition

Find a common domain for the variables x,y, and z for which the statement ∀x∀y((x≠y)→∀z((z=x)∨(z=y))) is true and another domain for which it is false. This problem stumped me. I wrote: The statement is true for any binary domain (such as {0,1})…
Ocasta Eshu
  • 307
2
votes
1 answer

Injection and Surjection

In each part of this problem, give examples of sets A,B,C and functions f : A → B and g : B → C satisfying the indicated properties. a) g is not injective but g ◦ f is injective. b) f is not surjective but g ◦ f is surjective. Suggestion: Work with…
Joe Neely
  • 101
2
votes
0 answers

Pigeon hole drunken mailman

Two letters need to be delivered to each of $n$ houses. How many ways can a postman deliver two letters to each house such that each house receives at least one incorrect letter? Right now I have the total number to deliver two letters to $n$…
user2980566
  • 365
2
votes
2 answers

Prove that for any integers x,y there are integers a,b such that gcd(x,y) = ax + by

How would I go about proving that: For any integers x,y there are integers a,b such that gcd(x,y) = ax + by? One thing I noticed is that when x is a multiple of y or vice versa, the smaller number is automatically the gcd; thus, in those situations,…
user193093
  • 23
2
votes
3 answers

Issue with Proof by Contradiction

So we were asked to solve a question in class about proof by contradiction... Q) Suppose integers $1,2,3,\dots,10$ are placed randomly in a circular wheel. Show that the sum of any three consecutive integers is at least $15$. Logical Answer: NO,…
arijeet
  • 123
2
votes
1 answer

Equivalence classes with respect to congruence modulo

If $A$ and $B$ are subsets of $\mathbb{Z}$, define $AB = \{ab : a ∈ A \wedge b ∈ B\}$. For each integer $x$, let $[x]$ be the equivalence class of $x$ in $\mathbb{Z}$ with respect to congruence modulo $n$. Then the equation $[x][y] = [xy]$…
Jay
  • 352
1
vote
0 answers

Is $\forall x\exists y \bigl(P(x)\to P(y)\bigr)\to\forall x\exists y\bigl(P(x)\to(y)\bigr)$ logically valid?

$$\forall x\exists y \bigl(P(x)\to P(y)\bigr)\to\forall x\exists y\bigl(P(x)\to(y)\bigr)$$ Here's what I have so far, but I think it's wrong: $$\begin{align*} &\neg\Bigl( \forall x\exists y\bigl(P(x)\to P(y)\bigr) \to \forall x\exists y\bigl(…
kylex
  • 123
1
vote
4 answers

Prove that $1+4+7+...+(3n-2) = \frac{n}{2}(3n-1)$

Using induction prove that $1+4+7+...+(3n-2) = \frac{n}{2}(3n-1) \forall n \in \mathbb{N}$ Attempt: Let $n =1$ so $3(1)-2 = 1$ and $\frac{1}{2}(3(1)-1)=1$ Assume true at $n=k$ so $3k-2 = \frac{k}{2}(3k-1)$ What do I do next? Here's where I'm…
Slae
  • 277
1
vote
1 answer

Prove that $\sum_{i=0}^n4^i$ = $1/3(4^{n+1} - 1)$

$\sum_{i=0}^n4^i$ = $1/3(4^{n+1} - 1)$ Attempt: Let $n =0$ $4^0 = 1 \text{ and } (4^{0+1} -1)/3 = 1$ Assume true at $n = k \text{ so we have} \sum_{i=0}^k4^i = 1/3(4^{k+1} -1)$ The part I'm stuck at is the 3rd step. Can someone point me in the right…
Slae
  • 277
1
vote
2 answers

How to prove this $\theta$ notation

How do you prove that the folowing function is equal to $\theta(n^2)$? $$f(n)=\frac{n^3+n+1}{2n+\ln(n)}.$$ Then $f(n)=\theta(n^2)$. Thanks!
Jody
  • 89
1
vote
2 answers

6th Grade Problem

Here's a problem from a 6th Grade textbook: A project was carried out by a 3-man brigade working for 5 days and a 4-man brigade working for 4 days. $390 was paid for the whole project. How much was the first brigade paid if the productivity of all…
Armen Tsirunyan
  • 869
1
vote
2 answers

Suppose that$\ gcd(b, a) = 1$. Prove that $\gcd(b + a, b − a) \leq 2$

Suppose that $\gcd(b, a) = 1$. Prove that $\gcd(b + a, b − a) \leq 2$ I've been given a hint I should use divisor rules, so I have if $d \mid b+a$ and $d \mid b-a$, then $d \mid 2a$ and $d \mid 2b$, but then I'm stumped on what to do after
user2980566
  • 365
1
vote
1 answer

Consider strings of length n taken from the restricted alphabet {a, b, c}.

Consider strings of length n taken from the restricted alphabet {a, b, c}. (a) How many such strings are there? (b) How many such strings are there with exactly two as? (c) How many such strings are there with at least two as? (d) How many such…
user186366
1 2 3
…
99 100