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

Proving Bijections

i'm working on this question here but I am having some trouble: $f: ℝ ⇒ ℝ$, $f(x) = x^3 - 6x$. A) Is $f(x)$ injective? B) Is $f(x)$ surjective? C) Is $f(x)$ bijective? My attempted solution: A) $f(x)$ is injective if and only if $f(x) = f(y)$ $⇒$ $x…
M.G
  • 133
2
votes
2 answers

Modulo: Calculate really large numbers without a calculator

working on a task: "Recall that $a \equiv b~[n]$ means that there exists an integer $k$ suck that $b = a + k \cdot n$. Are the following claims true or false? 5.a) $3 \equiv 5~[10]$ 5.b) $4 \equiv 44~[10]$ 5.c) $298709869876987655 \equiv…
Christian Iversen
  • 93
2
votes
1 answer

"Exactly one person" quantifier

How do I translate the following English sentences without Uniqueness Quantifier: There is exactly one person who hates everyone All people hates exactly one person.
HoneyBee
  • 29
2
votes
4 answers

Disprove this number that exists in the integers.

$\exists n\in \mathbb{Z}, n^{2}
ComputerScience1994
  • 103
2
votes
0 answers

How can I verify logical equivalence without using Truth Table?

I have an assignment and I need to prove the following logical equivalence using Laws of Logic and not using Truth Table: p → q ≡ ~q → ~p LAWS OF LOGIC: 1.Commutative Law: p ↔ q ≡ q ↔ p 2.Implication Laws: p →q ≡ ~p ∨ q ≡ ~(p ∧ ~q) 3.Exportation…
Khubaib Khawar
  • 87
2
votes
1 answer

what are transitivity reflexive symmetry, Reflexive closure?

I have seen these and honestly I did not understand what does they do, what is useful or important about them? I always confused at seeing them. can someone point a source with good real world examples or give some explanation here? what is the …
alim
  • 207
2
votes
3 answers

The absolute value of a sum of two numbers is less than or equal to the sum of the absolute values of two numbers

I am trying to prove (or this could be false) that $|x+y| \leq |x| + |y|$
op_finales
  • 199
2
votes
1 answer

Suppose S = {1,2,3,4}. How many different subsets are there of S?

Given: $S=\{1,2,3,4,5,6,7\}$ How many subsets of $S$ are there which have more than one element? I know that there are $2^7=128$ subsets of $S$. Now, if we take into account the empty set, then shouldn't there be $2^7-8=120$ subsets of $S$ that…
user3727648
  • 183
2
votes
1 answer

Simplify $\sum_{k=0}^n (-1)^k {{n}\choose{ k}} {{k}\choose{ j}}$

I have to simplify $\sum_{k=0}^n (-1)^k {{n}\choose{ k}} {{k}\choose{ j}}$. I found following identity which might be useful $(-1)^i{{x}\choose{ i}} = {{i - 1 - x}\choose{ i}}$ [but I don't know how it's possible since $i - 1 - x$ is negative].…
halex
  • 91
2
votes
1 answer

set theory maths please help

$\Bbb N$ is the set of natural numbers $\Bbb N=\{0,1,2,\dots\}$ . For every $n\in\Bbb N$, let $A_n = \{ x\in \Bbb N \,\vert\, 0\leq x \leq n\}$. Prove or Disprove the following: $$\forall_{n \in \Bbb N}, \forall_{m \in \Bbb N}, (A_m = \{x^2 \,|\,…
sivsi
  • 31
2
votes
2 answers

Show that R is an equivalence relation on set of integers.

x,y into a Z (set of integers) and x related y if and only if x-y is a multiple of 3. Show that R is an equivalence relation on Z (set of integers). I need to show proof. I don't know how to prove Transitivity. This is what I have done but don't…
user3023185
  • 75
2
votes
0 answers

Pigeon Hole Principle about two disjoint non empty sets

Prove that for every subset S of {1,2, ..., n} having size 6, there are 2 disjoint non empty subsets of S having the same sum
J. Guil
  • 21
2
votes
1 answer

Relations on a set. Discrete Mathematics.

just want to verify that my understanding of relations is correct, grammar and correct logical form. Thanks! Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where $(a, b) \in…
javaderek
  • 37
2
votes
2 answers

Let n be an arbitrary odd natural number. Prove that $n^2≡1$ (mod4)

Let n be an arbitrary odd natural number. Prove that $n^2≡1$ (mod4) I know that this is true, but I'm not exactly sure how to write the proof for it. I found out then when you square any odd number, it will end in a 1,5,or 9, which I think is…
Cantwait428
  • 45
2
votes
1 answer

Prove that if m and n are any two odd (integers) then mn is also odd.

Here is what i have so far By definition an integer is called odd if there exist an integer k such that n=2k+1 so if n and m are any two odd integers the product of those two integers is odd. I dont know is this is the correct way of proving that mn…
Phillip Mc
  • 159
1 2 3
…
99 100