Logica Matematica

Front 1

Proposizioni atomiche

Back 1

Predicati completamente istanziati:

Possono essere solo Vere o False.

In FOL si comportano come lettere proposizionali (P, Q, ...)

Hint 1

Più semplici frasi con senso compiuto: Vere o False in una data circostanza.

Si ottengono riempendo i posti dei predicati con dei sintagmi nominali

Front 2

Contesto

Back 2

Un insieme di circostanze. Gli si associa un linguaggio

Front 3

Sintagmi nominali

Back 3

Nomi o gruppi di nomi considerati come costanti

Front 4

Costanti

Back 4

Denotano gli oggetti del discorso.

(Nomi per indicare gli oggetti)

Front 5

Predicati (n-ari)

Back 5

Si usano per denotare relazioni fra oggetti. (o per definire delle proprietà)

Front 6

Linguaggio

Back 6

Dato da: costanti, predicati e funzioni

Front 7

Connettivi

Back 7

_ ∧ _ , _ ∨ _ , ¬ _ , ⊥ , _ ⟶ _ , _ ⟷ _

Costruiscono enunciati composti a partire da enunciati più semplici.

Front 8

Connettivo vero-funzionale

Back 8

Il valore di un enunciato è funzione dei valori di verità degli enunciati componenti. È quindi derivabile da una tavola di verità

Front 9

Conseguenza logica

Back 9

Q consegue logicamente da P₁ , ... , Pₙ in un contesto sse è vera in tutte le interpretazioni nel contesto in cui P₁ , ... , Pₙ sono vere:

P₁ , ... , Pₙ ⊨C Q.

Front 10

Conseguenza tautologica

Back 10

Q segue tautologicamente da P₁ , ... , Pₙ sse Q é vera in ogni interpretazione Booleana in cui P₁, ... , Pₙ sono vere:

P₁ , ... , Pₙ ⊨T Q.

Front 11

∧ Intro

Back 11

P₁ , ... , Pₙ ⊨ P₁ ∧ ... ∧ Pₙ

Front 12

∧ Elim

Back 12

P₁ , ... , Pₙ ⊨ P₁ ∧ ... ∧ Pₙ

Front 13

∨ Intro

Back 13

P₁ ⊨ P₁ ∨ ... ∨ Pₙ

Front 14

∨ Elim

Back 14

Dato P ∨ Q

Se P ⊨ C e Q ⊨ C

Allora C

Front 15

¬ Intro

Back 15

Se P ⊨ ⊥

Allora ¬P

Front 16

¬ Elim

Back 16

¬¬P ⟺ P

Front 17

⊥ Intro

Back 17

P, ¬P ⊨ ⊥

Front 18

⊥ Elim

Back 18

⊥ ⊨ qualsiasi enunciato

Front 19

Teorema di deduzione

Back 19

P₁ , ... , Pₙ ⊨ Q sse ⊨ (P₁ ∧ ... ∧ Pₙ) ⟶ Q

Hint 19

L'implicazione cattura la conseguanza (tauto)logica.

Front 20

De Morgan

Back 20

⊨ ¬(P ∧ Q) ⟷ (¬P ∨ ¬Q)

Front 21

Contrapposizione

Back 21

⊨ (P ⟶ Q) ⟷ (¬Q ⟶ ¬P)

Front 22

Modus Tollens

Back 22

¬Q, P ⟶ Q ⊨ ¬P

Front 23

Modus Ponens

Back 23

P, P ⟶ Q ⊨ Q

Front 24

Teorema di validità

Back 24

Se P₁ , ... , Pₙ ⊢ Q allora P₁ , ... , Pₙ ⊨ Q

Se abbiamo una prova in Fitch di Q da P₁ , ... , Pₙ è certo che Q è conseguenza tautologica di P₁ , ... , Pₙ

Front 25

Teorema di completezza

Back 25

Se P₁ , ... , Pₙ ⊨ Q allora P₁ , ... , Pₙ ⊢ Q

Se sappiamo che Q è conseguenza tautologica di P₁ , ... , Pₙ siamo certi che esiste una prova in Fitch di Q a partire da P₁ , ... , Pₙ

Front 26

Teoria (Γ)

