Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit 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.

0
votes
0answers
16 views

What is a dedekind cut?

I have searched on google but the explanations seem to be a little too abstract for me. Could someone explain it in as lamen terms as possible?
0
votes
0answers
13 views

Mean difference

I have two sets of sample data with the first one having the mean of 100.1 and the second set having the mean of 192.1 ...
0
votes
0answers
9 views

Solving/Proving Composite Functions

Suppose f is a function from X to Y and g is a function from Y to Z. Prove the following: g o f is one-to-one, then f is one-to-one. How would you prove this. I don't need like the whole answer. I ...
0
votes
1answer
14 views

Parsing a sentence using logical operators (Logical expressions)

Parse the logical structure "If everyone passes the quiz, Mr. Johnson will play his guitar." -Use q as a constant to represent the quiz -Use g as a constant to represent Mr. Johnson's guitar -Use ...
2
votes
1answer
11 views

When will the complement of a hypercube be bipartite?

I know that every hyper cube is bipartite, but I am lost when it comes to their complements... I'm try to go off the theorem that "A graph is bipartite if and only if it does not contain any odd ...
0
votes
1answer
11 views

Translating to logical notation

How would you change "p is a prime." and "x is an odd number" into a logical notation without defining any new predicates where the domain is all natural numbers. Are we supposed to use P (x)?
-2
votes
0answers
29 views

Translate the following statements into logical notation, just using common mathematical symbols where the domain is $\mathbb N$ [on hold]

Translate the following statements into logical notation, without defining any new predicates (just use common mathematical symbols), where the domain is the natural numbers. (a) x is a perfect square....
1
vote
1answer
8 views

Approximate Numerical Convolution with a Singularity in the kernel

Although similar to the other Convolution of function with singularity question, it is different as I am suggesting an approximation method but asking how to make it more rigorous. I asked on Signal ...
0
votes
1answer
15 views

Laws of Equivalence with 4 terms

Use equivalence laws to show that $(A ∨ C) ∧ (B ∨ C) ∧ (A ∨ D) ∧ (B ∨ D)$ and $(A ∧ B) ∨ (C ∧ D)$ are logically equivalent. I am trying to figure out how to go about this problem. The part that ...
-1
votes
1answer
37 views

Need some help regarding the family of $\mathbb{Z}_n = \lbrace 0, 1, 2, 3, \ldots, n-1 \rbrace$ [on hold]

I have a couple of questions about some problems in my discrete mathematics text, they are as follows. I'm not sure how to even approach these so anything helps. 1: Let $a ∈ \mathbb{Z}_n$ and $a \neq ...
2
votes
2answers
54 views

Prove that $ |x-a|<b \iff x∈(a-b,a+b)$

I am not sure if I am doing this correctly, my forward proof is: Since $|x-a|$ is an absolute value function, it can be defined as $|x-a|:= \max\{(x-a),-(x-a)\}$ . Let $S={(x-a) ∈ ℝ}$ and $b ∈ S, b&...
-8
votes
1answer
51 views

Do my proof for me. [on hold]

Please prove the following product:
-2
votes
1answer
26 views

discrete mathematics floor and ceiling function truth set predicate

this is the question ack.imgur.com/EyWu4.png Would anyone be able to give a solution to this question?
1
vote
1answer
39 views

Exact meaning of ∃x

I am a little bit confused about the meaning of quantifier ∃x Some definitions make it sound like There is exactly one x and some make it sound like There is at least one x I have this ...
4
votes
2answers
31 views

What is logical consequence and logically equivalent in discrete math?

I'm having a difficult time understanding what the meaning are with these two. Is it correct if I have (P ⇒ Q) ∧ P and I say Q is a logical consequence. This means that whatever P may be T or F the ...
0
votes
2answers
58 views

Mathematics - Number Theory [on hold]

How to determine if a positive integer $N$ is a sum of two exact powers of two or not? $N=2^m + 2^n $
1
vote
1answer
31 views

Simple induction proof, debugging…

I'm getting the hang of induction proofs but just can't seem to complete the inductive step. Meanwhile i beleive what i have made so far is correct. I have a quantity : $n∈N$ And a statement:$$\sum\...
1
vote
0answers
25 views

Computing a Powerset that contains a set

I understand the concepts of power-sets pretty easily, and have done some substitution to make things easier, but I'm not sure of my answer. I have the set {{a,b},ε,x} I replaced {a,b} with c, so ...
0
votes
0answers
23 views

Steps for proving proposition given the conditions.

