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.

Filter by
Sorted by
Tagged with
0
votes
0answers
15 views

Using sets to describe an area bounded by the axes

How do I describe the area of a region by using sets. I was asked to represent the area shown in this figure. I think it should be $\{(x,y) ∈ \mathbb{R}^2 : -1<x<1, -\infty <y<\infty \}$ ...
0
votes
0answers
24 views

Describing an area using set notation

I was confused about a question that asked me to describe the area of a region using set notation. This one : https://imgur.com/gallery/aE6km7D Could I say "{ (x,y) $\in R^2$ : -1<x<1, -inf ...
1
vote
2answers
37 views

Discrete mathematics, is this a function?

Let A={1,2,3,4,5} and B={a, b, c, d}, and let f={(1,a),(2,a),(3,d),(4,c)} is f a function? , the text book I'm working from says it's since all mapping are one to one or many one to many, & non ...
3
votes
2answers
36 views

How to represent combinations of plus and minus

Just wondering if there is a shortcut for representing the following: $$x=1+i,1-i,-1+i,-1-i$$ I know that you can do: $$x = 1\pm i,-1\pm i$$ But can you use something like: $$x = \pm 1 \pm i$$ NOTE: I ...
0
votes
1answer
21 views

Scalar Multiple times $n \times n$ Identity Matrix Proof

How to prove $\det(kA) = k^{n}$ where $A$ is the $n \times n$ Identity Matrix using induction. I started off using the base case, forming my inductive hypothesis and trying to factor out $k^{n}$ times ...
2
votes
1answer
29 views

Forming a vacuously true statement from a predicate

Suppose we have a predicate P(n) = "n is even". Then, to form a vacuously true statement from this predicate, can I say "If humans have gills, then P(2)". My logic is that the ...
-1
votes
1answer
23 views

How many positive four-digit numbers (from 1000-9999) do NOT have two or more 3’s next to each other? [closed]

I know the amount of numbers that contain at least one 3 is 3168, but I'm stuck on the next part
4
votes
0answers
87 views

Negation of a sentence written by Oscar Wilde

If I am asked to negate a sentence such as: We are all in the gutter, but some of us are looking at the stars. would it be "Either there exists someone who is not in the gutter or all of us are ...
1
vote
1answer
38 views

Transitivity of $nth$ tuple vectors of Lexicography ordering

I have read about Definition Of Lexicographic Ordering, Lexicographic Order, Generalized lexicographic order, Lexicographical order, Lexicographic ordering, Lexicographical order and many other ...
1
vote
3answers
38 views

demonstrate the following argument

argument to be demonstrated: $A ∨ (B ∧ C)$ $B → D$ $C → E$ $D ∧ E → A ∨ C$ $¬A$ $∴ C$ My attempt at this mathematical demonstration was as follows: $A ∨ (B ∧ C)$ $≡ (A ∨ B) ∧ (A ∨ C)$ $≡ (A ∨ A) ∧ (B ∨...
3
votes
3answers
50 views

How can I prove that the l.h.s equals the r.h.s?

I can't move forward. Can anyone help? $$\frac{k (2k) + 2 }{ k (k + 1) }= \frac{2k + 2 }{ k + 2}$$ I'm trying to prove that the left side equals the right side. It started like this $$\frac{2k }{ k + ...
0
votes
0answers
22 views

drawing a graph on subsets

Let U = {1,2,3}. We construct a graph G = (V,E) on n = 7 vertices with vertex set V = P(U) \ {∅}. That is, v ∈ V is a vertex in G if v is a non-empty subset of U. The vertex set V that I got is V = {{...
-2
votes
1answer
26 views

Given two graphs with identical Laplacian matrices, how would one prove they MUST be isomorphic?

I want to decompose the implications of identical laplacian matrices down to equal adjacency matrices, then how do i definitively prove that graphs with identical adjacency matrix are isomorphic?
0
votes
0answers
32 views

Law of logical equivalent

How do I solve the following question? Let $p$ and $q$ be statement variables. Show that $p\Leftrightarrow q\equiv(p\vee q)\Rightarrow(p\wedge q)$ by using the laws of logical equivalence. Show each ...
-1
votes
0answers
9 views
0
votes
0answers
20 views

Simplest form of [(p v q) ^ ~{~p ^ (~q v r)}] v (~p ^ ~q) v (~p ^ ~r).

Simplest form of [(p v q) ^ ~{~p ^ (~q v r)}] v (~p ^ ~q) v (~p ^ ~r). A) p B) q C) r D) T E) F My answer is coming out to be p v ~q v ~r everytime. Answer given is D) i.e. True
0
votes
0answers
27 views

I don't understand how a certain step has been reached.

I have found the $\gcd(408,126) = 6$. Now I am using Bézout's identity to find the coefficients. a) $408 = 3 * 126 + 30$ b) $126 = 4 * 30 + 6$ Now $6 = 126 – (4 ·30)$ (1) $ = 126 – 4 ·(408 – 3 ·...
-3
votes
1answer
20 views

