MATHEMATICAL LOGIC EXERCISES - UniTrento

M ATHEMATICAL L OGIC E XERCISES

Chiara Ghidini and Luciano Serafini

Anno Accademico 2013-2014

We thank Annapaola Marconi for her work in previous editions of this booklet.

Everything should be made as simple as possible,

but not simpler.

Reader¡¯s Digest. Oct. 1977

Albert Einstein

Contents

1 Introduction

3

2 Propositional Logic

5

2.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2 Truth Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3 Propositional Formalization . . . . . . . . . . . . . . . . . . . . .

10

2.3.1 Formalizing Simple Sentences . . . . . . . . . . . . . . . .

10

2.3.2 Formalizing Problems . . . . . . . . . . . . . . . . . . . .

17

2.4 Normal Form Reduction . . . . . . . . . . . . . . . . . . . . . . .

28

3 First Order Logic

31

3.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2 FOL Formalization . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4 Modal Logic

55

4.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.2 Satisfiability and Validity . . . . . . . . . . . . . . . . . . . . . .

63

4.3 Modal Logic Formalization . . . . . . . . . . . . . . . . . . . . . .

76

1

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download