discrete-math

[feral osprey]

I'm actually trying to see how I prove that G is cyclic

I was thinking it may be a proof if |G| is prime

[unreal stump]

You need Lagrange

[feral osprey]

[A:B][B]=A if B<A

[weary tiger]

have you seen lagrange thm?

ye

[feral osprey]

Yeah

I'm trying to implement it

[weary tiger]

stated differently, order of a subgroup divides order of the group

[feral osprey]

If B is a subgroup of A than A is divisible by B without remainder

[unreal stump]

So ,if g is not Id=e,<g> has atleast one more Element compared to {e}

And |<g>| divides p

[feral osprey]

|<g>| is the cyclic group of made from g?

[weary tiger]

<g> is

[unreal stump]

|<g>| is order of the cyclic group

[feral osprey]

right, my apologies

huh

[feral osprey]

I see, can you give an example?

[unreal stump]

Take (Z_7,+)

Take g=2

[feral osprey]

Thanks @unreal stump

[urban saddle]

How can I find -24 in Z5?

[pale epoch]

what's Z5?

[unreal stump]

I think they mean Z/5

[pale epoch]

ok what do they mean by find then

[urban saddle]

the equivalent of -24 in that set

[pale epoch]

how did you define Z5

[shell flicker]

Any good recommendations for online lectures that I can watch? That teaches from lesson 1 ?

[vital dew]

Speedrow

[errant bear]

hs algebra moment

[warm wren]

@marsh shuttle be quiet pleas!!!

@marsh shuttle stop smacking your lips and eat sensibly

[weary tiger]

LMAO

[warm wren]

every american says that damn word no wonder all the same shit

[weary tiger]

??????

I am not american

[gritty crescent]

????

Why such an absurd message in this channel?

[olive hamlet]

i believe both were in vc at this time, very wierd

[gritty crescent]

Yeah, it's a bit confusing why they'd respond in this channel lol.

[warm wren]

What is?

[gritty crescent]

Why are you posting random messages in #discrete-math ?

If you wish to text while someone is in VC, there's #mathematics-voice and #504761504571326464

[errant bear]

be quiet please!!!

[civic horizon]

pleas*

[errant bear]

stop harassing me. thanks.

[last timber]

@errant bear stop harassing others that they harass you

thanks

[errant bear]

please stop trolling me. this is a place of upmost professionalism and academic sincerity. thanks

[last timber]

@errant bear please stop harassing me that i am trolling you

i am trying to be polite and kind to my presumable fellow human being

[errant bear]

i have already reported you to the moderation of this establishment.

[last timber]

@errant bear but have you read #❓how-to-get-help

[errant bear]

no. i cannot read.

[feral osprey]

How do you multiply Permutation?

or multiply a Permutation by another Permutation?

[pale epoch]

most likely function composition

[cerulean wind]

you could represent them as matrices

[feral osprey]

How's that done?

let's say I've got circle permutations
(1,2,3,4)(5,6,7,8)

[cerulean wind]

ok. and you want to compose them?

[feral osprey]

yeah. I want to mutiply them as seperate permutations

But I don't even know what it means in this regard

[cerulean wind]

okay. since they are disjoint permutations, then you can just multiply them normally. so 1->2->3->4->1 and 5->6->7->8->5

[feral osprey]

right

So what does it mean to multiply?

[cerulean wind]

it would help if you drew out some functions. for example, the permutation (5 6 7 8) represents the function
1->1
2->2
3->3
4->4
5->6
6->7
7->8
8->5

where just the last four elements got cycled

[feral osprey]

1->2
2->3
3->4
4->1

Both are cycled

[cerulean wind]

right. thats what it means to multiply them in a sense. you get a new function which cycles the top four elements and the bottom four elements separately

[feral osprey]

Really, that's it?

[cerulean wind]

yes. its that simple in this case

[feral osprey]

I see thanks

[cerulean wind]

be careful tho, because if you have something like (123)(34)(28) then you need to think a little bit more about what happens when you multiply them

where the permutations arent disjoint

[feral osprey]

what do you mean?

[cerulean wind]

the function composition (123)(34) has three in both of them. this means the cycles will kind of overlap

[feral osprey]

So what i done in this case?

[cerulean wind]

you have to keep track of where the three and the four get moved. draw out the functions

[feral osprey]

1->2
2->3
3->1

3->4
4->3

Seems more complicated

[cerulean wind]

yes but you need to draw them like this:
1->1
2->2

[feral osprey]

Right, but why?

[cerulean wind]

im not done lol pressed enter to fast

[feral osprey]

srry

[feral osprey]

@cerulean wind You still there?

[cerulean wind]

yea sry. my internet went out

[feral osprey]

Hope all's well

[cerulean wind]

yes it is thanks

ok, so i was saying you need to write them like this:
1 -> 1 -> 2
2 -> 2 -> 4
3 -> 4 -> 1
4 -> 3 -> 3
note that we do (3 4) first then (1 2 3)
so that the composition (1 2 3)(3 4) = (1 2 4 3)

[feral osprey]

I see thanks

Wait

I don't understand the 3rd line

[cerulean wind]

where 3 -> 4 -> 1?

[feral osprey]

yeah

I see,

Than why is the result ...4->2->1?

[cerulean wind]

i think i messed up hold on

no i didnt.

i always have to think about these

[cerulean wind]

in case you didn't see, the result now is the correct result

[feral osprey]

I didn't. Thanks

[manic dome]

I need some help I'm stuck on this question 2,a

these are my steps so far

what ca I do next to help prove this is or isn't an interval

[cerulean wind]

what happens if b is strictly less than c?

and you try to intersect [a,b] and [c,d]?

[manic dome]

Wouldn't it just be a null set then

[cerulean wind]

yes. is that an interval?

[manic dome]

yeah thanks

[cerulean wind]

now what about it you take unions?

same set up

@manic dome

[manic dome]

That one I'm confused how I could prove/disprove it

I get the setup

[cerulean wind]

what’s ur definition of an interval?

[cerulean wind]

ok great

so look at numbers between b and c

[manic dome]

but b and c aren't defined to be any number tho

[cerulean wind]

what about (b+c)/2 tho

then b<(b+c)/2<c if b<c

you have to provide a counter example. you can let a, b, c, d be arbitrary real numbers with a<b<c<d

[manic dome]

gotcha I'll try that

thanks for the help

[cerulean wind]

np

[feral osprey]

if o(a) = 14
what would o(a^100)=?

[loud copper]

what is o ?

[feral osprey]

o(a) is the smallest interger in which a^o(a)=id

[light ginkgo]

R u talking ab groups?

[tardy mica]

