Appunti di ripasso per l'esame di Logica per il corso di Informatica

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

DEFINIZIONI

Argument: Esso consiste in una sequenza di asserzioni che portano ad una

conclusione supportata da delle premesse. Questo termine può anche indicare gli

elementi contenuti in una atomic wff (es. LeftOf(x,a) – x, a sono arguments).

Sentence: Le atomic sentences sono la combinazione tra nomi e predicati, le

sentences sono formate da atomic sentences e connettivi booleani.

Logical consequence: Una sentence S è una logical consequence se è impossibile per

le premesse essere vere quando la conclusione è falsa.

Logical truth: Una logical truth è una sentence che è logical consequence di un set di

premesse.

Logical validity: Un argument è logicamente valido se la conclusione è una logical

consequence.

Logical equivalence: Due sentences sono logicamente equivalenti se hanno gli stessi

valori di verità in ogni possibile circostanza.

Tautological consequence: Una sentence S è una tautological consequence se in

ogni caso in cui la premessa sia vera, è vera anche la conseguenza.

Taut Con -> Log Con

Tautological equivalence: Due sentences Q e S sono tautologicamente equivalenti

se e solo se la loro joint table assegna gli stessi valori di verità a Q e S.

First Order consequence: Una sentence S è una conseguenza del primo ordine se è

conseguenza delle premesse solo in virtù del connettivi booleani, dell’identità e i

quantificatori. (Sostituzione delle sentence con altre senza senso)

First Order validity: Una sentence S è valida nel primo ordine se è una logical truth

solo in virtù dei connettivi booleani, dell’identità e i quantificatori. 1

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

Universal Elimination

| ∀xP(x)

|..

|..

|P(c) ∀-Elim

“ c ” è una costante che non è stata utilizzata altrove. L’universale ci permette d

introdurre un oggetto che possieda quella proprietà lì, in quanto appunto viene

soddisfatta universalmente.

Universal Introduction

|..

||[c] P(c)

||---------

||..

||..

||Q(c)

|∀x(P(x) → Q(x)) ∀-Intro

Oppure:

|..

||[c]

||--------

||..

||P(c)

|∀x(P(x) ∀-Intro 2

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

Existential Introduction

|S(c)

|..

|∃x S(x) ∃-Intro

Existential Elimination

|∃x S(x)

||[c] S(c)

||------------

||..

||..

||Q

|Q ∃-Elim

Ci sono almeno 2 cubi:

Cube(y) x ≠ y)

∃x∃y(Cube(x) ∧ ∧

Ci sono al massimo 2 cubi:

↔ (z=x z=y))

∃x∃y∀z(Cube(z) ∨ 3

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

FIRST ORDER SET THEORY

Naive Set Theory

Un insieme è una collezione di cose e segue i due assiomi:

Assioma di comprensione:

x a ↔ P(x) ]

∃a∀x[ ∈

Esiste un insieme i cui membri soddisfano la formula P(x)

Assioma di comprensione non ristretta:

x a ↔ P(x) ]

∀z … ∀z ∃a∀x[ ∈

1 n

Assioma di estensionalità:

Un insieme è completamente determinato dai suoi membri

a ↔ x b) → a=b ]

∀a∀b[ ∀x(x ∈ ∈

Se due insiemi hanno gli stessi elementi, allora sono lo stesso insieme.

Teorema dell’unicità

Per ogni wff P(x) possiamo provare che c’è un unico insieme di oggetti che soddisfa

P(x) …∀z x a ↔ P(x) ]

∀z ∃!a ∀x[ ∈

1 n

INSIEME VUOTO

L’insieme vuoto è di per se una contraddizione, ossia nessun oggetto deve

soddisfare P(x)

A = { x | x ≠ x } è l’insieme vuoto 4

UNIVR Logica I Simone Bersani - VR429587 A.A. 2018/19

SINGOLETTO

Se c’è uno e un solo