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.

learn more… | top users | synonyms

0
votes
1answer
64 views

formula generalization finit sets union

To generalize some formula to finit sets union what is the best way to start? let me give an example: $$n(A\cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C + n (A \cap B ...
-2
votes
1answer
56 views

how can i reduce those propositions?

how to i reduce the below compound propositions ? 1) (p∨q∨¬r)∧(p∨¬q∨¬s)∧(p∨¬r∨¬s)∧ (¬p ∨ ¬q ∨ ¬s) ∧ (p ∨ q ∨ ¬s) 2) (¬p∨¬q∨r)∧(¬p∨q∨¬s)∧(p∨¬q∨ ¬s) ∧ (¬p ∨ ¬r ∨ ¬s) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ ¬r ∨ ¬s) ...
0
votes
1answer
373 views

How to prove “If $R$ is transitive, then $R^n$ is transitive.”?

I can understand $R^n$ is $R$'s subset, but I can't understand why $R^n$ is transitive,too. I used mathematical induction: Basis step: Let $n = 2$. If $a R^2 b$, $b R^2 c$, I need to prove $a R^2 c$. ...
1
vote
3answers
131 views

Validity of an argument

Can anyone help me solve this question? Determine whether the following argument is valid. Explain why: "If Batman were able and willing to prevent corruption, then he would do so. If Batman were ...
0
votes
0answers
40 views

Equal distribution of items (Fair Proportionment)

This is a xpost from SO: Original Tagedits are more then welcome. I'm thinking this might be just as appropriate here: The goal: Say I have X workers in a fruit plantation. At the plantation ...
0
votes
3answers
135 views

Can I apply the absorption law on $(\lnot R \land P) \land (Q \lor P) \equiv P$?

With the absorption law, I know I can do $$P \land (P \lor Q) \equiv P$$ Can the same be applied like this? $$(\lnot R \land P) \land (Q \lor P) \equiv P$$ Because, technically, I could move $Q$ ...
3
votes
4answers
245 views

Discrete Math - Set Theory - Power Set

