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

How do I derive the properties from a relation from the associated matrix?

Would anyone be able to help me answer this question? Let $A=\{1,2,3,4,5\}$ and $R$ be the relation on the set $A$ whose matrix is $$M_R = \begin{bmatrix}1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 0 &…
Kell
  • 69
1
vote
3 answers

Showing that a composite function is bijective.

Can i straight away claim that $\varphi : T \rightarrow X$ is injective, and if $f:X \rightarrow Y$ is injective, then this means $f \circ \varphi : T \rightarrow Y$ is injective for as well any set T base on the fact that the composition of two…
Joe
  • 143
1
vote
1 answer

Closed-form representation of a recursively defined sequence

I am trying to find a closed-form representation of the following recursively defined sequence $$_0 = 0, _1 = 0, _2 = −2, _3 = 0$$ $$_{+4} = −2_{+2} − _n$$ I've been working with a lot of homework problems similar to this, but most of the time they…
mar10
  • 473
1
vote
1 answer

discrete math basic question

Al has 75 days to master discrete mathematics. He decides to study at least one hour every day, but no more than a total of 125 hours. Assume Al always studies in one hour units. Show there must be a sequence of consecutive days during which he…
omair azam
  • 115
1
vote
2 answers

recurrence equations. solve the equation

Solve the following recurrence equation $a_0=0, a_1=7$, and $$a_n=\frac{1}{3}a_{n-1}+\frac{4}{3}a_{n-2}, n\geq2$$ I have tried using the general method, however i am getting the same thing as $a_n$ already. I am taking this class as an independent…
jasmine
  • 11
1
vote
1 answer

Natural Number (Recursion Theorem)

For any natural number $a ∈ N$ , the exponential map of base $a$ is the map $a^ {( )} \mathbb{N} \rightarrow \mathbb{N}$, $n \mid \rightarrow a^n$, defined recursively (using the recursion theorem) by setting $a^0 := 1$, and for any $n ∈…
Joe
  • 143
1
vote
1 answer

Inequality induction proof

I have been practicing using Mathematical Induction, in proofs. I came across a problem in my practice problems list that is giving me a lot of trouble. This is the question Prove that $n! > n^3\ \mbox{for}\ n > 5$ So here is my inductive step that…
ultrainstinct
  • 2,651
1
vote
1 answer

Is Proof by Resolution really needed here?

So I'm doing a problem in the book but this problem (where they ask me to use proof by resolution) seems unnecessary: $p\iff r$ $r$ $\therefore p$ By definition of IFF, this seems true, but they ask me to prove by resolution? How do I go about it?…
secondubly
  • 477
1
vote
3 answers

Proof with inequalities and a function

I need help approaching a proof which deals with inequalities: If p and r are the precision and recall of a test, then the F1 measure of the test is defined to be $$F(p, r) = \frac{2pr}{p+r}$$ Prove that, for all positive reals p, r, and t, if t ≥ r…
Pandamonium
  • 975
1
vote
2 answers

The difference between the statements $"\forall x \exists y y > x"$ and $"\exists y \forall x y> x"$

I have here an explanation for the difference between the two statements but I don't understand something in it. The first statement says that for each positive integer $x$, there is a larger positive integer $y$. The second statement says there is…
Out Of Bounds
  • 1,531
1
vote
1 answer

Discrete Math: Which of the following statements is right and wrong

a) ∀x F(x) ∧ ∀x G(x) ≡ ∀x (F(x) ∧ G(x)) b) ∀x F(x) ∨ ∀x G(x) ≡ ∀x (F(x) ∨ G(x)) c) ∃x F(x) ∧ ∃x G(x) ≡ ∃x (F(x) ∧ G(x)) d) ∃x F(x) ∨ ∃x G(x) ≡ ∃x (F(x) ∨ G(x)) This is Discrete Mathematics. the instructions are "Which of the following statements is…
alex
  • 13
1
vote
2 answers

Evaluating modulos with large powers

I need some help evaluating: $$13^{200} (mod \ 6)$$ What I've been trying to do: $$13^1 \equiv 1 (mod \ 6)$$ $$13^2 \equiv 1 (mod \ 6)$$ Can I just say that: $$13^{200} = 13^2 * 13^2 * ... * 13^2 \equiv 1^{200}$$ Or is this incorrect? Thanks in…
Pandamonium
  • 975
1
vote
3 answers

Well Ordering Principle for a sum and why we only care about the set less than the smallest in our counter example set?

I was trying to prove: $$ \sum_{i=1}^n{i} = \frac{n(n+1)}{2}$$ using the WOP. I think the part that is confusing me about this proof is a more general pattern for proofs by WOP. To prove it we say that there exists a set of counter examples: $$C =…
Charlie Parker
  • 6,546
1
vote
1 answer

Congruence mod k

I'm trying to evaluate the following scenario: $$7^b \equiv 9\pmod {17}$$ Find the smallest value for b in which the equivalence holds true. I know that we can rewrite this as : $$17 \mid (7^b - 9)$$ But I'm not sure how to continue, could anyone…
Pandamonium
  • 975
1
vote
1 answer

Prove $99^{100}>100^{99}$ using binomial theorem

Prove $0<(1+\frac{1}{n})<3$ and hence prove $99^{100}>100^{99}$. I did the first part and showed $0<\frac{1}{n^{n-1}}\le3$ and hence $0<(1+\frac{1}{n})<3$. But for the second bit, I don't know how to incorporate the first bit to help me prove th…
user117498
  • 775
1 2 3
…
99 100