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

Prove that there exists irrational numbers p and q such that $p^{q}$ is rational

I found this on the lecture slides of my Discrete Mathematics module today. I think they quote the theorems mostly from the Susanna S.Epp Discrete Mathematics with Applications 4th edition. Here's the proof: We know from Theorem 4.7.1(Epp) that…
Prashin Jeevaganth
  • 381
3
votes
1 answer

What is the mathematics of UML?

What is the mathematics of Unified Modeling Language (UML)? The concepts introduced in UML such as classes, associations, association classes, subclasses smell mathematical. Is there a mathematical foundation or theory behind it?
qazwsx
  • 562
3
votes
4 answers

Showing tautology ((q and(p implies ~q)) implies ~p)

Im having difficulty with this. Ive been able to go from ((q and(p implies ~q)) implies ~p) to ~(~p and q) or ~p Not sure whats next. Can I get some help please.
Deniz Cetinalp
  • 829
3
votes
3 answers

Need help finding maximum unpayable amount between two coins of values 5 and 7, and understanding why.

I am currently taking in introduction course to Discrete mathematics, and came across this problem: Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay…
Brandonbury
  • 31
3
votes
1 answer

How to count number of integer solutions of this inequality $(x - 1)^2 + (y - 2)^2 + (z - 3)^2\leqslant 81$?

I have inequality $$(x - 1)^2 + (y - 2)^2 + (z - 3)^2 \leqslant 81$$ and want to count all number of integer solutions. I tried $$(x - 1)^2 \leqslant 81 \Leftrightarrow -8\leqslant x\leqslant 10,$$ $$(y - 2)^2 \leqslant 81 \Leftrightarrow…
minhthien_2016
  • 724
3
votes
1 answer

Explain why the following are true for arbitrary statements P and Q:

Explain why the following are true for arbitrary statements P and Q: If P is a tautology then (P or Q) ≡ P
user8322
3
votes
1 answer

1 to 27 - Guess my number

Each of four people wear a hat with a distinct positive integer $<28$. Everyone can see everyone’s number except his own. At 12:00 pm everyone can say something: either “Red” or “Yellow” or nothing. After 12:00 everyone must know his own number. How…
user173628192
  • 1,506
3
votes
5 answers

Using Proof by Contradiction

Use a proof by contradiction to show that if $n^3 + 1$ is odd, then $n$ is even for all integer $n$. Given: $n^3 + 1$ is odd Assume: $n$ is not even I'm not sure where to go from here to prove this by contradiction.
Jacob McCullough
  • 35
3
votes
3 answers

Solve $2x\equiv 18\ (\operatorname{mod} 50)$

How can we solve $2x\equiv 18\ (\operatorname{mod} 50)$? I'm not sure what to do when the item being modded on the right is not $1$.
Doug Smith
  • 1,015
3
votes
2 answers

Find a Transitive closure on the relation R

Find the transitive closure of $R=\{(a,b),(b,a),(b,c),(c,d),(c,e)\}$ I got the $R \circ R =\{(a,a),(a,c),(b,b),(b,d),(b,e)\}=R^2$
user420309
3
votes
3 answers

How to convert a summation into a closed form

I stumbled upon two problems that I solved in an exam a while ago; however, the only reason why I solved them was through trial and error by picking each choice from the choices available, I set an upper limit and compared the two values from the…
S.Riyadh
  • 63
3
votes
3 answers

How do we solve for a

$a = (5^4\ (\text{mod}\ 7))^3\ (\text{mod}\ 13)$ I know that I have to evaluate $5^4\ (\text{mod}\ 7)$ first, but how do you do that without using a calc? then I have to evaluate $x^3\ (\text{mod}\ 13)$. Any tip?
PopularScience
  • 131
  • 1
  • 2
  • 5
3
votes
2 answers

Is this equation known?

When I was trying to prove a relation from solid state physics, I reached this mathematical problem. In the equation $$\sum_{i=1}^Nm_ix_i=n$$ $m_i$ and $n$ are known integers, $N=3$, and $x_i$ are unknown integers. Also we know that the greatest…
apadana
  • 191
3
votes
5 answers

Find smallest number m such that $9^{32} + 19^{433} + m$ is divisible by $4$

We went over this in class awhile ago, but I can't seem to figure out how to solve it. Obviously you can do it exhaustively with a supercomputer, but that doesn't seem practical when I know there's a simplistic way to solve it.
Doug Smith
  • 1,015
3
votes
1 answer

Explicit form for $f(n) = 6f(n-1) - 12f(n-2) + 8f(n-3)$ for $n \ge 3, f(0) = 1, f(1) = 0, f(2) = 1$

Given the recursion $f(n) = 6f(n-1) - 12f(n-2) + 8f(n-3)$ for $n \ge 3, f(0) = 1, f(1) = 0, f(2) = 1$, find an explicit form for $f(n)$. I already solved this excercise in the past, but the solutions I received didn't involve fractions (as they do…
Julian
  • 1,401
1 2 3
…
99 100