Foundations of Computer Science

• Exam 1, due 4/16/2001

  Discussion group for this class

  Exam 3:

  1. p. 336: 15.88, 15.89, 15.90
  2. Compute gcd(163125,2140) and integers X and Y such that
     163125X+2140Y=gcd(163125,2140)
  3. Prove Euclid's algorithm for Greatest Common Divisor for the ring Q[x] (polynomials on x with rational coefficients)
• Answer to question 5.8
• Textbook:
  • Title: A logical approach to discrete math
  • Authors: David Gries and Fred B. Schneider
  • Publisher: Springer-Verlag.
  • ISBN: 0-387-94115-0
  • Amazon web page for purchasing this text

Topics to be covered include:

• Chapter 1.
  • Role of logic in computer science.
  • Syntax vs. semantics. Leibniz Rule.
• Chapter 2.
  • Boolean expressions
  • Truth tables. States
  • Satisfiability, validity and duality.
  • Modeling English.
• Chapter 3. Propositional Calculus (0th order logic).
  • Basic manipulations: Leibniz rule, Transitivity and substitution.
  • Equivalence and true.
  • Negation, inequivalence and false.
  • Disjunction and conjunction. The Golden Rule.
  • Lemmas
  • Implication.
  • Normal forms.
• Chapter 4. Relaxing the proof style.
  • Extended deduction theorem.
  • Case analysis.
  • Conjunctive normal form and Automatic theorem proving
• Chapter 5. Applications of propositional calculus.
  The Otter System.
  • Solving word problems.
  • Combinatorial digital circuits.
• We will skip chapter 6
• Chapter 7. Formal logic. (We will only touch on this briefly)
  • Formal logic systems
  • Constructive logics
• Chapter 8. Quantification.
  • On types
  • Syntax and interpretation of quantification
  • Rules about quantification
• Chapter 9. Predicate calculus (first order logic).
  • Universal quantification.
  • Existential quantification.
  • English to predicate logic.
  • Applications to Database Queries

Links

• Logic programming links
• Otter Home Page
• Automated reasoning at Argonne National Labs
• Number theory tutorial
• Notes on number theory
• Notes on Galois Theory