discrete-math

[vital dew]

RSB

[small plume]

yup

p ^ T ^ ~r then ?

[gaunt nest]

yes that's a good next step

Then you're almost there

[small plume]

hmm

[gaunt nest]

Do you think that $p \wedge \top$ can be simplified?

[vital dew]

RSB

[small plume]

to just T ?

[gaunt nest]

Is that true for all p? What if p is false?

[small plume]

oh wait right

so it equals to p

ohh

I see

got it

[gaunt nest]

Sounds like recognition 🙂

[small plume]

probably should start with demorgans law on this too right?

[gaunt nest]

Yup

Push negations inward

(is it clear what I mean by "inward"?)

[small plume]

like distribute?

[gaunt nest]

I just mean, if you see a thing with parens that's negated, use demorgan to move the negation inside

like $\sim(p \wedge q)$ to $(\sim p \vee \sim q)$

[vital dew]

RSB

[gaunt nest]

The latter has more negations! But they're inside the parens instead of outside

[small plume]

$$ \sim p \land (q \lor \sim r)) \land \sim q $$

[vital dew]

Pingu

[small plume]

correct first step ?

or should I actually distribute the ~ into the (q v ~r) first

before doing the one on the outside

[gaunt nest]

Either way I think

[small plume]

wait am I just done here ?

[gaunt nest]

But be careful with that demorgan

[small plume]

because it looks basically the same as the one on the right

[gaunt nest]

shouldn't you get or not and for the first connective?

[small plume]

hold on let me re-do it

$$ \sim( p \land ({\sim}q \land r)) \land {\sim}q$$

[vital dew]

Pingu

[small plume]

$$ {\sim}p \lor q \lor {\sim} r\land {\sim}q$$

[vital dew]

Pingu

[small plume]

maybe I messed up somewhere

[gaunt nest]

Are you sure you have the question right?

Try filling in p=false, q=true, r=true

Then I think the left side of your question evaluates to false (because it has an "and not q" at the end)

But the right side evaluates to true because (~p ^ q) is true

so they're not equivalent

[small plume]

oh

let me see

oh right

they aren't

so when they aren't logically equivalent only way to show that they're not equal is truth tables?

[gaunt nest]

Ah is this a 'show they're equivalent OR show theyre not' problem?

Like "determine whether they're equivalent"

[gaunt nest]

Aha I see

I guess I just gave you the answer instead of leading you to it, sorry

I can show you how I got there though

Which is that I tried to prove them equivalent using demorgan and the same techniques as before

And if you do that, you'll come down to $(\neg p \wedge \neg q) \vee (\neg q \vee \neg r)$

[vital dew]

RSB

[gaunt nest]

Which you'll notice is a little bit different than the original right hand side, so from that I said, let me find a way to make one true and one false, since they only differ in the first clause, I want to make the second clause false (hence r true), and continued with that kind of reasoning

[small plume]

hmm

[elder berry]

I believe you guys deviated from the right answer at this step ^

T or !r is indeed just T

that yields that ||both statements are logically equivalent||

oh wait nvm

[gaunt nest]

different problem now 🙂

[small plume]

lol

[elder berry]

yeah, got confused, my bad

[gaunt nest]

np

[gaunt nest]

This is an interesting question

I would say, it's enough to show a single row of the truth table that differs

That's what I constructed above

But the problem statement seems to want you to write out the whole thing

[small plume]

yea...

im also doing it in latex so i honestly cant be bothered doing another table

[gaunt nest]

IDK, if I were asked that I would probably just write the single row of the truth table that shows they are inequivalent and write "..." above and below

[small plume]

like this is what I did for the ques before this

but I really dont wanna do another table lol

[gaunt nest]

You know the graders better than I do

All I can say is, from a mathematical standpoint, one row should be enough

[small plume]

but for this question is it even possible to use equivalence laws to show that they aren't equal?

[gaunt nest]

Not reeeeallly

[small plume]

or for any two statements if they aren't equal wouldn't you always want to use truth tables and not equivalence laws

hmm

[gaunt nest]

Like you can show that $p$ and $\sim p$ are not equivalent by showing their conjunction is equivalent to $\bot$

[vital dew]

RSB

[gaunt nest]

But that strategy won't always work

It wont' work here, I believe

[small plume]

damn

im really gonna have to do the whole table

[gaunt nest]

Well, hang on, there's another way maybe

They're not equivalent because there's some values you can substitute in for p,q, and r so that they differ

You could plug that in directly, then use "equivalency" rules to reduce one down to $\top$ and the other to $\bot$

[vital dew]

RSB

[gaunt nest]

That sort of answers the question

And sort of uses equivalencies

Again, if I were grading I would give that full credit, but, you know your course staff better than I do

[small plume]

this is basically my first hw ever so

lol

rip

[gaunt nest]

What kind of class is it

university or high school? for math majors or for everyone? how big?

[small plume]

uni cs

discrete structures

id say only cs and math majors take this if not only cs

[gaunt nest]

you could ask I guess

[small plume]

this is due tn so ig ill just play it safe and do the truth table

[gaunt nest]

"hey professor butthead, do you really want the whole truth table, or is just a row enough"

well you could do the whole truth table and also ask

[small plume]

the thing with truth tables I'm supposed to do them like this

so it's even longer

smh

[gaunt nest]

ah

well

you could write a latex macro that you just fill in the formula and it will make the truth table in that format for you

that will certainly take you much much longer

but it would be more fun

[small plume]

probably too much of a noob to do that

not that experienced in latex tbh

[gaunt nest]

i'm mostly joking

[small plume]

lol

[gaunt nest]

you could do that in latex but it would take forever

[small plume]

wait for what values did you say they were not equivalent?

I can just test that first and stop

[gaunt nest]

yes that's what i'm hoping you can do, leave the rest blank

[small plume]

I just need to know how to create the table now

because I just copied these tables sfrom my professors tex file

and filled them in

[gaunt nest]

incidentally, math and cs people write truth tables the way you do

my father studied formal logic as a philosopher and they start from all trues on the top to all falses on the bottom

(which is terrible)

[small plume]

hmm

interesting

[gaunt nest]

he was actually kind of disturbed to find that we do it "backwards"

but we do it the right way, imo, because that left hand side is counting up in binary

BUT it was a philospher, not a mathematician, who invented the truth table!

but...

i'm rambling now

[small plume]

lol

it's all good

by any chance do you have experience in latex

[gaunt nest]

DO I EVER

do you have a latex q?

[small plume]

just kinda need help w making the table

[gaunt nest]

sure, why don't you show me what you've tried already over in #latex-help

[small plume]

well it seems I have figured it out @gaunt nest

thanks anyway

[gaunt nest]

👍

[snow cedar]

can someone help me with breaking the problem down

[vague garden]

could someone help me with

[void crypt]

hey guys i found thesis papers entitled Optimal labelling of their respective chosen graph, i cant check the thesis papers. I’m wondering what is the definition of Optimal labelling in graph theory?

[ornate badge]

hi anyone know what this is pls

[pine lion]

For the right sum, you can develop the five on all terms, so you would obtain the sum of 20-5k, and since both sum are from one to n, you can add each k-th term of the first sum to the k-th term of the second sum.

[next sail]

is there a way to prove this? or is it by definition?

since D is the domain for both predicates, i believe that they're equivalent...

[grand totem]

The left side does imply the right side, but the converse doesn't generally hold. So they're not equivalent

[next sail]

but the conditional does hold, right? so wouldn't it be equivalent since we're only considering the conditional not the converse?

[grand totem]

I'm not quite sure what you mean.
$\forall x(P(x)\to Q(x))$ does imply $(\forall x P(x)) \to\forall x Q(x)$, but the two are not equivalent

[vital dew]

Neverbloom

[next sail]

they both do have the same truth value given the domain D, right?

[grand totem]

No, suppose D = {0, 1}
And suppose that:
P(0) holds, but both Q(0) and P(1) don't hold

[next sail]

i meant if the LHS is true, then the RHS will also be true and if the LHS is false, then the RHS is also false

