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

2
votes
2answers
35 views

How can I prove that $(a + b )\oplus(a + c)$ is not possible to simplify. Or is it?

I was trying to simplify the following expression $(a + b )\oplus(a + c)$, where $+$ is just a simple addition of two numbers and $\oplus$ is a binary xor operation. By simplifying I mean exanding or ...
0
votes
4answers
35 views

How many IT Majors must be American?

In a class of $40$ students who are either IT Majors or Americans, there are $29$ IT majors and $32$ Americans. How many IT Majors must be American? I SOMEHOW know how to solve this problem but what ...
3
votes
1answer
2k views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
1
vote
1answer
25 views

Using generating function to solve initial value problems

I have a hard exam coming up and something I've struggled with since week 1 of semester is initial value problems. How would I go about solving: (a) $u_{n} - 7u_{n-1} = 3 * 7^n : u_0 = 4 $ (b) ...
0
votes
0answers
19 views

Finding a general solution of recurrences

I am unsure how to even start the questions :S I need to learn this stuff for the final exam of my subject and its hard to find a tutorial on how to answer this type of question.
2
votes
2answers
22 views

Logic Puzzle (Valid and Invalid Arguments)

I have been given a logic puzzle and I am having a tough time figuring out how to set it up and solve. Here is the puzzle: a) The Statement "If Dr. Jones did not commit the murder then neither Ms. ...
3
votes
1answer
69 views

Why are Duals of Two Equivalent compound propositions Equivalent?

I know that if we have two equivalent propositions p and q then p* and q* will also be equivalent where p* and q* are duals of p and q respectively. I am looking for some explanation to why duals of ...
0
votes
2answers
41 views

Logical Equivalences not using a truth table

I am tasked by using logical equivalences to show [q and ~(p implies q)] is tautology or a contradiction. I know that by setting up a truth table that it is false. I did a truth table and confirmed ...
3
votes
1answer
228 views

Showing that the McCarthy Function is a well-defined function from the set of positive integers to the set of positive integers

For those of you who aren't familiar, the McCarthy Function states that $M(n) = n − 10$ if $n > 100$ and $M(M(n + 11))$ if $n \leq 100$ (a recursive function). I'm trying to prove that this ...
0
votes
0answers
16 views

Turing and Post–Turing machine [on hold]

Got an interesting question from my professor of mathematical logic. He asked as to prove this, as he said, "theorem": "For every Turing's machine exists Post–Turing's machine, which creates a ...
0
votes
1answer
126 views

True and false probability question

I'm stuck on how to do this problem. Given $p>0$ when husband and wife independently give correct answers Let $C$ denote the correct answer and $p > 0$, so let $P(C) = p$ and $P($NOT $\,C) ...
0
votes
0answers
15 views

Simple question about binary relation [on hold]

P - binary relation. P $\subseteq$P - binary relation. P $\subseteq$ $R^2$. P = {(x,y)| y = |x|}. 1) Find range of definition. I guess that R 2) Find all possible values. I guess that R+ Prove by ...
0
votes
2answers
24 views

How to simplify this logical expression?

Using logical laws, I would like to simplify the following expression: $\neg a \lor \neg b \lor (a \wedge b \wedge \neg c)$ 1) Distribution law: $(\neg a \lor a) \land (\neg a \lor b) \land (\neg ...
0
votes
1answer
40 views

How many integer numbers from 0 to 100000 contain 2 or more digits 5?

How many integer numbers from 0 to 100000 contain 2 or more digits 5? I know that I need to apply some kind of formula to this problem, but I can't choose which one. Can you please help me?
-1
votes
1answer
17 views

Discrete Maths Relations on the set {1,2,3,4}

I just want to make sure that I am doing these correctly. Here is what I have: Reflexive, symmetric, antisymmetric and transitive: And i have - {(1,1) (2,2) (3,3) (4,4)}. not Reflexive, not ...
1
vote
1answer
76 views

factoring cubic polynomial equation using Cramer's rule.

1) I have question about factoring cubic polynomials. In my note it says "Any polynomial equation with positive powers whose coefficients add to 0 will have a root of 1. Another, if sum of the ...
1
vote
1answer
29 views

Find the range of the function $f(x) = 4x + 8$ for the given domain $D = \{-5, -1, 0, 6, 10\}$

