APPLIED LOGIC FOR COMPUTER SCIENCE, CS 2209B, Winter 2016-2017

Announcements

Course Outline

Final Exam - Sunday, April 23, 7pm-10pm.

Class schedule

Assignment submission

Hard copies can be dropped in the CS2209b locker 304 in Middlesex College, 3rd floor (diagonally across from the center elevator).

Assignments

Teaching Assistants

Zihao Wang zwang688@uwo.ca
Gurjit Randhawa grandha8@uwo.ca
Parisa Alvandi palvandi@uwo.ca
Andy Yu ayu82@uwo.ca

Office hours

Monday, 4:30pm-5:30pm, Gurjit Randhawa, MC4A
Tuesday, 1:30pm-2:30pm, Parisa Alvandi, MC4A
Tuesday, 2:30-3:30, Andy Yu, MC4A
Wednesday, 1:30pm-3:30pm, Lila Kari, MC385
Wednesday, 3:30-4:30pm, Zihao Wang, MC326

Recommended reading

J.Rubin. Mathematical logic: applications and theory, Saunders College Publishing, 1990.

Course Notes

#	Date	Notes	Topic
L01	Mon.Jan.9	Notes	Introduction
		Notes	What is a logical argument? Propositions. Logical connectives
		Exercises
L02	Wed.Jan.11	Notes	Propositional logic - Syntax
L03	Mon.Jan.16	Notes	Propositional logic - Semantics. Value assignments, tautologies, contradictions
		Notes, pages 1-7	Proving arguments valid
		Exercises 1 Exercises 2 Exercises 3 Exercises 4 Exercises 5
L04	Wed., Jan.18	Notes, pages 7-33	Proving arguments valid
L05	Mon., Jan.23	Notes, pages 1-10	Propositional calculus. Laws of propositional calculus.
		Exercises
L06	Wed., Jan.25	Notes, pages 11 - 28	Disjunctive Normal Form and Conjunctive Normal Form
L07	Mon., Jan.30	Notes	Adequate set of connectives
		Exercises
		Notes, pages 1-7	Formal deduction for propositional logic, introduction
L08	Wed., Feb.1	Notes, pages 8 - 27	Formal deduction for propositional logic
L09	Mon., Feb.6	Notes, pages 28 - 33	Proving essential laws of propositional logic by formal deduction
		Exercises
L10	Wed., Feb.8	Notes, pages 34-44	Soundness and completeness of formal deduction for propositional logic
		Notes	Logic gates and circuits
		Exercises
L11	Mon., Feb. 13	Notes, pages 1-43	Circuit minimization and Karnaugh maps
		Exercises
L12	Wed., Feb. 15		Midterm Review
L13	Mon. Feb 27	In-class Midterm Exam
L14	Wed., March 1	Notes, pages 44-48	Karnaugh maps in 4 variables
		Notes, pages 1-38, 46-51	Predicate calculus introduction
		Exercises
L15	Mon., March 6	Notes, pages 39-45, 52	Predicate calculus - bound and free variables
		Notes	Predicate calculus - syntax
L16	Wed., March 8	Notes	Predicate calculus - semantics
		Notes	Logical consequence in predicate calculus
		Exercises
L17	Mon., March 13	Notes	Formal deduction for predicate calculus - introduction
L18	Wed., March 15	Notes	Formal deduction for predicate calculus
L19	Mon., March 20	See Exercises from L14 and L16	Formal deduction for predicate calculus: Exercises.
L20	Wed., March 22	Notes	Artificial Intelligence: Resolution in propositional calculus. The Davis-Putnam algorithm
		Exercises
L21	Mon., March 27	Notes, pages 1-11	Resolution in predicate calculus: Prenex normal form
		Exercises
L22	Wed., March 29	Notes, pages 11-38	Existential-free prenex normal form, clauses, unification, resolution in predicate calculus
L23	Mon., April 3	Notes, pages 39--43	Strategies for resolution in predicate calculus
L24	Wed., April 5		Review for final exam

Previous years' homeworks, midterm test and final exam

Assignment 1 (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 2 (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 3 (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 4 (ps) , (pdf) / Solutions (ps) , (pdf)
Midterm exam (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 5 (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 6 (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 7 (ps) , (pdf) / Solutions (ps) , (pdf)
Assignment 8 (ps) , (pdf) / Solutions (ps), (pdf)
Final exam (ps) , (pdf) / Solutions (ps) , (pdf)

More of past years' assignments

Assignment 1 (ps) , (pdf) Solutions (ps) (pdf)
Assignment 2 (ps) , (pdf) Solutions (ps), (pdf)
Assignment 3 (ps), (pdf) , Solutions (ps) (pdf)
Assignment 4 (ps) , (pdf) For all problems in Assignment 4 use the 11 rules of formal deducibility and any of the theorems proved by the method of formal deduction. Solutions (ps) (pdf)
Assignment 5 (ps) , (pdf) Solutions (ps), (pdf)
Assignment 6 (ps) , (pdf) Solutions (ps) , (pdf)
Assignment 7 (ps) (pdf) Solutions (ps) , (pdf) Errata: In Question 3, part e), the third quantifier should be "there exists z" instead of "there exists x".
Assignment 8 (ps) , (pdf) Solutions (ps) (pdf)
Assignment 9 (ps) (pdf) Solutions (ps) , (pdf)
Assignment 10 (ps) (pdf) Solutions (ps) (pdf)

A few logic books

K.Rosen. Discrete mathematics and its applications , 7th edition, McGraw-Hill, 2012.

W.K.Grassmann, J. Tremblay, Logic and discrete mathematics: a computer science perspective , Prentice Hall, 1996.

H.J.Gensler. Logic: Analyzing and appraising arguments , Prentice Hall, 1989.

L. Zhongwan. Mathematical logic for computer science , World Scientific, 1989.

S.Burris. Logic for mathematics and computer science , Prentice Hall, 1998.

G.M.Schneider, J.Gersting (S.Baase contributing author) An invitation to computer science , West Publishing Company, 1995.

N.Nissanke, Introductory logic and sets for computer scientists , Addison Wesley, 1999.

R. Smullyan. What is the name of this book? : The riddle of Dracula and other logical puzzles , Prentice-Hall, 1978.

Lewis Carroll. The complete works of Lewis Carroll [pseud.] , Illustrated by John Tenniel. Introduction by Alexander Woollcott. Modern Library, 1979.

Lewis, Carroll. Mathematical recreations of Lewis Carroll [pseud.]. Dover Publications, 1958, V.1. Symbolic logic and The game of logic.-- v.2. Pillow problems and A tangled tale.

E.Mendelson, Introduction to mathematical logic , Van Nostrand, 1997, 4th edition.

H.Enderton. A mathematical introduction to logic , Academic Press, 1978.

D.Gries, F.Schneider. A logical approach to discrete math , Springer Verlag, 1994.