Class Notes (1,100,000)
CA (620,000)
UW (20,000)
CS (1,000)
CS245 (70)
Lecture

CS245 Lecture Notes - Linear Temporal Logic, Temporal Logic, Modal Logic


Department
Computer Science
Course Code
CS245
Professor
Richard Trefler

This preview shows pages 1-3. to view the full 61 pages of the document.
SE112: Logic in Computer Science
Richard Trefler
September 14, 2009
Office hours: Monday and Wednesday, after class, DC2336, or by appointment
1

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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 Specific 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 SemanticTableaux ................................ 24
2.5 Extensions..................................... 27
2.5.1 Propositional Modal Logic . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.2 ReactiveSystem ............................. 31
2.5.3 Specifications for P1||P2......................... 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 Classification of Temporal Properties . . . . . . . . . . . . . . . . . . 36
2.6.4 Modal logic and Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 First Order Logic 39
3.1 PredicateLogic .................................. 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

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

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
You're Reading a Preview

Unlock to view full version