Back 26

Insieme, eventualmente infinito, di euniciati.

Front 27

Quantificatori (FOL)

Back 27

∃: esiste almeno un, qualche, un, ...

∀: ogni, tutti, un (in senso qualsiasi)

Per essere usati hanno bisogno di una variabile e una formula

Front 28

Variabili

Back 28

Insieme finito di simboli, fissato arbitrariamente.

Hint 28

Sono dei "segnaposto" che servono a riferirsi allo stesso individuo in diverse parti di una formula.

Front 29

Funzioni

Back 29

Denotano oggetti in maniera indiretta

Front 30

Termini

Back 30

Dato un linguaggio L, sia C(L)={c₁, c₂, ...} l'insieme delle sue costanti e F(L)={f₁, f₂, ...} l'insieme dei suoi simboli di funzione.

L'insieme T(L) dei termini di L è definito induttivamente come segue:

-Ogni variabile x è un termine di L.

-Ogni costante c in C(L) è un termine di L.

-Se f è un simbolo di funzione n-ario e t₁, ... , tₙ sono termini di L, allora anche f(t₁, ... , tₙ) è un termine di L.

-Null'altro è un termine di L

Hint 30

Costruiti a partire da variabili, costanti e simboli di funzione.

Servono a denotare oggetti del discorso.

Front 31

Formule

Back 31

Dato un linguaggio L, sia T(L) l'insieme dei suoi termini e P(L)={P₁, P₂, ...} l'insieme dei suoi predicati.

L'insieme FBLF(L) delle fbf è definito induttivamente come segue:

-Se P è un predicato n-ario in P(L) e t₁, ... , tₙ sono termini di L allora P(t₁, ... , tₙ) è una fbf detta atomica.

-Se P e Q sono fbf di L, allora anche

e x è una variabile, allora anche P∧Q, P∨Q, ¬P, P⟶Q, P⟷Q, P, ⊥, sono fbf di L.

-Se P è una fbf di L, e x è una variabile, allora ∀x P e ∃x P sono fbf di L.

-Null'altro è fbf di L.

Hint 31

Vengono costruiti solo a partire dai termini usando: predicati, connettivi e quantificatori.

Servono a denotare frasi che possono essere vere o false in una data circostanza.

Front 32

Occorrenze di variabili libere

Back 32

Definizione induttiva:

Base: Le occorrenze di variabili libere in una atomica P(t₁, ... , tₙ) sono tutte le occorrenze di variabili in t₁, ... , tₙ (⊥ non ha occorenze di variabili libere)

Passo:

-Le occorenze di variabili libere in P∧Q, P∨Q, ¬P, P⟶Q, P⟷Q, sono tutte le occorrenze variabili in P e Q.

-Le occorenze di variabili libere in ∀x P e ∃x P sono tutte le occorenze di variabili libere in P, ad eccezione di x; ogni occorrenza di x in P è vincolata in ∀x P o ∃x P.

Front 33

Fbf chiuse

Back 33

Una fbf che non contiente variabili libere si dice chiusa.

(aperta altrimenti)

Nota! Non è possibile interpretare il significato di una fbf aperta in una data circostanza.

Front 34

Proposizione

(o enunciato)

Back 34

Una fbf è detta enunciato sse è chiusa.

Le proposizioni atomiche sono fbf chiuse.

Front 35

L-strutture

Back 35

Sia L un linguaggio dato da C(L), F(L), P(L).

Allora una L-struttra è una coppia di (U, I) dove:

-U è un'insieme non vuoto (uiniverso del discorso).

-I è la funzione "interpretazione" definita come segue:

-∀c ∈ C(L), I(c) ∈ U (I(c) è un elemento di U).

- ∀f ∈ F(L), I(f): Uⁿ⟶U (I(f) è una funzione n-aria su U).

-∀P ∈ P(L), I(P) ⊆ Uⁿ (I(P) è una relazione n-aria su U).

Front 36

Termini chiusi su Lu

Back 36

Sia L un linguaggio e S=(U, I) una L-struttura.

L'insieme GT(Lu) dei termini chiusi di Lu è definito induttivamente come segue:

-Ogni costante c ∈ C(Lu)=C(L) ∪ {ca: a∈ U} è un termine chiuso di Lu.

-Se f ∈ F(L) e t₁, ... , tₙ sono termini chiusi di Lu, allora anche f(t₁, ... , tₙ) è un termine chiuso di Lu.

-Null'altro è un termini chiuso di Lu.

Front 37

Interpretazione dei termini chiusi su Lu

Back 37

Sia L un linguaggio e S=(U, I) una L-struttura.

l'interpretazione I(t) con t∈ GT(Lu), è data induttivamente come segue:

-∀c ∈ C(L), I(c) è già definita

-∀a ∈ U, si pone I(ca) := a

-Se f ∈ F(L) e t₁, ... , tₙ∈ GT(Lu), allora I(f(t₁, ... , tₙ)) := I(f)(I(t₁), ... , I(tₙ)).

Front 38

Ogni P è Q

Back 38

∀x (P(x)⟶Q(x))

Front 39

Qualche P è Q

Back 39

∃x (P(x)∧Q(x))

Front 40

Nessun P è Q

Back 40

∀x (P(x)⟶¬Q(x))

Front 41

Qualche P non è Q

Back 41

∃x (P(x) ∧¬Q(x))

Front 42

Modello

Back 42

Una struttura S = (U,I) è un modello di un L-enunciato A sse A è vero in S, cioè I(A) = T. Si scrive:

S ⊨ A.

Front 43

L-teoria

Back 43

Un insieme di L-enunciati Γ è detto L-teoria.

Front 44

Modello di una teoria

Back 44

Una struttura S = (U,I) è un modello di una teoria Γ sse A è vero in S, ∀A ∈ Γ. Si scrive:

S ⊨ A.

Front 45

Contromodello di una teoria

Back 45

Una struttura S = (U,I) è un contromodello di una teoria Γ sse A è falsa in S perqualche A ∈ Γ.

Front 46

Verità logica (in FO)

Back 46

Un L-enunciato A è una verità logica (in FO) sse S ⊨ A per ogni L-struttura S = (U,I). In tal caso, si scrive:

⊨FO A.

Front 47

Vero in una L-teoria (in FO)

Back 47

Un L-enunciato A è vero in una L-teoria Γ (in FO) sse, per ogni l-struttura S = (U,I), vale che:

Se S ⊨ Γ , allora S ⊨ A.In tal caso si scrive:

Γ ⊨FO A.

Front 48

Atomica generalizzata

Back 48

Una fbf A è una atomica generalizzata sse A non è di una delle seguenti forme:

A = ¬B, A = B∧C, A = B∨C, A = B⟶C, A = B⟷C, A = Ʇ.

Front 49

Forma verofunzionale di un enunciato

Back 49

-fvf(P(t1, … ,tn)) = Q, dove Q è una lettera proposizionale fissata.

-fvf(Ʇ) = Ʇ

-fvf(¬A) = ¬fvf(A)

-fvf(A ∧ B) = fvf(A) ∧ fvf(B), fvf(A ∨ B) = fvf(A) ∨ fvf(B)

-fvf(A ⟶ B) = fvf(A) ⟶ fvf(B), fvf(A ⟷ B) = fvf(A) ⟷ fvf(B)

-fvf(∀x B ) = Q, dove Q è una lettera proposizionale .

-fvf(∃x B) = Q, dove Q è una lettera proposizionale.

Hint 49

La forma verofunzionale fvf(A) di un enunciato (o di una fbf) A si ottiene rimpiazzando ogni atomica generalizzata di A con una lettera proposizionale

Front 50

TAUT CON

Back 50

Permette di inferire un enunciato che segue dagli enunciati selezionati unicamente in virtù della semantica dei connettivi vero-funzionali.

Front 51

FO CON

Back 51

Permette di inferire un enunciato che segue dagli enunciati selezionati unicamente in virtù della semantica dei connettivi vero-funzionali, dei quantificatori e del predicato di identità.

Front 52

ANA CON

Back 52

Permette di inferire un enunciato che segue dagli enunciati selezionati in virtù della semantica dei connettivi vero-funzionali, dei quantificatori, del predicato di identità e dei predicati di TW.

Front 53

