Foundations of Computer Science C Edition by Alfred Aho and Jeffrey Ullman
Throughout most careers there comes a point in time where even as your experience grows in many areas, some of the less common but basic skills tend to wane. I believe in the importance of reviewing the foundations of your skills every so often. Every time I do, I feel I experienced a different perspective on a topic I once thought I learned long ago. Foundations of Computer Science, C Edition is a great book for this purpose.
The book covers such areas like induction, big oh notation, probability, graphs, trees, sets, lists, etc. It goes on to explain the relational data model behind the all the ubiquitous SQL used today. It explains the fundamentals of regular expressions via automata, touches on grammars and provides a thorough introduction to propositional and predicate logic.
Though the book is rather old, the lessons remain relevant today for a complete introduction to computer science.