discrete-math

[vital dew]

bee [it/its]

[oak drift]

rn I have this

and I simplified the negatives

[fossil mural]

so, $((p \land \neg q) \lor (q \land \neg r)) \lor (\neg p \lor r)$?

[vital dew]

bee [it/its]

[oak drift]

yep

and I was thinking of removing the parenthesis and moving the -p from the end to the beggining

and maybe using the absorption law but I'm still searching how

cuz idk if I can use the law with a -p with a p

[fossil mural]

yeah no i don't think the absorption law is useful here

i think what you want is the distributive law

$\neg p \lor (p \land \neg q) \equiv ((\neg p \lor p) \land (\neg p \lor \neg q))$

[vital dew]

bee [it/its]

[oak drift]

true

[fossil mural]

and then $\neg p \lor p$ is true so it reduces to just $\neg p \lor \neg q$ which is a lot more convenient

[vital dew]

bee [it/its]

[oak drift]

and I do the same for the remaining r?

negative r*

[fossil mural]

well i'm not entirely sure which $\neg r$ you're referring to but yeah i think you want to use the distributive law on $(q \land \neg r) \lor r$

[vital dew]

bee [it/its]

[oak drift]

ohhhh I think im done wait a sec

I think I can cook from here give me a minute

nvm

it give me p->r V T

[fossil mural]

well we're done then

domination law: anything or true is true

[oak drift]

fr??

I didnt read the table till the end lol

[fossil mural]

well this is near the start of the table so i'm not sure that in particular is your issue

[oak drift]

masterclass mathematical thinking

[fossil mural]

you don't really need the last step where you rewrite ¬p v r as p -> r

[oak drift]

yeah I guess

it's just that I forgot about the domination law

so I tried to make the equation resemble what I needed in the beggining for some reason

[viral crown]

this just gave me inspiration

i forgot it was called that

[burnt nebula]

is this a trick question if a and b are an integer then the answer is going to be an integer?

i guess im not sure how to "prove" it

[brave rock]

No, this is not a trick question

The question is not to show that the thing on the left is a subset of the integers.

You have observed that it is a subset, and indeed this is trivial.

But you have forgot the other direction. The question is saying if every integer can be written in the form 12a + 25b for some integers a and b, and that is nontrivial.

When you are asked to prove that two sets are equal, this is what you should be thinking: is every element of the former an element of the latter, and is every element of the latter an element of the former. If both of these things are true, you know the sets are equal.

[fossil mural]

for instance if it was ${4a + 6b : a,b \in \mathbb{Z}} = \mathbb{Z}$, then this is false, everything in the set on the left is even so it doesn't contain integers like $1$ or $3$ (in fact it turns out to be exactly the set of even integers)

[vital dew]

bee [it/its]

[burnt nebula]

[brave rock]

OK do you have any further questions.

[burnt nebula]

okay so those are 2 different subsets inside the { }

[brave rock]

No

The notation {4a + 6b : a, b in Z} refers to the set of all numbers of the form 4a + 6b, where a and b are any integers.

There is only one set being described there.

[burnt nebula]

12a + 25b in this case if tha tmatters

[brave rock]

Yes, in your question it does matter.

[burnt nebula]

