Bratko's "Prolog Programming for AI" is excellent, clear, lively, accessible. Sterling and Shapiro's "The Art of Prolog" is very good too, very thorough with the basic/foundational stuff.
Bratko was the one were it "clicked" for me. I took this slogan from him (don't remember if he wrote it or if I distilled it from his book somehow) - in Prolog, to understand the question is to have your answer. Writing down the question properly gives you a runnable program, more or less. I remember reading a page on AVL trees where he wrote down the definition, and I turned the page expecting to see the "solution". But it was already about something else. Turning the page back I realized, that the statement of what AVL trees were, was already the program itself.