Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

-3
votes
3answers
32 views

Pr0ve the following using a direct proof [on hold]

Let x be an arbitrary real number. If |x-2|>4, then |x|>2.
0
votes
2answers
25 views

How should I simplify this expression using the Laws of Logic?

I have this expression here that I have attempted to solve, but as of now I have no success in solving. My problem is probably the distributing part because I don't know how to continue after ...
1
vote
2answers
20 views

Proving a bijection(injection and surjection) over a function

I need some help proving bijections: Suppose f is a function from $$ \mathbb R^2 \rightarrow \mathbb R^2$$ Defined by $$f(x,y) = (ax-by,bx+ay)$$ Where a,b are numbers with $$ a^2 + b^2 \neq 0 $$ ...
1
vote
1answer
25 views

Sets Theory Disproof

I have to disprove the statement: For all sets $S$, if $S$ is a subset of the Natural Numbers, then there must exists some $t ∈ S$ such that $|t|\ge1$ Any hints?
3
votes
2answers
64 views

Sums of binomial coefficients

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
1
vote
1answer
20 views

Inequality induction proof

I have been practicing using Mathematical Induction, in proofs. I came across a problem in my practice problems list that is giving me a lot of trouble. This is the question Prove that $n! > n^3\ ...
0
votes
2answers
9 views

What is the voltage gain of an amplifier that produces an output of 750 mV for a 30uV input?

What is the voltage gain of an amplifier that produces an output of 750 mV for a 30uV input? my solution: Av-? V out =750mv V in = 30 mV AV=? = V out/ V in = 750 mV / 30 mV =25 the answer is ...
0
votes
1answer
20 views

Discrete Mathematics and the Laws of Logic

I have this laws of logic question where it requires me to distribute stuff into brackets but no matter how many times I do it I keep getting it wrong because my distributing is done wrong. Q: ...
0
votes
1answer
15 views

counting bitstrings of specific length

Is my solution right refarding this question? How many bitstrings of length 77 are there that start with 010 (i.e, have 010 at position 1, 2, and 3) or have 101 at positions 2,3, and 4, or have 010 ...
0
votes
1answer
219 views

Discrete Math - Proving/Disproving set identities

I understand that this means that (A and B) or C = A and (B or C), but how would you prove or disprove these set identities. Any help would be appreciated, Thanks
0
votes
1answer
18 views

Is Proof by Resolution really needed here?

So I'm doing a problem in the book but this problem (where they ask me to use proof by resolution) seems unnecessary: $p\iff r$ $r$ $\therefore p$ By definition of IFF, this seems true, but they ...
2
votes
1answer
45 views

A knights and knave problem involving a native with a speech disorder

On an island, every native is either a knight, who always tells the truth, or a knave, who always lies. You meet 4 natives, A, B, C, and D. This is what they say: A: "C is a knight iff D is a ...
2
votes
3answers
177 views

Can someone explain this proof by case example?

I don't fully understand this example the book gives. I understand the section where they examine when $x\gt0$ but when $x\lt0$ things get murky for me. Prove that for every real number $x$, ...
3
votes
1answer
18 views

Minimum and Maximum of a set

I need help at the following: How can we find the minimum and the maximum of a set of $N$ numbers using $1.5N $ comparisons?
-1
votes
0answers
23 views

What would this proposition be expressed in words? [duplicate]

How can this proposition $\forall$n$\in$N$\exists$m$\in$N n^4 = m^2 be expressed in words. Sorry my attempt is: For every natural number, n, there is an existential prime number that is an element of ...
0
votes
0answers
18 views

How to calculate autocorrelation of a Gaussian stochatic

I would like to determine the autocorrelation function of a Gausian stochastic. Let see my problem Please help me to resolve my problem. Thank you so much
2
votes
2answers
155 views

Prove $f(S \cap T) \subseteq f(S) \cap f(T)$

$f(S \cap T) \subseteq f(S) \cap f(T)$ x lies in ($S \cap T$), which means the domain has fewer elements than the domain of S and T, since x must be in S and T. All f(x) values of x, which resides in ...
0
votes
0answers
23 views

