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
4answers
29 views

Verifying a proof of subsets.

Prove or disprove. If $f(A) \subseteq f(B)$ then $A \subseteq B$ Let y be arbitrary. $f(A)$ means $\exists a \in A (f(a)=y)$ $f(B)$ means $\exists b \in B (f(b)=y)$ but $\forall a \in A \exists !...
1
vote
2answers
189 views

Definition of identity law in the laws of proposition

I'm sure this is an easy one but I'm struggling. From my notes, there's this example on how to simplify a proposition using proposition laws: p $\lor$ (p$\land$ q) $\equiv$ (p $\land$ t) $\lor$ (...
1
vote
1answer
122 views

Connected components of a graph

If we have a graph $G$ and $e$ is an edge in this graph. Now I want to show that $G − e$ has at most one more connected component than G.Now if we remove one vertex from G, by how much can the ...
0
votes
1answer
48 views

What set is this? (Z \ {0})

I'm not sure what this set would look like. Integers divided by the set of 0? Is it Z over {0} or {0} over Z?
0
votes
1answer
82 views

Is $P=NP$ an $NP$-complete problem?

Is $P=NP$ an $NP$-complete problem? In other words, is it possible (and does it make any sense) to show that proving $P=NP$ (or $P\neq NP$) cannot be done in polynomial time? I am not even sure it ...
1
vote
0answers
25 views

Determine existence of matroid with some barrier given

Let $E$ be a finite ground set. Let $\mathcal{L}$ (as lower barrier) and $\mathcal{U}$ (upper) be subsets of $2^E$. How can we determine whether there is some matroid $\mathcal{M}=(E,\mathcal{I})$ ...
1
vote
2answers
35 views

the probability that there's an actual tornado if the alarm goes off (discrete math)

TornadoGuard: If there is a tornado in the users's area, an app has 99% probability of warning the user with a loud alert sound. On the other hand, it has 1% probability of playing the loud alert ...
-1
votes
1answer
202 views

Combinatorics of a quiz consisting of 10 true and false questions [closed]

A quiz consists of 10 true and false questions, each question is answered with either true or false (no blank questions) How many of the possible answer sequences begin and end with the answer True? ...
1
vote
3answers
77 views

Discrete Mathematics - Determine if the following function is onto, one to one or both.

I have a test next week and im going through a sample test. One of the questions involves determining if the function is one-to-one, onto or both. I managed to proof its not one-to-one but am stuck on ...
0
votes
0answers
27 views

Please help with probability counting? [duplicate]

A palindrome is a string whose reveral is identical to the string. For example,110010011 is a palindrome. So are BOB and KAYAK. How many of length n are palindrome? Explain your solution clearly. I ...
3
votes
2answers
48 views

If $(G, ∗, I)$ is a group and $a, b ∈ G.$ Show that $a^3 = I$ if and only if $(b^{−1} ∗ a ∗ b)^3 = I$.

If $(G, ∗, I)$ is a group and $a, b ∈ G.$ Show that $a^3 = I$ if and only if $(b^{−1} ∗ a ∗ b)^3 = I$.
0
votes
0answers
47 views

Example of a relation on a finite set

In one of the exercises, I proved that $R^n+1\subseteq R^n$ for all $n \ge1$ But now I need to give an example of relation on finite set such that $R^3 \subsetneq R^2 $ Here $R^3$ =$R \circ R \circ ...
1
vote
1answer
79 views

Prove for any number n, it is possible to select $X = 2^n$ numbers from $2^{n+1}$ numbers s.t. the sum of X is divisible by $2^n$

Prove, for any natural number $n$, that it is possible to select $2^n$ numbers from any collection of $2^{n+1}$ natural numbers such that that sum of the $2^n$ numbers is divisible by $2^n$. I am not ...
0
votes
1answer
20 views

Use the equivalences to transform the following wff into a CNF

I'm having trouble figuring out how we are arriving at this particular solution Use equivalences to transform the following wff into a CNF. (Conjuctive Normal Form). $(P \rightarrow (Q \rightarrow P)...
0
votes
1answer
38 views

Eulerian graph from vertex subsets

Let $K_{n1,n2,...,n\ell}$, where $\ell \geq 3$, denote a graph for which the vertex set is partitioned into $\ell$ subsets of respective size $n_1, n_2, ..., n_\ell$ and any two vertices are adjacent ...
1
vote
1answer
27 views

How do I correctly show a proof of this implication and refute it's converse?

If there is a valid implication between the two, show the proof. If not, refute it by giving a counter example. 1) $x+5>8$ 2) $\left| x \right| >3$ $$x+5>8\Rightarrow \left| x \right| >...
2
votes
1answer
150 views

Eulerian graph with odd/even vertices/edges

