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
1 answer

Combining "exists" and "forall" expressions

How to combine an "exists" and a "forall" expressions for a same variable? ex.: $(\forall e \mid e \in S \Rightarrow e \in T) \vee(\exists e \mid e \in S \wedge e \notin T)$ Combining $2$ foralls or $2$ exists is simple, but what if it is a mix of…
lolgab123
  • 31
1
vote
0 answers

Show that for any integer $n$ which is relatively prime to $N$, it can be written as $a^k \pmod N$ for some integer $0 < k < (p−1)(q−1)$

Assume $a^{(p−1)(q−1)} \equiv 1 \pmod N$, and for any positive integer k where $0 < k < (p−1)(q−1)$, $a^k \neq 1 \pmod N$. Show that for any integer s which is relatively prime to N, s can be written as $a^k \pmod\ N$ for some integer $0 \leq k <…
John
  • 11
1
vote
1 answer

T/F: $\exists x\in(0,1] \forall y\in(0,1](x \leq y)$

Question 1: T/F: $\exists x\in(0,1] \forall y\in(0,1](x \leq y)$ My first assumption is this statement is true. However, I'm having trouble providing a sufficient proof since we cannot find the 'smallest number' next to 0.
Mel A.
  • 13
1
vote
2 answers

Proving functional properties

How do I prove that: $f(S ∩ T) \neq f(S) ∩ f(T)$ unless $f$ is one-to-one? I tried finding contradicting example like considering the function $f(x)=x^2$ with $S = \{-2,-1,0,1,2\}$ and $T=\{0,1,2,3,4\}$ or using the function $f(x) = |x|$, but, it…
mathmaniage
  • 596
1
vote
1 answer

Is this function both increasing and not injective?

I'm supposed to come up with a function from $\mathbb R$ to $\mathbb R$ that is increasing and not injective. I came up with $$f(x) = 1$$ which by my understanding is increasing and obviously not injective. Am I correct in believing this?
Mdomin45
  • 145
1
vote
1 answer

Exhibit a one-to-one correspondence between the set of positive integers and the set of integers not divisible by $3$.

I'm working on a math problem and I'm kind of stuck. I have to show whether a set is countable or uncountable, and then as the title implies I have to exhibit a one-to-one correspondence between that set and the set of positive integers. The set I'm…
rts_carl
  • 15
1
vote
2 answers

Is there a fast way to see if a relation is transitive just by looking at its relation matrix?

I don't want to do 5 matrix multiplication for this. Is there any easy way?
Math
  • 11
1
vote
1 answer

Prove Hamilton and Euler - graphs

i want to prove that if this is Hamilton or Euler.Euler is when there is even number (in this case there are 12 edges so it is,if it was 7 it will not be Euler).Hamilton is when Hamilton when every edge once and acne is going only once.In this…
a.x
  • 11
1
vote
2 answers

Minimum and maximum number of elements in intersection of sets.

In a battle 70% of the combatants lost one eye, 80% an ear, 85% a leg, 75% an arm, x% lost all four limbs.Then What is the minimum value of x? What is the maximum value of x? From van diagram I figured that the minimum value of x is 10%. But I am…
Kangkan
  • 317
1
vote
2 answers

Prove that if $n$ is a positive integer, then $3^{2^{n}}-1$ is divisible by $2^{n+2}$

Prove that if $n$ is a positive integer, then $3^{2^{n}}-1$ is divisible by $2^{n+2}$ I tried to prove this using induction so for the base case $n=1$ you get that $8 \mid 8$ For the inductive step assume $P(k): 2^{k+2}\mid 3^{2^{k}}-1$ is true for…
HighSchool15
  • 2,061
  • 14
  • 35
1
vote
3 answers

How do you compute the number of reflexive relation?

Given a set with $n$ elements I know that there is $2^{n^2}$ relations, because there are $n$ rows and $n$ columns and it is either $1$ or $0$ in each case, but I don't know how to compute the number of reflexive relation. I am very dumb. Can…
George
  • 43
1
vote
2 answers

Discrete Mathematical Question (When is $P_1 \oplus \cdots \oplus P_n$ true)

Question: Let $P_1,\ldots,P_n$ be propositional variables. When is the statement $P_1 \oplus \cdots \oplus P_n$ true? I'm currently learning the basics of discrete math. I am stuck on this last question of my assignment... not really sure how to go…
I'm Hungry
  • 181
1
vote
1 answer

Structural Inductions

I'm looking at 2 versions of textbook for structural induction and I just can't understand structural induction and how to draw the rooted trees from it. Does anyone have a good resource or can help me lighten up my brain so that I can understand…
Aaron
  • 551
1
vote
2 answers

Proving this relation is an equivalence

For $\sim$ defined on $\mathbb{Z}$ by $$x\sim y \iff m^2 x = n^2 y$$ for some positive integers $m,n$. I'm not sure if the transitive property is properly proved here.. Suppose $x,y,z \in \mathbb{Z}$ with $x \sim y$ and $y \sim z$. Then, for…
Natash1
  • 1,379
1
vote
0 answers

Random line breaking distributions

Let's say I have two ropes of length $1$ which have each been broken into three pieces with each breaking point being chosen randomly and independently. We know from previous results that the expected value of the largest length in each is $11/18$…
Pierre Humbert Leblanc
  • 193
  • 1
  • 2
  • 9
1 2 3
…
99 100