Class Notes (837,186)
Canada (510,155)
CS 245 (33)
Lecture

Full lecture set Full lecture set including Hilbert style proof axioms

61 Pages
272 Views
Unlock Document

Department
Computer Science
Course
CS 245
Professor
Richard Trefler
Semester
Fall

Description
SE112: Logic in Computer Science Richard Tre er September 14, 2009 Oce hours: Monday and Wednesday, after class, DC2336, or by appointment 1 Fubrub SE112 September 14, 2009 Table of Contents 1 Introduction: Logic History 4 2 Propositional Logic 6 2.1 Syntax, Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Specic Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Syntax of Propositional Logic . . . . . . . . . . . . . . . . . . . . . . 6 2.1.3 Semantics of Propositional Logic . . . . . . . . . . . . . . . . . . . 10 2.2 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 . 2.3 Proofs, Soundness of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1 Hilbert Style Proof System . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Semantic Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 . 2.5.1 Propositional Modal Logic . . . . . . . . . . . . . . . . . . . . . . . .27 2.5.2 Reactive System . . . . . . . . . . . . . . . . . . . . . . . . . . . 31. 2.5.3 Specications for P1jjP2 . . . . . . . . . . . . . . . . . . . . . . . .33 2.6 Propositional Linear Temporal Logic . . . . . . . . . . . . . . . . . . . . . . 33 2.6.1 Semantics of Linear Temporal Logic . . . . . . . . . . . . . . . . . . . 34 2.6.2 Temporal logic model checking of reactive programs . . . . . . . . . . 35 2.6.3 Classication of Temporal Properties . . . . . . . . . . . . . . . . . . 36 2.6.4 Modal logic and Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 First Order Logic 39 3.1 Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39. 3.2 Relations between Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2.1 The Language of Predicate Logic . . . . . . . . . . . . . . . . . . . . 41 3.2.2 Predicate Logic Semantics . . . . . . . . . . . . . . . . . . . . . . . .43 3.3 Extensions to First Order Logic . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4 Second Order Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . .56 2 Fubrub SE112 September 14, 2009 4 Analysis of Sequential, Transformational programs 57 4.1 Grammar Generating Integer Expressions . . . . . . . . . . . . . . . . . . 57. 4.2 Grammar Generating Boolean Expressions . . . . . . . . . . . . . . . . . . 57 3 Fubrub SE112 September 14, 2009 1 Introduction: Logic History We will use the formal, descriptive languages of modern language to study and understand computational models and the problems that can be solved by computation. \Logic diereth from rhetoric ... in this, that logic handleth reason exact and in truth, and rhetoric handleth it as it is planted in popular opinion and manners." - Francis Bacon (1605) Logic: First used to demonstrate correctness of arguments. Example 1.0.1 All men are mortal. ! Declarative Sentence Socrates is a man. ! Declarative Sentence Therefore, Socrates is mortal. ! Declarative Sentence The entire example represents a logical argument. Denition 1.0.2 Declarative Sentence: A statement which in principle may be \true" or \false" History goes back to ancient greeks. What happens when we replace All men are mortal with Some men are mortal Ambiguity in natural language can cause diculty determining if an argument holds. Example 1.0.3 Eric does not believe that Mary can pass any test. Example 1.0.4 This sentence is a lie 4
More Less

Related notes for CS 245

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit