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

All girls are liked by some boys. No boy likes a sulk. No girl is a sulk.

All girls are liked by some boys. No boy likes a sulk. No girl is a sulk. How do you write the above in predicate logic statements without starting with a negation? My guess is below. Let me know if you differ. ∀x ∃y girl(x) → boy(y) ∧…
goldilocks
  • 73
3
votes
2 answers

How do I show this predicate is true?

Given a while loop and a predicate, show that if the predicate is true before entry to the loop, then it is also true after exit from the loop. predicate: m^3 > n^2 while (m ≥ 0 and m ≤ 100) do m := 3 · m n := 5 · n end while I tried…
FredJacobs
  • 41
3
votes
0 answers

Plane coloring $\mathbb{R}^2$, $2$ colors per line

Is there a coloring of $3$ colors on $\mathbb{R}^2$ such that every line contains exactly $2$ (different) colors and there is no triangle with unit area whose vertices lie on $3$ different colors? All points have to be colored. All $3$ colors have…
Richard22
  • 43
3
votes
3 answers

$4^n - 1$ in base $2$

How would you answer this question. Write $4^n - 1$ in base $2$. Given the context of the question I assume that $n \in \mathbb{Z}$. I'm fine with converting regular numbers to and from different bases but I don't know what a sufficient answer to…
Vishaal Vageshwari
  • 33
  • 2
3
votes
1 answer

Prove that $(p\oplus q)\oplus r$ is logically equivalent to $p\oplus (q \oplus r)$

I am reviewing for my upcoming Discrete Mathematics class and I'm clueless on the aforementioned question. I've tried expounding the XOR operator in hopes of transforming the problem but still I cannot find the solution to the problem. The title is…
marshblocker
  • 115
3
votes
3 answers

Translate these English statements into Predicate Logic

Given: P(x) = "x is a clear explanation" Q(x) = "x is satisfactory" R(x) = "x is an excuse I need to translate a) Some clear explanations are satisfactory. b) No excuses are clear explanations. (All excuses are not clear explanations) I have a…
Zevias
  • 109
3
votes
3 answers

bit string question

The question originally asked for four consecutive $1$s; this is the question that two of the answers address. It was later changed to ask for five consecutive $1$s. How many bit strings of length $10$ contain either five consecutive $0$'s or five…
Sara Meyer
  • 101
3
votes
0 answers

Number of legal bracket expressions of length n

I am currently working on calculating the number of legal bracket expressions of length n, that is expressions like ()(()) But not like ()())( These are to be counted as an analogy for another problem. That is, imagine a chessboard of size n, with…
Alan Jones
  • 59
3
votes
2 answers

Prove that each integer n ≥ 12 is a sum of 4's and 5's using strong induction

So I've been given the following problem: Prove that each integer n ≥ 12 is a sum of 4's and 5's What I have so far: (Basis): n ≥ 12 Therefore, 12 ≤ 4(x) + 5(y) x = 3 | y = 0 12 ≤ 4(3) + 5(0) 12 ≤ 12 = Correct However, what I don't…
MathNoob
  • 91
3
votes
2 answers

proving if a number is prime or not using combinations

I am really confused on this problem. I am given that $p$ = prime number, $1 \leq k \leq p-1$, and am asked to show $\binom{p}{k}$ multiple of $p.$ How do I prove that $\binom{p}{k}$ is a multple of $p$?
jyuserersh
  • 391
  • 1
  • 6
  • 15
3
votes
2 answers

Prove that if $(a,b)=1$ then there exist some $m,n$ such that $a^m+b^n\equiv 1 ($mod $ab)$

Prove that if $(a,b)=1$ then there exist some $m,n$ such that $a^m+b^n\equiv 1\pmod {ab}$. Number $a$, $b$ are nature and positive number. Since $(a,b)=1$ then there some number $x$, $y\in \mathbb Z$ such that $ax+by=1$. Since $(a,b)=1$ then I can…
Marko Škorić
  • 1,271
3
votes
1 answer

What is the cardinality of the set {a, {a, {a}}}?

I think that the answer is 2, but I'm not 100% sure. If the answer isn't 2, could someone help lead me to the correct answer?
Sam Goodin
  • 47
3
votes
4 answers

Summation of natural numbers

How would you prove this without induction? Prove the following statement for a collection of natural numbers $$ x_1, x_2, . . . , x_n $$ and the set $$ I = \{1, 2, . . . , n\} $$ Statement : $$ (x_1 + x_2 + · · · + x_n) > \frac{n(n + 1)}{2} → (∃i…
Geralt
  • 313
3
votes
1 answer

How to correctly express a variable with two solutions?

Say we have $(x+1)(x+2) = 0$. So possible solutions of $x$ are $x=-1$, and $x=-2$; Would it be considered correct syntax to say "$x = -1, -2$" ?
plu
  • 215
  • 2
  • 7
3
votes
4 answers

Proving divisibility by $3$

For all integers $a$, there exists an integer $b$ so that $3 | a + b$ and $3 | 2a + b$. So far I have been able to find an integer $b$ that satisfies both of them separately, but not at the same time. (For the first one I have $b = 6-a$, and for the…
mil236
  • 41
1 2 3
…
99 100