Find an Eulerian graph with an even/odd number of vertices and an even/odd number of edges or prove that there is no such graph (for each of the four cases). I came up with the graphs shown below ...
0
votes
1answer
14 views

Looking to find a lower bound to this term

I have this term I'm trying to bound(below). From numerical experimentation I'm fairly confident that the bound is 1/2. I've been out of school for a couple years and my proof skills have diminished ...
0
votes
2answers
25 views

How do I point out whether the propositions are implying one another?

1) It’s raining but the birds chirp. 2) If it’s not raining then the birds chirp. 3) It’s raining or the birds do not chirp. For each pair of propositions, point out whether the second is implied ...
0
votes
1answer
103 views

Line graph and Eulerian graph

Let $G$ be a simple, undirected and connected graph for which every vertex has degree $r$. Prove that the line graph $G'$ of $G$ is Eulerian. So, basically we have two options for $r$, either it is ...
1
vote
1answer
54 views

Control theory - what method is used to find the discrete time control system here

We are given a car model: $$\dot x = V\cos(a) \quad \dot y = V\sin(a) \quad \dot a = u$$ $V$ some arbitrary number Make an (first order) approximation $$\dot x = V \quad \dot y = Va \quad \dot a = ...
0
votes
3answers
32 views

How do I figure out if these two statements imply one another?

$$x^2>9\Rightarrow |x|>3 \quad \quad |x|>3\Rightarrow x^{ 2 }>9$$ If there is a valid implication between the two, I must show the proof. If not, I must refute it by giving a counter ...
0
votes
2answers
29 views

Set theory : Anti-symmetric but transitive (proof)

