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

Symmetric difference of symmetric difference

Let $X, Y, Z \neq \emptyset$. The set of elements that belong to exactly two of the sets $X,Y,Z$ was asked in the question and $(X\cup Y\cup Z) \setminus \left( \left(X\triangle Y\right) \triangle Z\right)$ was given as the answer I worked this out…
Ray
  • 129
3
votes
1 answer

Applying Zorn's lemma on a set of all sets.

Let $U$ be the set of all sets. Define a partial ordering on $U$ by inclusion: $A \leq B$ iff $A \subseteq B$ for $A, B \in U$. Consider a chain $C$ of $U$ under this partial ordering: $$ C : A_1 ≤ A_2 ≤ A_3 ≤ \cdots $$ Define $B =…
Jaswant
  • 39
3
votes
3 answers

Prove that $n^2-1$ is divisible by 8 for any odd integers n.

Below is my proof and I am confused about a few points. I am not sure the final lines are correct as I know that showing 2,4 are factors of $4k^2 + 4k$ is enough to prove that it is divisible by 8 and I have looked at some other examples. In an…
bloomsdayforever
  • 485
3
votes
0 answers

Is $x = 2^6$ a statement

I'm reading Susanna Epp's book on discrete mathematics. The exercise 2.1.5 ask which sentences are statements, a statement being something that is either true or false but not both. Question: is $x=2^6$ a statement? Can equations with variables be…
Erik Eriksson
  • 843
3
votes
2 answers

Prove that there exists infinitely many prime numbers of the form 4k+3 for some integer k.

We shall prove this theorem by contradiction. Assume $p_n$ is the largest prime number of the form 4$k_n$+3 for some n $\in$ $\mathbb{N}$. Consider an odd value of n. Even if n is even, we could miss one of the prime numbers to get an odd n. Now,…
Alex
  • 557
3
votes
2 answers

Counting donut problems

By using the permutation and combination techniques, i have attempt to solve this problem and i would like to know if where i did it wrong how many ways to choose $12$ donuts from a store that offers thirty varieties? here is my…
jake
  • 41
3
votes
3 answers

How to prove (p → q) ∨ (q → r) ≡ (p ∧ q) → r

My attempt at this mathematical demonstration was as follows: (p → q) ∨ (q → r) ≡ (~p ∧ q) ∨ (q → r) ≡ q ∨ (p → r) ≡ (q ∨ p) → r ≡ (p ∨ q) → r
LARICY EMMANUELLY DA SILVA FER
  • 65
3
votes
1 answer

Show that $ 3^n$ is not $\mathcal{O}(2^n)$

To show that $2^n$ is $\mathcal{O}(3^n)$ is straightforward. On the other hand, if we want to show the opposite that $3^n$ were $\mathcal{O}(2^n)$, then we would have $3^n\le C·2^n$ for all sufficiently large $n$. This is equivalent to $C\ge…
Avv
  • 1,159
3
votes
4 answers

Proving a floor function is injective/surjective

Is the function $\lfloor x/2\rfloor$ injective or surjective? If so why? The domain is $\mathbb R$ and the co-domain is $\mathbb Z$. I think it is not injective as if we take x to be $20$ and $y$ to be $21$, we end up with $f(x)=10=f(y)$, but $x$ is…
tom786
  • 59
3
votes
2 answers

Finding anti difference for a given expression

I am given: $$ a_n = \frac{1}{n^2 +3n+2}$$ And am asked to find the anti difference (i.e: quantity which when differences over gives the expression) So, I started by partial fractions $$ a_n = \frac{1}{n+1} + \frac{-1}{n+2} $$ Now the answer to this…
tryst with freedom
  • 11,538
3
votes
3 answers

Is there a tutorial that uses english to form an example of a proof, or a very simple way to show how a proof works?

I am in a discrete math in college and would like to understand proofs. I had to prove the fundamental theorem of calculus in Calc 1, and did horribly in Linear algebra because of proofs. How does one Understand proofs? Is there an elementary level…
Joe
  • 31
3
votes
1 answer

How can this statement be false? "If $\forall x \in D$, $P(x)$ then $\exists x \in D$ such that $P(x)$."

I'm a college student taking a discrete mathematic course for summer. I took midterm last monday and got back grades and solutions for the exam, but I'm still confused with this specific question. The question is: Let $D$ represent a set and $P(x)$…
Lumificier
  • 31
3
votes
3 answers

At least two points are $13$ apart

Let $x_0,\dots,x_{37}$ be $38$ distinct integral points inside $[0,60]$ with $x_0=0$ (e.g. $0,1,2,\dots 37$ or $0,2,3,\dots 38$, etc). Prove that there exists two points $x_i$ and $x_j$ such that $x_j-x_i=13$. I thought of pigeonhole principle, but…
anonymous67
  • 3,458
3
votes
1 answer

Determine whether a function is onto / one-to-one - Discrete mathematics

I need to determine for each domain $A$ and range $B$ if the function $f$ is onto/one-to-one: $f : A \rightarrow B $ Given: $f = \{(1,2), (2,4), (3,2)\}$ 1) $A = \{1,2,3,4\}$ and $B = \{2,4\}$ By seeing these two pairs: $(1,2)$ and $(3,2)$ I…
user757932
3
votes
2 answers

Floor and Ceiling (determining solutions)

"Determine which of the following are solutions of the equation $\lfloor x \rfloor = \lceil -x \rceil - 6$" I understand there are two methods to finding a solution for the floor when $x$ is an integer and $x$ is not an integer. Just wondering if…
Max Yendall
  • 31
1 2 3
…
99 100