so since a and b $\in \mathbb{Z}$ , and the sum and product of $\mathbb{Z}| are also $\mathbb{Z}$ we know that 12a + 25b will always be an $\mathbb{Z}$, meaning every $\in$ of the set {12a + 25b: a, b, $\in \mathbb{Z}$ is in $\mathbb{Z}$

[vital dew]

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

[burnt nebula]

latex fail oops

tsill learning it lol

[brave rock]

every element of the left hand side is in the right hand side.

[burnt nebula]

right

[brave rock]

This is what I said here.

[burnt nebula]

so now i have to reverse it to see if the Z is a subset of that whole bracket?

[brave rock]

Yes

[burnt nebula]

what is that a proof by "____"?

[brave rock]

I don't know if it has any special name.

I don't really care. It's just a proof.

[burnt nebula]

ah okay so are we now plugging in 12(Za) + 25 (Zb)?

[brave rock]

I don't know what that means.

[burnt nebula]

if we express Z as an integer

[brave rock]

But Z is the set of all integers, not an integer

[burnt nebula]

therefore every integer Z can be written as 12a + 25b for some integers a and b

[brave rock]

You should try to investigate the set on left on your own to see how you might find any integer there

You're not going to use some standard trick here, you will have to think.

You may have seen something previously about linear combinations of integers, called Bézout's lemma. If you haven't, just explore. If you have, then you should use this fact.

[burnt nebula]

Haven't seen that in the textbook

do i need to prove that two sets A and B are the same

[novel ore]

is the quotient set for b ${[k]_{\sim} \mid k \in [0, 1)}$?

[vital dew]

okeyokay

[brave rock]

[0, 1) is a set of representatives yes

N.b. what you've written isn't actually saying that [0, 1) is a set of representatives, only something a bit weaker, but it is still correct.

You could also have chosen e.g. (0, 1] or [5,6)\{5.5}u{12.5}

[burnt nebula]

so say i do n = n * 1 = n (12(-2) + 25(1)) = 12 (-2n) + 25(n), and both n and -2n are integers, so it follows the n is an element of the subset {12a +25b : a , b E Z}, therefore Z is a subset of {12a +25b : a , b E Z}.

[brave rock]

You have the right idea even if your terminology is a bit off

Oh no wait I read wrong

No you're bang on the money

Well done

[burnt nebula]

ok let me write my whole proof out on latex and ill post a pic and if you could check

[novel ore]

and then the quotient set for c would consist of those equivalence classes which relate points which are equidistant from the origin

and then a possible set of representatives could just be (x, x)

[brave rock]

No

Oh for (c)

Yes

[novel ore]

ok thanks

[brave rock]

Hold on

What is your set of representatives

[novel ore]

oh wait

[brave rock]

(x, x) is a point, so surely you don't mean that

And it's the empty interval

so you don't mean that

So what do you mean

[novel ore]

oh no i meant like the coordinate (x, x)

[brave rock]

So what is a set of representatives

[novel ore]

${(x, x) \mid x \in \mathbb{R}}$

[vital dew]

okeyokay

[brave rock]

No, this is not correct.

There are things that are related in this set

[novel ore]

oh wait

${(x, x) \mid x \in \mathbb{R} \text{ and } x \geq 0}$

[brave rock]

Yeah that's right

You could also just do (x, 0) for x >= 0 in R

[vital dew]

okeyokay

[novel ore]

oh yeah that works

i just pictured like expanding circles

[brave rock]

Typo

fixed

[novel ore]

ye makes sense

thank you

[brave rock]

No problemo

[burnt nebula]

does a have to be a =-2n and b = n for this to work

[novel ore]

and then D would just be the partition itself lol, with {7} and say {0} being a set of representatives

[fossil mural]

well the set of representatives would be something like {7, 0}

but yes

[novel ore]

why would it be {7, 0} instead of {{7}, {0}}?

(we haven't got to the idea of numbers being sets yet if that clarifies things)

[fossil mural]

well... oh wait hang on yeah you're right

i misread the definition

[novel ore]

all good

[burnt nebula]

sheesh that took 1 hr

ty Boytjie

[novel ore]

to show that a quotient set is something, does it suffice to take elements of set the we're quotienting on and show that it belongs to one of the elements of that quotient set, and to also show that the set of equivalence classes are disjoint?

[burnt nebula]

Not sure if this is true, i know everything can be factored by 1, but 1 isn't prime

like there is the integer 4, but that can't be divided by a prime

[novel ore]

is 3d just that P(E) is a set of representatives for the quotient set lol

[oblique pelican]

4 can be divided by 2 and 2 is prime

[burnt nebula]

oh ur right lol

[oblique pelican]

Look up the fundamental theorem of arithmetic

[burnt nebula]

so if it's 5 it can be divided by 5 which is prime

[oblique pelican]

Yeah

[burnt nebula]

my brain is fried

thank u

[oblique pelican]

Ok so yeah let x=1

Can you find a prime that divides 1

[burnt nebula]

well 1 isn't prime

so that wouldn't work

trick Q?

[oblique pelican]

Yeah there's no prime that divides 1

[oblique pelican]

What do you think

[burnt nebula]

well if x can be anything besides 0

and y can be any real number, if you multiply by it's recpriocal youll get 1

so like 5 (1/5) = 1

-5 (-1/5) = 1

true!

[oblique pelican]

Ye

So given x, let y=1/x

[burnt nebula]

is there a better way to write this formula so i can start pluggin in numbers?

in latex form

[terse wyvern]

technically it isnt $\approx$ its $\sim$ meaning that the quantities are asymptotic

[vital dew]

treesarentreal.com

[burnt nebula]

thank you all for your help

actually 1 more

so i have to prove both ways

If 0 | x then there exists an integer c, such that x = 0 * c. For any c, 0 * c = 0, therefore x = 0.

If x = 0, then 0 | x. Some integer c such that x = 0 * c. C can be any integer because 0 * c = 0

[oblique pelican]

[oak drift]

sorry but I forgot what I did

what did I do between step 7-8

can someone tell me if there is a mistake in my reasoning ?

[oak drift]

Hello, in this situation, do I have to write :
For all X, For all Y,

Y(x,y)
R(x,y)

like am I allowed to write this or do I need to write all the possilities (Y(x) and R(y) or Y(x,y) or R(x,y)

[grave sail]

how many subgraphs of $K_{n,m} \text{ are isomorphic to } K_{3,4} = \binom{n}{3} \binom{m}{4} + \binom{n}{4} \binom{m}{3}?$

[vital dew]

Adamm

[grave sail]

why is it needed to change the side of the partition in which we are choosing from ? (adding nC4 and mC3) ... why does this matter

[fossil mural]

distributive law on the right, then the truth law twice and the identity law twice

[frosty blade]

why is it that ∃z > 0 (z^2 = 2) cant be written as ∃z(z > 0 → z^2 = 2)

[chrome nexus]

hi does anyone know of any tool to grap sets online?

[novel ore]

Since $S \subseteq T$, we need only show that $T \subseteq S$. Suppose there was an element $C \in T$ not belonging to $S$. Since $S$ is a partition, we have $C \cap B \neq \varnothing$ for some $B \in S$. However, $C \in T$ and $B \in T$ (since $S \subseteq T$); thus $T$ is not a partition, since its sets are not disjoint. Since this is a contradiction, we conclude that every element of $T$ is an element of $S$, whence $T = S$.

Can someone check this please?

[vital dew]

okeyokay

[oblique pelican]

looks good to me

[frosty blade]

I am confused how Binding works in discrete math. For ∃xP(x) ∨ R(x), are the Xs in P(x) diffrent from X in R(x)?

[oak drift]

can someone help me rq

it's not a hard question just want to know how quantifiers work in the context of my exercise

for a)

do I write " for all X and all Y, R(x,y) V Y(x,y)

or do I write it another way

[oblique pelican]

Y(x) and R(x) are only in one variable

[oak drift]

but it says x and y make up the set of all birds

[oblique pelican]

they introduce y only to demonstrate what F(x,y) means

[oak drift]

or thats only relevant for B

okok thx man

[oblique pelican]

x and y are also just placeholder names, you can use any variable name

but it would probably make sense to stick with x and y for this problem

[oak drift]

also ( not the same exercise ) if I need to write that the sum of a positive int and a negative int is not necessarily positive

I can just say that for all X int and all Y int, where y is negative, I can just say "x+y is element of Z"

[oak drift]

so R(x,y) V Y(x,y)

[oblique pelican]

No, again R(x) and Y(x) are only in one variable. For any bird x, either x is red or x is yellow

[oak drift]

ok mb I read it wrong

I thought you meant it as "stick to using both x and y "

not stick to the variables already given

[oblique pelican]

Nah, just for when you need them

[oak drift]

okok thx

but am I right for the other exercise ?

[oblique pelican]

If you need a second variable, use y so it's clear the the problem

[oblique pelican]

Hmm, in a way yes. But this doesn't emphasize that x+y is not necessarily positive. For all we know, x+y could be always a positive integer and it would still be an element of Z.

Could you post a screenshot of the problem

[oak drift]

C

[oblique pelican]

There's a couple ways of going about this

One way is to say there is a positive x and negative y such that their sum is negative. Another way is to say that for all x and y, x being positive and y being negative does not imply that their sum is positive.

I'm trying to think if these are logically equivalent or if they're just different interpretations

[oak drift]

oooh I like the last one

I could just add negative before the P(x,y)

[oblique pelican]

The second one could be wrong

Because for some x's and y's it is true

[oak drift]

oh yeah thats true

[oblique pelican]

But lemme think

[oak drift]

what if I just do the negation of P(x)

so like there exists an X and exists Y for which P is not true if P = sum is positive

[oblique pelican]

Yeah you can say it is not true that for all x and all y that if x is positive and y is negative, then x+y is positive

That should be right

That should be logically equivalent to my first statement

[oak drift]

This but what I mean is

if I say for all X and for all Y P is true (P = sum is positive)

then the negation is

there exists and X and there exists a Y for which P is not true

[oblique pelican]

Yeah exactly

[oak drift]

would that work

[oblique pelican]

But

[oak drift]

well you said All X All Y

[oblique pelican]

You need to specify x>0 and y<0

[oak drift]

I dont mean just adding negative in front of P

[oblique pelican]

I basically did what you said here

[oak drift]

I mean negation of the logical statement

did I learn it wrongf

[oblique pelican]

Sorry, maybe I am confusing you

[oak drift]

usually for the negation you also flip the all X into an Exists X

same for Y

and you put a negative in front of P

[oblique pelican]

Ye exactly

That's right

I'm just saying you need to specify for positive x and negative y since that's what's in the problem

[oak drift]

yeah this I know

[oak drift]

but you said its not true that for all X and all Y

omg im dumb

mb you're right in my head you had the negation only behind the P

[oblique pelican]

Yeah so like $\neg(\forall x\forall yP(x,y))$

[vital dew]

Dilly

[oblique pelican]

Yeah originally I had it that way, but then I realized it should be behind the whole statement

[oak drift]

exactly

yep that should work

thx I think Im good for the rest of the homework

[oblique pelican]

Np, glad we made it to the same page

[frosty blade]

Does someone know why this is illegal - ∃x(P(y) ∧ Q(y)) - if y and x refer to the same domain?

[oblique pelican]

this probably means that y is some previously chosen value

[frosty blade]

but if y is just a variable are you allowed to do this

[oblique pelican]

you can

but its lacking context I guess

and it also wouldnt be very helpful in that statement since x has no role in the truth value of P(y) ∧ Q(y)

[frosty blade]

But doesnt the y just declare the domain for the qualifier.

[oblique pelican]

Well y isn't specified anywhere, its just some variable unbound to the statement

x and y could be in different domains

its like saying "There exists an integer x such that y is an ocean"

Let y = the pacific ocean

the statement is true, but its not very helpful since no integer will tell you whether or not y is an ocean

[frosty blade]

So if you just had a logicial expression with two x's, where one is bound and one is free. how can the free one be replaced by a diffrent variable like y and mean the same thing

[oblique pelican]

Hm well it would a little ambiguous to have a free variable x and an bound variable x since they would be referring to two different things but with the same name.

[frosty blade]

I have been just trying to rack my head around this for 3 hrs

[oblique pelican]

Can you give an example

Ah I see

So you have two separate statements using quantifiers

[frosty blade]

yea

[oblique pelican]

The first one just says "there exists a value where P and Q are true given that value" and the second said "R is true for every value"

[frosty blade]

yes

[oblique pelican]

The quantified variables are just a way to assign values to the propositions

Like just a visual/mathematical aid to show you where they are being plugged in

But in these two statements, the variable name itself doesn't matter, and the variables are completely separate between the statements

[frosty blade]

so this would hold true even if the quantifers werent their?

[oblique pelican]

If the quantifiers weren't there, x would be unbound to a statement and you would have to define what x is. In that case, x would refer to the same x in both things

[frosty blade]

But if I like assigned a number to x it would not just assign it to all three statements because their not connected

[oblique pelican]

With the quantifiers there, you cant assign a value to x because it would be like saying "there exists a 5 such that..." or "for all 5's ..." The quantifiers just tell you about the existence of a value that makes a proposition true or a universal property. They don't tell you anything about specific values.

It is kind of hard to grasp at the beginning

So in a way, quantifiers kind of make statements about sets instead of single values

[frosty blade]

Ok so heres my understanding. Quantifiers are applied to variables, which have a domain, and apply to a scope in which the same variable is supossdly used allowed for a propostion to be formed around a set of values. When the same letter of the variable is used as a variable outside scope in another statement it is just the recyling of the same letter in another seperate function which can refer to the same or diffrent domain.

[oblique pelican]

Yeah exactly. And it is better practice imo to use different variable names in separate statements so there isn't that confusion about where a variables scope is

[frosty blade]

Ok thank you very much

[oak drift]

does anyone know how to do d

[oblique pelican]

Which one you looking at

[oak drift]

the other ones are easy

[oblique pelican]

Do you have an idea of what it would be

It is kinda long

Try to symbolize each part of the statement separately first

You can reword some of it like
"If a bird is yellow, then the same red bird is faster than it."
And
"If a bird is red and not the same as the red bird in question, then the new red bird is faster"

[oak drift]

yeah I get this

but its especiially the "slower than other red" that idk

[oblique pelican]

yeah so "slower than all other red birds" is the same thing as saying "all other red birds are faster"

[vital dew]

a

[cerulean plover]

what's the rule for the cardinality of the power set of a set that contains the null set?

like what is the cardinality of the power set of {null, a, b, c, d}

2^5 = 32?

[oblique pelican]

Yeah, the null set as an element is treated as a regular element

[cerulean plover]

but the cardinality of the power set of the set only containing the null set is 1, not 2^1

is that the only exception?

[oblique pelican]

Wdym

[cerulean plover]

like, the cardinality of the power set of {null}

is 1

[oblique pelican]

No it's still 2

[cerulean plover]

huh?

what're the entries in the power set

[oblique pelican]

{{},{{}}}

Is the power set

[cerulean plover]

AH i'm dumb, i getchu i was thinking uh

cardinality of power set of the null set

[oblique pelican]

It is a strange example tho

[cerulean plover]

which is 1

because 2^0

[oblique pelican]

Yeah

[cerulean plover]

but i was conflating the null set with the set of the null set

all good now, ty

[lilac valve]

Yes. In ∃xP(x) ∨ R(x), the x in P(x) is bounded by the existential quantifier (∃). I.e. if I were to instantiate the existential quantifier, then that x inside P(x) would be instantiated as well.

However, the x in R(x) is not bounded by the existential quantifier. It is fully independant from it.

If one wants to make it so that the x in both P(x) and R(x) are bounded by the existential quantifier, then they should write :

∃x(P(x) ∨ R(x))

[lilac valve]

The parentheses are not needed

[lilac valve]

Because we want to explicitely assert that x is bounded by the existential quantifier

[oblique pelican]

ik, I just wanted to emphasize that the negation is for the entire thing

[lilac valve]

There's no such thing

[cerulean plover]

for this, i'm confused. wouldn't the intersection between all of these be like... a set that starts at infinity and counts onward?

i'd understand if it were bounded at n, then it'd be easy, the set's just {n + 1, n + 2, ... }. but idk if you can do that with infinity

[oblique pelican]

Think of any integer. Is that integer in the intersection of all of these sets?

[oblique pelican]

yeah basically this

no integer is contained in the set, so it is empty

[cerulean plover]

there's no way of saying {infinity + 1, infinity + 2, infinity + 3, ...}?

[oblique pelican]

well because this is an intersection of integers, of course no other numbers would be in there

[oblique pelican]

nah

[cerulean plover]

since in this case, "n" is infinity

[oblique pelican]

If you supposed the set was nonempty, then there exists some integer N contained in the set. But N is not contained in A_{N+1} so theres a contradiction

[cerulean plover]

ah

that's a good way of putting it

ty

for whatever reason our prof decided that we weren't gonna learn proofs by contradiction??? 😭

[oblique pelican]

smh

[cerulean plover]

i mean we understand like... theoretically what one is, but we've never done one

only biconditional proofs, proofs by cases, direct proofs, and proofs by contraposition

[median portal]

I have a midterm coming up with these topics covered and I will be allowed to bring one handwritten paper (one sided) with anything that I'd like. We also have this reference sheet provided for us. Any tips on what I should include?

[lean nexus]

Prove that if n and m are perfect squares, then (n · m) + 2 is not a perfect square.

[final cliff]

Wlog let u,v and k be positive integers where n=u^2 and m=v^2. Suppose nm+2=k^2. Now solve for 2 and factor. This implies a contradiction with a little case work.

In particular notice that 2 is prime and not 1 or 4. What are the possible cases for your two factors? Why are both cases a contradiction?

[next ocean]

can we draw a graph whose degree of each vertex is different ?

[little prism]

great problem to experiment a bunch with. try drawing such a graph

[gusty walrus]

If it's any graph, if the # of vertex is higher than 2 the degree can be different

Ur asking an existence proof so an example is enough to prove that it's true

Draw a edge between 2vertices and on either vertex make a loop.

U will se that the degree on one of the 2 is 3 and the other is 1

*non directional graph btw

[next ocean]

with parallel edge right ?

[gusty walrus]

Wdym parrallele edge?

[gusty walrus]

.

[next ocean]

two vertex connected with two edge like multi graph.

[gusty walrus]

No

Idk how to draw here

Mastdrbuild typing....

[inland zenith]

I don't know the answer but if it helps the handshake lemma says that the degree sum must be an even number and the degree of any vertex in any graph is at most n-1, so that rules out a lot of possibilities already

the graph must contain an even number of odd degree vertices I think

for this to work

[gusty walrus]

ooh but that for simple graph only I think

[inland zenith]

yes

[gusty walrus]

Hesaidgraph

Graph

As in generally

[inland zenith]

the handshake lemma applies for all graphs though, doesn't it?

[gusty walrus]

Let me check

[inland zenith]

but yeah if you allow loops or multiple edges the degree can be more than n-1, I thought they were thinking of simple graphs

[gusty walrus]

The restriction is undirected graph

So it would work for looped graphs

And multigraphs

@next ocean

Do u means simple or any graph

[inland zenith]

ok, I was just thinking out loud, it sounds like a fun problem

[fossil venture]

Specifically for 18b). idk how to show that such a rule works. My initial idea is just to say that since a euler cycle exists then as long as you don't abruptly terminate any rule works.

[untold kraken]

Are my Hasse Diagram correct?

[next ocean]

I'm trying to get it in simple graph... though

[inland zenith]

directed or only undirected?

[inland zenith]

also yeah, this is trivially possible of course, e.g. K_0 or K_1, both graphs have all vertices with different degree

[next ocean]

any ?

@inland zenith i got with 5 vertex

[inland zenith]

ok so what do you mean in the case of directed?

[inland zenith]

cool, share it?

[next ocean]

@inland zenith

[inland zenith]

doesn't the bottom vertex and the rightmost vertex have the same degree?

[next ocean]

oh yes...

uhhhhh

[inland zenith]

I think for undirected graph you can show this is impossible by handshake lemma somehow

[next ocean]

but how ?

[inland zenith]

for a directed graph do you mean that any pair of vertices has different in degree and different out degree?

both at the same time?

[next ocean]

not for directed graph, we have to work on undirected graph only

[inland zenith]

Ok, got it

[next ocean]

yup

[noble geyser]

I need some help with the second part specifically showing that $g$ is indeed an injection. I think the set of equivalence classes is really confusing me.

[vital dew]

mss

[noble geyser]

Okay I think what’s happening is I have $g(\pi(a))=b \forall a \in A$. But how do I know $\pi$ is an injection? Is it because of how they defined the relation on $A$?

[vital dew]

mss

[cerulean wind]

@noble geyser f(a) = g(bar(a)) = g(bar(a')) = f(a') means what about a and a'

[next ocean]

@inland zenith i got the proof

if n vertices have n different edge, but one can have max degree n-1, hence if there is a graph with all different degrees it means there has to be a vertex with 0 degree, contradiction

no such graph can form with one vertices with degree 0 and one with n-1

[noble geyser]

Okay I think I understand it. I said g(bar(a)) = f(a). Now for injection on g we need to show that g(bar(a)) = g(bar(a’)) which implies bar(a) = bar(a’). But they way we have defined g(bar(a)) it is actually f(a) so we can show f(a) = f(a’) which implies a=a’. Using the eq. relation on the set A, a=a’ which implies bar(a) = bar(a’). Boom.

[inland zenith]

@next ocean Nice, well done

[frosty blade]

Can someone tell me how "For every real number x and y" translates to ∀x∀y because it doesnt make sense to me. I was taught to look at it as every x being looped with every y value but how does that sentence say that?

[oblique pelican]

Think of it like a grid with the x values as the columns and y values as the rows. You can loop through the columns and then the rows, or the rows and then the columns. Either way you will go through every pair of values, so it doesn't matter the order you consider them.

[frosty blade]

But how does "For every real number x and y" mean that

[oblique pelican]

What if you reword it to "For any pair of real numbers x and y"

[frosty blade]

Yeah that make sense

[oblique pelican]

That's what it's saying

[frosty blade]

ok thank you

[oblique pelican]

But I can see now why it's a little strange of wording

[frosty blade]

is ∀x≠0∃y( xy = 1) a valid way to write ∀x((x ≠ 0) → ∃y(xy = 1))

[oblique pelican]

Yeah, this is a very common method for simplifying

[frosty blade]

ok thank you

[frosty blade]

Does someone know why Expressions in predicate logic add variables. Like for the Sentence "Everyone has exactly one friend" could you just do ∀xB(x) where B(x) is "x has exactly one friend" instead of ∀x∃!B(x,y) where B(x,y) is "x is friends with y"

[oblique crypt]

Hey guys, I need to take discrete math in college but I'm scared for it. Do you guys know any resources online I can use to self study?

[viral crown]

depends on the specific class ur in, there's not really a set curriculum. see if you can find old course notes from the same prof or a syllabus or just e-mail them or something

if you want a good legal introduction you can self study w anyways then https://discrete.openmathbooks.org/dmoi3.html will do

[next ocean]

Thnx to u man, u initialize the intuition

[rugged dock]

$\forall xB(x)$ doesn't really specify who this friend is and if they are different than $x$

[vital dew]

javier

[rugged dock]

we don't want our statement to come off as vague, so we add another variable

to my understanding

[frosty blade]

ok ty

[weary tiger]

boutta go to sleep but if anyone wants to solve this (preferably using induction or binomial theorem) much would be appreciated. spent wayyyyy too much time on this >_<

[vivid osprey]

Consider the implication $$A\subseteq B\implies A\cap C\subseteq B\cap C,$$where $A,B,C$ are arbitrary sets. Can one write this as an equivalence too or is it only an implication?

[vital dew]

psie

[odd heart]

You need to be more specific with quantifiers to get an equivalence: $A\subset B \iff \forall_C (A\cap C) \subset (B\cap C)$

[vital dew]

Outsider

[odd heart]

(I'm using \subset to mean weak inclusion, as is standard in real analysis, because I didn't notice this is #discrete-math )

[vivid osprey]

ah ok, subtle detail but crucial probably 👍

[cerulean plover]

for something like this, do i need to prove that x and y are not integers if i'm using contrapositive?

since the forward implication has "x and y are integers" in the antidecent

or do i just consider that as my domain and leave it out of the implication?

[brave rock]

That “if” is quantification, not implication. So no.

[cerulean plover]

So it's saying "for all x that are integers and y that are integers"? would i then have to invert that to make it "there exists an x and y that are integers where..."

[cerulean plover]

For this, I can really easily do this via a proof by exhaustion, but is there any easier/less tedious method?

[little prism]

what are you doing to call it tedious

[cerulean plover]

4 cases, x is an element of a and b, x is an element of a but not b, x is an element of b but not a, x is an element of neither

[little prism]

2 cases, x in AnB or not. if not then its not in one of them, wlog not in A.

[neon harbor]

Iverson bracket notation is pretty nice for this problem

$[x \in A \cap B] := \begin{dcases*} 1 & if $x \in A \cap B$ \ 0 & otherwise\end{dcases*}$

[vital dew]

sheddow

[cerulean plover]

we have not learned about wlog yet, good to know

[neon harbor]

Iverson brackets have the property that [P and Q] = [P][Q]

[little prism]

ok. but at the very least you dont need to consider the case that its not in either of them

[cerulean plover]

how come?

[little prism]

if its not in A for example then f_A(x)=0 already and in the product you dont care about what f_B(x) is

it doesnt matter at that point whether x is in B or not

[final cliff]

This is probably messier than most people will want to check. I'm pretty sure you can brute force out the cases to get a roughly tree shaped nfa. Based on skimming what you wrote I think you are aware of this as well. I don't see why you are forcing so many edges to QF and QFF however. You ought to be able to use as many reject states as you like. I think this will lead to a cleaner more obviously tree-like nfa that will make your thinking much clearer.

In fact, depending on the nuance of how your course formalized nfas, you might be able omit reject states entirely here.

Sometimes there is a convention that in an nfa, if there is no outgoing edge and you need to consume a symbol the particular branch of computation you are in just rejects+terminates. So, if you have a string like aab and you consume aa and there is no edge to consume b on then that branch of your computation ends and the aab string is rejected.

Though it may possibly be accepted on some other branch

[calm quarry]

yeah youre right, i think i got mixed up with thinking of it mroe as a dfa and obsessing over creating every possible edge

tons of unnecessary transitions and states

[final cliff]

The brute force/cases idea feels right to me. If you make it cleaner it'll probably be easier to check too.

[final cliff]

If you don't have this convention in ur course then just ignore this btw.

[neon harbor]

WLOG = without loss of generality, it just means that you're making some simplifying assumption without sacrificing the generality of the proof. Usually because there are two cases which are completely symmetrical; you could also assume that x is not in B, but it would be the exact same proof as when x is not in A

[calm quarry]

i think we do but in all the professors examples he writes teh edges regardless (likely to make it easier to understand on our parts)

ill try to clean it up thanks for the advice

would you mind glancing at a less convoluted one lol

[cerulean plover]

so how would i write this? do i have to prove that there's no loss in generality?

[neon harbor]

Usually we just claim WLOG and expect the reader to understand. Like if you were to prove something for two real numbers a and b, you can WLOG assume a <= b. For this particular problem just do what Denascite suggested: if x is not in AnB then we have that either x is not in A or x is not in B. We can assume WLOG that x is not in A because the other case is symmetric

[cerulean plover]

Do you need to specify WLOG? for example, i proved something worked for all real numbers, can i then WLOG say it works for all integers?

or is that something else?

[neon harbor]

No, that's not what WLOG means, that's just because the integers are a subset of the reals

Let's say you want to prove P(a, b) for all real numbers a, b. Then you can assume a <= b in your proof. But this doesn't mean that you have only proved P(a, b) for all a <= b. It holds for all reals because you know that either a <= b or b <= a, then you just call the smallest one a

If you first assume that x is not in A then secondly assume x is not in B, then you'll find that the proof of these two cases are identical, except A and B have swapped places. So you can just do it once

[burnt nebula]

is the conclusion if someone is wearing white gloves they look fascinating

and for this one is it 52 x 51 x 50 x 49 x 48 - 39 x 38 x 37 x 36 x 35

[willow halo]

An assignment wants me to
"Prove that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) using the distributive law for binary literals"
But this is the distributive law... so what is there to say?

[vivid osprey]

It's been a long day and I'm a bit groggy, but are these two expressions equal? $$\bigcup_{k=1}^\infty\bigcup_{j=1}^\infty E_{k,j},\quad \bigcup_{(k,j)\in \mathbb{N}\times\mathbb{N}}E_{k,j}.$$

[vital dew]

psie

[vivid osprey]

Basically, I'd like to know if the left expression is a countable union, but I can't figure out the index set.

Ok, I think these sets are equal and the index set is simply $\mathbb N\times\mathbb N$.

[vital dew]

psie

[oak drift]

I dont understand the fourth and fifth column of the table

what is LHS premise and LHS -> q inference

[oblique pelican]

I think its meant to be
$$LHS \equiv p\rightarrow q \wedge p$$

[vital dew]

Dilly

[oak drift]

ok but what is LHS

[oblique pelican]

left hand side

right hand side would be q

left hand side is p -> q and p

[oak drift]

ok I THINK I get it

[oblique pelican]

LHS and RHS are used for equations, theyre not specific to logic

[oak drift]

so LHS premise here is p->q if p is true? and if p is false?

wait no

[oblique pelican]

its just simply doing the and of the two premises

[oak drift]

oh ok I think I understand but here since the second premise is just p its the same as the first p

[oblique pelican]

in the truth table

[oak drift]

makes sense thank you

and then LHS -> q inference is ?

[oblique pelican]

so the "argument form" is really saying
$$((p\rightarrow q) \wedge p)\rightarrow q$$

[vital dew]

Dilly

[oak drift]

oh ok

so the last part is always implies that

"->"

[oblique pelican]

yeah

idk if $\rightarrow$ or $\implies$ is used here, but thats the idea

[vital dew]

Dilly

[oak drift]

makes sense

but it's related to what other part of the truth table?

so like it's LHS -> q like written?

in that case wouldn't the third one be false? since LHS premise is false and q is false

[oblique pelican]

it should be F -> T for the third one

either way, F -> T and F -> F are vacuously true

[oak drift]

yeah but here it's T -> F?

[oblique pelican]

nah its backwards on the table

its LHS -> q

[oak drift]

oh yeah mb

I was reading it wrong since its not in order in the table

[oblique pelican]

yeah its a little confusing going backwards

[oak drift]

well thank you 👍

[cerulean plover]

this is wrong, right? someone said this was an answer to a test question, but the question seems like it's cut off or something. if p and q are both true, then the biconditional is still true, but the "answer" is not true

unless i'm translating "p is not a necessary condition for not q" incorrectly, i'm translating that as (not p and not q)

[cerulean plover]

nevermind, i see it now. p is not a necessary condition for not q is true, but it is not equivalent.

[chrome nexus]

a) true
b) true
c) false
d) true
e) true
f) false
g) false

