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

" There exists either a computer scientist or a mathematician who knows both discrete math and C++ " what will be the logical equivalent sentence?

Assume, $P(x) : x$ is a computer scientist. $M(x): x$ is a mathematician. $D(x) : x$ knows discrete math. $C(X) : x$ knows C++. I translated the sentence into logical statement which is, $$∃x ( ( P(x) ∨ M(x) ) ∧ ( D(x) ∧ C(x) ) )$$ is it correct?…
Mr. Mayhem
  • 11
  • 1
1
vote
1 answer

Is this pumping lemma solution correct?

Let Σ = {a, b, c}. Use the pumping lemma to prove that A = {aibicj | i,j ≥ 0} is not regular. Please make sure that your proof is clear, logical and complete. The solution that I wrote was: Assume that A = {aibici | i,j ≥ 0} is regular. Let p be…
user2357373
  • 21
1
vote
1 answer

$[z^n]T(z)$ for $T(z)=\frac{1-\sqrt{1-4z^6}}{2z^2}$

Let $$B(z)=\frac{1-\sqrt{1-4z}}{2z}$$ and $$T(z)=\frac{1-\sqrt{1-4z^6}}{2z^2}$$ I know that $[z^n]B(z)=\frac{1}{n+1}\binom{2n}{n}$ (Catalan numbers). We have that $T(z)=z^4B(z^6)$, so $[z^n]T(z)=[z^{n-4}]B(z^6)$ I thought this would imply that…
user826130
  • 329
  • 1
  • 8
1
vote
1 answer

Logic error in proving that $(A\times{B})\cap{(C\times{D})} = (A\cap{C})\times{(B\cap{D})}$

I had a question about this proof, I sort of know intuitively how to do it but it's not aligning with my understanding of how logic works. My first part of the proof goes as followed... ($\longrightarrow$) Suppose that for some arbitrary $p$ that…
kman
  • 137
1
vote
2 answers

Proving a Set is a Subset of another (with functions)

we have $A =\{m ∈ \mathbb{Z}|m=6r-5,r ∈ \mathbb{Z}\} $ and $B = \{n ∈ \mathbb{Z}| n= 3s+1, s ∈ \mathbb{Z}\}$ prove $A ⊆ B$ I have Proof: suppose $A = \{m ∈ \mathbb{Z}|m=6r-5,r ∈ \mathbb{Z}\}$, $B = \{n ∈ \mathbb{Z}| n= 3s+1, s ∈…
Slowly_Learning
  • 47
  • 1
  • 1
  • 7
1
vote
1 answer

For weak partially ordered set $ R(f) = \{ \langle A,B \rangle | f(A) \subseteq f(B) \} $ , show function $ T(f) $ is one-to-one.

Problem: Let $ f \in P(\mathbb{N}) \rightarrow P(\mathbb{N}) $ be one-to-one. We define the weak partialy ordered set $ R(f) = \{ \langle A,B \rangle | f(A) \subseteq f(B) \} $. Let $ F \subseteq P(\mathbb{N}) \rightarrow P(\mathbb{N}) $ be the set…
hazelnut_116
  • 1,699
1
vote
2 answers

How to show that $f(x)=(x − 1)^3 + 2$ is surjective?

I need to show that the function is bijective. I already showed that it is injective but I struggle to show that it is surjective A function $F\colon X\to Y$ is called surjective, if for all $y$ belongs to $Y$, there exists an $x$ belongs to $X$…
Marinette
  • 29
1
vote
1 answer

prove that $|\{f|f:A\rightarrow \{0,1\}\}|=|P(A)|$

Let A be a set , prove that $|\{f|f:A\rightarrow \{0,1\}\}|=|P(A)|$ I tried to prove that $g:|\{f|f:A\rightarrow \{0,1\}\}|\rightarrow |P(A)|$ is one to one and onto but I didn't find the right function and I don't know how to find cardinality of…
alpha male
  • 79
1
vote
1 answer

What are the beginning steps to show this/ solve this?

The difference table for the sequence $a_0, a_1, a_2, a_3,\cdots$ is sequence $a_0$ $a_1$ $a_2$ $a_3$ $a_4$ $a_5$ $a_6$ ... first difference $b_0$ $b_1$ $b_2$ $b_3$ $b_4$ $b_5$ ... second…
Paul Steiner
  • 11
1
vote
0 answers

Combination in Divisors of Prime Numbers

Can anyone help me with this? Consider a positive natural number of the form $n=p_1^{a_1}\dots p_m^{a_m}$ where $p_1,\dots ,p_m$ are unique prime numbers and $a_1, \dots ,a_m \in \mathbb{N}$ a) How many unique divisors does $n$ have of the form…
JiSeung
  • 63
1
vote
2 answers

what result I should consider for GCD with polynomials?

I need to calculate the GCD of $$x^4+3x^3+2x^2+x+4 \ \text{and } x^3+3x+3 \ \text{in} \ \mathbb{Z}_5$$ Using Euclid algorithm: $$x^4+3x^3+2x^2+x+4 = (x^3+3x+3)(x+3)-3x\\ x^3+3x+3 = (-3x)(\frac{1}{3}x^2 - \frac{2}{3})+3 \\-3x = (3)(-x)+0 $$ Now I…
Loris Simonetti
  • 567
1
vote
1 answer

The total number of prime factors of this expression

The total number of prime factors of this number: $2^{22}$ x $7^5$ x $11^2$ Should be only 3, which are 2, 7 and 11 itself. However the answer states that there are total $(22+5+2) = 29$ prime factors. What? How?
Ruchi
  • 293
1
vote
1 answer

Math problem using cups..

I have the following question: Mike has 58 white cups and 198 green cups. He wants to place his cups in stacks by color so there are the same number in each stack and same color. What is the greatest number of cups he can place in each stack? How…
MethodManX
  • 1,127
1
vote
1 answer

Truth tables with $3$ rows of variables

$$\begin{array}{cccc} \textbf{X} &\textbf{Y} &\textbf{Z} & \textbf{A}\\ T & T & T & T\\ T & T & F & T\\ T& F& T& F\\ T& F& F& F\\ F& T& T& F\\ F& T& F& T\\ F& F& T& F\\ F& F& F& T\\ \end{array}$$ I'm fairly new to truth tables so…
sarem dave
  • 11
1
vote
0 answers

Find target string in a text using brute-force algorithm

Given the following brute-force algorithm to find target string $b_1, b_2,...,b_m$ in a text $a_1, a_2,...,a_n$ such that $m\le n$, Big-$O$ time complexity of the algorithm is as follows: If the entire text $a_1, a_2, ..., a_n$ does not contain…
Avv
  • 1,159
1 2 3
…
99 100