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
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.
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.
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)
- conjunctive normal form
- disjunctive normal form