Honestly, I don't know whether logic really fits as a math skill or not, but I tend to lump most thinking skill / problem solving / logic activities together and call them math.  One of the things I've included on our problem solving days, even before my children could read, is the logic matrix. 

Here's an example from Mr. Meyers site.  He has a few more here.

My children have developed much critical thinking from this type of activity.  I'd like to share some of my resources thus far for really great logic matrixes.

Beginners:

Primarily Bears from AIMS  (this is a great source for other fun "thinking" math with manipulatives - mostly bears counters)

EdHelper

Older:

Mind Benders

http://schools.portnet.k12.ny.us/~mayerweb/Logic3rd/Web/wmatrixlogic.htm

http://scifiles.larc.nasa.gov/text/educators/activities/2000_2001/worksheets/logic_problems.html

My children love the challenge of the logic matrix.  They also love that they seemingly don't have to do "real" math when I plop these in front of them.  (If they only knew!)