strong induction proof of sequence

Posting even though correct just for feedback, etc. $n_0,n_1$ are lower/upper bounds of true values for strong induction. Guess I could have used different values, like 2 and 3, or 1 and 2, but it ...
1
vote
2answers
22 views

Probability between two dice games

Two games, both use un-biased 6 sided dice. game A, Sam throws one die 4 times. He wins if he rolls at least a 6 game B, he has 24 turns, and each time he rolls two dice simultaneously. He wins if ...
0
votes
1answer
19 views

Proving $\lg n!=\Omega(n\lg n)$

In the answer given in the book for the proof of $\lg n=\Omega(n\lg n)$ there are several steps which I don't understand . $$\lg n!=\lg n+\lg(n-1)+\lg(n-2)+ ....+\lg(2)+\lg 1$$ Then it says that ...
0
votes
1answer
32 views

Find the positive constants

Find positive constants, c0 and c1 such that, for all positive integers n, $c_{0}n^{3} < 27n^{3} + 13n^{2} + 873(lg n)^{3} < c_{1}n^{3}$. Justify briefly. I don't even know where to start. Any ...
1
vote
4answers
41 views

Proving onto and 1-1 functions

I understand the 1-1 function side of things, but I still don't really get how to prove that the function is onto Question: Prove that the function $f:\mathbb{R}-\{2\} \to \mathbb{R}-\{5\}$ defined ...
0
votes
1answer
30 views

Can this expression be simplified any further with the Laws of logic?

I am currently on this Discrete math question and so far I have done a majority of the solving, but I am unsure if I am doing the steps right. Can someone give me some advice or explanations for the ...
0
votes
2answers
57 views

fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
2
votes
3answers
67 views

Proof: For all integers $x$ and $y$, if $x^2+ y^2= 0$ then $x =0$ and $y =0$

I need help proving the following statement: For all integers $x$ and $y$, if $x^2+ y^2= 0$ then $x =0$ and $y =0$ The statement is true, I just need to know the thought process, or a lead in the ...
-2
votes
0answers
18 views

Let A, B and C be sets. Show that $\overline A \cap B \cap C \subseteq (A \cup B)\cap(A \cup C)$ [on hold]

How do I solve this? Let $A, B$ and $C$ be three sets. Show that $\overline A \cap B \cap C \subseteq (A \cup B)\cap(A \cup C)$ I can't figure it out. Could I use venn or karnaugh?
-4
votes
1answer
46 views

How to show that $A-(B\cap \overline {C})\subseteq A\cup (B\cap C)$ [on hold]

How do I solve this? Let A, B and C be sets. Show that $A-(B\cap \overline {C})\subseteq A\cup (B\cap C)$ I can't figure it out. Could I use venn or karnaugh?
0
votes
1answer
44 views

Predicate Logic Proof Question

I am struggling really hard with proofs I cannot seem to understand them at all no matter how hard i try. I'm thinking of getting a tutor because questions like this I just give up and fail on. Any ...
0
votes
0answers
22 views

Discrete Math — Regular Expression to express an infinite string of same character?

How might I write an regular expression to represent an infinite string of 1's? In other words, I want an RE to accept 1111... 1* doesn't do the trick because it also contains finite strings of 1's. ...
2
votes
1answer
55 views

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$. My Solution: For all $n$ that is an element of Natural number there is ...
0
votes
1answer
29 views

How many comparisons for sets of 2 of 8 numbers [on hold]

This question appeared in a CS quiz. However I have no idea how to solve it. Your job is to decide which of a set of given numbers is the smallest. How many comparisons (of 2 numbers at a time) do ...
0
votes
3answers
42 views

“To show that f is injective” - I don't get this statement

Suppose that f: A -> B. To show that f is injective: Show that if f(x) = f(y) for arbitrary x, y element A with x != y, then x = y. Why does this defintion(?) of injective state that one of the ...
0
votes
0answers
21 views

HyperCube questions