right?

so they're equivalent i believe

[grand totem]

if the LHS is true, then the RHS will be as well, yes. But the situation I explained above gives a counterexample to your other claim

[next sail]

yeah i don't really understand that part

can you explain that in more detail?

[void crypt]

anyone here familiar with harmonious labelling in graphs?

[grand totem]

If the domain consists of two elements (namely 0 and 1) and we know that
P(0) is true, Q(0) is false and P(1) is false (the truth value of Q(1) won't matter for our argument, so let it be whatever you want), then what can you say about the following propositions:

1. P(0) -> Q(0)
2. ∀x∈D [P(x) -> Q(x)]
3. ∀x∈D P(x)
4. [∀x∈D P(x)] -> [∀x∈D Q(x)]

Notice that (2) is the left side of your proposed equivalence and (4) the right one

[next sail]

the statement (1), (2) and (4) would false then?

[grand totem]

(1) is false (why?) and that (2) is also false follows from (1) being false (why?)
(4) is actually true, but it's worth thinking about (3) first as the proposition (3) occurs in (4), namely as the premise of the implication

[next sail]

right, (3) will be true, but how is (4) true?

[grand totem]

(3) will not be true

[next sail]

oh right, my bad 😭

so is (4) true?

i don't think so but now i'm kinda confuesd

[grand totem]

P(0) is true, but P(1) is not, so P(x) can't be true for all x in D (as it isn't true for x = 1)

[grand totem]

Well what you can say about the truth of the implication A -> B when you know that A is false

[next sail]

we can't say much but we take it as true?

vacuously true

now that you say that, does that mean when we have
∀x∈D [P(x) -> Q(x)]

the value of x in each predicate must be the same right? as in we'll have
P(0)->Q(0) AND P(1)->Q(1)? (i used AND since universal quantifier is a generalization of AND statements)

but it's not the same with (4), right? for (4), we could have
P(0) -> Q(1) right?

[grand totem]

that is correct, A -> B will be (vacuously) true when A is false

[next sail]

yeapp

[grand totem]

the idea of writing ∀x∈D P(x) as P(0)->Q(0) AND P(1)->Q(1) (when D = {0,1}) is a good idea, but

the value of x in each predicate must be the same right?
Is not what the connective -> tells you, i.e. A -> B doesn't mean "A and B have the same truth value"

Oh wait I think I misunderstood what you were trying to say. You weren't claiming that the truth values are the same for each x, but making an argument for why you may rewrite ∀x∈D P(x) as P(0)->Q(0) AND P(1)->Q(1)

[next sail]

yeapp

[grand totem]

Not quite, rewriting [∀x∈D P(x)] -> [∀x∈D Q(x)] would lead to
[P(0) AND P(1)] -> [Q(0) AND Q(1)]

[next sail]

i see

so the (4) will also be vacuously true then?

since the hypothesis is false

namely, P(1) is false

[grand totem]

Yes

So you were claiming that
LHS false => RHS false, or equivalently (think about contrapositive if that was covered in your class)
RHS => LHS

but we found an example where the RHS is true and LHS is false

[next sail]

LHS will be false when x=0?

[grand totem]

x isn't a free variable (on either side) in your original question so that doesn't make much sense
What you were claiming was that
If [∀x∈D P(x)] -> [∀x∈D Q(x)] holds, then so does ∀x∈D [P(x) -> Q(x)]

But our example (with D = {0,1} and truth values of P, Q as before) made [∀x∈D P(x)] -> [∀x∈D Q(x)] true and ∀x∈D [P(x) -> Q(x)] false.

[next sail]

i see

so they're both not equivalent then

[∀x∈D P(x)] -> [∀x∈D Q(x)] this means (P(0) AND P(1))->(Q(0) AND Q(1))
while ∀x∈D [P(x) -> Q(x)] means P(0)->Q(0) AND P(1)->Q(1)

[gleaming gulch]

if we converted that to DFA is this what it would look like?

[grand totem]

they aren't equivalent; summing up:
If ∀x∈D [P(x) -> Q(x)], then [∀x∈D P(x)] -> [∀x∈D Q(x)]. That direction works out just fine (and is a good thing to know about)
But we generally do not have that if [∀x∈D P(x)] -> [∀x∈D Q(x)] then ∀x∈D [P(x) -> Q(x)] (as we found a counterexample that makes the premise true and the conclusion false)

[next sail]

alright, thanks a lot! that clears up a lot of things

[snow cedar]

are we supposed to substitute here?

[steady path]

I think so, you might try forming the function E^2(f) first to make sure you understand what's going on.

[hexed shore]

In how many ways can you choose eight coins in a piggy bank containing 100 identical one hundred coins and 80 identical five hundred coins?

[woeful raft]

would someone be able to explain vacuous logic to me?
to get specific, the problem I've encountered this on was figuring out the properties of the relation where it's just the empty set

[vital jolt]

I don't quite understand additively indecomposable limit ordinals

what exactly does the definition mean?

[coral parcel]

This definition? https://en.wikipedia.org/wiki/Additively_indecomposable_ordinal

[weary tiger]

Sure. What is your question?

Although "harmonious labelling" is really context-specific

[ripe mulch]

so if a number only have 3 divisors, would the only numbers that satisfy this have be a perfect square? 1 * itself and SQUARE_ROOT * SQUARE_ROOT which would make the divsors 1, SQUARE_ROOT and itself

[little prism]

it has to be a square, yes

you can limit it even further

not all squares have 3 divisors

eg 16

[frigid lion]

Hi

I don't understand how they got that

[little prism]

basic properties of real numbers

if a is not zero then a^(-1)=1/a exists and is a real number

R is a field

[frigid lion]

oh

didn't think of it that way

[grim tapir]

what does this mean bruh, why is (Z_26)^m

[little prism]

Z_26 is the integers mod 26

(Z_26)^m means that you have the cartesian product of that with itself m times

so m coordinates where in each one you are in Z_26

[grim tapir]

tbf the definitio nof P and C were confusing

it says they are the set of all plaintexts and cipher texts

what does it mean the set of all plaintext

[little prism]

well the set that contains all possible plaintexts

[grim tapir]

the plaintext can be so many things though

[little prism]

and?

[grim tapir]

how can it be encoded with just alphabet

[little prism]

do you know the caesar cipher

[grim tapir]

yeah they mentioned that

[little prism]

if you have a word ABCD for example, it shifts each letter by a fixed amount. eg 3 letters to get DEFG

[grim tapir]

sure

the examples for the encryption make sense just dont get the notation really

like this is the vigenere cipher

[little prism]

yes

math likes numbers over letters, so instead we use those

so instead of ABCD we write (1,2,3,4)

and then shift to (4,5,6,7)

[grim tapir]

what does it mean to raise the power of plaintex by m

[little prism]

that isn't done here

we raise a set to the power m

[grim tapir]

well yeah in caser it aint

[little prism]

A^m means the cartesian product of A with itself m times

do you mean RSA or something

[grim tapir]

I'm trying to understand from the original image i sent

what the notation even means

its describing the vigenere cipher which i understand but dont know what the maths is saying exactly

but yeah

[little prism]

do you know what cartesian products are

[grim tapir]

vaguley, its just the set of tuples i think

[little prism]

yes

all possible tuples

[grim tapir]

of length m

[little prism]

in our case, yes

[grim tapir]

if our key is RPI , plaintext HELLO, it gets encrypted using RPIRP etc

but i still dont get what it means the set of all plaintexts

that doesnt mean anything

[little prism]

"the set of all words of length m"

just all possible things we could encode

[grim tapir]

hello is not length m though

[little prism]

m=5

[grim tapir]

i thought m was the keylength

[little prism]

well in that notation the key and plaintext need to have the same length

so RPI wouldn't be a valid key

RPIRP would be tho

[grim tapir]

but what does the notation say about RPI then

or the phrase that repeats

thats whats confusing

[little prism]

nothing in this notation says anything about keys that repeat

RPIRP is a key