Hey anyone can help me with xor operation

[manic dome]

I need help on this question 4,b

[errant bear]

what do you think

[manic dome]

I'm not sure, I get it's going from cartersian to a real number but how exactly can I prove it's a function or not

[errant bear]

does it seem like one?

[manic dome]

yeah it does

these are the other 2 functions

and I said that they were functions

like all 4 of them are functions like that doesn't make sense to me I feel as if one isn't a function

[errant bear]

you said a was a function?

[manic dome]

yeah it is

cause none of the pairs repeat

[errant bear]

but what is the actua function

all i see are two sets

[light ginkgo]

the function is S @errant bear

or the set they need to check whether it is a function

[errant bear]

s is literally a set

pls

[light ginkgo]

a function f:A->B is a subset of the cartesian product AXB with some other properties

a function is literally a set

[errant bear]

ok

ur doing this

on purpose

gn

[light ginkgo]

wtf are you talking about

[errant bear]

ok

[weary tiger]

Hello 👋 every one

f(n) is a function such that it outputs the frequency of the digit 0 in the range of integers from 1 to n
Can we generalise a closed form for f(n)
I have noticed that for an k digit number

[vital dew]

Pucci

[weary tiger]

Not sure of the generalisation tho

Also I tried finding a recursion....but failed ...

Any advices suggestions criticism are welcome

[weary tiger]

Minor corrections it should be k+1 digit number and 99999... k+1 times

[tardy remnant]

can someone tell me what are the conditions of a degree array of a multigraph?

[vital dew]

Alek

[lament zenith]

I had a quick question if someone can help me out

I'm covering graph theory and I'm come across a walk with a single vertex

Would I consider this a closed walk?

Of length 0 right

And it wouldn't have any properties, like it cannot be a circuit

Since the edge occurs more than once in itself?

[obtuse lance]

I'd have to see the exact definition, it's too much of a corner case

then just follow the definition precisely

[lament zenith]

Thats really just it

By definition it says this

[obtuse lance]

first vertex is A and last vertex is A, so they are the same and it's a closed walk

[lament zenith]

Yeah

ok

[obtuse lance]

yup

[lament zenith]

But wait is there a clear differnece

between

<a> and <a, a>

They share the same properties, but the walk length is now 1 right?

[obtuse lance]

is there an edge between a and a

[lament zenith]

ahh no, just thinking like a general self-loop

[obtuse lance]

yeah, the difference is one is going through a self loop and the other isn't

[lament zenith]

Hmm interesting

so <a> would be no self loop

Since there is no edge exists

that loops into itself, therefore it remains still in its walk, hmm ok

Well thank you for helping out

[obtuse lance]

yeah you're welcome

[lament zenith]

Ah one more thing, sorry if I'm reentering back to the same topic but would <a> be also a circuit? Since a circuit is defined as a closed walk in which no edges occur more than once

And since that is the definition, a walk of <a> would also be a circuit, since there is no self-loop / edge going back to that verticie*

And finally it wouldn't be a cycle since a circuit must be of length 1 at least, by definition

[obtuse lance]

yeah definitely, it's vacuously true that no edge occurs more than once so you're good

[lament zenith]

Ah ok ty

[obtuse lance]

cool cool

[austere swan]

@obtuse lance I don't undirected graphs allow for edges from a vertex to itself

Simply by definition, an edge is a member of the powerset of V of size 2, and in the usual definitions you are talking about regular sets, not multisets, so {a,a}={a}

[sour arrow]

So you also don't allow for multiple edges between any two verticies?

[austere swan]

In an undirected graph if you had one edge going one way and another going the other way they would coincide

{u,v}={v,u}

In a directed graph it's possible to have both

Since the notion of an unordered pair is replaced with an ordered pair

I'm still not sure if regular definitions allow for an edge from a vertex to itself since (a,a)=(a)

In a multigraph you can also have multiple edges between 2 vertices

And loops

But a regular graph by most definitions cannot

[lament zenith]

Is there any way to make this more concise

The top is the question with its solution, mine is below

If I'm making a general case for every open walk that we know exists and has some way of getting from v to w

we can conclude that a path property exists of those vertices as we remove each duplication of edges and vertices being used

How can we make that statement ^ which I mentioned above, in a more formal math notation

[smoky needle]

hello , i am sorry for asking this easy question but i just don't get it

what are the numbers for?

not in circle but in paths

[pale epoch]

assigned weights

[smoky needle]

are we assigned them ?

[pale epoch]

this specific picture is probably just for illustration

in general they are arbitrary

[weary tiger]

A directed cycle is a strongly connected digraph, am I right?

[smoky needle]

thank you

[weary tiger]

Between any two nodes u and v, there's a walk connecting them in both directions

[pale epoch]

sure, just go around the cycle until you arrive wherever

[weary tiger]

When doing some combinatorial optimisation problems, I found out I'm often confused about the notion of "distance". When working in a network (that is, a digraph with a weight function), the distance from node u to v is just the smallest weight of a walk from u to v where the weight of a walk is just the sum of the weights of its arcs. If no negative cycle exists, then the shortest walk coincides with shortest path, where shortest path denotes the path of least weight. When working in a graph, how does one define the distance (usually)? In the problem I was working with, the author of the book specifies that the distance is the length of the shortest walk. I get that "length" is the number of edges, but what is meant by "shortest walk" ?

In the case where we have no weights, "shortest" would then refer to the walk that uses the least number of edges, am I correct in my reasoning?

[smoky needle]

I couldn't see the simple circuit in here but book says there is one

what is the path?

[vital dew]

WhiteKnife

[deft dock]

hello; im completely stuck on how to do this

[haughty garden]

Read equals as “congruent to”
p -> q V r = (~p V q) V r
= ~(p ^ ~q) V r
= (p ^ ~q) -> r

[deft dock]

is ^ = "and"?

[haughty garden]

Yeah

The question is just written a bit ambiguously imo

I originally thought the right side was p ^ (~q -> r)

[deft dock]

interesting; this is my first hw assignment and i have no clue what im doing lol

[haughty garden]

Basically you just want to use the logical equivalence laws as well as the definition of implication

[deft dock]

im confident in the last three, but the first one i dont really know, because the videos ive watched about conditional statements, none of them include negtation, only the last three

[deft dock]

ah ive heard of those; ill look at the reference sheet for the specific names

[haughty garden]

So P -> Q is logically equivalent to (not P or Q). So the negation of P -> Q is the negation of (not P or Q)

In other words, the negation is P and not Q

Does that help with the negation row?

[deft dock]

ohhhhhhh okay okay

but i cant find "those" laws anywhere

the ones that involve if then statements