Multiple quantifiers: Determine the truth value of following statement. Justify your answers. ∀x∃y∃z(3x=150y-39z) [closed]

Determine the truth value of following statement. Justify your answers. $\forall x\in \mathbb{R}, \exists y,z\in \mathbb{R}$ such that $3x=150y-39z$.
0
votes
1answer
26 views

I don't know to to prove by induction that this is true for any n number of cards where the number of red and black cards may be different. [closed]

We play a game with a deck of 52 regular playing cards, of which 26 are red and 26 are black. I randomly shuffle the cards and place the deck face down on a table. You have the option of “taking” or “...
1
vote
1answer
72 views

Prove $(p \land \lnot q \rightarrow c) \iff (p \rightarrow q)$ [closed]

My attempt at this mathematical demonstration was as follows: $(p \land \lnot q → c) \iff (p \rightarrow q)$ $(\sim(p \land ~q) \lor c)$ $(\sim p \lor q) \lor c$ $(p \rightarrow q) \lor c$ After that, ...
0
votes
0answers
53 views

Positive Integers Solutions — Why Was I Wrong?

This is going to be a long question, so I apologize in advance. I'm currently doing self-study for discrete mathematics by going through Grimaldi, and I had a question regarding my problem-solving ...
-2
votes
0answers
20 views

a proof based on the Theorem of Hall is needed for the following question [closed]

suppose that $A_i$ with $i \in I$, is a finite Family of finite subsets of the of the Set M and $r \le |I| $. prove that if $ \vert \cup_j A_j \vert \ge \vert J \vert - r$ $$$$($j \in J$) for all $J\...
2
votes
1answer
57 views

Does $\mathbb{E}[(1-\varepsilon_n)^{X_n}]\rightarrow 1$ imply that $\mathbb{P}(X_n\geq A_n)\rightarrow 0$?

