Suppose you were teaching an introductory course on logic as part of a TCS curriculum. Furthermore, suppose that you had one week (= two 90 minute lectures) to spare for introducing Prolog on the basis of a theoretical discussion of predicate logic and (definite) logic programming. What would be the topics you'd pick apart from the syntax and procedural semantics of Prolog? Would you introduce SLDNF resolution first or by way of the cut-fail "construction" to implement negation in Prolog programs? What sort of examples would you choose for an audience made up of people who do not know automata and might not even know graphs? There has to be something better than "mere" logic puzzles for more elaborate examples.
My idea is to teach them enough to write simple provers for (fragments of) the systems of logic used elsewhere in the course. I had lots of experience writing interpreters from other courses in my curriculum, so I would have been prepared for that sort of approach. Introduce SLDNF as the basis of sketching the limitations of using prolog in such a fashion, so they can reason about what's going to be hard and what's going to be easy to do in prolog for the remainder of the course. Of course, my approach needs prolog to be introduced early instead of the last week. If you like this approach, I suggest giving them libraries to render the proof trees or whatever that you use in the rest of the course.