https://www.amazon.ca/Mathematical-Proofs-Transition-Advance...
Theorem: Let x be an integer. Then x^2 is even if and only if x is even
It seems so simple, and I think would be accessible to anyone who had completed high school algebra but I found that even having done those calculus and linear algebra courses, I had now idea how to go about actually PROVING this! The book however, goes through the thought process step by step, and teaching the skills needed to be able to understand the real math books like Rudin.
Here are some examples of the kinds of books I mean, and you can find others by following Amazon recommendations from those:
http://www.amazon.com/Nuts-Bolts-Proofs-Fourth-Edition/dp/01... http://www.amazon.com/Mathematical-Proofs-Transition-Advance...
With math textbooks especially, it pays to look for a previous edition, as the current edition can be ridiculously expensive, and the previous edition might be only 20% of the price, with no significant differences between the two.
Also, don't get them for the Kindle, as Amazon doesn't seem capable of publishing a math book with lots of notation that doesn't also have tons of errors where symbols get incorrectly imported. I've bought at least 20 and yet have to see one that didn't have lots of incorrect symbols.
Some suggestions to get you started:
Book of Proof by Richard Hammack: https://www.people.vcu.edu/~rhammack/BookOfProof/
Discrete Math by Susanna Epp: https://www.amazon.com/Discrete-Mathematics-Applications-Sus...
Mathematical Proofs: A Transition to Advanced Mathematics by Chartrand et al: https://www.amazon.com/Mathematical-Proofs-Transition-Advanc...
How to Think About Analysis by Lara Alcock: https://www.amazon.com/Think-About-Analysis-Lara-Alcock/dp/0...
Learning to Reason: An Introduction to Logic, Sets, and Relations by Nancy Rodgers: https://www.amazon.com/Learning-Reason-Introduction-Logic-Re...
Mathematics: A Discrete Introduction by Edward Scheinerman: https://www.amazon.com/Mathematics-Discrete-Introduction-Edw...
The Real Analysis Lifesaver: All the Tools You Need to Understand Proofs by Rafi Grinberg: https://www.amazon.com/Real-Analysis-Lifesaver-Understand-Pr...
Linear Algebra: Step by Step by Kuldeep Singh: https://www.amazon.com/Linear-Algebra-Step-Kuldeep-Singh/dp/...
Abstract Algebra: A Student-Friendly Approach by the Dos Reis: https://www.amazon.com/Abstract-Algebra-Student-Friendly-Lau...
That's probably plenty for a start.