MATHEMATICAL LOGIC EXERCISES

MATHEMATICAL LOGIC EXERCISES

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

Chapter 1

Introduction

Mathematics is the only instructional material that can be presented in an entirely undogmatic way.

The Mathematical Intelligencer, v. 5, no. 2, 1983

MAX DEHN

The purpose of this booklet is to give you a number of exercises on propositional, first order and modal logics to complement the topics and exercises covered during the lectures of the course on mathematical logic. The material presented here is not a direct component of the course but is offered to you as an incentive and a support to understand and master the concepts and exercises presented during the course.

Symbol

Difficulty

Trivial Easy Medium Difficult Very difficult

3

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

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

Google Online Preview   Download