can someone lmk if these answers are right?

[neon harbor]

f) is true, and g) is true assuming ⊂ means non-strict subset

[chrome nexus]

sorry i forgot to add that ⊂ means proper subset and ⊆ means subset in this text book

[neon harbor]

okay, then f) is true and g) is false

[chrome nexus]

a) yes
b) yes
c) no
d) yes

would this be correct?

[neon harbor]

which set is Ø the power set of?

[chrome nexus]

i believe itself

[neon harbor]

Remember that the empty set is a subset of every set, so every power set must contain the empty set

[vital dew]

Spamakin🎷

[agile magnet]

I'm just plugging in the emptyset into the definition

[vital dew]

Spamakin🎷

[agile magnet]

Is that a true statement or not? Is there no such set X?

[chrome nexus]

not true

[agile magnet]

yea

so a) cannot be a correct answer

[chrome nexus]

tysm

[outer rune]

hey guys, I have this question that ive been working on for a few hours and im at a road block. made some decent progress but i just dont know how to find the prime implicants and determine which are essential using the quine mccluskey method

"Find all the prime implicant for the following Boolean functions, and determine which are essential using the Quine-McCluskey method: F(w, x, y, z) = Σ(0, 2, 4, 5, 6, 7, 8, 10, 13, 15)"

