Summer Preparation: Logic & Formal Reasoning

Logic is the foundation of mathematics and of programming.  CS 311H, which you will take during your first semester in the Turing Scholars Honors Program, will introduce you to logic as a language for thought, as well as techniques for using logic to prove theorems.  It will also introduce you to basic ideas of sets, functions and relations.  The class will start at the beginning, but it will move quickly, so you will have a much easier time in the class if some of the concepts are already familiar to you.

  • First, for motivation, you might want to take a quick look at Mathmatics as a Language.  It should dispel any doubts you have about the importance of logic as a language for concise, precise communication.
  • You may want to spend some time this summer getting comfortable with the basic notions and concepts of logic, sets, and functions. To help you do that, we've put together a set of resources for learning about them.
  • Along the way, you might enjoy trying some fun games to test your logical reasoning skills. No formal notation required for these. Just clear thinking.

Logic Resources

One way to learn logic is to read a book.  A very good book, which starts at the beginning and moves through to quite advanced concepts is Learning to Reason: An Introduction to Logic, Sets and Relations by Nancy Rogers.  It is targeted specifically at computer scientists, so it contains lots of examples of direct relevance to computer design and to programming.  But you don't need to spend the summer reading books.  The web is full of great resources for getting experience with the basic notions of logic, sets, and functions.  Check out Wikipedia's articles on:

Logic Games

There are some classic (meaning so simple they were around way before modern computers and fancy graphics) games and puzzles that can give you a chance to test your reasoning skills.  In all of these games, problem solving can be described as state space search.  At each move, you must choose from a fairly small (by the standards of living in the real world) set of legal moves.  Since any complete solution is a sequence of such moves, one way to think about finding a solution is to think something like, "Suppose I choose A first, then B, then C.  Will I win?"  Or, of course, you could try, "Choose A first, then B, then D."  And so forth.

There are two important things if you want to solve problems like this reasonably efficiently:

  • Most importantly: Try your options systematically so that you don't waste time trying redundant paths and you don't miss promising ones.
  • Use whatever constraints are available to rule out some paths without actually having to try them all.

Try these.  Remember, the goal is not just to get an answer but to get one in as few steps as possible.  Think about what you're doing.  Can you write out reasons for the moves you choose?