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

Countably Infinite, Uncountable or Finite

I am having trouble with the following terms: countably infinite, uncountable, and finite. In addition, for the following problems I need to select which category they fall into. $1)$ Consider a set of every function from integers to the set…
John Fda
  • 205
2
votes
1 answer

" only prime number that can only be divided by itself and one" logic

How do I write "only prime number that can only be divided by itself and one" and I can only use these predicates : H(x, y) is x/y=integer(x mod y=0), S(x, y) is x=y, and P(x) is x is prime number? My guess is : ∀x∀y(~S(x, 1)^(~S(x, y)^~S(y,1)→~H(x,…
Kevin Valiant
  • 23
2
votes
1 answer

Find count of subsets which have at least one even number

I have this set $S = \{1, 2, 3, ..., 30\}$ a I have to find count of subsets of subset $S$ which have at least one even number. I solved it that I substracted from total count of subsets ($2^{30}$) that subsets which have only odd numbers. Like…
Johny
  • 225
2
votes
2 answers

How many have there pairs of disjoint subsets of a set of $n$ elements?

-How many have there pairs of disjoint subsets of a set of $n$ elements? I did other assignments about pairs of subsets where one is a subset of the second, using functions similar to characteristic functions. But I dont have an idea about this…
Bozo Vulicevic
  • 2,836
2
votes
3 answers

Is it true that every positive integer is the sum of 18 fourth powers of integers? (No, but i don't understand given answer)

My question is actual at the bottom in bold and is about the logic the author uses. Is it true that every positive integer is the sum of 18 fourth powers of integers? This is a question form a discrete math book, not to worry the answer is detailed…
Drew Verlee
  • 195
  • 2
  • 7
2
votes
3 answers

How do I complete this proof?

Prove the following statement by contradiction: For each two positive integers $x$ and $y$, $x^2-y^2 \neq 1$ Proof: We use proof by contradiction. 1) Suppose $x^2-y^2 = 1$ 2) Assuming $x,y\in\mathbb{Z^+}$, let $x = \frac { a }{ b }$ and let…
nikolita
  • 125
2
votes
3 answers

How do I interpret the meaning of the following claims?

How do I interpret these claims in order to translate them into plain English. They seem a bit ambiguous in their meaning to me. $$1) \quad \forall x\in\mathbb{N}: \exists y\in\mathbb{N}: (x+y=0)$$ $$2) \quad \forall x\in\mathbb{Z}: \exists…
Cherry_Developer
  • 4,239
2
votes
2 answers

If (A − B) ∪ (B − A) = A ∪ B then A ∩ B = ∅

I just want to make sure I'm thinking of this correctly. From what I understand, this is basically saying that: If the union of everything in set A that's not in set B and everything that's in set B but not A = The union of A and B, then set A and B…
smitty werbenjagermanjensen
  • 161
2
votes
1 answer

How to write the truth table for a proposition and then determine its shortest possible equivalent expression?

$$(r\leftrightarrow \neg p)\wedge p\wedge (q\rightarrow \neg (p\oplus q))$$ Steps I took: I broke up the proposition into bits and pieces and assigned them to variables as such: $a=(p\oplus q)$, $b=(q\rightarrow \neg a)$, $c=(r\leftrightarrow \neg…
Cherry_Developer
  • 4,239
2
votes
1 answer

Is X a subset of the {X}?

I'm new to this website. I'm trying to understand the precise definition of a subset. In particular, this problem is tripping me up: True or False? $\{\emptyset, \{\emptyset\}\} \subseteq \{\{\emptyset, \{\emptyset\}\}\}$ I know that any set X is…
marukome_
  • 29
2
votes
0 answers

Translating set definition to English

The definition of the union set between two sets is: $$A \cup B = \{x | x\in A \lor x\in B\}$$ How do you say this in English? Do you say '$A \cup B$ is the set of all elements $x$, such that $x$ is an element of $A$ or $x$ is an element of $B$'?…
Carefullcars
  • 527
2
votes
1 answer

Find a recurrence relation for the sequence $u_n=$ number of nonnegative integral solutions of $2a+5b=n$.

Find a recurrence for the sequence $u_n=$ number of nonnegative integral solutions of $$2a+5b=n.$$ I think I can use a generating function, but I'm a bit confused at this point. Is anyone is able to give me a hint? I would like to solve the…
george
  • 39
2
votes
0 answers

Mutual friends at a game

At a tennis tournament, every group of $s$ participants shares exactly one common friend. Suppose player $Q$ has the largest number of friends. Determine how many friends $Q$ has. You must prove your answer. $s\in\Bbb N$ is a fixed but arbitrary…
user272379
2
votes
2 answers

what is the difference between well ordered set and totally ordered set?

I am unable to get the difference between a well ordered set and a totally ordered set ,I have gone through book , it says that if some non-empty subset of a poset has a least element then it is a well-ordered set but this least element can only be…
radhika
  • 361
2
votes
2 answers

Prove that there must be two distinct integers in $A$ whose sum is $104$.

Let A be any set of $20$ distinct integers chosen from the arithmetic progression ${1,4,7,...,100}$. Prove that there must be two distinct integers in $A$ whose sum is $104$. Define $A=\{1+3i\}_{i=0}^{33}$. I know that if two distinct integers…
user230283
1 2 3
…
99 100