talking about the parenthesis for the k+1?
#discrete-math
abstract ravine
pale epoch
he does not distinguish between what he wants to show and what is actually known
at least not in writing
buoyant bay
hello
weary tiger
Can anyone help me with this?
To help me prove this, I have chosen that $\epsilon = 0.9$ and that L = -1 since we're using contradiction to show that $L < 0$ is false, since there's no explicit formula for $a_n$ and using the formal definition of a limit of sequences i'm left with $|a_n + 1| < 0.9$, from here i'm not sure where to mathematically go
vital dewBOT
SoLongHongKong:
weary tiger
<@&286206848099549185>
stray reef
why is this in discrete-math and not in calculus, i wonder
weary tiger
@worthy palm I've never done contradictions before, how would one go about this for this sort of question?
stray reef
assume L < 0 and choose an epsilon that will force a_n to be negative
your attempt can be made to work by picking eps = -0.9L
zinc robin
Is there a way I can do this problem without just adding up the different possibilities depending on which letter gets left out in the 8 letter string
pale epoch
no
well, could be in theory
but you want to assume F(n) true and use that to prove F(n+1)
abstract ravine
ow ye thats right
ok, but how do you deal with >= 0
like there isnt anything i can do on the right hand side
pale epoch
start by expanding $(n+1)^2-7(n+1) + 12$
vital dewBOT
Lochverstärker:
pale epoch
and then use the fact that $n^2-7n+12 \geq 0$
vital dewBOT
Lochverstärker:
abstract ravine
wait doesnt that equal $n^2-5n+6 \geq 0$
vital dewBOT
MeIsNotGoodAtMath:
vital dewBOT
Lochverstärker:
pale epoch
so sure
by induction hypothesis you know that the first thing in parenthesis is >= 0
now you need to argue that the second thing in parenthesis is as well
abstract ravine
My hand writing is shit But it is What it is lol
So what do you think so far?
i think this makes sense now
@pale epoch
sorry if you dont want me to ping
pale epoch
i have no idea what you are doing
abstract ravine
well we are trying to see if n >= 3
will always result >= 0
and i did prove it didnt i?
abstract ravine
ye but then i tried a number larger than 3, and when you solve inequalities if the number thats larger than 3 will always be true
no?
pale epoch
why would it be true for all numbers larger than 3 if it is true for just one
abstract ravine
well isnt that how inequalities works
pale epoch
no
balmy turret
When you expanded it out you got n^2 -7n + 12 +2n - 6 & you could claim n^2 -7n + 12 >= 0 by your induction & then since n >= 3 2n - 6 >= 0
pale epoch
which is what i said earlier
abstract ravine
how is n^2 -7n + 12 +2n - 6 = n^2 -7n +12
pale epoch
its not
pale epoch
abstract ravine
Like do you guys have any resources you could share about induction?
The ones im using arent doing it for me
abstract ravine
When you expanded it out you got
n^2 -7n + 12 +2n - 6& you could claim n^2 -7n + 12 >= 0 by your induction & then since n >= 32n - 6>= 0
@balmy turret wait but why did you seperate them in that way? thats the question
balmy turret
I just rearranged your expansion. Since you've already proved n^2 -7n + 12 >=0 (by your induction), you just need to show that what's left over 2n - 6 is >=0 (which is trivial when n >= 3)
balmy turret
You prove the base case. The you assume it holds for n^2 -7n + 12 >=0, then you try to prove that it continues to hold for n + 1
So you show the base case
Then you have an induction hypotheis that it holds for n = k
k^2 -7k + 12 +2k - 6 >= 0
Then you show by induction that it holds for k + 1
abstract ravine
k^2 -7k + 12 +2k - 6 <= 0
@balmy turret you mean larger than 0
balmy turret
Yes
If you can get the k+1 case in terms of your induction hyp + something extra, you just need to show that it still holds when you add on that extra bit.
weary tiger
can a sequence have repeat elements?
abstract ravine
k^2 -7k + 12 +2k - 6 >= 0
@balmy turret here is the thing tho
if i find that 2k -6 >= 0
when n >= 3
that doesnt mean k^2 -7k + 12 +2k - 6 >= 0 is also true, right?
balmy turret
That's the idea
abstract ravine
the whole procedure should be heppening with the k^2 -7k + 12 +2k - 6 >= 0 and not seperately, no?
balmy turret
Not sure I follow. You know k^2 -7k + 12 >= 0 that's your induction hypotheis.
abstract ravine
ok yes, i agree
balmy turret
So adding 2k - 6 (k>=3) to that is adding something that's >= 0 to something that's >= 0 which clearly is something >=0
abstract ravine
yes
so it should be k^2 -7k + 12 +2k - 6 = 2k - 6
since we added 2k - 6
on one side, we should do the same on the other side
balmy turret
Oh, we're not adding it. It's just that when you expand out the case where n = (k + 1)
you get k^2 -7k + 12 +2k - 6 >= 0
Which happens to be the same as the case where n = k
With the extra bit +2k - 6
And since the case where n = k is your induction hypotheis, you just have to show it still holds with that extra bit from the k + 1 case.
abstract ravine
you get
k^2 -7k + 12 +2k - 6 >= 0
so i just plug in 3 to this and im pretty much done?
balmy turret
You don't need to plug 3 back in. You're showing it holds for all numbers >= 3
Your proof pretty much is (very roughly) ```
Base case:
Show it holds when n = 3
Induction hyp:
Assume it holds when n = k
Show it holds when n = k + 1:
... expand out stuff
get to:
k^2 -7k + 12 +2k - 6 >= 0
k^2 -7k + 12 >= 0 [induction hyp]
2k - 6 >= 0 [k >= 3, so 2k always >= 6]
so
k^2 -7k + 12 +2k - 6 >= 0
So it holds for n >= 3 (you're done)
It's kinda confusing at first but you're pretty much showing that it keeps holding every time n is incremented from the base case.
balmy turret
That's pretty much the form for all induction proofs
abstract ravine
do we always sepearate the induction hypothesis if possible and then we try to see if the 2k - 6 (the number that came out of k +1) also holds true?
and if so, then the whole expansion is true?
expansion = i mean the k+1 also holds true
balmy turret
You want to get to the point where you can use your induction hyp in the k + 1 case
That's the inductive part of the induction proof
abstract ravine
ok im gonna try with another question and see if i understand
im slowly understanding
abstract ravine
@balmy turret is this good?
balmy turret
I think that's the sort of idea. Normally (in the book or whatever you're working from) they'll have some kind of structure to follow, to make things a bit clearer.
weary tiger
can a sequence have repeat elements?
weary tiger
i see okay
warped mica
Is a perfectly valid sequence
unique herald
Can someone explain this step
How does the first expression equal the second expression
versed summit
How come {{1}} and {1, {1}} aren't equal, but {1,2,3,3,3,3,2,1,1,2,} and {1,2,3} are??
pale epoch
@unique herald that's the definition of intersection
ember obsidian
@unique herald don't crosspost
pale epoch
@versed summit {{1}} has 1 element (namely {1}), {1, {1}} has 2 elements (namely 1 and {1})
{1,2,3,3,3,3,2,1,1,2,} and {1,2,3} are equal because sets "don't care" about order or multiplicity of elements
the only thing sets "know" is whether an element is in them or not, a set is uniquely determined by all the elements in it
unique herald
idk what cross posting is lol
versed summit
whaaat
Isn't that the same thing though @pale epoch ? Like they both have {1} in it, so shouldn't it be equal logically?
pale epoch
indeed
pale epoch
yes
versed summit
okay the subset stuff just threw me off
ember obsidian
@unique herald posting in multiple channels
peak venture
I am a little confused about the whole R->R thing. So here I couldn't use like sqrt(x) right becuase not all real numbers are defined in the domain right?
errant bloom
yes, e.g. sqrt(-1) doesn't map to a number in R
hollow osprey
guys im not exactly sure if i should ask this here but i took discrete math last year and now im writing how it could help me with cyber security, so i think that i can write about this thing W O R D 1 2 3 4 What is that called? Its something where you do 1! + 2! + 3! +4! or something like that to get the possible combinations for the symbols
ember obsidian
f:R->R means f's domain is R & codomain is R
with the natural domain of sqrt being the positive reals, it'd make no sense to take f=sqrt
errant bloom
use \setminus
vital dewBOT
- -:
weary tiger
looking for help on these 6 questions - https://imgur.com/a/N0uKZJ2
balmy turret
If you're not sure it's pretty easy to draw it out
weary tiger
is it 5? @balmy turret
balmy turret
I don't think so. For each state there's two transitions (though I'm guessing cycles are not included).
weary tiger
i see now it's 10 since there's 5 states and 2 transitions in each
looking for help on this question
balmy turret
I think that's pretty clear, why do you think it's e?
weary tiger
i kinda guessed. is it d? since that is what is stated in the bracket rule
balmy turret
It is d.
the rule is the same as (if you've seen set operations) {w | w has an odd number of a's} ∩ {w | w ends with b}
the {w | ....} stuff is also defining a set
weary tiger
would the answer for this question be d?
balmy turret
Think so. If you rewrite the condtion a bit you can work it out using simple logic rules: neither ab nor ba -> not ab and not ba -> not (ab or ba)
lean cave
I need help!! My professor told me that the statements, ∀xP(x) ∨ ∀xQ(x) and ∀x(P(x) ∨ Q(x)), are not equivalent. JUST why are they not equivalent?
balmy turret
(for all x P(x) is true) OR (for all Q(x) is true)
vs
for all x either P(x) is true or Q(x) is true
in the 2nd case for some x P(x) could be false if Q(x) is true (and vise versa)
in the first x has to hold for all of P or all of Q
weary tiger
would the answer for this question be d? since dfas can only have one transition condition
balmy turret
I think you're almost there picking a. It's just a bit of a trick question (think about the length of string the first state q0 represents)
weary tiger
q0 is empty string so it would be e?
balmy turret
yes
weary tiger
last one, would this one be e
balmy turret
think so
lean cave
I need help!!! I've been trying to prove that A ∩ B = A ∪ B, but I can't get to it. Thank you!!!
turbid meadow
Just normal student 2 am question when im too tired to think:
lets say i have a ordered pair with the relation of real numbers
would (a,b) could be for example = (1,1)?
just not sure if a number can be "reused"?
thanks in advance.
I need help!!! I've been trying to prove that A ∩ B = A ∪ B, but I can't get to it. Thank you!!!
@lean cave do it in a ven diagram
lean cave
He doesn't want ut to do it in a venn diagram
turbid meadow
which one?
lean cave
is it my statement?
turbid meadow
yeah it is not true
yeah lmao
back to my question as im very tired xd
lets say i have a ordered pair with the relation of real numbers
would (a,b) could be for example = (1,1)?
just not sure if a number can be "reused"?
thanks in advance.```👍
ty
I need help!!! I've been trying to prove that A ∩ B = A ∪ B, but I can't get to it. Thank you!!!
@lean cave btw take a look at these rules
analog vault
Does anyone know the best way to tackle this problem?
unreal stump
Just apply the injectivity condition
craggy sun
Does it mean 'one element in set B' or 'value 1, which is an element in set B'
nova pewter
Does anyone know where I can learn about the shapes.gates.logic library for LaTeX?
OR basically, where can I learn how to draw logic gates in LaTeX 🙂
abstract ravine
Hey, so im kinda confused about recursive and non recursive definitions
so basically
How can i tell that a definition of a sequence is recursive or non-recursive?
Sequence Example:
2, 5, 8, 11,..
pale epoch
there is no definition here at all
abstract ravine
ye i know, i just gave a sequence
pale epoch
a recursive definition is in terms of previous elements of the sequence
like $a_n = f(a_{n-1})$ for some function $f$
vital dewBOT
Lochverstärker:
pale epoch
a non-recursive definition is like, only in terms of n
abstract ravine
ok the sequence above we could give it the definition t(n)= 3n - 1
that is the recursive definition?
pale epoch
no
stray reef
no, that's explicit
abstract ravine
what does that mean
stray reef
it means that to calculate a term of the sequence you do not need to know what comes before it
but only its position (n) is the sequence
abstract ravine
ok yes thats true
and?
wait so a recursive definition is one where you can obtain the nth term by using the one before like a_(n-1)+3?
just a random example
stray reef
a sequence is not the same as its definition
abstract ravine
i dont understand
stray reef
the same sequence can be described explicitly and recursively
abstract ravine
ok ? but what can i tell from this information?
explicit sequences are non-recursive?
stray reef
there is no such thing as an "explicit sequence"
abstract ravine
idk
stray reef
or a "recursive sequence"
explicit and recursive are words that describe FORMULAS, not sequences
stray reef
if your definition of $a_n$ requires you to know $a_{n-1}$ then the definition is recursive, if it only requires you to know $n$ then it's explicit
vital dewBOT
Ann:
versed summit
I have a question
Is ~q^p consistent? Our teacher said consistency meant that there was a line where it was all True on the truth table
But with ~q^p can't be all true on one line right?
gritty crescent
Right, it can't be consistent as you've defined it.
I need some hints to prove strong induction and backwards induction. Can someone help?
pale epoch
backwards induction?
fathom pond
sorry may i ask if P(A) is all possible outcomes then does |P(A)| represent all non-possible outcomes? I am not too sure what the two bars surrounding P(A) means
pale epoch
its the cardinality
gritty crescent
I'll state the exact proposition.
(Backwards Induction) Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is true, then $P(m)$ is true for all natural numbers $m\leq n$.
unreal stump
Isn't that a straight induction:
Let (n-k) th statement be true. Therefore,this implies (n-(k+1)th) statement is true
gritty crescent
I see. I'll try framing a proof based on this.
Can you give a hint for strong induction too?
fathom pond
its the cardinality
@pale epoch
okay thanks, i'll search up on it
gritty crescent
Yes, something like that. It's an exercise in Tao's Analysis 1.
unreal stump
idk, Why can't we call any induction just induction?
pale epoch
well, strong induction implies induction should be obvious
gritty crescent
Mathematical induction was taken as Peano Axiom in its usual form
pale epoch
and the other way is
strong induction is just induction finite amount of times
like if you want to prove P(k+1), then P(1) is true by checking it by hand
and regular induction then gives you P(2), P(3), ..., P(k-1), P(k)
so you might just as well assume all that
and that is strong induction
gritty crescent
What exactly is different between strong and regular induction? I still don't understand the distinction except the base case.
pale epoch
in regular induction you assume P(k) to prove P(k+1)
in strong induction you assume P(1), P(2), ..., P(k) to prove P(k+1)
gritty crescent
Ohhh, I see.
pale epoch
i.e. instead of just assuming the previous case, you assume all previous cases
but as i said
you get all previous cases "for free" anyway
via regular induction
gritty crescent
But it need not start with P(1)? The base case could be P(n) for some n<k+1, right?
gritty crescent
I see. Thanks for the help!
finite wren
Are these equivalent?
unreal stump
No
weary tiger
you can factor x out of the sum
finite wren
is that all i can do :(
naive saffron
Well it's $\frac{x^{10}(x^{32}-1)}{x-1}$
vital dewBOT
Whoever:
finite wren
im tryna look for smth like [x^40] , the coefficient in a generating series
split topaz
hey, i was wondering if it was just the teacher is drawing quickly or if U1 and U3 are neighbours?
or would it look like this if they were neighbours?
finite wren
@split topaz if neighbors means connected by a line, then I believe U1 and U3 are not neighbors, but are in the 2nd pic
Can anyone help me with the first step of finding the coeff of x^8
stray reef
it won't be the leading coefficient
(1 + x + x^2 + x^3 + x^4 + x^5)^8 is a polynomial of degree 40, not 8, so its x^8 coefficient will not be leading
anyway....
unique herald
What does the N with a subscripted o mean
I think it's the naught symbol but idk what that means
stray reef
ok ok w/e
finite wren
lol mb mb
stray reef
hmm
finite wren
i think multinomail thm
stray reef
yeah maybe that
finite wren
but idk how to work it
stray reef
looks kinda tricky ngl
i'd reframe this as solution-counting
let $$S = { (a_1, a_2, \dots, a_8) \in \bN_0^8 \mid a_1 + a_2 + \dots + a_8 = 8 }$$ and for each $k = 1, 2, \dots, 8$ define $$Z_k = { (a_1, a_2, \dots, a_8) \in S \mid a_k \geq 6 }$$
i claim, first and foremost, that $$x^8^8 = |S \setminus (Z_1 \cup Z_2 \cup \dots \cup Z_8)|$$
vital dewBOT
Ann:
stray reef
does that make sense to you? @finite wren
finite wren
why do they have to add to 8?
stray reef
cause you're looking for the x^8 coefficient
finite wren
ohhhhh
stray reef
yeah so does that reframing make sense or is there sth that needs explaining
stray reef
aight so
my goal is to count the solutions in nonnegative integers of the equation a_1+a_2+...+a_8=8, with the additional constraint that a_i <= 5 for all i
cause that'll give the coefficient you asked about
make sense?
finite wren
what about (8,0,...,0)
stray reef
what about it
yeah, that's one of the solutions i don't wanna count
i'll get to that in a moment
stray reef
yeah so counting with those constraints is hard
if they weren't there it would be easier
S is the solution set without taking the constraints (a_i <= 5) into account
the Z_k consist of the solutions which violate the constraints (i.e. a_k <= 5 is false, which is the same as a_k >= 6)
in particular (8,0,0,0,0,0,0,0) would be in Z_1
does this make more sense now?
finite wren
yes
im just wondering if
doing (1 - x^6)/(1-x) as a first step would be any easier
stray reef
i don't think so
weary tiger
lol
finite wren
hi big floppa
weary tiger
hi
weary tiger
ann, the method i told them to try was using generatingfunctionology
stray reef
yeah so like what's nice about the Z_k is that Z_k \cap Z_j is empty for k != j
since you don't have enough on the RHS to violate two constraints (you'd need 12 but you only have 8)
and also the Z_k are all the same size
so |S \ (Z_1 cup ... cup Z_8)| = |S| - 8 |Z_1|
finite wren
very interesting...
ok thx Ann, im gonna try this lol gonna take a fat while
@stray reef im confused why you pick a_k >= 6 and not a_k >= 5 or smth
stray reef
a_k >= 5 would allow for equality
and the a's are allowed to be 5
but i am looking for violated constraints
weary tiger
wait why are there 8 a's
unique herald
In the expression: (A × A) \ (A × B), what does the " \ " mean?
finite wren
@unique herald set difference i believe
finite wren
@stray reef :,( i really am struggling to understand - is 6 the special magic number to use in the definition of Z_k because we have 8?
analog vault
can anyone help me break down why b is false here?
pale epoch
what do you mean false?
analog vault
b is invalid but I need to provide an interpretation
I know its invalid but its hard getting to the conclusion
pale epoch
invalid?
it may be true or false depending on the interpretation
well, do you know what it's saying?
analog vault
There exists an x for A(x) and there exists an x for B(x) only if there exists an x for A(x) and B(x)
In the case that A(x) is even and B(x) is odd its false
no?
pale epoch
yes
there is an even number and an odd number, but no number that is both even and odd
analog vault
So how would you write the interpretation for b there? Im having a hard time visualizing A(x) as even and B(x) is odd even though I have the basic concept in my head
would you think of A(x) and B(x) as functions?
pale epoch
essentially the are function that output either true or false, yes
analog vault
so would you just say that they are even and odd or would you give some type of formula for a and b?
pale epoch
i would write "let A(x) be the statement 'x is an even number'"
delicate ridge
@weary tiger have you come across the pumping lemma?
if a language is regular, there exists an integer p such that any word w in the language can be expressed as w = xyz
where the following hold:
|y| >= 1
|xy| <= p
x y^n z is in the language for any integer n > 0
weary tiger
i have i just dont understand the professor
he has a heavy accent and no one really gets what he is sayinh
delicate ridge
ok, forget him for a second
so lets try and think of a string that may break this
weary tiger
okay
delicate ridge
so, suppose this integer p exists, and satisfies the conditions
let's think about the string w = a^p b^p
delicate ridge
lol
delicate ridge
haha ok
weary tiger
yeah no idea how to solve it
delicate ridge
let me have a think
im experimenting with a string of the form a^qr, where q and r are the first two primes greater than p
weary tiger
ohh
delicate ridge
actually where qr > p works too
weary tiger
tbh im already lost on what to do
delicate ridge
suppose |y| = k, where k <= p
if k is not equal to q or r, then |xyz| is the product of more than two primes
otherwise k * |xz| = q * r, which doesn't work
so let |y| = q wlog
then |xy^2z| = a^2q * r
which is of the form a^n, where n is the product of three primes
delicate ridge
haha, go for it
stray reef
@finite wren no the Z_k are the constraint violation sets
the 6 comes from the fact that NOT(a_k <= 5) is equivalent to a_k >= 6
unique herald
- In a class of 65 students, 25 speak Spanish, 32 are excellent cooks, and 50 love
dogs. Each student is in at least one of these categories.
There are 18 Spanish speakers who don’t cook. There are 21 dog lovers who are
excellent cooks. There are 4 cooks who speak Spanish and do not love dogs. Determine
the number of students in the class in each of the following categories:
1
(a) Speak Spanish and love dogs
(b) Love dogs and cannot cook
(c) Speak Spanish, are excellent cooks, and love dogs
Could somebody please help me
I'm using a Venn diagram to solve this and I've just been staring at my paper for 15 mins
stray reef
4 set venn diagrams are a bit too complex imo
wait no nvm
there are 3 sets here nvm
weary tiger
L7c = {w ∈ Σ ∗ : na(w) (mod 3) > 0}
where na(w) means, of course, the number of a’s in w and (mod 3) means the remainder when divided by 3```cuz automata is hard af 🤣
jovial swan
Reidivy, I would write letters in each sub-region of that Venn diagram and write formulas with these letters
like there are seven sub-regions so a+b+c+...+g = 65
unique herald
Could I simplify it to three sets?
i was using 7 sets
but maybe I could just use combinations of three sets?
jovial swan
no yeah, 3 main sets + 3 intersections of two + 1 intersection of 3 = 7
there is also the outside region but it's zero since > Each student is in at least one of these categories.
you start with seven unknowns, then all those pieces of information give you one equation. when you have seven equations, you will have a fully-defined system
like There are 18 Spanish speakers who don’t cook translate to a + b = 18
unique herald
So my first step should be to find seven equations?
jovial swan
in each step you find one equation, which reduces the number of unknowns. when you found the seventh equation, you have a fully-defined system that you can solve
like if you had a+b+c+d = 18 and a+b+c+d+e = 20, you immediately knew e = 2
this is the best i could find.. lol https://i.stack.imgur.com/BBICS.jpg
woo + yes = 18
woo + yes + .... + huh = 65
already two equations!
There are 21 dog lovers who are
excellent cooks. means bar + baa = 21
unique herald
but how do we know they dont speak spanish as well
jovial swan
oh. you are right
unique herald
do/dont
jovial swan
bar + baa = 21
unique herald
im lost
jovial swan
the circle AA (top-left) is Spanish speakers
BB is cooks
the bottom ones is Dog lovers
unique herald
right
jovial swan
so what is woo?
unique herald
solely spanish speakers
unique herald
what is the difference between bar and hoo
rustic stratus
does anyone know what this P means
jovial swan
yeah just ignore those 🙂 ignore hoo and foo
unique herald
Power set connor
jovial swan
yeah. cardinality of the power set
that image was the best i could find.. lol. i wrote "a" for "woo", "b" for "yes" etc
oh this is much better
https://www.combinatorics.org/files/Surveys/ds5/gifs/V3.gif
rustic stratus
wouldnt it be >= instead of >
unique herald
ohh i understand bar + baa = 21 now
unique herald
or for that diagram b
jovial swan
there you go, fourth equation 🙂
jovial swan
if it does, you have 8 uknowns :p so you need 8 equations
so it doesnt help :p
There are 18 Spanish speakers who don’t cook what does this mean?
for the last image, lets say P = cook, M = dog
or maybe go the other way and think about what those letters mean. like what does the region b+e represent
@rustic stratus, IIRC, power set always includes empty set. but if A itself is empty, they should be equal, yes
no wait, in that case cardinality of A would be zero, but power set would be 1. so it could be correct
i'm going afk for a bit. @unique herald , if it's still unclear you can PM me
jovial swan
yw 🙂
connor, yeah. since the power set always contains the set itself + the empty set, it always has more members. https://en.wikipedia.org/wiki/Cantor's_theorem
weary tiger
is it worth proving n/2 < (n/2)+1 for all n using induction or is it too trivial that there’s no point in doing it
honest barn
I'm pretty sure whatever definition of < you're using would automatically imply that
point being, that isn't worth proving
honest barn
I guess thinking about a definition of <, you might have to "prove" 1 is not negative but...
F that
drowsy vortex
i need help figuing out the negation for the sentence "This vertex is not connected to any other vertex in the graph."
I thought it would be "All vertices are connected to a vertex"
but thats wrong
naive saffron
Well it is useful to just put a "It is not the case that" in front of the statement, then you can find the negation
So if you do that, then you see that the negation is still about the specific vertex
drowsy vortex
so "this vertex is connected to any other vertex"?
naive saffron
No
The negation is "this vertex is connected to some other vertex"
If your statement has some variation of for all (in this case it is "the vertex is not connected to all the vertex") then the negation will have "there exists some" (in this case it is "there exists a vertex that is connected to the original vertex")
drowsy vortex
is some equivalent to "at least one" ?
drowsy vortex
ok thank you
naive saffron
It's just that "at least one" has the (intuitive) implication that there is potentially more
wintry schooner
hey guys, how can i show that this given relation above has a symmetric relation
wintry schooner
@cunning thistle uhm yeah I tried something
seems like an obvious answer haha
but if 2x+y is a multiple of 3 then i think 3 cannot be a multiple of 2x+y 😆
i think thats what the answer is?
glass condor
Consider the fact that 2x+y being divisible by 3 for a certain (x,y) means you can represent 2x+y as 3k, where k is some integer. Now see if you can then rewrite x+2y (for the same x,y) using k.
cunning thistle
What?
@wintry schooner i meant to ask what have you tried. Anyways did you get what ConfusedReptile is saying?
gritty crescent
Proposition: A subset of a finite set is finite.\Proof: Consider a finite set $A$. Since the subset of $A$ with the largest cardinality is $A$ itself, and $A$ is finite, therefore it follows that every subset of $A$ is finite.\Proposition: A superset of an infinite set is infinite.\Proof: Consider an infinite set $B$, and let $C$ be a superset of $B$. By definition, every element of $B$ is present in $C$, and since $B$ has infinitely many elements, so does $C$, which means $C$ is infinite.
vital dewBOT
TedNowKaczynski:
gritty crescent
Uh I'd like to get my proofs verified.
glass condor
The second just follows from the first - if a superset of an infinite set was finite, we'd have found a finite set with an infinite subset.
gritty crescent
Yeah, that makes sense!
Thanks :)
I hope my proofs are okay as they're stated though? No glitches in them?
glass condor
I'd say so, yes. Both follow from the general statement that if B is a subset of A, then |A| >= |B|.
gritty crescent
Makes sense. Thanks again!
gritty crescent
Can there be three sets $A, B$ and $C$ such that $$A\in B, B\in C\text{ and }C\in A?$$
vital dewBOT
TedNowKaczynski:
gritty crescent
I believe such sets don't exist but not completely sure.
glass condor
If by $\in$ you mean $\subseteq$, then sure, A=B=C 😛
vital dewBOT
ConfusedReptile:
glass condor
if $\subset$, then not for finite sets, but for infinite ones, hmm...
vital dewBOT
ConfusedReptile:
gritty crescent
Uh I meant belongs to, not subset actually.
stray reef
this would violate axiom of regularity iirc
gritty crescent
Oh, I see.
dapper rose
Hint: apply axiom of regularity on {A, B, C}
vital dewBOT
carlome:
spring aspen
if P(z,y) is false, meaning the room isn't in a building on the campus
and Q(x,z) is true, meaning student x has been in that room z
then why is it still true?
warped mica
The formal expression says "there are a student and a building on campus such that for every room, if the room is on such building, then the student has been in it"
The implication is the "if the room is in the building y, then student x has been in it" part of the statement
Which in usual language means that student x has been in every room of building y
spring aspen
i'm still confused, when for example "if the room is not in building y on campus , then student x has been in it" it is still true, right?
why don't I use the "and" logical operator instead where both P(z,y) and Q(x,z) has to be true.
spring aspen
like for example
this uses and
why does this use "and" and the other "implication"?
mystic moss
they're different statements. here you don't want to return true for any z that isn't in building y because you want to verify the existence of a z in every building. but in the previous example you want to show the existence of a student that has been to every room of a building, so we don't care about whether a student visits rooms that aren't in the building and we return true anyway
sonic path
can someone explain to me how the stuff in the black box is arrived at from 1 and 2?
i understand how everything before that is arrived at
spring aspen
@mystic moss thank you for the help
i'm still a little bit confused but i'll live with it for now
mystic moss
gl with that. if you have any specific questions you can post them here
sonic path
anybody can help with my question?
spring aspen
@mystic moss well while you're here. i do have more question about my inquiry
if you dont mind
but in the previous example you want to show the existence of a student that has been to every room of a building, so we don't care about whether a student visits rooms that aren't in the building and we return true anyway
@mystic moss
why wouldn't we care about the student visiting a room that isn't in the building of a campus?
halcyon mirage
for a question like this will a and b always be different numbers E = {n ∈ N : n = 2a+2b for some a,b ∈ N}.
spring aspen
shouldn't it be confirmed that that student must have at least visited a room IN every building on campus?
mystic moss
@spring aspen in the first proposition we only care about the rooms in at least one particular building
we don't care about every building on campus, we just need one that the student is familiar with
spring aspen
oh yeah
my bad
so even if the room isn't in that building, whether or not the student visited that room, it would still be true, right?
but all the rooms that is in that building that the student visited is also true
so the other rooms doesn't matter?
is that it?
mystic moss
yeah basically
spring aspen
okay
now i understand
i have one last question
can i use "and" here instead of "implies"?
mystic moss
where?
vital dewBOT
carlome:
mystic moss
well we know right off the bat that p(z, y) isn't going to be true for all z, no matter what y you choose
spring aspen
because the z consists of all rooms?
okay
now i understand
thank you very much for the help 🙂
it is really helpful
balmy turret
(this might be wrong -- I've not done this for a while)
(¬P(a) & Q(a)) -> R(a)
infers (exportation)
¬P(a) -> (Q(a) -> R(a))
you also have
¬P(a) -> Q(a)
now if ¬P(a) holds you have
Q(a)
Q(a) -> R(a)
which is
R(a) (modus ponens)
so
¬P(a) -> R(a)
which is
P(a) or R(a)
which is the same as:
R(a) or P(a)
which is
¬R(a) -> P(a)``` @sonic path(this might be wrong -- I've not done this for a while) (¬P(a) & Q(a)) -> R(a) infers (exportation) ¬P(a) -> (Q(a) -> R(a))
@fob nation#7601
@balmy turret Is there another name for exportation? Have not heard this term before
signal basin
For every integer $d\ge1$, let $\operatorname{Pol}(d)$ be the set of monic polynomials $p$ with rational coefficients, i.e. polynomials of the form $p(x)=x^{d}+a_{d-1} x^{d-1}+\cdots+a_{1} x+a_{0}, (a_{d-1},...,d_0)\in\mathbb{Q}^d$.
vital dewBOT
Schuams:
signal basin
I will like to show that $f:\mathrm{Pol}(d)\to\mathbb{Q}^d,f(p)=(a_{d-1},\ldots,a_0)$ is an bijection. I have shown that it is an injection. For surjection: \
Let $(a_{d-1},\ldots,a_0)\in\mathbb{Q}^d \overset{def}{\iff }p \in \mathrm{Pol}(d) \implies f(p) = (a_{d-1},\ldots,a_0)$.
Right?
vital dewBOT
Schuams:
light briar
Need help, How can I prove this property of atoms of a boolean algebra?
$atom.a \implies a + b = 0 \lor a \cdot b = a$
vital dewBOT
ErBurrero:
light briar
Our definition of an atom is this
$atom.a \equiv a\neq 0\land (\forall b|0\leq b\leq a:0=b\lor b=a)$
vital dewBOT
ErBurrero:
light briar
That seems to give enough info for proving that in the cases b = 0, where the proof is trivial (b = 0 => b.a = 0), but IDK how to prove the theorem for the cases where b is not 0, that is, b is an atom or not an atom and greater than 0. Need help with those cases.
spring mica
it says that in order to determine that a pair x y is an equivalence relation
we need those three things
however, why are these three conditions the case
why don't we need to know that y is equivalent to y for all y
@pale epoch
weary tiger
it's just the properties that must be satisfied for something to be defined an equivalence relation: 1) reflexive 2) symmetric 3) transitive
gritty crescent
I would like to prove that $A\cap(X-A)=\emptyset$, where $A\subseteq X$ and $X-A$ denotes the set difference.\Proof: $x\in A\cap(X-A)\iff x\in A$ and $(x\in X$ and $x\not\in A)\iff (x\in A$ and $x\in X)$ and $(x\in A$ and $x\not\in A)$. Since there does not exist any $x$ such that $x\in A$ and $x\not\in A$, therefore there does not exist any $x$ such that $x\in A\cap(X-A)$. Thus, $A\cap(X-A)=\emptyset$.
vital dewBOT
TedNowKaczynski:
gritty crescent
Is my proof okay? Can I make it better?
Also, do Venn Diagrams constitute legitimate proofs when proving basic set theory propositions like this one?
glass condor
The proof looks solid.
Also, do Venn Diagrams constitute legitimate proofs when proving basic set theory propositions like this one?
hmm, would like to know this too.
gritty crescent
Thanks for verifying. I've read "proofs with pictures" are considered legitimate when the pictures have reasonable meanings; I wonder if Venn Diagrams fall into that acceptable category.
gritty crescent
Oh, I see. Why is that though? Aren't Venn diagrams rigorous enough?
pale epoch
for one, you never directly work with any definition
you just claim that this diagram accurately represents the situation
which might not be the case
gritty crescent
Makes sense. Just read the same thing on Stackexchange.
Thanks for letting me know!
weary tiger
Venn diagrams = set theory 
nimble plover
for Sup(S) in 1i, is it infinity or 1?
because for n = 0 i get infinity, but idk if you can divide by 0 here (pls @ me)
drifting sail
I think $\mathbb N = {1,2,3,\hdots}$ here. It's also not 1 since you can find elements larger than 1. Try considering even and odd $n$ separately and see if you can conclude something about the subsequences $a_{n_k} = 1+\frac{(-1)^{n_k}}{n_k}$. (Are they increasing/decreasing for odd/even $n$?)
vital dewBOT
bastian.uwu:
drifting sail
@nimble plover
nimble plover
@drifting sail it decreases
as n gets larger the value overall is decreasing
but can u divide by 0 when working out the sup and inf?
if so, n = 0 gives the largest value being infinity
drifting sail
1+1/0 couldn't be an element of the set since that's not well defined. That's why I think here \mathbb N is the positive integers (convention varies from country to country)
drifting sail
yes
hollow bloom
In a Deterministic Finite Automata can the input alphabet be empty?
delicate ridge
it wouldn't make for a very interesting automata, but yeah
hollow bloom
@delicate ridge then would it just be only one node that doesn't have any transition functions?
plucky stirrup
can someone help with understanding how to solve this recurrence relation? I have the answer but don't understand how it was attained.
thats what ive done so far; but stuck from there
glass condor
$$x(2^k) = x(2^{k-1}) + 2^k$$
First terms: 1, 1+2=3, 3+4 = 7, 7+8=15.
Proposition: the formula is $$x(2^k) = 2^{k+1} - 1$$
Proof: $$x(2^{k+1}) = x(2^k) + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1} = 2^{k+2} - 1$$
Proven by induction.
vital dewBOT
ConfusedReptile:
glass condor
That's how I'd do it.
recurrence equations are commonly solved by just guessing at the answer, then formally proving it via induction.
plucky stirrup
interesting
right now i am having trouble just transforming the pattern into a equation
if the general solution is
x(2^k) = x(2^(k-i)) + 2^k + 2^(k-1) + ... + 2^(k - (i -1))
is there a way to break up the terms on the right into a summation forumula
glass condor
I mean, sure, you can also do it that way:
$$
x(2^k) = x(2^{k-1}) + 2^k = x(2^{k-2}) + 2^{k-1} + 2^k = ... = x(1) + 2 + 4 + 8 + ... + 2^k =
$$
$$
= \sum_{i=0}^{k} 2^k = 2^{k+1} - 1
$$
vital dewBOT
ConfusedReptile:
plucky stirrup
aah thank you that helps alot
vital dewBOT
YuJJun:
crude hill
Is this right??
crude hill
Ye
stray reef
then no
crude hill
Why would it include the regions in C
crude hill
I don't quite understand what it's asking
Since B-C is just the red part I shaded in my diagram would it not
stray reef
ok i miscolored B-C sorry
crude hill
Yea
crude hill
Ahh there we go
Thank you for clearing it up!!1
@stray reef hi sorry one more thing, would I be wrong in this or
stray reef
is (A-B) cap B' meant to be in yellow
crude hill
Yea I guess, bc wouldn't B' imply anything not in B so that's why I shaded C as well
stray reef
it says intersection
not union
A - B is actually the same as A cap B' so your thing is just A cap B' cap B'
crude hill
A-B means elements in A but not in B, so everything in the yellow part
And B' means elements not in B, so everything yellow AND red
And the intersection means elements in both A-B and B'
That's how I understand it
nova star
trying to solve this
stray reef
hmm
it feels as if there's some sort of invariant here which would change if one were to pass from this setup to one with just 1 marble
nova star
@stray reef professor explained the problem on board so i didnt write it correctly when trying to explain using MS paint, sorry 😅
but i think i have the proof, mind double checking if its correct for me?
i wonder if i can prove it for it being equal to 2, or even offer a generalised proof
last sigil
prove the minimum marbles is greater than 1?
Is that written correctly and I am really misunderstanding?
stray reef
is this not just literally $\exists! p (\forall q , S(q,p))$
vital dewBOT
Ann:
mild flicker
I'm given an array A of n distinct numbers. I need to find the number of triples of indicies i < j < k (not necessarily consecutive) such that a[i] < a[j] < a[k]. Example: [1, 4, 2, 6, 3, 5] will give 7 with [1, 4, 6], [1, 4, 5], [1, 2, 6], [1, 2, 3], [1, 2, 5], [1, 3, 5], [2, 3, 5]
How can I find that in O(n log n) ? The hint given was to use merge sort and pay attention when they're merging
plucky stirrup
So I am stuck on a logic riddle in class:
In the riddle there are two villages, Honest Village and Liar Village,
In the day time the two villages visit each other, so that both villages have a mix of honest and dishonest people
A traveller visits one of the villages but does not not whether it is an honest or liar village
What is one question to ask to find out what village the villager is in?
I feel like this has to deal with two inputs with AND OR NAND operators, but not sure
could you draw a logic statement from this to figure it out? or would there be a simpler method
hardy viper
umm it's just out-of-the-box thinking mostly
if you just focus on one village, you'll never be able to tell them apart, so your question needs to combine the two somehow
like instead of "what is the truth value of this?" you can try "what does the other village say about this?"
mystic moss
technically you could still only consider one type of person right? if you asked, say, "what would you say if my friend asked you this?"
hardy viper
o yea I was thinking about the 2 door problem nvm
winged bramble
whats the difference between a subset and a proper subset?
hardy viper
it's like < vs <=
mystic moss
o yea I was thinking about the 2 door problem nvm
even with the two door problem, can't you do the same kind of approach?
the truthful kid would just say the truth, and the kid who lies would end up saying the truth because of the double negative
hardy viper
right right
plucky stirrup
oh yeah i forget the questions can only be yes or no; so we can't ask what would you say if i asked person B etc..
mystic moss
just ask "would you say ___ if..." then
plucky stirrup
its a little bit different than two person problem in that, if we ask a person what would another person ask, that second person could be another liar or honest person; wheras in two door problem we only have two people
in two door problem we have
honest person --> liar
or
liar --> honest person
whereas in this scenario we can also have
honest person --> honest person
liar --> liar
mystic moss
right, exactly, so force the double negative by asking about his own answer
plucky stirrup
okay so you're saying it wouldnt matter if person was honest or dishonest
okay so like "would the disonest village say this is the truth village"
and then take the opposite answer
mystic moss
no not quite, you don't know if they are an honest person or not so you'll get differing answers
if my friend asked you, would you say that this is the truth village
plucky stirrup
how is that question different?
if they are in the truth village and the question was 'if my friend asked you, would you say that this is the truth village'
and if it is truth village
the honest person would say yes
and the dishonest person would say no
we still wouldnt know then
mystic moss
if my friend asked the dishonest person, the dishonest person would say no. the truthful answer to the question would be "no", but the dishonest person would lie and say "yes"
plucky stirrup
so your question is 'if a friends asked the dishonest person whether this is dishonest town, would they would say no?'
mystic moss
no, my question is
if my friend asked you, would you say that this is the truth village
i'm only using my friend to make it clear that the answer has to be negated
i could also say "if i asked you, would you say that this is the truth village"
but it may be a bit more ambiguous
plucky stirrup
how does using a friend negate the statement
oh you mean the answer has to be negated
mystic moss
if the person is dishonest, yes
if the person is truthful we'll get the right answer anyway
plucky stirrup
woah thats weird
is there a name for this property
or like is this a boolean statement
mystic moss
this isn't really a property...? but then again, if it was i wouldn't know. it's basically --p = p if p was a boolean variable
plucky stirrup
howd you double negate p tho; by just using the statement if my friend asked you
mystic moss
instead of just having him give me the answer, i'm asking about the answer
nova star
prove the minimum marbles is greater than 1?
@last sigil if u can prove that minimum number of marbles possible has to be greater than 1, then give a specific scenario where u can get minimum number of marbles to 2, u can prove that the minimum number of marbles is 2, I was focusing on the first part as the second part is easier and I had done it already
So we had multiple different sections to this
versed summit
I don’t understand this. Please help.
I have quiz on it tomorrow and she barely taught us it
weary tiger
maybe it would help to write what each of those mean with "cumbersome notation"
maybe pick a specific n if you need it less abstract
what does $\bigcap_{i=1}^4 A_i$ mean, for example
vital dewBOT
Botnuke:
weary tiger
$A_1 \cap A_2\cap A_3\cap A_4$
vital dewBOT
Botnuke:
weary tiger
@versed summit
weary tiger
A_1 is {1}
versed summit
Then what's A_2?
weary tiger
as you wrote it
versed summit
So then All of those intersected would just be 1 right?
weary tiger
yep
versed summit
What does the 4 above the intersection meaning?
weary tiger
it's indexing the intersection of multiple sets
similar to summation or product notation
versed summit
okay and then for the one where instead of intersections it's unions; what is it asking for there?
weary tiger
uh basically the exact same thing we just went through but with union symbols instead
weary tiger
up to?
versed summit
up to n?
weary tiger
yep
versed summit
I see
Okay few more questions
These two questions seem a lot more complex
And while I could sorta work through those last two, these im completely lost on
weary tiger
what have you thought about
versed summit
7A seems like the thing I did before but I feel like it should be different
Likewise with 7B
weary tiger
they seem a bit different to me but not by much
versed summit
So would my answer be the same?
versed summit
{0, 1, 2} ?
weary tiger
weary tiger
if I said A_2 = {00, 11, 01, 10 0, 1} would this ring any bells
versed summit
nope
weary tiger
well...
versed summit
my professor is kinda the worst
weary tiger
bit strings of length n are strings consisting of 0's and 1's of length n
A_n consists of all bit strings of length 1,2,3,..., and n
the bit strings of length 1 and 0 and 1
ones of length 2 are 00, 11, 01, 10
ones of length 3 are 000, 100, 110, 111, 010, 011, 110, 101
so A_3 would consist of all 14 strings I just mentioned
is this making sense
weary tiger
what's confusing?
versed summit
Just the set I suppose, what the heck am I looking at?
-i, -i + 1, -2?
I don't understand the pattern
weary tiger
the set of integers less than or equal to i, and greater than or equal to -i
versed summit
weary tiger
A_3 = {-3,-2,-1,0,1,2,3}
versed summit
alright i must be pretty dumb cuz I have no idea what i is
weary tiger
it's a dummy variable being used to index the unions and intersections
well actually it's more like a dummy variable being used to define the set
I guess it's comparable to x being the standard dummy variable in real valued functions
but f(x), f(t), f(z), doesn't matter what you variable name you pick, it has the same meaning
you could even view A as a function
dependent on variable i
given an i, A_i outputs (is equal to) the set of integers ≥ -i and ≤ i
does this make any sense or does it just make it more confusing
versed summit
It makes sense; thank you.
feral shell
Please I have no idea where to start, can someone lead me in the right direction
south sparrow
Hello. I'm trying to prove that it is impossible for a graph with n=17 vertices to be self complementary. So far I've figured out that you need to have n = 0 (mod4) or n=1 (mod4), which holds for n=17.
Also the number of edges is n*(n-1)/4 = 4*17, and then sum of all degrees is 8*17. I'm starting to look at the degree sequence but no luck so far. This is pretty early in a intro graph theory course so I don't have much to work with. Any ideas would be appreciated!
south sparrow
Okay I think it might be a mistake on the assignment since a https://en.wikipedia.org/wiki/Paley_graph is self-complementary and works for n=17.
junior bridge
Anyone who can help me with a problem im stuck on for combinations? Trying to evaluate this:
https://gyazo.com/0e702540297642ebf61cde0a545196a5
What ive tried so far is plug it into the formula for (n choose r) with n + 1 taking the place of n and n-r+1 taking the place of r. I have no idea how to simplify it from there though
So what I have right now is looking like:
[(n+1)*(n!)] / [(r!) * ((n-r+1)!)]
unreal stump
n+1 c r = n c (r-1) + n c r
Out of n+1 objects,fix a particular object. Now,there are 2 cases:the object is selected or the object is not selected
For the first case,there are n c (r-1) ways and for second there are n c r ways
(or just manipulate algebraically)
@junior bridge
junior bridge
what do i do about the n - r + 1?
junior bridge
I'm lost, why am I able to just change it to n + 1 c r?
junior bridge
oh i see
valid quail
hello
i am currently in second year university, i got discrete math and i barely pass even though i dont understand a thing. i want to ask help for mathematics induction and proof somthing, thx in advance
unreal stump
Go ahead
near root
A = {1, 2, 3, 4, 5}
f:A-->A
Find the number of functions that fulfill |f[A]| = 2
I already know that you choose 2 out of 5 and then you multiply by 2^5 since that's nunber of functions.
I also understand that for every pair I choose I need to subtract 5C2, but why do I multiply that by 2 ?
2^5 * 5C2 - 5C2
Is it because you can do this? (For example)
pale epoch
for every element in A you have a choice on where to map it
there are 2 choices, because the image has 2 elements
there are 2^5 ways to do this
opal cedar
How would you go about proving that there is a proposition that matches to every function, such that f(a1, a2... an) = P(a1, a2,...an)
all inputs and outputs are in set {T,F}
mystic moss
@opal cedar consider which inputs x result in f(x)=T
weary tiger
stray reef
what's $7Q$? \thonk
vital dewBOT
Ann:
delicate ridge
quite possible an incredibly clapped negation symbol
weary tiger
what's $7Q$? \thonk
@stray reef negation Q
weary tiger
yeah
opal cedar
just wanted to say thanks for the tip earlier, this class is absolutely wrecking my brain
can someone help me figure out what this means exactly, my textbook just jumps from regular propositional logic to things like this that I don't quite grasp yet $\bigvee_{i=1}^{n}$
vital dewBOT
satazero:
opal cedar
oh. should have put them separate, sorry
sour arrow
Do you understand this?:
|A×B| = |A||B|
karmic nymph
yes
sour arrow
Well, under what conditions is the right side equal to 0?
karmic nymph
well when a or b is zero
sour arrow
Gottem
karmic nymph
The null set isnt zero?
karmic nymph
oh right
sour arrow
And we're using cardinality in the equation above
karmic nymph
using cardinality to see how many elements there would be?
sour arrow
Exactly, and noting that any set with 0 elements is the empty set
karmic nymph
i understand
sour arrow
One can also argue with a contradiction. If A and B both have elements, A×B does as well
karmic nymph
oh
sour arrow
Contrapositive: If A×B has no elements, either A or B doesn't either
Sorry so I gave up on the contradiction route, the contrapositive was too good here
karmic nymph
ahhh i understand
so you changed negation of (A and B) into negation A or negation B right
is that a law?
sour arrow
Exactly you got it. That's DeMoivre's law
karmic nymph
nice
sour arrow
~(A and B) = ~A or ~B
karmic nymph
yup
sour arrow
~(A or B) = ~A and ~B
In case you were curious haha
sour arrow
Np, feel free to ask if you have any other questions
karmic nymph
good for now :)
frigid abyss
can someone help me with part 2. i got part 1, but idk how to aproach the second one. Ping me if u can help pls
karmic nymph
so if S is an element of S, does that lead to S cannot be the set {x | x epsilon x}
weary tiger
Hi -- I'm just starting out with logical equivalences and I'm a bit lost on this one.
I'm am assuming that I'd be maybe use De Morgen's Law and then Absorption.
Those are the only logical equivalences that look remotely close.
sour arrow
DeMorgan's is for distributing ~ into parenthesis which isn't useful here
Instead consider distribution @weary tiger
weary tiger
Both of these appear to be tautologies. Right? How do I denote that? Would each of them be t?
I saw this example and this appears that right way to go about it.
Do you think "p or p" is a tautology? What if I said "does 1=0 or does 1=0"?
Doesn't sound very tautological to me haha
but p would be the same statement
I suppose I'm missing something.
It'd be idempotent law
That's not the same as saying that "p or p" is a tautology, but it's true!
7 is just saying "saying the same thing twice or giving 2 options that are really the same thing, are just that thing"
For the other statement, I feel inclined to say its indempotent law as well but it doesnt fit the form defined by the chart. ~q is p correct? Is this a law I'm forgetting?
What are you trying to do? In what context are we talking?
p, q, and r are defined to be literally just anything that could be strictly true or false, they're not necessarily related
What do you want to know about that statement?
this statement needs to be logically equivelant to p
I'm unsure how to prove it
it's equivalent to ~(p=>q) i guess
Yeah slim is right those two are just not logically equivalent
all good <3
Okay -- so let's start from the beginning then because I'm lost.
This is my initial logical equivalence.
After distribution this is how the left side looks:
Nice, are you only allowed to use the equivalences on that list?
As far as I'm aware: yes.
Oop ok then 1 moment
Actually the way it was written in the problem one of those equivalences gives you what you want right away
Peep 10
The Absorption laws has a p and q though not p and ~q (like in my equivalence)
q is literally just any statement
And so ~q is also just any statement, ever, right?
You can just relabel q to something else if you want
I'm trusting you but I also feel skeptical
I think you are abstracting things too much, these are just intuitive statements about things that are true that look a little scary cause they are written in such a far-removed manner
So I could state the Absorption laws and that should be the end of it
Yep
A tip I think would help you is to just think of these variables as literally any thing that could be true or false, like "this" or "that", or maybe come up with examples
because that is what they are
Maybe go through that list and justify to yourself why each might be true
not in terms of manipulating symbols, but just normal human language with no jargon
For example 4 is just saying, maybe whether you like cheese AND that 1=1, that second detail is so obviously true I can just focus on whether you like cheese.
Interesting...
Just did a truth table and you're right.
So from 10 you know p or (p and q) is equivalent to p right? Now just rename q to anything. Literally anything, like Y maybe.
So you have p or (p and Y) is equivalent to p
let Y = ~q where this q has nothing to do with the first q lol and you get "p or (p and ~q) is equivalent to p"
just to show you why this works. you are simply renaming the variable
Would this be necessary when I'm using logical equivelances to prove?
Using another variable?