heres what i got so far:

so in the leftmost table i wrote the equivalent minterm values with their binary representations

in the 2nd table i arranged the binary numbers in groups. at the top is the group that contains binary numbers with zero 1's, the group under that has binary numbers with just one 1, etc. (each group is separated by a bold horizontal line)

in the 3rd table i formed the 2-minterm implicants by seeing which minterms only differ by 1 bit.

in the 4th table i formed the 4-minterm implicants by seeing which of the 2-minterm implicants only differed by 1 bit

then on the bottom table i attemped to make a prime implicant table but i wasnt sure if i did it properly

then here i tried filling in the prime implicant table

so the green circles are the minterms that are only covered by one prime implicant

but im not sure what other horizontal line to make or even how to finish this prime implicant table

i know this is A LOT of text but i would really appreciate some help if anyone knows how to do this

TLDR: trying to find prime implicants and essential prime implicants of F(w, x, y, z) = Σ(0, 2, 4, 5, 6, 7, 8, 10, 13, 15) but dont know how

[shut ivy]

Are my truth values correct to disproof this argument

s=0, q=1, r=1, p=1

[supple jetty]

Does anyone have any good video resources for Big O, Big Omega, and Big Theta notation?

Specifically something that focuses on working with the functions and inequalities themselves to prove things. Especially proving Big Omega

