Natural deduction for propositional logic? Simple rules, real math. There are lots of good problems of varying difficulty in Logic in Computer Science by Huth and Ryan.

Edit: Perhaps this doesn't qualify as a game per se, but I think it might be a fun activity to work through the proofs together.