Surprised to see Velleman's book so far down. It taught me that proofs are fun and do not in general require clever tricks. As a bonus, it provided plenty of practice with foundational objects such as sets, relations and functions. All this made me much better at doing mathematics and prepared to texts in real analysis, CS, algebra.