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

Suppose that a and b are real numbers with $0< a <1 $ and $0< b <1$. Prove by contradiction or contrapositive: If $a^2+b^2= 1$, then $a+b >1$.

So far I get the below: To prove the above statement with contrapositive, we need to show that if $a+b \leq 1$ then $a^2 + b^2 \ne 1$. If $a+b \leq 1$, then $a \leq 1 - b$. If we square both sides of the inequality we get $a^2 \leq (1 - b)^2$, which…
bloomsdayforever
  • 485
1
vote
1 answer

If a function $f(x)$ is constant complexity $f(x) = O(1)$ , describe $C$ and $k$.

If a function $f(x)$ is constant complexity $f(x) = O(1)$ , describe $C$ and $k$. This needs to be described in terms of the relation of $C$ and $k$. There exists constants $C$ and $k$ such that $C|f(x)| \le |1|$, for all $x > k$. The above cannot…
KudmiSubba
  • 97
1
vote
1 answer

Why $( → ) → $ and $( ∧ ) → $ not equivalent

Question: For this logical expression without truth table please: $( → ) → $ and $( ∧ ) → $ are not equivalent based on truth table below: Problem: Answer based on truth table is NO. But how to find out that they are not using logical equivalences…
Avv
  • 1,159
1
vote
0 answers

Is bijection implied by mutual injection?

Suppose $f : A \to B$ is one-to-one, and there is another function $g : B \to A$ which is also one-to-one. We don’t assume anything in particular about the relationship between $f$ and $g$. Are $f$ and $g$ necessarily bijections?
malte
  • 11
1
vote
1 answer

How do we prove that $\frac{x^{2} + y^{2}}{2}\geq \sqrt{2(x-y)^{2}}$ if $xy = 1$ and $x\neq y$?

Apparently this can be solved using AGM: $$(xy = 1)\wedge(x \neq y) \Rightarrow \frac{x^{2} + y^{2}}{2}\geq \sqrt{2(x-y)^{2}}$$ I've tried doing $$\frac{x^2 + y^2}{2} \geq \sqrt{x^2 y^2}$$
Noel
  • 21
  • 3
1
vote
1 answer

Concrete mathematics: Computing the value of certain infinite sums example

In Concrete Mathematics (Graham, Knuth, Patashnik), on page 58, there is the below example of calculating the value of an infinite sum : $$ \begin{align} \sum_{k \geq 0} \frac{1}{(k+1)(k+2)} &= \sum_{k \geq 0} k^{\underline{-2}} \\ &= \underset{n…
Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12
1
vote
4 answers

congruence proof: Prove that there is no integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true.

Prove that there is no Integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true. How should I approach this question? I attempted using contra-positive proof, so $x=6p+2$ and $x=9q+3$ where $p,q$ are integers. Then $6p+2=9q+3$.
calakala
  • 15
1
vote
3 answers

Prove the following by contradiction: for any $n \in \mathbb{Z}$ we have $9 \nmid (n^2 + 3)$

I understand that I need to derive false from $\neg(9 \nmid (n^2 + 3))$, or $9 \mid n^2 + 3$. To do this, I attempted to say $n^2 + 3 = 9k$ for some $k \in \mathbb{Z}$. Then I tried something like $3 = -n^2 = -3(k - 1)$, but $-3 \mid 3$. That…
user956014
  • 23
1
vote
1 answer

Self-duality of two boolean functions

I'm stuck with one problem. I have two boolean functions: $1)$ $x \oplus 1$ $2)$ $x \oplus y \oplus 1$ The question is which of them is self-dual and which is not. I know the definition that one boolean function is self-dual iff it is equivalent to…
ash975
  • 13
1
vote
0 answers

Proof: If n is a perfect square, then n + 2 is not a perfect square using Contrapositive

The following is my approach: Since we're using contraposition approach, we assume that $n + 2$ is a perfect square. We assume that $√(n+2)=p$ Then $p$ may be even or odd Let $p = 2q$ (for even) or $p = 2q+1$ (for odd) Now $p² = (2q)^2 = 4q^2 = 2k,…
Nigel Ang
  • 11
1
vote
2 answers

For each value for $a$ and $b$, being real numbers, $a^2 + b^2 \ge ab$

For each value for $a$ and $b$, being real numbers, $a^2 + b^2 \ge ab$ Should I solve this by replacing all possible real number formulas in these to be able to prove this? As an example for odd numbers, by replacing $2x + 1$, etc...?
JOUA
  • 203
1
vote
1 answer

Final number after a skip-delete algorithm acting on a circular seating of numbers

There are 128 numbers 1, 2, . . . , 128 which are arranged in a circular pattern in clockwise order. We start deleting numbers from this set in a clockwise fashion as follows. First delete the number 2, then skip the next available number (which is…
tryst with freedom
  • 11,538
1
vote
2 answers

Find bijection $\Bbb R\setminus\Bbb Q \to \Bbb R$

Find bijection $\Bbb R\setminus\Bbb Q \to \Bbb R $ I've tried using Schröder–Bernstein theorem to show a 1-1 function in both directions. But I only succeed to prove one direction. Explicit function seems much harder to prove. thanks for any help.
DanielG
  • 397
1
vote
1 answer

Basic algebraic/arithmetic manipulations

I do not know the rules governing the transformation of each member of the following group of equations into the the next one: $$ 5(1 + 2^{k -1} + 3^{k -1}) - 6(1 + 2^{k -2} + 3^{k -2}) + 2 \\= (5 -6 + 2) + (5 \times 2^{k - 1} - 6 \times 2^{k - 2})…
Edward.Lin
  • 175
1
vote
0 answers

How to prove $(3^b \mod 17)^a \mod 17 = 3^{(ba)} \mod 17$?

I watched this 2min video https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-2 and I am struggling on understanding the proof in a comment (@Cameron) below. Basically, the author…
Rick
  • 111
1 2 3
…
99 100