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

Help with discrete math proof?

I am having trouble proving the following: If $x\in R$ and $x > 0$, then $x^4+1 \geq x^3+x$. Work: I tried to rearrange the equation as $x^4-x^3-x+1 \geq 1$, but that does not really help. I also tried proof by cases where case 1 would be that x is…
mrQWERTY
  • 595
2
votes
1 answer

Integer division problem

I'm trying to solve the following problem: For any positive integer $a$, find the least positive integer $n$ for which the formula below produces an integer result $$\frac {a-n}{2n+1}$$ except for the trivial solutions with $n$ being $0$ or…
Desmond Hume
  • 157
2
votes
3 answers

find the big oh for the function $f(n) =1+4+7+\cdots+(3n+1)$. Can someone explain why the answer is $n^2$

This is a review question and the teachers gave us the answer as $n^2$. Can someone explain why it is $n^2$? Thank you
hello
  • 79
2
votes
1 answer

Need help with Proof by Strong Induction question

So, here is the question: For any position integer $n$, let $T(n)$ be the number 1 if $n<4$ and the number $T(n-1) + T(n-2) + T(n-3)$ if $n \geq 4$. We have $T(1)=1, T(2)=2, T(3)=3$ $$T(4)=T(3)+T(2)+T(1) = 1+1+1+1 = 3$$ $$T(5) = T(4)+T(3)+T(2) =…
Mike Jones
  • 21
  • 1
2
votes
2 answers

Discrete Math on Cycles and Circuits

I'm not sure how to show that the graph G contains a cycle if the minimum degree delta ≥ 2 for the following question Show that if G is a graph with minimum degree ≥ 2, then G contains a cycle.
ali
  • 21
2
votes
2 answers

How is Pascal's Triangle Important?

Question: What are the uses of Pascal's Triangle? What are some interesting properties of Pascal's Triangle? I know that Pascal's Triangle has many uses, but I only know a few of them. I know that the binomial theorem is based on Pascal's…
Anonymous Computer
  • 5,639
2
votes
1 answer

how can i prove: $|P(\Bbb R)\times \Bbb R|=|P(\Bbb R)|$?

How can I prove that $|P(\Bbb R)\times \Bbb R|=|P(\Bbb R)|$? I can use the following statements: $$|A|<|P(A)| $$$$ |P(\Bbb N)|=|\Bbb R|$$$$ |\Bbb R\times\Bbb R|=|\Bbb R|$$$$ |\Bbb Z\times\Bbb Z|=|\Bbb Z|$$$$ |\Bbb Z|=|\Bbb N|=\aleph_0$$ I tried a…
daniel
  • 101
2
votes
2 answers

How to determine if a relation is a partial order, an equivalence relation, or none.

My understanding of relations is fair enough for now, however I am unsure how to determine the answer and provide a brief explanation. I can't say I am a fan (yet) of the notation used either. Here is an example taken from the homework: $$xRy…
user134768
  • 21
2
votes
0 answers

Discrete Math creating functions that map sets

contruct a simple one-to-one function from $Z^+ → P(Z^+)$ How would I approach this type of problem? I'm guessing from utilizing $F: Z^+ → P(Z^+)$ I'm guessing need to find some way to map all positive integers to the power set of all positive…
Snowyace
  • 37
2
votes
1 answer

boolean function

Let f = “she is out of work” and s = “she is spending more.” Write the following statements in symbolic form: 1. Neither is she out of work nor is she spending more. ANS : not f and not s is this answer corret if not can i please get help
nelson
  • 33
2
votes
2 answers

Proving or disproving if sets are equal

Does this mean we can ignore A because its a subset of B, so now were only dealing with B or C? So you substitute B or C with A. Am I right because that gives me the right answer. (C-C) and empty set = empty set or (B-b) and empty set = empty…
Roy Kesserwani
  • 383
2
votes
1 answer

Help with a proof using the Schröder-Bernstein theorem.

Suppose that $f$ is a function from $A$ to $B$, where $A$ and $B$ are finite sets with $|A|=|B|$. Show that $f$ is one-to-one if and only if it is onto. My prof. wants us to use the Schröder-Bernstein theorem to prove this. I am not really sure how…
user131264
  • 23
2
votes
1 answer

P(A) $\subset$ P(B) implies A $\subset $ B proof or disproof.

P(A) $\subset$ P(B) implies A $\subset $ B proof or disproof. I have a strange feeling this is false but I do not know. Something to do with P(A) $\subset$ P(B) seems strange since P(B) is itself a powerself with P(A) being a subset.
Adam Staples
  • 967
2
votes
1 answer

Find formula, which certain truth table

I have this truth table, and I must find the right formula. (T = TRUE , V = FALSE) Where should I start with this? I first wrote out everything : A&B&C&D v A&B&C&-D v -A&-B&C&-D etc... But then I was told, that I can solve this even easier. Any…
Jaanus
  • 145
2
votes
2 answers

Prove that $f(m,n)=(m+2n, m-n)$ is 1-1 and Onto. The domain and co-domain are $\mathbb R\times \mathbb R$

So I know how to prove injectivity $f(x)=f(y)\Rightarrow x=y$ and surjectivity but am not sure how to go about it in this case since there are multi variables.
atherton
  • 1,234
1 2 3
…
99 100