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
3 answers

The range of function in Discrete Math

If A = {1,2,3} and B = {w,x,y,z},then the domain of f is A and codomain is B. However what about the range? Why is the range f=f(A)={w,x}, why cant it be {w,z}? Edit: f ={（1,w),(2,x),(3,x)}
Belphegor
  • 1,268
  • 6
  • 27
  • 51
1
vote
2 answers

Discrete Math and non-empty relations

Let $A=\{a,b,c,d\}$ and $B = \{w,x,y\}$, then a non-empty relations on $A$ is: $\{ (b,c), (b,d）\}$ Can someone explain why this is true? I thought that the requirements for any relations of a set has to be such that for $(x,y)$, $x$ has to be a…
jack
  • 11
1
vote
1 answer

Prove that there are $12 + n = 4k_1 + 5k_2, k_1, k_2 \in \mathbb{N}, n \in \mathbb{N}^+$

Question: Prove that there are $12 + n = 4k_1 + 5k_2, k_1, k_2 \in \mathbb{N}, n \in \mathbb{N}^+$ The question above is taken from the following: Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent…
JoeyAndres
  • 1,269
1
vote
2 answers

Prove or disprove that there are $n$ consecutive odd positive integers that are prime

Question: Prove or disprove that there are $n$ consecutive odd positive integers that are prime. If my answer for the question above is correct, then a new question arises. My Attempt: Odd numbers consist of multiples of $5$. I think that address…
JoeyAndres
  • 1,269
1
vote
2 answers

$\lfloor \sqrt{\lceil x \rceil} \rfloor = \lfloor \sqrt{x} \rfloor, \forall x \in \mathbb{R}$

Question: $\lfloor \sqrt{\lceil x \rceil} \rfloor = \lfloor \sqrt{x} \rfloor, \forall x \in \mathbb{R}$ My Attempt: Let $a = \lfloor \sqrt{\lceil x \rceil} \rfloor$ $$a \leq \sqrt{\lceil x \rceil} < a + 1\\ a^2 \leq \lceil x \rceil < (a+1)^2$$ Since…
JoeyAndres
  • 1,269
1
vote
5 answers

discrete mathematics and proofs

Let $a$ and $b$ be in the universe of all integers, so that $2a + 3b$ is a multiple of $17$. Prove that $17$ divides $9a + 5b$. In my textbook they do $17|(2a+3b) \implies 17|(-4)(2a+3b)$. They do this with the theorem of $a|b \implies…
Belphegor
  • 1,268
  • 6
  • 27
  • 51
1
vote
1 answer

Mathematical induction of the harmonics number

My textbook has the steps to prove it, but I can't comprehend the steps that the textbook are showing. Can someone explain the math or logic used going from steps red to yellow and finally green?
Belphegor
  • 1,268
  • 6
  • 27
  • 51
1
vote
1 answer

chinese remainder theorem constructive proof

I am trying to understand CRT constructive proof from wikipedia [http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution] I am unable to follow it from x = $\sum\limits_{i=0}^{k} a_i * e_i$ this…
thetatheta
  • 227
1
vote
2 answers

Equality of two sets written differently

$$A = \{2m+ 1:m \text{ exists in } \mathbb{Z}\}$$ $$B= \{2n + 3:n \text{ exists in } \mathbb{Z}\}$$ For this question, it seems that $A=B$, and we know it's equal because we can just plug in numbers from the universe of all integers, but my question…
Belphegor
  • 1,268
  • 6
  • 27
  • 51
1
vote
1 answer

Inclusion–exclusion principle (about intersections)

As an outcome of this question what does the Inclusion–exclusion principle means in disjoint? is {1,4}$\cap${1,2}=$\emptyset$?
gbox
  • 12,867
1
vote
4 answers

Modulus number theory (basic)

I'm having some trouble understanding Modulus. Suppose that a and b are integers, a ≡ 4 (mod 13) and b ≡ 9 (mod 13). Find the integer c with 0 ≤ c ≤ 12 such that a) c ≡ 9a (mod 13) b) c ≡ 11b (mod 13) c) c ≡ a + b (mod 13) d) c ≡ 2a +3b (mod 13) e)…
Mike
  • 11
  • 1
  • 1
  • 2
1
vote
1 answer

Is a function $f:\mathbb{Z}^2\rightarrow\mathbb{Z}$ injective?

The elements of $\mathbb{Z}^2$ would all be positive perfect squares, so when mapped onto integers, it is injective right?
baba
  • 299
1
vote
2 answers

Using the resolution proof system

so I can't figure out something when using the resolution proof system. We are given: {¬a → ¬b, b} on a what I can't figure out is why: ¬a → ¬b becomes a ∨ ¬b I understand it becomes an ∨, but why does ¬a get changed it to a? Thanks.
Javanoob33
  • 29
1
vote
1 answer

Composition on sets

[(1,2,3,4) ○ (1,2)(3,5)]^-1 The solution has the following steps: f=(1,2,3,4) g=(1,2)(3,5) Compute f○g: Where can I find information regarding what the steps are doing in this problem? I understand how to compute the composition of two functions…
dukevin
  • 507
1
vote
1 answer

Cartesian Product of $\emptyset \times \emptyset$

A bit of homework that I'm not sure on. The question reads: Let $A=\{a\}$ and $B=\{1,2\}$. Find the following: $$\mathcal{P}(A) \times \mathcal{P}(B)$$ The worked out solution is as follows. $\{ (\emptyset, \emptyset), (\emptyset, \{1\}),…
Tim
  • 219
1 2 3
…
99 100