The Little Schemer <http://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/02...; and
Clause and Effect <http://www.amazon.com/Clause-Effect-Programming-Working-Prog....
Also a help is that the languages they use ('use' is a more appropriate word here than 'teach') — Scheme and Prolog, respectively — are much more mathematical in nature than typical mainstream languages are.
Sterling and Shapiro's _The Art of Prolog_ is also excellent, though you'll probably be better off reading _Clause and Effect_ first if you've never used Prolog. CAE is all about getting a feel for how Prolog operates, step-by-step* , while TAoP is about the logic programming paradigm, interspersed with project case studies and comparisons between Prolog (as an LP implementation with various compromises) and "pure" LP.
* This is the main thing it has in common with The Little Schemer: both begin by stepping through their respective languages' evaluation at a micro-level, until the semantics feel totally clear. This is especially helpful since Scheme and Prolog are both very different from the typical imperative/OO languages people know.
FWIW, The Little MLer is written in the same style as TLS, and is a good, lightweight introduction to ML's type system / static typing.