I'm suprised that no one has yet mentioned Boolos 'Computability and Logic'. The first 100 pages are pretty solid computability theoyr, and then follows Meta-logic, with an especially good précis on first-order logic that emphasizes the difference between a Language, an theory, and logical/non-logical symbols. Worth a gander, espeically if you're interested in CS related logic.

Robert Sores 'Recursively Enumerable Sets and Degrees' is another good place to start for recursion theory, as well as general logic. His approach is very clear (if a little assuming that you're following everything at once) and the first 120pp are very informative on recursively enumerable sets (now usually called computably enumerable). But for undergraduates, I'd go with the Boolos...

Note of warning - Mendelson's book Introduction to Mathematical Logic I found confusing when starting out - this was confirmed by supervisors/colleagues.

I hope this helps!

I'm surprised that no one has yet mentioned Boolos 'Computability and Logic'. The first 100 pages are pretty solid computability theory, and then follows Meta-logic, with an especially good précis on first-order logic that emphasizes the difference between a language, a theory, and logical/non-logical symbols. Worth a gander, especially if you're interested in CS related logic.

Robert Soare's 'Recursively Enumerable Sets and Degrees' is another good place to start for recursion theory, as well as general logic. His approach is very clear (if a little assuming that you're following everything at once) and the first 120pp are very informative on recursively enumerable sets (now usually called computably enumerable). But for undergraduates, I'd go with the Boolos...

Note of warning - Mendelson's book Introduction to Mathematical Logic I found confusing when starting out - this was confirmed by supervisors/colleagues.

I hope this helps!