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

How many 6 letter words can be made in English with at most 2 vowels?

How many 6 letter words can be made in English with at most 2 vowels?
Mia
  • 31
3
votes
1 answer

Evaluate $\lfloor \frac{x}{m} \rfloor + \lfloor \frac{x+1}{m} \rfloor + \dots + \lfloor \frac{x+m-1}{m} \rfloor $

For any $x \in \mathbb{R}$ and $m \in \mathbb{N} $ evaluate $\lfloor \frac{x}{m} \rfloor + \lfloor \frac{x+1}{m} \rfloor + \dots + \lfloor \frac{x+m-1}{m} \rfloor $. Well if $x=m$ then we obviously have $\lfloor \frac{x}{m} \rfloor + \lfloor …
Arek Krawczyk
  • 2,114
3
votes
0 answers

Number of non-decreasing functions of n boolean variables

If f(a) is greater than or equal to f(b) for two domain elements a,b in X^n {0,1} whenever the number of 1's in a is greater than or equal to the number of 1's in b, that function is called a non-decreasing boolean function. How many non-decreasing…
Adam Cart
  • 43
3
votes
4 answers

Why if $x^2$ is divisible by two then $x$ is divisible by $2$?

In the proof for "$\sqrt2$ is irrational" one of the steps goes like this: $a^2 = 2b^2$ From this we conclude that $a^2 \equiv 0 \mod 2 $ We don't stop here and infer that $a \equiv 0 \mod 2$ implying $a^2 \equiv 0 \mod 4$ How can we make that…
Rire1979
  • 409
3
votes
2 answers

Discrete Math Question with "all" and "except"

I came across this question on an exam and am not sure why I am wrong. The question: Using the following predicates over the domain of people: $$A(x) = \text{x is an American.}$$ $$B(x) = \text{x likes Burgers.}$$ $$H(x) = \text{x likes Hot…
Jackson
  • 49
3
votes
4 answers

Direct proof of a contraposition

If the product of two integers is not divisible by some integer $n$, then neither integer is divisible by $n$. $Q1$. State the contrapositive statement: $A1$. If either $a$ or $b$ is divisible by $n$ then $ab$ is divisible by $n$. $Q2$. Do a direct…
Chris
  • 35
3
votes
5 answers

Prove: For any integer $n$, if $n^3+5$ is even, then $n$ is odd.

Is this proof good? Proof: This will be proven by contrapositive. Let $n$ belong to all integers such that $n$ is even. Then $n=2k$ where $k \in \mathbb Z$ Thus $n^3+5=(2k)^3+5$ which is odd.
Chris A
  • 39
3
votes
1 answer

An algorithm that always reach the number one.

Using the function below $$ f(n)=\begin{cases} n/2, & n \text{ even} \\ n+\lceil\sqrt{n}\rceil, & n \text{ odd} \end{cases} $$ for an integer $0
Pinteco
  • 2,631
3
votes
5 answers

Prove that if $gcd(a, b) = c$ then $c^2|ab$.

I recently just started this topic in class and have been going over some examples without much success. I understand the concept behind if a|b and b|c then a|c but when it comes to more complex ones, I become a tad confused.. *Thanks for the help…
Ergo
  • 169
3
votes
2 answers

Prove that $xRy \longleftrightarrow 7|(2x+5y)$ for all $x,y\in Z$ is an equivalence relation

I'm trying to show that this relation is an equivalence relation. $$xRy \longleftrightarrow 7|(2x+5y) \text{ for all } x,y\in Z$$ I need to show that $R$ is reflexive. If I take every $x$ and $y$ are the same I can see that it's fine, how to…
Ofir Attia
  • 3,136
3
votes
3 answers

Mathematical Logic: Having trouble understanding this inference

So here I wanted for fun to infer that: $$(\lvert a\rvert<\varepsilon) \rightarrow (a > -\varepsilon) \land (a < \varepsilon)$$ In other words, if it is true that the absolute value of $a$ is less than $\varepsilon$, then $a$ is in between…
gmmk
  • 33
3
votes
4 answers

Prove $A \bigtriangleup B = B \bigtriangleup A$

I`m trying to prove the following statement: $$A \bigtriangleup B = B \bigtriangleup A$$ I know that: $$A \bigtriangleup B = (A \cup B )\setminus (A \cap B )= (A \setminus B) \cup (B \setminus A)$$ I can do that with truth table. but want to prove…
Ofir Attia
  • 3,136
3
votes
1 answer

How to create a trace table for a recursive function

So, I know how to trace an algorithm in discrete mathematics when you have e.g., a for or while loop and then output. But, for some unknown reason, I am lost when it comes to tracing a recursive function calling itself. def func(n): if n = 1…
Alix Blaine
  • 251
3
votes
1 answer

Identify an inverse of 7 modulo 26.

I was tasked to identify an inverse for 7 modulo 26 Here is what I have done: 26 = 7(3) + 5 7 = 5 (1) + 2 5 = 2 (2) + 1 2 = 1 (2) + 0 Working backward: 1 = 5 - 2 (2) 1 = 5 - 2 (7 - 1(5)) 1 = 3(5) - 2(7) 1 = 3( 26 - 3(7) ) - 2(7) 1 = 3(26) - 11(7) So…
Wsiz
  • 111
3
votes
2 answers

Discrete Math Question: arithmetic progression

A lumberjack has $4n + 110$ logs in a pile consisting of n layers. Each layer has two more logs than the layer directly above it. If the top layer has six logs, how many layers are there? Write the steps to calculate the equation for the problem and…
Brian Smith
  • 157
1 2 3
…
99 100