RPI isn't

AGUAT is a key

all 5 letter words are keys

[grim tapir]

what does it even say then if its not describign the vig cipher

[little prism]

it is describing the vig cipher

just for only one repetition

[grim tapir]

how does it relate to the graph though

[little prism]

what graph

[grim tapir]

where you map 2 letters to 1

[little prism]

what

[grim tapir]

thats the cipher

if we have plaintext HELLO

key RPIRP

we read H and R > obtain a letter which is the first letter of the ciphertex

[little prism]

so HELLO gets translated to (8,5,12,12,15) and RPIRP gets translated to (18,16,9,18,16)

then you add them mod 26 in each coordinate

so (26, 21, 21, 30,31) = (26, 21, 21, 4, 5) which gets translated back to ZUUDE

[grim tapir]

what is the x_1, x_m in this case its just the RPIRP or HELLO

or both

[little prism]

(x_1, x_2, x_3, x_4, x_5) = (8,5,12,12,15)

(k_1, k_2, k_3, k_4, k_5) = (18, 16, 9, 18, 16)

[grim tapir]

okay so each of those letters + the corresponding key

so RPIRP is acc denoted as being a set of keys

not a single key

[little prism]

it's just a single key

not a set

[grim tapir]

surely not it says its a set

[little prism]

no

[little prism]

curly K is the set of all keys

but each key is just a single tuple

not a set on its own

[grim tapir]

all keys up to length m

?

[little prism]

all keys of exactly length m

[grim tapir]

it says k1, k2, km so it would have 3 keys if we have length m

does not mention the length tbf

[little prism]

k_1, k_2 etc are the letters of the key

it's still just one key

[grim tapir]

thats so confusing to say

what so K is the set of all keys length m, but does not mention anything about what the characters of the key can be

regarding the numbers they are

[little prism]

yeah that is bad notation

[grim tapir]

the plaintext is length m and 0 - 25

[little prism]

it should also say K = (Z_26)^m

[grim tapir]

but then the guy mentions further that a phrase is used generally

such as RPI

which repeats over the plaintext

[little prism]

from the phrase RPI you can generate a key, here RPIRP

[grim tapir]

how would that be expressed formally

[little prism]

but RPI is not a key in itself

[grim tapir]

yeah sure

[little prism]

that would be slightly painful to express formally

[grim tapir]

but two people need to know the letters being repeated

but yeah so how does modular 26 come into all of this

[little prism]

key_gen(a1, a2, a3) = (a1, a2, a3, a1, a2, ..., ai) where the ai is whatever you end up with

stuff like that

[grim tapir]

like if x_1 + k_1 > 25 > loop back etc

so its basically

[little prism]

like I did here

with the numbers over 26 I reduced them

[grim tapir]

take a letter from original plantext > read the key > use that as the offset

repeat for the entire keystream

[little prism]

yes

[grim tapir]

but yeah thats fair the notation doesnt technically need to mention how the key works

just that its length m

its implied that its in Z_26 but yeah surely should be clear about that

but i guess it techncially doesnt need to be 0 - 26?

if the key was (1255455,356356,35757) it would still work for (5,14,23) lmao

[little prism]

yes

[grim tapir]

okay yeah and obv Z_26 is like

(0,1,2,...,25,0,1,2, ...)

or 1 26 whatever

and (Z_26)^m is like {(0,1,2),(0,1,3),(25,21,0), ....} etc

which is finite , but surely if it wasnt modulo this set with m is infinite

obv

[woeful raft]

what kind of proof should I use for this? I've tried doing contradiction, but I've reached a case that I don't know if I can prove

[little prism]

yes

[little prism]

you could show it's monotone

and calculate the limits for x-> +- infty

[mortal coyote]

Im a litte confused with relational databases

[woeful raft]

as in strictly monotically increasing? And if I do that, why would I need to show the limits?

[void crypt]

ohh hey there, im wondering if there’s an easy way to label a graph harmoniously. I’m working with Z mod 20 graph n=11

[next sail]

hi, i've got a question about predicates. when can we say that two predicates are equal and when can we say that two predicates are logically equivalent?

[spiral aspen]

can someone explain this proof for me? I dont understand it.

the question is Show that
0 + a ≡ a + 0 ≡ a (mod n)
for all a ∈ Zn

I do understand the thing on top (so the thing before kn+a ≡ a+kn ≡ a)

but i am lost when they use the division algorithm.

the way I tried proving it was different. I said that since 0+a and a+0 give the same remainder a they are congruent. (a < n)

[coral parcel]

The word "predicate" is used in a number of contexts, for slight different purposes. In some of these contexts it is useful to distinguish between "equal" and "equivalent", in others it is not.

In general "equivalent" would mean that the two predicates have the same truth values on all inputs.
It varies more whether one needs to speak about a more discerning kind of "sameness" where we might want to consider two predicates to be different "things" even if they agree about their answers.

For example, in a context where a predicate means a concrete string of symbols, "x>5 or x<3" and "x<3 or x>5" are plainly different strings of symbols, but they will be equivalent when interpreted for their meaning.

[coral parcel]

Yeah, on the face of it, this proof makes little sense. If ___ == ___ (mod ___) is a relation between three concrete integers (as the notation strongly suggests), then the only proof a + 0 == a (mod n) needs is to say that the left-hand side a+0 is the same as a according to plain old integer arithmetic, and we hopefully already know that a == a (mod n).

I think what the author must have been trying to show was [a] + [0] = [a], where the + is now an addition operation defined on equivalence classes modulo n, and the point would be that the equivalence class [0] is a identity for this new addition operation. But then apparently they got confused by their own (lack of) notation or something.

But even in that case, the proof is rather strange. Speaking about kn seems to be pointless if you have proved that the outcome of addition of equivalence classes is independent of which representative of the class you calculate with. And if you haven't proved that fact yet, then I think what your screenshot does is not enough to work around the lack of it.

[spiral aspen]

thanks! I did find it confusing. For the question"Prove that there is a multiplicative identity for the integers
modulo n:" a · 1 ≡ a (mod n). is it enough to say that for a*b ≡ a mod n this is true for b=1 because LHS and RHS will give same remainder?

[coral parcel]

It should be enough, if your arithmetic operations have been defined in a sane way.

And you could even say: because LHS and RHS are the same number and therefore of course have the same remainder.

[spiral aspen]

yeah and i could add that its gonna be" a " because a<n (because a is an element of Zn)

[coral parcel]

That is not necessary for the proof, though.

[spiral aspen]

but shouldnt the remainder be a?

[coral parcel]

It doesn't matter what it is. We could equally well say, for example 17·1 == 17 (mod 5) -- and that's true because the remainder of 17 divided by 5 will surely be the same both times we do the exact same division. We don't need to actually figure out what that remainder is in order to be sure it won't change.

[spiral aspen]

ahh i see

thanks!

[wise nexus]

You really think this is discrete math stuff? Lol

Memes go in #chill

[wise nexus]

P and Q are Logically equivalent if P implies Q and Q implies P

[vital dew]

DarQ

[wise nexus]

Now I'm not sure if I've ever heard of a notion of equality of predacates

[wise nexus]

This could very well mean they're equal, for the record

But it's prolly just some semantic jargon non sense that you needn't worry about

[woeful raft]

is my proof here enough? I can’t tell if my proofs have enough substance unless they’re more direct

I don’t know if I can readily claim my “if, then” statements. But if I need to show more work to make those claims, then I don’t know how to do it other than a direct proof, which I had gotten really far on, but there was one flaw I didn’t know how to fix

[brave rock]

If x = y, then f(x) = f(y)
This is true for all functions, and does not show anything about whether or not f is one-to-one.

I cannot tell what you're proving here.

It would be true that if f is strictly increasing, then it would be injective, but you don't seem to have proved that either.

I like the drawing tho :)

[woeful raft]

I was trying to make the statement to show the strictness based on the definition, because it felt the need to specify that fact in there

lol thanks ahah

[brave rock]

OK well you have stated that it is increasing, but not strictly

