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
1
vote
0 answers

Show that there is a Boolean function equal to 1 on the set

Show that for $n\to\infty$ there is such a boolean function $f:\{0,1\}^n\to \{0,1\}$ such that $n^3\le||f||\le2^{n-1}$ and with average complexity $T(f)=\theta(\frac{||f||}{log_2||f||})$. Help me solve this problem, I don't know where to start. If I…
gkndy
  • 117
1
vote
0 answers

How to proceed with this counting problem?

The question is — How many functions are there from the set ${1,2,...,n}$, where $n$ is a positive integer, to the set ${{0,1}}$ that assign $1$ to exactly one of the positive integers less than $n$? I have done this — there are $(n-1)$ elements in…
user733666
  • 578
1
vote
4 answers

Find the sum using properties of binomial coefficients

I need to find the following sum using properties of binomial coefficients:$$\sum\limits_{k=0}^{n} k^3 {n\choose k}^2.$$ I transformed this sum first in:$n^2\sum\limits_{k=1}^{n} k{n-1\choose k-1}^2$. Then after substitution $j=k-1$ I get…
Trevor
  • 533
1
vote
1 answer

Am I determining the Image correctly?

basically we have $f: \mathbb{Z} \rightarrow\mathbb{N_0} $ with $f (n) = \left\{ \begin{array}{ll} -2n & n \leq 0 \\ 2n-1 & \, \textrm{n > 0} \\ \end{array} \right. $ And I should determine $Im(2\mathbb{Z})$ the image of f under $2\mathbb{Z}$ with…
jenny
  • 87
1
vote
3 answers

Recursive function of $n^2$?

How would you convert $n^2$ into a recursive function? Like for example, I can say the recursive function of $2^n$ is $2 \cdot 2^{n-1}$, and it can be applied recursively since it requires the previous value.
kyleawayan
  • 35
1
vote
1 answer

Question about uniform continuous proof.

If $f(x)$ define as: $f(x) = x\cos(\log(x))$, when $x > 0$. $f(x) = 0$, when $x = 0$. How we prove that $f$ is uniform continuous in $[0, +\infty[$?
LLLLLLLL
  • 23
1
vote
2 answers

$B=\{f\in\{0,1\}^\mathbb N :f^{-1}(\{0\}) \,\text{and}\, f^{-1}(\{1\}) \, \text{infinite}\, \}$

$$B=\{f\in\{0,1\}^\mathbb N :f^{-1}(\{0\}) \,\text{and}\, f^{-1}(\{1\}) \, \text{infinite}\, \}$$ Prove that B is not a countable set. I thought about creating a function for every $n\in\mathbb N$ so $\pi :\mathbb N\longrightarrow B$, and another…
Mr787
  • 27
  • 3
1
vote
1 answer

How do you find a square on a grid from a position?

The title might be a bit confusing, since I didn't know how to put this into one sentence. I have a 10x10 grid and every square on the grid is 100 pixels (this is a programming problem) from edge to edge. If I have a position where the x and y-value…
JensB
  • 113
1
vote
0 answers

Quantifier matrix

Let $A$ be a matrix with $m$ rows and $n$ columns. $a_{ij}$ denotes the real number in the cell in row $i$ and column $j$. How can I express (with a quantified statement) that: All diagonal elements of $A$ are equal to $0$. The largest value in the…
FPSX V
  • 33
1
vote
2 answers

How to express an if and only if statement using ∧, ∨, and ¬?

Say I have a statement A if and only if B. How do I do it without an arrow just using these symbols? Do I get a truth table? Thank you.
Math Whiz
  • 335
1
vote
0 answers

For each of the following sets A, B prove or disprove whether A ⊆ B and B ⊆ A

Would this proof be sufficient for just proving B ⊆ A alone? $A = \{x ∈ \Bbb Z : ∃y∈\Bbb Z,x = 5y + 1\},\ $$B = \{x ∈ \Bbb Z : ∃y∈\Bbb Z, x = 10y − 9\}$ Suppose some arbitrary element x is in B. if x∈B, then x∈A by definition of B ⊆ A. Also, by the…
Nicholas
  • 21
  • 2
1
vote
0 answers

Set proof attempt

I'm not very confident in what I'm doing here yet so I'd just like to get some verification that if the logic is correct or not. Thanks. Prove of disprove: P(R ∪ S) ⊆ P(R) ∪ P(S) ∪ P(R ∩ S) My attempt: Counterexample: Let R= {1,2} and S= {2,3} R…
Nicholas
  • 21
  • 2
1
vote
1 answer

Prove the existence of a row and a column in the Boolean matrix which satisfy the conditions

"Let A be an 8x8 Boolean matrix. If the sum of A = 51, prove that there is a row and a column such that when the total entries of the row and column are added, the sum is greater than 13." I have started with the idea that a sum of 51 implies that…
JesseP_613
  • 63
1
vote
2 answers

Find the size of the set using additive rule

how do I go about finding set sizes? Example |A| = 129; |B| = 53; |A ∩ B| = 34; |A ∪ B| =
Nick
  • 15
  • 2
1
vote
1 answer

Relations. Check whether symmetric,reflexive or transitive .?

Q6. Let R and S be relations on a set A. Assuming A has at least three elements, state whether each of the following statements is true or false. If it is false, give a counterexample on the set A = {1,2,3}. If R and S are symmetric then R ∩ S is…
veeyikpong
  • 121
1 2 3
…
99 100