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

Infinite sum on totient function

Find the value of $$\sum_{i=1}^{\infty}{\frac{\varphi(i)\cdot 7^i}{15^i-7^i}},$$where $\varphi(i)$ is the usual totient function. Any ideas? I tried to coax a telescoping sum and even the closed form of $\varphi(i)$ but of course the totient…
user799557
1
vote
1 answer

How to prove $a \leq c \Leftrightarrow [a\lor(b\land c)] \leq [(a\lor b)\land c]$

$(X, \leq)$ is a lattice (order). For all $ a,b,c \in X$, can you prove $$a \leq c \Leftrightarrow [a\lor(b\land c)] \leq [(a\lor b)\land c]?$$ As far as I have managed to do this: (1) Let: $[a\lor (b\land c)]\leq [(a\lor b)\land c]$ $a\leq…
De Costa
  • 75
1
vote
1 answer

Discretization of Continuous Mathematics

I am currently taking a course involving the use of numerical methods to solve partial differential equations. I have not yet been exposed to such a technique and as an aspiring computer scientist, am particularly intrigued as to its implications. …
vrume21
  • 497
1
vote
2 answers

Need help solving a problem using the rules of inference - Discrete Math

I am having issues solving this problem and I believe I would benefit if someone could help me break it down into simpler terms to perhaps give me a starting point. I tried applying DeMorgan's Law to the first line but I don't know what to do next…
M.M.
  • 19
1
vote
3 answers

Proving two claims about sets and functions

Let X,Y be sets, and let $f:X\rightarrow Y$ be a function. Prove: $f(f^{-1}(B))\subset B$ for every $B\subset Y$. Intuitively I understand why's that, but how do I prove it with formality? For every $B\subset Y$, $f(f^{-1}(B))=B$ if and only if $f$…
ohad
  • 633
1
vote
1 answer

Uniform Dequantization in Machine Learning or Deep Learning

Recently, i have read a paper (Thesis et al., 2015) about dequantization method, which is a technique to transform a discrete variable to continuous variable. Theis, L., Oord, A. v. d., and Bethge, M. A note on the evaluation of generative models.…
sungho park
  • 21
1
vote
1 answer

How would I solve this modular arithmetic? (large number)

I am trying to solve this modular arithmetic problem but the numbers are large. How would I simplify? $M \equiv (1567)^{5}$ mod $2881$
Router Power
  • 11
1
vote
1 answer

Proof by Induction of Modified Boole’s Inequality

Suppose that $A_1, . . . , A_k$ is a collection of $k ≥ 2$ sets. Show that (using induction), $$\big| \bigcup\limits_{i=1}^{k}A_i \big| \ge \sum\limits_{i=1}^{k} \big|A_i| - \sum\limits_{\{i,j\}} \big|A_i \cap A_j \big| $$ where the second term on…
big32
  • 55
1
vote
1 answer

How to find relation correctly and their property?

I have such a question: $${A = \{1, 2, 3\}}$$ $${R \text{ on } P(A)}$$ $${\{3\} \subset a \cap b \leftrightarrow aRb}$$ Question is - if such relation is symmetric, antisymmetric, transitive or reflexive So, as I far as I understand first of all we…
Sirop4ik
  • 297
1
vote
1 answer

Proof in textbook regarding the uncountability of the set of all functions from $\mathbb{Z}^{+}$ to the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

In her proof of this problem, Epp defines a function that I do not understand. How is it possible for a function that sends each positive integer $n$ to $a_n$ to have codomain $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. My understanding of this function is…
mooglin
  • 281
1
vote
1 answer

Why there is two possible equals solution?

While I was reading I faced such example $${(A\cap B) * (C \cap D) = (A * C) \cap (B * D)}$$ But then I faced another example that looks almost equal to this one, but has another solution $${(A\cup B) * (C \cup D) = (A * C) \cup (A * D) \cup (B * C)…
Sirop4ik
  • 297
1
vote
0 answers

Series of ones and zeros

So I got this task "How many series are there of length 10 with values {0,1} that have at least one "110" configuration?" It says i should use the inclusion-exclusion pattern, but I don't know how. Any help would be nice
WPHakoon
  • 117
1
vote
1 answer

How many elements must be selected from the set $S$ to ensure at least two elements have a sum of 110?

Question: Let $S$= $\{3, 7, 11, 15, 19, . . . , 95, 99, 103\} $ How many elements must be selected from the set $S$ to ensure at least two elements have a sum of 110? Answer: There are 14 pairs: $\{7, 103\}, \{11, 99\}, . . . \{51, 59\}, \{55\},…
user749176
1
vote
1 answer

Sets $X,Y,Z$ are subsets of a universal set $S$. If $Z \subseteq (X \cap Y^c) \cup (Y \cap X^c)$, then $Z \cap (X \cap Y) = \emptyset$

Sets $X,Y,Z$ are subsets of a universal set $S$. If $Z \subseteq (X \cap Y^c) \cup (Y \cap X^c)$, then $Z \cap (X \cap Y) = \emptyset$ I started with Allow $k\in Z$ such that $k\in (X\cap Y^c)$ or $k\in (Y\cap X^c)$, therefore $k\notin (X\cap Y)$…
lostintranslation
  • 35
1
vote
1 answer

Determine the validity of the argument.

I have this question and was hoping I could get some help on it: p∧q∧r → s u →s p∧u∧~r ∴q I have found: p is true u is true ~r is true r is false. But I am unsure what to do to find the validity of the statement. My thinking is that premise 1 is…
Jay_ Niel
  • 11
1 2 3
…
99 100