Particolarizzazione universale

∀ Elim

Back 53

Da ∀x P(x) possiamo inferire P(c).

Dove c è un termine chiuso (costante o composto)

Front 54

Generalizzazione esistenziale

∃ Intro

Back 54

Da P(c) possiamo inferire ∃x P(x).

Dove c è un termine chiuso (costante o composto)

Front 55

Generalizzazione universale

∀ Intro

Back 55

Si usa un nuovo nome per denotare un generico elemento del dominio che sia rappresentativo di «tutti».

In una sotto-prova dimostriamo P(c) con c generico, in modo da poter inferire ∀x P(x).

Front 56

Particolarizzazione esistenziale

∃ Elim

Back 56

Si usa un nuovo nome per denotare un generico elemento del dominioche esiste ma non conosciamo.

Eliminando ∃x P(x) assumiamo, in una sotto-prova, P(c) e il ragionamento deve andare bene per qalunque elemento.

Front 57

Rimpiazzamento

(o riscrittura)

Back 57

Se P ⟺ Q, possorimpiazzare P con Q in una formula F, ottenendo unaformula G tale che G ⟺ F

Front 58

De Morgan per i quantificatori

Back 58

¬∀x P(x) ⟺FO ∃x ¬P(x)

¬∃x P(x) ⟺FO ∀x ¬P(x)

∀x P(x) ⟺FO ¬∃x ¬P(x)

∃x P(x) ⟺FO ¬∀x ¬P(x)

Front 59

Spostare i quantificatori

Back 59

∀x (P(x) ∧ Q(x)) ⟺FO ∀x P(x) ∧ ∀x Q(x)

∃x (P(x) ∨ Q(x)) ⟺FO ∃x P(x) ∨ ∃x Q(x)

Front 60

De Morgan per i quantificatori, forme aristoteliche

Qualche P non è Q

Back 60

∃x (P(x) ∧ ¬Q(x))

⟺FO

∃x (¬P(x) ∨ ¬Q(x))

⟺FO

∃x ¬(P(x) ⟶ Q(x))

⟺FO

¬∀x (P(x) ⟶ Q(x))

Front 61

Scambiare i quantificatori

Back 61

∀x ∀y P(x,y) ⟺FO ∀y ∀x P(x,y)

∃x ∃y P(x,y) ⟺FO ∃y ∃x P(x,y)

Front 62

De Morgan per i quantificatori, forme aristoteliche

Nessun P è Q

Back 62

∀x (P(x) ⟶ ¬Q(x))

⟺FO

∀x (¬P(x) ∨ ¬Q(x))

⟺FO

∀x ¬(P(x) ∧ Q(x))

⟺FO

¬∃x (P(x) ∧ Q(x))

Front 63

Quantificazione vacua

Back 63

Se x non occorre libera in P allora: ∀xP ⟺FO P ⟺FO ∃xP.

Dunque:

∀x P(x) ⟺FO x P(x) ⟺FO x P(x) e

∃x P(x) ⟺FO x x P(x) ⟺FO x P(x).

x (P Q(x)) ⟺FO P x Q(x)x (P Q(x)) ⟺FO P x Q(x)

Front 64

Completezza formale

Back 64

Una teoria T si dice formalmente completa sse per ogni enunciato Q:

T |–FO Q o T |–FO ~Q

Front 65

Modello standard dell'aritmetica

Back 65

Il modello standard dell'aritmetica è N=(N,I) dove:

-I(0) = 0, I(s) = {(n, n+1) : n N},

-I(+) = {(m, n, m+n) : n, m N},

-I(×) = {(m, n, mn) : n, m N}.

Front 66

Teorema di Semidecidibilità

Back 66

Il teorema di semidecidibilità prova che non vi può essere un metodo algoritmico per elencare gli enunciati Q che non sono verità logiche.

Se ci fosse potrei decidere, per ogni enunciato Q, se è verità logica o no.

Front 67

Teorema di compattezza

Back 67

Sia T un insieme di l-enunciati (una teoria), eventualmente infinito, per qualche linguaggio L.

Se ogni sotto insieme di T ha un modello, allora anche T stesso ha un modello.

(Il viceversa è banale)