discrete-math

[still nexus]

so does “p only if q” = p—>q or q—>p?

[violet tulip]

"p only if q" = p—>q

same as saying if p, then q

looks like the answer shouldve been b there

[still nexus]

that’s what I’m thinking, but I argued with the prof on it for like 10 minutes and he still disagrees so idk. It’s the only question I missed anyway

Actually, he said it could be either because only if can mean “is necessary for” or “is sufficient for” (which I disagree with), but he’s only accepting d even though b is also correct by that logic.

[violet tulip]

sure, you can say that q “is necessary for” p, but just because q is true, that doesn’t guarantee that p is true. We could say, for example, “You are eligible to become president only if you are a natural born U.S. citizen.” So being a natural born U.S. citizen is necessary for becoming president, but just because you’re a natural born U.S citizen doesn’t mean you are eligible to become president (there are other requirements to become one such as your age).

i do disagree with your professor as well. "only if" implies p->q, but not the other way around

[main socket]

In response to Skyler's query, when it says "p only if q" that is referring to "q --> p". It's the same as saying p happens only when q is true. So your premise is q and conclusion is p.

[soft thorn]

but q --> p can have p true without q being true?

so that does not sound right

[reef thistle]

it's the other way around, p --> q. If p happens, you can conclude q happens.

[main socket]

Think about it like this, "p only if q" says that p can only happen when q has happened. So q is a necessary condition for p to happen. This lets us see that if p doesn't happen then q doesn't happen, which gives the following expression: "~p -> ~q". Take the contrapositive of this to get expression for "p only if q": "~~q -> ~~p" which is equivalent to "q -> p"

[violet tulip]

it’s still the other way around. you stated that q is a necessary condition for p to happen, which is true. but this means that if q doesn’t occur, then p doesn’t occur either. this gives the expression ~q -> ~p, which is equivalent to p -> q

[main socket]

Have a look at the following stackexchange answer
https://math.stackexchange.com/questions/617562/conditional-statements-only-if

Take the following expression:
a <-> b which means a if and only if b
Which is equivalent to saying "a if b and a only if b", so in terms of equivalent expression we get:
a -> b & b -> a
This is a well known equivalence relation

[violet tulip]

which part in particular from that website? they all seem to agree that p only if q is equivalent to p --> q

[main socket]

Look at the top answer

[violet tulip]

and yes, we can take a look at the biconditional statement, a if and only if b. so theres 2 parts

• a if b, which is equivalent to b -> a
• a only if b, which is equivalent to a -> b

yeah i read that

are you referring specifically to the last paragraph of it?

[main socket]

Yea

[violet tulip]

in the last paragraph, they're considering q only if p, which leads up to q->p

[main socket]

Yea, you are right. Did it on paper and it makes sense now

[rough shell]

Does anyone have a comparison or opinion on discrete math textbooks for self study? I have the latest Ken Rosen Discrete Math book and latest Suzanne Epp Discrete Math book in pdf form.

[still nexus]

I don’t remember the author of the discrete textbook published by Springer, but I’m using that textbook to suplement the textbook we’re using for my actual class and I much prefer the springer one. It’s more detailed and it flows well, which I’ve found helpful for self study.

The textbook we’re using for class rn is the zyBooks textbook and it’s nice because it has problems you can work and see the answers for in real-time, but it’s $58 and you can just work practice problems in a regular textbook and google answers

But if you need that feature to help you keep on task for working lots of problems, the zyBook is fantastic.

[weary tiger]

anyone good at boolean algebra?

[weary tiger]

now thats epic

[vast dust]

How to show two equations are the same without an equal sign

[ivory badge]

what

[soft thorn]

but that only tells you H is true when M is true

it doesn't tell you what happens if M is not true

yes

[vagrant warren]

"unless" usually means "if not"

that's a very very unusual way of interpreting unless

it would seem so

according to that explanation in your notes

but damn if that isn't completely messed up

usually "Q unless P" means !P => Q

I'd just caution you to be really careful in the future about it, once this class is over, that that's really nonstandard

[tacit willow]

quick question

14 􀵊 2 􀵌 24

14/2=24, is this a valid proposition?

[sleek swallow]

Is / allowed as an operator in your class?

If so, then that's a proposition.

[tacit willow]

``

(z A) (z*2>z2)

(∀z ∉A)(z*2>z^2)

Is that the correct negation?

[soft thorn]

does not look correct

[tacit willow]

Whats wrong?

[soft thorn]

the inequality for one

and you don't need to turn in to not in

[tacit willow]

hm

So how would i do this then

[soft thorn]

what's the negation of a < b?

[tacit willow]

a>b

[soft thorn]

no

[tacit willow]

hmm.. ?

