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
4
votes
4 answers

proof by contradiction example

Any ideas on how I can use proof by contradiction to show that at least 3 of any 25 days chosen must fall in the same month of the year? I don't even understand the question.
user87274
4
votes
3 answers

Proving $(a → (b → c)) ∧ (∼ c) ≡ (a → ∼ b) ∧ (∼ c)$ confusion.

I have the following statement that I want to prove:$(a → (b → c)) ∧ (∼ c) ≡ (a → ∼ b) ∧ (∼ c)$ I think I can prove this using the law of equivalences, however I also noticed that both statements, the LHS and the RHS has a ∧ (∼ c) at the end. So is…
Probability_Sarah
  • 561
4
votes
2 answers

Prove that $\bigcup \{A,B \} = A \cup B$.

Prove that $\;\bigcup\big\{A,B\big\} = A \cup B$. I am trying to work on this problem here. But I just do not know where to start. So I know that the union of set {A,B} is {A,B}. And the union of Set A and B we also get {A,B} for any common…
SC10
  • 41
4
votes
4 answers

Prove $((P \cup Q) \cap (P \to R) \cap (Q \to R)) \to R $ is a Tautology

$[(P \cup Q) \cap (P \rightarrow R) \cap (\neg Q \cup R)] \rightarrow R $ Logical Equivalences. $[(P \cup Q) \cap (\neg P \cup R) \cap (\neg Q \cup R)] \rightarrow R$ Logical Equivalences. $\neg[(P \cup Q) \cap (\neg P \cup R) \cap (\neg Q \cup R)]…
SqualoredToad
  • 49
4
votes
2 answers

Prove that $f$ is Injective and Surjective: $f:N\times N \rightarrow N :f(m,n)= 2^{m-1}(2n-1)$

I`m trying to prove that $f$ is Injective and Surjective $$f:N\times N \rightarrow N :f(m,n)= 2^{m-1}(2n-1)$$ what I did so far is to set $m_{1},m_{2},n_{1},n_{2}$ so by definition of injective function if $f(x1)=f(x2) \rightarrow…
Ofir Attia
  • 3,136
4
votes
0 answers

How to get maximum sums from groups of numbers without exceeding a total?

This is an abstract computer code application that I'm trying to solve, but I think the following real life example kind of helps to illustrate the type of problem I'm working with. In this example, the first group contains railroad passenger cars.…
Timothy
  • 41
4
votes
1 answer

2n ambassador problem

I found this problem, from the book Problem-Solving Strategies by Engel. And I found they have solved it in a very elegant(read: complex) way for me to comprehend. On the contrary, I came up with a different (read: easier) proof. But there might be…
Alex
  • 557
4
votes
1 answer

Ordered "sums" of natural number k using natural number addends no smaller than 2

Using natural numbers no smaller than 2, we can express the number 3 as one ordered "sum": 3, and we can express the number 6 as 5 ordered "sums": 6 = 4 + 2 = 3 + 3 = 2 + 4 = 2 + 2 + 2. In how many ways can the number k be expressed as an ordered…
koisaucer
  • 121
4
votes
2 answers

Prove or disprove the statement: For all real numbers $x,y$, $⌊xy⌋=⌊x⌋⌈y⌉$. What's wrong with my counter example?

Prove or disprove the statement: For all real numbers $x,y$, $⌊xy⌋=⌊x⌋⌈y⌉$. I used the counter example $x = 1.9$, $y = 1.9$. $⌊1.9 \cdot 1.9⌋ = 3$ $⌊1.9⌋⌈1.9⌉ = (1)(2) = 2$ But the professor said that this statement was actually true and I got 0…
Xero
  • 59
4
votes
5 answers

Why is $\mathbb{R}-\mathbb{Q}$ an uncountable set and how can I prove it?

I am now starting to prepare for a discrete mathematics class. On a test, I came across the following question: Which of the following sets are countable? $$\mathbb{Z},\mathbb{R}, \mathbb{R-Q}, \{31,2,2019\} $$ The only countable sets are:…
average_discrete_math_enjoyer
  • 832
  • 5
  • 17
4
votes
6 answers

Prove that for any $n > 0$, if $a^n$ is even, then $a$ is even

the proof at hand is: Prove that for any $n > 0$, if $a^n$ is even, then $a$ is even. Hint: Contradiction So I know to start the problem in a contradiction format would be: $a^n$ is even, then $a$ is odd so that $a = 2k+1$. Then plug in that into…
sparky123
  • 73
4
votes
2 answers

Efficient homework grading: 3 graders, each HW needs to be graded by 2 people

No idea if this is a math problem, but it sounds like a problem that would have been covered in my discrete math class 4 years ago, which I remember very little about. This is a real life situation, not an assignment question: 3 people in a group.…
blindside044
  • 143
4
votes
4 answers

$x$ is rational, $\frac{x}{2}$ is rational, and $3x-1$ is rational are equivalent

How do we prove that the three statements below about the real number $x$ are equivalent? (i) $\displaystyle x$ is rational (ii) $\displaystyle \frac{x}{2}$ is rational (iii) $\displaystyle 3x-1$ is rational
Siamoka
  • 159
4
votes
3 answers

A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible...

A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible - So that he walks as far as possible from the first post he paints to the last post he paints. He can only turn around and go back the other way…
user65132
  • 287
4
votes
2 answers

Given $f:\Bbb N\to P(\Bbb N)$, present two sets of naturals not in the image of $f$.

Let $f: \Bbb N \to P(\Bbb N)$. Present 2 different sets of natural numbers A, B that are not in Im(f) What I did: First idea: I defined an injective function f that takes each n and returns it's singleton. Now each other member of $P(\Bbb N)$ which…
jreing
  • 3,297
1 2 3
…
99 100