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

Is {{∅}} ⊂ {{∅},{∅}} true

Is {{∅}} ⊂ {{∅},{∅}} true or false. I can't decide if this question is true or false. It seems to be false as the sets would be equal? is that correct since an proper subset isn't equal. the ⊂ in this means proper subset, the answer is false thanks…
Collin McCabe
  • 23
2
votes
1 answer

Proving properties of a sequence

I just received my first assignment for a mathematical proofs course I am taking this year. We just began the course, and we have so far only covered examples of proofs (how to prove if-then statements in different ways) and the mathematical…
user41419
2
votes
2 answers

Prove a formula is corect

I am trying to figure out this discrete math problem. I am not sure how to do it or even how to really start it. The problem is as follows: Consider values of $\frac{\sum_{i=1}^n i^2}{\sum_{i=1}^n i}$ for several small values of n. What formula…
Michael Guantonio
  • 173
2
votes
1 answer

A discrete maths problem on $2$ sets

We have $2$ sets, $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$ with $a_i, b_j\in\mathbb{Z}$. Is there any condition on elements of $A$ and $B$ that yield $A+B=\{a_i+b_j| i,j \in\{1,2,3\}\}$ or $A.B=\{a_i.b_j| i,j \in\{1,2,3\}\}$ have $3$ distinct…
Vahid
2
votes
2 answers

Are proofs by contradiction and counterexample two different techniques?

New to proofs. Suppose I want to prove $f: \mathbb Z \to \mathbb Z$ as $f(n) = 2n$ for all $n$ is not onto. Are the two arguments below valid, separate proofs? Are they invalid iterations of a single proof? By contradiction: Suppose $f$ is onto.…
user366786
  • 37
2
votes
2 answers

Suppose the alphabet consists of just {a,b,c,d,e}. How many 4-letter strings are there that do not have “aa” in the middle?

Suppose the alphabet consists of just {a,b,c,d,e}. How many 4-letter strings are there that do not have “aa” in the middle? I so far answered: We assume that a word could have multiple same letters. Since the word is only four letters, a can not be…
Dan Marchisella
  • 61
2
votes
1 answer

How many strings contain the words...

Good day My question is as follows Suppose the alphabet consists of ${A,B,C,D,E,F}$ (1) How many $4$-letter strings contain the word $“ACE”$? (2) How many $4$-letter strings don’t have $“F”$ in the first position and $“E”$ in the last position? (3)…
Dan Marchisella
  • 61
2
votes
2 answers

Why is pi used to represent prime numbers here?

I've just begun the "Concrete Mathematics" book by Knuth et al. In the first section about sums (and I apologise if this is really trivial, but I'm new and struggling a little); and they show this as one of the examples: $\sum_{k = 1}^{\pi(N)} …
yoonsi
  • 279
2
votes
2 answers

Negation of "some" logic statement

I need to negate the following statement : "Some integers are not odd" I have the below, where O(x) is "odd" $$ \exists x (\neg O(x)) $$ Would the negation be $$ \forall x (O(x)) $$ I'm confused, since if so, this statement does not make sense…
splinks
  • 157
2
votes
2 answers

$x + y = y + x$ is not a statement in Discrete Mathematics?

I was reading my notes and i noticed something a little unusual. How is $$x + y = y + x$$ not a statement? The reason that was given in the notes was "we don't know what $x$ and $y$ are, so they are not a statement. In Mathematics, $x$ and $y$…
Bryan
  • 319
2
votes
2 answers

Enumerate elements of the following relations from the set A

Literally the first homework question, and I seem to be struggling. There doesn't seem to be any examples in our book, so I'm hoping someone might help walk me through it. I'm guessing it's pretty simple too... I'm not looking for the answer, I'd…
Rickybobby
  • 367
2
votes
4 answers

Simplifying number of sets in a relationship

Got this monster set ((A∩B) ∪C ) ∪ (A∪(B∩C)) I'm trying to reduce the number of sets to be as small as possible using set identities Set Rules All I can think of is to apply distribution law ((C∪A) ∩ (C∪B) ∪ (A∪B) ∩ (A∪C)) Maybe I could play around…
Simon Kawa
  • 21
  • 1
2
votes
2 answers

Write the expression(I don't know understand the question)

Write the expression (p^ ~q) ^ r, using only the operators v and ~. The question meant the ^ operator with v operator?
sudl
  • 55
2
votes
7 answers

$x$ is odd if and only if $3x+6$ is odd

Prove the following proposition. Let $x\in\Bbb Z$. Then $x$ is odd if and only if $3x+6$ is odd. I'm currently not seeing a way to transform $3x+6$ into the format of $2k+1$ in order to prove odd. This is my first time dealing with discrete…
Andy C
  • 41
2
votes
2 answers

logical equivalence statements in discrete math

Construct another English form sentence, which is logically equivalent to that which was given. "Susan goes to school or Susan does not talk on the phone or Susan does not go to school."
Mike Shasaco
  • 31
1 2 3
…
99 100