Propositional Logic: Deduction and Algorithms (Cambridge Tracts in Theoretical Computer Science, Series Number 48)

Here is an excellent introduction to classical logic, emphasizing the computational aspects. It addresses the question of whether or not one logical statement follows from another by examining algorithms that test this question in practice. The book moves into issues of complexity and algorithmic analysis that have traditionally not been considered the realm of mathematical logic, but which are vital in areas such as automated reasoning, knowledge engineering, logic programming and AI. These application areas are reflected in the two central themes of the book: satisfiability and derivability. To make the book suitable for teaching and for self-study, the authors provide a systematic account of theoretical results, as well as an exposition of those appropriate algorithms that incorporate them. The algorithms are illustrated with examples drawn from automatic theorem proving.