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

1
vote
0answers
20 views

How do I represent these complements in membership tables?

I couldn't find examples of some of these elsewhere, so I'm just kind of guessing here. I'm fairly certain I've made a mistake somewhere, particularly the columns with complements. I've placed ...
1
vote
2answers
26 views

Is this conclusion via rules of inference correct?

Use rules of inference to show: ∀x(P(x) → Q(x)) premise ∀x(Q(x) → R(x)) premise ¬R(a) premise ¬P(a) conclusion I have a lot of trouble with these sort of questions and was wondering if I did this ...
-1
votes
2answers
27 views

Proving by contradiction (6/9)

I have been given a statement that I need to prove using the contradiction method and I am just a little unsure of how to go about setting this up and executing. Here is the statement: If x is any ...
3
votes
1answer
66 views

How many ways are there to pick a collection of 12 coins from piles of pennies, nickels, dimes, and quarters?

How many ways are there to pick a collection of 12 coins from piles of pennies, nickels, dimes, and quarters? a) Assuming that each pile has at least 12 or more coins. For this one, I got CR(4,12) =...
0
votes
3answers
36 views

Define the relation $R\subset \mathbb{ℕ} × \mathbb{ℕ}$

I'm working on a task I dont really understand. It says "Define the relation $R\subset \mathbb{ℕ} × \mathbb{ℕ}$ by: $R = \{(a,b) \in \mathbb{N} : a-2 \le b \le a+2\}$. Draw the graph of the ...
0
votes
0answers
31 views

Closure of Poset $Q_n = \{x : x \mid n\}$

Let $(S, <)$ be a poset. A smallest poset $(S', <)$ is called a closure of poset $(S,<)$ iff $S$ is a subset of $S'$, $\operatorname{glb}(x,y)$ is in $S'$, and $\operatorname{lub}(x,y)$ is in ...
0
votes
3answers
60 views

Solving a recurrence relation with n squared

I have trouble solving the following recurrence: $$a_{1}=1, a_{n}=a_{n-1}\cdot n^{2}$$ for $n>1$. It seems somewhat untypical to me, could you give me some general advice on dealing with such ...
0
votes
2answers
43 views

For all real numbers x and y there is a real number $z$ such that $x + z = y − z$.

To Prove: For all real numbers $x$ and $y$ there is a real number $z$ such that $x + z = y − z$. Proof: $x+z=y-z \Rightarrow y-x=2z$. Since $y$ and $x$ are real numbers, $2z$ is also real. Therefore ...
2
votes
2answers
58 views

Modulo: Calculate really large numbers without a calculator

working on a task: "Recall that $a \equiv b~[n]$ means that there exists an integer $k$ suck that $b = a + k \cdot n$. Are the following claims true or false? 5.a) $3 \equiv 5~[10]$ 5.b) $4 \...
3
votes
3answers
60 views

Truth Table - implies false

I'm work with a task where I am not exactly sure if I proceed right. The task is saying: "We define the operation $\oplus$ by $a \oplus b = (a \wedge \neg b) \vee (\neg a \wedge b)$. Give the truth ...
-1
votes
1answer
42 views

Time complexity (in Θ –notation) in terms of n [closed]

I am struggling quite a bit trying to solve these and any help would be greatly appreciated. a) ...
0
votes
1answer
32 views

Tower of Hanoi containing 2n disks with reproduced order

This is exercise 11b from Concrete Mathematics book. I know how to solve problem with Tower of Hanoi. I was able to interpret how many movements is required to transfer Tower of Hanoi with 2n disks ...
1
vote
1answer
24 views

What does “induced operations” means in congruence operations

