Lambda the Ultimate

My best recommendation would be to see your local library and get a good book, but that might be my preference for books speaking.

If you have access to an academic library (at a University or research organisation) or a decent public library, they should have a selection of books introducing formal logic (they'll probably be catalogued under Philosophy, though you might find some under Mathematics or Computer Science). They tend to have titles like "An Introduction to Formal Logic", "A New Introduction to Formal Logic", or even just "Formal Logic". :-)

Online, MIT's 'Logic I' course is available (though I'm not sure how much material is provided). There is also Proof and Counterexample, but it isn't complete.

You'll probably need more than just propositional logic, so make sure you get a book that introduces first order logic (logic with predicates, quantifiers, etc) and possibly modal logic (logics of possibility, temporality, knowledge, belief, execution and pretty much anything else involving a concept similar to 'state').

The introductional course to logic I took used 'Logic in Computer Science' by Huth & Ryan, which I found to be quite good. Besides the usual propositional and predicate logic, it also covers some modal logic (but only epistemic it seems as I skim through it) and a little bit on program verification. Something like this should get you ready for the more interesting material.

(As for books on modal logic, Richard Zach has a short list on his weblog.)

You might find Logic: An Introduction to the Formal Study of Reasoning helpful. For a combined text and software approach, see Language, Proof, and Logic.

Seems pretty recent (2004). The Logical Foundations of Computer Science and Mathematics.

I found The Haskell Road to Logic, Maths and Programming pretty useful for brushing up on the basics, and it serves as a nice tutorial on Haskell too. Perhaps not enough depth for the topics you want to look into, though.