## Introduction to logic

author: Alwen Tiu, Australian National University
published: April 1, 2009,   recorded: January 2009,   views: 5416
Categories
You might be experiencing some problems with Your Video player.

# Slides

0:00 Slides Introduction to Logic Logic and its applications in Computer Science Outline of the lectures Part I - Propositional Logic Propositional Logic Composing propositions The language of propositional logic Syntax vs Semantics Assigning truth values to formulae Boolean valuations and models Boolean functions Truth tables for standard connectives Statisfiability and validity Closure under substitutions Logical equivalence Some useful tautologies Normal forms - Some useful tautologies - Part 2 - Normal forms - Part 2 Negation normal form NNF Algorithm Conjunctive Normal Form CNF Algorithm (1) CNF Algorithm (2) - CNF Algorithm (1) - Part 2 Disjunctive Normal Form The resolution proof method A representation of CNF using sets The inference rule for resolution Saturated sets of clauses - The inference rule for resolution - Part 2 - Saturated sets of clauses - Part 2 Unsatis ability testing with resolutions - Saturated sets of clauses - Part 3 - Unsatis ability testing with resolutions - Part 2 Soundness and completeness of resolution Satis ability testing Heuristics for SAT solving Representing boolean functions Binary Decision Tree (BDT) Representing formulae as BDTs Example: a binary decision tree Binary Decision Diagram (BDD) Example: a BDD - Example: a binary decision tree - Part 2 - Example: a BDD - Part 2 Isomorphic BDDs Reduced BDD Example: a non-reduced BDD Example: a reduced BDD Reducing BDDs Dependency on variable ordering

# Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Part 1 56:22
!NOW PLAYING

Part 2 38:53

Part 3 49:25