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

Unable to understand this lemma

The lemma is from the book Discrete Mathematics for computer scientists and mathematicians by Joe L Mott, Abraham Kendal, and Theodore P Baker Suppose $x$ and $m$ are positive integers and $r$ is the smallest positive integer for which there exist…
Aditya
  • 6,191
1
vote
0 answers

Term for a function from ℕ to ℕ where every element of the codomain is hit infinitely many times?

The sequence A000120 is a familiar example of such a function. For other examples, see the answers to this question: Existence of a sequence that has every element of $\mathbb N$ infinite number of times
firstname gklsodascb
  • 65
1
vote
1 answer

In Rosen's Discrete Maths text the example propositions seem the same as proposition functions?

Very noob to math and stackexchange: Example propositions given in Rosen's Discrete Maths textbook, such as a. "It is raining today"; or b. "Today is Thursday" - Can't they be considered as propositional functions themselves: If $x$ is a variable…
ramiah ariya
  • 25
1
vote
1 answer

Convert the following statements into predicate logic.

G(x) x has a portal gun R(x) x is a rick M(x) x is a Morty Convert the following statements into predicate logic. 1.) There is a Rick. 2.) Everything is a Morty 3.) No morty has a portal gun How do I even start this? I've watched some videos and it…
AzuraCF
  • 11
1
vote
2 answers

Why the one-on-one implies $\kappa<2^\kappa$ and $|S|=\kappa\implies |\mathcal{P}(S)|=2^\kappa$?

Let $S=\{a_1,a_2,a_3,\cdots,a_n\}$. The number of functions from $S$ to $\{0,1\}$ is just $2^n$, since each input of the $a_i$ can have 2 choice of output. Recall that the number of subsets of a finite set with cardinal number $n$ is just $2^n$.…
鈴木悠真
  • 387
  • 1
  • 8
1
vote
3 answers

Evaluating $\sum_{i=1}^n\sum_{j=1}^n(i+j)$

I am trying to self teach myself discrete maths and I am unable to solve this double summation for a closed form. Would really appreciate if someone help me understand the next step. $$\sum_{i=1}^n\sum_{j=1}^n(i+j)$$ What I have tried: I have…
Furrukh Jamal
  • 49
1
vote
0 answers

Inverted pairing function without square root.

I've given a pairing function c = (x+y)(x+y) + x and asked to make fst and snd functions which return x and y, if c is given. Values x,y,c are non-negative integers: 0,1,2,3... The problem is, that I'm currently working with plus and multiply…
nutella_eater
  • 43
1
vote
2 answers

Proving a simple property of Floor function

I have to prove the following property of Floor function: For any real number $x$, $x$ not being an integer, $\lfloor x \rfloor + \lfloor -x \rfloor = -1$. Now, we know from the definition of floor that $\lfloor x \rfloor$ is the unique integer…
ankush981
  • 2,033
1
vote
2 answers

Cartesian Product of non-rectangular region

I know that the Cartesian product $[0,1]\times[0,1]$ represents a unit square in the first quadrant. Is it possible to write the triangular region with vertices $(0,0)$, $(0,1)$ and $(1,1)$, interior included, as a Cartesian product o two sets? I…
user210190
  • 147
1
vote
1 answer

How to express symbolically "C and B have at least one element in common"?

Is this correct? If it is, is there a better way to write it? $C\cap B≠\{Ø\}$
Anonymous
  • 13
1
vote
1 answer

Is my inference reasoning correct here?

I'm trying to prove this argument is valid: Hypotheses: $(p$ or $q)$ implies $r$ not $r$ $q$ Conclusion: not $p$ I used modus tollens on steps 1 and 2 to get not $(p$ or $q).$ Then I distributed the not sign using De Morgans law to get not $p$…
Alex S.
  • 43
  • 1
  • 4
1
vote
0 answers

Euler diagram and min-terms graph

I learned about Euler diagram just this week. It brought me some thoughts about boolean algebra when I saw this figure. Given an Euler diagram representation, it is possible to establish a interconnection graph between min-terms (the modern term for…
Bruno Peixoto
  • 21
1
vote
0 answers

Find $n$th integer which does not contain any repeating digit sequence

The integers $61231239$, $30302$, and $55$ contain sequences of digits that repeat ($123$, $30$, and $5$). In a given base, I want to filter out integers with repeating digit sequences from the set of non-negative integers and find the $n$th integer…
Tomas Langkaas
  • 163
1
vote
1 answer

Fermat's little theorem to calculate $x·y^z \bmod p$

How do I calculate $$ 25·41^{16} \bmod 17 $$ using Fermat's little theorem? More specifically, how do I find an $x$ such that $$ x \equiv 25·41^{16}\bmod 17 $$ One part of Fermat's theorem states that, if $p$ is a prime number and $a$ is an integer…
human bean
  • 113
1
vote
0 answers

Discrete Math - Countable Sets

Here's the problem: Let A be the set of infinite-length binary strings that have a finite number of 1s. For example, the string 001110101011110000100110000000000... has all 0s after the twelfth 1 and thus is an element of A. Is the set of A…
mathtase
  • 45
1 2 3
…
99 100