Summer Schools in Logic and Learning, Canberra 2009

Introduction to logic

author: Alwen Tiu, Australian National University
published: April 1, 2009, recorded: January 2009, views: 5416

Slides

Slides
0:00	Introduction to Logic
0:55	Logic and its applications in Computer Science
5:29	Outline of the lectures
6:30	Part I - Propositional Logic
6:33	Propositional Logic
7:50	Composing propositions
8:28	The language of propositional logic
10:18	Syntax vs Semantics
13:20	Assigning truth values to formulae
14:33	Boolean valuations and models
16:18	Boolean functions
16:55	Truth tables for standard connectives
17:50	Statisfiability and validity
20:29	Closure under substitutions
21:04	Logical equivalence
21:56	Some useful tautologies
25:50	Normal forms
26:45	- Some useful tautologies - Part 2
27:06	- Normal forms - Part 2
27:23	Negation normal form
28:55	NNF Algorithm
30:07	Conjunctive Normal Form
32:37	CNF Algorithm (1)
33:44	CNF Algorithm (2)
35:26	- CNF Algorithm (1) - Part 2
36:52	Disjunctive Normal Form
37:33	The resolution proof method
38:27	A representation of CNF using sets
40:27	The inference rule for resolution
41:36	Saturated sets of clauses
41:49	- The inference rule for resolution - Part 2
41:53	- Saturated sets of clauses - Part 2
42:26	Unsatisability testing with resolutions
42:49	- Saturated sets of clauses - Part 3
43:09	- Unsatisability testing with resolutions - Part 2
43:50	Soundness and completeness of resolution
44:31	Satisability testing
46:53	Heuristics for SAT solving
47:51	Representing boolean functions
48:50	Binary Decision Tree (BDT)
49:51	Representing formulae as BDTs
49:53	Example: a binary decision tree
51:25	Binary Decision Diagram (BDD)
51:33	Example: a BDD
51:39	- Example: a binary decision tree - Part 2
51:43	- Example: a BDD - Part 2
52:06	Isomorphic BDDs
53:36	Reduced BDD
53:54	Example: a non-reduced BDD
54:42	Example: a reduced BDD
55:22	Reducing BDDs
55:36	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.

Lecture popularity: You need to login to cast your vote.