and you have not proved it

[woeful raft]

do I need to show it algebraically?

[brave rock]

I'm not sure why you're defining the relations P and Q when you already have the symbol <

[brave rock]

You need to show it.

[woeful raft]

because in my lecture notes monotonicity is defined by partial order relations

and < is not a POR

[brave rock]

But <= is

[woeful raft]

correct, which is why I used it

[brave rock]

But you redefined it as Q which is exactly why I'm saying any of this

[woeful raft]

I tried proving it with a contradiction yesterday

[analog flare]

Sorry sir

[woeful raft]

it went really well except for one flaw that I couldn’t figure out

I wasn’t using it as the symbol to represent any specific relation

I was just trying to show the relation between two elements as <=

so what direction would you suggest?

I’m very inexperienced with proofs so I don’t know what is considered obvious and what isn’t

i.e. how much I should show when it feels apparent. 9 time out of 10 the fact I’m trying to prove is clear to me, but I don’t know how to represent my logic mathematically or explain it

https://cdn.discordapp.com/attachments/1015330219739054151/1074070190616232087/IMG_1021.jpg

the flaw here is the case where the two pieces in parentheses add up to zero, but don’t equal zero, so I don’t think this is enough. But the parentheses singled out are really simple to show x=y

[slender breach]

Is there a specific name for a graph or path/circuit that is both Hamiltonian and Eulerian?

[hidden patrol]

A Hamiltonian eulerian graph

[coral parcel]

Such a path is called "all the way around the cycle graph",

[spiral aspen]

gcd(a, b). the question is what can u say about gcd(a, b)
as+ bt = 2?
would the answer be gcd(a, b) =2?

and gcd(a,b) would also divide 1.

as+ bt = 6
and for this gcd(a, b) would mean it divides a b and 6 (and 1, 2, 3)

but in the answer sheet its written that gcd(a, b) = 1, 2, 3, or 6. But isnt gcd the greatest common divisor? so its just 6?

[sudden minnow]

gcd is the greatest common divisor for one (a,b) pair

you are going through all possible (a,b) pairs that satisfy the equation and looking at their gcd

[spiral aspen]

ahh ok thanks

[vital dew]

Pingu

[small plume]

nvm lol

[leaden jay]

Does anyone have any ideas?

[royal holly]

could someone explain what they did here

[olive relic]