the only reference sheet i have is this:

[haughty garden]

If P, then Q is the same as P -> Q

[deft dock]

mhm

[haughty garden]

So here P is “you are a computer science major” and Q is “you can take M2211 and M2212”

[deft dock]

i dont see the "if, then" statement logical equivalences

[deft dock]

understood

[haughty garden]

Then the negation is (P and not Q)

So what would that be

It would be “you are a computer science major AND you cannot take M2211 and M2212”

[deft dock]

yup that makes sense

but where can i find logical equivalences (like a reference sheet above) for "if, then" statements?

[haughty garden]

We were taught it as an equivalent definition of implication

It’s not exactly a “law”

[deft dock]

no no i get all of that

but like

is there like a formula sheet with all of that written?

[haughty garden]

I don’t think I have one that also included the implication laws

[deft dock]

ah okay

[haughty garden]

But if you’re happy with the equivalent definition, you can derive them

For example not (P -> Q) can be derived using the definition of implication and the laws you’re already provided

Same as things like (not P -> Q) and any of the variations

[deft dock]

hmm

okay i think i see

also is "=" the same as the triple lines?

[haughty garden]

Not exactly but I didn’t have the congruent symbol on my phone so I just used it to mean congruent to

Usually you’d have triple lines when writing laws of logical equivalence

[lament zenith]

So ya asking whether a path exists or a circuit?

those are two completely different things

since one is a open walk and a closed walk

[hybrid oxide]

equals and triple-lined equals aren't the same. for the intents and purposes of formal logic, think of = as "these are syntactically the same" (i.e. $p \lor q = p \lor q$) and think of $\equiv$ as "these look different but are logically equivalent" (i.e. $p \rightarrow q \equiv\lnot p \lor q$)

[vital dew]

mmmbruh

[deft dock]

ohhhhhhhhhhhhhhhh that makes a lot of sense

thanks man

ight so what im getting at

is like

1 = 1

but

1 ≡ 2-1

?

[hybrid oxide]

i would be careful cross applying the purpose of equals to things outside of formal logic because i don't think that's correct

it's more a distinction of notation within this domain of math rather than anything particularly concrete

[deft dock]

ah okay thank you

i was more using it to show concept rather than communicate

[hybrid oxide]

yeah, just think of it more of a notational thing and just understand that using ≡ is meant to show equivalence specifically for propositional logic

and you'll be fine

[lament zenith]

Anyone got any good resource or questions they have for beginners on graph theory proofs?

I'm trying to cover / understand: circuits, walks, trials, paths and cycles, to graph connectivity

[deft dock]

could someone explain how this went from p ^ ~ q --> r to (~p V q) V r

[lament zenith]

Apply de morg law on the lhs

p^~q

wait one sec

[deft dock]

i was thinking that

but then where would that ~ we just factored out go

[lament zenith]

yeah so it goes like this

p ^ ~ q --> r

then

conditional identitiy

~(p^~q)vr

apply demorgan

to get

~pVqVr