When a question asks you to give an example in the domain of real numbers where $\forall x$, $\forall y$, $\exists z$ P(x, y, z) is true, but $\forall x$, $\exists y$, $\forall z$ P(x, y, z) is ...
0
votes
1answer
39 views

(Hard) Counting problem with recurrence [on hold]

Let $f(n)$ be the number of integer sequences with length of n which start with $0$, end with $0$ and every two adjacent numbers in the sequence has the difference of $1$ (i.e. for every $1\leq i \leq ...
-2
votes
0answers
41 views

Use equivalence laws to show that ¬p → (q → r) and q → (p ∨ r) are logically equivalent. [on hold]

Use equivalence laws to show that ¬p → (q → r) and q → (p ∨ r) are logically equivalent. (Show the intermediate steps and specify the equivalence laws.) ¬(¬p) V (q → r) implication law p V (q → r) ...
1
vote
2answers
36 views

How to prove the equation for the union of two sets?

Given the Sets A and B, how do you prove that $|A \cup B| = |A| + |B| - |A \cap B|$ I know that if the sets are pairwise disjoint, the last term would be 0 and hence not be necessary for the equation....
4
votes
1answer
61 views

Sum of the square of a recursively defined function

This problem is from a math competition from 1994. I have been having trouble working with this problem: Let $f(1) = 1, $ and $f(n + 1) = 2\sqrt{f(n)^2 + 1}$ for $n \geq 1$. If $N \geq 1$ is an ...
0
votes
1answer
25 views

How does modulo operation work in terms of the remainder of long division with negative dividends?

I'm trying to figure out how the modulo operation works using long division with negative dividends. I know that $-1 \bmod 10 = 9$. But I can't figure out why. For positive dividends, it's ...
0
votes
1answer
39 views

Where Have I Gone Wrong? 2 Combinatorics Problems

Three physics books, five biology books, a dictionary and two comic books are stored on a bookshelf. (a) Determine the number of possible arrangements where the two comic books are not next to each ...
5
votes
2answers
61 views

Explanation for counter-intuitive discrete probability results

Suppose there're two players $A$, $B$ playing a dice game, $A$ has a normal dice whose faces are numbered 1 to 6, $B$, on the other hand, has a (regular) icosahedron dice with faces numbered 1 to 20. ...
-1
votes
1answer
86 views

predicate logic statements, discrete math [duplicate]

I have been given an assignment question to convert english statements into predicate logic statements. I have no idea where to begin Loves(x, y): x loves y Reindeer(x): x is a reindeer *we are ...
0
votes
1answer
32 views

Rational probabilities and discrete paths on a lattice

Consider an urn containing $c$ elements, $b$ of which are black. If we perform $n$ trials with replacement of one element at a time from the urn, the probability to get $n$ times a black ball is $\...
0
votes
1answer
18 views

How to determine the following sets (ex a ∪ {∅}) [on hold]

Help! I don't know how to determine the following sets The question was: Let A={∅,{∅},{{∅}}. Determine the following sets a∪{∅} a∩{∅} a∩{{∅},{∅,{∅}}} a∪{{∅},{∅,{∅}}}
-3
votes
0answers
21 views

Prove the distributive law: Discrete Mathematics [on hold]

We're supposed to prove the distributive law and I can't seem to figure it out. I need to prove: A and (B or C) = (A and B) or (A and C) A or (B and C) = (A or B) and (A or C)
-2
votes
1answer
103 views

Proof: For what positive integers k is it the case that the complement of a k-cycle is also a k-cycle? [on hold]

I am really confused and would really appreciate help regarding this question. For what positive integers k is it the case that the complement of a k-cycle is also a k-cycle? Prove your answer.
2
votes
3answers
30 views

Modular Multiplicative Inverses

I'm in a cryptography and struggling with understanding how the Euclidean Algorithm necessarily works for finding multiplicative inverses. We haven't actually covered the algorithm yet, just a way to ...
1
vote
2answers
35 views

Discrete math contrapositive statment of universal statement

I have researched many sides about it but could not find exact answer. My professor asked me to write contrapositive statment and convert statment of statment “ all red cars are fast “ Meanwhile he ...
1
vote
2answers
95 views

Predicate Statements— Every person loves at most only one reindeer

I was given a question by my professor during lecture today, to translate into predicate logic statements, "Every human loves a reindeer, but every human loves at most only 1 reindeer", without ...
4
votes
5answers
294 views

If $n$ is such a positive integer, that $8|n^2$, then $4|n$

I'm new to the subject of discrete mathematics. This statement is either true or false and it has to be proved. I've struggled with this exercise for quite a while, and this is what I came up with: ...
1
vote
2answers
51 views

How to prove the following statement using direct proofs.

I'm currently in Discrete Mathematics and I'm currently on the chapters about direct proofs. I'm working on some practice problems and got stuck on this currently one. Any help would be much ...
0
votes
1answer
23 views

What does the “?” mean in generated language grammar?

I know $a^*$ means that a string could be composed of zero to infinite $a$'s, and $a^+$ means one or more $a$'s. But the professor posted this question... Given the regular expression $b?a(a|b)ab?$...
0
votes
0answers
16 views

Estimate based on data

I have a set of data containing the price of stores where y = 100.4,560.2,432.1,600.2,231.5,706.6 and I want to calculate the estimate of the average price of ...
-4
votes
0answers
18 views

can you help me simplify this logic problem? [on hold]

could you help me with this discrete math problem that is logic related? simplify the following, using laws and expressions such as absorption,... ( p V q) <-> ( p -> q)
0
votes
0answers
7 views

Complex of graphs having domination number greater than $k$

I am studying discrete Morse theory and as an example, discrete Morse theory is used to obtain the homotopy type of the complex of non-connected graphs of $n$ vertices. I also read that this kind of ...
-4
votes
0answers
18 views

prove a regular graph is perfect matching by using Tutte theorem [on hold]

Let $k>0$ and let $G$ be an $k$-regular graph such that for any $S\subseteq V(G)$ with $|S|$ odd, $e(S,\bar{S})\ge k$. Show that $G$ has a perfect matching. this is an excise proved by my ...
-4
votes
0answers
29 views

How to solve this discrete math basic questions? [on hold]

I am new to this topic, so it would be great if you could give a bit of explanation as well. So the question is: p: There is iceberg in the harbor q: Whales are spotted near signal hill r: Boat ...
-3
votes
0answers
30 views

Hasse diagram for $\{2,3,4,5,6,7,8\}$ with $a \le b$ iff $a$ divides $b$ [on hold]

I'm trying to draw the Hasse diagram for this poset $A=\{2,3,4,5,6,7,8\}$ with partial relation that $a \le b$ iff $a$ divides $b$. I'm having problems with 1 not being in the set because there no ...
-1
votes
0answers
39 views

Proving that $F: [A\to [B \to C]] \to [(A \times B) \to C]$, such that $F(f)(x,y) = (f(x))(y)$, is surjective. [on hold]

I know that to prove this. I need to find a function $g$ in the domain of $F$ such that for all functions $h$ in the codomain, F(g) = h. I'm having a ton of trouble determining what this function g ...
0
votes
1answer
20 views

bipartite graph has a matching such that all vertices on one side are matched.

Let $G$ be a bipartite graph with partition sets $V_1,V_2$. Suppose for any edge $v_1v_2$ with $v_i \in V_i$ for $i=1,2$, we have $d(v_1) \ge d(v_2)$. Show that $G$ has a matching such that all ...
2
votes
0answers
51 views

Inclusion/exclusion, at least and exactly arrangements?

The question is given the word "ARRANGEMENT", a) find exactly 2 pairs of consecutive letters? b) find at least 3 pairs of consecutive letters? I have the answer given from the tutor but it doesn't ...
3
votes
2answers
53 views

Rising Factorial and Stirling number of the 1st kind

Is it true that $$(x+1)^{\bar{n}}= \sum_{k \ge 0} \sum _{i=0}^{n} {i \choose k}s_{n,i}\,\,x^k \,\,\,\,?$$ where $s_{n,i}$ is the Stirling number of the first kind and the $\bar{n}$ denote rising ...
1
vote
1answer
21 views

Is it possible to solve $n=\text{floor}\left(\frac{L-1}{k}\right)$ for $L$?

Is it possible to solve $$n=\text{floor}\left(\frac{L-1}{k}\right), n,k,L \in \mathbb{Z}^+$$ for $L$?
1
vote
2answers
40 views

How many ways are there for 50 people to divide them into three groups, A, B and C such that each consists of 20, 18, and 12, respectively?

I have tried to solve this problem but I can not figure out where to start. Any help would be appreciated. Thanks, EDIT: After another attempt I am leaning towards the answer $\frac{50!}{20!18!12!}$ ...
1
vote
2answers
36 views

Is it the case that certain probability problems can only be solve by listing events

Just wondering if there’s a more systematic approach for those problems using combinatorics, (combinations or permutations) For instance: The probability that the sum of the numbers of 3 rolled dice ...