All the videos I'm finding are contient to just give a conceptual overview and ask basic questions but this course I am taking is wanting something a bit more involved than that

Reading the same handful of examples from my textbook isn't really soaking in

[mental plaza]

yes because from 1st premise we know P is true. 2nd premise since we know P is true and P - > r , so r must be true. 3rd premise P -> ( q v ~r). we know that r is true so ~r must be false and since ~r is false and (q v ~r) is true, q must be true. 4th premise (~q v ~s) since we already know that q is true, ~q must be false and thus ~s must be true, therefore s is false. so s = 0, q = 1, r = 1, p = 1. it is correct

[scarlet spire]

if x + y = ( x ↓ y ) ↓ ( x ↓ y )

Would that make x + y + z = ( x ↓ y ↓ z ) ↓ ( x ↓ y ↓ z ) ?

[vital dew]

nesymerp1, the C++ lover

[quaint flower]

note, B and C bar is seperate.

[scarlet spire]

@quaint flower You could use a kmap table

[quaint flower]

Oh yeah, I could map out the minterms on a k-map and derive the solution with the least amount of minterms.

[scarlet spire]

ye

I just learnt that last week lol

[quaint flower]

but assuming I wasn't allowed to do that, how does one do this without k maps?

[scarlet spire]

factor it out and use identities. Idk if u get a table of them like I do. give me a moment let me go find the table of identities u can use

[quaint flower]

Yeah idk how to factor such thing tbh.

ok

[quaint flower]

I don't think we are allowed to use tables on our uni exams

but uh

[scarlet spire]

you can start with 2 terms since these are all ors

so let say

[quaint flower]

I know the laws, just not where to apply them

[scarlet spire]

(compliment A and compliment B) + (A and Compliment B and Compliment C)

you can take out a compliment B

[inland zenith]

factor out A for example, then you have BC or compl(BC) which is true

[quaint flower]

$$ Y = \overline{B}( \overline{A} + A\overline{ C}) + ABC $$

[vital dew]

nesymerp1, the C++ lover

[scarlet spire]

Yes

[inland zenith]

could do that too

[quaint flower]

I guess I can use absorption law here

So it becomes AC(bar)

Or wait...

[scarlet spire]

I go microsoft pain and write it out. Writitng it out on discord too hard

[quaint flower]

I think it becomes:

A bar + C bar

$$ Y = \overline{B} \overline{A} + B\overline{ C} + ABC $$

[vital dew]

nesymerp1, the C++ lover

[quaint flower]

This is the final solution I bet

(And also, B and A is seperate, the bars are not joined)

[scarlet spire]

One sec i go check this

[quaint flower]

ok

[quaint flower]

Though, I am unsure how to factor A bar + B(Cbar)

[quaint flower]

$$ Y = \overline{B} \overline{A} +\overline{B} \overline{ C} + ABC $$

[vital dew]

nesymerp1, the C++ lover

[quaint flower]

nvm this is the correct solution

note, B and A are seperate, so are B and C.

$$

But my only problem is, how does one factor this?
\overline{A} + A\overline{ C}$$

[vital dew]

nesymerp1, the C++ lover
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[scarlet spire]

what canceled out the A infront of the A b bar and c bar?

[quaint flower]

I am unsure, is it the absorption law? It doesn't sound right though.

[scarlet spire]

unsure, im also kind of stuck here. very sorry that i offered help and am confused myself

[quaint flower]

$$ \overline{A} + A\overline{ C} $$

[vital dew]

nesymerp1, the C++ lover

[quaint flower]

Like how does one factor this, xD

[quaint flower]

and np, dude, i just don't know what to do with this other then using a k map

[scarlet spire]

ok

i figured it out

you are right

[quaint flower]

ye

[scarlet spire]

so basically

U can apply distribute law on it

[quaint flower]

Righto, and how can I do that?

do you factor it out?

[scarlet spire]

If you think of A bar as x, A as y, and c bar as z

there for making it

(a bar + a)(a bar + c bar)

a bar + a = 1

so leaving it as a bar c bar

[quaint flower]

Oh I see...

[quaint flower]

I do not remember that law, but I need to remember it.

xD

I see now, I need to memorize this law actually

[scarlet spire]

Me too bro me too. I hope its not on my next exam

[quaint flower]

Yeah that solves that issue

ty

[scarlet spire]

happy to help

[sand pelican]