since this ~(

applies the negation to each proposition

Either way its not that hard to think about, just write each step down

[deft dock]

wait hold on what

[lament zenith]

here

[deft dock]

whats the conditional identity

and how did we just ~

outside of (

[deft dock]

oh this

OHHHHHHHHHHH

wait

[lament zenith]

Hmm, are you sure this ain't highschool maths ya doing. I swear I've seen that textbook page before

[deft dock]

so we're treating (p ^ ~q) as an entire entity?

[lament zenith]

yes

[deft dock]

no im dualling at a local college

omg bro that makes so much sense

[lament zenith]

Either way, yes you treat it as one

Since you can apply that same fact

[deft dock]

and ~p V q = p --> q rihgt?

so this?

[lament zenith]

yes

[deft dock]

https://tenor.com/view/mind-blown-amazed-explosion-space-omg-gif-10279314

[lament zenith]

not sure what you are saying there

just apply the law on the rhs

[lament zenith]

to show what you applied

[deft dock]

ight ight thanks a lot man

[lament zenith]

Thats not what you asked right

you asked to to show this proof

[deft dock]

well no i get how to do it now

[deft dock]

the other guy did it for me, i just didnt get how he got taht certain step

like that random ~

[lament zenith]

Hmm

Well at least you got there

[deft dock]

and what would i call that to justify it?

just "def. of conditional statement"?

[lament zenith]

yeah

I need to see your steps, since I'm lost at what point you're at

Of trying to show this is a logical equivalence

[deft dock]

the second step here is also "def of conditional statement" right?

cuz the arrow becomes V ?

[deft dock]

okay gimme a sec

[lament zenith]

it applies the negation and makes the clause an AND

From original proposition made

[lament zenith]

This

it will take 4 steps

to prove its logical equivalence

[deft dock]

okay this is what i was saying

/trying to understand

this is right right?

[deft dock]

oh no.

i only got 3

what did i miss?

or do i just seperate the first step into 2?

[lament zenith]

Do you understand logical equivalence

[deft dock]

barely

[lament zenith]

its prove the LHS is equal to the RHS

[deft dock]

oh.

[lament zenith]

I'd suggest read over your material please and attempt it again

[deft dock]

wait so start on the left then?

[deft dock]

bro i have no clue because my teacher doesnt have any videos on proofs

we're just given a bunch of formulas

[lament zenith]

I'm not gonna provide anymore help since I'm guessing this is assessed. And I can't really help out anymore

I'll put it simply

Make the LHS equation into the RHS

Using the current laws of propositional logic

[deft dock]

yeah true understood

lemme do it one more time

[lament zenith]

The material should explain it fairly well and there is A LOT of videos on this

[deft dock]

wait but the other guy worked on the rhs?

[lament zenith]

You can work on the RHS to achieve the LHS

Either side works

[deft dock]

oh okay but u just said i have to do the lhs?

[lament zenith]

You can start from the LHS to see if you can make that statement from the LHS can be made using the laws of propositional logic to make the RHS equation

Therefore this can be used vice versa, we can get the equation on the RHS and try to prove that its equal to the LHS

[deft dock]

anyone know how u go from the first thing to the second?

[haughty garden]

Reverse distributive law

p V (q ^ r) is equivalent to (p V q) ^ (p V r)

So treat p as ~q, q as p and r as ~p, we get the result

That is, ~q V (p ^ ~p) is equivalent to (~q V p) ^ (~q V ~p) which is the proposition in the first line

And because they are equivalent propositions, we simplify the first prop into the second

[deft dock]

[proven notch]

Can anyone help me with

[obtuse lance]

maybe try to set up a recurrence relation

[light radish]

is my "solution" what they mean with the underlined part?

[stray reef]

yes, but your naming scheme is bad

[light radish]

could you explain why? @stray reef

or suggest a better one

[stray reef]

well for starters

what you named "B" has to do with the box called A, and what you named "C" has to do with the box called B... it's confusing

and also, "A is blue" is equivalent to "A is not red" so why not just have A = "A is red", B = "B is red", etc.?

only 5 propositional variables instead of 10, too

[light radish]

ah yeah

i see what you mean

thank you!

[haughty garden]

If you want to be pedantic, “A is not red” and “A is blue” can be made as syntactic distinctions — that is to say, they are not syntactically equivalent. Instead we can impose it as a semantic equivalence. This is just an alternative approach

But if you don’t care about this distinction, then saying that “A is blue” and “A is not red” can be syntactically equivalent in your model

[proven notch]

But how?

[light radish]

I'm stuck on this one, could anyone possibly help me out?

[smoky needle]

Hi

Is this the right solution?

[obtuse lance]

,rotate

[obtuse lance]

looks perfect

[smoky needle]

Thank youuu @obtuse lance

[obtuse lance]

you're welcome

[smoky needle]

what can i write for the accepting set

i mean i figured it accepts ax*a or bx*b

but how can i write it as a set?

@obtuse lance my hero ? xD

omg i misunderstood the question

okay i solved it

[radiant oasis]

Hi, where can I ask a graph theoretic question?

[radiant oasis]

I'll give it a try anyway:
Let K_n be a complete graph on n vertices. Is there a formula to calculate the number of paths of length k from v_1 (some vertex) to itself? Note that one can go over same vertices more than once (e.g for a path of length 4, the path v_1->v_2->v_1->v_2 is valid).

[stray reef]

isn't this just calculating the diagonal entries of A^n, where A is the adjacency matrix of K_n?

[light ginkgo]

@stray reef That gives you the number of walks not paths.

[stray reef]

the difference being what exactly?

[light ginkgo]

Of nvm i see they are using path to mean walk.

Walk can repeat vertices and edges

Path cannot repeat either

[radiant oasis]

@light ginkgo Oh sorry, didn't pay attention 🙂

[stray reef]

anyway, the adjacency matrix of K_n is J - E, where J is the all 1s matrix and E is the identity

$J^k = n^{k-1} J$ for $k=1,2,\dots$

[vital dew]

Ann

[radiant oasis]

One can use binomial expansion , I guess

[stray reef]

that's what i'm going for

$(J-E)^n = (-1)^n E + \sum_{k=1}^n \binom{n}{k} (-1)^{n-k} J^k$

[vital dew]

Ann

[radiant oasis]

Didn't think of it that way.. so simple

So simple.. Thanks

[stray reef]

yw

[dire totem]

Where should I start off to learn discrete math?

[minor lake]

The way I did was in the following order

1. Boolean logic
2. Overview on functions
3. Naive set theory
4. Proofs
5. Combinatorics
6. Graph Theory
7. Recurrences
8. Number Theory

Unfortunately I don't really have any books since most of the content consisted of notes given by the teacher

[weary tiger]

I'm stuck at this question: prove or disprove that

$$29!\frac{n^{29}}{log(n)} = O(n^{12}+n^5log(n))$$

Any tips please

[vital dew]

Laïka

[weary tiger]

My guess is no

But how to disprove

[unreal stump]

Isn't RHS just O(n^12)?

Note log n = O(n)

[weary tiger]

Makes sense yeah

log(n) <= n for all n

So is it just enough to say that 29 is much bigger than 12 so the LHS is not equal O(n^12)

Oh

Is it equivalent to saying that $$29!n^{29} = O((n^{12} + n^5log(n))log(n)) = O(n^{13})$$

[vital dew]

Laïka

[pale epoch]

this big oh notatio is horrible

[sturdy dirge]

on a practice problem the answer is saying f(n) ∈ Θ(g(n)), where f(n) = log(n!) and g(n) = log(n^n), but I dont see how f(n) ∈ Ω(g(n)) because there is no constant that can be multiplied by g(n) such that f(n) will be >= as n approaches infinity

[pale epoch]

how did you define big oh

[weary tiger]

f(n) = O(g(n)) if there is a constant C and a rank N beyond which f(n) <= Cg(n)

[unreal stump]

Yea,via a sequence of abuses of notation yes

[sturdy dirge]

wouldnt this graph show that log(n!) is always <= log(n^n) as n approaches infinity which means f(n) is only an element of big oh

[pale epoch]

its just a graph

[stray reef]

"only" an element of O(g(n))?

just because f ≤ g doesn't mean f ∉ Θ(g)

you could have f ≥ 1/2 g or something

[pale epoch]

hint: $\log(n!) = \sum_{i=1}^n\log(i)$

[vital dew]

Lochverstärker

[sturdy dirge]

yeah but the growth of log(n^n) means it will eventually pass log(n!) even with a multiplier right?

[stray reef]

will it now?

[sturdy dirge]

I think n! will never pass n^n but I could be wrong

[pale epoch]

n^n does grow faster than n!

but that is not the question

[sturdy dirge]

so if it grows faster it would be impossible for log(n!) >= c * log(n^n), even if c is some super small fraction for all n values right

[pale epoch]

no

complexity is not closed under taking logs

n^100 grows faster than n

but taking logs changes that

[pale epoch]

consider this and notice that ||half the terms in the sum are greater than log(n/2)||

[sturdy dirge]

wait so would the log eventually level off and the multiplier would keep it below

[pale epoch]

also have you tried just multiplying any small number in front of your log(x^x) in desmos

that should convince you

[pale epoch]

i dont know what you mean by level off

[sturdy dirge]

desmos stops calculating them pretty early but I think I see it with wolfram

[tame arrow]

How many 10-bit strings with weight 7 start with 1001?

[tight lotus]

dunno what weight means

[errant bear]

find the number of 6 bit strings w weight 5

[stray reef]

most likely hamming weight, i.e. number of 1's

@tame arrow do you still need help with this?

[cursive crescent]

Well, since there are already two 1s in the beginning, the weight goes down to 5. So you need to find the number of ways one can arrange 6 digits with a weight of 5. This is just n C k or 6 C 5.

There are 6 strings with this property

[tight lotus]

and number of ways to put a single 0 into a string of six 1s

this is more confusing if I didn't write that very well

[cursive crescent]

111110, 111101, 111011, 110111, 101111, 011111. Just add 1001 behind these and you're done!

[past plaza]

Hey can anyone help with a definition of a path? I have a question that asks for paths of length 4 between 2 vertices. However, if vertices in a path are distinct, then how can you have a path of length 4 in a graph with only 3 vertices?

[hybrid oxide]

technically there are some versions of the path definition that specify that only simple paths require unique vertices. do you know for a fact that your given definition requires unique vertices?

[deft dock]

hmm for some reason she said it should be or? and i dont really get how

[pale epoch]

the negation of (P and Q) is (not P) or (not Q)

this is kind of a weird language issue tbh

logically speaking the original sentence says that if you are a computer science major you can take both(!) M 2211 and M 2212

so for example in the contrapositive it suffices that you are unable to take one of them to deduce that you are not a computer science major

(i just noticed this was asked some time ago but @deft dock )

[deft dock]

ah that makes sense

ig me thinking too technically kept me from seeing that

kind of a dumb question given that my teacher only provided videos in which she was very technical

but thank you

[kindred otter]

anyone know how to solve this?

[drifting sail]

I suppose a geometric sequence is defined as t_n=ar^n for some numbers a and r?

if so, then you have t_3=ar^3 and t_7=ar^7 for some a and r and you want to find the value of t_6=ar^6.

[kindred otter]

huh

we just started this unit recently and we're being given out homework to work on, i was wondering if by any chance you could solve it and show the steps and how what got to what

[drifting sail]

once you get to this it shouldn't be too hard, it's basic algebraic manipulations. For instance you can get r^4=(ar^7)/(ar^3) and r/a=(ar^7)/(ar^3)(ar^3), and since you know the values for t_3 and t_7 you can solve explicitly for r and a and then find t_6 that way.

[drifting sail]

I edited this a bit since I think the definition is that of a https://en.wikipedia.org/wiki/Geometric_progression

[obtuse lance]

looks like there's a cycle to me by following along the edges in the direction of the arrows

[lament zenith]

like

c, e, f, d?

[obtuse lance]

yeah

[lament zenith]

would it make it cyclic the whole graph

like it would be called a directed cyclic graph right?

[obtuse lance]

well, I guess it depends on what your definition of cyclic is

I'm not really concerned with the terminology personally so I don't know

to me it's a directed graph with at least one cycle

so I guess if being cyclic means it contains at least one cycle, then yeah

[fair cedar]

Existence of a cycle makes it cyclic

Not sure what you are saying here

[quartz badge]

Does anyone see how to get the bound?

[storm pollen]

Can someone help me understand this difference between 3 and 4?

[red nest]

I mean, imagine a class of 2 people where both people only know their own number, that satisfies 3, but not 4 (there is nobody whose number is known by the whole class).

[storm pollen]

Could anybody do a video call with me I have some questions that I just can’t explain through text

[light ginkgo]

You would show it is reflexive G~G by showing G is isomorphic to G. So just provide an explicit isomorphism.

I dont see a relation defined on the vertex set so I wouldnt say they all relate to themselves.

[light ginkgo]

To show a relation on a set A, ~, is reflexive you need to show for x in A, x ~ x. In your case A is the set of all graphs and ~ is G~H if and only if G is isomorphic to H. So to show ~ is reflexive you must show a graph G is isomorphic to itself. @coarse token

[light ginkgo]

Yea

[weary tiger]

i did this more generally as i think it holds for countable families of sigma-algebras, but my proof seemed too easy so im paranoid its wrong

[vital dew]

Carla_

[weary tiger]

<@&286206848099549185>

[manic dome]

Can somebody help me with this question

[last timber]

@manic dome formula for odd number gives a hint for bijection

[drowsy mantle]

Hint 2: you know the size of the set with all natural numbers.

[shell flicker]

any good sources to learn discrete math from 0?(preferably youtube, basically with videos doesn't have to be specifically youtube videos)I signed up for discrete math next semester and I want to start be forehead so I can be more prepared.

[gritty crescent]

Have you tried 'Mathematics for Computer Science' playlist by MIT OCW?

[shell flicker]

no, I will look it up now

@gritty crescent looks awesome, thank you.

[gritty crescent]

[cerulean wind]

a walk through combinatorics is a pretty good book imo

[shell flicker]

@cerulean wind do you recommand on reading it? did it help you to improve more then your lectures?

does it give a good fundamental ground for the information? whats unique about it if I may ask.

[cerulean wind]

yes i would recommend reading it. the book really reinforced my understanding of the lectures, since trying to understand many combinatorial arguments in the span of an hour and a half lecture can be difficult at times. it explains key concepts in clearly and in fairly good detail. in addition, the author provides concept checks intermittently throughout chapters along with ample question sets at the end of chapters. the first half covers just about all that an intro course would cover regarding enumerators combinatorics and the second half introduces graph theory and other more advanced topics. it was my first read through and i feel it offers good fundamental ground work for learning combinatorics.

[shell flicker]

@cerulean wind sounds like I was presented with a present, thank you I appropriate your help, and I will begin reading into soon!

[undone eagle]

Hello need verification as to whether my answers are correct. I have a lot of confusion regarding with each of their truth tables because there are some hypothesis which would return a true conclusion and there are some who would return as false in the same table. Clarifications are pretty much appreciated

[last timber]

@undone eagle why you think 1st is valid and second is invalid?

[undone eagle]

For number 2 i believe it is valid since it is part of the rule of inference which is modus tollens if i am not mistaken

for number 1 this is the truth table i made

but i am really not sure since row 3 shows that the first and second hypothesis results in f

so i am quite confused there

:/

[last timber]

@undone eagle consider that p->q is true whenever p is false

so value of q does not matter

[undone eagle]

Sorry it's hard for me to comprehend is my value for p->q wrong in the 1st row? since p is true yet it still returns as true

[last timber]

@undone eagle you cannot infer ~q from p->q and ~p

since F->q is true for all values of q

[undone eagle]

Owww yeah I get your point

[pallid lintel]

I don't really understand what this sentence means to 'nondeterministically' select the vertices/nodes to be numbers between 1 and m

does it just mean go through p1,p2,...,pm one by one assigning a random number between 1 and m to them?

if we did that, it would allow s and pt to be any of the vertices, allowing us to check every possible path in the graph to see if its hamiltonian or not?

I think that's what is going on here but i dont know

[candid chasm]

it says d in the answer sheet but its c isnt it?

im so confused

[pale epoch]

how is the multiplication defined

[candid chasm]

idk this is exactly how the question is i didt cut out any part

but if i remember it should be equal to c

but idk if im wrong or if the answer sheer is

[pale epoch]

it's impossible to answer if you don't know how the multiplication is defined

[stray reef]

@candid chasm have you ever worked with matrices and matrix multiplication before? Y/N

[candid chasm]

Yes but i dont really remember so im about to revise

cuz i confused it with the sets thing

[stray reef]

well you need to recall how matrix multiplication works

[candid chasm]

yah nvm it gotta be 27

i confused matrix multiplication with smth else

[light radish]

Hey, can anyone help me out with this? I managed to do every other exercise apart from this one and I have to submit it in a few hours

[feral osprey]

What does mean?

[light ginkgo]

In what context @feral osprey?

In algebra ik it was being a normal subgroup

[feral osprey]

Thanks

My apologies than. wrong channel

[light ginkgo]

Youre fine I was just saying thats the only context ive seen it in.

[cloud cargo]

why does this work?

the last line

ah i suppose the key is that each of the summands is less than $\frac{1}{d}$

[vital dew]

jabra

[cloud cargo]

thus if d * a, where a <= 1/d, then d*a <= 1

since there are d summands

[deft dock]

hello; i was wondering if this is correct?

the "or" by the D should be "and"

[deft dock]

<@&286206848099549185>

[iron marsh]

Looks good

[meager dew]

Struggling to understand this

[fossil torrent]

I'm still confused what does set division means. Like Z/2Z

[short juniper]

@meager dew Problem above require that for each problem you determine the resulting value for variable answer from the above set of statements.
Taking Q1. as an example, We have n=5 and outside = false.
Looking the above statements, we can determine that the variable ans will be "TRUE".

[fossil torrent]

Z/2Z is used for mod 2 arithmetic, but I don't understand why did we use that.

Later, I heard that multiples of phi is equidistributed on Z/Q

What does Z/Q mean?

[meager dew]

It's requiring code to answer it, but is there any code involved at all?

[errant bear]

Z/Q is clearly phi

[fossil torrent]

It's a syntax error: unexpected identifier answer at line 5

[short juniper]

At the second else in the statement/code, I think it can be taking as "If outside=True". The wording of the problem is somewhat unclear.@meager dew

[deft dock]

gracias

[iron marsh]

Yea, you are right. The syntax on this code is a bit poor

[deft dock]

hello, i was wondering if B and C are correct?

and im not sure where to start with A

im not sure if this is right

ohhh okay this makes sense

[vital dew]

dackid (jump king +)

[iron marsh]

This is the same thing except I have the real number symbol. That was my mistake.

[deft dock]

why do we not have to define x as part of the R?

towards the beginning

[iron marsh]

We do

Both x and y are in R

[deft dock]

ohhhhhhhhh x,y

okay okay

[iron marsh]

With this knowledge, try to redo B and A

[deft dock]

A i can just rewrite as a if then statement right

∀x, if P(x) then Q(x)

in this format?

[iron marsh]

Not really

[deft dock]

thats what my teacher gave me

[iron marsh]

I mean, you do need that statement, but it needs a bit of refining

I'll share my a) once you retry it

[deft dock]

okay gimme a second

[iron marsh]

Also, quick notation. x|y means x divides y

[deft dock]

ahhhhhhhh is that what is meant when it says x mod y or something

?

[iron marsh]

Mod is slightly different

[deft dock]

wait would this not be Q?

wait no nvm

[iron marsh]

No, because b specifically refers to the real numbers

[deft dock]

Q is rational numbers and R is real

yeah yeah

would it be inapprorpiate to say x or y =0?

or do we have to say x = 0 y =0?

[iron marsh]

If we say $x\equiv 3\mod y$, this essentially means that $\exists k\in \Z$ so that $x=ky+3$.

[vital dew]

dackid (jump king +)

[iron marsh]

In other words, it is 3 more than a multiple of y.

[iron marsh]

Since you are practicing, I recommend keeping it as is.

[deft dock]

okay

this is wrong isnt it

[iron marsh]

Here's how I would do it: [ \forall x\in \Z,(16|x \Rightarrow 8|x).]

[vital dew]

dackid (jump king +)

[deft dock]

oh i dont think i should use | because my prof hasnt exosed us to it

and i dont want her thinking i cheated ya know

[iron marsh]

Well, it's extremely common notation. I don't think she'll be bothered by it

[deft dock]

so this is the same as this right

just less wordy?

and more signs?

[iron marsh]

Yes

[deft dock]

ah it all makes sense

okay lemme change that / and then you can give it a final glance

[iron marsh]

Alrighty

[deft dock]

wait no

[iron marsh]

Don't forget to redo C

[deft dock]

that last 16 should be 8

[deft dock]

aw shoot i got C wrong too?

okay gimme another sec

[iron marsh]

And you do not need to say x|16 is in Z

That is what divides means

[deft dock]

oh we assume no remainders?

[iron marsh]

x divides 16 means there is some integer k so that x=16k

There is no remainder

[deft dock]

oh divisible means no remained anyways

[iron marsh]

Nope. Like I said, it's really nice notation

[deft dock]

[iron marsh]

To be fair, I never said the word divisible

[deft dock]

wait what did i mess up in C?

[iron marsh]

Yes. In fact your statement is saying the completely wrong thing. It is also false in its current form.

[deft dock]

[iron marsh]

What you said is for any x in Q, it's square root is also in Q

But we know that's false. Consider x=2

√2 is irrational, which means it is not in Q

[deft dock]

the aqrt of 2 is irrational...

yes yes

[iron marsh]

However, that wasn't what it was saying.

[deft dock]

wait so then its a

what is it called?

the reversed E

thing

[iron marsh]

What it said is for any x in Q, x^2 is in Q

[ \forall x\in \Q, x^2\in \Q.]

[deft dock]

ohhhhhhhhh

[vital dew]

dackid (jump king +)

[deft dock]

omg i read it wrong

it says square not square root

okay okay

[iron marsh]

It sure does

Now once you revise a), you should be good to go

[deft dock]

bam

could u check one last thing for me? its the weird negtation things for statements

[iron marsh]

Once you get rid of the second (in Z) you are good

It is unnecessary

Also, x|16 is not a number, so saying it's in Z is meaningless

[deft dock]

for the first one?

[iron marsh]

Yes.

x is a number, x|16 is a statement

[deft dock]

oh because we've defined x as part of that domain alr

gotcha

[iron marsh]

Yes, and the fact that x|16 is NOT a number.

[deft dock]

gotcha

okay what do you think of these?

c i put true

[iron marsh]

The converse in b) is good, but is it a true statement?

[deft dock]

i think so?

because every odd is a prime

and 2 is a prime

[iron marsh]

Is 25 a prime number?

[deft dock]

C should be good right?

because no such thing as even prime number?

except 2

[iron marsh]

Let $\mathcal{P}$ be the prime numbers. [ \forall x\in \mathcal{P},\forall a\in \N,(a|x \Leftrightarrow a=1 \text{ or } a=x).]

[iron marsh]

The negation is good, but is the claim true?

[vital dew]

dackid (jump king +)

[iron marsh]

This is what it means to be prime

If x is prime, it can only be divided by 1 and itself.

[deft dock]

right

[iron marsh]

But 15=5*3. So 5|15 and 3|15, so it is not prime

15 is odd and not prime, so the converse is false.

We also found a number that is not prime and odd, so the negation is also false (as it should be).

Also, note that when negating a statement $\neg(\forall x\in \Z)=\exists x\in \Z$.

[vital dew]

dackid (jump king +)

[iron marsh]

And exists turns into forall

[deft dock]

aw okay

[iron marsh]

Ah, your negation is wrong

[deft dock]

okay so B is false because one example is 25

[deft dock]

[iron marsh]

$\neg(A\Rightarrow B)=A\land \neg B$.

[errant bear]

"a sufficient condition for an integer to be divisible by 8 is that it be divisible by 16"

[vital dew]

dackid (jump king +)

[deft dock]

wait what are we talking about

[iron marsh]

This is the negation of an implication

The negation of A implies B is A and not B

[deft dock]

i thought it only wants inverse, contrapostiive, and the other thing

[iron marsh]

So there exists a real number p, so that p is prime and p is not odd and p=2

[iron marsh]

Pretty sure inverse is just negation here.

Never heard of an inverse statement

[deft dock]

hmm okay

[iron marsh]

And what you have shown so far looks like an attempt at negation

[deft dock]

i was just following this thing verbatim

[iron marsh]

Oh interesting.

Disregard then

[deft dock]

okay

but for A, that has to be true right?

[iron marsh]

Does the inverse have forall or exists in there?

[deft dock]

for all

[iron marsh]

The contrapositive is always true iff the original statement is

[deft dock]

good to know

[iron marsh]

It is a useful proof technique to instead prove the contrapositive.

So a) is right, I already showed why b) is false

