[boris_m]

For category theory, I like Spivak's books.

For logic, it really depends of what you are searching for, for classical logic you can read the the classics, for example Russell and Tarski.

For constructive logic I cannot think of a good introduction (besides mine ;) ), I personally picked it up from books about category theory and computer science.