I don't quite get it why I have this in my note, I mean I can't get to the "then" part from "if"

[wicked smelt]

can someone explain how to use the table to prove that X is universal

[high helm]

I'm a bit lost

is this something Ramsey's theorem?

[obtuse lance]

they need to at minimum buy a network switch; this kind of configuration is ridiculous in the real world

[viral crown]

agreed no self-respecting computer user would ever do this

anyways this is pigeonhole

[obtuse lance]

interesting, I accidentally proved it without using the assumption that they each have at least one connection

maybe I proved the wrong thing 🤣

that, or the added assumption makes the pigeonhole proof simpler

[velvet lynx]

lmfao

[obtuse lance]

Ah, I found my mistake but I'll post my fake proof for n computers and you can spot where the error is for funsies:

There are n(n-1)/2 possible connections between n computers. If we try to take the best case of each computer having a different number of connections we would have 0 connections for the first, 1 for the second, etc... so in total there are 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 connections being made. However this is impossible because the first computer has 0 connections and the last computer is connected to everyone.

[viral crown]

||we would have 0 connections for the first||
!

[obtuse lance]

that's valid cause I've removed the condition they have at least one connection

[viral crown]

ah right

||the last computer can't be connected to everyone?||

[obtuse lance]

that's part of the proof so that's ok

[viral crown]

does it count tho bc the last computer can't have ||n-1|| connections so the formula is invalid

[obtuse lance]

well we're trying to pigeonhole for that result

minimum number of ways to get distinct number of connections 0, 1, 2, etc

[viral crown]

hmmmmmm

[fossil mural]

||so in total there are 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 connections being made||
||if you just add up the degrees you get twice the total number of connections||

[obtuse lance]

winner

[viral crown]

ah shit i really should have seen that

[obtuse lance]

now despite that proof being wrong, I think the result is still true

guess if someone has a counterexample that'd be convenient before I waste time on that lol

[fossil mural]

yeah for a bit i was confused by like, "i mean this works but half of the steps are irrelevant" because when i read it i ended up filling in the correct logic instead of following the incorrect steps that you intended

it's always going to be 0 for the first one, 1 for the second, etc., up to n-1

because you can't have less than 0 connections, and you can't have more than n-1 connections (not enough computers to connect to)

or, roughly equivalently, we can just say 0 and n-1 aren't compatible as an extra step at the end of the pigeonhole proof

[viral crown]

pigeonhole principle 🔛🔝

[fossil mural]

we're stuck in either [1, n-1] or [0, n-2], because 0 and n-1 can't both happen, and so we only have n-1 numbers available

[viral crown]

the best theorem in mathematics

and it's not even close

[obtuse lance]

yeah, I guess the trickiest part is realizing 0 and n-1 are mutually exclusive. Does the original question's assumption that every computer has at least one connection have a simpler proof I'm not seeing then?

[fossil mural]

pigeonhole

[viral crown]

^

[obtuse lance]

isn't it already pigeonhole

[fossil mural]

n-1 holes (number of computers connected), n computers, so there must be a duplicate

[obtuse lance]

oh ok I'm being lazy with the term pigeonhole

thanks

[fossil mural]

the point is that if you assume they all have at least one connection you get to skip over the hard part of dealing with 0 and n-1

[velvet lynx]

uh
we know if $ac \equiv bc \pmod m$ then $a \equiv b \pmod m$ if $c$ is coprime to $m$.

if $c \equiv 0 \pmod m$, $a$ and $b$ can be anything,
and if $c$ is coprime $m$, this is trivial to see

let d be $\gcd(m, c)$
we can substitute this equation as $\frac{c}{d}a \equiv \frac{c}{d}b \pmod \frac{m}{d}$
however, $\gcd(\frac{c}{d}, \frac{m}{d}) = 1$, therefore $a \equiv b \pmod \frac{c}{d}b \pmod \frac{m}{d}$

oh wow no newlines :(

[vital dew]

somehybrid

[velvet lynx]

aaaaa

gotta head to class now

[sand pelican]

Very glad to get an answer after my nap

[velvet lynx]

wait no thats bad im dumb

actually is it

formatting fix so i can actually read
we know if $ac \equiv bc \pmod m$ then $a \equiv b \pmod m$ if $c$ is coprime to $m$. \

if $c \equiv 0 \pmod m$, $a$ and $b$ can be anything, \
and if $c$ is coprime $m$, this is trivial to see \

let d be $\gcd(m, c)$ \
we can substitute this equation as $\frac{c}{d}a \equiv \frac{c}{d}b \pmod {\frac{m}{d}}$ \
however, $\gcd(\frac{c}{d}, \frac{m}{d}) = 1$, therefore $a \equiv b \pmod {\frac{m}{d}}$

[vital dew]

somehybrid

[velvet lynx]

hmm

this doesnt feel right

imma look at it when i get home

no there's definitely an issue here

the proof is left as an exercise to the reader

and the mistake

[sweet sleet]

I am doing a problem where I want to find the smallest number of people n such that the proability of two people having the same birthday is > 1/2. I am doing this by calculating P(2 people (of n total people) have same birthday) = 1 - P(no 2 people have the same birthday)

Then P(no 2 people have the same birthday) = #(ways to have no people (n people total) have same birthday)/#(ways to assign birthdays without restrictions) = {365 \choose n}/#(weak permutations of n into 365 parts). However, this is not correct for some reason as the denominator should be 365^n...

so where did I go wrong?

[peak olive]

Hi does anyone know about college math? Specifically permutations and combinations? I’m barely making it through math class because my professor isn’t the best at teaching

[velvet lynx]

actually is this right?

[mental plaza]

how would you simplify these and make a circuit?

ive used k maps and tried simplifying but i feel like im not doing it correctly

[weary tiger]

does having the method for finding the partition is a sufficient condition for the existence of the partition?

[dire schooner]

kill me

i have to separate it into every single problem

[random sparrow]

google split pdf

[tiny geyser]

I'm in an inquary based learning class and I'm stuck on this problem. When I asked my professor for help, she just told me that my classmate would be presenting the answer tomorrow and that might help. But I want to actually understand the steps into doing this.

[weary tiger]

bruh
I guess you see that (k+1)^2 -k^2 = 2k+1 that is exactly an odd number by definition

[dire schooner]

discrete math

[dire schooner]

i wrote my own script :p

[tiny geyser]

yeah i started by trying to prove that O is a subset of D by showing this, but I was stuck on showing how D is a subset of O other than just showing the same thing. I showed my professor that and she told me I needed to explain more with words and it needs to be a full proof, but I honestly don't know how to explain or prove mutual containment since we've never done it in class

[weary tiger]

prove that the definition of a odd number is 2k+1
so if it is an odd number then it is of the form 2k+1
and then prove that if it is of the form 2k+1 then it is an odd number

[tiny geyser]

ohhh, and that's how I would prove that D is a subset of O?

[bronze spire]

what did you get

[mental plaza]

bunch of different answers but i got i think (P and Q and R) v (~P and Q and ~R)

but then i searched up the answer and it said it simplifies to (P and ~R) V Q V (~P and R)

im just confused on what method should i use to get the simplified expression for the circuit

do i simplify manually using boolean algebra and laws

or using a k map

[bronze spire]

it's easy to visualize with a k map

and faster probably

[mental plaza]

Thanks! are there any good videos on k maps? my textbook only shows us simplifying using boolean algebra

[bronze spire]

also u probably know already (P and ~R) V (~P and R) simplifies to P xor R

[mental plaza]

i did not know...

[bronze spire]

so the simplest answer is Q V P XOR R

[mental plaza]

i didnt catch ot

it

[bronze spire]

im not sure but im sure u can find one

[mental plaza]

alright thanks for the help

[waxen bone]

First time formally using latex so forgive any odd formatting. can I get some feedback on these proofs

[fossil mural]

``Let $U = {x_1, x_2, x_3, \dots, x_i}$ for any $i \in \mathbb{N}$ be the universe'' - why is this here?

[vital dew]

bee [it/its]

[fossil mural]

the rest of the proof doesn't use x at all, and in fact it's valid even if U can't be enumerated (because it's infinite), so you kind of just, made the proof longer and less general for no obvious benefit

if you don't want to just start using the symbol $U$ with no explanation then you can introduce it as just ``Let $U$ be the universe''

[vital dew]

bee [it/its]

[waxen bone]

ok that makes sense