a¬<b
```?

[soft thorn]

what if a = b?

[tacit willow]

``

¬(a = b)

?

[soft thorn]

the negation of a < b is a >= b

[tacit willow]

a is greater than equals b?

[soft thorn]

yes

[tacit willow]

hmmm, not sure i understand the logic

[soft thorn]

try test out a few numbers

1 < 1 is false right?

[tacit willow]

yea

[soft thorn]

what about 1 >= 1?

[tacit willow]

True

[soft thorn]

you can reason about it

if it helps

(a < b) <=> a is less than b and a is not equal to b

negating gives

(a >= b) <=> a is greater than b or a is equal to b

[tacit willow]

ooooooooooh

i seee

have to see whats not there

[dense pier]

Hello

Anybody can explain how they go from first red arrow to second red arrow?

Please

[violet tulip]

because V is the identity for ∧

[dense pier]

What?

I don't get it

[violet tulip]

p ≡ p ∧ V by the identity law

its like saying, x + 0 = x, or x * 1 = x

well, i should point out that V is a tautology here. that V always has a truth value of true

[sudden wedge]

I am so stumped on this one gang. Can anyone provide some insight into how to tackkle this problem?

If we are trying to prove the proposition “if x is a non-zero real number and 1/x is irrational then x is irrational” by contrapositive then what should be assumed?

[violet tulip]

do you know what proof by contrapositive is

[lethal oak]

if we have a set A = {1,2,3} and we take its power set P(A)

then $$P(A) \cap \mathbb{R} = \emptyset$$

[vital dew]

rocco:

[lethal oak]

right?

i should probably ask this in questions

[faint narwhal]

Yes

[lethal oak]

yes as in ask in questions or i am right

[faint narwhal]

You're right

[errant patio]

Hi im very new to discrete math, can i get some pointers on this question https://media.discordapp.net/attachments/496964187101331458/671394365033414679/2980x162.png?width=2688&height=147

[sleek swallow]

Well, there's no problem with regards to that.

$(p \implies q) \iff (\lnot{p} \lor q)$

[vital dew]

Abhijeet Vats:

[sleek swallow]

^Do you know of that equivalence?

@errant patio

[errant patio]

yes, does it go like this?

@sleek swallow

[sleek swallow]

Nope

You have to turn the implications into disjunctions first

Then you can use de morgan’s law to simplify

[errant patio]

So i need to turn the q->r into disjunction after that?

[stray reef]

$\neg(p \to q) \neq (\neg p \to \neg q)$

[vital dew]

Ann:

[thick sky]

x is students, y is courses

A(x) means they're part time student, M(y) = the class is a math class, and T(x,y) that x student is taking y class

Does this show that there is some part time student who is not taking any math classes?

whoops, M(x) should be M(y) in the picture

[faint narwhal]

I assume knights always tell the truth and knaves always lie?

[weary tiger]

I mean break it down: A's statement is true if either ABC are knights.
B's statement is true if he is a knave.
C's statement is true if A is a knave.

If A is not a knave B would be wrong and C would be wrong#

@teal latch they all speak the truth=

?

@faint narwhal would you assume all speak the truth? i mean you are most likely more into formal logics than me. how would matrice like of truth look like

I mean as someone that wasnt that much expose to math since hight school i would check all of the their statements agains each other to show which statements make contradictions

say 1 is truth -1 is lie 0 is indetermate and i is knave and b is a knight
A(1i) = B(1i) and C(1b)

[faint narwhal]

I think the point of the question is that knights always tell the truth and knaves always lie

So having all three of them be knights doesn't work since then C would be lying about A being a knave

[paper scroll]

Can someone explain how to make a venn diagram from truth table data?

[paper scroll]

Would I shade in p and the all the intersecting ones in the middle?

[tranquil jewel]

would 2b be false for (e) as the converse doesn't hold or am I wrong?, sorta confused on it since it would be written as "If x = sqrt(x^2) then x e R", but is that for any possible x?, and is x e R just always true?

[soft thorn]

For whatever values it holds for x

Is x a real number

I guess it's easier to think when/if it can be false

[tranquil jewel]

But we're talking about the converse

[soft thorn]

That is the converse?

[tranquil jewel]

No

1 is the regular

It would be false as regular like you said

[soft thorn]

??

[tranquil jewel]

uh

For the converse

"If x = sqrt(x^2) then x e R"

is x just all real numbers still?

[soft thorn]

Which is what i stated?

Reread what I said

[tranquil jewel]

Ah

Would the x e R be True tho then?

im confused about that

[soft thorn]

Is there a non-real number such that x = sqrt(x^2)?

[tranquil jewel]

Uh

[soft thorn]

Think of the simplest possible example

[tranquil jewel]

I'm confused on the "non-real number" part

[soft thorn]

Try i

[tranquil jewel]

So i would work?

[soft thorn]

Yes

And obviously i is not real

So the converse implication is not necessarily true

So the converse is false

[tranquil jewel]

Okay wait I'm sorta lost

is x = sqrt(x^2) is false proven to be false as you said right

doesn't that mean its impossible for the converse to be false

cause of the truth table

[soft thorn]

?

[tranquil jewel]

thats the truth table right, for P implies Q

[soft thorn]

Yes

[tranquil jewel]

So we're saying that P, (x = sqrt(x^2) is false

Wouldn't it mean the converse is true

[soft thorn]

No

P => Q is false whenever we have a P true, and Q false situation

[tranquil jewel]

Correct

[soft thorn]

Q => P is false whenever we have a Q true, P false situation

We've found both of these situations

[tranquil jewel]

Okay wait,

So the original statement is False correct?

If x e R then x = sqrt(x^2)

[soft thorn]

Yes

It's false

[tranquil jewel]

So the converse means we flip the P and Q basically right

[soft thorn]

Yes

[tranquil jewel]

So the new P, x = sqrt(x^2)

we know its false right?

as you said

[soft thorn]

That depends what value of x you pick

[tranquil jewel]

Alright so thats where im confused

how do we dictate that

its obviously easier to prove its false

but like before it said the number has to be x e R

[soft thorn]

The converse is basically asking

Whenever x = sqrt(x^2) is true

Does it then hold that x is a real number

[tranquil jewel]

so the P is the hypothesis

ahh

Okay so

the overall statement is false

gimme a sec

So can we compare this converse to the truth table is what I'm wondering?

[soft thorn]

Sure

Draw a new one

Or draw a new column

For the converse

[tranquil jewel]

What im lost on about the truth table right, we're assuming that P implies Q, so when do we dictate if P is false?

Like this example

It's true right?

Hol on

[soft thorn]

Yes

[tranquil jewel]

Could I just ignore the truth table and think about these implications logically?

[soft thorn]

Sure

[tranquil jewel]

So in the pic I posted, we're saying that 0 = 1 then 8 is odd right?, are we stating that 0 = 1 is true?

or is it just a test

[soft thorn]

Ehh

[tranquil jewel]

Cause my brain is thinking like

[soft thorn]

I would not state that is true

[tranquil jewel]

so on a truth table would P be false then

[soft thorn]

It's a false implies true situation

[tranquil jewel]

Ye

[soft thorn]

Which is true

[tranquil jewel]

Mhm

If I went about the question like

assumed that 0 = 1 is true for now

and then test the 8 is odd

and obviously its true

well actually nvm that lemme jus

go back to my question but not e

[soft thorn]

Actually wait

False implies false

Which is also true

[tranquil jewel]

Yee

Okay so for 2(b) for 1(a)

If -1^2 = 1 then (9 is even or 5>=5) < converse

It is a true converse correct

[soft thorn]

Yes

False implies anything is true

[tranquil jewel]

Where is the false

like

[soft thorn]

-1^2 = 1

[tranquil jewel]

isn't that true

even if it was true or false

the statement is true cause 5>=5 right

[soft thorn]

You can view it like that as well I guess

Anything implies true is true

[tranquil jewel]

Alright so then for 2(b) for 1(b)

I said it was true

but im confused on how to go about it logically

when the k e N or x e R comes after I sorta get confused on what to test

[soft thorn]

Hmm

[tranquil jewel]

the converse being (If x^2 + kx + 1 > 0 then k e N)

I said the original would be false

Assuming you had like k = 100 then an x like -1 it would be less then 0

But going with the converse I don't really get how to go about it

[soft thorn]

That seems valid

[tranquil jewel]

Since the k e N comes after

[soft thorn]

I mean

What if k was 0.5?

[tranquil jewel]

Like the way you went about the 1(e) converse how would you do that for 1(b) converse

Hm but like

isn't k all natural numbers

or are we saying if we chose k as that

it means k e N is false

since its not the hypothesis this time

[soft thorn]

If we pick a k

Such that the inequality hold

Must k be a natural number?

[tranquil jewel]

No

So it would be false then?

but like im confused

cause obviously you can pick a k which makes it true

but you can pick one that makes it false too cant you

[soft thorn]

Yes

The overall statement P => Q is true

When

[tranquil jewel]

so it has to be true

since there is a possibility of always being true

but it could be false obviously

[soft thorn]

We want that whenever P is true

Q is also true

[tranquil jewel]

Correct but the statement is only false if Q is false tho

but yea

we want to make P true alright

[soft thorn]

It's only false if Q is false when P is true

[tranquil jewel]

Yes

Alright okay so

for just the regular 1(e)

It's false right

obviously if you chose a negative number when you square and square root it, it won't be negative

hence x = sqrt(x^2) is false

[soft thorn]

Yeah

[tranquil jewel]

Now for the confusing 2(b) 1(e) one more time oof

What is the best approach to test it?

[soft thorn]

Just make a guess of whether you think it's true or false

If it's false

Try find a counterexample

[tranquil jewel]

By true/false you mean the overall statement right

[soft thorn]

Yeah

[tranquil jewel]

Alr

I get the imagery part now kinda

so you're forcing Q to be false to test if P is true right

[soft thorn]

I'm trying to find any true implies false situation

[tranquil jewel]

Correct

So if you use i then p is true

but the q part is false

[soft thorn]

Yes

[tranquil jewel]

alr I get that and uh how would I go about this

[soft thorn]

What have you tried

And which one

[tranquil jewel]

Just the first one

so,

[soft thorn]

I mean

[tranquil jewel]

one sec

alr I get why a is false

LOL

[soft thorn]

Yes

[tranquil jewel]

no integers multiplied by a give b

makes sense

[soft thorn]

Yes

[tranquil jewel]

to b

[soft thorn]

Yes

[tranquil jewel]

i'll give it a try one sec

I'm sorta confused whats the point of the "if and only if"

does that mean the n has to be the same?

[soft thorn]

No

It's a bidirectional implication

a if and only if b

Is the same as

if a then b

And

if b then a

[tranquil jewel]

uh hm

So are we saying that n is the "b" tho right?, and "b" can be any natural number

"b"

I mean

[soft thorn]

a is 16 | n^2

b is 8 | n

Where n is a natural number in both cases

[tranquil jewel]

wait

oh ok I get what you mean

I mean uh

like diff variables then

for 16 | n^2

16 is say c in this case and n is d

[soft thorn]

I mean

Ok

[tranquil jewel]

LMAO

but like if I pick n as 7 say

doesn't that just make a false

16 | n^2

[soft thorn]

Yes

[tranquil jewel]

Is that all I need to prove its false

[soft thorn]

No

[tranquil jewel]

What else do I need to do?

[soft thorn]

a being false doesn't tell you about the whole statement

[tranquil jewel]

Hm

[soft thorn]

unless b is true

[tranquil jewel]

so the if and only if

[soft thorn]

Then you would have true implies false in the backwards implication

[tranquil jewel]

means two implications?

[soft thorn]

Yes

[tranquil jewel]

So I need to prove both are false implications

[soft thorn]

No

If one direction is false

Then the whole statement is false

[tranquil jewel]

isn't that like saying

if the statement is false the converse has to be false

[soft thorn]

No

a <=> b

Is the same as

a => b and

b => a

[tranquil jewel]

so if I prove one of the implications is false then I'm good because of the "and"?*

[soft thorn]

Yes

[tranquil jewel]

two false make a false for "and" right

[soft thorn]

Yes

a and b is false

If at least one of a and b is false

It's only true when both are true

[tranquil jewel]

Alr back to the question now uh

[soft thorn]

The forwards implication is much easier to work with

[tranquil jewel]

the what now

[soft thorn]

if 16 | n^2 then 8 | n

[tranquil jewel]

ahh ok

So if I make

16 | n^2 true and 8 | n false then I've proven its false right

[soft thorn]

And 8 | n is false

Yes

[tranquil jewel]

hm

[soft thorn]

Think of the simplest counterexample

[tranquil jewel]

Can I say n = 16

so then like,

n^2 = 16q

[soft thorn]

8 | 16

Is true

So that's not very useful

[tranquil jewel]

I was proving a to be true tho

oh wait

oops

LOL

hm

n = 4

[soft thorn]

Yes

That works

[tranquil jewel]

n^2 = 16q so q would be 1, and 8 | 4 is false right

ok

[soft thorn]

So the entire statement is false

Because the forwards implication is false

[tranquil jewel]

So what would be the other way to go about it tho

[soft thorn]

I believe the backwards implication is true

But that tells us nothing useful

[tranquil jewel]

Hmm

to c

[soft thorn]

That one is just kind of dumb

[tranquil jewel]

LOL

so its saying x and y real numbers but both greater then 0 then uh

oh

if I just pick large x and y value

its false then

[soft thorn]

Yes

[tranquil jewel]

LOL

alr to d

[soft thorn]

This one is just finding such an x where it doesn't hold

Or just knowing about how polynomials grow

[tranquil jewel]

its easy?

okie i skip

!

[soft thorn]

If you know how polynomials grow

Then sure

[tranquil jewel]

Uh

Let me take a closer look

[soft thorn]

Logically it should make sense as well

[tranquil jewel]

so x is any real number

[soft thorn]

E.g. think what happens when x = 456789

[tranquil jewel]

OH

so once it gets that big

it cancels the division term

[soft thorn]

Yes

[tranquil jewel]

and is just 456789^5

[errant bear]

yes but not really

[soft thorn]

Yes

[tranquil jewel]

which is bigger then alr

well I just need to prove its false right

and if that side is bigger its false then ye?

[soft thorn]

Yes

Think about what the left hand side is equal now

[tranquil jewel]

somethin to the power of 24

well scientific notation

[errant bear]

[soft thorn]

123 * 456789^4 right?

[tranquil jewel]

Ye

it was like

somethin x10^24 i gotta put it in again

[soft thorn]

Which is clearly less than 456789^5

[tranquil jewel]

ye

[errant bear]

just cancel the x^4... what r u doing

[soft thorn]

🤔

[tranquil jewel]

he just means divide

the side

by it

probably

[errant bear]

123•456789>=x^2

so is false for any x greater than the square of that

u dont have to do all that

[tranquil jewel]

Is there any examples of these statements my notes got like none LOL

[soft thorn]

I wanted to avoid reasoning out of the division by 0 problems

[sleek swallow]

Uhh examples of those statements?

[soft thorn]

Also manipulating an inequality by assuming it's true to begin with

Is kind of sus

[tranquil jewel]

Yea

like

written out

what are they called

[errant bear]

how lmao

you are proving it false, so assume its correct and show falsity

[soft thorn]

That's true

But more reasoning required

[errant bear]

well its asking for an explanation not just a counterexample

so you need reasoning not just "look at this big number it doesnt work"

[soft thorn]

🤔

[errant bear]

idk thats just me

[soft thorn]

A single counterexample is a perfectly fine way to disprove a for all statement

[errant bear]

i mean yeah technically, but it asked for explanation

[soft thorn]

🤔

What could you possibly give

"it doesn't hold for all numbers"

[errant bear]

yeah, and show the inequality

idk, just the reasoning for why big numbers break the proposition

[soft thorn]

Isn't that what I did though?

[errant bear]

i mean ig

im just being technical ig

it grinds my gears slightly

[tranquil jewel]

ima take a break ru gonna be here still kang?

[soft thorn]

Sure

[tranquil jewel]

alr

[tranquil jewel]

okie

Do I just start it out like "There exists an integer x such that.."

[warm coral]

https://i.gyazo.com/thumb/1200/c37aa1938b6134e4863aa94d173525d5-png.jpg

i genuinely dont know what this is asking

do i just guess and check to find the first aEN?

then how tf do i use MI

[soft thorn]

You want to find the first a where the inequality holds

The prove its true for all natural n > a

Hmm

Should that be a strict inequality

Meh

[warm coral]

no one in my class understands this question

[soft thorn]

n = a essentially becomes your base case for induction

Hmm

[warm coral]

do you think this question is valid? like do you think you would possibly work it out

[soft thorn]

Yes

It's a perfectly reasonable induction question

[warm coral]

i honestly cant trust my discrete math prof loool this guy makes so many mistakes

so this is just regular induction, no strong induction or anything

[soft thorn]

Regular induction should be fine

I don't get why that inequality is strict inequality

But I don't think it matters too much

[warm coral]

i dont understand what 3^n < n^3 computes to

how do i expand that

its really odd

[soft thorn]

You don't

Flip the inequality around

Try n = 1, n = 2, and so on

Until the inequality is true

That becomes your base case

[warm coral]

honestly, im just gonna come back to this question later, i have so many things to do rn

[soft thorn]

Ok

That's kind of sus as well

It's not necessarily the first a that guarantees good results

[manic abyss]

I can vouch for cali that this question could be wrong

We have the same prof and he always makes mistakes

[soft thorn]

Pick the second a where the inequality is true lol

Or is it

Nvm

[manic abyss]

Idk I don’t understand why there are 2 inequality symbols

I can’t even translate that question to English aha

[soft thorn]

You want to prove that for all n greater than a

The inequality holds

[manic abyss]

What even is a

Ik it can be a natural number

But like wat, how do you know what a is xD

All n greater than a but a is any natural number wtf

[soft thorn]

That's why the question says find the first a

[manic abyss]

Hmmm

Using MI, spooky

[soft thorn]

Finding the first a is literally just testing numbers

But

There is an issue

It can't be the first a

[manic abyss]

So essentially the question is asking us to find the base case using induction?

[soft thorn]

No

You find the base case just by checking

And then prove the inequality holds for n > a by induction

[manic abyss]

makes more sense now

thanks 🙂

[soft thorn]

But there is a small error

The smallest a isn't going to give a good result

Pick the next smallest a

[fickle horizon]

Does anybody know what I am doing wrong here?

I know for sure that -10+12 is not 18 :/

[faint narwhal]

You didn't flip all the bits when you went to -10

[fickle horizon]

thanks :)

[long forum]

Union and intersection on sets are associative as well as distributive right.

Then why am I getting different answers

Pls mention me @long forum if you reply

[sleek swallow]

Associativity holds as follows:

$(A \cup B) \cup C = A \cup (B \cup C)$

[vital dew]

Abhijeet Vats:

[sleek swallow]

@long forum what you have written is not correct because there are two different set operations at play

Like, in the bottom half of the image

[long forum]

You're right

Yeah thanks

[sleek swallow]

You’re welcome.

[tough locust]

Is it correct to view a tree as a mapping from N²?

[stray reef]

from N^2 to what

[tough locust]

A boolean set i guess if it's just a graph with nothing on it. Or if it's a tree that assigns an object to each edge or vertex, to the set of all those objects

[stray reef]

[tough locust]

I was thinking of the Caulkin-Wilf tree when thus question occured to me

I can never remember how to spell "occured"

Two rs it should be okay

Well are graphs in 1-1 correspondence with matrices?

That would answer my question

[pale epoch]

finite ones, yeah

[tough locust]

Actually it doesn't quite answer it

Maybe

[pale epoch]

i guess if you have a graph with vertices a subset of natural numbers you can assign to each tuple a 1 if there is a edge between them and a 0 if there is not

and that is your mapping 🤷

[tough locust]

Aight thanks

[edgy plume]

Yes, those matrices are called "adjacency matrices".

[pale epoch]

but a graph can have uncountable many vertices

[stray reef]

are there any graphs which cannot be embedded in R^3 with every edge of length 1

[pale epoch]

how do you embed |2^R| many vertices in R^3

[tranquil jewel]

I'm confused on how to do 6, so for the negation I know I would flip the "all" or "exists" to the opposite but what else do I do?

[soft thorn]

That's pretty much it

Negate inequalities as well

[tranquil jewel]

So flip the x < y to x > y for 5(a)?

or would just putting the negation symbol be good enough there

[soft thorn]

No

Well

Firstly that's not the negation

Secondly, putting the negating symbol in front

Ehh

It's not wrong

But not useful

[tranquil jewel]

Hm

by infront I mean like

negation symbol(x<y)

[soft thorn]

I know

It's not wrong

But not useful

Like

It's mathematically valid and correct

But I think it's better to actually rewrite the inequality

[tranquil jewel]

gimme a sec lemme just get a pic off my ipad

so would this be wrong

[soft thorn]

It's not wrong

[tranquil jewel]

What is a better way of writing it?

[soft thorn]

But I would say rewriting the inequality is better

[tranquil jewel]

so actually negate the inequality

[soft thorn]

Yeah

Well

Rewrite it

[tranquil jewel]

So is the negation of that x >= y?

[soft thorn]

Yes

[tranquil jewel]

for b it would be x > y?

or does the equal stay

[soft thorn]

It would be x > y

[tranquil jewel]

So the new 6a would be false right

since we choose the x first, then y

oh wait

It would be true right

So we can choose x out of any of the integers, then we choose a y out of the rational numbers, and we can make it so y is always less then x right? which makes it true

[soft thorn]

I mean

Was the original 6a true or false?

[tranquil jewel]

True

5a was true

Cause its there exists

both of them

[soft thorn]

Ok

Looking at just a)

[tranquil jewel]

ah

is it false because it says all

[soft thorn]

What if I pick x = 5, y = 1?

[tranquil jewel]

we looking at just 5a right

[soft thorn]

For the negation

[tranquil jewel]

for the negation

it would be true

the x = 5 y = 1

[soft thorn]

Is it?

[tranquil jewel]

didn't we say the negation is

x>=y

[soft thorn]

Ah rip

Flip what I said

[tranquil jewel]

but yea

[soft thorn]

y = 5, x = 1

[tranquil jewel]

false then

[soft thorn]

And since it's supposed to hold for all x and all y

And we found a specific x and y where it doesn't hold

The negation is false

[tranquil jewel]

ah

Alr

Now for b

it would flip to true for the negation right

cause its "exists"

OH WAIT

hol on

one sec

it would be false also

[soft thorn]

The original statement?

[tranquil jewel]

no

the original is false

negation is false

for (b)

wait

flip what I said

[soft thorn]

The original is false

That is correct

[tranquil jewel]

Wouldn't the negation also be false, since there exists an integer x such that for all rational numbers of y, x is greater then y

[soft thorn]

There exists an x and there exists a y such that the inequality holds

[tranquil jewel]

i wrote my b wrong

oops

i wrong exists for x

and all for y

LOL

[soft thorn]

Nice

[tranquil jewel]

Okay so its negation on (b) is true

[soft thorn]

Yes

Negation flips truth values

[tranquil jewel]

ima try this one next one sec

also going back to 4(d) from yesterday can't we just use x = 0 as an example

[soft thorn]

Probably lol

[tranquil jewel]

alr

How do I begin proving that?

[soft thorn]

There's a neat factoring trick

[tranquil jewel]

So factor it all the way to x(x-1)(x+1) ?

[soft thorn]

Yes

[tranquil jewel]

Hm

What should I attempt to do from there?

[soft thorn]

Well

What do you notice about the 3 factors?

[tranquil jewel]

Uh

does it have to do with factorial?

[soft thorn]

They're 3 consecutive integers are they not?

[tranquil jewel]

Yea

[soft thorn]

So 1 has to be divisible by 2

And another has to be divisible by 3

Ok, the divisible by 2 part is not important

But the divisible by 3 part is very important

[tranquil jewel]

thinking

Still kinda lost, I get if I divide any 3 consecutive integers by 3 it will be a whole number but like

How do I prove that

[soft thorn]

Personally I think it's sufficient proof

But worst case

Hmm

[tranquil jewel]

Like

uh

[soft thorn]

Follow the generic method to prove divisibility

[tranquil jewel]

what method of proof

would this be as

We only know like 4

[soft thorn]

Induction maybe

[tranquil jewel]

Direct Proof, Proof by cases, Proof by the conterpositive

we haven't done induction proof

actually literally made us write "not seen this till later in course" LOL

It can't be a direct proof right

[tranquil jewel]

Where should I start on this

[soft thorn]

What's the definition of odd?

[tranquil jewel]

any number that cant be divided by exactly 2

[soft thorn]

Hmm

Sure

[analog dagger]

eh

[soft thorn]

But

There's a more workable definition

What's the form of an odd number?

[tranquil jewel]

Uh

[loud basalt]

if i have any integer

[sleek swallow]

In an iff, you have to prove both directions

So you’re starting with the forward direction first?

[loud basalt]

how can i create an odd number from said integer

[tranquil jewel]

like 2x + 1?

[soft thorn]

I'm doing backwards first

[loud basalt]

yes!

the form of an odd number is typically 2k+1

[soft thorn]

I probably wouldn't do direct proof for the forwards direction

[loud basalt]

lemme think for a second

[soft thorn]

I mean

I know how I would approach the forwards direction

[loud basalt]

well i mean

wdym forward direction

from xy to x, y

[soft thorn]

Yeah

[loud basalt]

thats easy

theres only 3 cases

and prove only 1 of those cases

results in an odd number

aka

an even times odd

is always even

even times even is always even

so only an odd * odd can result in an odd number

@soft thorn

[soft thorn]

That's true

[tranquil jewel]

How do I prove that tho multiply two odd numbers i.e (2k+1)(2k+1)?

[soft thorn]

Expand it

[loud basalt]

use different variable

[soft thorn]

Refactor it

[loud basalt]

(2a+1)(2b+1)

=

[tranquil jewel]

so 4ab + 2a + 2b + 1

[loud basalt]

no?

[tranquil jewel]

uh

[soft thorn]

Isn't it?

[tranquil jewel]

wat

you said expand "(2a+1)(2b+1)" right

[loud basalt]

wait

im dumb

i was thinkin of something else

[soft thorn]

You know an odd number is of the form 2k + 1 for some integer k

[loud basalt]

ya

[soft thorn]

Can you rewrite your result in this form?

[tranquil jewel]

so factor the thing I just expanded?

[soft thorn]

Yes

[loud basalt]

but factor it

such that

u are left with something of form

2(x)+1

[tranquil jewel]

alr one sec

2a(2b+1) ?

[loud basalt]

uhh

[tranquil jewel]

I did grouping

[loud basalt]

no?

[tranquil jewel]

uh

[loud basalt]

unless ur talking just bout

the part excluding 1

2a(2b+1) +1 =(2a+1)(2b+1)

u forgot the +1

[tranquil jewel]

Well no

[loud basalt]

no?

[tranquil jewel]

cause I got (2a)(2b+1)

[loud basalt]

uhh

[tranquil jewel]

ohh

[ivory badge]

That’s wrong tho

[tranquil jewel]

i forgot the 1

[loud basalt]

wait

[tranquil jewel]

(2a+1)(2b+1)

isn't that back

[loud basalt]

why factor it like that

[tranquil jewel]

where i started tho

[loud basalt]

..

no

listen

do this

[ivory badge]

They want it to look like 2k+1

[loud basalt]

2x+1 = 4ab+2b+2a+1

ok

now how do we find x

2x=4ab+2b+2a

[tranquil jewel]

we move the 1

[loud basalt]

x=2ab+b+a

[tranquil jewel]

so we're forcing it to equal an odd number

[loud basalt]

yes

[soft thorn]

It is odd

We just making it more clear that it's odd

[tranquil jewel]

Is that it tho?

[loud basalt]

yes

[tranquil jewel]

so I'm just wondering we proved that its odd if its a odd multiplied by an odd but we don't need to prove the other things false?

i.e the even x odd even x even

[loud basalt]

well

those are trivial

and even number is of form (2k)

2a*(2b+1) =

2*(2ab+a)

for even times even we have

2a*2b

=

2(2ab)

[tranquil jewel]

ah

[soft thorn]

I think there's a bit of elegance to proof by contrapositive here

But that's unnecessary

[tranquil jewel]

sounds like an issue for another day one left

So for 9a its false right

if I use like x = 7 it doesn't work

[ivory badge]

Well, show 7 is a counter example

Going fully through the steps justifying it is one might be a good idea

[tranquil jewel]

Like you mean putting 7 in

and solving it all the way

[ivory badge]

Yes

Show it’s a counterexample

[tranquil jewel]

Yee did it all the way in my workings

[ivory badge]

So, does 4 | 0?

Just wondering for how your course handles that

[tranquil jewel]

would 4 | 0 be true is what ur asking right?

[ivory badge]

Ye

Also good to justify your steps, esp when starting out

[tranquil jewel]

this was the definition given so I'm not quite sure

[ivory badge]

Don’t wanna accidentally make a mistake like misreading 3 as 2 or smth

[tranquil jewel]

Wym justify my steps?

[ivory badge]

Also yeah that would give you 4|0, just asking as a sanity check for myself, dont mind me

Should be obvious this holds, q isn’t nonzero

I’m just stupid and making sure I’m not too rarted

[tranquil jewel]

LOL

How would I write the negation of it

for (b)

[ivory badge]

@tranquil jewel I’m saying it’s good you write out the steps you take so you have a proof that it’s a counter example

Also, how do you think?

Clearly the negation will disagree with the original

[tranquil jewel]

I was gonna switch the "All" to "exists" but I'm not sure how to deal with the x is odd, would just putting a negation sign infront of that suffice?

[ivory badge]

Well

The x odd part isn’t the proposition

The proposition is x odd -> 4|expression

The arrow is part of it

[tranquil jewel]

so I can't treat it separate

[ivory badge]

Here’s a hint, it’s a statement you just showed was true

I.e. shown there’s a counterexample

[tranquil jewel]

kinda lost

[ivory badge]

So

You have something which is odd but 4 does not divide the expression

[tranquil jewel]

Hm

So I can keep the x is odd

[ivory badge]

Yes

[tranquil jewel]

so do I change the implies to an "and"

and keep everything else the same

or is there more things to do with the negation on the last part, I'm not really sure how to deal with the 4 | (7x-x^3)

[ivory badge]

You do change it to an and, but you want to negate that expression on the right

@tranquil jewel

[fresh flame]

Can someone explain to me how we can reach the conclusion ∃x R(x) given these premises: ∀x (∃y P(x, y) →¬Q(x)), ∀x (¬R(x) → (Q(x) ∨ ¬P(x, x)), and ∃x P(x, x)?

[tranquil jewel]

@ivory badge How do I negate that expression tho is what I'm wondering

[ivory badge]

What would you say to negate “4 divides Y”?

[tranquil jewel]

4 Does not divide y?

[ivory badge]

Yes

[tranquil jewel]

so would I just put a cross through the line or like how would I write it

[ivory badge]

Ye

Or with words ofc

[mint horizon]

hi! uh.... can i get help?

[echo saddle]

@mint horizon https://sol.gfxile.net/dontask.html

[mint horizon]

i'm always going to ask first

[echo saddle]

There's no point in asking to ask, trust me, just ask. You're less likely to get your question answered.

[mint horizon]

eh still.

[echo saddle]

In fact it can be rude.

[mint horizon]

but i need help proving that ) ∃x∀yP(x, y) and ∃y∀xP(x, y) aren't logically equivalent using a counterexample and the limited domain of {-1,0,1}

help.

idk. look on the internet for what \ means in discrete mathematics

do you know anything abotu mine?

argh

yeah the 'uh' gave that away.

first

i just need some clarification

it's not hard i just need someone to clarify some shit for me.

[mint horizon]

how do i take the converse of ∀?

seriously anyone

[stray reef]

,,, you don't?

[mint horizon]

okay. they didn't cover that in my class

thank you though

[weary tiger]

Hey folks, I'm having a hard time describing what combinatorial proofs are. I've looked at many examples and I can somewhat understand what it's use for base from those but I can't really put it in a nice description. Here's what I have so far with a definition though:

Combinatorial Proofs: Is a way to prove an equality problem by finding two ways to answer the same question.

Would that be right? If not, what would be a good and objective way of describing this topic?

[stray reef]

too vague

a combinatorial proof is a way to prove a certain equality by counting the same collection of things in two different ways each of which leads to one of the sides of the equality being proved

[weary tiger]

Perfect. Thank you very much!!!

[tranquil jewel]

How do I prove this by cases?

[stray reef]

find a suitable case breakdown

[tranquil jewel]

I’m kinda confused on where to go, like I get it’s gonna be something along the lines of x(x-1)(x+1) which is 3 consecutive integers but like, I’m don’t really get how to use the cases to prove it

[stray reef]

why not split this into cases based on the remainder of x modulo 3?

i.e. x can be written in exactly one of the following forms: 3k, 3k+1, 3k+2

[tranquil jewel]

Not really following

Why are we using 3k 3k+1 and 3k+2

[stray reef]

your cases are

• x is a multiple of 3
• x is 1 above a multiple of 3
• x is 2 above a multiple of 3

[tranquil jewel]

Correct

But like where do I go from there, with each individual case

[stray reef]

x is a multiple of 3 iff x = 3k for some integer k by definition

similarly for the other cases

[tranquil jewel]

so since it’s a multiple that proves the x = 3k case then for some integer k

[stray reef]

write the proof out

[tranquil jewel]

I’m confused on how to write it though, do you just mean write out the statement explaining thar

[stray reef]

i feel like you're kind of overthinking it here

[tranquil jewel]

I am 😂

I understand what you’re saying but like I dunno how to like write it or am I just making it complicated

[warm coral]

so i think i have an impossible question on my discrete math assignment

for n > 0: prove my mathematical induction that there are at most 2^n nodes at level n of a binary tree

well, i can prove very easy if n >= 0, the base case of n = 0, 2^0 = 1 node, then i can easily prove that for n > 0, there are 2^n - 1 nodes

am i correct?

[faint narwhal]

You don't understand what level means

[warm coral]

alright

what am i missing here, i've never learned about binary trees so im new to this

[faint narwhal]

I'm not sure why you think it's impossible if you've done it

You're right in what you said actually

I mean, you didn't really give a proof but

[warm coral]

i meant, we have to prove for n > 0

so n = 0 isnt allowed

which would be the case that would satisfy 2^n

[faint narwhal]

I'm not sure what your point is

Just start your base case at n= 1 then

[warm coral]

so at level 1, 2 ^1 = 2 right

so basically the root

is level 1

?

[faint narwhal]

No

[warm coral]

explain? i am confused here

so at level 1, this is referring to the amount of nodes connected to each node of the preceding level?

[obtuse lance]

no if you prove it for n>=0 then you just proved something more general than n>0

it's still valid you just proved something that's valid for more than you were asked for, which is fine

[warm coral]

It’s more like I thought only at level 0, it was 2^0 = 1

= 2^n

And the rest is 2^n - 1

[faint narwhal]

How many nodes do you have on level 1

[warm coral]

4?

Sry

[faint narwhal]

What four nodes do you have

[warm coral]

level 0, level 1, level 2, level 3? ive never learned about binary nodes so i seriously am vexed, bear with me here

wait, hmmmmmm i think something is clicking?

so since we dont get access to level 0

as in

n cannot be 0, the root is actually n = 1

and all i have to do is prove that for all levels, there are 2^n nodes

[obtuse lance]

no you're thinking about the whole tree at once or something

https://prnt.sc/qv8tkr

each level is only what's in each box like they're labeled here

[warm coral]

yep

[obtuse lance]

How many nodes do you have on level 1

[warm coral]

2

level 2: 4

[obtuse lance]

good

[warm coral]

level 4: 8

[obtuse lance]

earlier you answered that by saying there were 4 on level 1

[warm coral]

so i can conjecture that its always 2^n for k > 0 eh??