It says: prove that R is a congruence (it means it's a relation of equivalence and it preserves operations) ith respect to sum and multiplication in $\mathbb{R}$. $a,b\in \mathbb{R}: aRb \iff a-b \in ...
-1
votes
1answer
31 views

Finding the Time Complexity in Big theta notation [closed]

sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++; How would I go about finding the time complexity in ...
0
votes
0answers
30 views

Deducing MaxFlowMinCut from Menger

So the MaxFlowMinCut theorem with rational network capacities and (the edge-version of) Menger's theorem for undirected graphs are equivalent, both directions being not too hard. I gather that since ...
2
votes
1answer
43 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
0
votes
1answer
16 views

Nested Quantifiers (And vs Implies)

I would like to understand something regarding the nested quantifiers in discrete math. In the following question part (c): Let $M(x,y)$ be "$x$ has sent $y$ an e-mail message", and $T(x,y)$ be "$...
0
votes
0answers
30 views

Probability // Dice problem [duplicate]

I couldn't figure out the solution of it. Assume we are tossing a fair dice 3 times. Describe the probability space related to this experiment and calculate the probability that we have tossed ...
0
votes
1answer
21 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
3
votes
1answer
47 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
0
votes
3answers
41 views

Comparing the cardinality of (0,1) and (0,1] [duplicate]

Question Consider the intervals of real numbers (0,1) = {x | 0 < x < 1} and (0,1] = {x | 0 < x ≤ 1}. Show that |(0,1)| = |(0,1]| Work I stated that since both intervals are uncountably ...
0
votes
1answer
39 views

Showing the convergence of a difference equation?

Suppose I have some variable $x_t$ which is the value of $x$ at time step $t$. Now, half the time I update it by adding $0.05$ and the other half of the time I update it by multiplying it by $0.95$. ...
0
votes
0answers
14 views

Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
0
votes
0answers
15 views

What is union of $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$

$L=L_1^+\cup L_2^*$ Where, $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$ My attempt: $L=L_1^+\cup L_2^*$ $L=(CSL)^+\cup (CSL)^*=CSL \cup CSL =...
0
votes
1answer
23 views

Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
0
votes
0answers
21 views

First Intersection Of Periodically Repeating Intervals

I have a set of coupled tasks, let's say $M$ of them. The $ith$ coupled task is represented as the following 3-tuple $\{A_i,D_i,B_i\}$ where $A_i$ represents the time it takes to perform the first ...
0
votes
0answers
27 views

Complexity of some contact circuit

How to prove that for every boolean function $f$ of $n$ variables there exists a (1, 2)-contact circuit $\Sigma_f$ (i.e. with one input and two outputs), implementing boolean function system $(f, \...
2
votes
2answers
39 views

Number of possible routes through n countries and 2n cities, with restrictions

Someone is planning a round-the-world trip that involves visiting $2n$ cities, with two cities from each of $n$ different countries. He can choose a city to start and end the journey in, with ...
0
votes
3answers
58 views

Number of Surjective functions. How does $2! S(r, 2) = 2^r−2$ for $|A| = r, |B| = 2$ where $r \ge 2$?

Currently prepping for a Discrete Mathematics exam and stumbled across a question from last year's exam: Suppose that $|A|= r$ and $|B|=2$, where $r \geq 2$ . Find all values of $r$ for which the ...
0
votes
6answers
70 views

Is the following function bijective?

Is this function bijective? Bijective means both onto and 1 to 1 $$ F(x) = \frac{x^2+1}{x^2+2} $$ I'm not sure how to go about this. Edit: The domain is ${\rm I\!R}$
1
vote
1answer
35 views

Prove that $\lambda(f) = o(2^n)$ for almost all boolean functions

How to prove that $\lambda(f) = o(2^n)$ for almost all boolean functions $f$ of $n$ variables? Here $\lambda(f)$ denotes minimal length (i.e. count of terms) of all possible disjunctive normal forms (...
1
vote
0answers
24 views

Lower bound of DNF terms count for some symmetric boolean function

Consider boolean function $s_n^{[r,\,n - r]}\colon \{0,1\}^n\rightarrow\{0,1\}$ defined as follows: $$ s_n^{[r,\,n - r]}(x_1, ..., x_n) = 1 \iff |\{x_i: x_i = 1\}| \in [r,\,n - r] $$ (in other words,...
3
votes
3answers
138 views

Problem solving a word problem using a generating function

How many ways are there to hand out 24 cookies to 3 children so that they each get an even number, and they each get at least 2 and no more than 10? Use generating functions. So the first couple ...
5
votes
2answers
158 views

Confusion about event in a sample space.

I am a beginner in probability and counting. I am reading an open course by MIT. While reading the introductory chapter I am stuck in one conceptual doubt, if I understand correctly an event is the ...
1
vote
0answers
21 views

How to solve complicated floor function equations?

I have been thinking about solving equations involving several groups of floor functions. My research on solving floor function equations has only shown sums of individual floors, such as: $\lfloor ...
0
votes
1answer
21 views

How to write the formula in Disjunctive Normal Form (DNF)?

Formula is: $$\emptyset=((p \lor r)\to q)\land (q\to r)$$ This is what I've already done: $$(p \lor r) \lor \lnot q)\land (q \lor \lnot r)$$ $$(p \lor r \lor \lnot q)\land (q \lor \lnot r)$$ and ...
2
votes
1answer
35 views

Show that a 2k regular graph has a matching of size at least k-1

Let $H$ be a 2k-regular graph with $n=4k+1$ vertices (and thus $m=k(4k+1)$ edges). Show that $H$ has at least k-1 independent edges (or that there exists a matching of size at least k-1 in $H$). If ...
0
votes
1answer
29 views

Let $X$ denote an infinite set. Is every partitioning of $X^2$ induced by an associative operation $f:X^2 \rightarrow X$?

Proposition. Let $X$ denote an infinite set. Then for each partitioning $\Pi$ of $X$, there exists a function $f : X \rightarrow X$ whose coimage is $\Pi$. I'd like to know whether the analogous ...
1
vote
0answers
26 views

Constructing a bijection between two sets of pairs

I am working on a problem in a different area and the following problem appeared. Let numbers $j,k,l \in \mathbb{N}_0$ be fixed. I need to construct a bijection between the sets $$\{(A,B) \in \...
0
votes
1answer
49 views

Solving Chinese Remainder Theorem Algebraically

I am doing a practice problem for my final which asks: Solve the following Chinese Remainder Theorem: $$ x \equiv 2 \pmod{3}, \\ x \equiv 3 \pmod{5}, \\ x \equiv 5 \pmod{7}, \\ x \equiv 7 \pmod{11} \...
0
votes
0answers
20 views

Regular expression that defnes the set of all words

I'm trying to write a regular expression that defines the set of all words written in lower case characters and digits that contain a binary number. My idea: $(\varepsilon |[a-z]^{*})(\varepsilon |(...
0
votes
1answer
15 views

Regular expression that begins and ends with digit

I'm trying to write a regular expression that defines all words written in lower case characters and digits that begin with a digit, end with a digit and contain total of 4 digits. My idea is : $[0-...
1
vote
1answer
21 views

Is the hypercube graph $Q_n$ k-factorable for k=modn?

Definition of k-factorable graph: https://en.wikipedia.org/wiki/Graph_factorization I have proved that a hypercube of any dimension has a perfect matching, thus also a 1-factorization. Can it be ...
0
votes
0answers
35 views

Sticky boots and modular arithmetic: Find the formula!

Suppose a trek begins and on this trek the road is paved by squares with labels on them. The warning sign next to the beginning of the first square, labeled $1$, states: Beware that due to natural ...
0
votes
0answers
20 views

Prove that every maximal outerplanar graph has a 3-coloring

A maximal outerplanar graph is an outerplanar graph (which is a graph with a planar drawing with all vertices belonging in the outer face), where adding any edge would make it stop being outerplanar. ...
1
vote
1answer
63 views

Can we logically analyze mathematical theorems as if-then statements?

Many theorems in math have an if-then form. For example: "If a polynomial is of $n^{th}$ degree, then it has $n$ roots. In my other question, I learned that in order to analyze statements using truth ...
1
vote
1answer
64 views

Are standalone statements conventionally considered to imply truth?

From what I understand, the statement $\exists x(p(x) \vee q(x))$ in the English language sounds something like this: "There exists $x$ such that $p(x)$ or $q(x)$". But this sounds like an incomplete ...
0
votes
1answer
45 views

Regular language or not?

Let $L$ be a regular language over the alphabet $A=\{0, 1\}$. Is it true that the language of strings $0^n$, where binary representation of n $\in L$, is regular?
0
votes
0answers
9 views

Prove that for any PDA there is another PDA that accepts exactly the same language bu has only one POP state.

Prove that for any PDA there is another PDA that accepts exactly the same language but has only one POP state. My attempt: Let the counter example $L=\{wcw^R|w\in(a,b)^*\}$ and string of $L$ is $...
0
votes
1answer
11 views

Possible strings of Kleene star of $L = \{a^nb^n|n≥1\}$

Consider the following CFL. $L = \{a^nb^n|n≥1\}$ Then which of the following string can be accepted by the kleene star of the language. $aaabbb$ $aabbaaabbab$ $abbaab$ $λ$ My attempt: The ...