an implication $A \to B$ can always be rewritten in the form $\neg A \vee B$ (read as ``(not $A$) or $B")

[vital dew]

rob
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[olive relic]

Then negated with de Morgan's laws

The reason is because "if A is true, then B must necessarily also be true" can be restated as "A can't be true when B is false"

or $\neg(A \wedge \neg B)$

[vital dew]

rob

[royal holly]

how do you know what symbol to us

in these equations

[floral moss]

are you talking about the quantifiers? (upside down A and backwards E)

[royal holly]

the ANd and the conditional

[floral moss]

oh

for all needs implication and there exists uses and

let me give example

if you have forall x (P(x) /\ Q(x))

that is literally saying for all of the universe, both P(x) and Q(x) are true, which is almost never going to be what you are trying to say. whereas with the implication we are saying: for all of the universe IF P(x) THEN Q(x). So for all of the universe, IF you are a mammal THEN you have hair. vs using /\ would be all of the universe is a mammal and has hair

to be clear, I'm a student in discrete math so if you are looking for a more polished answer, wait for someone else to explain it but that is how my professor explained it to us

[vital jolt]

yes

[ebon berry]

hi

is anyone up..

[meager prairie]

why u ask to ask

[ebon berry]

i need help with discrete math

[sudden minnow]

just ask the damn question mate

[ebon berry]

i did

its in help

[meager prairie]

you are making it harder to help you

lol

i have no idea what that means

[ebon berry]

o

should i just ask here

[meager prairie]

are you fucking with us on purpose

[ebon berry]

? no

im srry :/ its a genuine question i dont get it?

i thought you cant ask questions in any section

you have to ask in help

which i did

#help-2

[grim tapir]

im confused what pi_s actually does tbf

like we have l bits of some string

and it defines a mapping that like jumbles up the character or sumn

but like does the A bits mean like the bits in unicode form?

or am i just thinking about it wrong way like it just takes some arbritary stream of bits with an invertible substituion operation for decryption

[leaden jay]

Any thoughts? I got 45…

[weary tiger]

Anyone know what this is asking

[tame bone]

someone german? jemand deutsch?

[grand totem]

Just ask your question and do your best to translate it into English

[sacred fern]

for this one why cant I just fix 2 spots, leaving 6 open hence 2^6 choices then multiply by the number of ways to permute 2 things in 8 spots?

[brave rock]

you will double count a lot

Small example: if I look at binary strings of length 3, then 111 is counted three times by your method.

[sacred fern]

how would I fix this?

[brave rock]

Trying a different method

[sacred fern]

is the answer 2^8 - 9?

[brave rock]

yup

[sacred fern]

ok thank you

[spiral aspen]

what do they mean by cannot fold upon itself?

[bitter slate]

I have this problem for discrete math II and I wanna make sure that I’m approaching it the right way and how I would go on from where I stopped if I did do everything else correctly

[uneven condor]

3^2 is 9 right?

[red rover]

otherwise known as 3x3

or 3 + 3 + 3

[broken sonnet]

I have a feeling that I may need to use strong induction to solve this one, because of that fact that there can be two cases for p. But at the same time I not sure if I am thinking about it in the correct way. Can someone give me some pointers please?

[stray reef]

yeah gonna need strong induction on this one and not in the sense you wrote

assuming all numbers smaller than n can be written in the form 2^p * d, do the following:

• if n is even, write n/2 in this form, so that n/2 = 2^p * d; then n = 2^(p+1) * d
• if n is odd, take p = 0 and d = n.

[sick lantern]

How is the first expression correct and the second wrong,
why is there a for all x anyway, because if I choose x to be 1
and y also to be 1 in the first and the second case the implication goes haywire.

[broken sonnet]

i used a slightly different approach

[smoky herald]

What means exactly "left-induced"

it refers to asociativity????

[brave rock]

No, it does not refer to associativity

I don't know how to explain it better than how they've written it there.

You should try to finish the exercise to discover more about it.

[smoky herald]

okay, thank you very much

[devout stag]

Anyone know how I can go to solve this?

[snow cedar]

does anyone know about isomorphic graph? im not sure how to think about the last question

when it says "can you tell why?"

[brave rock]

It's asking you to think of some feature that distinguishes the two graphs

I suggest you should try to be creative and find one for yourself, then prove that the property you found prohibits isomorphisms.

[snow cedar]

maybe because theres a cycle and theres no vertex part of the cycle connected to two other vertices?

[snow cedar]

another question i had, not sure how to break this down

[vital dew]

Pingu

[small plume]

for questions involving p implies q like this is it just to think of it in terms of

[vital dew]

Pingu

[small plume]

like I just can't fathom it in english

like how does If you follow your dreams, then you will find happiness mean the same thing as Either you don't follow your dreams or you will find happiness

[small plume]

yea no

most straight forward math ive done is till calculus

only gets worse from here

any chance you understand like how does If you follow your dreams, then you will find happiness mean the same thing as Either you don't follow your dreams or you will find happiness

like idk how to make sense of these in my head

lol

I see what you're trying to say I think

like the then doesn't imply casual

but in like the real world if ur talking to someone it does

but that's the weird part abt this ig

vacuously true

[snow cedar]

can someone help for this, im trying to use the binomial coefficient. or do i not need that

[sacred fern]

How many pairs can you form with 15 greed and 15 red balls?

[glacial flame]

I remember there being some special term for converting a forall statement to something else (I believe to “arbitrary”); is it called something like instantiation?

I feel like my prof mentioned something about when starting with a forall and ending up with a different form of saying it (all in formal writing), it’s called something special.

(It was an off handed remark and it was a few months back, so I can’t remember it very well.)

[haughty garden]

The idea is that: following your dreams will always lead to happiness, or at least it should always lead to happiness. However, if you don’t follow your dreams, you can choose to be happy or not with that choice. So not following your dreams gives you any outcome of whether you find happiness, the implication still holds. This is equivalent to the “you don’t follow your dreams”. However, if you’re always happy, then it didn’t matter whether you followed your dreams or not because either outcome led to the conclusion that you were happy. This is equivalent to the “or you will find happiness”

[hard fern]

any advice on how to start a proof

im new to discrete math and i follow all the logic i just have a hard time knowing where to start when writing a proof

[brave rock]

Depends on the proof

[shell loom]

for the last 2 steps am I allowed to do that since a+b is an integer?

[fresh laurel]

I k

[tawny mist]

In a large marathon, runners start the race in stages. Tim started in group E and ran at a rate of 5.7 miles per hour. During the race he was passed by Lorenzo who ran at a rate of 6.2 miles per hour and started in group H. 5 minutes after Tim started. How far did Tim run before he was passed by Lorenzo?

If the answer is not an integer, enter it as an exact decimal.

What's the answer & how to solve it❓

[halcyon onyx]

tim ran 19/40=0.475miles when Lorenzo was just abt to start running. Since Lorenzo runs 0.5miles per hour faster then Tim, lets say that Tim doesn't move, and Lorenzo runs 0.5miles per hour. so Lorenzo ran for 0.95hrs until he passed Tim. so the answer would be 0.475+5.415=5.89miles

[magic knoll]

any hints?

[chrome fossil]

Find number of binary strings of length n with w as a subsequence

[slender crest]

My solution was total possible - passwords with no digits - passwords with 1 digit.
Correct?

[cinder crane]

hi help me

[magic knoll]

easier said than done

[slender crest]

How to go upon creating FA or CFG with certain conditions such as "accept all binary strings with at most one occurrence of 000"

I understand both FA and CFG but creating them with such conditions seems so difficult. Spending way too much time trying to solve these.

Any tips?

[stuck sigil]

Hi there, I want to know, why in (math, CS) absolute value and module (or rest), often called same word?

[little prism]

Technically its modulus for absolute value, and modulo for remainders.

Probably just some historical coincidence

Just like a billion different things are called normal in math

[stuck sigil]

thanks

[little prism]

well you dont assume that

you show that

[hoary cloak]

hey so does anyone know some survey on (x, y) values for the tutte polynomial for different graph invariants?

i have one here that presented five properties, but it sounds like there's a lot more

[magic knoll]

anyone?

seems like subsequence of fixed length have the same count

but idk how to show that

[grim tapir]

im looking at SPNs atm and they mentioned this example

why is the key that length but each round is 4 strings of 4 bits of state

like what even is the difference between the key and the key rounds tbh kinda confused

[coral parcel]

Strictly speaking there's no such thing as "a modulo". When we say something like "38 and 16 are congruent modulo 11", the origin of this wording is not "the modulo is 11", but "congruent when we use the modulus 11". (Modulo in Latin is the word modulus declined in the ablative, or instrumental, case).

[vivid gust]

does anyone understand cryptography and can explain to me how it works?

i know it's like secret code

[coral parcel]

That's an extremely broad question.

[vivid gust]

but how is 26 ≡ -16 mod 3?

[coral parcel]

Their difference is 42, which is a multiple of 3.

[vivid gust]

how do we find the difference?

like mod 3 means the remainder is 3 correct?

[coral parcel]

By subtracting the two numbers?

[vivid gust]

so we do -16 - 26?

[coral parcel]

Yeah, though I did it the other way around: 26 - (-16).

[vivid gust]

and why is there a 3?

[coral parcel]

That specifies which kind of congruence between 26 and -16 we're talking about.

[vivid gust]

im confused

how does that work?

what does 3 have to do with anything?

?

[remote crane]

Any hints on howw to show this without pulling a trick out of a hat?

[coral parcel]

It's simply part of what's being claimed. For example, "26 ≡ -16 mod 3" and "26 ≡ -16 mod 7" are both true, because 42 is a multiple of 3 and is also a multiple of 7. But "26 ≡ -16 mod 5" and "26 ≡ -16 mod 22" are both false claims because 42 is not a multiple of 5, and is not a multiple of 22 either.

Note that the "mod 3" is a specification that qualifies the entire "26 ≡ -16" part of the claim. It does not attach stronger to the -16.
In other words "26 ≡ -16 mod 3" is not a claim that a particular relation exists between the number 26 and something called "-16 mod 3".

[broken sonnet]

I'm a little confused with some set notation, could someone explain to me the difference

Let $S = {1, 2 ,3, ..., n}$ versus $S_{n} = {1, 2, 3, ..., n}$

[vital dew]

phamous

[little prism]

well in the first case they call the set S and in the second case they call it S_n

its just a different name

[broken sonnet]

so do they both mean the same?

[little prism]

presumably in the first case n is fixed and doesn't change, while in the second it can change

well they are the same set, just a different name

whether you count that as meaning the same, no clue

[broken sonnet]

ok because im trying apply the same approach that I saw my discrete math book to another problem, I'm just confused while trying to adapt it

[coral parcel]

It depends on what you're going to use your definition for.

If you need to have different variants of the set around for different n's, you need to make the n part of the name of the each of the sets so you ca distinguish between them.

[broken sonnet]

for example, the problem in the book is to find the recurrence relation for the set $S_{n} = {1, 2, 3, ..., n}$, where the subsets contain no consecutive integers. So in this problem, we don't know what $n$ is, since it can be any number greater than 2.

[vital dew]

phamous

[broken sonnet]

I'm trying to adapt approach to a finding the recurrence relation for 26 letters of the alphabet, where the subset does not contain consecutive letters. For example, ${}, {a}, {a,z}$ are all permissible subsets, but ${a,b}$ is not

[vital dew]

phamous

[broken sonnet]

so obviously the set $S = {a, b, c,...,z}$ is fixed.

[vital dew]

phamous

[fossil mural]

...wait, what exactly do you mean by "recurrence relation" here?

[broken sonnet]

ok ill show you have i have, so you have a better understanding what the problem

im just having trouble conveying a certain idea using math logic

[coral parcel]

If you want a recurrence then that means you're going to speak about both S_{n} and S_{n-1} at the same time (and for this particular problem the neatest solution also speaks about S_{n-2}). So you won't get away with simply calling all of those sets S.

[coral parcel]

... wait a moment, isn't that just asking for the answer to the previous problem when n=26 specifically? How would there be a "recurrence" if all you're interested in here it the n=26 case?

Can you show the exact statement of the second problem, exactly as it was given to you?

[broken sonnet]

so im trying to use this approach from the book below:

this approach solves the problem for consecutive integers, where n >= 2

im confused because we're saying n is the size of the subset, but then we say n is also an element

its like we're assigning 2 different meanings to n

which i don't understand

[fossil mural]

well n is a number

and these sets contain numbers

[broken sonnet]

so would the subset S_1 be just a subset of {1}?

and S_2 be a subset of {1, 2}?

[fossil mural]

well S_1 is just a set, it's not really a subset of anything in particular

[broken sonnet]

ok

[fossil mural]

S_1 is {1}, S_2 is {1, 2}, S_3 is {1, 2, 3}, and so on

[broken sonnet]

so basically S_n denotes the nth subset

[fossil mural]

...subset of what?

[broken sonnet]

what it contains is just some elements of S

[fossil mural]

no there's no "S"

we're just considering a set like {1, 2, 3} or {1, 2, 3, 4}

the subscript n is part of the name of the set
we could have called them A = {1}, B = {1, 2}, C = {1, 2, 3}, D = {1, 2, 3, 4}, but putting the number somewhere in the name of the set is more convenient for when we want to talk about all of them at the same time

[coral parcel]

Instead of tying to replicate the proof of the situation with integers, I think your strategy should be to apply the earlier result.

Establish a bijection of {a,b,...,z} with {1,2,...26} such that the subsets of {a,b,...,z} you want to count correspond to the subset of {1,2,...,26} you have already counted.

Since there F_26 of the latter, that is also the number of good subsets of {a,b,...,z}.

[broken sonnet]

ok

i wanted to say something like Let S ={a, b, c,... ,z} and their respective positions are p_1, p_2, p_3,..., p_26 such that p_i = s_i.

go from the perspective of the letters themselves

[cerulean slate]

Can someone explain why 5+6+7+8+ ... + 50 is not the same as 1+2+3+4+...+46?

Cant I just subtract 4 from each term in the sequence

[stray reef]

imagine you have a group of friends each with some money in their wallet

and you have them all pay you $4

do you agree that the total amount of money shared by them (not including you) would change

@cerulean slate

[cerulean slate]

yeah

i just feel really stupid now lol

[safe carbon]

Can anyone help me with this: A sequence {an} is defined recursively by a1 = 2, a2 = 2 and an = an−2an−1 for n ≥ 1

[stray reef]

what's the goal?

to find $a_{420} - a_{69}$?

[vital dew]

Ann

[coral parcel]

Be nice.

[safe carbon]

sorry I need to find an equation for all an when n>= 1 in terms of n

[coral parcel]

As Ann says it is not clear what it is you want to do with that definitions -- but if your post means what I guess it means, most things you might want to do will become easier if you define a new sequence b_n = log2(a_n).

[safe carbon]

shouldve made that clear

[stray reef]

right, okay

and just to make sure,

[coral parcel]

And express your recurrence (which I assume means $a_n = a_{n-2} a_{n-1}$ rather than $a_n = a_n - 2a_n - 1$) in terms of the $b_n$s instead.

[stray reef]

you mean $a_n = a_{n-1} a_{n-2}$?

[vital dew]

Ann

Troposphere

[stray reef]

it's better to see a screenshot of the problem as it was given originally

since math notation has the unfortunate tendency to get butchered if posted as plaintext

[coral parcel]

Part (a) of these, at least, should be purely mechanical.

If you've already done that, what did you get?

Not that this exercise is not asking you to "apply the standard procedure for finding the equation" -- there's no such standard procedure to apply! It's asking you to compute the first few terms explicitly and then guess based on what you see.

[safe carbon]

Yes I got 4,8,32,256

I’m just trying to guess a formula and I can’t seem to find anything that works for all

[coral parcel]

Now you might recognize that these are all powers of 2. Perhaps if you write down which powers of 2, it might be clearer. Don't forget the initial "2,2,".

[safe carbon]

Yeah I found 2^n-1 works for all except a1

[coral parcel]

How does that work for a_6?

[safe carbon]

I haven’t checked that

Do you have a suggestion for a formula to try?

[coral parcel]

I gave a suggestion here, which apparently you have not followed yet.

[sage lance]

What is the point of the Utility Graph? Is it more of a "fun" graph or does it have a general purpose? For reference, here is what I am talking about:

[vital dew]

TheCedarPrince

[sage lance]

Properties:

• Only one Utility Graph exists
• Based on trying to map three utility companies to three houses.
  • Requires one to not cross any lines
  • Cannot be done

[spiral aspen]

I dont understand whAt they are trying to say here. Could soneone explain? (For more context its about color refinement and alpha i thjnk represents a vertex color)

[coral parcel]

It is one of the two fundamental ways to make a graph that cannot be drawn in a flat plane without crossing edges. (See "Wagner's theorem", "Kuratowski's theorem").

[sage lance]

Oh perfect. I am coming up on Wagner's and Kuratowski's theorems soon in a book I am reading. It was introduced as being a common graph and it confused me as to why I should "care" about the graph specie (to put it bluntly). Thanks for contextualizing it for me.

[safe carbon]

Hmm I realize that it is the powers of two that are 1,1,2,3,5,8,13 which is a Fibonacci sequence but not sure how to put that into the equation

[coral parcel]

Excellent.

I would just write the conjecture as:
$$a_n = 2^{F_n} \text{ where $F_n$ is the $n$th Fibonacci number}$$

[vital dew]

Troposphere

[coral parcel]

I'm pretty certain that's the level of formality the problem expects.

[safe carbon]

Okay thanks! I haven’t heard the professor mention that notation but I will put that down

[coral parcel]

The only obvious alternative would be something like substituting in Binet's formula for the Fibonacci numbers, but that would make everything horribly worse in the "prove that it works" step and can't possibly be what you're expected to do.

[cerulean slate]

can someone explain how this works?

[coral parcel]

The asterisks probably stand for plain multiplication.

[safe carbon]

That makes sense. I also need help on part c. How do I prove it that using induction?

[coral parcel]

I expect you can assume the recursion formula for the Fibonacci numbers.

Then use strong induction so you can assume both $a_{n-1}=2^{F_{n-1}}$ and $a_{n-2}=2^{F_{n-2}}$ in the induction step.

[vital dew]

Troposphere

[safe carbon]

ohhh okay I gotcha

Thank you so much for the help!!

[lyric quartz]

A closure is by definition unique, right? Is there some name for "closures" that are not unique but are subset-minimum/maximum?

[coral parcel]

It would be very unusual to use the word "closure" about something that is not fairly easily seen to be unique.
(At least up to some appropriate notion of equivalence, and under common assumptions in whatever the area is. E.g. "algebraic closures" of arbitrary fields are not unique if you reject the axiom of choice, but basically nobody does that anyway).

[stuck sigil]

Can someone explain me, why in this point U becames AND?

[brave rock]

What's written there is not right

Specifically, that should be an or, not an and.

Oh wait, I misread

I thought this was an intersection not a union

Are you aware of De Morgan's law?

If you know De Morgan, this should come immediately.

[lyric quartz]

Ok, thank you. I was reading about closures in the context of relations. And the closure also explained as the subset-smallest element of the family of supersets of R with some property P (paraphrased). And since the subset relation is a partial order and not total, I thought there does not have to be a smallest element but there can be multiple minimal elements. Or is there always a unique minimal element as well if it exists and therefore the smallest?

[coral parcel]

In many cases you'll be able to prove that the intersection of all supersets with property P has the property itself, and then it is obviously the unique smallest such set.

Where such a proof is not available, one needs some other argument to justify that the definition makes sense.

[lyric quartz]

@coral parcel thank you very much!

[lyric quartz]

Ah, this is also how they define the transitive closure

[coral parcel]

It should be your first suspicion anytime anyone says "the smallest set such that ..."

[lyric quartz]

Ah I missed a theorem. The subset greatest lower bound of F is the intersection of F.

And if g.l.b. is in F it is the smallest element

Hm, had (g.l.b) after my notes, but forgot what it meant.

[night mantle]

Hi, I want to ask a set theory question, I know the answer is N_0 but I'm having trouble proving it. I'm supposed to show w^w is equipotent to the natural numbers but how do I construct such an isomorphism? Or do I show by definition that w^w=sup{w^n, n natural} and w^n is countable so it is also countable? And I'm actually struggling to prove w^n is a countable ordinal number too, Idk if I'm missing something obvious.

set theory is so confusing

[lyric quartz]

Is $\omega^\omega$ the function space $\omega \rightarrow \omega$?

[tight hound]

ω^ω is not countable

[vital dew]

WanderingLethe

[tight hound]

Function space as in? Do you mean the set of functions from ω to ω?

[lyric quartz]

Yes

Just trying to understand Amelia's question

[tight hound]

Probably does mean that then, this is the usual notation.

[lyric quartz]

I should learn some more set theory

Guess what chapter I just reached, infinite sets 🙂

[weary tiger]

could someone help me

The sum of the first three terms of an arithmetic series is 138 and of the next three terms is 255. What are
the first six terms of the series?

[chrome fossil]

Arithmetic sequence: a, a+d, a+2d, …

Sum of first three is a + (a+d) + (a+2d)

Sum of next three is (a+3d) + (a+4d) + (a+5d)

[sudden minnow]

it is countable if it is ordinal exponentiation

since they particularly used ordinals and not cardinals for the exponentiation, this is likely

[bright knot]

Task: For integers x, y, z, prove that if x+y+z is odd, then at least one of the three integers is odd. Should I use contradiction?

[tight hound]

Could you explain this to me, please?

I just thought of it as |ℝ|=|2^ω|≤
|ω^ω|

And now I realise that these are cardinals

So we aren't doing 'ordinal exponentiation', I guess

[sudden minnow]

ordinal arithmetic is defined differently from cardinal arithmetic, which gets confusing especially when people like to use ordinals in places where they want to do cardinal arithmetic

[tight hound]

Yeah I certainly got confused lol

[junior field]

I'm not really sure how to start this one besides just plugging in 2 for Y

[mint portal]

Where should I learn proofs? I have a quiz on friday on them but they are so confusing to me.

Like, direct, contrapositive, and contradiction.

[last flicker]

If Q(x, y) then we have x+y=x^2-y^2. Specifically, if Q(x,2), then x+2=x^2-2^2. This is just a quadratic, so you can find the x for which it is true.

And if that x is in the domain, \exists x Q(x,2) is a true statement

[stuck sigil]

Can someone explain me why these two sum are equal?

I referred to first image

the second one is just to understand the context

[little prism]

well in the first sum for each g you count the x so that gx=x. and in the second sum for each x you count the g for which gx=x. so in total on both sides you count all the same pairs (g,x) with gx=x

[stuck sigil]

ah ok

thanks

[weary tiger]

is it ok for me to use the distributive property on x(yz)' ?

[agile magnet]

dumb question what is a clique in a hypergraph

I know what it is in a regular graph but how does it generalize in a hypergraph (say a k clique)

[spare holly]

A bounded region (say a circle) containing k vertices (roughly)

[little prism]

there are several different definitions for what a clique in a hypergraph is

one is that it is a set of vertices so that every subset is an hyperedge

another is that it is a set of vertices so that all subsets of a fixed size r are hyperedges

and there are probably more

[agile magnet]

My context is an r-uniform graph

So that last definition makes the most sense

[night mantle]

hi, I want to ask a set theory question, this should be trivial to ppl but I'm not sure if this is what is intended? I'm thinking of writing a+b = sup{sup{m+n:m<b}+n:n<a}. Looks a bit strange and I'm not sure it could be simplified

[broken sonnet]

Can I get some hints / guidance on this question? It's asking us to use PIE, but from what I know PIE would be:

$|A| + |B| - |A \cap B|$

[vital dew]

phamous

[broken sonnet]

yeah you mean for when you are trying to prove the LHS and RHS using some counting problem?

[grand totem]

You don't particularly need to use the full power of inclusion-exclusion here, it would be sufficient to use the fact that $\Pr(X\cup Y)=\Pr(X)+\Pr(Y)$ for $X,Y$ disjoint.

A possible start would be to notice that $A\cup (B\setminus A)=A\cup B=B\cup (A\setminus B)$

[vital dew]

Neverbloom

[broken sonnet]

ah i see

that is one probability "property"

[grand totem]

And since you need to prove an inequality, you'd also want to use the fact that probabilities are non-negative, here in particular you may want to use it as $0\leq\Pr(B\setminus A)$

[vital dew]

Neverbloom

[broken sonnet]

got it, thanks for the tips I'll go ahead see what I come up with

[broken sonnet]

@grand totem thank you so much for the dots, i was able to connect them and arrive at this solution

I would say try to formulate a counting problem that solves one side, then for the other side, try to think how it is saying the same thing but in a different way

then tweak your counting problem to account for that

[civic pasture]

How hard is discrete math compared to calc?

[coral parcel]

Some find it easier, some harder. Depends on temperament and/or teachers.

[civic pasture]

Does discrete math require any prior knowledge like calc does? If so, what topics should I know about before taking it?

[little prism]

well depends on the course

some might require some basic logic or combinatorics or stuff

[grim tapir]

why do they increment the counter for some k if the state = expected difference

really confused tbf with chosen plaintext attack in differential cryptanalysis

like what does the expected difference mean even

[broken sonnet]

I see that the next step is to show $\frac{1}{n! - 1}$ because we don't want to count the actual sequence, but can someone explain to me why that is?

[vital dew]

phamous

[broken sonnet]

since each outcome has a probability of 1/n!, wouldn't just be that the outcome for a reverse permutation is just that?

[leaden jay]

I need help with this problem:

[lapis mulch]

question about pigeonhole principle

in the sol'n for problem #3, was Briar pulling 3 socks of each color a mere assumption?

nvm i think i got it now

[crystal spruce]

could someone explain the first step of this? f is the fibonacci sequence

this "solution" from pearson is remarkably unhelpful lol

nevermind, it's the inductive hypothesis

which i left out of the screenshot

mb

[night mantle]

hiiii, I'm reading the Hrbacek set theory book, and got confused by this proof. Why do they go through this length to say that N^n is enumerable? They already proved that N^n is countable by previous lemma, so why not just use the fact there is bijective f from N to N^n, so (f(i): i natural ) is an enumeration?

btw, they want to show an explicit enumeration of N^n because they are using this theorem:

[vivid gust]

hi

can anyone help me with crytography and like teach it to me?

[coral parcel]

You probably won't find any takers for "teach it to you" in the sense of taking responsibility for what you learn in which order, or think up exercises that will help you learn and remember the relevant facts and techniques, and so forth.

But if you have concrete questions you're stuck on, chances are good that someone will be up to answering them.

[vivid gust]

i have a bunch of questions

does anyone cryptography

like the mod of stuff

[covert terrace]

I do a mild amount of cryptography

the extent of my knowledge in that area is mostly in signals analysis, though

[vivid gust]

@covert terrace could you teach me some? i can tell you what im learning

[covert terrace]

erm I dont think im really qualified to teach but i can try to answer questions (as troposphere said)

What are you learning?

[snow cedar]

can someone help for the proof of this

im thinking that its saying G has a k-length walk from i to j <=> c_jk^k > 0

talking about part a)

