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ù dei 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.

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 di 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

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) ∨

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 sé una contraddizione, ossia nessun oggetto deve soddisfare P(x)

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

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

Singoletto

Se c’è uno e un solo