[deft dock]

yup with 25

and C false with 15?

nvm yes

[iron marsh]

And the inverse is once again false because 15 is not prime but odd.

[deft dock]

okay this is a general question, but with that circuit thing, is that the least sloppiest way to write it?

[iron marsh]

Well we can try to find out

[vital dew]

dackid (jump king +)

[deft dock]

hold on gimme like 10 minutes i have one problem left and im working it

my assignemtns due in 6 minutes lol

[iron marsh]

Okay, this is gonna take a minute, so I'll just be writing about it for a minute

$\neg E=\neg ((A\land B)\lor \neg C),$ and this is equivalent to [ \neg(A\land B) \land C. ]
Finally, we have $\neg(A\land B)=\neg A \lor \neg B.$.

[vital dew]

dackid (jump king +)

[iron marsh]

With this we can combine it all together to get this statement:
[ ((\neg A \lor \neg B) \land C)\land \neg D. ]

[vital dew]

dackid (jump king +)

[deft dock]

one minute clutch

[iron marsh]

Nice!

[deft dock]

okay back to what we were saying

[deft dock]

okay demorgan makes sense but how did we get to the bottom part

[iron marsh]

That's also using demorgan's laws

[deft dock]

ik but where did the C go?

the ^ C

wait no

man my brain not working

