Appunti di Logica Matematica

INTRODUZIONE

La logica nasce ai tempi di Aristotele, con la teoria del sil- ogismo. La logica matematica è molto più recente. La logica aristotelica viene studiata con metodi matematici da Boole intorno alla metà dell'Ottocento. Alla fine dell'Ot- tocento risolve la logica applicata alla matematica da Frege.

Due concetti fondamentali:

• LOGICA E RAGIONAMENTO MATEMATICO: quando un ragionamento matematica è corretto?
• LOGICA E FONDAMENTI DELLA MATEMATICA: quali sono i fondamen- ti della matematica?

ESEMPIO 1 (Logica e ragionamento matematico)

Mostriamo che C_x (A ∧ B) = C_x (A) ∪ C_x (B) x ∈ C_x (A ∧ B) ⇔ x ∈ C_x e x ∉ A ∧ B ⇔ x ∉ C_x e non (x ∈ A ∧ B) ⇔ _{definizione di Cx} ⇔ x ∈ C_x e non (x ∈ A e x ∈ B) ⇔ x ∈ C_x e (x ∉ A oppure x ∈ B) ⇔ _{passaggio logico} ⇔ (x ∈ C_x ∧ x ∉ A) oppure (x ∈ C_x e x ∉ B) ⇔ x ∈ C_x (A) ∪ C_x (B)

Nel esempio 1 abbiamo utilizzato tre CONNETTIVI LOGICI non (cometrivo) monocomponenziale indicato con ¬), oppure (cometitivo biargomentale indicato con v), e ∧ (connettivo biargomentale indicato con ∧). Oppure può essere inte- so in due modi diversi:

1. "aut" oppure esclusivo (uno o l'altro, ma non entrambi);
2. "vel" oppure inclusivo (uno, l'altro e entrambi)

con "oppure" intenderemo sempre "vel" o "∨".

Abbiamo poi il connettivo condizionale A ⇒ B (da leggera "A solo se B", scomponidati "se A allora B"). Infine c'è il connettivo bicondizionale A ⇔ B ("A se e solo se B").

Tratteremo una logica a due valori di verità: una PRO- POSIZIONE è vera (1, vero) o falsa (0, falso). Ricordiamo che esistono logiche con più di due valori di verità (magari infiniti).

∼(A∧B)⇔(∼A)∨(∼B),

∼(A∨B)⇔(∼A)∧(∼B),

A∧(B∨C)⇔(A∧B)∨(A∧C)

sono esempi di proposizioni. Chiamiamo TAUTOLOGIA una proposizione che assume sempre valore vero.

Non confondiamo → e ↔ con ⇒ e ⇔ che sono simboli del METALINGUAGGIO. Ecco un esempio di utilizzo congiunto di → e ⇒:

A⇒B tautologia ⇒⇒ B tautologia

A tautologia

ESEMPIO 2:

(logica e fondamenti della matematica)

Trattiamo la famosa "antinomia di Russell" (1902)

Sia R={x:x ∉ x} e ci chiediamo se R ∈ R. Si ha

R ∈ R → R ∉ R

R ∉ R → R ∈ R.

Non è possibile risolvere il problema dicendo che R non esiste, infatti per Frege data qualunque proprietà P l'insieme {x:P(x)} esiste.

ESEMPIO

Un'altra antinomia è quella dell'"eterologico".

Diciamo che un aggettivo è "autologico" se si applica a se stesso (ad esempio "plurilibrico"), diciamo che un aggettivo è "eterologico" se non si applica a se stesso (ad esempio "verde").

L'antinomia sta nella questione se l'aggettivo "eterologico" sia autologico o eterologico. Si giunge alla seguente conclusione: "eterologico è autologico se e solo se è eterologico".

ESEMPIO

Proviamo che esistono a e b irrazionali t.c. a^b ∈ ℚ.

Prendiamo a=b=√2. Se √2^√2 ∉ ℚ abbiamo concluso.

Se √2^√2 ∉ ℚ basta scegliere a=√2^√2, b=√2 ⋅ è certamente non raro a^b = √2^√22 = 2 ∈ ℚ.

Quindi i due numeri esistono, anche se non sappiamo dire quale dei due essi si verifica.

ESEMPIO

A B (A→B) ↔ (∼A→B)

• V V V F
• V F F V
• F V V V
• F F V V

il connettivo principalein questo caso è ↔

A B (A→B) ↔ (∼B→∼A)

• V V V V
• V F F F
• F V V V
• F F V V

questa formula è una tautologia

Le tautologie costituiscono un insieme decidibile all'internodell'insieme ambiente delle formule.Provare che una formula è una tautologia tramite le tabellepuò essere dispendioso. Vediamo un altro modo.

ESEMPIO

Proviamo che è una tautologia la formula seguente:(A→(B→C))→((A→B)→(A→C)).Supponiamo la formula falsa e troviamo un assurdo. Ilconnettivo principale è il condizionale che ha il vantaggiodi essere falso una sola volta (quando l'antecedente è veroe il conseguente è falso).Schematizziamo:

(A (∗) (B → C)) → ((A → B) → (A → C))

• V (1)
• V (5)
• F (6)
• F (1) V (2)
• F (4) V (4)
• V (3) F (3)
• F (1) V (2)
• V (3) F (3)
• V (4) V (4)

Al settimo passaggio si trova che (∗) è falsa, ma questo èun assurdo (V ⊢ 1). Pertanto la formula è una tautologia.

Abbiamo già visto che {∼, ∧, ∨} è una base.

D'altra parte, se D è una funzione di verità entro D contenente ∼, ∧, ∨, che determina f, f può essere definito da ∼ ed A sfruttando la tautologia ∼(A₁ A₂ ⇔ (∼A₁ ∧ ∼A₂).

Sostituendo in D ogni sottformulo del tipo ∼(z₁ ∨ z₂) con la formula ∼ (∼z₁ ∧ ∼z₂, ad essa equivalente si ottiene D₁ contenente ∼ solo ed A equivalente a D. Pertanto {∼, ∨} è una base.

Per mostrare che {∼,∨} è una base si sfrutta la tautologia A₁ A₂ ⇔ (∼A₁ ∧ ∨A₂).

Esempio

{∼, →} è una base di connettivi. Per vederlo, definiamo ∧ e ∨ a partire da ∼, →:

• A ∨ B def ⇔ ∼A → B, A ∧ B def ⇔ (A → ∼B)

Osserviamo che A → B equivale a ∼(A ∧ ∼B). Allora A ∧ B equivale a ∼(A → B), quindi A ∧ B equivale a ∼(A → ∼B). Inoltre (De Morgan) ∼(A ∧ ∼B) equivale a ∼A ∨ B, quindi A ∧ B equivale a ∼A ∨ B. Perciò A ∧ B equivale a ∼A → B.

Esempio

{NAND} e {NOR} sono basi di connettivi e sono le uniche basi formate da un solo connettivo.

Per vedere che sono basi osserviamo che sono tautologhe le formule seguenti:

1. ∼ A ⇔ A NAND A
2. ∼ A ⇔ A NOR A
3. A ∧ B ⇔ (A NAND (B NAND B))

Trattiamo adesso l'unicità. Sia ^* un connettivo bianrio mentale t.c. {*} sia una base. Proviamo che * coincide con NAND oppure con NOR.

Passo 1. Proviamo che Γ ⊢_K λ → β_i ammettendo l'ipotesi induttiva che Γ ⊢_K λ → β_j, per ogni j < i.

β_i può essere β_i ∈ Γ ∪ {ζ}.

Ottenuta da β_H e β_K per HP (h, k < i).

I primi due casi sono analoghi a quanto visto per β₁.

La derivazione della β_i ottenuta per HP da β_H e β_K. La derivazione sarà la seguente:

β_HK

β_K = β_H → β_i

β_i

Per ipotesi induttiva Γ ⊢_K λ → β_K e

Γ ⊢_K λ → (β_H → β_i)

Costruiamo la derivazione seguente:

λ → β_H {derivazione di λ → β_H da Γ}

λ → (β_H → β_i) {derivazione di λ → (β_H → β_i) da Γ}

λ → β_H → β_i

(λ → β_H → β_i) → (λ → β_H) → (λ → β_i) (assioma 2)

(λ → β_H) rarr; (λ → β_i) (MP)

λ → β_i (MP)

OSSERVAZIONI (sul teorema di deduzione)

1. Il viceversa del teorema è banale:

λ → β {derivazione di λ → β da Γ}

λ → β

β (MP)

2. Il teorema di deduzione offre una duplice semplificazione di derivazioni e dimostrazioni:
• (a) la formula da derivare è più facile;
• (b) abbiamo un'ipotesi in più;
3. Il teorema di deduzione è un metateorema.