The exam practice question is as follows: We call a relation $R$ anti-reflexive iff $\forall a \in A : (a,a) \notin R$ and anti-symmetric iff $\forall a,b \in A : (a,b) \in R \rightarrow (b,...
0
votes
0answers
8 views

Tree decomposition (Citation needed)

Recently, I read the statement "Fix $k\geq 1$, Any tree with at least $k$ edges may be decomposed as a union of edge-disjoint subtrees, each having between $k$ and $3k$ edges" Now I was wondering ...
1
vote
0answers
43 views

chromatic number in a “duo-planar graph”

For the purposes of this task, we will call a "duo-planar" graph, a graph that has been made of joined two planar graphs. More precisely, G is duo-planar, when $E(G)$ can be divided into two sets $E_{...
0
votes
2answers
19 views

Function Properties

The question is as follows: Let $f$ be a function $f : U → V$ , where $U$ and $V$ are non-empty sets. Prove or refute that $f$ is injective iff there is a function $g : V → U$ with $g ◦ f = Id_U$ . ...
2
votes
1answer
35 views

Choosing distinct balls to put into indentical urns.

"There are 10 distinct balls that can be put into two identical urns such that no urn is empty. How many ways can that be done?" I know how to do this question when the urns are distinct (its simply ...
0
votes
3answers
43 views

Am I correct in evaluating this mathematical statement?

Determine whether this statement is $T$ or $F$, or whether this cannot be determined without knowledge of the value of $x$. If the truth value cannot be determined, show one example of a value of for ...
0
votes
1answer
27 views

How to determine pairings table?

For example, you have four players, then the parings are: round1: 1-4, 2,3 round2: 4-3 , 1-2 round3: 2-4, 3-1 So every player plays once against each ...
2
votes
2answers
39 views

Show that $n^{n-3} \ge n!$ for n=9, 10,…

Show that $n^{n-3} \ge n!$ for n=9, 10,... I have tried to n=9 $9^{9-3} = 9^6 = 531411$ $9! = 362880$ So $9^6 \ge 9!$ is true My question is how do I prove it by every for n=9, 10,... by ...
2
votes
2answers
96 views

Prove that there are no primes in the following infinite sequence of numbers: $1001, 1001001, 1001001001, 1001001001001, …$

Prove that there are no primes in the following infinite sequence of numbers: $$1001, 1001001, 1001001001, 1001001001001, ...$$ The sequence can be expressed as follows: $$ f: \mathbb{N}-\{0\} \to ...
0
votes
4answers
82 views

Mathematical Induction for $4 + 10 + 16 +…+ (6n−2) = n(3n +1)$

Use mathematical induction to prove: $$4 + 10 + 16 +…+ (6n−2) = n(3n +1)$$ I'm having a hard time understanding the induction process. Can someone please explain this to me?
2
votes
0answers
27 views

n-formula for k n-evaluations

I am trying to solve the following problem Let $N = \{0, 1, 2, ...\} $ is the set of natural numbers. Propositional variables are $ A_{n}$ for $n \in N $ . An evaluation $v$ is called $n$-...
-1
votes
1answer
55 views

Transitivity, symmetry on empty set X, non-empty relation R [closed]

If I had an empty set X, with a relation R containing elements 1 and 2 In my directed graph if I had (1,2) and (2,1), would I still have transitivity and symmetry even though this is an invalid ...
2
votes
1answer
22 views

How to write the truth table for a proposition and then determine its shortest possible equivalent expression?

$$(r\leftrightarrow \neg p)\wedge p\wedge (q\rightarrow \neg (p\oplus q))$$ Steps I took: I broke up the proposition into bits and pieces and assigned them to variables as such: $a=(p\oplus q)$, $b=...
0
votes
2answers
38 views

How do I evaluate the following mathematical statement?

Determine whether this statement is $T$ or $F$, or whether its truth value cannot be determined without knowledge of the value of $x$. If the truth value cannot be determined, show one example of a ...
2
votes
0answers
36 views

Tree graphs maximum degree 2?

With a non-isomorphic tree with 7 vertices, if each vertices has at most 2 degree. Wouldn't the number of trees that follow this condition be just 1? The tree in a row juggles between 1 and 2 degrees ...
0
votes
0answers
53 views

The number of facets of an affine image

I have a full dimensional polyhedron $P_1 \subseteq \mathbb{R}^d.$ Now i define another polyhedron as follows: $$P_2 = AP_1 \oplus B$$ with $A \in \mathbb{R}^{(d-1) \times d}, \,\, B \in \mathbb{R}^{...
2
votes
3answers
55 views

Find general form for summation expression

I am learning about combinatorics and am trying to solve the following problem. Find the value of $$\sum_{k=0}^n {n\choose k}(-1)^k\frac{1}{k+1}$$ for several values of n. What do you think is ...
1
vote
2answers
272 views

Write a recursive definition for the set of all binary strings that contain an odd number of zeros, and for all that end with a 0.

I am trying to do two things. Write a recursive definition for the set of all binary strings with an odd number of $0$s. Write a recursive definition for the set of all binary strings that end with ...
0
votes
1answer
51 views

Prove that if a sequence with $50$ members is $p$-balanced for $p=3,5,7,11,13, 17$, then all its members are equal zero.

A finite sequence $a_1, a_2, ..., a_n$ is called $p$-balanced if any sum of the form $a_k+a_{k+p} + a_{k+2p}+...$ is the same for any $k = 1, 2, 3, ..., p$. For instance the sequence $a_1 = 1$, $a_2 ...
2
votes
1answer
71 views

How many spanning trees do the graphs have?

How many spanning trees do the graphs have? -We know the answer for $a$ is 4 and for $b$ is 40, we could easily do $a$ by drawing it out, but I know for b.) you can use the formula $ \tau (G) = \...
2
votes
2answers
158 views

Prove that a simple graph with 17 vertices and 73 edges cannot be bipartite

Prove that a simple graph with 17 vertices and 73 edges cannot be bipartite. -I asked my professor for help on this and his hint was to break the graph up into two vertex sets and count the number of ...
1
vote
2answers
38 views

Find a model for the given WFF

Find a model for the given WFF: $\exists xp(x) \rightarrow \forall xp(x)$ I'm interpreting this as saying "There exists an x in the function p(x) which implies For all X in p(x)? So my solution ...
1
vote
1answer
32 views

Verifying partial order relation

I have the following question where i have to verify if the relation is partial order: $A=\{1,2,3,\ldots,100\}$, relation $x\mathrel{R}y \leftrightarrow \frac{y}x=2^k$, where $k\ge 0$ is an ...
0
votes
1answer
33 views

Combinations of people on a committee

Unsure about my answers: ...
1
vote
3answers
55 views

Use Fermat's Little Theorem to prove $24^{31} \equiv 23^{32} \mod{19}$

I'm trying to prove $24^{31} \equiv_{19} 23^{32}$. All I have so far is that this is equivalent to $23^5 \equiv_{19} 24^6$ by multiplying both sides by $24^623^5$. I can see that there seems to be ...
1
vote
2answers
41 views

Finding the particular solution to the following non-homogeneous recurrence relation

$$x_n = 2x_{n-1}+2^n$$ $$x_1 =5$$ Finding the homogenous solution is easy enough but when attempting to solve the particular solution I arrive at: $$C_22^n = 2C_22^{n-1} + 2^n $$ $$2C_2 = 2C_2 + 2 $$...
0
votes
1answer
22 views

Where am I going wrong in calculating this truth table?

I need to find the truth table for the following problem and then find its equivalent statement. $$(((!r\wedge (p\Leftrightarrow !p)\vee q)\Rightarrow p)$$ Steps I took: First, I decided to try and ...
1
vote
2answers
37 views

Does this proof that $\chi(\mathbb{Q}^2) = 2$ rely on choice?

I'm teaching a course on discrete math and came across a paper related to the Hadwiger-Nelson problem. The question asks how many colors are needed to color every point in $\mathbb{Q}^2$ such that no ...