[novel ore]

what would im g be in the case that g is not a functoin? just the range of g?

[clever sail]

wdym

Pretty sure the idea is just like

if g isn’t a function then there’s some point in the domain that it maps to more than 1 value which means two functions f,f’ in X disagree at that point, which means either f doesn’t contain f’ or vice versa violating the assumption

[north junco]

how does my proof look?

[clever sail]

Is N considered to be strictly positive integers or just nonnegative integers here

[north junco]

strictly positive

[clever sail]

Mmm

Oh wait

Ignore that

[north junco]

ok

[quartz flame]

Found this nice pattern from the discrete slope case

[quartz flame]

(yeah, it is just the inverse function of the sum inside, but still nice pattern)

[sand pelican]

What is the lcm of a non zero x and 0? Some sources say it's 0 but my teacher said lcm is positive

[zenith anchor]

Umm, 1 maybe? Idk

[neon harbor]

It's 0, since every multiple of 0 is 0. Alternatively you can use lcm(a, b) = ab/gcd(a, b)

[manic coral]

Hi everyone

I'm reading a book called Discrete Mathematics with Graph Theory

And I don't understand this example right at the beginning of the chapter named "Adjacency matrix"

How is it possible that a matrix on the right is adjacency matrix of the graph on the left? It's not even 5x5

This example it seems contradicts their own definition

Am I stupid or what

[brave rock]

Yup I agree seems wrong to me

[signal sable]

lmao they forgot the before last line

That's legit a typo, they forgot the line for v_4

[clever kite]

Could someone help me see where I've gone wrong here?

[manic coral]

thanks, I was thinking that I'm going insane

[full maple]

anyone awake ?

🙂

[wheat lichen]

I am lost man

[full maple]

hi!

bro

do you know how to do discrete math?

[manic coral]

Idk maybe this book is full of typos but again, the text description does not match the permuation matrix P

maybe if they said that the columns of identity matrix instead of rows, the picture would also match

I just want to get some intuition on how this linear algebra works. Like, why can't we just multiply by P on the left? Why we also should multiply by the transpose on the right?

[full maple]

this is literally the last question

[wheat lichen]

💀

you are asking someone who passed

[full maple]

wdym

[wheat lichen]

very close

☠️

[full maple]

sooo

dyk?

🙂

[wheat lichen]

logic

[full maple]

yeah

[wheat lichen]

what is your doubt

[full maple]

its a deep logic tutor lmao

i just cant find the steps to do it

[wheat lichen]

see my man if you are not logical you are cooked

[full maple]

dyk those games

where you like combine

fire and earth

to get lava

[wheat lichen]

bro what

[full maple]

and then lava and water

[wheat lichen]

💀

[full maple]

to get rock

etc.

?

[wheat lichen]

fire and earth

@still vortex

[full maple]

doesnt matter

but

thats what this tutor is

[wheat lichen]

so you have to simplify a logical statment?

You wont to D implies C

[full maple]

i want to get to d implies c

yeah

you see the top 3

[wheat lichen]

and where are starting

[full maple]

1 2 3

those are my premises

[wheat lichen]

ye

[full maple]

I have to apply rules

to get to d implies c

[wheat lichen]

damn

[full maple]

yeah

so

whats the way

¬D∨C

this is what I have to get

to get d --> c

[wheat lichen]

ok good

¬D∨C∨T

[full maple]

t??

[wheat lichen]

tautology

[full maple]

yeha

[wheat lichen]

because i wanna bring in A

[full maple]

so I can use conjunction to craft in this tutor

so I need ¬D and C

and thats where im lost

[wheat lichen]

oh

[full maple]

if I can find how to get (B ^ ¬C) I can get ¬D from MP

[wheat lichen]

<=> ¬D∨C
<=> ¬(D∧¬C)

[full maple]

huh

[wheat lichen]

you wanted D and C

[full maple]

from what I already have

and wtf is <=>

[wheat lichen]

equivalence

tautological equivalence

[full maple]

there isnt a single equivalence operator in here bro

[wheat lichen]

that's not the point

[full maple]

I cant pull shit outta my ass bro

[wheat lichen]

this looks like you are trying to rewrite the same statement until you get somewhere

[full maple]

I have to apply the rules

yes

exactly what I tried to do

[wheat lichen]

bro i dont even know the game

but if you wanna get from A to B

all our steps need to be equivalent

[full maple]

game lmaooo

lets start here

so whats the next step sir

[wheat lichen]

idk

but you had a good start

[full maple]

;/

[wheat lichen]

A -> (B -> C)

[full maple]

I needa go back to highschool

[wheat lichen]

let's try to convert that into something with and

¬A ∨ (B -> C)

[full maple]

done

[wheat lichen]

or actually

¬A ∨ (¬B ∨ C)

¬A ∨ ¬B ∨ C

Now we need somehow D

[full maple]

?

[wheat lichen]

ye

[full maple]

so if I get ¬(¬B v C)

we can get ¬A

[wheat lichen]

¬A ∨ ¬B ∨ C ∨ (D ∧ ¬D)

[full maple]

woah

how

woah

?

nah that wont work

[wheat lichen]

I think it's better to start backwards

D -> C

[full maple]

so get d..?

[wheat lichen]

but i am bad at these games anyway so i wont be of a good help for that

[full maple]

i can only add certain things

its not a game bro its 12% of my grade lmao

[wheat lichen]

yea i mean these riddles

i am not made for that

[wheat lichen]

also you should be careful here around with needing help on graded stuff

[full maple]

why

[wheat lichen]

against the rules

[full maple]

bruh

thats dumb

its a tutor that keeps going until i pass lma

okay so if I get A

I win

[wheat lichen]

You can add (A ∨ ¬A) ∨ (B ∨ ¬B) shouldn't change the D->C statement

[full maple]

I need to us MP

i cant just add like that dude

lmao

[wheat lichen]

why

[full maple]

becaue it only lets me add specific things

i showed you

okay

i need the oppositve of either 1 or 4

[wheat lichen]

weird game

[full maple]

both things that I can us MP on to get A

how do I get it

[wheat lichen]

oh you got far

[full maple]

either ¬(B --> C)

or ¬(¬B v C)

to use modus ponens

[wheat lichen]

I think I got it

[full maple]

please share sir

[full maple]

dude I cannot add like thst

i told you

[wheat lichen]

there is an Add tho

[full maple]

this is what it lets you add

[wheat lichen]

select wisely then

[full maple]

bro??

[wheat lichen]

one should fit what i have

[full maple]

it wont

because its inclusive

[wheat lichen]

weird ass game 😭 🙏🏻

good luck tho

[vivid osprey]

Suppose $A=E\cup F\subset\mathbb R$ and $s\in\mathbb R$. Does $$A+s=(E\cup F)+s=(E+s)\cup(F+s),$$hold without assuming the union $E\cup F$ to be disjoint?

[vital dew]

psie

[vivid osprey]

I have the same question about tA=t(E cup F)=tE cup tF.

[vast halo]

sure, to both:
Let $A = E \cup F$.
If $x \in A$, then $x \in E \lor x \in F$
If $x \in E$, then $x+s \in E+s$, so $x+s \in A+s$.
Analogously for $F$.
If $x+s \in A+s$, then $x+s \in E+s \lor x+s \in F+s$
If $x+s \in E+s$, then $x \in E$, so $x \in E \cup F$, so $x \in A$.
Analogously for $F+s$.

Then, assuming that $A+s=(E+s)\cup (F+s)$, we have the desirable property that $x+s \in A+s \iff x \in A$

[vital dew]

MSP729

[toxic gorge]

Can anyone help me with this? Everytime I try and solve it, I end up doing so with contrapositive instead of contradiction

[cedar spindle]

the contrapositive proof would be to prove the statement: if n is not prime then 2^n-1 is not prime

the contradiction would to be assume 2^n-1 is prime but n is not prime and then try to reach some kind of contradiction

@toxic gorge

[snow cedar]

I'm having difficulty showing the direction where assigning odd number to edges => eulerian.

I am trying to show that there is an eulerian circuit. Any help would be greatly appreciated!

[snow cedar]

I noticed that if I cross an edge to arrive at a vertex, then cross that same edge to leave it, if f_e > 1 I'd need to come back to it eventually and alternate "leaving" and "arriving".