i need to do part a) to understand b)

[snow cedar]

anyone know

<@&286206848099549185> if anyone can shed some insight 🙏

[leaden jay]

I need help with this problem:

[grim tapir]

why does the S-box go from m to n in length of input to output

i thought it would be the same surely?

[little prism]

well different lengths is more general

just do that for now and maybe later set m=n

[royal holly]

does anyone know why it is false

when it is true?

[thorny turret]

Can some one explain graph theory for me

I’m lost in bipartite and loops I’m so lost

[lyric quartz]

third column "r" looks at the case r is false, so then the conclusion would be that r is false...? What is the question?

[hasty herald]

Yeah I thought this too, but I’m slacking in my discrete maths class 🤣

[leaden jay]

Can anyone help me with this?

[north cargo]

can someone help me

[last flicker]

What's the definition of countable?

[north cargo]

a set that is 1-1 to the set of natural numbers

[smoky herald]

I have a set A and a relation * in A. I have to demonstrate that * is a equivalence relation in A if and only if we have this 2 conditions:
a)* is reflexive
b)* is transitive

but i suspect that in the second conditional is not avaliable have the conditional, cause we dont have the simetry to proof that is not a order relation if we have antisimetry instead regular simetry

[stray reef]

so you have to prove that a relation which is reflexive and transitive is also symmetric...?

