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

Converting compound statements to Conjunctive Normal Form

$\newcommand{\tt}{\text{t}}\newcommand{\ff}{\text{f}}$Given a compound statement how do we convert it to conjunctive normal form? I have no idea where to begin. a) $$(r\to \lnot p)\land(q\to \lnot r) :CNF=?$$ b) Find the value of this statement when…
Sc4r
  • 639
1
vote
3 answers

Proving n is a multiple of 3 if and only if 2n is a multiple of 3

I want to prove that for all natural numbers $n$, $n$ n is a multiple of 3 if and only if $2n$ is a multiple of 3. I started by writing: $$x\equiv n=3k$$ $$y\equiv 2n=3k'$$ (where $k$ and $k'$ is any integer) Since we want to prove $x\iff y$, it can…
Bob Shannon
  • 1,561
1
vote
1 answer

Discrete math help w/propsitions

How would I be able to write the proposition -2n+1 is divisible by 5 if and only if 3n-4 is divisible by 5?
Stranger12345
  • 11
1
vote
2 answers

How would I get this number in base -3?

I want to find 4655 in base -3. Does this mean I would first find it in base 10 or is that already in that? In that case I have tried to find out what it is and I got this as my number "-64". Is my number correct or did I get the wrong one?
James C.
  • 21
1
vote
0 answers

Recurrence relation

Okay, I have the following problem: Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one, two, or three stairs at a time? And I basically have no idea how to do it, so I looked up the…
FrostyStraw
  • 1,045
1
vote
4 answers

How would I express this as a linear combination?

I want to express 1 as a linear combination of 51781 and 4655. I have a lot of other problems that consist of finding a linear combination but I just need to know do one so then I will be able to do them all. What steps do I need to take to…
James C.
  • 21
1
vote
3 answers

If $n\in\Bbb N$, then gcd($8n+1, 7n+1)$ =

If $n\in\Bbb N$, then gcd($8n+1, 7n+1)$ = How to do these type of questions?
user109886
  • 498
  • 1
  • 6
  • 12
1
vote
3 answers

How would I show this problem through mathematical induction?

I am trying to learn a lot of this on my own but I have never tried proving something through mathematical induction. Here is the problem below. $$1+3+3^2 + \cdots + 3^n = \frac{3^{(n+1)}-1}{2}$$ for all $n\in\mathbb{N}_0$, using mathematical…
Carl T.
  • 11
1
vote
3 answers

If sum of $N$ natural numbers is less than $N+2$ then each of these numbers is less than $3$.

Prove by contradiction. If sum of $N$ natural numbers is less than $N+2$ then each of these numbers is less than $3$. Attempt: Assume if the sum of $N$ natural numbers is less than $N+2$ then each of these numbers is greater than $3$. Let $x$ be…
user109886
  • 498
  • 1
  • 6
  • 12
1
vote
4 answers

Prove that $R$ is an equivalence relation.

Define the following $R$ on the set of integers $\Bbb{Z}$ $(a,b) \in R$ if and only if $3a + 5b$ is divisible by $8$ Prove that $R$ is an equivalence relation. Attempt: Reflexive: a~a if and only if $3a+5a$ is divisible by 8 Since $3a+5a = 8a$ is…
John
  • 99
  • 1
  • 6
1
vote
3 answers

Prove, by induction, that $5^n + 5 < 5^{n+1}$ for all $n\in\Bbb N$.

Prove, by induction, that $5^n + 5 < 5^{n+1}$ for all $n\in\Bbb N$. Attempt: If $n = 1$, then $5^1 + 5 < 5^{2}$ => $10 < 25$ which is a true statement so the base case holds. Assume $5^k + 5 < 5^{k+1}$ is true for some $k\in\Bbb N$. How to prove it…
user109886
  • 498
  • 1
  • 6
  • 12
1
vote
2 answers

Give a recursive definition

Give a recursive definition of a) The set of odd positive integers. b) The set of positive integers powers of 3. Solution for a) $ a^0 =1$ $ a^n = 2n+1 $ Is that right ? and how can i find b) ?
Out Of Bounds
  • 1,531
1
vote
1 answer

Find all integer solutions. (REVISION)

Find all integer solutions to $70x$ + $28y$ = $518$ Attempt: By reducing the equation we get, $5x$ + $2y$ = $37$ Since, $5(9) + 2(-4) = 37$ So, solutions are $(x,y) = (9,-4)$ And gcd(2,5) is 1 The full set of integer solutions is: $(x,y):x = 9-4k…
user109886
  • 498
  • 1
  • 6
  • 12
1
vote
0 answers

Find the number of distinct 6-tuples of integers with constant sum

(a) How many distinct 6-tuples of positive integers (a1,...,a6) are there such that a1+...+a6 = 14? (b) How many distinct 6-tuples of nonnegative integers (a1,...,a6) are there such that a1+...+a6 = 14? I'm thinking the only difference between (a)…
user3003255
  • 107
  • 1
  • 1
  • 4
1
vote
1 answer

How to find minimal and maximal elements of set K?

Let's say I have a set K which are a set of positive integers of the divisors of 180. I want to find the minimal and maximal elements of this set. A maximal element means that there is no element smaller than it within the set and a minimal element…
Jerry
  • 21
1 2 3
…
99 100