#discrete-math
1 messages · Page 207 of 1
If R is an equvalence relation, I would just say "an equivalence class" instead of insisting on symbols.
Your underlying trouble here seems to be that you are attempting to write a single closed expression but you want it to produce a variety of different sets.
Yes
What you can write is { a | xRa } with x being a parameter, and by varying x you will then get different equivalence classes.
parameter you mean an argument of a function?
Sure, you could view it that way. What I mean is just, rather down-to-earth, that "{ a | xRa }" doesn't evaluate to a concrete set until you supply a value for the variable x.
Is there a keyword or book which would nail more complex set building notations?
theres not much to setbuilder, u just need to have the right syntax if u wanna write these sets symbolically
say P(x) is a statement, pertaining to each object x in a set of interest, thats either true or false
this is how to write the set of all objects x such that P(x) is true
$\brc{x:P(x)}$
RokabeJintaro
yeah that i've understood.
can I legally define P(x) as x belongs to a set { a | a != x } and { x }
meaning any set which has distinct elements
the thing is ur struggling to translate conditions into symbols
this is a bit unclear
i do.
a set from which I take a random element and all the other elements from the same set are not equal to it
{ a b c d e f.. } every element is not equal between each.
im unsure what ur trying to define
"other" already means different from what ur looking at
Again, your problem is that you want a single expression to give you multiple different results. Expressions simply don't work that way.
Its just the way math works?
It's how expressions work.
Their job is to evalate to one particular thing.
If you want to speak about several different things, you need to speak about the set of all those things, or write down a property that they all have.
but if I define expression a > b
a > b is not an expression.
a>b is a proposition, i.e. something that can be true or false. In contrast expressions are not true or false, but evaluate to things.
got it
And in particular, a set builder is an expression.
the parameter n is an arbitrary natural number
once i set n to a specific value, we get a specific set
if i set n=2 then i get
{ (1 2) (2 4) (3 6) (4 8) ... }
got it
n should probably be an arbitrary rational if I'm understanding Lambdaman correctly.
yes
ah yes but it doesnt detract from the point about how parameters work
yeah just a tiny detail
Hello
We did not get to cover this in class, and I can’t find an example in the textbook but can anyone explain to me what is \ ?
Thanks in advance
Set difference.
$A\sm B=\brc{x\in A:x\notin B}$
RokabeJintaro
But you can't really write down questions 3, 4, and 5 in list form without some assumptions of whether a and/or b might equal one of 1,2,3,4.
Does anyone have any experience with implementing optimization algorithms for vehicle routing problems? I have zero experience with it and wanted to implement a paper so I could make a mod for city management game.
Can someone help me with B
Ive tried multiple things and im just working in circles
Im not sure what the ideal way of getting started would be or what manipulations i can do with the laws
Determine whether the statements are true or false:
(a) {1, 2} ⊆ [1, 2]
oh lmao, meaning there's no graph which has one vertex of odd degree
so it's axiomatically impossible
right, I see
Apply the rule p -> q = !p or q
Or convert it to this form [ a or b or c or d ]. If there are some two x such as [ a or .. or .. or x or x! ] then its always correct.
what does that operator ⊆ means? How does it different from the one without _ underneath?
So first assume (P->Q)V(P->R)
Then first assume P->Q
Then we can assume P
Using our 2. assumption we get Q
Then we can insert V to get Q V R
Then we can conclude that P->(QVR)
You can then do the same thing with P->R
And since you proved it for both sides of the V
We can conclude that ((P->Q)V(P->R))->(P->(QVR))
It means it can be the set itself as well
oh then same as =<
Yes
Determine whether the statements are true or false:
(a) {1, 2} ⊆ [1, 2] so this statement is true then?
How are your square brackets defined?
I'm saying that as something you'd want to clarify before thinking about the statement
square brackets mean the interval 1..2 including ends.
i know what you mean, its semantic problem
as I see on the net and books [ ] denote a set usually
Sometimes you'll see $x \in [a, b]$
pitabread
There are just two numbers to check, which should be easy.
what do you mean?
1 is an element of [1,2], and 2 is an element of [1,2], therefore 1 and 2 are both elements of [1,2], therefore {1,2} is a subset of [1,2].
True. It's just syntax problem to understand what square brackets means which bugs this thing a little.
I don't think square brackets in this context can mean anything else than a closed interval. Round brackets are more ambiguous.
Is your problem to understand how a closed interval is a set?
Hmmm. What is your understanding of the closed interval if not as a set?
I don't know. Maybe just the definitions set != interval
but since interval is a subset so its a set. no problem.
I'm trying to figure out what your current understanding is. If an interval is not automatically a set to you, what else can it be?
just a different type of datatype in math
same as I take some piece from integer number and get rational
Hmm, I don't think that sounds like a very productive notion. The mainstream way to think is that intervals are (always) a particular kind of sets.
Is there something you can do with a non-set interval that you cannot do when viewing it as a set?
Good question.
Probably no.
I suppose you can ask "what is the right endpoint of this interval" but not in general "what is the right endpoint of this set".
So a better model might be "subtypes" rather than a completely separate type.
but encoding kinda equalizes it
I just can say that this element does not belong to the set
or all elements belong except the two
Uh, now you've lost me.
I mean you say that interval can have the property of left and right endpoints
set does not
but we can express endpoint meaning in a set notation still
That sounds like a train of thought leading in a dangerous direction. Properties of things is not the same as elements of a set.
(1 , 2) means that 1,2 does not belong in a set
I have to take a break and think about it.
No, in interval notation (1,2) means one particular set.
My bad. I wanted to state that (1, 2) means a set which does not have 1 ,2 in it
But is one particular set, and that set happens to not have 1 or 2 in it. It doesn't have 3 or 42 in it either.
You can't take any random set and declare that set to be (1,2) just because neither 1 nor 2 is in your set.
True
What I was getting at is what we can still say "the left endpoint of (1,2) is 1" even though 1 is not an element of (1,2).
$(1,2) = { x\in\mathbb R \mid (x>1) \land (x<2) }$
Troposphere
It's still a legal set builder notation, but you'll get a different set out of it.
${ x\in\mathbb R \mid (x\ne1) \land (x\ne2) }$ contains all the elements of $(1,2)$ but it also contains, for example, $0$, $\pi$ and $-42$.
Troposphere
oh so then (1,2) != {5,6,7,4}
Very much so.
Yes, in each case plus all of the additional boilerplate of the set builder notation.
Got it.
Derive a discrete formulation for the gradient in two dimensions using finite difference quotients
can someone explain to me what could this mean
i dont even know what discrete math is
this is correct
a lot of writing for such a simple problem, but yes this is also correct
thanks, how would you condense it to be shorter
"The statement claims for all primes, if p is prime, then p+1 is not prime. Consider 2 which is prime, 3 is also prime. Thus this statement is false"
something like that?
i would only provide your counterexample, yes
k
but i dont know what your teacher expects and what you need to convince yourself
okay, that makes sense
can i also get a check for: "Prove that “if p is a prime number, then p + 7 is not a prime number” is true."
ignore my typo
its correct, but unnecessarily phrased as a proof by contradiction
also technically you have to check that p+7 is not 2 in the second case
let me think about checking p+7 is not 2 in the second case
how would you prove it if not by contradiction
how do i check p+7 is not 2 when i get to the: (2k+1)+7=2k+8=2(k+4) part
all numbers greater than 2 happen to be not 2
ok let me rewrite
i only mentioned "technically" because p + 7 > 2 should be obvious
its just that 2 | a is not enough to conclude a is not prime
so youd just start the proof at the cases part?
which is exactly what you need to do
right
no reason to assume p+7 prime at the start
sure
k, excellent ty
We weren’t taught this yet. He told us to use propositional laws
That's a "propositional law" too.
In that case I think it is up to you to disclose what you can use.
Wait im sorry
Im a dumbass
We did learn it bit the negation sign is to the side rather than the top
Also when they grouped the terms together into three was there any law used or we did just because its all or’s
Is Ø ⊆ {Ø} true?
Was there a law used for the grouping of the statement on the left side?
From the second line to the third
I thought you could only use distributive and the signs had to be or and or
And or and
To work
What about Ø ∈ Ø?
That's not true -- but that's not a subset symbol either.
is there a name of the law that allows us to make the following proposition: let B be a set of balls, balls in B are red, if a set P is a subset of B then balls in P are red?
just need a formal name
@coral parcel sorry to tag you but can you take a look at my recent question
If you mean my second screenshot. It was grouped not just because it's all or's. That transformation can be achieved by applying propositional laws for target expression. There is the algorithm which you can apply if you wanna do it by hand. But I don't know it well enough so I just fed it to auto solver.
ahh okay i was just confused becasue i wasnt sure if two p's could be converted into just one without using distributive law
(a or b or a) = ( a or b).. (a and b and a) = ( a and b).. those cases I saw in the book. Don't have deep knowledge to explain in further.
Dumb question: can anyone tell me why these formulas:
together logically imply that p and r is not a valid consequence but p or r is?
the first formula should be premise 1, the one on the right - premise 2 and the two possible answers - conclusions, correct?
You should have a column for the conjunction of the two premises.
It would go 0,1,0,0,1,1,0,0
And in the lines where both your premises are true, p or r is also true.
But there are lines where boh your premises are true, but p and r is not.
For example the second line in your truth table.
what would the conjunction sign be?
conjunction = fancy word for "and".
ah gotcha
ok so if I put the conjunction of the two premises in the table
as you said we will have 0,1,0,0,1,1,0,0
but I still don't get what makes the conclusion valid
In all the lines where 01001100 has a 1 there's also a 1 in 01011111.
On the other hand, the second line (p=q=0, r=1) is a case where the two premises are both true, yet p and r is not true. Therefore p and r is not true in all the situations where the premises are, so it had better not be a consequence.
ahh, I think I get it now, so it would be equal to say "if 1 in the conjunction of the two premises does not correspond to a 1 in the conclusion, the conclusion is not valid"...? is my logic correct? 😂
considering p or r is the conclusion...?
Right.
Can I have a hint of this question?
Give an example of a relation that is reflexive and symmetric but not transitive. Consider the partition generated by the relation
All I came up with is that the sets in the "partition" are not disjoint, but im not sure how that helps
You can just wing it, figuring out which pairs need to be in the relation in order to be an example. (Hint: take the underlying set to be {1,2,3} and start with the requirement that the relation is not transitive).
I thought of doing your hint for that set already and got P={{1,3,5}{3,1},{5,1}} as an example; but I'm not sure how to define the relation such that this is the generated equivalence classes
can someone hekp me with this problem:
@frosty heron delete it from here, we don’t like people posting in multiple channels
if (x v y) = x + y - xy can we just assume that (~x v y) = ~x + y - ~x*y? or nah
not sure if thats allowed but
@lime rover What have you tried/thought so far?
does anyone know a real life data set i could apply the discrete fourier series on
like i need a real life situation to apply the fourier series on
try looking up sunrise/sunset data
found this... png of a record
you can use that
I have a quesiton
Can anyone check if my set notation is correct?
($\forall$x, y, z $\epsilon$ [0,1])[x > $\frac{1}{2}$][y < $\frac{1}{2}$][x + y $\leq$ 1] $\vee$ ($\forall$x, y, z $\epsilon$ [0,1])[z $\geq$ $\frac{1}{2}$]
hm
eswag
does that make sense to connect two conditions?
($\forall$x, y, z $\epsilon$ [0,1])[x $\textgreater$ $\frac{1}{2}$][y $\textless$ $\frac{1}{2}$][x + y $\leq$ 1] $\vee$ ($\forall$x, y, z $\epsilon$ [0,1])[z $\geq$ $\frac{1}{2}$]
eswag
are [] restrictions
will do it
can you show me?
sure
i want to write it as an or condition
like x has to be greater than 1/2 and y has to be less than 1/2 so that x + y <= 1
or if that entire condition fails make z >= 1/2
ok
can you connect those two?
my professor wrote his sets like this
but
so yeah i wasnt sure if mine was right
oh
the condition is kinda redundent
since we take any x such that z from [0,1] is larger than 0.5
yea that makes sense
ah
yes
can't we just say z epsilon [0,1] ?
and then just call that a day
there wouldnt be any redundancy
im not sure what u want that set to be
hm
it doesnt really make sense
So i'm given this problem
i figured out that to satisfy this set i need the first condition to either be this
if this first condition fails make z >= 1/2
and at that point x,y can be anything
@gritty pumice hopefully that makes sense?
Think you left but that's okay I guess
Hi sorry
Hmm
Are you trying to put an or between the conditions?
Yes
either this works
or this
if condition one evaluates to >= 1/2 then z can be anything
if condition one does not evaluate, make z to be >= 1/2
Right I see
Let me do it
so first step is to just expand those symbols
so $x(1-y) + z(1-x+xy) \geq 1/2$
Lsfhv
yes
okay gotcha
im not really sure how to find every condition on x,y,z easily tbh
i kinda just
wrote test conditions
and found a pattern
and went along with that
and i figured out that x > 1/2 and y < 1/2 so that x + y <= 1
or just make z >= 1/2
uh
the problem with that is that
the ~x becomes too big
if its < 0.5
so it doesnt work
what are x,y,z
oh :/
that makes it alot easier lmfao
it doesnt say that on ur question!!!!
lol
yea but this fails though
where
okay to my understanding
x ^ ~y can be written as
~(~x + y - ~x*y)
given the properties they write
which is just
ok
1-\left(\left(1-x\right)+y-\left(1-x\right)\cdot y\right)
this is what it expands to
if you substitute x to be 0
and put y to be anything
such as 0,1
why is that an issue
so technically we can just say x and y can be anything
and z is just >= 1/2
what i was thinking of was
dont get this
x and y can be any value in [0,1]
if that first condition doesnt work
you have z which must be >= 1/2
right
.
from this equation
the brackets are never going to be negative
so yea i think the only condition u need is 1 <= z <= 1/2
okay but that can't be the point of the question though
{(x,y,z) : 1<= z <= 1/2}
the next problem is literally just
the same thing
theres no way it can be that one-dimensional
this is the set of solutions
the definitions of ^ and V are different
yeah but the premise of the quesiton is still the same
yes
x and y can be anything while z is just >= 1/2
😄
i mean i havnt done it
but
i guess its just a coincidence ?
discrete math
nice
@gritty pumice apparently this reasoning was wrong 🤣
the TA said we cannot restrict z to be >= 0.5
because there exist z less than 0.5 such that
the left side evaluates to >= 0.5
yes it makes sense
this seems like a really...... bad way of writing this argument, is there anyone that can give me insight on how these types of arguments can be written in a more rigorous and "formal" manner?
As a wheel graph contains a cycle of order n-1 are all wheel graphs W_n Hamiltonian?
for n >= 3
Can someone help with this?
I don't really get B. Anyone knows how to approach it?
try to think of a universe where for every x either only p(x) is true or only q(x) is true
then those two statements should differ
so
they have the be =
for the statment to be correct?
but if value of x for p(x) and q(x) is different
then it's worng?
?
try to think of what the statements mean in words
the first is "every x has property p or q"
the second is "every x has property p or every x has property q"
with p(x) = "x = 0" and q(x) = "x = 1"
but that was the answer to A
and I got it right
a the answer is whenever statment 1 is true
statment 2 is true
so they are logically equivalent
I guess
by conversing
a) is the other way around from what i presented
it does not
i mean just because a statement is true, doesnt mean the converse is true
this is an example
"everyone in this room wears a red or a blue shirt" ≠ "this room is filled with red shirts or filled with blue shirts"
x has lenghth 1
oh yeah it says for all x in the kleene closure of Sigma
basic step should be the smallest number right
so youre gonna wanna do 0
yessir
In most cases
In this case, yes
for this question, how do you know the range of x?
shouldn't it be epsilon ?
the smallest
or at least 1 since a word's shortest length is 1
MISSISSIPPI in which there are no consecutive symbols S?```
is 70 correct answer? i used (8 choose 4)
a is part of the characters
x is part of the strings
and the r means reverse of the string
Yes okay
And it asked you to prove this by induction on the length of x
x is in the kleene closure of Sigma
So all the words above Sigma
so all strings yea?
Yes
So it means it can have any nonnegative integer length
yes
The shortest string is epsilon
yes
no
Concatenation is literally just appending another word. So if you're concatenating hello and there, you get hellothere.
So if you're not appending anything it doesn't change the word
Basically $x\varepsilon = \varepsilon x = x$
Slurp
thanks
how do you read there ]x ]y?
]x]y[xy=1]
double quantifiers really
confuse me
Ann
"there exist x and y such that..."
you can abbreviate $\exists x \exists y$ to $\exists x, y$ unless you're a staunch formalist or your teacher beats you for the slightest informality
Ann
but yes what you said is a true statement in any reasonable interpretation
then it would be false
you would do good to say "true" and "false" instead of "correct" and "incorrect"
ok
it is of course not true that for all real x and y we have xy = 1
ok thanks
Is this how to do it?
,rotate
what did you do here?
mathematical induction
should i switch out the x for k in ih?
No
what should my ih be?
That forall $x\in\Sigma^*$ with a length of $n$ and forall $a\in\Sigma$, $(ax)^r = x^ra$
Slurp
And you have to prove that forall $x\in\Sigma^*$ with a length of $n+1$, $(ax)^r=x^ra$
Slurp
Remember that if $x$ has a length of $n+1$, then there exists some $x'\in\Sigma^*$ with a length of $n$ and $\alpha\in\Sigma$ such that $x=x'\alpha$
Slurp
LOL I JUST finished my quiz and got the same question
that I asked you 5 minutes prior thats so lucky
n+1 will be true because n + 1 is part of length n right?
wdym?
quick question this is asking me to translate the statements into logic set them apart by using and
and using propositional laws to make it false?
so it would be (M -> S) and (S -> P) and (not M -> P)
I'm not sure if the translation for the third statement is true
if i have p = x^2 -4y =2, will NOT p, ¬p = x^2 -4y !=2, How can i write NOT p
is it possible to have a set of cardinality > 1 but all elements behave the same as each other when any algebraic operation is performed on them?
if so, can cardinality be infinite? Can this be extended to any operation?
I'm just wondering about this, not in any classes or anything right now
are you asking if you can have an infinite number of elements in a set theoretically you could
I'm asking if distinct elements in a set can at least be algebraically identical
i.e minimum {2, n} for n which is algebraically identical to 2 while |{2, n}| = 2
I'm asking because I used a program which has a "superset" function but that superset function treats identical repeated integers as distinct and returns a "superset" as such, so I wondered if that's actually possible in math
Im currently in a discrete mathematics class with computer science application and as far as I know a set can be FINITE with having a 1-1 correspondence with {1,2...,n} for some natural number n. with INFINITE sets they cannot be put into a 1-1 correspondence with {1,2...,n}, that means it has more n elements for any natural number n
so depending on the type of set the answer to your question is yes and no
I guess this is number theory or something, I'm asking if two numbers can be distinct if they have the same algebraic properties
I think
but yeah this wouldn't just be a set over integers
I think "multiset" is the concept you really want here; try googling that.
There are some interesting rabbit holes to explore related to making "elements that are distinct but not algebraically distinguishable" precise, but they're not really relevant if what you need is just a multiset concept. :-)
haha exactly, glad to know those rabbit holes are there though
x^2 ≡ 2 (mod 26) --> is there any solution for this? if so, how?
it helps if you know the chinese remainder theorem, then it breaks the problem down to solving x^2=2 mod 2 and x^2=2 mod 13
yeah I have been looking into that, but I cannot wrap my head around it
do you want to find a solution or do you just want to know if one exists
quadratic reciprocity can give you the answer without giving you a solution pretty quick is why I ask
I know that no x exists to satisfy that
I wanted to find a solution, without necessarily trial and error
I gotta run rn, but maybe someone can help, at least this lets you know you're on the right path
sure thing
What boolean law can i apply to keep simplifying
actually i lied so i know i can apply complement law
but did i use the distributive law correctly?
I ended up simplifying it too CD
But im still not sure if I used distributive law correctly
on the first line you have $AB \overline{AB}$ which if you think of $P=AB$ then you have $P \overline{P}$ which is P and not P, which is false, so you can throw it out
Merosity
ahh okay
What are the minimal vectors of a lattice?
Probably the shortest nonzero vectors in the lattice. In which context?
Can someone point to/give a handwavy explanation for why v is likely to be the shortest non-zero vector in L? (or should I ask in #linear-algebra)
I think it must be something like: If it's not already a shortest vector in L, you can make it the shortest vector by scaling all of the b_i's and s by a large constant factor. Then a mismatch in the last column will make the vector much larger, so a shortest vector after the scaling must have its last component zero. And then the only contribution to the norm is sum of (2xi-1)², which is minimized by choosing each xi in {0,1}.
The reason why this is handwavy is that if the some of the b_i's are noncommensurable, the last component of v can be arbitrarily close to 0, so it needs some argument to see that keeping it small whlle we blow up the last column will require the integer coefficients to be so large that the other columns dominate the norm.
(I'm assuming all of the b_i's are positive).
Thanks, will have a think
learning about this in my today's lecture, nice
If i have 12 different balls :
4 blues, 3 red, 5 yellow
And i want to get 6 balls in one pick
How many possibiltys that i pick 2 balls of ea color?
Is this correct. ?
@weary tiger First one is correct
yeah im sure
Not quite, the sum is going from n to 5n, and you sum each term in-between.
The terms between n and 5n aren't just 2n, 3n & 4n, rather you have:
n + (n + 1) + (n + 2) + ... + (2n - 1) + 2n + (2n + 1) + ... + (5n - 1) + (5n).
@weary tiger
- (2n - 1) + 2n + (2n + 1)
how did u get these terms?
They are just a couple of terms, if the letters confuse you, let's see the same thing with numbers
Let n = 5, we are calculating the sum from i = 5 to i = 25 of i
So far it's clear right? (n = 5, 5n = 25)
yeah
If i have 12 different balls :
4 blues, 3 red, 5 yellow
And i want to get 6 balls in one pick
How many possibiltys that i pick 2 balls of ea color?
Occupied, wait for a bit
It was occupied before you
If it were strictly n + 2n + 3n + 4n + 5n, then that would be the sum of 5 + 10 + 15 + 20 + 25
Look above
yeah
But, we need the sum of 5 + 6 + 7 + ... + 23 + 24 + 25
You can write that sum as n + (n+1) + ... + (5n - 1) + 5n
ah I see
doesn't matter how many terms you include, just the end points matter
is it possible
that I move
the 5
to i instead
and make it i=n to n
or? thats not possible
no nvm
thank you
as far as I can see, that isn't possible, also np
@elder berry could you help me please haha ty
Let me see the problem
If i have 12 different balls :
4 blues, 3 red, 5 yellow
And i want to get 6 balls in one pick
How many possibiltys that i pick 2 balls of ea color?
The blue balls not similar as well as yellow balls and red balls
For example we have a blue ball that is bigger then other blue balls
Alright, if you need 2 of each, and order doesn't matter, in how many ways can you pick 2 red balls first?
Why the red first
Im gonna pick 6 balls in one pick
6 balls in one pick
Im not gonna pick 2 balls then another 2 then another 2
Im gonna pick the 6 balls in one pick
Well arriving at the solution is easier if you pick 2 by 2 by 2
and it is no different if you selected all 6 at the same time
Yup, it will count the same thing
just that, picking 6 at the same time is harder to calculate
What is the proposed answer?
180
Give me just a second to calculate it
Ok beast ty
Yup, 180 seems to be correct
Let's start with calculating the possibilities
we start considering each color first, in how many ways can you choose 2 red balls
How many are you given at the start?
We have 3 red
Right, so from 3 red, you chose 2. What does that end up being?
3!
just 3
Since we have (3 choose 2) which is the binomial coefficient, you've studied those right?
peaceGiant
Yes!
Great, let's repeat this for the other colors, we have 5 yellow, you need to choose 2; and you have 4 blue, and you need to choose 2.
peaceGiant
I'll leave the calculations up to you, first one is 10, second one is 6
So far we calculated each independent result, but now we need to combine it together
Very good!
I would, but I don't know how you arrived at that answer
Can you explain how you got it?
Why would you?
Indeed they are different, however let's work with an example
Say I have B1 and B2, blue ball 1 and 2
If I had B2 and B1, would that be a different possibility?
It wouldn't, since you essentially have the same pairs of balls at the end
and we care about the distinct scenarios, say having B1 and B3
The combinations already do that division for us, they make the distinction between the given balls
When we say (4 choose 2), we make sure that B1 and B2 are counted once!
So we don't divide by 2.
Np, glad to help
I don't know where to begin for the 2nd question. this is for probability class.
hey quick question on finite automaton (nfas/dfas) i have a question to create a nfa that accepts strings that start and end with the same two letters for strings greater than length 2. although the solution i have come up with is a dfa. is there a way of thinking in order to create something thats nondeterministic that completes the same task
(also the next step is to convert my nfa into a dfa using the construction game method so i dont think i can have my nfa = dfa even though my "dfa" would be a valid nfa)
ive been stuck on this for a good hour and any help would be appreciated lol thanks
also 2 weeks into learn this stuff so my knowlege is limited haha
hey (2n - 1) + 2n + (2n + 1)
why did the pattern change agian?
going from n+1 n+2 n+3... to 2n-1
do you mean strings like xyblahxy or strings like xxblahyy?
If you already have a DFA, you can declare yourself to be done -- every DFA is also an NFA. But especially in the xyblahxy case, it's quite a bit simpler to write down an NFA directly.
There is no pattern. I just wrote some terms, not all of them. Again, n is not given, so it get be arbitrarily large or small.
The main idea is that you are going from n to 5n, rather n + (n + 1) + ... + (5n - 1) + 5n.
In the ... part, you could have the terms 2n - 1, 3n + 2, and so on. It doesn't really matter though.
Say we have n=5, 5n - 1 is 24.
5 + 6 + ... + 24 + 25.
So that term is definitely there
Yup
No problem, are you required to find a general expression for that sum?
yea for {a,b}* where the x starts and ends with the same two for example abab bbb aabaa ab as long as the front and back read the same. and the thing is the question asks to convert my nfa into a dfa so id assume showing them the same machine would defeat the purpose.
and ik if it was only like only xy....xy it would be sm easier for nfa but its xy...xy, yy...yy, xx....xx, yx...yx (for strings larger than 2)
ive made this so far and i think it works perfectly although my brain went and made a dfa instead of an nfa
FWIW, that looks like it works.
I imagine what the exercise intended for you to come up with was an NFA with four copies of something like
,---. a,b
a b \ / a b
* -----> * -----> * -----> * -----> (*)
but the need to recognize strings or length 2 and 3 too would require additional states and/or transitions on top of that.
I want to make ordered set with set builder notation. This text generates set with elements like (1,a) (1,b) (2,a).. what predicate to put inside it in order to say "Every element in this set is distinct both by x and y" ?
@spring surge wdym "Every element in this set is distinct both by x and y"?
I mean that if we have (a,1) in this set then in this same set cannot be (b,1) (c,1) (a,2)
this set isnt well defined
What would be a logical expression for A person can park in the school parking lot if they are a senior or at least 17 years of age. I wrote Parking implies 17 or senior . Does this seem correct?
i see
there are many possible sets that satisfy that condition
How to express tuple in set builder notation?
wdym
How to encode a set which has element as permutation of given elements?
{ (ordered set of a b c elements) | a b c belongs to {1,2,3} }
the set of permutations on 3 items
thats the easiest way to word it
formally such permutations are bijections {1,2,3}->{1,2,3}
Is it possible to define it without using function definition?
How to put it in formal way?
forall n in {1,2,3} the triple contains n
thanks.
ur welcome
The central fact seems to be that on average you expect to find a new smallest number logn times as you walk through the array.
(How to prove that, though ...)
ah i think so exactly as i have 4 paths with a few others to deal with things like aaa bbb aa bb. although if i use something like the subset construction game on an nfa and get almsot the exact same thing, do you think i would be peanalized for doing so.
(the only nfa feature i really have is a self loop for a duplicate letter, although the way i have structured it kinda renders it useless)
sorry didn't mean to send that just yet
start with a base case at n=1 and see that it holds
yes
it does
I'm stuggling with the
inductive step
been trying to do it for 1 hour 😦
what is your inductive hypothesis?
I expect if you use the subset construction on the kind of NFA I sketched, you would get something more or less like you already have, but probably with some of the states duplicated, and you'd have to minimize the DFA afterwards if you wanted to end with something that's exactly isomorphic to your hand-constructed DFA.
Whether you'd be penalized for jumping directly to the final solution depends (unfortunately) on how inflexible the grader is. It doesn't sound outrageous to me that you could keep enough of the situation in your head to just write down your DFA, but I suppose there's always a risk that they'll be enforcing a secret "you must use the particular tactic we had in mind" grading criterion. It would probably feel safest at least to write some text explicitly showing that you're aware that there could have been such-and-such steps you needed to take here.
ahhh ok makes sense haha, and just to clarify what do you mean by 'minimize' my dfa?
There's an algorithm that takes a DFA and produces a DFA that has the smallest number of states among all DFAs that accept the same language.
but yea ill jsut wrtie down my though process and hope for the best bc i find it hard to think with a 'undeterminable' mindset
ohhh no way
ill def look into it
thank you for all the help
acc really appreciate it 🙂
I'm trying to prove Associativity of /\ but i'm unclear how to do it using logical axioms
it's not difficult to understand at all
just unclear on how to properly reference axioms
would you guys recommend an equational proof or hilbert style?
You'd need to show which axioms about conjunction you have to start from.
do you have any idea how to solve that problem?
so just to make sure we're on the same page there's 11 axioms
and only the golden rule uses a conjunction
Treat others like you want them to treat you?
lol
they call it the Golden Rule in my class for some reason lol
That looks like it is in dire need of some explicit brackets.
apparrently you can drop them according to axiom 1 lol
it doesn't seem like any of the axioms use conjunction other than 1
Okay, equivalence is actually associative. But that is one funky set of axioms nonetheless.
That is not the inductive step. You want to show \begin{align*}
\sum_{i=k+1}^{5(k+1)} i&=\sum_{i=k+1}^{5k} i+(5k+1)+(5k+2)+(5k+3)+(5k+4)+(5k+5) \
&=3(k+1)(4(k+1)+1)
\end{align}
Notice the sum also starts a different place, so can’t use inductive hypothesis just yet before fixing that.
huh?
ScapeProf
Compile Error! Click the
reaction for more information.
(You may edit your message to recompile.)
shouldn't it
i=k+1 to 5(k+1) or no?
That is what I wrote?
No?
Your best bet is probably to rewrite each of the "p and q" in the desired equivalence to "p == q == p or q" and hope things look feasible after the dust settles.
1 sec
well
you wrote all the terms
betwen 5k+!
and 5k+5
Because they should be there?
That is what the sum means
if i convert everything to conjunction
and then show the associativity of / is that enough?
Do you agree the 1st equality I wrote is correct and yours is wrong?
Possibly. I'd hope you have proved some laws already that make it more approachable than it looks. I'd need to sit down and meditate over those axioms for a few hours before I can start to give useful advice about how to use them ...
yes
i do
So what are you confused about?
because
u said =
summation +...
the first summation isn't =
to the first one
one startks with i=k
and the other starts with i=k+1
so how are u gonna plug one for the other?
which is
i=k to 5k of i = 3k(4k+1)
You just said “yes I agree yours is true”. Now saying “no I don’t agree”?
Or what are you saying?
No
I said the thing you want to prove is not what you wrote down
Its what I wrote down
You want to show it holds for k+1
Your 1st equality is false like I said
how
are u gonna plug
the first summation at (sk) for first expression?
if they dont match
ok
1 sec
can u type
s(k)?
forget about s(k+1)
Now read the text I said after the equation
Yes what you wrote down for n=k is true
ok
so now
we need to take s(k)
and prove that it's works
for all k
which makes sense
in the summation u wroye
well I dont get the part where
we need to fix it because its starting at different points
maybe thats why I'm confused
||Try adding and subtracting the 1st term||
what do you think about this:
Let a, b, c ∈ Z with a != 0. If there exist integers m and n such that a|(m · b + n · c), then a|b and a|c.
this is not necessarily true
you could have a = 3, b = 2, c = 4, and m = 3, n = 6
glad I am not losing my mind then, thank you for that
I am however losing over this one though at the moment:
Let a, b, c ∈ Z with a != 0. If a|(m · b + n · c) for all integers m and n, then a|b and a|c.
that sounds true but i’m not sure of how to prove it
they say we can prove it to be true like this:
take m = 1, n = 0: a|(1 · b + 0 · c), which is to say a|b
take m = 0, n = 1: a|(0 · b + 1 · c), which is to say a|c
what I do not get is that how come we are allowed to show via two cases, when there is an AND in the conclusion of the statement
are you aware that this doesn’t prove anything
I am aware, and I mentioned that to my professor too
Looks like a good proof to me. What's wrong with it?
i thought you couldn’t just consider one case
or something
idk
i wasn’t really sure
If you're promised that such-and-such holds for all m and n, you're in effect being given infinitely many facts, and you can use as many r few of them to reach your conclusions as you like.
thank you for the ping
would you mind joining in a voice channel to explain why the proof works?
Yes, I would mind.
alright, then do you mind writing out why the proof works?
What about it do you think doesn't work?
I just read this, it is just that, it seems weird to me how you can just use "as many" as you can to prove a statement
^^^^
well, like he said, you know all those cases are true
since it works for any integer value of those two
That's what "for all" means: The statements you can get by plugging in values for m and n are each true, separately.

thank you for that
@craggy juniper @coral parcel
idk how much help i was
but no problem lol
^^^^, you helped here
hey guys
so Im in grade 11 and i just started my functions introductions
relations
so how does -4,-2,2 corespond with 1
I know its not a function because it has 3 y values
but i just dont understand how -4,-2 and 2 all corespond with 1?
That is a drawing of a function. In particular the function f defined by f(-4)=1 and f(-2)=1 and f(2)=1 and f(5)=6.
@loud carbon
Varsity Tutors connects you to top tutors through its award-winning live learning platform for private in-home or online tutoring in your area.
This arrival might help with the idea of mapping
But the problem you have is a mapping or function is a many to one
Here some pictures from google
ok I got it now thanks
il ask for help if i need more
another questions
Im seeing a notation that says (-5,1) (-3,2) (-1,3) (1,2)
nvm
a negation of a statement and the original can't both be true, right?
bc I'm running into the issue where my negation and my original statement are true, so I'm probably negating wrong
Yeah, that's a bad sign.
At least the statement and its negation can't be true at the same time.
so I'm guessing I'm erroneous in converting (1) into the negation (2)? or would it be fine because as long as they're never true with the same x and y then it's fine?
Hmm, that looks like a correct negation to me. Why do you think they're both true?
In particular, u=1 is a counterexample to (2).
for these types of questions should i use
n+k-1 C k
or
n+k-1 C k-1?
Let f (x) = 2x where the domain is the set of real numbers. W hat is f(R)? what is the right way to approach this question?
f(R) is the set of all numbers that the function can give you when you input something from R.
Which real numbers are twice something?
So this discrete math chat is not specifically like for discrete calculus but generally whenever there is something discrete in math?
you can read the channel descriptions for more information
I did
introduction to sets, propositional logic, proofs; elementary number theory, graph theory, combinatorics, basic coding theory, and other discrete subjects. has overlap with other channels.
It basically exists because many universities have a course called "discrete mathematics" covering all the disjointed (!) pieces of math they require computer science or software engineering majors to take, and we can't expect students in such courses to have enough of an overview to know which of 4 or 5 other channels each of their questions fits into.
And now that it does exist, it's also the only good place to talk about certain of the topics which don't really fit naturally in the other "early university" channels, such as graph theory or elementary combinatorics.
Hey just another question, If i am told to prove that something is regular. ik you can make a dfa, then its regular, but the question before it tells me to make a dfa. I also dont think I can use induction in my case as I have nothing to do it over. are there any other methods of proofs use to prove something is regular?
If the task just tells you to prove that such-and-such language is regular, you get to choose the method of proof yourself.
Showing a DFA for the language is one way to conduct such a proof. Other strategies include showing an NFA, or a regular expression, or a regular grammar (but that is essentially just an NFA with different notation), or to apply the Myhill-Nerode theorem if you've learned that.
Using induction is allowed, like in any other proof -- but in most problems of this type there won't really be any way to apply induction as the top-level proof step. Induction always concludes statements of the form "for every natural number n such-and-such is true", and "this particular language is regular" doesn't have that form.
However, it can sometimes be useful to use induction as part of your argument that the DFA/NFA/regex/grammar you showed actually recognizes the language you're looking at. (The details will depend a lot on how the definition of the language is structured, and what your overall strategy is).
can someone explain the difference between "sufficient" and "necessary" regarding some if then condition
I believe sufficient is like 1 or many possible ways
like an or
my questions pertain to these exercieses
I don't know how I could exactly do (a)
I understand (b)
If Joe is eligible for the honors role then he is maintaining a B average.
I just don't see how I can do some implication with (a)
maybe I am not suppose to?
they had this example early in the section
Because for (a) it seems to suggest that there are many ways of being eligible for the honors program and that maintaining the B average is one of many or perhaps the minimum?
wait
maybe the (a) is
If Joe maintains a B average, then Joe is eligible for the honors program.
because say joe doesn't maintain a B average
the whole thing goes True
take the implication "if p then q"
as the "contract" of p -> q isn't held by p
other ways to say it include "p is sufficient for q", "q is necessary for p"
Being an archbishop in the Church of England is a sufficient condition for being a member of the House of Lords. (Both archbishops are automatically members).
But it is not a necessary condition. (The house has some members who are not bishops).
On the other hand, being British is a necessary condition for being a member of the House of Lords. (All the members are British subjects).
But it is not a sufficient condition. (I know a Brit who isn't a member).
okay so I believe I have it correct for my (a) and (b).
(a): If Joe maintains a B average, then Joe is eligible for the honors program.
(b):If Joe is eligible for the honors program, then Joe has maintained a B average
Ahhh i see i was thinking the same thing, I ended up writing out the regular expressions for my dfa, and since I had 4 regular sets, I used a closure property of how the union of regular sets is also regular
Ahhh i see i was thinking the same thing, I ended up writing out the regular expressions for my dfa, and since I had 4 regular sets, I used a closure property of how the union of regular sets is also regular
im not too sure how valid of an argument it was but i think it was enouugh xd
im not too sure how valid of an argument it was but i think it was enouugh xd
I'd follow the hint.
im not sure what the hint is telling me
Instead of men and women, we could also say: Suppose the set A has m elements and B has n elements. If A and B have no elements in common, then how many subsets of size r does A union B have?
still dont get it
What is the answer to my question?
dont know