Logic for Computing Scientists

Course Number: CS 251
Transcript Title: Logic for Computing Scientists
Created: February 17, 2015
Updated: July 10, 2015
Total Credits: 4
Lecture Hours: 40
Lecture / Lab Hours: 0
Lab Hours: 0
Satisfies Cultural Literacy requirement: No
Satisfies General Education requirement: No
Grading options: A-F (default), P-NP, audit
Repeats available for credit: 0

Prerequisites

Course Description

Explores the fundamental logics used to model computing, including propositional logic, first-order logic, and first-order logic with equality. Introduces the skills to write formulae that model real-word situations, manipulate them formally, and create simple proofs. Prerequisite: CS 250. Audit available.

Intended Outcomes

Upon successful completion of this course, students will be able to:

  1. Use standard proof techniques and the technique of inductive proof to write short informal proofs about simple properties of numbers, sets, and ordered structures.
  2. Write simple formal proofs using basic inference rules of propositional logic, first-order logic, and first-order logic with equality.
  3. 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).
  4. Construct equivalence proofs; and transform WFFs into conjunctive or disjunctive normal form.
  5. Transform simple English sentences into formal logic (propositional, first-order, or higher-order).
  6. 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.

Outcome Assessment Strategies

Homework, observation, class discussion, examination.

Course Activities and Design

Lecture, in-class and out-of-class assignments, discussion and examination.

Course Content (Themes, Concepts, Issues and Skills)

  • logic
    • propositional
    • first-order
  • proof
  • induction
  • expressions
    • tautologies
    • contradictions
    • contingencies
    • conjunctive normal form
    • disjunctive normal form