Found in 3 comments on Hacker News
parenthesis · 2010-07-21 · Original thread
Two good books which are in the sort of style you seek are:

The Little Schemer <; and

Clause and Effect <

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.

parenthesis · 2008-08-17 · Original thread
I've only dabbled in Prolog so far, but enough to be able to thoroughly recommend the book Clause and Effect by Clocksin. As one of the amazon reviewers says 'It serves roughly the same purpose for the Prolog language that "The Little Schemer" serves for Scheme.'

For a preliminary taste, this online tutorial seems quite good:

You might also like to look at this free book:

Fresh book recommendations delivered straight to your inbox every Thursday.