SI242 Discrete Structures: Course Introduction

When you think of mathematics you probably think of calculus, since that is what you've been doing in math classes most recently. While calculus is certainly important in many areas of computer science, the kinds of mathematics we need most of the time as computer scientists is different. Of course we need algebra (everyone needs algebra!) but, beyond that, there are some crucial mathematical topics that we cover in this course:

• Proof - we need proofs to ensure our programs are correct, to analyze the performance of our procedures, to understand the problem domains our programs work in, and to do many other things.
• Logic - computers are, fundamentally, logical machines. We need to understand logic to understand how they work as physical devices, but we also need to understand logic to write our programs and for many more reasons ... including understanding proof.
• Number theory - primarily this means understanding integers. This seems like basic stuff, but in fact there is a lot to it. Integers are important to computing on many levels, but perhaps the easiest to understand up front is this: computers are powerful when they do things over and over again (we call this iteration) and it is the mathematics of the integers (not rational, real or complex numbers) that governs repeated action.
• Linear algebra - this means vectors and matrices. Many, many areas of computer science, including AI, machine learning, computer graphics, robotics, and cryptography, rely on linear algebra.
• Sequences, series, recurrence relations - as a process repeats, we typically have variables whose values are updated with each iteration. The values taken on by such a variable form a sequence, and understanding such sequences is key to understanding computer programs.

An anology to show what we hope to get from logic

Consider the following two high-school-ish word problems:

1. You have 16 horses to transport. You have one 4-horse trailer that you'll definitely use, and many 3-horse trailers at your disposal. How many 3-horse trailers will you need?
2. You're at the movie theater snack counter. You're definitely going to buy the \$4 coke, and you'd like to buy as many \$3 hot pretzles as possible. You have \$16. How many pretzles can you buy?

In both cases you map your problem to the equation 4 + 3*x = 16 and using your algebra skilz, solve for x. This value of x then gets mapped back to your "real world", either as horse trailers or pretzels.

  16 horses,
  1 4-horse trailer
  need x 3-horse trailers      need 4 3-horse trailers  <-- HORSE-WORLD
      |                                 ^              
      |                                 |
      V                                 |
    4 + 3*x = 16 -------------------> x = 4             <-- ALGEBRA-WORLD
      ^            algebraic stuff      |
      |                                 |
      |                                 V
  have $16                     can buy 4 $3 cokes       <--COKE-n-PRETZLE-WORLD
  1 $4 coke
  x $3 pretzles

What this tells us is that algebra is *universal*. You don't need special "horse-trailer math" or "coke-and-pretzel" math. This is the power of algebra, and this is why we take the trouble to map or model our real-world problems as algebraic equations. Logic works the same way. We map our real world problem to logic derive new true statements in logic, and map them back to the real world as new facts about that world.

Our Goal: we want an "algebra" for logical reasoning (as opposed to arithmetic reasoning)

Why are we as Computer Scientists studying logic?

The anology above (hopefully) gives you some insight as to what one generally would hope to get from studying logic. However, it is worth asking why for computer scientists studying logic is particularly important. So here are three broad ways computer scientists use logic. All three will be important over the course of your studies here and beyond. *

1. understanding logical arguments
   This is a life skill, obviously. But in Computer Science we are most often interested in logical arguments in the form of proofs: proofs about algorithms, for example, or proofs about the kinds of things we want to write programs to compute with.

   EXAMPLE PROBLEM ABOUT LOGICAL ARGUMENT
   Suppose traffic law in a town states:
   LAW: if 20 more more mph over speed limit, then fine must be greater than or equal to $150
   Consider the following two arguments (each is about a different scenario):
   ARG1: "My fine was less than $150, therefore I must not have been 20 or more mph over the limit!"
   ARG2: "Your fine was greater than or equal to $150, therefore you were speeding by 20 or more mph!"
   One of these arguments is logically sound, the other is flawed.  Which?  Why?  How to convince
   others that one is logically sound and the other is not?

2. modeling problem spaces and deducing new facts
   Just as algebra gives us a way of modelling problems about (think about your typical high school math "word problem"), logic gives us a way of modelling problems about true and false statements.

   EXAMPLE PROBLEM ABOUT MODELING AND DEDUCING NEW FACTS:
   Suppose a car is offered with various packages and options, with
   the following restrictions:
   1. the sport package requires ceramic brakes
   2. the sport package comes with rearwing and rear wing only comes with the sport package
   3. if turbo then the car can't have stock brakes
   4. ceramic brakes require the large wheels
   5. the only wheels are large wheels or regular wheels
   6. only base models (i.e. no packages) are available with regular wheels
   7. base models (i.e. no packages) don't have turbo
   8. the touring package comes with roof rack.
   	    
   Q1: "Can I have the turbo with regwheels?"
   Q2: "Can I have the turbo without having the rearwing?"

   Logic gives us a systematic way to model this problem space and answer these kinds of questions.
3. modeling programs & "gates" (the physical building blocks of computers)
   This is a special case of (2) that is particularly important to CS, and that is particularly easy in the sense that the worlds you are trying to model are very similar to propositional logic already.

   EXAMPLE PROBLEM REASONING ABOUT PROGRAMS:
   Here are three program snippets with different "if" conditions:
   
   if (!(a <= b || a != 0 && b == 0)) { DO THING X }
   
   if (a > b && (a == 0 || b != 0)) { DO THING X }
   
   if (a > b && b != 0) { DO THING X }
   
   Are these equivalent or do they actually behave differently?