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

functional dependencies

Consider the schema R(ABEFJK) with functional dependencies {BE->JK, J->FA, F->B}. I was told to find all the keys for this function this is what I did I dont know if im correct BE->JK BE -> J BE -> K BE->FA BE->F {ABEFJK} BE is a…
jyuserersh
  • 391
  • 1
  • 6
  • 15
2
votes
1 answer

Degenerate Pi-notation

can i say that a degenerate productory like $$ \prod_{t=1}^{0} (1+r_t) $$ is equal to one? I cant seem to find a precise answer about this anywhere.
Lucas
  • 21
2
votes
2 answers

Discrete and Combinatorial Mathematics Ralph P. Grimaldi (fifth edition) Problem 18 Section 11.3

I'm working on problem #18 of section 11.3 from Ralph P. Grimaldi's textbook Discrete and Combinatorial Mathematics an Applied Introduction, fifth edition. Let $k$ be a fixed positive integer and let $G=(V,E)$ be a loop-free undirected graph, where…
no lemon no melon
  • 2,129
2
votes
3 answers

For every integer a, b, c, if 3c is not divisible by a, then b is not divisible by a or 3c is not divisible by b

I can't seem to figure this proof out. How would I prove this by contradiction and contraposition? I tried doing it by saying $3c=bk=(ak)k=a(kk)$ since $b=ak$, $3c=bk$ for some interger $k$ $3c=a(kk)$ contradicts "3c is not divisible by…
William
  • 23
2
votes
2 answers

Let $X \subseteq \mathbb{R}$ s.t $X \cap (y+X) \neq \emptyset \ \forall y \in \mathbb{R}$, prove $X$ is not countable

Given $X \subseteq \mathbb{R}, y \in \mathbb{R}$, define $y+X \triangleq \left \{ y+x : x\in X \right \}$ Let $X \subseteq \mathbb{R}$ s.t $X \cap (y+X) \neq \emptyset \ \forall y \in \mathbb{R}$. Prove $X$ is not countable. My first idea was…
paxtibimarce
  • 645
  • 5
  • 13
2
votes
2 answers

Probability question about distinguishable and non distinguishable objects

so for part a I got the answer as m choose 1 times (1/m)^b but for part B I am having different approaches and dont know which one is correct approach 1: m choose 2 times (2/m)^m approach 2: m choose 2 times (1/m)^m approach 3: (i was thinking…
jyuserersh
  • 391
  • 1
  • 6
  • 15
2
votes
4 answers

If $n$ is odd, then $n/2 + 1/2$ is always even?

If $n$ is odd, prove that $n/2 + 1/2$ is even. Context: I'm a Statistician and the term $n/2 + 1/2$ showed up in the index of a summation when deriving the pdf of some Order Statistic: $$ \sum_{j = (n+1)/2}^{n}... $$ I realized that $n/2 + 1/2$ is…
Sigma
  • 1,836
  • 15
  • 35
2
votes
3 answers

What is the meaning of this set notation?

I am studying discrete mathematics using Rosen Discrete Mathematics 7th Edition. I am doing sets. I don't understand what this means. I don't understand why the intersection of all these sets is {1}. I thought it would be all {1,2,3,...., i}.
chaulap
  • 157
  • 6
2
votes
0 answers

How to Determine a Formula for a Sequence of Numbers?

Possible Duplicate: How can I write an equation that matches any sequence? I'm learning sequences right about now, and I'm having a really hard time finding the formula for a given sequence of numbers. I'm worried that, at exam time I'll be…
IAE
  • 1,327
2
votes
1 answer

Proving closure of set

My attempt: $\overline{B} \subseteq \ell^\infty$ follows from the fact that $B \subseteq \ell^\infty$ and $\ell^\infty$ is closed. For $\ell^\infty \subseteq \overline{B}$, we must show every sequence in $\ell^\infty$ can be represented as a limit…
learning_linalg
  • 101
2
votes
1 answer

Is the map $\mathbb{Z}\times (\mathbb{Z}_{>0})\to \mathbb{Q}$, given by $(m,n)\mapsto \frac{m}{n}$ injective, surjective or bijective?

Is the following mapping $$\mathbb{Z}\times (\mathbb{Z}_{>0})\to \mathbb{Q},(m,n)\mapsto \frac{m}{n}$$ injective, surjective or bijective? I have been working on this problem for a couple of hours and I think it is surjective, and here is my…
Mattmmmmm
  • 69
2
votes
3 answers

Given cups that are $\frac12$, $\frac13$, $\frac14$, $\frac15$, $\frac18$, $\frac19$, $\frac1{10}$ full, can we pour to get a cup $\frac16$ full?

There are seven cups, $C_1$, $C_2$, $\ldots$, $C_7$ and they have the same capacity $V$. Initial: Water of $C_1$ occupies $\frac{1}{2}V$ Water of $C_2$ occupies $\frac{1}{3}V$ Water of $C_3$ occupies $\frac{1}{4}V$ Water of $C_4$ occupies…
know dont
  • 415
2
votes
3 answers

How is this proposition false?

I have a proposition: ((x v y) <=> (~x => ~y)) When I solve this, I end up getting True but the answer is False. Here's how I solved it: when we have a <=> b, we can write it as ~a.~b + a.b and a => b becomes ~a+b So the above equation becomes: =>…
Sarvagya Gupta
  • 163
2
votes
1 answer

Let $A$ be a set of size $4$. How many reflexive relations are on $A$?

Let $A$ be a set of size $4$. How many reflexive relations are on $A$? Let $n = |A| = 4$ Number of reflexive relations = $ 2^n $ Is that correct? I think so because I imagine I only want to calculate the number of relations in the diagonal of the…
user1766555
  • 553
2
votes
1 answer

$R = \{(f,g) \mid f(0) = g(0)\;\text{or}\; f(1) = g(1)\}$ The relation is...

Let $A$ be the set of all functions from the set of integers to the set of integers, and let $R$ be the relation on $A$ given by $$ R = \{(f,g) \mid f(0) = g(0) \;\;\text{or}\;\;f(1) = g(1)\} $$ The relation is: (a) reflexive, symmetric,…
user1766555
  • 553
1 2 3
…
99 100