Portland Community College | Portland, Oregon

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

? Formulate, interpret, and apply properties of propositional and first-order predicate calculus in real world

contexts.          

? Use analytical problem solving strategies to solve problems using multiple approaches and to interpret the

results in practical terms.

? Utilize those techniques in discrete mathematics and logic that are used in the study and practice of computer

science.

? Be successful in subsequent coursework in the mathematical foundation of Computer Science.

Assessment must include:
1. At least two in-class proctored examinations, one of which may be the final exam, and
2. At least two of the following additional measures, where at least one includes writing:
a) Take-home examinations. (Group and/or individual)
b) Projects. (Group and/or individual)
c) Quizzes. (Group and/or individual)
d) Graded homework/worksheets.
e) In-class activities.
f) Attendance.

Major Topics:

·         Apply the properties of propositional calculus to: determine whether a wff is a tautology, a contradiction, or a contingency by truth tables and by Quine's method; construct equivalence proofs; and transform truth functions and wffs into conjunctive or disjunctive normal form.

·         Describe the basic inference rules and use them to write formal proofs in propositional calculus.

·         Apply the properties of first-order predicate calculus to: determine whether a wff is valid, invalid, satisfiable, or unsatisfiable; construct equivalence proofs; and transform first-order wffs into prenex conjunctive or disjunctive normal form.

·         Describe the rules of inference for quantifiers and use them along with the basic inference rules to write formal proofs in first-order predicate calculus.

·         Write formal proofs in first-order predicate calculus with equality.

·         Construct partial correctness proofs of simple imperative programs and construct termination proofs for simple loops.

·         Transform first-order wffs into clausal form; and unify atoms from a set of clauses.

·         Describe the resolution inference rule; use it to write formal proofs in first-order logic; and describe how resolution is used to execute a logic program.

·         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.