Istituzioni di logica - riassunto

Le possibili liste di elementi di un insieme

1. Se n=1, l'insieme delle possibili liste di elementi di Α coinciderà con Α stesso. Perché sarà l'insieme di tutte le possibili liste contenenti ciascuna un solo elemento di Α. Ad esempio, quale sarà il significato di "essere rosso" riferito al dominio di "tutte le donne italiane"? Sarà il sottoinsieme delle "donne dai capelli rossi".

2. Se n=2, l'insieme delle possibili liste di elementi di Α consisterà nell'insieme di tutte le possibili liste contenenti ciascuna due elementi di Α. Ad esempio, quale sarà il significato di "amare" riferito al dominio di "tutti gli esseri umani"? Sarà il sottoinsieme di coppie costituito dalle coppie in cui il primo elemento ama il secondo.

3. Se n=3, l'insieme delle possibili liste di elementi di Α consisterà nell'insieme di tutte le possibili liste contenenti ciascuna tre elementi di Α.

Α → Α L'interpretazione associa ∈f F nAd ogni simbolo di funzione ( ) di arietà (( )=nβ f ) ( )I f :Una funzione ( ) che agisce sugli elementi dinΑ Agisce su 1 elemento di alla voltaΑ Se il simbolo di funzione ha arietà 1Agisce su coppie di elementi di Α Se il simbolo di funzione ha arietà 2 ΑE dà come risultato elementi di DUNQUE La funzione che costituisce il significato di un simbolof , di arietà 1Ha per dominio un insieme di individui E come codominio un insieme di individui La funzione che costituisce il significato di un simbolof , di arietà 2Ha per dominio un insieme di coppie di individuiE come codominio un insieme di individui Funzioni di ARIETÀ 0 Sono casi limite di funzioni → simboli di costantiindividualiSono cioè nomi per enti Il loro significato è l'ente stesso, designato

LEGENDAA =

struttura nel suo con quel nome ∈ Fcomplesso Se , è un elemento di( I c)0Α = dominio ΑA = metavariabile per Se è simbolo di costanteco La sua interpretazione è uno Αelemento di L LVERITÀ di una -formula in una -strutturaData una -struttura (quindi una interpretazione) per iL Ao Lsimboli di un linguaggio L AÈ possibile dire quali enunciati di sono veri in e qualinoDefiniremo la verità di un enunciato in una struttura sulla base dellao sua complessità ⊨A A A AQuindi definiremo se → è vero nella struttura Dando, in questo ordine, prima la verità di: Enunciati costituiti da simboli di predicato e termini Enunciati in cui compaiono connettivi Enunciati in cui compaiono quantificatoriVERITÀ DEGLI ENUNCIATI costituiti da SIMBOLI DI PREDICATO E TERMINI )P(t , … , tLa verità di enunciati 1 n( )P t , … ,tSe è → cioè:Ao 1 n Se

l'enunciato è costituito da un simbolo di predicato seguito da un numero di termini pari alla sua arietà. Sarà vero nella struttura se e solo se:

• Gli enti che costituiscono il significato dei termini
• Secondo l'interpretazione data nella struttura
• Appartengono all'insieme che dà il significato del simbolo di predicato (I ∈ P)

Quindi, significa che se e solo se:

(P(t, ..., t) ⊨ A P(t, ..., t))

Cosa significa che se e solo se:

(P(t, ..., t) ⊨ A P(t, ..., t))

è vero nella struttura Ao

(I(t, ..., I(t)) → è la lista dell'interpretazione dei termini

è l'interpretazione del simbolo di predicato (Po ∈ P)

Cioè, a seconda dell'arietà del predicato, sarà:

• Un insieme di enti
• Un insieme di coppie di enti
• Un insieme di terne di enti, ecc.

QUINDI significa che:

(P(t, ..., t) ⊨ A P(t, ..., t))

1A• L'enunciato non è vero nella struttura1⊨¬ ⊭A A A A se e solo se1 1VERITÀ DELLE FORMULE contenenti QUANTIFICATORI∀ xA• Una formula del tipo sarà vera nella struttura se e solo se:1Ogni enunciato che risulta dalla sostituzione di tutte le occorrenze dio Ax dentro con un elemento del dominio della struttura è vero1nella struttura⊨ ∀A x A• se e solo se:1⊨ (a / ∈A A x) a Aper ogni1 (a /x )A → significa l'enunciato che risulta1sostituendoIl nome dell'entea a• AAlla variabile inx• 1 ∈a A → significa che l'ente appartiene al dominioAdi∃ xA• Una formula del tipo sarà vera nella struttura se e solo se:1Almeno un enunciato che risulta dalla sostituzione di tutte leo Axoccorrenze di dentro con un elemento del dominio della1struttura è vero nella struttura⊨∃A x A• se e solo se:1⊨ (a / ∈A A x) a Aper qualche1• Necessità di

ampliamento del linguaggio

Nel caso di formule contenenti quantificatori, è necessario utilizzare la dicitura ∀x (a(x))

Questa però è senza senso → non è una formula

In quanto è un elemento del dominio di interpretazione A

E NON un simbolo del linguaggio ∈

Il linguaggio non ha a disposizione un nome per ogni a

È quindi necessario ampliare il linguaggio dando un nome per ogni a

Ampliamento del linguaggio elementare che diventa A

Che contenga un nome per ogni elemento del dominio della struttura

TEORIE, MODELLI e CONSEGUENZA LOGICA

Chiamiamo L-teoria un qualsiasi insieme di enunciati di L

Se T è una L-teoria si dice che:

⊨T è modello di → A ⊨T ∀x (a(x))

Qualora valga per ogni enunciato appartenente a T

T è soddisfacibile → Qualora abbia almeno 1 modello

⊨T A → A ⊨T T

che si legge,

è conseguenza logica diSignifica che è vera in ogni modello diA To• ⊨L A A A

Una -formula è logicamente valida qualora valga per ogniAFORMA NORMALE NEGATIVA

Una formula è in forma normale negativa(fnn) se e solo se non contieneimplicazioni e negazioniSolo di fronte a sottoformule atomicheo

A B A ↔ B

Due formule , sono logicamente equivalenti se e solo se èuna verità logica

Per trasformare una formula in una formula in fnnA A 'o Alogicamente equivalente ad

Bisogna eseguire delle trasformazioni secondo le seguentiregole di riscrittura

CALCOLO dei TABLEAUX

Un⋀(C¬(C → D) ¬ D)→ ⋁(C (¬C→ D) D)→¬¬C C→⋁ ⋀(¬C¬(C D) ¬ D)→⋀ ⋁(¬C¬(C D) ¬ D)→∀ ∃¬ xC x¬C→ ∀¬∃ xC x ¬C→

A Aenunciato è soddisfacibile se e solo se esiste una struttura tale che⊨A A

Il calcolo dei tableaux si occupa della

soddisfacibilità di enunciati ino fnn

Si prende in considerazione un albero di refutazione (=tableaux)I cui nodi sono degli ins