Natural Sciences > Mathematics > Introduction to Logic
 Introduction to Logic  posted by  member150_php   on 4/3/2009 Add To Favorites
Abstract/Syllabus
Courseware/Lectures
Test/Tutorials
Webliography
More Options

Abstract/Syllabus:

## Introduction to Logic

#### Contents

The History of Logic                                          1

A Logic - patterns of reasoning                               1

A.2 Aristotle..........................................       2

A.3 Other patterns and later developments.....................4

B Logic — a language about something                          5

B.I Karly semantic observations and problems   ...............6

B.2 The Scholastic theory of supposition......................0

B-3 Intension vs. extension.................................. 0

B.4 Modalities.........................................       7

C Logic - a symbolic language                                 8

C. I The "lijjjvwrsviiiy characteristic language".............8

D 19th and 20th Century — mathematization of logic                                                    10

D.I George Boole........................................     10

D.2 Gottlob Frege.......................................     12

D.3 Set theory.........................................     II

D.4 20th century logic.....................................     15

E Modern Symbolic Logic                                                                                                   17

E.l Formal logical systems: syntax...............................     I 7

K.2 Formal semantics    .....................................     19

E.3 Compntability and Decidability    .............................     2[

F Summary                                                                                                                            24

Bibliography                                                                                                                           24

Part T. Basic Set Theory                                                                                           29

1.  Sets, Functions, Relations                                                                                               29

1.1.  Sets and Functions....................................     29

1.2.  Relations..........................................     33

L.3. Ordering Relations....................................     34

1.4. Infinities..........................................     3G

2.  Induction                                                                                                                            43

2.1.  Well Founded Orderings.................................     43

2.LI. Inductive Proof's on Well-founded Orderings..................    45

2.2.  Inductive Definitions...................................    48

2.2.1.  "I  I" Definitions..................................     50

2.2.2.  Inductive Definitions and Recursive Programming...............     52

2.2.3.  Proof's by Structural Induction..........................     54

2.3.  Transfinite Induction [optional..............................     58

Part TT. Turing Machines                                                                         6]

3.  Turing Machines                                                                                                                         61

3.1.  Alphabets and Languages.................................     Gl

3.2.  Turing Machines......................................     62

3.2.1.  Composing Turing machines...........................     66

3.2.2.  Alternative representation of TMs [optional     ..................     67

3.3.  Universal Tiring Machine.................................     68

3.4.  Decidability and the Halting Problem..........................     71

Part TTT. Statement Logic                                                                       75

4.  Syntax and Proof Systems                                                                                                      75

4.1.  Axiomatic Systems....................................     75

4.2.  Syntax of SL........................................     79

4.3.  The axiomatic system of Hilbert's............................     80

4.4.  Natural Deduction system    ................................     81

1.5.  Hilbert vs. ND.......................................     83

4.6.  Provable Kqui valence of formulae............................     8-1

1.7.  Consistency    ........................................     85

4.8.  The axiomatic system of Gent/.en's...........................     86

4.8.1.  Decidability of the axiomatic systems for SL..................     86

4.8.2.  Gent/.en's rules for abbreviated connectives...................     88

4.9.  Some proof techniques    ..................................     88

5.  Semantics of SL                                                                                                                            91

5.1.  Semantics of SL......................................     91

5.2.  Semantic properties of formulae.............................     9")

5.3.  Abbreviations.......................................     90

5.4.  Sets, Propositions and Boolean Algebras........................     97

o.l.l. Laws........................................     97

5.4.2.  Sets and SL.....................................     98

5.1.3.  Boolean Algebras [optional]............................    100

6.  Soundness and Completeness                                                                                               104

6.1.  Adequate Sets of Connectives    ..............................    101

6.2.  DNF, CNF.........................................    106

6.3.  Soundness.........................................    107

6.4.  Completeness    .......................................    109

6.4-1. Some Applications of Soundness and Completeness    ..............    112

Part TV. Predicate Logic                                                                       116

7.  Syntax and Proof System of FOL                                                                                         116

7.1.  Syntax of FOL.......................................    117

7.1.1. Abbreviations...................................    119

7.2.  Scope of Quantifiers, Free Variables, Substitution...................    I If!

7.2.1.  Some examples...................................    120

7.2.2.  Substitution....................................    122

7.3.  Proof System........................................    123

7.3.1. Deduction Theorem in FOL............................    124

7.4.  Gent/.en's system for FOL.................................    126

8- Semantics                                                                                                                                    130

8.1- Semantics of'FOL.....................................    130

8.2. Semantic properties of formulae.............................    13-1

8-3. Open vs. closed formulae.................................    135

8.3.1. Deduction Theorem in Q and A'.........................    137

9.  More Semantics                                                                                                                        140

9.1.  I'renex operations.....................................    110

9.2.  A few bits of Model Theory    ...............................    113

9.2.1.  Substructures    ...................................    143

9.2.2.  v.\\ classification    .................................    Ill

9.3.  "Syntactic" semantic and Computations    ........................    145

9.3.1. Reachable structures and Term structures....................    145

9-3-2. Herbrand's theorem................................    148

9.3.3.  Horn clauses and logic programming.......................    I 19

10.  Soundness. Completeness                                                                                                    155

10.1.  Soundness.........................................    loo

10.2.  Completeness.......................................    155

10.2.1. Some Applications................................    100

11. Identity and Some Consequences     .                                                                                164

I I.I. FOL with Identity.........]..........................    161

I I.I.I. Axioms for Identity    ...............................    105

11.1.2.  Some examples..................................    166

11.1.3.  Soundness and Completeness of FOL~.....................    IG7

11.2.  A few more bits of Model Theory............................    169

I 1.2.1. Compactness...................................    169

11.2.2. Skolem-Lowenheim................................    170

11.3.  Semi-Decidability and Undecidability of FOL.....................    170

11.4.  Why is First-Order Logic "First-Order"?    .......................    171

www.sharecourseware.org   Tell A Friend