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

Double negation elimination rule

Can someone explain to me how the double negation of A is a premise for the negation of A? My understanding is this, if A is true then the double negation of A is A which is true, how is this a premise for negation of A? problem
Code971
  • 135
1
vote
2 answers

Surjectivity of an $\mathbb{N}^2$ to $\mathbb{N}$ function

(This is my first post on here - let me know if I need to edit anything.) I'm just starting an introductory topology course and I've come across a problem that I've been trying to solve for a few hours now. I'm supposed to prove the bijectivity of…
mathboy
  • 11
  • 1
1
vote
1 answer

Solving Recurrence Relation Denominator

Let $x_0 = 1, x_1 = \frac{1}{1+x_0}, x_2 = \frac{1}{1+x_1} \cdots x_n = \frac{1}{1+x_{n-1}}$ Find $\lim_{n\rightarrow \infty} x_n$ as $n$ approaches infinity. I don't know to represent this recurrence relation in a way that I can solve for $x_n$ and…
Uq'''12wn1F12u2x3uW31H1JBk9m
  • 199
1
vote
1 answer

Implication, propositional logic.

P: n is divided by 2. Q: n is an even number. Here n belongs to integer numbes only. How does it follow the truth table of 'if P then Q' ? In truth table, if truth value of P is false and Q is true then How the whole statement is true.
shashikant dwivedi
  • 13
  • 3
1
vote
2 answers

antisymmetric relation is when $a, b ∈ A$, if $(a, b) ∈ R$ and $(b, a) ∈ R$, then $a = b$ , is this a typo?

A relation $R$ on a set $A$ is called symmetric if$(b,a) ∈ R$ whenever $(a,b) ∈ R$,for all $a,b ∈ A$. A relation $R$ on a set $A$ such that for all $a, b ∈ A$, if $(a, b) ∈ R$ and $(b, a) ∈ R$, then $a = b$ is called antisymmetric. Shouldn't it be…
DSL
  • 1,359
1
vote
1 answer

what does $A\times B$ mean in this statement?

Recall that a function $f$ from a set $A$ to a set $B$ exactly one element of $B$ to each element of $A$. The graph of f is the set of ordered pairs $(a, b)$ such that $b=f(a)$. Because the graph of $f$ is a subset of $A\times B$, it is a relation…
DSL
  • 1,359
1
vote
2 answers

A binomial identity from counting permutations with cycles of length two.

Let $n\ge 1$ be an integer. Consider the following sequence: where $\left\{l_j\right\}_{j=1}^n$ are indices.By analyzing all possible decompositions of the sequence above into distinct pairs we have discovered the following…
Przemo
  • 11,331
1
vote
1 answer

simplification help

I'm unsure on how this simplifies. Could anyone explain how and what technique is used to produce the answer? Any help would be most appreciated. $$ (n+1)(n+1)!+(n+1)!−1 \\ = (n + 1)!((n + 1) + 1) − 1 \\ = (n + 1)!(n + 2) − 1 $$
Bradley
  • 17
  • 6
1
vote
2 answers

How to solve $\{ k \in \mathbb Z /266\mathbb Z \;\lvert\; 217k \equiv 210 \bmod 266 \}$

How to solve $\{ k \in \mathbb Z /266\mathbb Z \;\lvert\; 217k \equiv 210 \bmod 266 \}$ ? Question: Since $217$ is not invertible in $266$ how can I solve the equation? Usually I would multiply $210$ by $217^{-1}$ mod $266$. I appreciate every…
jublikon
  • 943
1
vote
2 answers

how to solve $min\{x \in \mathbb N_0 \quad |x \cdot 714\quad mod \quad 1972 \quad = \quad 1292 \quad mod \quad 1972 \} $ (modulo equation)

Question: How can I solve: $min\{x \in \mathbb N_0 \quad |x \cdot 714 \equiv 1292 \mod 1972 \} $ ? I only know about: $x \cdot a \equiv _m b \Rightarrow m|x \cdot a - b$ different way of notation: $min\{x \in \mathbb N_0 \quad | x \cdot 714…
jublikon
  • 943
1
vote
6 answers

Find ALL solutions to $23x + 13y = 275$ when $x,y \ge 0$

Find ALL solutions to $23x + 13y = 275$ when $x,y \in \Bbb N$. How can I approach this exercise? do I need to use GCD? I got to $y = 23k + 16, x = 13t + 4$, when $k,t \in \Bbb Z$
Ilan Aizelman WS
  • 4,128
1
vote
3 answers

Discrete Math: Compound Propostions

So this is another practice problem I have for discrete math, this time involving compound propositions, with the book my campus uses is Discrete Mathematics with Applications, 7th Edition by Ken Rosen. The problem goes "Let p and q be two given…
009
  • 125
1
vote
0 answers

Find all possible a and b for which α is nonempty

Let $a$ and $b$ be two integers. The relation $\alpha\subseteq \mathbb{Z}\times\mathbb{Z}$ is defined by $x \alpha y$ if and only if $аx+by=1$. Find all possible $a$ and $b$ for which $α$ is nonempty. For all $а$ and $b$ proof existence or absence…
Filip Markoski
  • 369
1
vote
3 answers

discrete mathematics notes possibilities problem

In how many ways you can put two similar notes in a bag, so on each one there is a password of 6 letters (abc..z). I am having trouble with it. My way of thinking: On the first note: 26^6 On the second note: it is the same thing, but i may have…
sheldonzy
  • 667
1
vote
0 answers

How do you solve for x in an equation with 'Ceiling'

I have this equation $ Ceiling[(r + x) - z (r + x)] - ((r + x) - z (r + x)) = x$ I'm trying to solve for the value of $x$, but I'm not sure how to do this since $x $is also inside the Ceiling function. Is there a way I can find the value of $x$…
Akshat
  • 119
1 2 3
…
99
100