The question is to find the range of each function for the given domain $f(x)=4x+8$, $D=\{-5, -1, 0,6, 10\}$. Is the range just $R= \{-12,4,8,32,48\}$ or am I mistaken? Could you elaborate why my ...
-5
votes
0answers
34 views
0
votes
1answer
18 views

non-homogeneous Recurrence Relation for f(x) = n^2

Im having some trouble with a non-homogeneous Recurrence Relation. My question is: $u_{n} - 5u_{n-1} + 4u_{n-2} = n^2$ My working out so far: $r^{2}-5r+4r = 0$ = (r-1)(r-4) Giving the roots 1 and ...
2
votes
4answers
87 views

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer.

Prove that $n^4-n^2$ is divisible by $8$ if $n$ is an odd positive integer. I'm supposed to use proof by induction, but I failed at it miserably. So far I have this: $$(n^4) - (n^2) = ...
1
vote
0answers
54 views

When does the dual of $s =s$?

Why I believe this is not a duplicate: The linked question might be the same, but the accepted answer is only a partial answer, because it gives no reason as to why those are the only solutions. Since ...
1
vote
2answers
491 views

Cardinality of a set of matrices

Consider the set $S$ of $3\times3$ matrices with binary coefficients, that is, the coefficients are integers modulo $2$. Compute $|S|$. I am not sure what is this question trying to ask. Am I ...
5
votes
1answer
59 views

number of ways to partition an integer.

A partition of a positive integer n is a way of writingn as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 ...
0
votes
2answers
60 views

Is $y \in\{f(x)\mid x \in X\} ⇔ f(x) \space ∃ x \in X$ true?

Definition 9 $f(A) =\{f (x) \mid x\in A\}$ The following is from the proof of $f(\bigcup_{\gamma \in \Gamma}A_{\gamma})$ = $\bigcup_{\gamma \in \Gamma}f(A_{\gamma})$. $$y \in f \left( ...
0
votes
0answers
43 views

Stirling number of the second kind. [on hold]

I cannot utilize the hint anywhere.. Please help. Let $S(n,k)$ be the Stirling number of the second kind. Show algebraically and combinatorially that $$S(n,k)=\sum1^{a_1-1}2^{a_2-1}\cdots ...
0
votes
1answer
64 views

What does ± times ± equal? [on hold]

What does ± times ± equal as we know that - * - = + and + * + = + ? I'm sorry for this layman question I'm purely curious. Thanks.
1
vote
1answer
59 views

Where in the proof of this theorem shows “If (x, y)$\in f$ and (x, z) $\in f$, then y=z.”?

Definition 8. Let X and Y be sets. A function from X to Y is a triple (f, X, Y), where f is a relation from X to Y satisfying (a) Dom(f) = X. (b) If (x, y)$\in f$ and (x, z) $\in f$, then y=z. ...
1
vote
1answer
406 views

How many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads?

I am trying to figure out how many different necklaces can be make from 8 blue beads, 3 green beads, and 3 brown beads. I understand how to do the problem with two colors, but I am struggling to ...
1
vote
2answers
35 views

In how many ways can $5$ students and $3$ teacher sit around a table so that no two teachers are together?

In how many ways can $5$ students and $3$ teacher sit around a table so that no two teachers are together? My attempt: $5$ student can sit $(5-1)!$ in round table. A teacher can sit between ...
0
votes
3answers
34 views

How many numbers of $7$ digits can be formed with the digit $0,1,1,5,6,6,6$.

How many numbers of $7$ digits can be formed with the digit $0,1,1,5,6,6,6$. My attempt: Seventh place, total number of possibility is $=\frac{6!}{2!\times 3!}=60$ ways. Sixth place, total ...
0
votes
0answers
33 views

Decrease distance between max and min

Let $a:=(a_1,a_2,\ldots,a_n) \in \mathbb{Z}^n $ and $k \in \mathbb{N}^*$, with $$f: \begin{cases} \hfill \mathbb{Z}^n \times \mathbb{N}^* \hfill &\rightarrow \mathbb{Z}^n \\ \hfill ...
0
votes
0answers
19 views

Simplifying logical expression using logical laws

I simplified the logical expression: $(z \land w) \lor (\lnot z \land w) \lor (z \land \lnot w)$ using logical laws following these steps: 1) Absorption Law: $(z \land w) \lor (\lnot z \land w)$ ...
2
votes
1answer
28 views

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$.

