[PDF] MATHEMATICAL LOGIC EXERCISES 8. 7. Page 12. Propositional

View - Download MATHEMATICAL LOGIC EXERCISES

Previous PDF

Next PDF

MATHEMATICALLOGICEXERCISESChiara GhidiniandLuciano Serafini

Anno Accademico 2013-2014

We thankAnnapaola Marconifor 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

Mathematics is the only

instructional material that can be presented in an entirely undogmatic way.The Mathematical

Intelligencer, v. 5, no. 2, 1983

MAXDEHNChapter 1

Introduction

The purpose of this booklet is to give you a number of exercises on proposi- tional, first order and modal logics to complement the topics and exercises covered during the lectures of the course onmathematical logic. The mate- rial 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.SymbolDifficulty ?Trivial ?Easy ?Medium ?Difficult ?Very difficult 3

When you have eliminated the

impossible, what ever remains, however improbable must be the truth.The Sign of Four.

SIRARTHURCONANDOYLEChapter 2

Propositional Logic

2.1 Basic Concepts

Exercise 2.1.?-

Which of the following are well formed propositional formulas? 1._pq

2.(:(p!(q^p)))

3.(:(p!(q=p)))

4.(:((q_p)))

5.(p^ :q)_(q!r)

6.p:r

Solution.

Well formed formulas: 2. and 5.

5

Propositional Logic

Exercise 2.2.?-

Let"s consider the interpretationvwherev(p) =F,v(q) =T,v(r) =T. Doesvsatisfy the following propositional formulas?

1.(p! :q)_ :(r^q)

2.(:p_ :q)!(p_ :r)

3.:(:p! :q)^r

4.:(:p!q^ :r)

Solution.

vsatisfies 1., 3. and 4. vdoesn"t satisfy 2.

2.2 Truth Tables

Exercise 2.3.?-

Compute the truth table of(F_G)^ :(F^G).

Solution.FGF_GF^G:(F^G)(F_G)^ :(F^G)TTTTFF

TFTFTT

FTTFTT

FFFFTF

+The formula models an exclusive or! ]6

2.2 Truth Tables

Exercise 2.4.?-

Use the truth tables method to determine whether(p!q)_(p! :q)is valid.

Solution.pqp!q:qp! :q(p!q)_(p! :q)TTTFFT

TFFTTT

FTTFTT

FFTTTT

The formula is valid since it is satisfied by every interpretation.

Exercise 2.5.?-

Use the truth tables method to determine whether(:p_q)^(q! :r^:p)^(p_r) (denoted with') is satisfiable.

Solution.pqr:p_q:r^ :pq! :r^ :p(p_r)'

TTTTFFTF

TTFTFFTF

TFTFFTTF

TFFFFTTF

FTTTFFTF

FTFTTTFF

FFTTFTTT

FFFTTTFF

There exists an interpretation satisfying', thus'is satisfiable. ]7

Propositional Logic

Exercise 2.6.?-

Use the truth tables method to determine whether the formula':p^:q!p^q is a logical consequence of the formula ::p.

Solution.pq:pp^ :qp^qp^ :q!p^qTTFFTT

TFFTFF

FTTFFT

FFTFFT j='since each

interpretation satisfyingpsisatisfies also'.

Exercise 2.7.?-

Use the truth tables method to determine whetherp!(q^ :q)and:pare logically equivalent.

Solution.pqq^ :qp!(q^ :q):pTTFFF

TFFFF FTFTT

FFFTTThe two formulas are equivalent since

for every possible interpretation they evaluate to tha same truth value.

Exercise 2.8.?

Compute the truth tables for the following propositional formulas:8

2.2 Truth Tables

(p!p)!p p!(p!p) p_q!p^q p_(q^r)!(p^r)_q p!(q!p) (p^ :q)_ :(p$q)

Exercise 2.9.?

Use the truth table method to verify whether the following formulas are valid, satisfiable or unsatisfiable: (p!q)^ :q! :p (p!q)!(p! :q) (p_q!r)_p_q (p_q)^(p!r^q)^(q! :r^p) (p!(q!r))!((p!q)!(p!r)) (p_q)^(:q^ :p) (:p!q)_((p^ :r)$q) (p!q)^(p! :q) (p!(q_r))_(r! :p) ]9

Propositional Logic

Exercise 2.10.?

Use the truth table method to verify whether the following logical consequences and equivalences are correct: (p!q)j=:p! :q (p!q)^ :qj=:p p!q^rj= (p!q)!r p_(:q^r)j=q_ :r!p : (p^q) :p_ :q (p_q)^(:p! :q)q (p^q)_r(p! :q)!r (p_q)^(:p! :q)p ((p!q)!q)!qp!q

2.3 Propositional Formalization

2.3.1 Formalizing Simple Sentences

Exercise 2.11.?-

Let"s consider a propositional language where

pmeans"Paola is happy", qmeans"Paola paints a picture", rmeans"Renzo is happy".

Formalize the following sentences:10

2.3 Propositional Formalization

1."if Paola is happy and paints a picture then Renzo isn"t happy"

2."if Paola is happy, then she paints a picture"

3."Paola is happy only if she paints a picture"

Solution.

1.p^q! :r

2.p!q

3.:(p^ :q)..which is equivalent top!q

+The precision of formal languages avoid the ambiguities of natural lan- guages.

Exercise 2.12.?-

Let"s consider a propositional language where

pmeans"xis a prime number", qmeans"xis odd".

Formalize the following sentences:

1."xbeing prime is a sufficient condition forxbeing odd"

2."xbeing odd is a necessary condition forxbeing prime"

Solution.1. and 2.p!q

]11

Propositional Logic

Exercise 2.13.?-

LetA="Aldo is Italian"andB="Bob is English".

Formalize the following sentences:

1."Aldo isn"t Italian"

2."Aldo is Italian while Bob is English"

3."If Aldo is Italian then Bob is not English"

4."Aldo is Italian or if Aldo isn"t Italian then Bob is English"

5."Either Aldo is Italian and Bob is English, or neither Aldo is Italian nor

Bob is English"

Solution.

quotesdbs_dbs47.pdfusesText_47

[PDF] maths exercice 1ère S

[PDF] maths exercice 1ère s , tableau de variations de fonctions

[PDF] MATHS Exercice 2nde

[PDF] MATHS EXERCICE 3EME

[PDF] maths exercice d'équation

[PDF] Maths exercice Devoir Maison

[PDF] Maths exercice droite graduée

[PDF] Maths exercice eee

[PDF] Maths exercice éoliennes

[PDF] Maths exercice équation de droites

[PDF] Maths Exercice factorisation

[PDF] Maths exercice fonction polynôme

[PDF] maths exercice maths phare

[PDF] Maths exercice seconde

[PDF] maths exercice sur moyenne et ecart types