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

60 views61 pages
SE112: Logic in Computer Science
Richard Trefler
September 14, 2009
Office hours: Monday and Wednesday, after class, DC2336, or by appointment
1
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 61 pages and 3 million more documents.

Already have an account? Log in
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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 61 pages and 3 million more documents.

Already have an account? Log in
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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 61 pages and 3 million more documents.

Already have an account? Log in

Document Summary

O ce hours: monday and wednesday, after class, dc2336, or by appointment. 2. 6. 2 temporal logic model checking of reactive programs . 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 di ereth 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. Logic: first used to demonstrate correctness of arguments. De nition 1. 0. 2 declarative sentence: a statement which in principle may be true or. Ambiguity in natural language can cause di culty determining if an argument holds. Eric does not believe that mary can pass any test. De nition 1. 0. 6 computer science: study and design of systems through the use of formal languages that are themselves formal systems.

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
Booster Classes
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
Booster Classes