How many $3$ digit different number that will be divisible by $5$ can be formed from the digit $0,2,3,4,5,6$ lying between $100$ and $1000$. My attempt: Divisible by $5$ is possible only when ...
0
votes
1answer
43 views

How to know the contrapositive of a compound logical expression?

In simple expressions like: $p \implies q $ the contrapositive would be: $\lnot q \implies \lnot p$. But in other cases where the expression gets more complex: ($p \land q) \implies (\lnot q \lor p)$. ...
1
vote
4answers
69 views

Recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, then find $a_{20}$

Consider the recurrence relation $a_r+6a_{r-1}+9a_{r-2}=3$, given that $a_0=0, a_1=1$. Let $a_{20}=x\times10^9$, then the value of $x$ is______ . My attempt: $a_r=3-6a_{r-1}-9a_{r-2}$ I ...
0
votes
1answer
15 views

Can you denote a family $F: N → P(R)$ such that $F(n) = R\space, ∀n ∈ N$ in a set builder notation?

I don't fully understand the meaning of the following underlined explanation. Can you denote $F: N → P(R)$ such that $F(n) = R\space, ∀n ∈ N$ in a set builder notation? Definition A family of ...
1
vote
2answers
9 views

Find total number of relations that are equivalence as well as partial order set

Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements. My attempt: As equivalence relation has property reflexive, symmetric ...
0
votes
2answers
39 views

How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies?

A cookie store sells 6 varieties of cookies. It has a large supply of each kind. How many ways are there to select $15$ cookies if at most $2$ can be sugar cookies? For my answer, I put $6 \cdot ...
0
votes
0answers
34 views

Prove by contradiction that any sequence of five distinct integers must contain a 3-chain.

Define a $3$-chain to be a (not necessarily contiguous) subsequence of three integers, which is either monotonically increasing or monotonically decreasing. We will show here that any sequence of five ...
-1
votes
0answers
16 views

log - log plot. [on hold]

Show that the relation $$N(s) = \frac{a}{s^α}$$ will show a linear dependency in a log - log plot. Can you please help me about choosing values for $s$ and $N(s)$? It's related to power law.
-2
votes
0answers
11 views

Formal Specification - discrete math for Stack

I need to define a series of Abstract Data Types (ADT) using discrete mathematics for a Formal Specification. For example, to define Empty of a Set ADT I would do the following ...
0
votes
0answers
11 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
0
votes
1answer
706 views

Size K subset sum problem?

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer ...
0
votes
0answers
18 views

Lattices and Boolean algebra

I have read in a text book that the set of natural numbers form a lattice under divisibility. How can it possibe, since there is no upper bound and therefore a Sup of the set?
1
vote
0answers
13 views

The existence of a cycle in a graph

Let C and D will be different cycles in the graph G, and e - common edge to the cycles of C and D. Show that a graph G contains a cycle not passing through the e. I think, it's not easy task, because ...
1
vote
0answers
30 views

In how many ways consonants and vowels alternatively for letters of word `CONSTITUTION`. [on hold]

In how many ways consonants and vowels alternatively for letters of word CONSTITUTION. My attempt: The word 'CONSTITUTION' has 7 consonants (C N S T T T ...
0
votes
0answers
14 views

Partition of set [list]

i have a question that: "List all the partition of set {1,2,3,4}" i have solved this using the definition: "A partition of a set S is a collection of disjoint non empty subsets of S that have S as ...
1
vote
1answer
30 views

generating function for $0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,\dotsc$

I know that the generating functions is $$x + x^4 + x^7 + x^{10} +\dotsb$$ and then we can factor out a $x$ to get $$x(1+(x^3) + (x^3)^2 + (x^3)^3 + \dotsb )$$ Now I need my answer in closed form ...
0
votes
1answer
37 views

What is the order of

What is the order of the following: $$\frac{(33x^{7}+6)(x^{2}+3)}{\sqrt{x^3+7x^2-x+5}}$$ Would it be $$\Theta (x^{\frac{17}{2}})$$
3
votes
1answer
57 views

Question about regular languages

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?