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
1 answer

Given |x-y|≤2 ], proving |y-x|≤2

I'm given the following: If $|x-y|≤2$ then $|y-x|≤2$. How would I go about proving $|y-x|≤2$? The answer I came up with: If $|x-y|≤2$ then $|y-x|≤2$. By saying $|x-y|≤2$, we are saying that x and y are within 2 integer value places of one another,…
GainzNerd
  • 279
1
vote
3 answers

Proving a union of sets

How to prove: $\cup_n[\frac{1}{n},1] = (0,1]$, where $n \in \mathbb N $ The only thing I'm aware of is that we have to prove both left to right and right to left as I'm dealing with sets, and couldn't find a starting point. Can anyone help with…
Orvin
  • 15
1
vote
2 answers

Im have trouble with this question.

im having a bit of trouble with this problem and and how to go about it. show that: 2^n=O(n!) thanks
Chandler K Sharp
  • 39
1
vote
1 answer

What is the fewest number of testers needed to identify the poisoned wine?

The King has 1000 bottles of wine, exactly one of which is poisoned. Your job is to identify and throw out the poisoned bottle as quickly as possible by having the royal taste-testers drink the wines. Since the poison takes a little while to take…
Linux27
  • 19
1
vote
1 answer

Show that $\forall A,B\in P(S), f(A\cup B)=f(A)+f(B)−f(A\cap B)$

Let $S$ be a set and let $f$ be a function from $\mathcal P(S)$ to $\mathbb R$ such that for all $A,B\in\mathcal P(S)$ with $A\cap B=\emptyset$, $$f(A\cup B)=f(A)+f(B)$$ Show that for all $A,B\in\mathcal P(S)$, $$f(A\cup B)=f(A)+f(B)−f(A\cap…
Mahdi Klouz
  • 11
1
vote
1 answer

Cartesian product of a set and an interval

Lets assume we have following subsets of $\mathbb{R}$: $A = \lbrace 1,3 \rbrace , B=[-1,3], C = \lbrace 0, \frac{20}{7}, \frac{18}{5} \rbrace $ Let $M=A \times ( B \cap C )$ What is M written in enumeration? What i did so far: $B \cap C = [ 0,…
wolfffi
  • 29
1
vote
3 answers

Why is the Inductive Hypothesis assumed to be true?

The logic of the Inductive proof seems circular, the whole proof seems to hinge on whether or not the Inductive Hypothesis is true. Sure you can show that p(k+1) is true if p(k) is true, you have your instance of p(k) being true, and if p(k+1) is…
Andrew
  • 385
1
vote
1 answer

I am having trouble understanding the task for part B and how to prove it?

Let $X =\mathbb N$ . Say $(k, l) ∼\text{di}(m, n)$ if and only if $k + n = l + m$. Prove that $∼\text{di}$ is an equivalence relation on $X$. Prove that $\{(m, 1)|m ∈ \mathbb N\} ∪ \{(1, n)|n ∈ \mathbb N, n > 1\}$ is a complete set of…
V Harvey
  • 15
1
vote
1 answer

what is the number of 10 × 10 squares in the 100 × 100 image

I read and calculate the answer to be $(n - k + 1)^2$ in general (where $n=100$ and $k=10$ in the example). But have come across a paper where they use $90 \cdot 90$ - so I wanted to check with others on the answer. Thanks
javid912
  • 11
  • 1
1
vote
1 answer

solving equation using diagram venn

In a computer shop, there are $33$ PC set that are sold: with 18 sets of PC have crystal screen PC included, with 12 sets of PC have printer included, with 6 sets of PC have scanner system included, with 3 sets of PC that include all(printer,…
vedss
  • 343
1
vote
0 answers

How can I make a collection of sets where every pair of sets has exactly one element in common?

I've played around with this for a while and I've managed to make sets of size 1, 2, 3, 4, 5, 6, 8, and 12 elements where each set is of the same size and has only 1 element in common with every other set. For example, for sets of size 3, this is…
David
  • 11
  • 1
1
vote
2 answers

Union of intersections and intersection of unions

Would someone be able to help me understand the (concept of) "union of intersections" and the "intersection of unions". More specifically, how to approach (prove) the following equality of two sets $X$ and…
dpakasa
  • 125
1
vote
0 answers

How to know what is the right approach to a propositional argument?

I am fairly new to discrete mathematics. I came across a question where I have the following premises: $p \implies q$ $q \implies r$ $\neg r$ Based on the text, the answer is the following: $\neg q$ using Modus Tollens on 2, 3 $\neg p$ using…
Rahul Wadhwani
  • 111
1
vote
2 answers

Is this relation $R : (f,g) \in R$ on the set $\{f:\mathbb{R} \rightarrow \mathbb{R} \}$ partial order relation? And total order relation?

R is defined aas the relation on the set of all functions from $\mathbb{R}$ to $\mathbb{R}$. $$ R: (f,g) \in R \iff f(x) \leq g(x), x \in \mathbb{R}$$ The question is, is R a relation of partial order? If yes, is it a relation of total order? My…
Belen
  • 568
1
vote
2 answers

For what three sets $A,B,C$ is this equality true: $(A \cap B)\times(B\cup C) = (A\times B) \cup (A\times C) $?

For what three sets $A,B,C$ is this equality true: $(A \cap B)\times(B\cup C) = (A\times B) \cup (A\times C) $? Justify your answer. I've struggling with this for a while, but I'm quite lost. Could you help me out how to approach this type of…
S. V.
  • 15
1 2 3
…
99 100