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

Find the smallest positive integer solution

Find the smallest positive integer solution (non-zero) for the following inequalities: $a_1
usr1092803564
  • 41
2
votes
1 answer

Multiplying sets

Is there simpler way of doing this problem? $$(\{1, 2, 3, 4, 5\} \times \{6, 7, 8, 9, 10\}) \cap (\{4, 6, 8, 9, 10\} \times\{2, 3, 5, 7, 11\})$$ I've been doing this problem and it's taking me a long time. How would I approach this problem? help me
Cami Maine
  • 21
2
votes
1 answer

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

I can't comment on this question A man has to paint n consecutive mile posts and wants to do this as inefficiently as possible... but I have further questions from this problem. Based on the most voted answer, "Now, if we wish to maximize this sum…
winter
  • 71
  • 2
2
votes
2 answers

Trying to understand recursive definitions in discrete math

Consider the recursive definition of the natural numbers: Basis: $0 \in \mathbb{N}$ Recursive step: if $n \in \mathbb{N}$ , then $s(n) \in \mathbb{N} $ Give recursive definitions of: $T_0$ the set of natural numbers that are divisible by…
user312739
  • 21
2
votes
2 answers

Prove that a planar graph has four coloring

There is a theorem which says that every planar graph can be colored with five colors. It can also be colored with four colors. How can I prove that any planar graph with max degree of $4$, has a four coloring? Can someone help me prove this?
user312732
  • 21
2
votes
1 answer

Determining Whether or not a graph is bipartition?

So I have been trying to do research on this online, and all I see are a bunch of graphs with multicolored dots, and telling me to use those to determine if the graph is bipartition. The ones in the book do not have no color to them, so everything…
Jebus Crust
  • 149
2
votes
2 answers

If $B= \{1, 2\}$ and $C = \{\{1,2\}\}$ what is $B \times C$?

I understand the basics of Cartesian products, but I'm not sure how to handle a set inside of a set like $C = \{\{1,2\}\}$. Do I simply include the set as an element, or do I break it down? If I use it as an element I think it would be something…
123
  • 807
2
votes
1 answer

Help finding Cardinality of two sets, and their interactions?

I'm trying to find the cardinality of the below: $$A = \left\{ x\in \mathbb{Z}: \bigg|\frac{3x^3 + x^2 - 2x + 4}{3x + 4}\bigg| \geq (2^{50} -1 ) \right\}$$ and the set $$B = \left\{ x\in \mathbb{Z}: \frac{3x^3 + x^2 - 2x + 4}{3x + 4} = 0…
dustyblade
  • 151
2
votes
1 answer

How to express logical equivalence arrow using Pierce's arrow?

I am really confused about this and not sure how to show $P\iff Q$ with the ↓ arrow and only the ↓ arrow. I understand that $P \iff Q$ is $P\implies Q$ and $Q\implies P$. I also know that $P\implies Q$ is also $\neg P$ or $Q$. If anyone can help…
Tarek Nabulsi
  • 39
  • 1
  • 4
2
votes
2 answers

How many ordered pairs (with limitations)?

having hard time with the following question: $$A = \{1,2,.....,n\}$$ How many ordered pairs $(B,C)$ which are members of $P(A) \times P(A)$ are there where $B\cap \overline{C}$ is the empty set?
Noam
  • 853
  • 4
  • 16
2
votes
2 answers

Notation for List where elements are members of a given Set

Is $(a, b, c, d) \in\mathbb{R}$ an adequate way to say to "a, b, c, d is a list of real numbers?" Or would it be better to say: Given list $(a,b,c,d)$ where $a,b,c,d \in\mathbb{R}$ ? I am pretty clear on set notation but my search on list notation…
jmxdbx
  • 51
2
votes
0 answers

Using definition of pre-image to prove $ X \subset f^{-1}(f(X)) $

I am trying to prove easy statements such as one listed here: http://mathworld.wolfram.com/Pre-Image.html My attempt: let $ x \in X$ then $f(x) \in f(X)$ so $x \in f^{-1}(f(X))$ but I am not really doing anything but looking at the definitions - how…
settheory
  • 31
2
votes
1 answer

Bound on number of rooks on an $n \times n$ board if empty squares share row or column with at least $n$ rooks

Rooks are place on a $n \times n$ chessboard satisfying the following condition: If the square $(i;j)$ is free, then at least $n$ rooks are on the $i$th row and $j$th column together. Show that there are at least $ n^2/2 $ rooks. Among these $2n$…
Sierra Res
  • 329
2
votes
2 answers

Example of a relation on $X$?

I can understand "relation $R$ in $X$" through the following example in the book, but I haven't got a clue of what "relation on $X$" looks like. Can you give an example of of a relation on $X$? "Often $A$ and $B$ are the same set, say $X$. In that…
buzzee
  • 1,530
2
votes
1 answer

Transitive Closure, $R =\{(0,0), (0,3), (1,0), (1,2), (2,0), (3,2)\}$

Let the relation $R = \{(0,0), (0,3), (1,0), (1,2), (2,0), (3,2)\}$ Find $R^*$ the transitive closure of $R$. Show all steps. For the following problem I have a question on the Transitive Closure. I know I have to add the following: $\{(0,2), (1,3),…
Vaughnjavier
  • 77
1 2 3
…
99 100