Looking back at the psets, i think it's actually worth looking at them in reverse order just to not get too discouraged: the class ends on some number theory and begins with the Relation/Axiom/Set/Sequence stuff you see in early high level math classes. Some of that number theory/counting stuff is incredibly accessible from the outset, so the class doesn't just get monotonically more obtuse.
That said, if you've worked through vellman and you finish up this class, you're more than ready to do a class in proper number theory, discrete math or even real or complex analysis. Somebody else said that this course was a prereq for clrs, it is sort of, but you could take them both concurrently if you had to, as clrs doesn't have such a strong focus on proofs (if you're interested, 6.045j is a good followup in automata/computability/etc, lots of regexes, state machines and turing machines)
anyhow, i just want to say that it's ok if you don't get it all at once. i think i ended up seeing lots of these ideas two or three times in a variety of classes. probably the first time i was just mechanically spitting out proofs without understanding them. by the third time i came across them, they actually clicked for me. But there was value (for me at least) to exposure early on because you do know the things that are hazy and it's easier to dive deeper on those the next time you encounter them.
have fun!