We propose a new approach to teaching discrete math: First, teach logic as a powerful and versatile tool for discovering and communicating truths; then use this tool in all other topics of the course. We spend 6 weeks teaching an equational style of propositional and predicate calculus, thereby ensuring that students gain a fluency in logical notation and some skill in its use. We teach basic heuristics for developing proofs, and we relate such proofs to more common informal proofs in mathematics. Then, we use logic extensively and rigorously in teaching topics like set theory, relations and functions, a theory of integers, induction, combinatorics, and solving recurrence relations. Success in teaching logic as a tool means that students lose their fear of mathematics and formalism, gain a positive view of rigorous proofs, learn to appreciate the use of syntactic manipulation, and begin using logic in other areas of study. Our experiences in teaching discrete math at Cornell shows that such success is possible.