I have three hypercube questions. 1) How many nodes does a d-dimensional HyperRing have (as a function of d) ? 2) How many edges ? 3)What is the degree of each node in a HyperRing with n nodes ? I ...
0
votes
1answer
30 views

Applying De Morgan's Law

I'm working on my assignment for Discrete Math and I'm not fully understanding how to do this question for it so I was wondering if anyone here could help show me how to do it properly; Use De ...
0
votes
0answers
7 views

How to calculate discrete cosine transform for a matrix

I have a 8x8 matrix and I want to calculate its discrete cosine transform (DCT-II). I have this formula but I don't know to use it with a matrix. In the French Wikipedia they gave an example for ...
3
votes
2answers
167 views

How many tuples of numbers from [1..n] have the sum of its elements equal to n?

[1..n] is the set of integers from 1 to n. The tuples can be of any finite length. The length of each tuple should range from 1 to n. I am asking how many tuples have elements such that the total sum ...
0
votes
1answer
32 views

Show that $\frac{a^{n+2} - 1}{a - 1}=\frac{a^{n+1} - 1}{a - 1} + (n + 1)$ [on hold]

How can I show that \[ \frac{a^{n+2} - 1}{a - 1}=\frac{a^{n+1} - 1}{a - 1} + (n + 1) \]
5
votes
4answers
187 views

How many ways can 5 dice produce a total of 20?

How many ways can $5$ dice produce a total of $20$? I set up the equation $x_1+x_2+x_3+x_4+x_5 = 20$. The total possible number of combinations is $\binom{19}4$. From there I subtracted the ...
1
vote
1answer
38 views

Is ∃xP(x) ∨ ∃xQ(x) the same as ∃xP(x) ∨ ∃yQ(y)?

Very simple question: is ∃xP(x) ∨ ∃xQ(x)the same as ∃xP(x) ∨ ∃yQ(y) Thank you.
4
votes
1answer
20 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
3
votes
1answer
47 views

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a.

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a. Any ideas? (Suggested proof by contradiction). Not really sure how to go about this.
0
votes
2answers
357 views

Writing a boolean formula and logic circuit that computes mux

Let $mux(p_{11}, p_{10}, p_{01}, p_{00}, x_1, x_0) = P_{x1x0}$ (with all variables bits). Write a boolean formula, and then draw a circuit, that computes mux. For ...
0
votes
3answers
42 views

Turn 6 cards upside down

Six identical cards are placed on a table. Each card has number '1' marked on one side and '2' on the other. All cards are placed with '1' facing upward on a table. In one try, exactly four cards ...
-5
votes
1answer
100 views

Are variables the same in pure mathematics???

my question is In pure mathematics, $x$ always $=x$ $x = x$, the variables are abstract. In modelling, $t$ could mean the time that has elapsed since you started a machine for example. Or ...
-1
votes
2answers
22 views

Is there any compact notation for the count [on hold]

Can any one suggest what is the best compact notation that I can use for the following pseudo problem. I think it is simple counting with some constraints but don't know if is there any notation for ...
0
votes
1answer
58 views

Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
0
votes
2answers
410 views

Example of an infinite complete lattice which is distributive but not complemented

Which is an example of an infinite complete lattice which is distributive but not complemented? Is the set of natural numbers under the relation divides an example? Also is the set of natural numbers ...
1
vote
1answer
36 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
0
votes
1answer
13 views

Let n be an arbitrary natural number and let the property P(n) be the equation 2 · 6 · 10 · 14 · … · (4n - 2) = (2n)! / n!

Here's my proof: Base Case: Show that P(1) is true: n = 1 (4(1) - 2) = (2(1))! / (1)! 4 - 2 = 2! / 1 2 = 2 The base case holds. Induction Step: Show that for all natural numbers k, if P(k) is ...
0
votes
1answer
20 views

Find the coefficient of $x^1y^7$ in the expansion of $(2x−y)^8$.

I was doing practice problems for a discrete math class and came across this one which has stumped me. I know that if the problem was "Find the coefficient of x^1y^7 in the expansion of $(x−y)^8$" the ...