I found "A Logical Approach to Discrete Math" by Gries and Schneider to be delightful. It teaches discrete math using formal logic as the basis of the whole system.

http://www.amazon.com/Logical-Approach-Discrete-Monographs-C...