I feel like this observation isn't enough though because it's still not clear how to use it to show there's an Eulerian circuit: I need to show that I can start at a vertex, and end at the same vertex, and along the way I only cross each edge once. When I'm done, I would have crossed all edges without repeats

[blazing seal]

I feel like my approach (and I haven't done a done of graph theory) would be to show that if you complete a circuit by crossing an edge n times (for odd n), then you can do it by crossing that edge n-2 times and the proceeds by induction on n, starting with if you can do it by crossing an edge 3 times then you can do it by crossing an edge once

[snow cedar]

Yeah for f_e = 3, I can just repeatedly enter a vertex and leave it then finally enter it again. I am assuming this property though, but I can see that instead of doing that I can just go through it once

[mental plaza]

Prove that the following is a valid argument:
All real numbers have nonnegative squares.
The number i has a negative square.
Therefore, the number i is not a real number.

is this a good proof

[woeful trench]

Struggling with conceptualizing proofs and disproofs. Primarily "reading" the equation and understanding what it means. Could anybody give me a rough translation? I am familiar with introductory concepts of discrete math.

[blazing seal]

So, for A, r is going to range over all integers so we're going to have stuff like

r  | 6r + 12    | m
---------------------
-2 | 6(-2) + 12 | 0
-1 | 6(-1) + 12 | 6
0  | 6(0) + 12  | 12
1  | 6(1) + 12  | 18
2  | 6(2) + 12  | 24
``` so on and so forth. So, `A = {..., 0, 6, 12, 18, 24, ...}`. Similarly for `B`. Does that help at all ?

[scarlet harness]

Hi. Does anyone recognize the book with these exercises? I'm looking for the solutions to compare them with my answers.

[dense dawn]

is that from kenneth rosen 8th edition?

[sterile walrus]

hello

Some element of K is both in L and greater than 5.
the answer is:
∃x(b(x,K)∧b(x,L)∧x>5)
but why not
∃x(b(x,K)->b(x,L)∧x>5)

[mental plaza]

what is the function b?

[mental plaza]

did you have the original question

[sterile walrus]

it's about predicate logic

[sterile walrus]

any function where x belongs to K

[mental plaza]

the correct answers captures the statement correctly because it is saying that there is an element x which exists in both K and L and also is greater than 5.

the wrong answer is wrong because it says that if some element x exists in K then it exists in L and is greater than 5

so there is an implication

simply, first statement says there is an element which is both in k and l and also greater than 5. second one( wrong answer) says that the element must exist in K in order to exist in B and be greater than 5.

hopefully it makes sense

[sterile walrus]

ahhh got it

yeah it does

thx

[mental plaza]

np

[analog tinsel]

guys, what am I missing?

Isnt the minimum weight spanning forest of a graph G always just (V(G), {}) , when the edgeweights are positiv ??

[quiet eagle]

For all the nodes to be in the induced subgraph, every node needs to be "matched" by an edge

So if you chose E = {} the induced graph would also have no nodes

[analog tinsel]

I dont get it, a graph H is a spanning subgraph of G iff V(H)=V(G). A forest is an acyclic graph. Where does the induced subgraph thing come from ?

for this to make sense we would need to define a spanning forest as an edge induced graph

but afaik thats not the definition

[open wyvern]

okay so i have a very stupid counting problem that i somehow am struggling with

how many sequences of A's and B's of length m are there such that there are at most n A's in a row

if this cannot be generalized, then the specific case would be m=22 and n=4

i think you'd use recursion from say the back of it based on if it ends with some number of As, or some Bs and build it up, but idk

is this the correct approach

[quiet eagle]

Hm thats seems to be true. I don't have a definition for spanning forests in my textbook, but I assumed for this problem to make sense that it would be defined via induced subgraphs. If there is no definition in the book from your excerpt, check the (hopefully?) following algorithm

[analog tinsel]

well in wikipedia they define it as the union of spanning trees of the components. So yes it fine.
The paper I had didnt define it anywhere but it wouldnt make sense otherwise. But anyways, seems like it was a very basic definition that I just wasnt aware of. Thank you very much for helping!

[sterile walrus]

I was solving some questions... and faced this. The correct answer said its a, why? And why not c if a is true

[oblique pelican]

C says "If there exists an x such that P(x) is false, then there does not exist an x such that P(x) is true"
This is false because it is possible that P(x) is false for some x but then P(y) is true for some y != x. Basically one value doesn't tell you the whole picture.

A says "If there does not exists an x such that P(x) is true, then there exists an x such that P(x) is false"
This is definitely true. If P(x) is never true for any given x, then of course there is an x where P(x) is not true (assuming that the set that x comes from is nonempty).

The wording is kinda hard to comprehend if you dont look at it closely

Basically C says "If P(x) is false for at least one value, then P(x) is never true" while A says "If P(x) is never true, then P(x) is false for at least one value"

[sterile walrus]

can u give an example, i don't think i fully get it

[clever kite]

Am I doing something wrong here?

I feel like I must've missed something

[oblique pelican]

Let P(x) be the statement "person x is a male" and let the universe of discourse be everyone on Earth.

A says this: "If no person on Earth is a male, then there exists a person who is not a male" (that would be true because everyone would be not a male. "I know no one on Earth is a male, so if I approach any single person, I know they will not be a male")
C says this: "If there is some person on Earth who is not male, then no males exist on Earth" (not true because there definitely could be another person who IS male. This is like saying "well I know someone who is a female, so therefore males do not exist")

[obtuse lance]

looks about right to me. Maybe for part b instead of saying if p^k divides... just say if p divides. Since x and x-1 are relatively prime, p can only ever divide one or the other. Once you know which one it divides then the fact that it's 0 mod p^k tells you all of p^k divides it from knowing p

not sure if that is what you mean by feeling you're missing something or not

[clever kite]

Ah ok, I'll definitely make that clarification

Mostly felt like I was missing something since it was super short and simple compared to other problems in the chapter

[sterile walrus]

i completely understand it, many thanks for your help!!!

[limpid flax]

Trying to prove this statement through induction. Here's my attempt: Case n=1: 3^1 > 2^1. This case is true. Induction case: Let n{N be arbitrary. Assume 3^n>2^n is true. Multiply each side by 6. Now we have 6(3^n)>6(2^n). Factoring 6 we have (2)(3^1)(3^n)>(3)(2^1)(2^n). Simplifying we have (2)(3^(n+1)) > 3(2^(n+1)). I'm confused on what the next step would be

[snow cedar]

Think I had some time to think over this, for proving that it is Eulerian, we just need to somehow justify that the degrees of each vertex are right?

[limpid flax]

would it be something like divide by 2 on each side leaving 3^(n+1) > 3/2 (2^n+1) > 2^(n+1) ?

[obtuse lance]

I wouldn't approach it this way personally, I was thinking more like start from 3^{n+1} = 3 * 3^n > 3 * 2^n ...

[limpid flax]

we were just introduced to induction today and only saw one example. I get the 3^(n+1) part but what does multiplying by 3*2^n do?

[obtuse lance]

oh that's using the inductive hypothesis 3^n > 2^n

[sick grail]

assuming that's meant to say "even degree" then yes that would be sufficient

(I'm unsure what the expected way to do this exercise is, and the way I'd do it is not something I can really provide just hints for nor do I think it's particularly nice)

[snow cedar]

Oops, yes I meant "even degree"

Hmm yeah this is harder than i thought

I was trying contradiction but couldn't really see anything

[sick grail]

the more I think about it the more I think my method might actually be the intended one, although it must just be me being blinded to alternatives now that I have one proof

it's essentially to construct a different graph G' so that there's an obvious analogue to the walk which shows G' is eulerian and hence has every vertex of even degree, and justify this means G also has vertices of even degree

[snow cedar]

Constructing a different graph You mean it might not even have the same edges?

I'm guessing the value of each f_e is supposed to help out with this

[sick grail]

I mean there's a way to do it with G as a subgraph, with the small downside of being only slightly more annoying to describe

[snow cedar]

The graph is undirected, does that simplify anything?

[sick grail]

it's more a question of whether you're allowed multiple edges between vertices

[snow cedar]

sounds like a multigraph, I think no

[sick grail]

the annoyance is incredibly small btw: it's the difference between introducing a new vertex in the middle of each edge of a multigraph (this turns it into a simple graph!) and leaving one of the edges between each pair of vertices as is (which still turns it into a simple graph)