Let $X_n$ be a sequence of random variables taking values on the non negative integers which is finite almost surely (that is, for all $n\in\mathbb{N}$, there exists $k=k(n)$ such that $\mathbb{P}(X_n&...
1
vote
2answers
37 views

Can this system of congruences be solved? [duplicate]

\begin{equation} \left\{\begin{array}{@{}l@{}} 2x\equiv7\mod9 \\ 5x\equiv2\mod6 \end{array}\right.\,. \end{equation} Can this system of congruences be solved? I notice that $(9,6) = 3 \ne ...
0
votes
1answer
37 views

Combinatorics and logic equivalences

I've seen the following question and I wondered about whether or not the change I did is valid, the question is: "For how many numbers $i$ when $1 \leq i \leq 120$, the following statement holds: ...
0
votes
1answer
18 views

Find a logical statement containing 3 variables, where it is only true when any two of the variables are true.

I can only use negations and implications. My first idea was to try out all the possibilities, but that failed. My second idea was to write the solution in a truth table and look for two statements ...
-1
votes
0answers
41 views

How would I determine all the cubes in mod 13? [closed]

Just looking how to do this I have been asked to find all cubes in Z_13, which I assume is cubing all elements of Z_13 under mod 13, then what is the remainder is what can be involved in the set?
-1
votes
3answers
54 views

How to prove p → q ≡ ¬q → ¬p [closed]

My attempt at this mathematical demonstration was as follows: p → q ≡ ¬q → ¬p ≡ ¬p ∨ q ≡ q ∨ ¬p ≡ ¬q → ¬p
0
votes
0answers
69 views

Why does $(a + 1)^p - (a)^p$ have so few prime factors?

Why does $(a + 1)^p - (a)^p$ have so few prime factors where $a$ is an positive integer and $p$ is any odd prime.
0
votes
0answers
21 views

can ∃x(x+y=1) be turned into a proposition?

My book says all the variables that occur in a propositional function must be bound or set equal to a particular value to turn it into a proposition, and below that there's an example ∃x(x+y=1). In ...
2
votes
5answers
67 views

$A, B,$ and $C$ are all sets that lie in a common universal set. Prove $A = B$ given the following statements.

$(A \cup C) = (B \cup C)$ and $(A \cap C) = (B \cap C)$ I know I have to start with $A = ...$ to get to $B$. I incorporated $A = A \cap (A \cup C)$ as the first step using absorption law, but I don't ...
1
vote
1answer
19 views

What is the domain in the First Order Logic expression?

I think I'm misunderstanding how to apply the domain for these expressions. The question is: Let $P(x), Q(x), R(x),$ and $S(x)$ be the statements “$x$ is a duck,” “$x$ is one of my poultry,” “$x$ is ...
1
vote
3answers
53 views

Struggling to understand basics of complete residue system

I'm really struggling to understand the literal arithmetic being applied to find a complete residue system of modulo $n$. Below is the definition my textbook provides along with an example. Let $k$ ...
0
votes
1answer
27 views

Struggling with the meaning of discrete.

Even though the set of all integers is infinite, is it still discrete? Also, is a finite set of decimals, such as the following set of $3$ decimals $\{ .1, .2, .3\}$ discrete because it's members are ...
0
votes
1answer
23 views

Golden Mean - Prove, in general, that For all $\in N | τ^{n+1} = τ^n + τ^{n-1} $

Prove in general that For all $\in N | τ^{n+1} = τ^n + τ^{n-1} $ I've been trying to work on this problem over the past few days and I seem to be missing something. I know that $ τ = (1 + √5)/2$ I ...
-1
votes
2answers
40 views

Let A = {1, 2, 3, 4, 5} and define a function F: Ƥ (A)→ Z as follows: For all sets X in Ƥ (A), F(X) = { 0 if X has even number of elements} [closed]

Let $A = \{1, 2, 3, 4, 5\}$ and define a function $F: \mathcal P(A) \to \mathbb Z$ as follows: For all sets $X$ in $\mathcal P(A)$, $$ F(X) = \begin{cases} 0 & \textrm{if $X$ has an even number ...
1
vote
3answers
108 views

How to prove (p → q) ∨ (q → r) ≡ (p ∧ q) → r [closed]

My attempt at this mathematical demonstration was as follows: (p → q) ∨ (q → r) ≡ (~p ∧ q) ∨ (q → r) ≡ q ∨ (p → r) ≡ (q ∨ p) → r ≡ (p ∨ q) → r
2
votes
0answers
27 views

recurrence relalation in Kenneth Rosen's book

I saw a question in Kenneth Rosen's Discrete math book in chapter $8.1$ , question $3$. There is an answer for it in stack exchange such that Recurrence relation question My question is as to part a , ...
0
votes
2answers
42 views

Big-O notation for algorithm

I'm working in an algorithm and I have achieved to know that its cost is $O \Big(\prod_{i = 1}^{N} i \cdot \log i \Big)$. I don't know how to simplify my cost even more. Can anyone help me? Thank you ...
2
votes
3answers
48 views

If you roll a fair 6-sided die and then flip a fair coin that number of times, what is the probability that you will get at least two heads?

My idea is to use disjoint events and calculating the probability of getting at least two heads for each number rolled. For example, if I roll a 3, I would calculate the probability with the ...
-1
votes
2answers
61 views

Prove that $(A - B)^c = A^c \cup B$

I cannot resolve and prove this equality in any way. My attempt Suppose $x\in(A-B)^c. x\not\in(A-B), x∉A$ and $x\not\in B$
1
vote
2answers
36 views

Show that $\forall n\ge3,(2 n-1) \times(2 n-3) \times(2 n-5) \times \cdots \times 5 \times 3 \times 1\ge2 \times 7^{n-2}$

Here's my question: Let $f(n)=(2 n-1) \times(2 n-3) \times(2 n-5) \times \cdots \times 5 \times 3 \times 1$, and I need to prove that for all $n\ge3,f(n)\ge2\times7^{n-2}$. I have figured out some ...
2
votes
1answer
39 views

Graph convergence on probability

Good afternoon. In one book on probability theory I came across this problem which I found myself difficult to understand and prove. Would appreciate any help on that: Let $X_n$ be the number of ...
1
vote
1answer
53 views

Proving convergence to Poisson distribution [closed]

I've been examining some problems on convergence and found some issues solving this one. Let $X_n$ be the number of triangles in $G(n, \frac{1}{n})$, where G - is graph and triangle - 3 vertices ...
0
votes
0answers
37 views

Discrete Math induction: The correct answer is 354162, but what are the steps to get to this answer?

Got this question wrong, so I'm reviewing this question so I can understand this problem. I'm confused as to how to get the answer $3,5,4,1,6,2$ individually in that particular order. Theorem $5.1.1$. ...
-3
votes
3answers
45 views

Help with basic modular arithmetic question [duplicate]

I asked this question moments ago but it was closed despite the link being non-applicable to my question. I need help solving the below basic modular problem, Show that $39$ divides $17^{48}-5^{24}$ ...
0
votes
1answer
28 views

Help solving basic modular arithmetic problem [duplicate]

I'm stuck on this basic problem, Show that $39$ divides $17^{48}-5^{24}$ I am familiar with the basic arithmetic properties of modular. But I have absolutely no idea how I'm supposed to apply them ...
0
votes
1answer
21 views

Are Ramsey numbers defined for $n=0$?

I'm familiar with the trivial case $R(1,a)=1$, as there are no edges to colour. Is $R(0,a)$ defined at all? Or would it similarly be trivially 0 since there are no edges and no vertices?
10
votes
1answer
116 views
+50

How to color a board such that each square has exactly two neighbors of the opposite color

Let $m≥2$, $n≥2$ integers. We want to color the squares of an $m × n$ board with black and white so that each square has exactly two neighbors of the other color. Determine all the values ​​of $m$ and ...
-1
votes
1answer
32 views

Let $f(x)=(x+1)/x$ for all $x \in \mathbb{R}$ and $x\not= 0$ prove that this function is one-to-one correspondence

Let $f: R\setminus\{0\} \rightarrow R\setminus\{1\}$ be a function defined by the formula $f(x)=(x+1)/x$ for all $x \in \mathbb{R}$ and $x \not= 0$ prove that this function is one-to-one ...

1
2 3 4 5
564