i get it we still have the C

[iron marsh]

Oh, I was just working with one negation at a time.

[deft dock]

but you were just looking that one part

ya ya

[iron marsh]

Getting the messy stuff out of the way as we go.

[deft dock]

[deft dock]

okay so not much different

[iron marsh]

Lastly, since the and operation is associative, we have [(\neg A \lor \neg B) \land (C\land \neg D).]

[deft dock]

but still a few less brackets

[vital dew]

dackid (jump king +)

[iron marsh]

It does look nicer though

[deft dock]

indeed quite satisfactory

okay another question

the problem i was working on:

why would

in the boolean expression

would we not inclue

include

v (P ^ Q ^ R)?

because it is satisfactory

according to the table

[iron marsh]

Why exactly do we have a fourth variable

It says there are only 3 control panels

[deft dock]

i thought that was

like the

hold on

[iron marsh]

Oh, I get it

[deft dock]

i thought that was like the output or something

[iron marsh]

Yea, it is

[deft dock]

okay okay

[iron marsh]

The expression looks good

[deft dock]

yah but i was wondering why would we not have v (P ^ Q ^ R)?

because S = 1

for it

[iron marsh]

The triple AND is not necessary as $(P\land Q \land R)$ is included in $P\land Q$ or $P \land R$.

[vital dew]

