Mathematical Logic

Comp520e Hui Li

Turing Machine

  1. Alan Turing
  2. Turing Machine, Abacus Machine
  3. A Doubling Turing Machine: Flow Chart, Results

Propositional Logic

  1. Formula, Tree Form, String Form, Formal Grammar
  2. Interpretation, Truth Table, Boolean Operators, Sets of Operators, Functional Completeness
  3. Logically Equivalent, Logical Equivalence Examples
  4. Satisfiable/Valid (Tautology)/Unsatisfiable/Falsible, Decision Procedures
  5. Satisfiability of a set of formulas, Logical Consequence, Semantic Tableaux
  6. Deductive Systems, Hilbert System, Variant Form of the Deductive Systems
  7. Resolution, Conjunctive Norm Form, Clausal Form, CNF to 3CNF
  8. Binary Decision Diagram, Efficient Truth Table, Reduced Binary Decision Diagram

First-Order Logic

  1. Sequence, Tuple, Cartesian Product, Relation, Function
  2. Generalization, Symbols, Formula, Open and Close, Formal Grammar
  3. Interpretation, Assignment and Truth Value, Ground, Validity and Satisfiability
  4. Interpretation for A Set of formulas
  5. Language of Arithmetic, Interpretation of Arithmetic Language, Syntax of Language
  6. Logical Equivalence, Logical Consequence, Logical Equivalence Examples
  7. Semantic Tableaux, Hilbert System
  8. PCNF, Clauses Form, Skolem's Theorem, Skolem's Algorithm
  9. Herbrand Models, Ground Resolution, Substitution, Unification

Prolog Programming

  1. Horn Clause
  2. SLD Resolution, Search Rules, SLD Tree
  3. Prolog Software: SWI Prolog
  4. Prolog Examples: Hanoi, Results; GK.2010.83

网站备案