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

Discrete math problem confusion.

I found another post regarding this here, but I'm still confused how we are going to write the final answer. Your help will be appreciated.
Alexandra Smith
  • 11
  • 2
1
vote
0 answers

Find examples of formulas with the following characteristics.

(a.) Find an example of a formula with at least one quantifier that is $\textbf{false}$ when we quantify over the natural numbers $\mathbb{N}$, but $\textbf{true}$ when we quantify over the integer numbers $\mathbb{Z}$. $(\exists x \in \mathbb{N} :…
needHelp
  • 15
1
vote
2 answers

Arithmetic-Geometric mean inequality proof

I am trying to follow along on this proof of the Arithmetic-geometric mean inequality, but I pretty much crashed at a couple steps. If $a_1 \leq G \leq a_n$, then why is it that $a_1 + a_n \geq \frac{a_1a_n}{G}+ G$? Why do we remove $a_1$ in the…
fdkjghre
  • 11
1
vote
0 answers

Two-dimensional Topology and Ordering

This question came up for me when thinking about an answer to this: https://stackoverflow.com/questions/16326318/finding-blocks-in-arrays. I had the idea of listing the 1's, for example: example1 = [[0,1,0,0] ,[0,1,0,0] ,[0,1,1,0] …
גלעד ברקן
  • 550
1
vote
1 answer

Concrete Mathematics: Chapter 1: Generalised Josephus Recurrence: Understanding Radix 3 to 10 digit-by-digit replacement

Summary When converting $(201)_3$, specifically, converting the $2$, I am not entirely sure how they select $5$ (from $f(2) = 5$) and not $8$ (from $f(3n+2) = 10f(n)+8$) when doing the radix replacement operation for the recurrence following…
Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12
1
vote
2 answers

Constructing A Truth Table

How do I construct a truth table with a formula that has 3 logical operators that lack a parentheses? $$P \lor Q \land \neg(R \lor \neg S)$$
Gerome Tahud
  • 35
1
vote
1 answer

For direct proof, is the case of exception, do we mention it in the proof

For direct proof, if an exception appears, like for example a(a-1) is always divisible by 2 except for the value 1. Do we mention the exception or we need to find an alternative way of explaining to not mention the exception? I am new to discrete…
MikeyYo Ho
  • 23
1
vote
1 answer

True/False cardinal question in Discrete Maths

I would like some help on these claims. Thanks in advance! True or false? If true, give a proof, if not, give a counterexample. If $A$ is a set of functions $\Bbb N \rightarrow \Bbb N$ and for each $f,g\in A$, the set $\{n\in N : f(n)\neq g(n)\}$…
ohad
  • 633
1
vote
1 answer

Concrete Mathematics: Where is the cyclic shift for rewritten generalised Josephus function (1.15 and 1.16)?

Summary In equation labelled 1.16 how is the cyclic left shift happening? I.e. should the $\alpha$ not be at the end as in $(\beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0} \alpha)_2$ instead of $(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}}…
Friedrich 'Fred' Clausen
  • 387
  • 2
  • 12
1
vote
1 answer

The set of all finite subsets of $\mathbb{R}_+$ is countable.

I'm struggling to figure out how to prove that the set of all finite subsets of $\mathbb{R}_+$ is countable. I thought that it wasn't but a TA told me it was and I need to prove why it's countable. I don't even know how to start this proof. If it…
simey
  • 11
1
vote
2 answers

Prove the sum of $\sqrt{3} + \sqrt[3]{4}$ is Irrational number

I really don't know how to prove it. I can prove that $\sqrt[3]{4}$ is irrational and prove that $\sqrt{3}$ is irrational. but as we know , sum of 2 irrational can be irrational or rational ($\sqrt{2} + -\sqrt{2} =$ rational). so I tried to prove…
Roach87
  • 696
1
vote
1 answer

$\forall x\in\mathbb{R}\enspace \enspace, \forall y\in\mathbb{R} : (x\ge y)$ or $(x\le y)$ proof?

Well, it's obvious that it's true. but our teacher just proved it by saying "for each $x$ and $y$ we will input, we will receive true element". My question is - How can I prove it in the best way? I did the contradiction proof and said $\exists…
Roach87
  • 696
1
vote
1 answer

The 50 cards riddle: will this process ever stop?

Assume a deck of $50$ cards, numbered from $1$ to $50$. Look at the number of the top card, assume it is $K$. Now, reverse the order of the first $K$ cards of the deck. For example, if $K=5$ change the order of the top $5$ cards so that the fifth…
user75013
  • 131
1
vote
1 answer

If A is a formula and B is its Negation Normal Form , then are A and B about the same size or is there no relationship between the sizes of A and B?

All the details in the title. I think that they are about the same size (to a multiplicative constant). Am I right? Other options include: $3)$ $A$ is much larger than $B$ $4)$ $B$ is much larger than $A$
Anonymous Molecule
  • 105
1
vote
1 answer

Prove that a countable set of parabolas $\alpha (y-\beta)^2+\gamma=x$, for $\alpha, \beta, \gamma \in \Bbb R$, doesn't cover the entire $xy$ plane

A question I found hard to solve. Prove that a countable set of parabolas $\alpha (y-\beta)^2+\gamma=x$, for $\alpha, \beta, \gamma \in \Bbb R$, doesn't cover the entire $xy$ plane Thanks in advnace for any assistance.
henry
  • 13
1 2 3
…
99 100