I am yet to find a better introduction than Busby and Kolman's "Introductory Discrete Structures with Applications".
Beautifully written, concise, very accessible with the precise right amount of formalism.
http://books.google.com/books/about/Introductory_Discrete_St...