[grim tapir]

Can someone explain the entire process of differential crypyanalysis for an SPN using chosen plaintext attack, makes no sense.

[snow cedar]

can i get this by computing total # of edges - # edges of same colour?

[snow cedar]

it says it should not equal 2pq

[royal holly]

#help-11 message

could someone help me understand how they factor out 2+2*3^2

[smoky herald]

yes

[royal gull]

what does this notation mean

First 4 pos integers?

4 positive integers?

[sudden minnow]

if I saw that in the wild, I'd assume it is the positive integers cartesian product with itself 4 times

Z_+ x Z_+ ...

if it means something else it is notation unknown to me

[floral forge]

hey guys for g i got the first answer (first line) but my textbook has the second answer (second line). i was wondering if the ordering matters here

oh i sent the same thing twice

whoops wait

11 g

And this is my andwer (first line) vs the textbooks (second line)

the ordering is very different but idk if it matters?

also for h i got a different answer from the book i cant tell if mines wrong or not

[stray reef]

then you are asked to prove a false statement.

[royal holly]

this is what i did based on this example

did i do it right?

[leaden jay]

Can anyone construct a 2-regular and 3-regular graph with no perfect matching?

[coral parcel]

Yes. Can you?

[leaden jay]

NVM...I was able to figure out how to do it LOL