I am stuck on a problem in my discrete mathematics textbook at the moment. The problem, as written in the textbook, is: For a certain set $A$, the power set of $A$ is $\mathcal{P}(A) = \{\aleph_0, ...
1
vote
3answers
714 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
85 views

How many 7 letter passwords can I make using letter A,B,C?

I did it using the multichoose formula but it does not work where Order Matters. So I am stuck please help!! EDIT: You have to use all three letters.
0
votes
1answer
54 views

Language equivalence - manipulation of languages with Star operator

Why is this always true $(A^{*} \cap B^{*})^{*} = (A \cap B)^{*}$ ? $A^{*} = \{ x_{1}x_{2}...x_{k}| k \ge 0$ and each $x_{i} \in A\}$, and similarly for B. Assuming A and B are any languages i.e. ...
0
votes
1answer
65 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
1
vote
2answers
58 views

Expressing “there is none” in universe discourse

I'm attempting to express: There is no Vans that are fast and turbocharged. The domain of this is all vans. $V$ $F(v)$ is fast $T(v)$ is turbocharged Is the correct way to equate this, as ...
0
votes
4answers
116 views

Proof of continuity [closed]

Let $$f:\mathbb{R}\mapsto \mathbb{R}.$$ Prove that if f is differentiable at a real number c, then f is continuous at c.
1
vote
2answers
84 views

How to express “exactly one” in the universe of discourse?

Lets say we have a proposition: There is exactly one car parked out side that is black. How can I express this in the universal discourse?
1
vote
2answers
106 views

Discrete math Exponential Generating Series

Solve the recurrence $y_{n+1} = 2y_{n} + n$ using exponential generating series. The given condition is $y_{0} = 1$. It is also noted that the equation is equivalent to $y_{n} = 2y_{n-1} +n -1$. I ...
2
votes
1answer
58 views

Question on normal subgroup

Let $x=(1 \, 2 \, 3 \, 4)$ and $y= (2 \, 4)$ be elements of $S_4$. Let $G= \langle x,y\rangle_{S_4}$, Let $H =\langle y\rangle_{S_4}$ and let $K=\langle x\rangle_{S_4}$. I have never seen this ...
0
votes
2answers
111 views

Rewrite equivalent boolean function for p ⇔ q

Using only the operators ⇒ (conditional) and ∼ (negation) Rewrite p ⇔ q How should I go about this? Thanks
0
votes
1answer
640 views

Convexity of sum and intersection of convex sets

Let $A_i$ be a subset of $\Bbb{R}^m$ which is convex for $i=1,...,n$. How can I prove that the sum of $A_i$ is also convex? I know how to prove it with two sets: Let $x = a_1 + b_1$ and $y = a_2 ...
3
votes
0answers
82 views

Counting number of distinct systems

This is an enumeration problem in conjonction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
2
votes
2answers
79 views

Prove that $t$ is a one-to-one correspondence.

I am having problems with this discrete math proof. I have made it this far, but I do not understand how to go from here. Problem: Define a map $t: \mathbb{R} \times \mathbb{R} \rightarrow ...
1
vote
0answers
80 views

Decryption of an Encrypted Message

Suppose we are given sending a message to two people: A and C. A and C have the same RSA encryption modulas: R=(some arbitrary number, say) 454564515456465465465156. But A and C have two different ...
1
vote
1answer
177 views

Converting into CNF Form

If you have disjunctive clause comprising of n literals for example $(X_1\cup X_2\cup X_3\cup\cdots \cup X_n)$. where $n\geq 4$. How you can convert it into CNF (Conjunctive Normal Form) of $n-2$ ...
1
vote
2answers
98 views

Is $\{1, 2, 3\}\times \Bbb Z$ uncountable?

$\Bbb Z$ being the set of integers. My understanding is that a set is uncountable if it's greater than the set of $\Bbb N$. Might it be that I'm misunderstanding the question, and misinterpreting ...
1
vote
1answer
1k views

If a composition of functions is injective, must its components be injective?

Assume that we have one on one function, that look like that: $$f(g(x))$$ We need to proof or dis-proof that: I.f is one on one. II.g is one on one. I know the answer on booth questions, but my ...
1
vote
1answer
96 views

Could someone please explain counting to me?

I'm taking a Discrete Math class and I understand the concepts behind counting, but I feel like I'm having to learn how to tackle word problems all over again. I can't seem to figure out how to ...
2
votes
1answer
75 views

A problem about the discrete logarithm

suppose there are a multiplicative cyclic group $F_p^*(p \;is\;big\; prime)$, and $G=\langle g \rangle(g \;is\; a\; generator)$ is a subgroup of it and $G$'s order is $q(q\;is\;big\;prime \;and ...
2
votes
1answer
1k views

Word and Latex: Probability

I was practicing my probability and counting solving ability when I came across this rather interesting question on the web: The Reviews editor for a certain scientific journal decides ...
0
votes
1answer
122 views

Show that the ith power of the reversal of a string is the reversal of the ith power of the string

I need to show that (wr)i = (wi)r I'm trying to do this through inductions, so this is what I have so far: Let P(w) be the statement: (wr)i = (wi)r Basis: Prove P(λ) is true: (λr)i = (λ)i = λλ...λ ...
1
vote
1answer
781 views

Probability and Counting

I have just picked up a text on discrete math and its been ages since I have done this so if anyone can show me with steps to correct my fault, that would be so great. Repair facility has 25 failed ...
2
votes
2answers
9k views

Proof by induction: $2^n > n^2$ for all integer $n$ greater than $4$ [duplicate]

I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list: Prove, using mathematical induction, that $2^n > n^2$ for all integer n greater than ...
1
vote
1answer
120 views

Counting Problem: Baseball problem

I am self studying statistics and having hard time with figuring this one out. In a baseball team, there are 15 players on its roster. How many ways are there to select 9 players for the starting ...
1
vote
1answer
50 views

Sets, Total Functions, Equality

Suppose you have finite Sets $A$, $B$, $C$. The function from $X \to_\text{total}Y$ represents a set of all of the total functions from set $X$ to set $Y$. Ex: Suppose $X$ is the set ...
3
votes
1answer
86 views

Proving $R$ is a Equivalence Relation?

The Relation: $\left\{R = ((m, n) |\ mn \geq 0\ \right\} on \ \mathbb{Z}$ apparently has an equivalence class. I can't really see it, I can see that reflexive does not fail. From the looks for it, ...
0
votes
2answers
122 views

Closed form for a summation with 3 factors in the summand fraction denominator

I'm studying for a Discrete Math exam and I'm preparing myself with an (unsolved) exam from a previous year. One of those exams had two exercises in a section of the Exam. The first exercise - that ...
1
vote
2answers
242 views

Prove that Hamming cube has a Hamiltonian cycle

How would one prove that all Hamming cubes with 2 or greater dimensions have a Hamiltonian cycle.
1
vote
1answer
92 views

Proof of a combinatorial identity$\binom{4n}{2}-4\binom{n}{2}=\binom{4}{2}n^2$ [closed]

I struggle to prove the combinatorial identity: $$\binom{4n}{2}-4\binom{n}{2}=\binom{4}{2}n^2.$$ The proof needs to be combinatorial, not algebraic.
0
votes
1answer
57 views

meaning of $C_4$ tree in graph theory

I was reading a paper. There a term was defined as $C_4$ tree. It was written that a graph is $C_n$ tree if it can b constructed from $C_n$ by a finite number of applications of the following theorem ...
0
votes
3answers
47 views

Random variable $X$ inducing a distribution on $V$

I have been learning about discrete probability and found a somehow confusing (to me) definition of distribution of a random variable $X$ on a set $V$. The definition of a Random variable $X$: $$ ...
0
votes
4answers
72 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
27
votes
8answers
2k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
3
votes
4answers
194 views

Why if $x^2$ is divisible by two then $x$ is divisible by $2$?

In the proof for "$\sqrt2$ is irrational" one of the steps goes like this: $a^2 = 2b^2$ From this we conclude that $a^2 \equiv 0 \mod 2 $ We don't stop here and infer that $a \equiv 0 \mod 2$ ...
1
vote
2answers
150 views

Equation for determining a car's fuel consumption as well as cost

Purchase price: 24000 Avg km/year: 40000 L/100 km: 5.3 Price of gas (per L):1.30 I was wondering what the formula is to find out how much litres of gas the car would consume as well as the cost of ...
1
vote
1answer
32 views

Relations properties

Let $\mathrm M = \Bbb R; \mathrm R = \{(x,y)\mid x = y\}$ Investigate wheter the relation is reflexive, transitive, symemtric, antisymmetric. Reflexivity $\rightarrow (\forall x \in \mathrm ...
3
votes
2answers
131 views

“Upper summation” binomial identity: different version from “Concrete Mathematics”

The book "Concrete Mathematics: A Foundation for Computer Science", 2nd Edition - authored by Ronald L. Graham, Donald E. Knuth, Oren Patashnik - has, in its page 174, a table called: "Table 174 The ...
0
votes
2answers
52 views

Justify a relation

let $\mathrm A = \Bbb Z \text{ and } R = \{(a,b) \in \mathrm A\times \mathrm A | a \lt b \}$ investigate whether the relationship is symmetric or antisymmetric. So (...) Symetric [...
2
votes
4answers
422 views

Proper subsets of $\{a,b,c,d\}$.

List the members of $\mathcal P\left(\{a, b, c, d\}\right)$ which are proper subsets of $\{a, b, c, d\}$. Sorry, I know this is basic, but I'm knew to this. I think the answer is just $\{a\}, \{b\}, ...
2
votes
1answer
57 views

Find $A_1,A_2, A_3, A_4$ such that $\lvert A_i \cap A_j\lvert = \lvert i-j \lvert$

Give example of four sets $A_1,A_2, A_3, A_4$ such that $\lvert A_i \cap A_j\lvert = \lvert i-j \lvert$ for every two integers $i$ and $j$ with $1\leq i < j \leq 4$. I was able to solve this ...
1
vote
3answers
193 views

Set Theory question

I have some exercises to prove different laws of set theory but my study guide does not provide any answers for the exercise. I have completed one of the exercises and just want to make sure I am ...
2
votes
1answer
162 views

approximation of sum of gaussian-like function?

Let: $g(u; x,s) = \dfrac{1}{s\sqrt{2\pi}} \exp\left(-\dfrac{1}{2} \left(\dfrac{x-u}{s}\right)^2\right)$ Where $x,s$ are parameters I'm looking for a closed-form solution or approximation of: ...
0
votes
1answer
263 views

Intro to proofs in real analysis 3

Prove that for real numbers $x,y$ with $x< y$, there is a rational and an irrational between $x$ and $y$ in the following cases: a) when $x< 0< y$; b) when $x< y \le 0$. For a) this is ...