dackid (jump king +)

[deft dock]

by logical equivalence?

or do we have to logically think it out

[iron marsh]

If both P and Q are true, the system will still turn on regardless of R's input

[deft dock]

ah so no point in specifying that all three are necessary?

[iron marsh]

Precisely

[deft dock]

thank you bob ross

btw are you a cs major?

[iron marsh]

You betcha NUT (doesn't quite have the same ring as bob ross 😛)

[iron marsh]

Nope, I am a pure math major

[deft dock]

interesting; what year are you in and when did u do discrete?

[iron marsh]

Technically this stuff is in any intro to proofs course, but I am taking discrete now for my CS minor.
I am in the middle of my junior year. I have a year and a half left to finish my bachelor's.

Kinda crazy that I'm so close

[deft dock]

woah nice

we're the complete opposite; i just finished sophomore year of high school

[iron marsh]

Heyy! Just a couple more years left of HS and you're off to whatever the next thing is

[deft dock]

yeah i have no clue & honestly scared; but ig we'll see. coming from precalc this year to discrete math at a local cc is very strange lol

i have yet to use a calculator in discrete

[iron marsh]

I wouldn't expect you too

There may be some stats, but it's a bit more proof oriented

[deft dock]

yeah i hate proofs

i remember geo in 8th grade

[iron marsh]

No no no, those are geometry proofs. That is not what proofs are

[deft dock]

oh no.

are you implying they are harder?

[iron marsh]

I'm implying they are more interesting and thoughtful than you might think :)

[deft dock]

okay so no: "prove this triangle in front of you is a triangle"?

[iron marsh]

The geometry proof format is just for geometry (and really just HS geometry).

There is no set proof format when writing proofs

There are multiple techniques to prove things, but they are not a guaranteed solution.

[deft dock]

interesting

[iron marsh]

Proofs are not generally obvious. They require a lot of thought and critical thinking.

[deft dock]

you can say that again

those circuit expressions

arent prooving anything

but like

trying to nit pick logical equivalences

is hell

[iron marsh]

Logical equivalences are rather useful

[deft dock]

true

but hell

[vital dew]

dackid (jump king +)

[iron marsh]

They are logically equivalent statements, so we effectively prove the original claim by proving the contrapositive.

[deft dock]

makes sense

okay bob ross

until next time

[iron marsh]

Have a good night NUT

[gilded merlin]

can someone help me in it?

[last timber]

what have you tried and where are you stuck

[weary tiger]

can someone help me on this please

[cerulean wind]

@weary tiger for what x does x = 1 - x ? that is the only place that f has any hope of being continuous

[weary tiger]

I need help

[weary tiger]

sry no, the problem i was having was how to prove this..

quadratic

[cerulean wind]

ok. take any sequence x_n converging to 1/2. show that the sequence f(x_n) also converges to f(1/2)

that will get you continuity at x_0 = 1/2

[weary tiger]

ohhhh ok tysm for explaining, would you mind checking if im on the right track once i finish it? also how would i go about ii pls

[cerulean wind]

yes. just ping me

[weary tiger]

I forgot how to factor

[cerulean wind]

well, since this is multiple choice, you can just brute force and expand each answer until you find the one that matches

otherwise, you need to find p and a such that (5x+p)(x+q)=5x^2-23x+12

expand the left hand side and then compare coefficients.

[weary tiger]

So A

[cerulean wind]

yes

[weary tiger]

What is solving and finding square root

[cerulean wind]

in what context

[weary tiger]

(x+5)^2=36

Solve by factoring or finding square root

[cerulean wind]

well, take square roots on both sides

[weary tiger]

-6,1?

[cerulean wind]

you should get that $x+5=\pm 6$ so that $x=5\pm 6$

[vital dew]

coycoy

[weary tiger]

Huh

[cerulean wind]

where is your confusion coming from?

[weary tiger]

Square root

[cerulean wind]

square root of 36 is either 6 or -6. you have to account for both solutions in this case

[weary tiger]

So it’s 6,-6?

What about the (x+5)^2

[cerulean wind]

no. if $(x+5)^2=36$ then $x+5=\sqrt{(x+5)^2}=\sqrt{36}=\pm 6$

[vital dew]

coycoy

[cerulean wind]

so x can be either 5+6=11 or x can be 5-6=-1.

[weary tiger]

Hmm

So -6,1

[cerulean wind]

what is the significance of -6 and 1 that you keep typing?

[iron marsh]

Sorry, I need to butt in real quick. $\sqrt{x}$ always refers to the positive square root. To make coycoy's thing a bit more precise, we say [ \sqrt{(x+5)^2}=\pm \sqrt{36}.]
Although it was accounted for later, it should happen the moment the square root operation takes place.

[vital dew]

dackid (jump king +)

[iron marsh]

It isn't extremely necessary now, but this plus or minus square root thing tended to confuse me a lot since I didn't realize that initially (and I have been corrected multiple times).

[cerulean wind]

no worries. i clearly wasn’t getting the point across well enough lol

[weary tiger]

Cuz 6 is 36

[iron marsh]

Nah, you did perfectly fine. It's just one of those minor nitpicks that will eventually become relevant down the road.

[weary tiger]

hey this is what i got

[cerulean wind]

@weary tiger im actually not sure if what you have shown is sufficient or not. i have to think about it more. not exactly what i was expecting tbh

[onyx mountain]

hello

can someone help me with a simple proof

for a tautology

<@&286206848099549185>

[cerulean wind]

just ask

[onyx mountain]

(p ^ (p -> q)) -> q

my first step i did was with a conditional statement

(p ^ (-p v q)) -> q

but i dont know where to go fro here

[cerulean wind]

i believe this is sufficient but requires showing that the two forms of continuity ate equivalent if you want to be completely rigorous. you also need to let s_n be an arbitrary rational sequence and t_n be an arbitrary irrational sequence, both converging to 1/2

[vital dew]

coycoy

[onyx mountain]

Can anyone help with the proof <@&286206848099549185>

[minor lake]

Helpers

Well you can start by converting the ->

[onyx mountain]

how though

into what

[minor lake]

A -> B

not(A) or B

:/

[vast narwhal]

The same way you did the first step, but with parentheses.

[onyx mountain]

im sorry

i dont really understand what you mean

i just started these yesterday

[vast narwhal]

In your first step, you substituted $p \to q$ with $\neg p \vee q$

[vital dew]

Apopheniac

[onyx mountain]

yep

[vast narwhal]

After making the substitution, you have some expression, followed by another $\to q$

[vital dew]

Apopheniac

[vast narwhal]

So you can use the same rule, just with that larger expression instead of a single letter

The rule is everything to the left of the arrow gets wrapped in parentheses and negated, and the arrow changes to "or"

[onyx mountain]

so

wait

the rule i used was

(p ^ (-p v q)) -> q

becomes

-p ^ (-p v q) v q

is that right

[vast narwhal]

with parentheses around the expression before negating it

$\neg( p \wedge (\neg p \vee q) )\vee q$

[vital dew]

Apopheniac

[onyx mountain]

okay that is what i have

[vast narwhal]

Now what are some other rules? If we want a tautology, we'd like to reduce to something that's a tautology.

[onyx mountain]

i was looking at absorption

but i dont think anything works here

do you have any ideas

[vast narwhal]

how about deMorgan

[onyx mountain]

-p ^ (-p v q) v -q

right

[vast narwhal]

Yes almost, but with the negation applied to the $(\neg p \vee q)$ term, not to the rightmost $q$.

[vital dew]

Apopheniac

[onyx mountain]

-p ^ (-p v -q) v q

[vast narwhal]

and it will change the $\wedge$ to $\vee$

$\neg(A\wedge B) = \neg A \vee \neg B$. It flips the and to or and vice-versa when you distribute negation

[vital dew]

Apopheniac

[onyx mountain]

-p ^ (-p ^ -q) v q 

[vast narwhal]

not quite

So we want to distribute the negative at the beginning of
$\neg( p \wedge (\neg p \vee q) )\vee q$

[vital dew]

Apopheniac

[vast narwhal]

That doesn't involve the last $q$ term on the right, so it'll remain the same.
We have the two terms to distribute, separated by a conjunction. So negate both of those, and change the and to or:
$\neg( p \wedge (\neg p \vee q) )\vee q \equiv \neg p \vee \neg(\neg p \vee q) \vee q $

[vital dew]

Apopheniac

[vast narwhal]

That's almost an easy tautology at that point, in the form of $A \vee \neg A$

[vital dew]

Apopheniac

[fierce osprey]

does anyone know of a good online resource to start learning discrete math/discrete structures?

(preferably a more fun one heh)

[last timber]

Maybe khan academy?

also you can check MIT OCW

[weary tiger]

lol

[fierce osprey]

lol?