[cerulean slate]

How does he get to the second step?

[silk adder]

C’ n C = {}
B’ U {} = B’

[lyric quartz]

What does C' mean?

Hm complement, Universe \ C

[spring hound]

Yeah, I don't know what the precedence is, but I'd assume that ⋃ is like addition and ⋂ is like multiplication, and so it's A ⋂ ((C' ⋂ B') ⋃ (C' ⋂ C)).

If it isn't, I think allthesepollitos got it.

[lyric quartz]

Precedence is the same as + and *

[spring hound]

If it is, then you just eliminate C' ⋂ C.

And it's just a commutative jump and an associative placing of parentheses.

[cerulean slate]

what about this?

A extra c' seems to have appeared

[haughty garden]

They just used the distributive law

[ A \cap (B \cup C) \equiv (A \cap B) \cup (A \cap C) ]

[haughty garden]

So here, we have that [ C’ \cap (B’ \cup C) = (C’ \cap B’) \cup (C’ \cap C) ]

[cerulean slate]

im a bit confused on when you can distributive vs when you can just use the assocative property

[remote cosmos]

can you think of any situations where that's invalid?

notice that the for all y is a pretty strong statement

one hint: are all these functions continuous?

[iron marsh]

I don't have any questions yet, but if it comes down to it, would this be a good channel to ask about spectral graph theory?

[silk adder]

U is the Union of sets
A U B = { x | x € A or X € B}

n is the intersection of sets
A n B = { x | x € A and x € B}

[stray reef]

i don't think chai was asking to explain what union and intersection were...

[rapid mural]

you are correct lol

there is no smallest real number

[lyric quartz]

Depends on the ordering, right? And if you accept axiom of choice.

[magic knoll]

yea, but unless stated we'll take the default order

[spring hound]

Yes, I know that. I was talking about precedence of the operators.

[indigo rapids]

4^17 mod 100 ≡ 4^7 mod 100 - can someone explain to me how the two are equivalent?

[tight hound]

4^17 - 4^7 is divisible by both 4 and 25

[indigo rapids]

why are you taking them away?

[tight hound]

Do you understand what the equivalence you referred to means?

[indigo rapids]

the one on the left will yield the same result as the one on the right?

awwww

i seeeeee

cuz the mod repeats after every 10 increase in the exponent

as in the result obtained from 4^x mod 100 \equiv 4^{x+10} mod 100

idk how to get latex on discord

but

i see nowww

haha

thanks

[coral parcel]

We have a bot in the server that will usually render your posts with LaTeX if it sees dollar signs or \(...\) in what you write, but it seems to be down at the moment.

[broken sonnet]

I'm having a hard time understanding how I can define a function for f

I know that each distinct element in the domain A needs to map to a distinct element in codomain B

[stray reef]

the elements of {0,1} × {0,1} are ordered pairs and should be notated with round brackets and not curly ones. that's a notation issue for you to fix

however, you've listed these things out explicitly.

so you can just say

define f by f({0}) = (0,0), f({1}) = (0,1), f({0,1}) = (1,0) and f(∅) = (1,1)

(in accordance with your listing order for both of these)

[broken sonnet]

ah thats right they are tuples

thank you for pointing that out

ooo i see

so i can just make up the mappings

is there a way to frame in a more general way

something like f(x) = (x, y)

[brave rock]

There is, yes

If S is some statement, I will write [S] to be 1 if S is true and 0 if S is false

Then one possible map is f(x) = ([0 in x], [1 in x])

[broken sonnet]

ahh i see

thank you for pointing that out

it finally clicked

[stray reef]

iverson bracket moment

[brave rock]

The tex bot is down so I went for the easiest thing to notate lol

[shut mesa]

Does anyone have a list of useful formal definitions that are good to know for Discrete Math?

Feel free to DM if anyone would like to provide any insight, thank you!

[coral parcel]

I think exactly what "discrete math" is varies too much between institutions for such a list to be generally useful.

[shut mesa]

I see, I think I might come up with one from exercises out of the book and just see what the professor thinks or if he's willing to give pointers on what's relevant and what's not.

[nocturne geode]

how many different three letter initials can people have where one initial is an A

[weary tiger]

Anyone could help on this ?
Design a DFA for language that has odd number of ones or odd number of zeros, but not both.

[weary tiger]

Is there anything I need to know before taking discrete math?

[west wren]

Can anyone check my proof?

[cerulean slate]

,, A \cap (A^c \cap (B^c \cup A^c))

[vital dew]

Scratch

[cerulean slate]

In this case I know I can distributive to

,, A \cap ( (A^c \cap B^c) \cup (A^c \cap A^c) ))

[vital dew]

Scratch

[cerulean slate]

but does the associative property also work, like

,, (A \cap A^c) \cap (B^c \cup A^c)

[vital dew]

Scratch

[west wren]

Can anyone please help?

[coral parcel]

Proof checking is tedious and boring work, and often nobody in the channel will feel they have the energy.

If there's a particular step in your proof you feel uncertain about, asking a focused question about that can have better chances of engaging someone.

[next sail]

i was reading a proof about conjunction of universal propositions. is there a reason why we switched from using P(x) to P(a) in step 2? i've seen similar proof from a book and they also switch the symbol for the predicate variable.

[west wren]

That is fair enough; I will do just that. I did highlight the section of the proof that I was the most unsure of, though.

[west wren]

Can anyone check my proof? I have highlighted the section of the proof that I am the most unsure of. Thank you.

[weary tiger]

dang i had the same question

although mines is probably far easier

how could i have this proof better?

[grizzled ore]

im not sure that what you have written is a proof of anything...

[vital dew]

Tubular Cat

Tubular Cat

[spice warren]

would the codomain become the domain when taking the inverse of this function?

or is it only the range

[brave rock]

This function does not have an inverse. It only has partial inverses.

You'll have to clarify what you mean

[spice warren]

when you take the inverse of a function do you swap the codomain and domain

or the range and domain

[brave rock]

If the function has an inverse, then you do swap the domain and codomain, yes

This can be seen as a reason why the function you have above does not have an inverse

[spice warren]

ok i see, so the function above is one to one, but taking the inverse is not one to one because it is not a valid function?

[brave rock]

I would say that's a valid reason, yeah

[spice warren]

can anyone explain why there are n^pq ways?

[brave rock]

Let's abstract to the case where we're counting the number of functions from a set X to a set Y

To define a function, you choose an element of Y to assign to each element of X

This means you have |Y| choices for every element of X

Hence you have |Y|^|X| possibilities in total.

[spice warren]

if X = {1,2,3} and Y = {1,2,3}
then |Y|^|X| = 27, how are there 27 possibilities?
1 -> 1, 1 -> 2, 1 -> 3, 2 -> 1, 2 -> 2, 2 -> 3, 3 -> 1, 3 -> 2, 3 -> 3

Or am I completely misinterpreting the meaning of set "to" another set

[fossil mural]

1 -> 1, 1 -> 2, 1 -> 3, 2 -> 1, 2 -> 2, 2 -> 3, 3 -> 1, 3 -> 2, 3 -> 3
that's not "functions", it's just pairs

a function doesn't have one particular inputs, it has one output for each possible input

so "1 -> 1, 2 -> 1, 3 -> 2" is one function

in general they look like "1 -> ?, 2 -> ?, 3 -> ?"

if "1 -> 1" was a function then,
let's say f = 1 -> 1
what's f(2)?

[spice warren]

ah i see. im confused as to what "to" means