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

Suppose $ k $ is a positive integer. Prove that there is some positive integer $ a $ such that for all $ n>a, 2^n \geq n^k $.

Suppose $ k $ is a positive integer. Prove that there is some positive integer $ a $ such that for all $ n>a, 2^n \geq n^k $. Hint use divisor algorithm. From this book http://users.metu.edu.tr/serge/courses/111-2011/textbook-math111.pdf page 298…
helios123
  • 63
1
vote
1 answer

Finding number of strings

How many ternary strings of length 10 that contain exactly 2 1s and 3 2s. Since it must contain exactly 2 1s and 3 2s the other 5 spaces must be 0s. I was thinking it's 2!3!5! But apparently it's 10!/(2!3!5!) Can someone explain why we need the 10!
Sook Lim
  • 243
1
vote
1 answer

Are these two statements on predicates equivalent?

$\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall x P(x) \rightarrow \forall x Q(x)]$ $\forall x [P(x) \rightarrow Q(x)] \Rightarrow [\forall y P(y) \rightarrow \forall z Q(z)]$ How do you prove them if it's the case? I mean, we don't know the…
hjggh
  • 183
  • 1
  • 7
1
vote
1 answer

Is this the correct way to prove $\exists y \forall x (P(x) \vee Q(y)) \equiv \forall xP(x) \vee \exists x Q(x)$?

$\exists y \forall x (P(x) \vee Q(y)) \equiv \forall xP(x) \vee \exists x Q(x)$ If the LHS is true, then there are two cases: P(x) is true, in which case $\forall$ P(x) is true and the RHS is true, and Q(y) is true, in which case $\exists$ x Q(x) is…
Gladstone Asder
  • 1,051
1
vote
1 answer

is it possible to make two statements in one predicate sentence?

The statement i want to translate is this: x is the smallest real number and P(x) is false $\exists x \in \mathbb{R} \forall y \in \mathbb{R} \neg (P(x)); x > y$ I don't know how to put two statements in one predicate sentence.
hjggh
  • 183
  • 1
  • 7
1
vote
1 answer

How do you write the following statements in predicate form?

There is no greater real number. There is no positive integer that is greater than any other positive integer. I was wondering if the negative sign is necessary here or not. Are there many different ways of writing the two statements?
hjggh
  • 183
  • 1
  • 7
1
vote
1 answer

Define a recursion that gives the number of sequences that include the numbers $0,1$ that does not contain the sequence $0011$.

Define a recursion that gives the number of sequences that include the numbers $0,1$ that does not contain the sequence $0011$. The way I thought about it is to start with a all possible beginnings and complete the the beginning to a complete…
Baraa Natour
  • 35
1
vote
3 answers

Proof for sum of consecutive number from one to any odd number is $(k+1)(2k+1)$

I recently saw a formula that was found by Levi Ben Gershon in 13th century. The formula allows you to sum up the integers from one to any odd number by multiplying the middle element with the last. $$ \sum_{n=1}^{2k+1}n = (k+1)(2k+1)$$ ​ Is there…
Gigalala
  • 193
1
vote
0 answers

Show that $F_n \geq\phi^{n-2}\hspace{0.35cm} \forall n \in \mathbb{N},\hspace{0.35cm} n \geq 2$

Let $(F_n)_{n = 1} ^ \infty$ be the Fibonnaci sequence. Show that $F_n \geq\phi^{n-2}\hspace{0.35cm} \forall n \in \mathbb{N},\hspace{0.35cm} n \geq 2$ where $\phi$ is the golden ratio. This is my solution, Proof method: strong induction on…
Philip
  • 198
1
vote
1 answer

Theorem 4.5.1 and Corollary 4.5.2 simplify

Let U be the universal set and let A, B and C be subsets of U. By using the properties of U, ∩ and ~(complement), Theorem 4.5.1 and Corollary 4.5.2, how can I simplify the following? (i) (C ∩ U) ∪ ~C (ii) ~(A ∩ U) U ~A (iii) ~[~(C U 0) U C] (iv) …
Julfikar
  • 127
1
vote
3 answers

Spot error in proof: If A×B⊆C×D , then A⊆C and B⊆D

This question is from pg 171 of this book. http://users.metu.edu.tr/serge/courses/111-2011/textbook-math111.pdf For any sets A, B, C, and D, if A × B ⊆ C × D then A ⊆ C and B ⊆ D. Is the following proof correct? If so, what proof strategies does…
helios123
  • 63
1
vote
2 answers

How do we simplify mod expressions?

I have a modulus function that looks like this $f(x) = 2x+3 \bmod b$, and i have to show that $x = y$ to prove that the function is $1-1.$ I know that mod functions can't be algebraically manipulated like regular function, so I was wondering if it…
hjggh
  • 183
  • 1
  • 7
1
vote
1 answer

Give the elements of the partially ordered set,which covering relation is the following $\{(a,c),(c,d),(b,e),(d,e) \} \subseteq \{a,b,c,d,e \}^2$

$ \{(a,c),(c,d),(b,e),(d,e) \} \subseteq \{a,b,c,d,e \}^2$ I don't know exactly, how to write these elements. I know that a poset has to be reflexive,antisymmetric, and transitive. I also know that a covering relation of a poset is a binary relation…
Herrpeter
  • 1,326
1
vote
2 answers

How do we show that this modular function is one-to-one?

$$f(x) = {(x^2+5)}\bmod{9}$$ $${(x^2 + 5)} \bmod {9} = (x^2 + 5)\bmod 9$$ $$(x^2 + 5) = (x^2 + 5)$$ $$x^2 = x^2$$ $$x = x$$ Is this the correct way to do this? I have no idea how to manipulate the terms.
Gladstone Asder
  • 1,051
1
vote
3 answers

Is a function that is one-to-one necessarily onto?

I'd would like to know that, because I don't want to prove a function is onto if I don't have to. If the answer is no, is there any particular case where it is true?
Gladstone Asder
  • 1,051
1 2 3
…
99 100