Logic for computing scientists
CS 251, Spring 2019
Columbia Gorge Community College
Hood River Indian Creek Campus
1730 College Way, Hood River, Oregon
TuTh 5:00pm–6:50pm HRC 303
CRN 1093967, 4 credits
Instructor
Robert Surton
rsurton@cgcc.edu
Office hours
MW 2:00–2:50pm, faculty office
Course description
Explores the fundamental logics used to model computing, including propositional logic, first-order logic, and first-order logic with equality. Introduces the skill to write formulæ that model real-world situations, manipulate them formally, and create simple proofs.
Prerequisites: CS 250.
Resources
Turing Award winners by year (notes)
- April 1
- Doug Engelbart, "A Research Center for Augmenting Human Intellect", a.k.a. The Mother of All Demos (reel 1 2 3)
- April 3
- Perlis, Alan J
- April 8
- Wilkes, Maurice V
- April 10
- Minsky, Marvin
- April 15
- Cerf, Vinton “Vint” Gray and Kahn, Robert “Bob” Elliot
- (Just a video in class, no reading other than bios.)
- April 17
- Dijkstra, Edsger Wybe
- April 22
- Knuth, Donald “Don” Ervin
- April 29
- Rabin, Michael O and Scott, Dana S
- (Read both bios and both papers.)
- May 1
- Backus, John
- May 8
- Floyd, Robert “Bob” W
- Iverson, Kenneth “Ken” E
- May 13
- C Antony “Tony” R Hoare
- May 15
- Cook, Stephen Arthur
- May 20
- Ritchie, Dennis M
- Thompson, Kenneth Lane
- May 22
- Wirth, Niklaus E
- May 29
- Karp, Richard “Dick” Manning
- June 3
- Hopcroft, John E
- Tarjan, Robert “Bob” Endre
- June 5
- Sutherland, Ivan
- June 10
- Allen, Frances “Fran” Elizabeth
- June 12
- Liskov, Barbara (before class, for discussion)
- Goldwasser, Shafi (in class)
Learning outcomes
Upon successful completion of this course, students will be able to:
- Use standard proof techniques and the technique of inductive proof to write short informal proofs about simple properties of numbers, sets, and ordered structures.
- Write simple formal proofs using basic inference rules of propositional logic, first-order logic, and first-order logic with equality.
- Apply the properties of propositional and first-order logic to: determine whether a wff is a tautology, a contradiction, or a contingency (valid, invalid or satisfiable).
- Construct equivalence proofs; and transform WFFs into conjunctive or disjunctive normal form.
- Transform simple English sentences into formal logic (propositional, first-order, or higher-order).
- Apply appropriate algebraic properties to: simplify Boolean expressions; simplify regular expressions; write recursive definitions for simple functions in terms of operations for abstract data types; write expressions to represent relations constructed in terms of operations for relational databases; and work with congruences.
Classroom expectations and policies
This is a work- and discussion-based class, and attendance is required. Your grade will be based on demonstrating your achievement of the course outcomes in class, and therefore participation is the only way to succeed. If you must miss a class, give me as much notice as you can and make a plan with me for how to make up your participation.
My classes are always safe space. The Advocates for Youth define a safe space as:
A place where anyone can relax and be fully self-expressed, without fear of being made to feel uncomfortable, unwelcome, or unsafe on account of biological sex, race/ethnicity, sexual orientation, gender identity or expression, cultural background, age, or physical or mental ability; a place where the rules guard each person's self-respect and dignity and strongly encourage everyone to respect others.
The policies of CGCC also apply.
It is important to me that students come to my classes eager to learn; if there is something in your life making it difficult to participate, please come to me. I will do what I can to make sure you can find the resources you need outside of class, in order to foster an energetic community inside of class.