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

How do I show a statement is a tautology in the Booleans algebra

I want to show through Boolean algebra that the statement $$\neg Q\Rightarrow (R\Rightarrow \neg (P\land Q))$$ is equivalent to the tautology $Q\lor(\neg Q)$?
user8322
1
vote
1 answer

Different balls in an urn

There are 20 red, 20 green and 20 blue balls in an urn. In how many different ways can 10 balls be selected? How many ways are there if there are 6 red balls instead of 20? I would think to solve this with the binomial coefficient (i.e. 60 choose…
Johnny
  • 31
  • 4
1
vote
2 answers

Help me understand how to Find f(n)

I have this question: $f(0) = 0$ $f(1) = 1$ $f(n) = f(n-1) + f(n-2)$ help me understand and find $f(n)$.
zac
  • 129
1
vote
4 answers

Simplifying Quantified Statement

For my assignment, I have to simplify this statement leaving no negations in the end. $$\neg\exists x\ \forall x(\neg B(x) \wedge C(x))$$ Everything I've tried so far leaves me with a single negation sign on $B(x)$ or $C(x)$ and I just cannot figure…
1
vote
1 answer

Weighing the odd one out in a group of 12 objects using only 3 uses of a balancebeam scale

The basic premise is to find the odd one out (weight-wise) in a group of 12 objects. One object has a different weight than the others. Using the balancebeam scale three times, find out which one is which. How would I even begin to go about this…
Gingeas
  • 11
1
vote
1 answer

Inverse of a multivariable function 3

Consider a function $f : Y_n \rightarrow X_{n^2} $ For any $(a, b) \in Y_n $, let $f((a, b)) = f(a, b) = an + b.$ Prove that $f$ is a bijection and find its inverse $f^{-1}$. I am struggling to see how I can find an inverse of this multivariable…
Tyler K
  • 11
1
vote
1 answer

real number and p(N) Equinumerosity

I am not familiar with all rule but I read about infinite set and Cantor's diagonal. I want to prove there is one to one correspondence between power set of natural number and real number. I search a lot but I don't find anything. Is it possible…
Amin
  • 595
1
vote
1 answer

Is the following statement true or false?: There are integers $x$, $y$ and $z$ such that $15$ divides $2^x \cdot 3^y \cdot 7^z$

My son asked me for help on this question but I have forgotten how to do it. Could you please save me from looking like an idiot in front of my son, it would be very much appreciated. Thank you
1
vote
1 answer

Suppose that a set has an odd number of elements. Explain why half of the subsets will have an odd number of elements

Suppose that a set has an odd number of elements. Explain why half of the subsets will have an odd number of elements . Now assuming set A is the set with an odd number of integer elements{1,2,3,4,5} Subset b ={1,2} subset c={3} Subset d={4,5} Now…
1
vote
1 answer

How many hands in poker?

I guess the answer is pretty intuitive that its 52 C 4 to most people, but no one has been able to explain to me why it's not 52*51*50*49*48... My reasoning is the first time you choose you to have 52 cards to choose from, then 51, and so on and so…
1
vote
1 answer

Question about big o

I have trouble starting this homework assignment for my discrete math class. Does $\Theta(n^3+2n+1) = \Theta(n^3)$ hold? Justify your answer. We need to prove $n^3+2n+1 \in \Theta(n^3)$ AND $n^3 \in \Theta(n^3+2n+1)$\ First lets solve $n^3+2n+1 \in…
1
vote
3 answers

What's the difference of $xRy=1$ on $\mathbb {Z}$ or $\mathbb {R}$?

Suppose we define the relation xRy iff xy=1, is this relation: Reflexive? Irreflexive? Symmetric? Antisymmtric? Transitive? From my understanding on Z (integers), the relation is symmetric and transitive. Symmetric: if xy=1 then yx=1 is…
Slurpee
  • 13
1
vote
4 answers

I need help proving a proof by contrapositive. (I dont know where to begin)

So I have been working on a homework assignment and I'm just beyond stuck and can't seem to figure out where to start. We are suppose to prove some proofs with either direct proof, proof by contrapositive, proof by contradiciton, or a proof by…
Josh
  • 21
1
vote
0 answers

Jumping all over the place [Discrete Mathematics]

Question: You are allowed to put a checker on any lattice point in the Cartesian plane with y-coordinate less than or equal to zero (i.e. a point with integer coordinates on or below the x-axis). Note that you may place infinitely many checkers to…
user517784
1
vote
2 answers

Linear system in $\mathbb{Z_3}$

Given the linear system in $\mathbb{Z_3}$: $$ \left\{ \begin{array}{c} a+b+c+d=1 \\ b+c+e=2 \\ a+2e=0 \end{array} \right. $$ I used the row reduction with matrices and I got: $$ \left\{ \begin{array}{c} a+b+c+d=1 \\ b+c+e=2 \\…
user530437
  • 11
  • 4