# CS 251 Discrete Structures II

(Syllabus written by Martin Cenek)

Term: Spring 2010
Credits: 4
CRN: (Section 002) 60791
Meeting Time: Mon, Wed 14:00-15:50
Meeting Location: CH (Cramer Hall) Room 50

Instructor: Bart Massey (bart AT cs DOT pdx DOT edu)
Office Hours: TBA
Office Location: FAB 120-18

TA: Martin Cenek (cenek AT cs DOT pdx DOT edu)
TA Office Hours: TBA
TA Office Location: EB 88-06 (Tutor Area / Linux Labs)

Prerequisite: CS 250 Discrete Structures I

## Disclaimer

Everything about this syllabus is entirely tentative, and maybe be changed at the whim of the instructor without warning.

## Description

CS 251 is the second term of the two term sequence CS 250-251. The main goal of the sequence is that students obtain those skills in discrete mathematics and logic that are used in the study and practice of computer science. A second goal is that students become familiar with symbolic algebra and logic programming as tools for doing laboratory experiments in discrete mathematics and logic. Logic: propositional calculus, first-order predicate calculus. Formal reasoning: natural deduction, resolution. Applications to program correctness and automatic reasoning. Introduction to algebraic structures in computing. Logic programming is introduced and used for programming experiments

### Topics

• Propositional logic: propositional calculus, normal forms, formal reasoning.

• First-order logic: first-order predicate calculus, equivalence, quantifier inference rules, equality.

• Automatic Reasoning: clausal forms, unification, resolution.

• Algebraic Structures: Boolean algebra, abstract data types.

### Goals and Objectives

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

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

• Describe the resolution inference rule, and use it to write formal proofs in first-order logic.

• Transform simple English sentences into formal logic.

• Apply appropriate algebraic properties to: simplify Boolean expressions; write recursive definitions for simple functions in terms of operations for abstract data types.

### Textbooks

Discrete Structures, Logic, and Computability, Third Edition. James L. Hein. Jones and Bartlett, 2002.

## Course Work

This course requires weekly readings, homework, and lab experiments. All coursework must be completed individually. I do encourage group collaboration. This means creating study groups, online chat-rooms to discuss the approach, understand the problem, methodology is acceptable and encouraged. The write up, programming, and actual solutions must be your individual work. If you represent someone else's work as your own, you are committing plagiarism.

### Attendance

Class attendance is not required, but VERY STRONGLY recommended. You are responsible to know ALL material discussed in the class (might not be in the book). There is no substitute for attendance.

### Test and Testing Policy

• Three tests will be given: two mid-term tests and one final test.

• No make up tests are given unless YOU arrange for them in advance.

### Homework

I will assign HW assignments every week - both as a study guide and as a small part of your grade. Complete the HWs before next class. These assignments will be collected using Blackboard, but will be graded only for having been turned in and having made a reasonable effort; the solutions will not be carefully checked. We will go through some of the problems during the class, as a part of the learning.

   Homework     25%
Midterm 1    20%
Midterm 2    20%
Final        35%


The midterms will be in-class exams.

### Make-ups

There will be no make up exams or homework deadlines except in a case of medical or family emergency. (The instructor reserves the right to request documentation in this case.) It is your responsibility to contact the instructor and arrange for special accommodations.

Cheating on homework or exams will result in a grade of zero on the affected material, and will be reported to your school/department. Plagiarism is a form of cheating.

Plagiarism: n 1: a piece of writing/work that has been copied from someone else and is presented as being your own work 2: the act of plagiarizing; taking someone's words or ideas as if they were your own.
—www.dictionary.com

If you use code, ideas, or text authored by someone else, cite them. It is OK to get help from external sources of knowledge, but citation is mandatory.

## Study Guide

• Study a little every day, you cannot learn the material in a day...

• Learn language - syntax, semantics, glossary of symbols and definitions.

• Do lots of problems, and then some.

• Do additional problems - ones that were not assigned.

• Make study groups.

• Make up your own problems and try to solve them.

• Start early on the assignments and the lab experiments.

• Review the topics frequently - not just the increments, review entire topics.

• Read the assigned chapters and lab manual before each lecture.

• Don't expect immediate success. Anything worthwhile takes time and effort