LOGICA

La logica è una disciplina che studia i principi del ragionamento corretto e le strutture del pensiero. Si
occupa di capire come le affermazioni, le proposizioni e i concetti possono essere combinati per formare
argomentazioni valide, cioè che seguono regole precise e conducono a conclusioni coerenti. In altre parole,
la logica si interessa dei modi in cui possiamo derivare conclusioni veritiere da premesse date,
assicurandoci che il processo di ragionamento sia privo di errori o contraddizioni. Infatti la logica si occupa
di riconoscere la verità di un enunciato non tanto in quanto corrisponde ad uno stato del mondo (come
avviene per le scienze) quanto di stabilire le condizioni di verità di un enunciato a partire da altri basandoci
solo sulla sua forma logica espressa in un LINGUAGGIO FORMALE.

In particolare, la parola denoterà un sistema formale di regole fissate per poter dedurre la verità di certe
asserzioni, scritte come formule, a partire dall’assumere come vere eventuali altre assunzioni. Il linguaggio
di una logica, o sistema formale, può essere proprio pensato come un linguaggio di programmazione ove i
programmi sono le deduzioni della verità di formule a partire dalla verità di un insieme (anche vuoto) di
formule assunte come vere. La logica formale è un insieme di metodi per stabilire se un argomento è valido
o meno. Le proposizioni sono rappresentate con costanti e variabili, e i connettivi logici permettono di
ottenere proposizioni complesse “connettendo” proposizioni semplici. I connettivi logici funzionano come i
comuni operatori dell’aritmetica (quelli di somma, sottrazione ecc.). Infine, è possibile tradurre enunciati dal
linguaggio comune a quello formale e viceversa.
Esempio di codifica in linguaggio formale. L’asserzione: Ammesso che “non si dia il caso che non esista
input su cui il programma X si ferma” allora è vero che “il programma X si ferma su qualche input”.
si potrà formalizzare in: CORRETTA

¬¬ (∃x F(x)) ⊢ ∃x F(x)

 ∃ ESISTE
 ¬¬ NON+NON AFFERMAZIONE;

 F(X) IL PROGRAMMA X SI FERMA SULL’IMPUT X

La logica formale nasce dalla considerazione che l'efficacia di un'argomentazione dipende in buona misura
dalla sua forma, non dal contenuto specifico delle premesse e della conclusione.

In logica, il concetto di verità è fondamentale e riguarda la relazione tra una proposizione e lo stato di cose
che descrive. Una proposizione, infatti, si distingue in verità o tautologia, una opinione e una
contraddizione.

La verità logica è una proposizione che è vera in virtù della sua forma logica e indipendentemente dal
contenuto specifico delle proposizioni coinvolte. In altre parole, una verità logica è vera in ogni situazione
possibile, perché la sua struttura garantisce che non possa essere falsa. Una tautologia (verità logica) è
una proposizione logica che è sempre vera, indipendentemente dal valore di verità delle singole
proposizioni che la compongono. In altre parole, una tautologia è una formula che è vera in ogni possibile
interpretazione. La verità teorica riguarda le proposizioni che sono vere all'interno di una teoria
specifica. Queste proposizioni sono vere solo se derivano dai postulati o assiomi di quella teoria e sono
coerenti con il sistema teorico in cui sono formulate. La loro verità dipende dalle regole, dalle definizioni e
dai principi stabiliti dalla teoria. È vera relativamente a un sistema teorico o un insieme di assiomi.
 Verità logica: È universale e indipendente dal contenuto. Non cambia da una teoria all'altra. È valida
in virtù della forma logica e delle regole logiche generali.
 Verità teorica: È relativa a un particolare sistema teorico (come una teoria fisica, matematica o
logica). La sua verità dipende dagli assiomi o postulati di quella teoria.
Per verità teorica si intende dunque una verità extra-logica in quanto una teoria è un’estensione di una
logica con assiomi specifici ovvero teoria = logica + assiomi. In logica, una teoria è un insieme di
proposizioni o formule che sono coerenti tra loro e che seguono un sistema di assiomi o regole. Queste
proposizioni descrivono relazioni logiche e strutture all'interno di un certo linguaggio formale.

Ad esempio l’asserzione complessa Ammesso che “non si dia il caso che non esista input su cui il
programma X si ferma” allora è vero che “il programma X si ferma su qualche input”. è corretta in logica
classica.
Altro esempio è l’asserzione Ammesso che “se la radice quadrata canta alla Scala di Milano allora il tuo
vicino di banco è Napoleone” allora è vero che “se il tuo vicino di banco non è Napoleone ne segue che la
radice quadrata non canta alla Scala di Milano”. che è corretta formalmente ma senza significato perché la
proposizione “la radice quadrata canta alla Scala di Milano” non ha senso semanticamente.

L’asserzione per ogni numero naturale n esiste un numero naturale m tale che n + m = n’è corretta nella
teoria dell’aritmetica, ma non è verità logica. L’asserzione “Dio esiste” è corretta nella teoria della dottrina
cristiana ma non è una verità logica.
Un paradosso è un'affermazione o una situazione che sembra contraddittoria o che viola l'intuizione
comune, ma che potrebbe nascondere una verità profonda o rivelare un problema concettuale.
 Esempio di paradosso: Il paradosso del mentitore è un classico esempio. L'affermazione
"Questa frase è falsa" è paradossale: se la frase è vera, allora è falsa, ma se è falsa, allora è vera.
 Caratteristiche: I paradossi spesso mettono in luce limitazioni o ambiguità nelle nostre regole
logiche o linguistiche. Possono anche servire come strumenti per riflettere su questioni complesse o
per evidenziare incoerenze teoriche.
Un paradosso è una contraddizione apparente che sfida la logica o l'intuizione che non ha né valore di
verità né valore di falsità. Ad esempio, “Nel villaggio di Cantù c’è un unico barbiere che rade tutti e soli gli
uomini che non si radono da sé.” Si vede che questa affermazione è un paradosso in quanto afferma una

il barbiere di Cantù rade sé stesso sse non si rade da sé ⇒ l’esistenza di un tal barbiere porta ad una
contraddizione: l’esistenza di tale barbiere. Questo barbiere, infatti, deve radersi ma non può farlo.

CONTRADDIZIONE. Il paradosso che emerge da questa affermazione è simile a quello di un barbiere che
si occupa di radere tutte le persone del villaggio che non si radono da sole, e solo quelle. La domanda
cruciale è: il barbiere si rade da solo o no? Se si rade, secondo la definizione, non dovrebbe farlo, poiché
rade solo chi non si rade da solo. Ma se non si rade, dovrebbe radersi, in quanto rade tutti coloro che non
lo fanno da soli. Questo genera una contraddizione.
livello 1 — barbiere soggetto dell’azione “radere” quelli che “non si radono” (che a posteriori non può
essere anche oggetto)
livello 2 — cliente oggetto dell’azione “radere” (che a posteriori non può coincidere con il barbiere!)
Ovvero: barbiere = cliente dà contraddizione.

Il paradosso del mentitore è uno dei paradossi più noti nella logica e nella filosofia, e coinvolge una contraddizione
basata sull'auto-referenza. Il paradosso è tradizionalmente formulato attraverso l'affermazione: "Questa
affermazione è falsa."
Se analizziamo il contenuto di questa affermazione, emergono due possibili interpretazioni, entrambe contraddittorie:
1. Se l'affermazione è vera: Se la frase "Questa affermazione è falsa" è vera, allora ciò che dice deve essere
vero. Ma la frase afferma che è falsa, quindi, se è vera, deve essere falsa. Qui abbiamo una contraddizione: è
sia vera che falsa allo stesso tempo.
2. Se l'affermazione è falsa: Se la frase "Questa affermazione è falsa" è falsa, ciò significherebbe che la frase
non è falsa, quindi deve essere vera. Anche qui si crea una contraddizione: se è falsa, allora deve essere
vera, e di nuovo si ottiene un'incoerenza.
In entrambe le interpretazioni, si arriva a una contraddizione, creando un paradosso.

Il paradosso del mentitore si basa su tre elementi fondamentali:

1. Auto-referenza: L'affermazione parla di sé stessa.
2. Contraddizione: Se accettiamo una delle due possibilità (vera o falsa), essa conduce logicamente al suo
contrario.
3. Bivalenza logica: Il paradosso sfrutta il principio della logica classica per cui ogni proposizione deve essere o
vera o falsa. Non esiste una terza possibilità.
Il paradosso evidenzia i problemi che sorgono quando un'affermazione fa riferimento a sé stessa. La logica classica
(bivalente) ha difficoltà a trattare queste affermazioni, poiché porta a contraddizioni. Il paradosso mostra che il
linguaggio naturale (quello che usiamo tutti i giorni) può essere ambiguo e suscettibile di auto-contraddizioni. Questo
ha portato allo sviluppo di sistemi di logica formale, che cercano di evitare tali paradossi imponendo restrizioni sull'uso
dell'auto-referenza.

I paradossi sono strumenti estremamente utili in logica, filosofia e scienza, poiché mettono in evidenza
contraddizioni apparenti o reali, stimolano la riflessione critica e aiutano a migliorare la nostra
comprensione di concetti complessi. I paradossi ci costringono a mettere in discussione le nostre
supposizioni e a esaminare in modo più profondo le regole logiche e concettuali che utilizziamo.
Confrontarsi con un paradosso spesso porta a una più chiara definizione dei concetti e delle regole che
usiamo in determinati sistemi. Nello studio delle teorie scientifiche i paradossi sono molto utili per scoprire
ciò che una teoria (formale) non può dire. Ad esempio ragionando come segue: se una certa assunzione
all’interno di una teoria porta ad un paradosso, allora nella teoria in questione l’assunzione risulta falsa.
 I paradossi logici sono falsi in ogni teoria scientifica. I paradossi logici sono contraddizioni ovvero
affermazioni sempre false per motivi puramente logici.
  le scienze devono dare per scontato le VERITÀ LOGICHE
 le verità logiche sono valide a priori (e basta la logica per riconoscerle) e i paradossi sono falsi a
priori.

Un'opinione è una credenza, un giudizio o un punto di vista soggettivo, che può variare da persona a
persona e non è necessariamente basato su fatti oggettivi o verificabili. Le opinioni non sono né vere né
false in senso assoluto, ma riflettono il pensiero individuale.
 Esempio di opinione: "Il cioccolato è il miglior dolce." Questo è un giudizio personale e soggettivo,
che può essere vero per alcune persone e falso per altre.
 Caratteristiche: Le opinioni possono essere influenzate da emozioni, esperienze personali, cultura
e valori, e non devono necessariamente essere supportate da prove oggettive.
Quindi, ha senso che uno scienziato verifichi la validità di asserzioni tramite DEDUZIONI LOGICHE
all’interno della sua teoria solo se queste asserzioni rientrano tra le opinioni logiche (quindi né verità
logiche, né paradossi).
Per distinguere una verità, un paradosso o un’opinione è possibile utilizzare:
 PROCEDURE AUTOMATICHE (robotizzabili) oppure PROCEDURE SEMI-AUTOMATICHE
(robotizzabili con interazione umana)

Il linguaggio formale in logica è un sistema rigorosamente definito di simboli, regole e strutture utilizzato
per esprimere proposizioni, ragionamenti e argomentazioni in modo preciso e privo di ambiguità. A
differenza del linguaggio naturale, come l'italiano, che è spesso ambiguo e soggetto a interpretazioni
multiple, il linguaggio formale segue regole rigorose che consentono di evitare fraintendimenti e paradossi,
rendendo i ragionamenti chiari e verificabili.
 Un linguaggio formale utilizza un alfabeto di simboli o segni (come lettere, connettivi logici,
quantificatori, ecc.) che hanno significati precisi. Ogni simbolo ha un ruolo specifico, e non può
essere interpretato in modi diversi; e utilizza le parole. Una parola è una sequenza ordinata o
stringa di simboli presi dall'alfabeto di un linguaggio formale. Ogni linguaggio formale è definito da
un insieme finito di simboli, detto alfabeto, e le parole sono semplicemente combinazioni di questi
simboli. Queste parole formano le proposizioni

Il linguaggio formale si compone di due livelli di riferimento:

 IL LIVELLO FORMALE: La sintassi di un linguaggio formale stabilisce come i simboli possono
essere combinati per formare espressioni o formule corrette. Le regole sintattiche determinano quali
sequenze di simboli sono ben formate (cioè quali proposizioni sono costruite correttamente) e quali
no.
 IL LIVELLO DEL METALINGUAGGIO/ NOSTRO LINGUAGGIO NATURALE: Oltre alla sintassi, il
linguaggio formale ha una semantica, cioè un insieme di regole che determinano il significato di
ogni espressione ben formata. Questo significa che ogni formula può essere interpretata in modo
preciso (ad esempio, valutata come vera o falsa, a seconda dell'interpretazione delle proposizioni).

Il livello del linguaggio formale è costituito da simboli ed espressioni del linguaggio che possiamo associare
in modo specifico ad una MACCHINA o ROBOT. Invece il livello del metalinguaggio è dato dal significato
dei simboli ed espressioni del precedente livello che è assegnato da NOI in modo specifico. Sulla macchina
sintassi e semantica sono due livelli distinti e la macchina esegue solo il livello sintattico. Ricordiamo che
dobbiamo operare una netta distinzione tra tali livelli di riferimento per non incorrere in paradossi. Il
linguaggio formale utilizzato per rappresentare le formule logiche è UNIVERSALE nel senso che non fa
riferimento a nessun lingua parlata ma anzi potrebbe essere utilizzato per costruire traduttori automatici tra
lingue diverse.

Lo scopo della logica è di introdurre un linguaggio simbolico per studiare la FORMA degli enunciati SENZA
RIFERIMENTO al contenuto semantico specifico. L'autoriferimento è un concetto che riguarda situazioni
in cui un'espressione o una frase si riferisce a sé stessa. In logica, matematica e filosofia, l'autoriferimento
può essere fonte di paradossi e problematiche complesse. L'autoriferimento è il piano in cui semantica
e sintassi sono sullo stesso livello. In generale, nei linguaggi formali, c'è una separazione tra sintassi (la
struttura formale delle espressioni) e semantica (il loro significato e interpretazione). Quando diciamo che
sintassi e semantica sono sullo stesso livello in un contesto di autoriferimento, stiamo osservando una
situazione in cui un'espressione fa riferimento a sé stessa sia sul piano sintattico che sul piano
semantico. Il paradosso del mentitore rompe la distinzione usuale tra sintassi e semantica, perché la frase
non è solo un'entità formale (sintattica), ma cerca anche di dire qualcosa sul proprio stato di verità
(semantica). Questa commistione di livelli sintattico e semantico è ciò che porta a paradossi o ambiguità
logiche. DUNQUE UNA MACCHINA NON POTRÀ MAI AUTORIFERIRSI POICHÉ SINTASSI E
SEMANTICA SONO SULLO STESSO PIANO.

Costituenti delle nostre asserzioni sono le proposizioni (o formule), ove con proposizione si intende un
enunciato in un determinato linguaggio, non solo dotato di senso ma anche di valore di verità. Le
PROPOSIZIONI si distinguono in atomiche e composte e per denotarle si utilizza un linguaggio formale
specifico. A tale fine utilizziamo le lettere dell’alfabeto maiuscole (A, B, C…) come nomi per indicare le
proposizioni atomiche. Quando una lettera è utilizzata per indicare una proposizione specifica la definiamo
una variabile proposizionale.
 usiamo le lettere dell’alfabeto MAIUSCOLO A, B, C . . . per indicare variabili proposizionali che sono
GIÀ particolari parole del linguaggio ovvero sono PROPOSIZIONI formali
Le variabili proposizionali ha cinque operatori fondamentali, chiamati connettivi. I connettivi sono simili agli
operatori aritmetici, in quanto prendono dei valori dati e ne producono di nuovi. Gli operatori logici però
operano su due soli valori: i valori di verità, V e F.
 connettivo unario della negazione (1 sola
formula dopo)
 connettivo binario congiunzione
 connettivo binario disgiunzione
 connettivo binario dell’implicazione

 le parentesi ( e ) Le parentesi vengono utilizzate per specificare l'ordine in cui devono essere
valutate le operazioni logiche, Chiarire la struttura delle proposizioni e ridurre l'ambiguità,

 la proposizione costante atomica falso ⊥

Separare le proposizioni per facilitare la comprensione e la lettura.

 la proposizione costante atomica vero tt.

Una proposizione formale pr (che è una META-variabile per indicare una proposizione formale generica) è
una stringa di simboli ottenuti in tal modo: pr ≡ A oppure pr ≡ B oppure una qualsiasi variabile
proposizionale, detta proposizione atomica (ovvero una parola del linguaggio formale proposizionale), che

proposizione costante falso ⊥ o la proposizione costante vero tt oppure pr coincide con una delle seguenti
noi abbiamo fissato essere una lettera maiuscola dell’alfabeto inglese; oppure pr coincide con la

proposizioni ottenute da altre due generiche proposizioni pr1 e pr2 (una proposizione composta)

 (pr1) ∨ (pr2) che sta per pr1 o pr2

 (pr1) & (pr2) che sta per pr1 e pr2

 (pr1) → (pr2) che sta per sé pr1 allora pr2 ovvero pr1 implica pr2
 ¬ (pr1) che sta per NON si dà il caso che pr1
la proposizione del linguaggio naturale “Oggi e venerdì e domani è sabato” si può formalizzare nella
proposizione formale (V) & (S) ove V = “Oggi e venerdì” S= “domani e sabato”

Nello scrivere le proposizioni simboliche possiamo eliminare le parentesi dalle variabili proposizionali, dette
proposizioni atomiche, e dalle proposizioni composte CONVENENDO che

parentesi, ∨, & si legano a proposizioni atomiche o negazioni ¬ vicine SENZA bisogno di parentesi
¬ si lega soltanto alla proposizione atomica vicina o ad altra negazione ¬ vicina SENZA bisogno di

→ si lega a proposizioni atomiche, negazioni ¬, disgiunzioni ∨ o congiunzioni & vicine SENZA bisogno di

Ovvero ¬ lega più di ∨, & legano più di →

parentesi

In altre parole possiamo togliere le parentesi se il connettivo più esterno lega meno di quello o quelli
immediatamente più interni rispetto alla convenzione sopra. Possiamo togliere le parentesi se il
connettivo più esterno lega meno di quello o quelli immediatamente più interni rispetto alla convenzione
sopra.

Esempi:
 “(negazione di A) e B” si scrive ¬A&B
 “negazione di (A e B)” si scrive ¬(A&B)
 “la (negazione di A) implica (B e C)” si scrive ¬A→B&C
 “la negazione di ((A implica B) e C)” si scrive ¬ ((A→B) &C)
congiunzione è solo binario!! Inoltre (A e B) o C si scrive (A&B) ∨ C ove non si può togliere altre parentesi
Si osservi che (A e B) e C si scrive (A&B) &C che NON si può semplificare in A&B&C perché il connettivo di

perché sia la congiunzione che la disgiunzione sono connettivi binari.

 CONNETTIVI
Si noti che la congiunzione pr1&pr2 traduce legami tra pr1 e pr2 del tipo
pr1e pr2
pr1perchè pr2
pr1mentre pr2
pr1però pr2
pr1quindi pr2
pr1ma pr2
pr1 dunque pr2

mentre l’implicazione pr1 → pr2 traduce legami del tipo

se pr1 allora pr2
pr1 solo se pr2
pr2 se pr1
solo se pr2 vale pr1

Trucco per tradurre il solo se

- riscrivere la frase togliendo il “solo”
- tradurre la frase ottenuta usando l’implicazione
- se la frase ottenuta è pr1 → pr2 allora la traduzione della frase iniziale si trova SCAMBIANDO
antecedente con conseguente, ovvero scrivendo pr2 → pr1

La formalizzazione di “Prendo l’ombrello solo se piove” è O→P

posto O = prendo l’ombrello; P = piove
mentre la formalizzazione di “Prendo l’ombrello se e solo se piove” coincide con quella di “Se piove prendo
l’ombrello e se prendo l’ombrello di sicuro piove” che è (P→O) & (O→P)

“Sono a Padova solo se sono in Italia.” che si formalizza in P →I con P = sono a Padova; I = sono in Italia.
E con tal affermazione NON intendo dire assolutamente “Sono a Padova se solo se sono in Italia.” ma
invece che “Se sono a Padova allora necessariamente sono in Italia” ovvero “L’essere in Italia è una
condizione necessaria affinché io sia Padova” oppure equivalentemente che “L’essere a Padova è una
condizione sufficiente affinché io sia in Italia.”
 In un’implicazione Pr1 → Pr2 l’antecedente dell’implicazione Pr1 si dice condizione SUFFICIENTE
affinché si verifichi il conseguente dell’implicazione Pr2. il conseguente dell’implicazione Pr2 si dice
si dice condizione NECESSARIA affinché si verifichi l’antecedente dell’implicazione Pr1

Si raccomanda di tradurre in linguaggio formale un enunciato che inizia con “NON si dà il caso che” come
segue
1. si riscriva la parte positiva dopo NON si dà il caso che che chiamiamo enunciato oggetto negazione
(che può al suo interno contenere altre negazioni!) e lo si ponga tra parentesi preceduto dal segno
di negazione ¬ ( enunciato oggetto negazione )
2. si proceda a tradurre l’enunciato in forma positiva interno alle parentesi a parte.
3. Si inserisca l’enunciato tradotto sopra al posto di enunciato oggetto negazione. Lo stesso si operi
con un enunciato con una sola proposizione principale al suo interno.

Non si dà il caso che Mario non mangi o non guardi la TV con M= Mario mangia; G=Mario guarda la TV

tal modo ( ¬( Mario mangia ) ∨ (¬( Mario guarda la TV ) ) che si traduce infine in questo modo ¬M ∨ ¬C e
si scriva ¬ (Mario non mangia o non guarda la TV) e poi si traduca Mario non mangia o non guarda la TV in

quindi la traduzione finale è ¬(¬M ∨ ¬C)

connettivi ¬ , ∨ , & , → che compongono pr e che definiamo di seguito.
La tabella di ogni proposizione formale pr si costruisce componendo (come funzioni) le tabelle dei

 Tabella di verità di ¬
si ottiene considerando che ¬A è vero sse A è falso ed è la funzione unaria

 Tabella di verità di &

si ottiene considerando che A&B è vero sse A è vero e B è vero ed è la funzione
binaria

 Tabella di verità di ∨
si ottiene considerando che A∨B è vero sse A è vero o B è vero o sono veri
entrambi ed è la funzione binaria

 Tabella di verità di →
si ottiene considerando che A→B è vero sse ¬A∨B è vero ed è la funzione binaria

La proposizione pr si dice vera in logica classica e nel

gergo logico pr si dice TAUTOLOGIA sse la tabella di verità
di pr dà sempre 1 in uscita

Una proposizione pr è vera classicamente sse la tabella di

verità di pr dà sempre 1 in uscita e
sinonimi di “pr `e vera classicamente” sono i seguenti:
• “pr `e TAUTOLOGIA classica”
• “pr `e VALIDA classicamente”
• la scrittura simbolica |= pr che si legge “pr vale
classicamente”.

Una proposizione pr si dice:

 TAUTOLOGIA in logica classica, o semplicemente VALIDA se sono TUTTI 1 i valori in uscita nella
sua tabella di verità.
 OPINIONE in logica classica se ha ALMENO un 1 e ALMENO uno 0 come valori in uscita nella sua
tabella di verità.
 CONTRADDIZIONE o PARADOSSO o INSODDISFACIBILE se sono TUTTI 0 i valori in uscita nella
sua tabella di verità.
 SODDISFACIBILE se è 1 QUALCHE valore in uscita nella sua tabella di verità.
 NON VALIDA se è 0 QUALCHE valore in uscita nella sua tabella di verità.

esempio di TAUTOLOGIA o proposizione VALIDA: ¬¬(P∨¬P).

esempio di proposizione OPINIONE: P → Q visto che nella sua tabella di verità per P = 0 ha 1 in
uscita e che per P = 1 e Q = 0 ha 0 in uscita
esempio di proposizione CONTRADDITTORIA: P&¬P
esempio di proposizione SODDISFACIBILE: ¬P visto che nella sua tabella di verità per P = 0 ha 1 in
uscita.
esempio di proposizione NON VALIDA: P→¬P visto che nella sua tabella di verità per P = 1 ha 0 in
uscita.

Valgono le seguenti relazioni tra una proposizione e la sua negazione:

 pr TAUTOLOGIA sse ¬pr PARADOSSO
 pr PARADOSSO sse ¬pr TAUTOLOGIA
 pr OPINIONE sse ¬pr OPINIONE
 pr NON VALIDA sse ¬pr SODDISFACIBILE
 pr SODDISFACIBILE sse ¬pr NON VALIDA
ATTENZIONE che se ¬pr è soddisfacibile NON implica che pr sia insoddisfacibile come pure se pr è NON
valida non implica che ¬pr sia valida.
quando due proposizioni formali pr1 e pr2 hanno la STESSA tabella di verità? Innanzitutto notiamo che
proposizioni sintatticamente diverse possono avere la
stessa tabella di verità:

Diciamo che “pr1 è equivalente a “pr2” se e solo se pr1 e

pr2 hanno la stessa tabella di verità.

Per capire come sono relazionate tale proposizioni

introduciamo il connettivo di equivalenza col segno ↔.
Date due proposizioni formali pr1 e pr2,
pr1 ↔ pr2 ≡ (pr1→pr2 ) & ( pr2→pr1 ) che si legge “pr1 è equivalente a “pr2”.

Date proposizioni pr1 e pr2,

allora pr1 e pr2 hanno la stessa tabella di verità sse
pr1↔pr2 è una tautologia.

pr1↔pr2 è tautologia (ovvero la sua tabella ha tutti 1 in

uscita) se e solo se pr1 e pr2 hanno la stessa tabella di
verità ovvero pr1 e pr2 sono equivalenti. Indichiamo con il segno ↔ il connettivo equivalenza come
ABBREVIAZIONE di: date proposizioni formali pr1 e pr2, pr1 ↔ pr2 ≡ (pr1→pr2 ) & ( pr2→pr1 )

In tal caso si dice che la proposizione pr1 è uguale semanticamente a pr2, ovvero l’uguaglianza
semantica di proposizioni è l’equivalenza di proposizioni nel senso che Date due proposizioni formali pr1 e
pr2, la proposizione pr1 si dice equivalente a pr2 e se e solo se pr1↔pr2 è una tautologia.

Perché la tabella di pr1↔pr2 e ottenuta da quelle di pr1 e pr2, componendo con la tabella di ↔, e quindi la
tabella di pr1↔pr2 su una stessa riga d’entrata dà 1 in uscita se e solo se le tabelle di pr1 e pr2 sulla
stessa entrata danno tutti e due 1 oppure tutti e due 0 (ovvero le loro tabelle concordano in uscita su una
stessa entrata e sono quindi uguali!). PER ESEMPIO: A&A ed (A&A) & A sono equivalenti nel senso che
A&A ↔ (A&A) & A è una TAUTOLOGIA,

Per classificare una pr, è possibile impiegare 2 strategie:

 strategia tabella di verità: fai la tabella di verità di pr
vantaggio: strategia sicura e automatica; svantaggio: la tabella può essere molto complessa e lenta
 strategia riduzione: riduci pr tramite equivalenze note ad una tautologia classica nota
vantaggio: strategia veloce, se termina; svantaggio: strategia non automatica e non sempre
terminante in una proposizione nota (poiché infinita).

Questo metodo si basa sull'applicazione di tautologie già note della logica proposizionale per
trasformare e semplificare l'espressione fino a verificarne la validità.

Lista di proposizioni valide classicamente (ha TUTTI 1 in uscita):

Se vale |= pr1 ↔ pr2, ovvero pr1 è equivalente a

pr2 presa un’altra proposizione pr3(A),

allora vale |= pr3(pr1) ↔ pr3(pr2)

Date pr1, pr2 e pr3 proposizioni se |= pr1 ↔ pr2

e |= pr2 ↔ pr3 allora |= pr1 ↔ pr3

Passaggi del metodo della riduzione:

1. Identificare la proposizione da verificare e
decomporla nei suoi elementi costitutivi
(proposizioni atomiche e connettivi logici).
2. Applicare le tautologie classiche note per
semplificare la proposizione.
 tautologia, come ⊤ (vero) o un'espressione logica equivalente a una tautologia.
3. Ripetere il processo di semplificazione finché non si arriva a una forma che sia chiaramente una

Consideriamo la seguente proposizione: (P→Q) ∨ (¬P→R)

Passo 1: Analizzare la proposizione
Questa proposizione è composta da due implicazioni logiche collegate da una disgiunzione. La nostra
prima mossa è trasformare le implicazioni in una forma equivalente usando la legge dell'implicazione:
(P→Q) ≡ ¬P∨Q; (¬P→R) ≡ P∨R

(¬P∨Q) ∨ (P∨R)
Quindi la proposizione originale diventa:

Passo 2: Semplificazione
Ora applichiamo le leggi logiche per semplificare ulteriormente questa proposizione. In questo caso,

1. Proprietà associativa: possiamo riscrivere la proposizione come: ¬P∨(Q∨P) ∨ R

possiamo usare le proprietà della disgiunzione (∨):

P∨¬P≡⊤ Quindi la proposizione diventa: ⊤∨R

2. Legge dell'assorbimento: Q∨P≡P∨Q, ma ciò che ci interessa è che P∨¬P è una tautologia:

Poiché ⊤ rappresenta il vero, e ⊤∨R è sempre vero, indipendentemente dal valore di R, possiamo
Passo 3: Risultato finale

concludere che l'intera proposizione è una tautologia.

Tautologie classiche utilizzate:
1. Legge dell'implicazione: A→B≡¬A∨B.
2. Legge dell'assorbimento: P∨¬P≡⊤ (una tautologia).
3. Proprietà associativa della disgiunzione.

ESISTE UNA TERZA STRATEGIA, CHE È QUELLA CHE UTILIZZEREMO, SEMPLICE E AUTOMATICA
per stabilire se una proposizione `e valida o meno e soddisfacibile o meno. Tale metodo è MENO
COMPLESSO di quello delle tabelle di verità e consiste in una procedura algoritmica che TERMINA
SEMPRE con una risposta. Questa procedura fa uso di un calcolo dei sequenti per la logica classica
proposizionale.
 Il calcolo dei sequenti serve a costruire alberi di derivazione

In logica, un sequente è una notazione formale che esprime una relazione di deduzione tra premesse e
conclusioni. È usato per rappresentare formalmente che da un insieme di proposizioni (le premesse) segue
una certa proposizione (la conclusione). Un sequente è un'espressione logica che rappresenta una
relazione di deduzione formale, dichiarando che, se le premesse (lato sinistro) sono vere, allora segue
almeno una delle conclusioni (lato destro).

Un sequente ha la seguente forma generale: Γ⊢Δ (liste di proposizioni) Dove:

 Γ (gamma) (il lato sinistro del sequente) rappresenta l'insieme delle premesse (può anche essere
vuoto). Può essere un insieme di formule logiche (proposizioni), separate da virgole, che sono
assunte come vere.

 ⊢ è il simbolo di deduzione, chiamato turnstile. Indica che dalle premesse Γ si può dedurre la
pr1 , pr2 , . . . prn

conclusione Δ. È IL SIMBOLO DI IMPLICA

 Δ (Delta) (il lato destro del sequente) rappresenta l'insieme delle conclusioni (può anche essere
vuoto). Anche qui può essere una singola proposizione o un insieme di proposizioni.

In pratica, il sequente afferma che, se tutte le premesse in Γ sono vere, allora almeno una delle
proposizioni in Δ deve essere vera.

equivalentemente che la proposizione formale ( pr1&pr2 ). . . &prn → ( cl1 ∨cl2 ). . . ∨ clm è vera. Un
“se pr1 è vero e pr2 è vero... e prn `e vero allora o cl1 è vero oppure cl2 è vero... oppure clm è vero” o

esempio semplice di sequente potrebbe essere: P, Q ⊢R

Questo si legge come: "se P e Q sono veri, allora R deve essere vero". Questo può essere interpretato
come: "le conclusioni Δ possono essere derivate dalle premesse Γ". Più formalmente, significa che se tutte
le formule di Γ sono vere, allora almeno una formula di Δ è vera.

 Sequente con premesse vuote: ⊢ Δ

Sequente vuoto
condizione. Questo tipo di sequente indica che la proposizione a destra del ⊢ è una tautologia, cioè è
Ciò significa che non ci sono premesse e si afferma che la conclusione Δ è vera senza alcuna

sempre vera indipendentemente da qualsiasi altra proposizione.

significa che P è una tautologia, cioè una proposizione vera indipendentemente dalle premesse.

che la proposizione ( cl1∨cl2 ). . . ∨ clm è vera o anche equivalentemente che la proposizione tt →

rappresenta un’asserzione del tipo “o cl1 è vero oppure cl2 è vero...oppure clm è vero” o equivalentemente

(cl1∨cl2 ). . . ∨ clm è vera

tt rappresenta la costante vero

Esempio: ⊢P∨¬P. Questo sequente afferma che P∨¬P (cioè, "o P è vero o P è falso") è vero in ogni
situazione. Si tratta di una tautologia.
 Sequente con conclusioni vuote: Γ⊢

Ciò significa che le premesse Γ non portano ad alcuna conclusione possibile, ossia le premesse
conducono a una contraddizione. Questo tipo di sequente è usato per indicare che l'insieme di
premesse Γ è incoerente o contraddittorio.
indica che la proposizione P è una contraddizione, perché non c'è una conclusione valida che può
essere dedotta da P.

(pr1&pr2 ) . . . &prn → ⊥ è vera

significa “se pr1 è vero e pr2 è vero... e prn è vero allora la costante falso è vera ” o equivalentemente

⊥ rappresenta la costante falso

Ciò significa che le premesse Γ non portano ad alcuna conclusione possibile, ossia le premesse
conducono a una contraddizione. Questo tipo di sequente è usato per indicare che l'insieme di
premesse Γ è incoerente o contraddittorio.

Quando sia le premesse che le conclusioni sono vuote, il sequente ha la forma: ⊢

 Sequente completamente vuoto (⊢)

Questo è un sequente che non ha né premesse né conclusioni, e non ha senso logico. In pratica, un

La scrittura ⊢ che rappresenta un’asserzione del tipo “la costante falso è vera” o equivalentemente che la
sequente completamente vuoto è considerato privo di significato, perché non c'è nulla da inferire.

proposizione ⊥ è vera o anche equivalentemente che la proposizione tt → ⊥ è vera

 Sequente con premesse vuote (⊢Δ): le conclusioni sono sempre vere (tautologia).
 Sequente con conclusioni vuote (Γ⊢ le premesse sono contraddittorie.
 Sequente completamente vuoto (⊢): è privo di significato.

Per rappresentare con un’unica scrittura i quattro tipi di sequenti illustrati usiamo lettere greche maiuscole del tipo Γ,
∆, Σ . . . come META-VARIABILI per indicare una generica LISTA di PROPOSIZIONI anche vuota. Per esempio,
possiamo pensare che una variabile Γ denoti Γ ≡ [ ] la lista vuota oppure Γ ≡ pr1 , pr2, . . . E poi indichiamo con Γ⊢∆
un generico sequente ove Γ e ∆ rappresentano liste anche vuote di proposizioni. nelle regole dei sequenti le
METAvariabili date da lettere greche MAIUSCOLE Γ e ∆, Σ.. stanno per LISTE DI PROPOSIZIONI anche VUOTE e
quindi NON compaiono mai in un sequente ottenuto da
una TRADUZIONE in linguaggio formale di un enunciato
in linguaggio naturale;

lista di proposizioni Γ a sinistra del segno ⊢ come

Queste notazioni servono quindi per interpretare una

un’unica proposizione Γ& che è la congiunzione

(associata a sinistra) delle proposizioni nella lista Γ e

del segno ⊢ come un’unica proposizione ∆∨ che è

per interpretare una lista di proposizioni ∆ a destra

la disgiunzione (associata a sinistra) delle

proposizioni nella lista ∆.

La tabella di verità di un sequente ` Γ ⊢ ∆ e la `

tabella di verità della proposizione
Γ& → ∆∨
Γ⊢∆ è TAUTOLOGIA/OPINIONE/PARADOSSO sse Γ& → ∆∨ è TAUTOLOGIA/OPINIONE/PARADOSSO

sequente ⊢ pr attraverso la costruzione di alberi di derivazione utilizzando le regole del calcolo dei
Per stabilire se la proposizione pr è TAUTOLOGIA seguiremo una procedura AUTOMATICA che opera sul

sequenti. Il calcolo dei sequenti consiste nell'applicare, partendo da un sequente formato da asserzioni
complesse, le regole del sistema per giungere a sequenti riconosciuti validi. Se l'applicazione delle regole
di derivazione porta sempre a scritture ambigue o non vere (ad esempio da una proposizione B segue che
A non viene di certo considerato un sequente valido) allora si può concludere che quel sequente non è
derivabile, o, meglio, che la frase che esprime non è dimostrabile. Il calcolo dei sequenti è composto da
assiomi e da delle regole con cui operiamo trasformazioni di sequenti secondo lo schema se VALE
QUESTO SEQUENTE (o QUESTI due SEQUENTI) allora VALE QUEST’ALTRO SEQUENTE detto anche
regola di inferenza di sequenti. Nel calcolo dei sequenti, ogni passaggio nella derivazione formale di un
teorema è giustificato da una regola di inferenza. Le regole sono divise in due categorie:
1. Regole strutturali: riguardano la manipolazione generale delle premesse e delle conclusioni senza

o Assioma (A): Un sequente della forma Γ, A ⊢ A, Δ sempre valido (cioè ogni formula può
riferirsi alle particolari proprietà logiche delle formule.

essere derivata da se stessa).

o Taglio (Cut): Se è possibile derivare Γ⊢Δ, A e Γ′, A⊢Δ′, allora è possibile derivare Γ, Γ′⊢ Δ,

2. Regole logiche: queste riguardano il modo in cui i connettivi logici (come ¬, ∧, ∨, →) possono
Δ′ (questa regola permette di "tagliare" una formula intermedia).

essere manipolati all'interno dei sequenti.

o Regola del "non" (¬): Si può introdurre
o eliminare la negazione con regole che
spostano formule da una parte all'altra

 Γ ⊢ ¬A, Δ se e solo se Γ, A ⊢ Δ.
del sequente:

o Regola del "e" ∧: Per l'introduzione e

 Γ⊢A ∧ B, Δ se e solo se Γ⊢A,B,Δ .

l'eliminazione della congiunzione:

Il calcolo è composto dai seguenti schemi di assiomi e regole:

 ⊥ ovvero la proposizione falsa in qualsiasi interpretazione, allora vale che Γ, ⊥ ⊢ Δ (da falso segue
Vengono definiti:

 T ovvero la proposizione sempre vera ⊢ ⊤

qualsiasi cosa)

 ASSIOMA Identità: è sempre vero il sequente te A ⊢ A per qualsiasi proposizione A.

Quando si cerca una derivazione per un sequente, conviene costruire dal basso verso l’alto un albero di

assiomi per ⊤ o ⊥. L’albero è costruito “impilando” regole di inferenza.

derivazione che ha come radice (conclusione) il sequente da dimostrare e ha come foglie le identità o gli

sono alberi di derivazione ove ALBERO di DERIVAZIONE per Γ ⊢

Il calcolo dei sequenti serve a costruire alberi che occasionalmente

∆ = albero con radice Γ ⊢ ∆ ottenuto con regole del calcolo e le

cui foglie terminanti sono TUTTE ASSIOMI.
un sequente Γ ⊢ ∆ è derivabile nel calcolo dei sequenti sse è radice di un albero di derivazione

sequente ⊢ pr è radice di una

data una proposizione formale pr il

derivazione nel calcolo dei sequenti

LCp sse pr è una TAUTOLOGIA

Un sequente Γ⊢∆ si dice derivabile nel calcolo dei sequenti LCp se esiste un albero avente
• Γ⊢∆ come radice;

pr1 e pr2 e le variabili Γ, ∆, ∇, Σ con liste di proposizioni arbitrarie (anche con la lista vuota).
• ogni foglia è istanza di un assioma di LCp ottenuto sostituendo le variabili A, B con arbitrarie proposizioni

con arbitrarie proposizioni pr1 e pr2 e le variabili Γ, ∆, ∇, Σ con liste di proposizioni arbitrarie (anche con la
• l’albero è costruito applicando istanze delle regole del calcolo di LCp ottenute sostituendo le variabili A,B

lista vuota).

Γ ⊢ ∆ è radice di una derivazione in LCp sse Γ ⊢ ∆ è TAUTOLOGIA ovvero Γ & → ∆∨ è TAUTOLOGIA

singoli sequenti ax-⊥ ⊥⊢; ax-⊥ ⊢ tt sono assiomi (rispettivamente del falso e del vero) e quindi sono alberi
Gli assiomi sono gli unici alberi di derivazione formati da un singolo sequente che è sia radice che foglia. I

di derivazione. I singoli sequenti ⊢; ⊢⊥; tt ⊢ NON sono assiomi e quindi NON sono alberi di derivazione.
Un sequente non è derivabile nel calcolo dei sequenti quando non esiste alcuna sequenza di applicazioni
delle regole di inferenza che ci permetta di dedurre le conclusioni (Δ) dalle premesse (Γ). In altre parole,
non è possibile dimostrare che le formule presenti nelle conclusioni siano vere partendo dalle formule delle
premesse.  la stessa variabile non compare tra le conclusioni e le premesse

PER DECIDERE SE UNA PROPOSIZIONE è TAUTOLOGIA/OPINIONE/PARADOSSO IN LCP

 passo 1: si applichi la procedura di decisione provando a derivare ⊢ pr in LCp

Data una proposizione pr:

se si deriva ⇒ pr è una tautologia

se la procedura termina con un NON derivabile, vai al passo 2

 passo 3: prova a derivare ⊢ ¬pr in LCp applicando la procedura di decisione

 passo 2: la proposizione pr NON è una tautologia e la si nega

se ⊢ ¬pr si deriva ⇒ ⊢ pr è un paradosso

se la procedura termina con ⊢ ¬pr NON derivabile è un’opinione.

Γ⊢∆ è una tautologia sse ⊢ ¬( Γ & → ∆∨ ) è un paradosso/insoddisfacibile

Γ⊢∆ è un paradosso sse ⊢ ¬( Γ & → ∆∨ ) è una tautologia

NB: Una delle regole è la regola di scambio (detta anche scambio strutturale), che riguarda la gestione dell'ordine
delle formule nelle premesse (Γ) o nelle conclusioni (Δ). La regola di scambio permette di scambiare l'ordine delle
formule o dei termini all'interno dell'insieme delle premesse (Γ) o all'interno dell'insieme delle conclusioni (Δ) di un
sequente, senza cambiare il loro significato logico. Formalmente, se hai un sequente del tipo:
Γ1, A, B, Γ2⊢Δ Applicando la regola di scambio (SINISTRO) sulle premesse (Γ), otteniamo: Γ1,B,A,Γ2⊢Δ
Analogamente, puoi applicare la regola di scambio (DESTRO) anche nelle conclusioni: Γ⊢Δ1,A,B,Δ2 Diventa:
Γ⊢Δ1,B,A,Δ2

Un assioma di identità ha la forma A⊢A, dove la stessa formula compare sia a sinistra (nelle premesse) che a destra
(nelle conclusioni) del sequente, esattamente con la stessa forma.

Se abbiamo una derivazione valida che utilizza delle variabili proposizionali, possiamo sostituire tutte le occorrenze di
una variabile proposizionale (ad esempio, p o q) con una proposizione qualsiasi, e il risultato sarà comunque una
derivazione valida.
Dettagli del Processo
1. Derivazione Iniziale: Immaginiamo di partire con una derivazione, cioè una sequenza di passaggi logici che
porta a una conclusione a partire da alcune premesse. In questa derivazione, sono presenti variabili
proposizionali che rappresentano delle proposizioni generiche.
2. Sostituzione di Tutte le Occorrenze di una Variabile: Scegliamo una variabile proposizionale, ad esempio
p, e la sostituiamo in tutta la derivazione con una proposizione arbitraria φ (che può essere una proposizione
complessa come (A∧B)→C.
3. Mantenimento della Validità della Derivazione: Dopo la sostituzione, il nuovo "albero" della derivazione,
ovvero la sequenza di passaggi logici modificata, rimane valido. Questo significa che tutte le regole di
inferenza applicate nella derivazione originale sono rispettate anche nella derivazione modificata.
4. Chiusura delle Derivazioni: Questo processo mostra che le derivazioni sono "chiuse" rispetto alla
sostituzione delle variabili proposizionali con proposizioni generiche, perché non importa quale proposizione
usiamo al posto di una variabile, il risultato sarà sempre una derivazione valida.
Questo principio è cruciale perché garantisce la generalizzabilità delle derivazioni. Una derivazione costruita
usando variabili proposizionali non dipende dal contenuto specifico delle proposizioni rappresentate da queste
variabili, ma solo dalla struttura logica della derivazione stessa. Di conseguenza, ogni derivazione costruita con
variabili proposizionali è applicabile a una vasta gamma di proposizioni, rendendo possibile l'uso di regole logiche
in maniera astratta e universale. In altre parole, ogni derivazione valida mantiene la sua validità anche se applichiamo
trasformazioni per sostituzione, permettendo di generalizzare le tecniche di derivazione logica e assicurando che tali
trasformazioni non compromettano la correttezza del ragionamento.

Interpretazione del contesto vuoto come costante logica

 Contesto vuoto a sinistra del sequente: Quando un sequente ha il contesto vuoto a sinistra (cioè non ci

del tipo: ⊢pr è valido se e solo se tt→pr è una tautologia. Poiché tt→pr è logicamente equivalente a pr,
sono premesse), viene interpretato come la costante vero (tt). Questo significa che se abbiamo un sequente

possiamo concludere che ⊢pr è valido se e solo se pr è una tautologia. Inoltre, la relazione tt ∧ pr↔pr ci
dice che la costante vero è l'elemento neutro della congiunzione: aggiungere vero ad una proposizione non
ne cambia il valore di verità.
 Contesto vuoto a destra del sequente: Quando il contesto è vuoto a destra, si interpreta come la costante
falso (⊥). Un sequente come: pr⊢ è valido se e solo se pr→⊥ è una tautologia. Poiché pr→⊥ è
logicamente equivalente a ¬pr, deduciamo che pr⊢ è valido se e solo se ¬pr è una tautologia. La
 relazione ⊥∨pr↔pr mostra che il falso è l'elemento neutro della disgiunzione, poiché aggiungere falso ad una
proposizione non altera il valore di verità della proposizione stessa.

2. Coincidenza tra derivabilità e tautologia in LCp

Una proprietà fondamentale del calcolo LCp è che la derivabilità di un sequente Γ⊢∇ coincide con la sua validità
come tautologia. Questo significa che, in LCp, ogni sequente derivabile è una tautologia e viceversa. Inoltre, LCp
permette una procedura di decisione per determinare se un sequente è derivabile (e quindi valido). Ciò implica che

⊢pr: se questo sequente è derivabile, allora pr è una tautologia. L'esistenza della procedura di decisione si basa su
possiamo decidere meccanicamente se una proposizione è valida, applicando la procedura di decisione al sequente

due proprietà chiave delle regole di LCp:

 Conservazione della verità: Le regole di LCp preservano il valore di verità sia quando si procede "dall’alto in
basso" (dalle premesse verso la conclusione) sia "dal basso in alto" (dalla conclusione verso le premesse). In altre
parole, le trasformazioni eseguite secondo le regole di LCp non alterano la verità logica delle proposizioni
coinvolte.
 Diminuzione della complessità: Quasi tutte le regole di LCp (eccetto quelle per lo scambio delle formule a
sinistra e a destra) riducono la complessità del sequente procedendo dalla conclusione verso le premesse.
Questo significa che, applicando le regole, si scompongono le formule complesse nei loro componenti più
semplici, fino a ottenere proposizioni atomiche o assiomi.
Per verificare la derivabilità di un sequente Γ⊢Δ, costruiamo un albero di derivazione applicando le regole di LCp sui
connettivi presenti nelle proposizioni composte del sequente. Utilizziamo le regole di scambio (se necessario) per
riorganizzare le proposizioni, finché non otteniamo foglie dell'albero che sono:
 Assiomi (formule sempre vere, come p⊢p).
 Oppure variabili proposizionali senza ulteriori proposizioni composte.

Alla fine del processo, si presentano due possibilità:

1. Tutte le foglie sono assiomi: In questo caso, Γ⊢Δ è derivabile in LCp, quindi è una tautologia e rappresenta
un sequente valido nella logica classica.
2. Almeno una foglia non è un assioma: In questo caso, Γ⊢Δ non è derivabile in LCp, e quindi non è valido
in logica classica. Per dimostrare la non validità, si possono individuare interpretazioni che rendono falso il
sequente, continuando l'analisi dell'albero per trovare una "riga falsa".

COME INDIVIDUARE UNA "RIGA FALSARIA" (ovvero una configurazione di valori di verità) per un sequente che non
è una tautologia attraverso la procedura di decisione per la logica dei sequenti. La procedura mira a costruire un
albero di derivazione che riveli se un sequente può essere reso falso e, in caso affermativo, fornisce una riga specifica
che rende il sequente non valido.
1. La procedura per trovare una riga falsaria di un sequente Γ⊢∇ non valido
Quando l'albero di derivazione di Γ⊢∇ include una foglia non assioma (cioè un nodo terminale che non è identità e
non è un assioma), si può individuare una riga falsaria assegnando valori di verità alle variabili proposizionali come

 Ogni variabile in Γ (a sinistra del simbolo ⊢) viene impostata su vero (1).

segue:

 Ogni variabile in ∇ (a destra del simbolo ⊢) viene impostata su falso (0).

 Tutte le altre variabili nel sequente originale Γ⊢∇ possono avere valori assegnati a piacere.

La procedura distingue vari tipi di foglie non assioma, per ognuna delle quali è possibile individuare una riga che

1. Foglia del tipo Ai1 ,…, Ain ⊢ Vk1,…, Vkm:

rende il sequente falso:

o Se l'insieme di proposizioni in Γ è esattamente uguale a quello in ∇ (ovvero, {Ai1,…,Ain} ∩ {Vk1,…,Vkm}=∅

allora qualsiasi riga con: Aij=1 e Vkj=0 dà valore falso alla proposizione associata al sequente.

2. Foglia del tipo ()⊢Vk1,…,Vkm:

o In questo caso, ogni riga della tabella che assegna Vkj=0 per ogni j=1,…,m rende il sequente Γ⊢∇ falso.

3. Foglia del tipo Ai1,…,Ain ⊢():

o In questo caso, ogni riga della tabella che assegna Aij=1 per ogni j=1,…,n rende il sequente Γ⊢∇ falso.

3. Esempi di applicazione della procedura di decisione

Esempio 1: Sequente non tautologico

P→A∧B ⊢ (A∧B→R)∧(D∨M)
Consideriamo il sequente:

Secondo la procedura, l'albero di derivazione costruito rivela una foglia non assioma del tipo A, B⊢P,R. Questo
implica che possiamo ottenere una riga falsaria assegnando:
 A=1, B=1, P=0, R=0
 Non importa quali valori abbiano D e M.
Questa configurazione rende falso il sequente radice.
Esempio 2: Proposizione tautologica
Consideriamo la proposizione:

La procedura applicata al sequente ⊢Q→¬¬Q produce un albero che termina con una foglia di tipo assioma (identità
Q→¬¬Q

Q⊢Q), confermando che la proposizione è una tautologia.

Esempio 3: Proposizione non tautologica

Applicando la procedura al sequente ⊢(V→¬R) →(¬V→R), l'albero di derivazione include una foglia non assioma,
Consideriamo la proposizione: (V→¬R) →(¬V→R)

indicante che la proposizione non è una tautologia. La riga falsaria corrisponde a V=0 e R=0, che rende il sequente
radice falso.
o Per stabilire che un sequente non è derivabile, serve che tutte le foglie siano senza proposizioni

proposizioni atomiche su entrambi i lati del ⊢.

composte? No. È sufficiente che ci sia almeno una foglia senza proposizioni composte e senza

Se una foglia ha il tipo ⊢P, Q, R, quale riga rende zero il sequente? La riga con P=0, Q=0, R=0 rende zero il
sequente, poiché la proposizione tt→(P∨Q) ∨ R risulta falsa con queste assegnazioni.


zero il sequente, poiché la proposizione (P∧Q) ∧R→⊥ risulta falsa.

o Se una foglia ha il tipo P, Q, R⊢ quale riga rende zero il sequente? La riga con P=1, Q=1, R=1 rende

PROCEDURE PER DETERMINARE SE UNA PROPOSIZIONE O UN SEQUENTE LOGICO È UNA TAUTOLOGIA,

UN'OPINIONE O UN PARADOSSO, e le modalità per trovare una riga che possa falsificare un sequente.
1. Classificazione delle proposizioni
 Tautologia: una proposizione pr è sempre vera.
 Paradosso: pr è sempre falsa.
 Opinione: pr è vera su alcune righe e falsa su altre.
 Non valida/soddisfacibile: pr non è una tautologia e c’è almeno una riga su cui è vera.

 Passo 1: Verifica se ⊢pr è derivabile.

2. Procedura di decisione per una proposizione pr

o Se è derivabile, pr è una tautologia.

o Altrimenti, passare al Passo 2.
 Passo 2: Poiché pr non è una tautologia, trova una riga su cui pr è falsa. Questo è ottenuto prendendo una
foglia dell'albero di derivazione che ha causato il fallimento e assegnando 1 alle variabili a sinistra e 0 a quelle

 Passo 3: Verifica se la negazione ⊢¬pr è derivabile.

a destra del sequente.

o Se ⊢¬pr è derivabile, pr è un paradosso.

o Altrimenti, pr è soddisfacibile e quindi un’opinione.
3. Classificazione di un sequente
 Un sequente Γ⊢Δ può essere:
o Tautologia: vero su tutte le righe.
o Paradosso: falso su tutte le righe.
o Opinione: vero su alcune righe e falso su altre.
4. Procedura di decisione per un sequente Γ⊢Δ
 Passo 1: Verifica se il sequente Γ⊢Δ è derivabile.
o Se sì, è una tautologia.
o Se no, prosegui al Passo 2.

o Applica la procedura di decisione alla negazione ⊢¬(Γ∧→Δ∨).

 Passo 2: Verifica la soddisfacibilità del sequente:

 Se ⊢¬(Γ∧→Δ∨) è NON derivabile, Γ⊢Δ è soddisfacibile e quindi un’opinione.

 Se ⊢¬(Γ∧→Δ∨) è derivabile, allora Γ⊢Δ è insoddisfacibile, quindi è un paradosso.

 Per falsificare un sequente A1,…,An⊢B1,…,Bm, si può considerare una riga con Ai=1e Bj=0. Questo
corrisponde alla riga che rende vera la negazione del sequente.
Questa procedura consente di determinare la natura logica di una proposizione o di un sequente attraverso
derivazioni formali senza dover costruire
tabelle di verità.

LA CORRETTEZZA DELLE PROCEDURE

DI DECISIONE IN LOGICA CLASSICA
PROPOSIZIONALE, permettendo di
stabilire in modo automatico se un
sequente è una tautologia, un'opinione o
un paradosso. Questa dimostrazione si
basa sull’idea di regola valida, ossia una
regola che conserva la verità dei sequenti,
e successivamente viene introdotto il
concetto di regola sicura. La nozione di
regola valida per regole di inferenza di sequenti in logica classica proposizionale si basa sulla capacità della regola di
preservare la verità dei sequenti da una riga all'altra, cioè dall'alto verso il basso in una dimostrazione. In particolare,
una regola si dice valida se, assumendo che tutti i sequenti premessa siano veri su una determinata riga r, allora
anche il sequente conclusione risulta vero sulla stessa riga r. Questa riga deve includere tutte le variabili
proposizionali coinvolte in almeno una delle proposizioni all'interno dei sequenti della regola. In altre parole, la validità
implica che, su ogni riga r di una tabella di verità che verifica i sequenti premessa, anche la conclusione della regola
sarà verificata.

Per stabilire se una regola di inferenza sia valida in logica classica, si considera la tabella di verità estesa delle
proposizioni coinvolte. Le regole di inferenza vengono analizzate distinguendo tra:
1. Regole a una premessa:
o Una regola del tipo Γ1⊢Δ1⇒Γ2⊢Δ2 è valida se, supponendo vero il sequente premessa Γ1⊢Δ1 su una certa riga
r, anche il sequente conclusione Γ2⊢Δ2 risulta vero su quella stessa riga.

2. Regole a due premesse:

o Una regola del tipo Γ1⊢Δ1 e Γ2⊢Δ2⇒Γ3⊢Δ3 è valida se, supponendo veri entrambi i sequenti premessa (Γ1⊢Δ1
e Γ2⊢Δ2) su una riga r, il sequente conclusione Γ3⊢Δ3 risulta vero su quella stessa riga.

Per stabilire se una proposizione del tipo pr→pr′ è vera (assume valore 1) su una specifica riga r della sua tabella di
verità, è sufficiente verificare la seguente condizione:
 Se pr=1su r, allora deve anche essere pr′=1 su r. In altre parole, per sapere se pr → pr′ è vero su r, non è
necessario esaminare tutti i possibili valori di pr e pr′ su quella riga. Basta considerare che:
1. Se pr=0, allora pr→pr′ è automaticamente vera su quella riga, indipendentemente dal valore di pr′. Questo è
coerente con la definizione di implicazione materiale in logica classica, dove un antecedente falso rende
sempre l'implicazione vera.
2. Se pr=1, allora l'implicazione pr→pr′ sarà vera solo se pr′=1 su quella stessa riga. Se pr′=0, l'implicazione
risulterà falsa su r.

Proposizioni e Lemmi
 Proposizione 9.10 e
Proposizione 9.11: Stabiliscono
che una regola è valida se
l'implicazione che rappresenta la
sua struttura è una tautologia. Per
le regole ad una premessa, si
verifica se (Γ1→Δ1)→ (Γ2→Δ2) è
tautologia; per le regole a due

∧ (Γ2→Δ2)→ (Γ3→Δ3) è una

premesse, si verifica se (Γ1→Δ1)

tautologia.

Validità e conservazione della verità

 se una regola di inferenza è
valida, allora conserva la verità
tautologica dei sequenti: se i
sequenti premessa sono tautologie, anche il sequente conclusione lo sarà.

Supponiamo di avere una regola valida nel linguaggio proposizionale e che tutti i suoi sequenti premessa siano tautologie.
Essendo tautologie, questi sequenti premessa sono veri su ogni riga della rispettiva tabella di verità. Prendiamo una riga arbitraria r
nella tabella di verità che contiene tutte le variabili proposizionali presenti nei sequenti della regola (sia nelle premesse sia nella
conclusione). Per definizione di tautologia, sappiamo che tutti i sequenti premessa saranno veri su questa riga r, poiché sono veri
su ogni possibile assegnazione di verità. Poiché la regola è valida, sappiamo che se tutte le premesse sono vere su una
determinata riga, allora anche la conclusione della regola deve essere vera su quella stessa riga. Quindi, su questa riga r, il
sequente conclusione risulta vero. Poiché abbiamo scelto r come una riga arbitraria e tutte le premesse sono tautologie (e quindi
vere su ogni riga), possiamo ripetere lo stesso ragionamento per tutte le altre righe della tabella di verità. Di conseguenza, anche la
conclusione deve essere vera su ogni riga della tabella di verità. Poiché la conclusione è vera su ogni riga della sua tabella di
verità, ne segue che essa stessa è una tautologia.

 Lemma 9.13 (scorciatoia1) e Lemma 9.14 (scorciatoia2): Questi lemmi propongono delle scorciatoie per
verificare la validità delle regole. La scorciatoia si basa sull'analisi delle righe della tabella di verità in cui tutte
le premesse risultano vere, controllando che anche la conclusione sia vera su tali righe.

o Lemma 9.13: Per una regola ad una premessa, la condizione di validità è che per ogni riga r, se Γ1→Δ1=1 e
Γ2=1, allora Δ2=1. Se esiste una riga in cui queste condizioni sono soddisfatte ma Δ2=0, allora la regola non è
valida.
o Se la condizione Γ1→Δ1=1 e Γ2=1⇒Δ2=1 è soddisfatta su ogni riga, la regola è valida.
o Se esiste una riga con Γ1→Δ1=1, Γ2=1 e Δ2=0, allora la regola è non valida.

In altre parole, se su una riga r si verificano entrambe le condizioni Γ1→Δ1=1 e Γ2=1, allora deve essere vera anche
Δ2=1. Se questa condizione è soddisfatta su ogni riga, allora possiamo concludere che la regola è valida, in quanto
conserva la verità dei sequenti dalla premessa alla conclusione su tutte le righe della tabella. Questo significa che, su
almeno una riga della tabella di verità, si verificano le condizioni Γ1→Δ1=1 e Γ2=1, ma Δ2 risulta falsa (0). Tale riga
costituisce un controesempio alla validità della regola, poiché mostra una situazione in cui la regola non conserva la
verità: la premessa è vera, ma la conclusione è falsa. In pratica, questo lemma fornisce un metodo per evitare di
dover controllare tutte le righe della tabella di verità per determinare se una regola di inferenza è valida o meno.
Anziché controllare ogni singola riga, possiamo concentrarci sulle righe in cui Γ1→Δ1=1 e Γ2=1, poiché solo in queste
righe la validità della regola può essere messa in discussione. Se troviamo una riga in cui queste condizioni sono
soddisfatte e Δ2=0, allora la regola non è valida. Se invece in tutte le righe in cui Γ1→Δ1=1 e Γ2=1 risulta anche
Δ2=1, allora la regola è valida.
o Lemma 9.14: Per una regola a due premesse, la condizione di validità è che per ogni riga r, se Γ1→Δ1, Γ2→Δ2 e
Γ3=1, allora Δ3=1. Se esiste una riga con queste condizioni in cui Δ3=0, la regola non è valida.
Questo significa che se entrambe le premesse sono vere, allora anche la conclusione deve essere vera. In
altre parole, la regola di inferenza è valida se ogni volta che le premesse sono vere, anche la conclusione è
vera.

In conclusione, la correttezza delle procedure di decisione in logica classica proposizionale si basa sull’idea di
preservare la verità: una regola di inferenza è considerata valida se, assumendo vere le premesse su una riga della
tabella di verità, garantisce la verità della conclusione su quella stessa riga. I lemmi forniscono dei metodi pratici per
verificare la validità delle regole, riducendo il controllo alle righe significative della tabella di verità.

Proposizione 1: (Γ1→Δ1) → (Γ2→Δ2) Questa proposizione afferma che se Γ1 implica Δ1 allora Γ2 deve implicare Δ2. Le righe
che soddisfano la condizione di verità della proposizione sono quelle in cui:
 Γ1→Δ1=0: significa che Γ1 è vera e Δ1 è falsa. In questo caso, la proposizione diventa vera indipendentemente dal valore
di Γ2→Δ2.

Proposizione 2: (Γ1→Δ1) ∧ (Γ2→Δ2) → (Γ3→Δ3) Questa proposizione è più complessa e afferma che se entrambe le premesse
 Γ2=0: significa che Γ2 è falsa. Anche in questo caso, Γ2→Δ2 sarà sempre vera, quindi la proposizione è vera.

sono vere, allora deve essere vera anche la conclusione. Le condizioni che portano alla verità della proposizione sono:
 Γ1→Δ1=0: in questo caso, la proposizione è vera, indipendentemente dal valore delle altre espressioni.
 Γ2→Δ2=0: anch'essa rende vera l'intera proposizione per lo stesso motivo.
 Γ3=0: anche in questo caso, la proposizione è vera.

Quindi, possiamo concludere che:

 La regola conserva la verità nelle righe dove le premesse sono false (o portano a 0).
 La validità della regola dipende dall’analisi delle righe in cui tutte le implicazioni sono vere, e in tali casi, la conclusione
deve anch'essa risultare vera.
Questo approccio fornisce un metodo efficace per verificare la validità delle implicazioni e delle regole di inferenza, riducendo il
numero di casi da considerare.

Tutte le regole (assiomi) del calcolo LCp sono tautologie, ovvero proposizioni vere in ogni
interpretazione e TUTTE le regole di LCp sono valide.

DIMOSTRAZIONE:
 Assioma dell’identità (ax-id): Γ1, A, Γ2⊢∆1, A, ∆2 è UNA TAUTOLOGIA
afferma che se in un sequente compare una proposizione A sia a sinistra che a destra, allora è sempre
vera perché segue direttamente dall’uso dell'implicazione.

Il ragionamento si basa sul fatto che, se l’intera congiunzione (Γ1∧A) ∧ Γ2 è vera in una certa riga della tabella di

Quindi, anche il termine (Δ1∨A) ∨ Δ2 sarà vero, poiché contiene A come disgiunto. Poiché questo ragionamento vale
verità (riga generica r), allora A deve necessariamente essere vera (dato che è una componente della congiunzione).

per una riga qualsiasi della tabella di verità, si conclude che il sequente è vero su ogni riga e, pertanto, è una
tautologia. In altre parole, l’assioma di identità è sempre vero indipendentemente dai valori di verità delle altre formule
in Γ e Δ, soddisfacendo così la proprietà di tautologia.

 Assioma del falso (ax-⊥): Γ1, ⊥, Γ2⊢∇ è UNA TAUTOLOGIA

qualsiasi cosa segue da una contraddizione. Esprime che se partiamo da una proposizione falsa (come ⊥,
che simboleggia il falso), qualsiasi conclusione segue logicamente.

Poiché l’elemento ⊥ all’interno della congiunzione fa sì che (Γ1∧⊥) ∧ Γ2 sia sempre falso (o assegni sempre il valore
di verità 0), l’intera proposizione implicativa assume il valore di verità 1, rendendo la proposizione complessiva una

essere formalizzata come: ⊥⊢V dove ⊥ rappresenta la falsa affermazione "Sono Superman" e V l'affermazione "Sono
tautologia. Un esempio chiarisce questo concetto: la proposizione "Se fossi Superman, sarei in grado di volare" può
modo analogo, la proposizione: ⊥⊢¬V che rappresenta "Se fossi Superman, non sarei in grado di volare", è
in grado di volare." Poiché la premessa è falsa, l'intera implicazione è vera per la natura dell’implicazione logica. In

anch’essa una tautologia.

Validità delle Regole:

o Scambio Sinistro (scsx) e Scambio Destro (scdx): dimostrano che l’ordine delle proposizioni non
influisce sulla verità di un sequente; l’ordine dei termini nei congiunti a sinistra o nei disgiunti a destra
non cambia la validità.

La regola di scambio a sinistra (scsx) afferma che è possibile scambiare l’ordine delle proposizioni a sinistra del
simbolo di conseguenza senza alterare la validità del sequente. In altre parole, se abbiamo un sequente nella forma:
Σ,Γ1,Θ,Γ2,Δ⊢∇ possiamo riscriverlo come: Σ,Γ2,Θ,Γ1,Δ⊢∇

La validità di questa regola è evidente perché il valore di verità della congiunzione (Σ∧Γ1∧Θ∧Γ2∧Δ) non dipende
dall'ordine delle proposizioni, essendo la congiunzione un’operazione commutativa. Per dimostrare rigorosamente
questa validità, utilizziamo il lemma scorciatoia1 (9.13).
 Ipotesi: Sia r una riga fissa della tabella di verità dei sequenti coinvolti, per cui:
1. (Σ∧Γ1∧Θ∧Γ2∧Δ)→∇∨=1 su r.

 Tesi: Dimostrare che ∇∨=1 su r.

2. (Σ∧Γ2∧Θ∧Γ1∧Δ)=1 su r.

Dimostrazione: Dall’ipotesi (2), sappiamo che ogni congiunto ha valore di verità 1, quindi anche la proposizione

regola, concludiamo che ∇∨=1 su r. Questo soddisfa le condizioni del lemma scorciatoia1, dimostrando la validità
completa ((Σ∧Γ1)∧Θ∧Γ2)∧Δ sarà vera su r. Di conseguenza, dall’ipotesi (1) e dalla verità della premessa della

della regola di scambio a sinistra.

La regola di scambio a destra (scdx) afferma che possiamo scambiare l’ordine delle proposizioni a destra del
simbolo di conseguenza, ottenendo: Γ⊢Σ, Δ1,Θ,Δ2,∇ e riscriverlo come: Γ⊢Σ,Δ2,Θ,Δ1,∇. Questa validità è evidente,
poiché il valore di verità della disgiunzione (Σ∨Δ1∨Θ∨Δ2∨∇) non cambia con l’ordine degli elementi, essendo la
disgiunzione un’operazione commutativa. Applichiamo anche qui il lemma scorciatoia1.
 Ipotesi: Sia r una riga fissa della tabella di verità per cui:
1. Γ→(Σ∨Δ1∨Θ∨Δ2∨∇)=1 su r.
2. Γ=1 su r.
 Tesi: Dimostrare che (Σ∨Δ2∨Θ∨Δ1∨∇)=1su r.
Dimostrazione: Dalle ipotesi (1) e (2) e dalla definizione di verità dell’implicazione, segue che
(Σ∨Δ1∨Θ∨Δ2∨∇)=1su r. Poiché almeno un disgiunto in questa disgiunzione ha valore 1 su r, possiamo concludere
che anche (Σ∨Δ2∨Θ∨Δ1∨∇) è vera, poiché la disgiunzione non dipende dall’ordine dei termini.

o Regola della Congiunzione (&-D e &-S): se possiamo derivare A e B separatamente, allora possiamo
derivare anche A&B.

La regola &-D afferma che se possiamo derivare sia A che B in modo indipendente da Γ e Δ, possiamo concludere
che A∧B è derivabile, concludendo:

Per dimostrarne la validità, usiamo il lemma scorciatoia 2 (9.14), verificando le ipotesi e

tesi di tale lemma.
Ipotesi Sia r una riga fissa della tabella di verità dei sequenti, tale che:
1. Γ→(A∨Δ) = 1su r.
2. Γ→(B∨Δ) =1 su r.
3. Γ=1 su r.
Tesi Dimostrare che (A∧B∨Δ) =1 su r.
Dimostrazione Dall’ipotesi (3) e (1), possiamo dedurre che (A∨Δ) =1 su r. Analogamente, dall’ipotesi (3) e (2)
otteniamo che (B∨Δ)=1 su r. Questo ci porta a considerare due casi:
 Caso 1: A=1 su r. In questo caso, dall’ipotesi (2) otteniamo che almeno una proposizione in B∨Δ è vera su r,

o Sottocaso 1a: B=1 su r. Con A=1 e B=1 otteniamo A∧B=1 su r, quindi (A∧B) ∨Δ=1, e la tesi è verificata.
ovvero:

 Caso 2: Δ=1 su r. In questo caso, (A∧B) ∨Δ=1 è immediatamente vera.

o Sottocaso 1b: Δ=1 su r. Questo implica che anche (A∧B)∨Δ=1, quindi la tesi è verificata.

Quindi, la condizione del lemma scorciatoia2 è verificata e, per il lemma, la regola &-D è valida.

La regola &-S afferma che, se A e B sono congiunti a sinistra, possiamo combinarli con l’operatore & in modo che:

Questa regola è intuitiva, poiché la virgola a sinistra del simbolo di conseguenza è interpretata come
congiunzione logica.
Anche qui, applichiamo il lemma scorciatoia1 (9.13), verificando ipotesi e tesi.
Ipotesi Sia r una riga fissa della tabella di verità per cui:
 1. (Γ∧A∧B)→Δ=1su r.
2. (Γ∧A∧B)=1su r.
Tesi Dimostrare che Δ=1 su r.
Dimostrazione Dall’ipotesi (1), poiché (Γ∧A∧B)=1 su r, ogni proposizione di Γ, A, e B è vera su r, quindi anche A=1 e
B=1 su r. Da ciò segue che (Γ∧A∧B)=1, che implica, per la verità dell’implicazione, che Δ=1 su r, verificando la tesi.
Poiché la condizione del lemma scorciatoia1 è rispettata, possiamo concludere che la regola &-S è valida.

o Regola della Disgiunzione (∨-D e ∨-S): serve per la disgiunzione, affermando che se almeno una
delle proposizioni è vera, allora possiamo derivare la loro disgiunzione.

La regola ∨-S afferma che se possiamo derivare separatamente A e B da Γ per ottenere Δ,

allora possiamo derivare anche A∨B per ottenere Δ:

Per dimostrare la validità della regola, usiamo il lemma scorciatoia2 (9.14), verificando le
ipotesi e la tesi del lemma.
Ipotesi Sia r una riga fissa della tabella di verità dei sequenti coinvolti nella regola per cui valgono:
1. (Γ∧A)→Δ=1 su r.
2. (Γ∧B)→Δ=1su r.
3. (Γ∧(A∨B))=1 su r.

Tesi Dimostrare che Δ=1 su r.

Dimostrazione Dall’ipotesi (3), sappiamo che su r ogni proposizione in Γ è vera, quindi Γ=1 e anche A∨B=1 su r.
Questo ci porta a considerare due casi:
 Caso 1: A=1 su r. Poiché Γ=1, ne segue che (Γ∧A) =1 su r. Dall’ipotesi (1) e per la verità dell’implicazione,
otteniamo che Δ=1 su r. La tesi è verificata in questo caso.
 Caso 2: B=1 su r. Poiché Γ=1 su r, segue che (Γ∧B) =1 su r. Dall’ipotesi (2) e per la verità dell’implicazione,

La condizione del lemma scorciatoia2 è quindi rispettata e, per il lemma, la regola ∨-S è valida.
otteniamo che Δ=1 su r, verificando la tesi anche in questo caso.

La regola ∨-D afferma che se possiamo derivare A e B (insieme) dalla premessa Γ, allora possiamo derivare A∨B

Questa regola risulta evidente in quanto, per definizione logica, la disgiunzione (A∨B) nella
conclusione rappresenta lo stesso valore di verità dell'espressione (A,B)∨ nella premessa.

Dimostrazione Consideriamo la proposizione (A,B) ∨Δ. Per definizione di disgiunzione, possiamo riscrivere questa
espressione come (A∨B) ∨Δ. Pertanto, i sequenti della premessa e della conclusione rappresentano esattamente la
stessa proposizione: Γ→((A∨B) ∨Δ). Quindi, la regola ∨-D è valida.

9.10.9 Validità di ¬
La regola ¬-D stabilisce che se Γ, A⊢Δ è valido, allora si può derivare Γ⊢¬A, Δ:

Per dimostrare la validità della regola, usiamo il lemma scorciatoia1 (9.13), verificando che la
condizione del lemma è soddisfatta.
Ipotesi
Sia r una riga fissa della tabella di verità dei sequenti coinvolti nella regola per cui valgono:
1. (Γ∧ A) → Δ=1 su r.
2. Γ=1 su r.
Tesi Dimostrare che (¬A∨ Δ)=1su r.
Dimostrazione Procediamo considerando i casi per il valore di verità di A su r:
 Caso 1: A=1 su r. Dall’ipotesi (2), sappiamo che (Γ∧A) =1 su r. Quindi, per l’ipotesi (1) e la definizione di
verità dell’implicazione, segue che Δ=1 su r. Di conseguenza, (¬A∨Δ) =1 su r per la definizione di
disgiunzione, e quindi la tesi è verificata.
 Caso 2: A=0 su r. In questo caso, ¬A=1 su r, e quindi (¬A∨Δ)= 1 su r, il che verifica la tesi anche in questo
caso.
La condizione del lemma scorciatoia1 è quindi verificata, e per il lemma concludiamo che la regola ¬-D è valida.

La regola ¬-S afferma che, se Γ⊢A, Δ è valido, allora si può derivare Γ,¬A⊢Δ:
Per mostrare la validità della regola, usiamo nuovamente il lemma scorciatoia1 (9.13),
verificando che vale la condizione richiesta.

Ipotesi Sia r una riga fissa della tabella di verità dei sequenti coinvolti nella regola per cui
valgono:
1. Γ→(A∨Δ) =1 su r.
2. (Γ∧¬A) =1 su r.
Tesi Dimostrare che Δ=1 su r.
Dimostrazione Dall'ipotesi (2) sappiamo che ogni proposizione in Γ∧¬A è vera su r, quindi in particolare Γ=1 e ¬A=1
su r. Per la definizione di verità della negazione, sappiamo quindi che A=0 su r. Ora, dall'ipotesi (1) e la definizione di
verità dell’implicazione, segue che (A∨Δ) =1 su r, ovvero o A=1 oppure almeno una proposizione in Δ è vera su r.
Tuttavia, poiché abbiamo dedotto che A=0 su r (dall’ipotesi (2)), l'unica possibilità è che Δ=1 su r, il che verifica la tesi.
Poiché la condizione del lemma scorciatoia1 è rispettata, per il lemma possiamo concludere che la regola ¬-S è
valida.

9.10.11 Validità di →
La regola →-D afferma che, se Γ, A⊢B, Δ è valido, allora possiamo derivare Γ⊢ A→B, Δ:

Per dimostrare la validità della regola, utilizziamo il lemma scorciatoia1 (9.13) verificando che la
condizione di tale lemma è soddisfatta.
Ipotesi Sia r una riga fissa della tabella di verità dei sequenti coinvolti nella regola per cui
valgono:
1. (Γ∧A) → (B∨Δ) =1 su r.

Tesi Dimostrare che (A→B) ∨Δ=1 su r.

2. Γ=1 su r.

Dimostrazione
Procediamo per casi sul valore di verità di A su r:
 Caso 1: A=1 su r. Dall’ipotesi (2) sappiamo che Γ=1 su r, quindi (Γ∧A) =1 su r. Per l’ipotesi (1), segue che

o Sottocaso 1.1: B=1. In tal caso, per la definizione di verità dell'implicazione, A→B=1, quindi (A→B) ∨Δ=1, e
(B∨Δ) =1 su r, cioè o B=1 oppure una proposizione in Δ è vera su r. Pertanto, analizziamo due sottocasi:

o Sottocaso 1.2: Δ=1. Per la definizione di verità della disgiunzione, segue che (A→B) ∨ Δ=1 su r, verificando
la tesi è verificata.

la tesi.

della disgiunzione, (A→B) ∨ Δ=1, che dimostra la tesi.

 Caso 2: A=0 su r. In questo caso, ¬A=1, quindi per la verità dell’implicazione A→B=1 su r. Per la definizione

La condizione del lemma scorciatoia1 è quindi verificata, e per il lemma concludiamo che la regola →-D è valida.

La regola →S stabilisce che, se Γ⊢A, Δ sono validi, allora possiamo derivare Γ, A→B⊢Δ:

Per dimostrare la validità della regola, utilizziamo il lemma scorciatoia2 (9.14) e

verifichiamo che la condizione del lemma è soddisfatta.
Ipotesi Sia r una riga fissa della tabella di verità dei sequenti coinvolti nella regola per cui
valgono:
1. Γ→(A∨Δ) =1.
2. (Γ∧B) →Δ=1.
3. (Γ∧(A→B))=1.
Tesi Dimostrare che Δ=1.
Dimostrazione Dall'ipotesi (3) sappiamo che ogni proposizione di Γ∧(A→B) è vera su r, quindi in particolare Γ=1 e
A→B=1 su r. Per l'ipotesi (1) e la definizione di verità dell'implicazione, segue che (A∨Δ) =1. Da A→B=1, abbiamo
due casi:
 Caso 1: A=0. Dal momento che (A∨Δ) =1 su r, una delle proposizioni in A∨Δ deve essere vera; poiché A=0,
segue che Δ=1, e la tesi è verificata.
 Caso 2: B=1. Poiché Γ=1 su r, anche (Γ∧B) = 1 su r. Per l’ipotesi (2), segue che Δ=1, verificando la tesi.
La condizione del lemma scorciatoia2 è dunque rispettata, e per il lemma concludiamo che la regola →-S è valida.

Il teorema 9.15 nel contesto del calcolo per i sequenti della Logica Classica Proposizionale (LCp) afferma
la validità delle regole di inferenza usate nel sistema LCp. In altre parole, il teorema 9.15 garantisce che
tutte le regole di inferenza utilizzate nella logica classica proposizionale, come quelle per i connettivi logici,
sono valide. Ciò significa che, applicando queste regole, si preserva sempre la verità dei sequenti: se i
sequenti delle premesse sono veri, anche quelli delle conclusioni lo saranno. La validità delle regole
dimostrata tramite questo teorema assicura la correttezza del sistema logico LCp, permettendo di derivare
conclusioni corrette a partire da premesse vere.

La correttezza della procedura di decisione per il calcolo dei sequenti della Logica Classica Proposizionale
(LCp) si basa sulla conservazione della verità attraverso le regole di inferenza.
1. Struttura dell'Albero e Direzione della Verità
In un albero di deduzione costruito esclusivamente con regole valide di LCp, ogni nodo rappresenta un
sequente e i rami rappresentano l'applicazione di una regola di inferenza che porta a nuovi sequenti. Ecco
come funziona la diffusione della verità e della falsità in questo albero:
 La verità "scende" dall'alto verso il basso: Se partiamo da un sequente vero nella radice dell'albero
(in alto), e applichiamo solo regole di inferenza valide, la verità viene "trasferita" dai nodi superiori a
 quelli inferiori. Questo significa che, se le premesse di una regola sono vere, anche la conclusione
ottenuta applicando la regola sarà vera.
 La verità "sale" dal basso verso l'alto: Al contrario, se iniziamo con foglie dell'albero (nodi più in
basso) e "risaliamo" l'albero applicando le regole, possiamo mantenere la verità dei sequenti. La
correttezza della procedura di decisione si basa sulla capacità di questa verità di fluire in entrambe le
direzioni, garantendo coerenza attraverso l'albero.
2. Diffusione della Falsità
La falsità funziona in modo leggermente diverso:
 La falsità scende solo dalla foglia alla radice: Se troviamo una foglia falsa, possiamo risalire
lungo il ramo specifico che parte da quella foglia fino alla radice, trasferendo la falsità solo lungo
quel percorso. Questo implica che una falsità in una foglia può invalidare un'intera deduzione.
3. Nozione di Regola Valida
Una regola di inferenza di sequenti è valida se conserva la verità quando viene applicata. In altre parole:
 La regola è valida se e solo se la sua applicazione su sequenti veri produce un sequente
conclusione vero. La verità "scende" dall'alto al basso attraverso l'applicazione della regola,
conservandosi in ogni nodo dell'albero di deduzione.

4. Conclusione sulla Correttezza

Grazie alla struttura dell'albero e alla proprietà delle regole valide di LCp, possiamo garantire che se il
sequente iniziale (radice) è vero, tutte le conclusioni a cui giungiamo nell'albero di deduzione saranno vere.
La procedura è quindi corretta perché garantisce la verità dei sequenti lungo tutta la deduzione, senza
introdurre contraddizioni.
In sintesi:
 Un albero costruito con regole di LCp valide permette alla verità di scendere dalla radice alle foglie
e di risalire dalle foglie alla radice, mantenendo la correttezza della deduzione.
 Se esiste una falsità, essa si propaga lungo un percorso specifico dall'alto al basso, invalidando
solo quel percorso.

La nozione di regola valida per le regole di inferenza nei calcoli di sequenti ha come base il concetto di conservazione
della verità tra sequenti. In altre parole, una regola di inferenza è valida se è in grado di trasformare sequenti veri
(nelle premesse) in sequenti veri (nella conclusione) su una stessa riga di una tabella di verità, garantendo quindi la
verità “dall’alto verso il basso”. Una regola di inferenza per i sequenti è detta valida se, dato un certo contesto e sotto
specifiche condizioni, la verità dei sequenti nelle premesse garantisce la verità del sequente nella conclusione sulla
stessa riga di una tabella di verità. La riga in questione deve contenere tutte le variabili proposizionali che compaiono
in almeno una delle proposizioni dei sequenti della regola. Questa definizione implica che:

1. Se tutti i sequenti premessa di una regola sono veri su una certa riga rrr, allora anche il sequente conclusione
deve essere vero su quella stessa riga rrr.
2. La validità della regola è intesa come una conservazione della verità dall’alto verso il basso, ossia lungo la
derivazione.

La validità di una regola può essere vista

come una proprietà di coerenza logica: la
regola non introduce contraddizioni o falsità
lungo il percorso di derivazione. Per questo,
una regola è valida se garantisce che la
verità sia mantenuta su ogni riga dalla
premessa (o dalle premesse) alla
conclusione. Se, al contrario, esistesse una
riga per la quale la conclusione non è vera
nonostante tutte le premesse siano vere, la
regola risulterebbe non valida.

Le regole di LCp sono:

 Valide: questo significa che se tutte le premesse di un sequente sono vere in una determinata riga
della tabella di verità, anche la conclusione è vera in quella stessa riga.
 Sicure: una regola è sicura se è valida e anche tutte le sue regole inverse sono valide. Le regole
inverse consentono di risalire dagli effetti (conclusioni) alle cause (premesse) mantenendo la
validità delle verità.
 Per ogni regola di LCp, si può definire una regola
inversa. Questo permette di passare dalla
conclusione alle premesse. Le regole inverse
sono valide per ogni riga
della tabella di verità, quindi
applicandole otteniamo una
procedura che preserva la
verità "sia dall'alto verso il
basso che dal basso verso
l'alto". Questo concetto di
sicurezza delle regole è
cruciale per le procedure di
decisione di LCp, poiché
consente di costruire alberi
di derivazione nei quali la
verità e la falsità possono
"scendere" o "salire"
attraverso i nodi dell'albero
senza perdere coerenza.
Un altro aspetto essenziale è che le regole di LCp, eccetto le regole di scambio, diminuiscono la
complessità dei sequenti. Questo significa che ogni applicazione di una regola produce sequenti più
semplici, permettendo di avvicinarsi progressivamente a sequenti atomici o assiomi, che sono facilmente
verificabili. Questa proprietà è fondamentale per assicurare che le procedure di decisione di LCp siano
finite e terminate.

Grazie alla validità delle regole inverse, ogni regola di LCp è sicura. Questo implica che in un albero
costruito solo con regole di LCp:
 La verità può scendere dalla radice verso tutte le foglie. La verità su una riga scende dall'alto verso
il basso: se tutte le foglie di un albero di derivazione sono vere su una determinata riga r, allora anche il
sequente radice dell'albero sarà vero su quella stessa riga.
 La verità può anche salire dalle foglie alla radice, e quindi, se tutte le foglie sono vere, anche la
radice sarà vera. La verità sale dal basso verso l'alto: se il sequente radice è vero su una riga r, allora
questa verità si propaga verso ogni singola foglia dell'albero.

Per dualità con la proprietà della verità, possiamo dimostrare anche il comportamento della falsità:
 Se una foglia è falsa su una riga, la falsità "scende" fino alla radice.
 Se la radice fosse vera, per la validità delle regole inverse, la verità risalirebbe verso ogni foglia,
contraddicendo l'ipotesi che una foglia sia falsa. Pertanto, se una foglia è falsa, anche la radice
deve essere falsa.

Queste proprietà consentono di garantire che, in un albero di derivazione, la verità possa "fluttuare" liberamente tra
foglie e radice, sia verso il basso che verso l'alto, senza perdita di validità.
Negli alberi costruiti con regole di LCp, la falsità ha un comportamento opposto rispetto alla verità:
 La falsità su una riga scende da una singola foglia fino alla radice.
Supponiamo che in un albero di derivazione esista una foglia falsa su una riga r. Vogliamo dimostrare che anche il
sequente radice dell'albero è falso su quella stessa riga r.
1. Per Assurdo: Supponiamo che il sequente radice sia vero su r.
2. Validità delle Inverse: Dal momento che le regole inverse di LCp sono valide, possiamo propagare la verità
della radice verso l'alto, risalendo l'albero fino a ciascuna foglia.
3. Contraddizione: Se la verità sale verso ogni foglia, dovremmo concludere che tutte le foglie sono vere su r.
Ma abbiamo assunto che almeno una foglia è falsa su r, il che porta a una contraddizione.
4. Conclusione: Quindi, l'ipotesi che il sequente radice sia vero su r è insostenibile. Deve essere invece falso su
r, come volevamo dimostrare.

La falsità "scende" nell'albero: se una foglia è falsa su una riga r, anche la radice deve essere falsa su quella riga.
Questa proprietà è particolarmente utile nei procedimenti di dimostrazione per assurdo, poiché permette di mostrare
che la falsità si propaga verso la radice se è presente in una foglia.
Grazie alla sicurezza e alla validità delle regole di LCp, possiamo affermare che:
 La verità e la falsità si propagano in modo coerente attraverso l'albero di derivazione.
 La verità può scendere dalla radice verso le foglie e salire dalle foglie alla radice.
 La falsità, invece, scende dalla foglia alla radice, garantendo che un errore (falsità) in una parte dell'albero si
rifletterà nella radice.
Le regole del calcolo LCp (Logica Classica Proposizionale) sono giustificate usando tautologie della logica classica,
dimostrate con tabelle di verità.
1. Regole di Congiunzione (∧) e Disgiunzione (∨)
 Congiunzione sinistra: la virgola a sinistra del simbolo del sequente (Γ⊢Δ) rappresenta il fatto che ogni
elemento di Γ è vero. La regola di congiunzione sinistra (per cui Γ, A, B⊢Δ implica Γ,A∧B⊢Δ) è accettabile
poiché rappresenta il significato della congiunzione nella logica classica: A∧B è vero solo se entrambi A e
BBB sono veri.
 Disgiunzione destra: se uno dei termini nel succedente (Δ\DeltaΔ) è vero, il sequente è vero. La regola di
disgiunzione destra si basa sulla logica classica: se Γ⊢A \Gamma \vdash AΓ⊢A e Γ⊢B\Gamma \vdash BΓ⊢B,
allora Γ⊢A∨B\Gamma \vdash A \lor BΓ⊢A∨B è vero, poiché A∨BA \lor BA∨B è vero se uno dei due lo è.

2. Assiomi di Identità e del Falso

 Assioma di Identità (ax−id): la formula (Γ, A, Γ′⊢Δ, A, Δ′) riflette una tautologia classica, ovvero che se A

( G1 & A ) & G2 → ( D1 ∨ A ) ∨ D2.

appare sia nel contesto di sinistra che in quello di destra, il sequente è automaticamente valido

 Assioma del Falso (ax−⊥): data una contraddizione come ⊥ (falsità), il sequente è automaticamente valido,
poiché una premessa falsa implica tutto Γ, ⊥, Γ ′ ⊢ ∇ segue dalla tautologia classica (G1& ⊥ ) & G2 → D
ponendo G1 al posto di Γ, G2 al posto di Γ′ e D al posto di ∇.

3. Regole di Scambio (sx e dx)

 Scambio sinistra (sc sx): questa regola consente di riordinare le formule nel contesto di sinistra. La sua
giustificazione proviene dalla commutatività della congiunzione, secondo cui A∧B equivale a B∧A.
((((E & G1) & P) & G2) & D → N) → ((((E & G2) & P) & G1) & D → N)
 Scambio destra (scdx): consente di riordinare le formule nel contesto di destra, basata sulla commutatività

(G → (((E1 ∨ G1) ∨ P) ∨ G2) ∨ N) → (G → (((E1 ∨ G2) ∨ P) ∨ G1) ∨ N)

della disgiunzione (A∨B≡B∨A).

4. Regola di Congiunzione Destra (&−D)

 La regola deriva dalla tautologia classica (G→A ∨ D) ∧ (G→B ∨ D) → (G→ (A ∧ B) ∨ D), il che significa
 Se Γ⊢A, Δ e Γ⊢B, Δ, allora possiamo derivare Γ⊢A∧B, Δ.

che se entrambe le proposizioni sono vere, anche la loro congiunzione lo sarà.

(A ∨ D) & (B ∨ D) → (A & B) ∨ D che è un verso della distributività della disgiunzione sulla congiunzione
 In particolare il caso in cui Γ è la lista vuota e ∆ è semplicemente D segue dalla tautologia classica

 Se Γ, A⊢Δ e Γ, B⊢Δ, allora possiamo dedurre Γ, A∨B ⊢Δ.

5. Regola di Disgiunzione Sinistra (∨−S)

 Questa regola si basa sulla logica classica: (G∧ A→D) ∧ (G ∧ B→D) → (G ∧ (A ∨ B) →D), ovvero se D è
vero indipendentemente dal verificarsi di A o B, allora lo sarà anche per A∨B.

6. Regole di Negazione
 Negazione destra (¬−D): se Γ, A⊢Δ, allora Γ⊢¬A, Δ. Questa regola segue dalla tautologia classica
(G∧ A→D) → (G→¬A∨D), affermando che se aggiungiamo ¬A nel succedente, manteniamo la validità.
 Negazione sinistra (¬−S): se Γ⊢A, Δ, allora Γ, ¬A⊢Δ. Questa regola si basa sulla tautologia (G→A∨D) →
(G∧¬A→D).

7. Regole di Implicazione

(G∧A→B∨D) → (G→(A→B) ∨ D), cioè, dato che (A→B) ≡(¬A∨B), possiamo derivare (G→A→B)
 Implicazione destra (→−D): se Γ, A⊢B, Δ allora Γ⊢A→B, Δ. Questa segue dalla tautologia

combinando negazione e disgiunzione.

 tautologia (G→A∨D) ∧ (G∧B→D) → (G∧(A→B) → D).
 Implicazione sinistra (→−S): se Γ⊢A, Δ e Γ, B⊢Δ, allora Γ, A→B⊢Δ. La giustificazione si basa sulla

NOZIONE DI TEORIA PROPOSIZIONALE ED ESEMPI

teorie proposizionali rappresentano estensioni della LCp integrate con assiomi specifici ed extralogici.
Questo ci consente di esplorare come una teoria scientifica possa essere formalizzata logicamente a
partire da una base di assiomi extralogici e di regole di inferenza.

Una teoria proposizionale si definisce come un'estensione della logica classica proposizionale (LCp)
ottenuta aggiungendo:
1. Un numero finito di assiomi extralogici:
o Questi assiomi sono formule aggiuntive specifiche della teoria e non derivabili dalla LCp.
o Si indicano con una lista Ax1, Ax2,…,Axk, ciascuna rappresentante una proposizione considerata vera
nella teoria.
2. Regole di composizione a sinistra:
o Queste regole estendono le regole della LCp, permettendo di comporre le formule in modo specifico.
o La regola generale di composizione a sinistra è indicata come:
dove fr è una formula del linguaggio proposizionale della teoria, e Γ, Γ′ e
Δ sono insiemi di formule.

In sintesi, possiamo rappresentare una teoria proposizionale come:

TEORIA proposizionale=LOGICA proposizionale + regole di composizione + assiomi extralogici

Un sequente derivabile in una teoria proposizionale T è un sequente Γ⊢Δ tale che esista un albero di
derivazione con le seguenti proprietà:
 La radice dell’albero è proprio il sequente Γ⊢Δ.
 Ogni foglia dell’albero è un’istanza di un assioma di T, ossia:
o Un assioma logico della LCp;
o Oppure un assioma extralogico specifico di T.

 L’albero è costruito applicando le regole del calcolo T, cioè le regole della LCp insieme alle regole di
composizione e agli assiomi extralogici.
Questa struttura permette di derivare nuovi sequenti a partire da una combinazione di assiomi e regole
specifiche di T.

Una formula fr si dice teorema di una teoria proposizionale T se è derivabile nella teoria T. In altre parole,
fr è un teorema di T se è possibile costruire un albero di derivazione, come già descritto, che ha fr come
formula derivabile. I teoremi di una teoria T sono quindi le tautologie di T, ossia formule che risultano
vere nel contesto della teoria. Un’osservazione importante è che tutte le tautologie classiche (ossia, le
formule vere in ogni modello della logica classica) sono automaticamente teoremi di qualsiasi teoria
proposizionale. Questo implica che ogni teoria proposizionale include almeno tutte le verità della logica
classica, indipendentemente dagli assiomi extralogici aggiuntivi.
Per identificare una teoria proposizionale in modo chiaro, si indicano solamente gli assiomi extralogici
specifici di quella teoria. Questo perché le regole logiche classiche e le regole di composizione sono già
implicite nella struttura della teoria proposizionale. In sintesi, una teoria proposizionale è un’estensione
strutturata della logica proposizionale, in cui a partire da alcuni assiomi extralogici e da regole di
composizione possiamo derivare teoremi che riflettono le verità logiche all'interno di un contesto scientifico
o concettuale specifico.

COME DERIVARE? Supponiamo di avere una teoria T composta da alcuni assiomi extralogici:
 Ax1, Ax2,…,Axk.
La regola di composizione può essere applicata in due modi principali per costruire dimostrazioni e nuovi
teoremi:

1. Uso della Regola di Composizione su Assiomi

Se abbiamo una derivazione nella logica classica π in cui un enunciato fr è derivato a partire dagli assiomi
extralogici Axi1, Axi2…, allora possiamo comporre questa derivazione con gli assiomi per ottenere che
fr sia un teorema della teoria T. Ecco il processo:

b. Composizione: Utilizzando la regola di composizione su ogni passaggio, possiamo derivare ⊢fr

a. Premessa: Abbiamo una derivazione π che arriva a fr a partire da Axi1 e Axi2: π Axi1, Axi2⊢ fr

senza premesse, quindi fr diventa teorema in T. Componendo: Axi1⊢fr⇒⊢fr

La derivazione mostra come utilizzare la regola di composizione per trasformare una proposizione derivata a partire
da alcuni assiomi extralogici in un teorema della teoria T, ovvero una proposizione derivabile senza premesse.
Premessa: Abbiamo una derivazione π che conclude con fr, a partire dagli assiomi extralogici Axi1 e Axi2. Abbiamo una
derivazione π che conclude fr utilizzando due assiomi extralogici Ax.i1 e Ax.i2 come premesse. Questa derivazione è indicata
come: π Ax.i1, Ax.i2⊢fr

Questo significa che, assumendo veri gli

assiomi Ax.i1 e Ax.i2, possiamo derivare fr.
Step 1: Derivazione di Ax.i1 e Ax.i2: Ora possiamo
"comporre" questa derivazione con gli assiomi Ax.i1
e Ax.i2 per arrivare a una dimostrazione di fr senza
alcuna premessa (quindi come teorema della teoria
T).
Si inizia affermando che possiamo derivare ciascun

righe: ⊢Ax.i1 e ⊢Ax.i2

assioma separatamente, come enunciato nelle

Qui, ⊢Ax.i1 e ⊢Ax.i2 rappresentano che gli assiomi

extralogici sono veri senza necessità di premesse
aggiuntive.

o Applichiamo la regola di composizione per eliminare Ax.i2 e ottenere ⊢fr

o Usiamo Ax.i1 da sola per ottenere Ax.i1⊢fr.

1. Step 2: Componendo tutte le derivazioni, otteniamo ⊢fr senza premesse, il che implica che fr è diventato un teorema
della teoria T.
Risultato Finale: In breve, grazie alla regola di composizione, possiamo partire da assiomi e ottenere un teorema nella teoria T.

2. Uso della Regola di Composizione su Teoremi Già Noti

Se un teorema T1 è già stato dimostrato in T

tramite una derivazione π1, possiamo usare T1
come premessa per derivare ulteriori teoremi.

a T2, componendo π1 e π2 si ottiene: π1 ⊢T1

Se si ottiene una derivazione π2 che porta da T1

π2 T1⊢T2⇒⊢T2
Questo significa che in T, possiamo costruire
nuove dimostrazioni basate su teoremi già
derivati, consentendo un accumulo di
conoscenza.

In una teoria proposizionale, si possono derivare

nuovi teoremi a partire da teoremi già dimostrati,
grazie alla regola di composizione. Questo
meccanismo permette di accumulare conoscenza:
ogni nuovo teorema può essere usato come base per dimostrarne altri, costruendo così una struttura teorica sempre
più ampia.
Classificazione degli Enunciati in una Teoria Enunciato Derivabile in Opposto Classificazione in
Proposizionale fr τ? ¬fr? τ
In una teoria τ, un enunciato fr può essere classificato fr Sì No Teorema di τ
come:
fr No No Opinione di τ
 Teorema di τ: Se fr è derivabile in τ;
 Opinione di τ: Se né fr né ¬fr sono derivabili in τ; fr No Sì Contraddizione di τ
 Contraddizione di τ: Se ¬fr è derivabile in τ.

Teorema 10.4: Derivabilità dei Sequenti in una Teoria

Il Teorema 10.4 stabilisce che un sequente Γ⊢fr è derivabile in T= LCp+(Axi) se e solo se esiste una lista finita di
assiomi extralogici Ax.i1,Ax.i2,…,[Link] tale che:
Ax.i1, Ax.i2,…,[Link], Γ⊢fr è derivabile in LCp.

Ciò significa che, se possiamo derivare fr aggiungendo alcuni assiomi extralogici a LCp, allora fr è derivabile in T
utilizzando anche la regola di composizione.

Corollario 10.5: Sequente Non Derivabile in T

Il Corollario 10.5 indica che un sequente Γ⊢Δ non è derivabile in T se e solo se, per ogni lista finita di assiomi
extralogici Ax.i1,Ax.i2,…,[Link], il sequente:
Ax.i1, Ax.i2,…,[Link], Γ⊢Δ non è una tautologia in LCp.
In altre parole, per dimostrare che Γ⊢Δ non è derivabile in T, è sufficiente trovare un contromodello in LCp che:
 Rende veri tutti gli assiomi extralogici Ax.i;
 Rende vero Γ;
 Rende falso Δ.

REGOLE VALIDE UTILI A VELOCIZZARE LE DERIVAZIONI

Le regole di indebolimento permettono di aggiungere formule nelle ipotesi o nelle conclusioni di un sequente, senza
cambiare la sua validità. Queste regole sono utili perché consentono di "espandere" una derivazione con informazioni
addizionali che non cambiano il risultato finale, ma possono semplificare i passaggi intermedi. Ecco la forma delle
regole di indebolimento:
1. Indebolimento a sinistra (insx):
Questa regola permette di aggiungere una nuova ipotesi Γ′ al lato sinistro del sequente. In altre
parole, possiamo aggiungere qualsiasi ipotesi extra al contesto Γ senza cambiare la validità del
sequente finale.

2. Indebolimento a destra (indx):

Questa regola permette di aggiungere una nuova conclusione Σ′ al lato destro del sequente.
Analogamente all'indebolimento a sinistra, aggiungere una conclusione extra a Σ non influisce sulla
validità del sequente, in quanto si sta solo ampliando l'insieme di conclusioni.

Perché le regole di indebolimento sono valide

Queste regole sono valide perché aggiungere ulteriori ipotesi o conclusioni non cambia la validità del sequente. Infatti:
 Aggiungere ipotesi a sinistra significa che stiamo ampliando il contesto con ulteriori informazioni che non
contraddicono il sequente originale.
 Aggiungere conclusioni a destra significa che stiamo affermando che se Γ implica Σ, allora sicuramente
implica anche un insieme più ampio che include Σ insieme ad altre conclusioni.

Perché le inverse delle regole di indebolimento non sono valide

L'inverso delle regole di indebolimento sarebbe il seguente:
1. Per l'indebolimento a sinistra: data la derivazione Γ, Γ′, Γ′′⊢Σ, non è possibile in generale concludere che Γ,
Γ′′⊢Σ (cioè, senza Γ′).
2. Per l'indebolimento a destra: data la derivazione Γ⊢Σ, Σ′, Σ′′, non è possibile concludere in generale che
Γ⊢Σ, Σ′′ (cioè, senza Σ′).
Le inverse non sono valide perché:
 Rimuovere ipotesi (a sinistra) potrebbe rendere il sequente non valido: l’ipotesi rimossa potrebbe essere
essenziale per derivare la conclusione.
 Rimuovere conclusioni (a destra) potrebbe anche rendere il sequente non valido: la conclusione rimossa
potrebbe essere un risultato che segue esclusivamente con tutte le ipotesi presenti e non con un
sottoinsieme.
In sintesi, mentre le regole di indebolimento sono valide perché ampliano il contesto senza perdere validità, le loro
inverse non sono valide perché rimuovere ipotesi o conclusioni potrebbe compromettere la derivabilità del sequente
stesso.
In logica proposizionale, una regola derivata è una regola che, anche se non è presente esplicitamente tra
le regole di inferenza del sistema, può essere dimostrata utilizzando esclusivamente le regole già presenti
nel sistema. Le regole derivate sono utili perché permettono di velocizzare le derivazioni, evitando di rifare i
passaggi già noti.

Consideriamo una regola del tipo:

Questa regola si dice derivata nel sistema logico LCp se, supponendo che i sequenti
premessa (Γ′⊢D′) siano derivabili in LCp, si può ottenere una derivazione del
sequente finale (Γ⊢D) basandosi esclusivamente sulle regole di LCp.

Espansione della regola derivata

Quando si applica una regola derivata, è possibile "espanderla" in un pezzo di derivazione usando solo le
regole originali di LCp. In altre parole, anche se abbiamo applicato la regola derivata per derivare Γ⊢D,
possiamo sostituire l’applicazione di questa regola con una derivazione completa che non fa uso della
regola derivata ma che deriva Γ⊢D solo con le regole di LCp. Questo concetto implica che una regola
derivata non aggiunge potere al sistema: essa non permette di dimostrare nuovi teoremi, ma rende solo le
derivazioni più efficienti, evitando di espandere ogni volta i passaggi intermedi. Dire che una regola
derivata è localmente trasformabile in un pezzo di albero di derivazione significa che possiamo sostituire
l’uso della regola derivata con una sequenza di passaggi più dettagliati, rispettando sempre le regole del
sistema logico base. In pratica, una regola derivata è un'abbreviazione di un insieme di passaggi che
possono essere svolti usando le regole del sistema, e può essere "tradotta" in quei passaggi più dettagliati
ogni volta che si desidera espandere la derivazione completa.
Ad esempio, il sequente:
Γ, A, Γ′, ¬ A, Γ′′⊢C
è un assioma derivato perché può essere abbreviato nella seguente derivazione con regole di LCp:
1. Da Γ, A, Γ′, Γ′′⊢A, C si usa la regola di scissione (&) per ottenere Γ, A, Γ′, Γ′′⊢A, C.
2. Si ottiene quindi Γ, A, Γ′, ¬A, Γ′′⊢C tramite la regola di negazione ¬S.
Questo sequente derivato può quindi essere usato in derivazioni più complesse come abbreviazione,
semplificando il processo.

LOGICA PREDICATIVA
La logica classica predicativa (o logica dei predicati) è un'estensione della logica proposizionale, che
permette di esprimere enunciati più complessi grazie all’uso di predicati e quantificatori.

Differenza tra Logica Proposizionale e Logica Predicativa

 Logica proposizionale: lavora con proposizioni semplici, cioè enunciati atomici, collegati tramite
connettivi logici come "e", "o", "non", "se...allora". Esempi di proposizioni sono: "Piove" o "La lampada è
accesa".
 Logica predicativa: introduce i predicati e la possibilità di quantificare variabili. In altre parole, la logica
predicativa può riferirsi a proprietà o relazioni tra oggetti. Ad esempio, "x è un uomo" o "x è mortale"
sono espressioni predicative, dove x è una variabile che può rappresentare qualsiasi individuo.
Linguaggio della Logica Predicativa
Un linguaggio predicativo ha due classi principali di simboli:
1. Termini: rappresentano gli oggetti o individui del dominio di discorso. Possono essere variabili
(come x, y) o costanti (come il nome "Socrate", indicato come s).
2. Predicati: rappresentano proprietà o relazioni tra gli oggetti. Ad esempio, il predicato U(x) può
indicare "x è un uomo", e M(x) "x è mortale".
Costruzione delle Formule
Le formule nel linguaggio predicativo possono essere costruite a partire dai predicati atomici tramite:
 Connettivi proposizionali: come nella logica proposizionale (ad esempio, U(x)∧M(x) significa "x è
un uomo ed è mortale").

o Quantificatore universale (∀): indica che una proprietà vale per tutti gli individui. ∀x M(x) significa
 Quantificatori:

o Quantificatore esistenziale (∃): indica che esiste almeno un individuo per cui la proprietà è vera. ∃x
"tutti sono mortali".

M(x) significa "esiste qualcuno di mortale".

Tipologie di Formule
Le formule possono essere:
 Atomiche: cioè predicati di base, come U(x) o M(s) (dove "s" rappresenta Socrate).
 Composte: ottenute combinando predicati atomici tramite connettivi e quantificatori. Ad esempio, ∀x
(U(x)→M(x)) significa "se x è un uomo, allora è mortale".

Calcolo dei Sequenti e Validità

Nella logica predicativa si cerca di determinare se una formula è valida, cioè vera in ogni interpretazione
possibile. Tuttavia, a differenza della logica proposizionale, non esiste una procedura completamente
automatica per stabilire sempre la validità di una formula predicativa, a causa della complessità introdotta
dai quantificatori e dalle variabili. Tuttavia, esistono procedure semi-automatiche (metodi che funzionano
in molti casi ma non garantiscono una risposta in ogni caso) per determinare la validità.

Componenti di un Linguaggio Predicativo Formale (Definizione Formale)

Un linguaggio predicativo L è costituito da:
 Costanti: simboli per oggetti specifici, come a, b, o una famiglia di costanti indicata genericamente
come (cj)j∈J.
 Predicati atomici: che possono dipendere da un numero finito di variabili (es. A(x1,…,xn) o essere
predicati proposizionali (senza variabili, come B o C).
Questi elementi formano l'alfabeto di L, da cui si generano termini e formule complesse.

La logica predicativa permette di esprimere relazioni e proprietà più articolate rispetto alla logica
proposizionale, ma presenta una maggiore complessità. Studiare la validità delle formule in questo
contesto richiede strumenti avanzati e spesso procedure semi-automatiche, poiché la verifica della validità
non è sempre algoritmicamente decidibile. Nella logica predicativa, i termini sono usati per rappresentare
individui o oggetti, e possono essere variabili o costanti. La grammatica dei termini simbolici nel
linguaggio L stabilisce le regole per costruire questi termini, distinguendo tra variabili, costanti e meta-
variabili.

Costruzione dei Termini

1. Variabili: le variabili rappresentano oggetti generici del dominio di discorso e sono indicate con le
ultime lettere minuscole dell’alfabeto inglese, ovvero w, x, y, z. Per avere una quantità infinita di
variabili, possiamo indicizzarle: x1, x2…,xn, e così via. Questo ci permette di avere un insieme illimitato
di simboli variabili.
2. Costanti: le costanti sono usate per rappresentare oggetti specifici e sono indicate con le prime lettere
minuscole dell’alfabeto italiano, come a, b, c, ecc. Anche le costanti possono essere rese infinite
indicizzandole con numeri, ad esempio a1, a2,…,an,…
3. Meta-variabili: le meta-variabili servono a rappresentare in modo generale i termini nelle regole
logiche. Sono simboli che indicano una categoria di termini e sono usati per esprimere formule
generiche o “schemi” di formule. Ad esempio:
o tter, ster, uter, e vter sono meta-variabili per termini. Possono essere sostituite da variabili o costanti
specifiche, come x, y, a, b, ecc.
o Anche le meta-variabili possono essere rese infinite con indici: t1,t2,…,tn.
Esempio d’Uso
 La frase “a=x” significa che la costante a (un termine specifico) è uguale alla variabile x.
 Una formula come tter=ster∧∀x (x=ster) rappresenta un'espressione generale in cui tter e ster possono
essere sostituiti da variabili o costanti, permettendo di generare diverse formule sostituendo le meta-
variabili con termini concreti.

Per distinguere facilmente tra costanti, variabili e meta-variabili:

 Costanti: usiamo le prime lettere dell’alfabeto italiano, ad esempio a, b, ccc.
 Variabili: utilizziamo le ultime lettere dell’alfabeto inglese (come x, y, z), con l’aggiunta di indici numerici per
creare variabili infinite.
 Meta-variabili: utilizziamo lettere dell’alfabeto italiano diverse dalle costanti (come tter, ecc.) e possiamo
indicizzarle per estenderne il numero.
Questa struttura grammaticale serve a formalizzare frasi in linguaggio comune e a costruire espressioni logiche per
manipolare le formule. Le variabili consentono di esprimere generalità, mentre le costanti rappresentano elementi
specifici, e le meta-variabili forniscono un modo di riferirsi a insiemi di termini in modo astratto.

Nel linguaggio predicativo L, una formula può essere costruita seguendo specifiche regole di formazione.
La grammatica delle formule stabilisce come combinare i predicati, le variabili, i quantificatori, i connettivi
logici e le costanti per formare espressioni logiche valide.
Componenti della Grammatica delle Formule
1. Predicati atomici: Sono formule di base che coinvolgono predicati e termini. Un predicato atomico è
una formula del tipo Pk(ter1,…,term), dove Pk è un predicato con m argomenti (i termini) sostituendo le
variabili di un predicato atomico di base Pk(x1,…,xm) con termini specifici.
2. Quantificatori:

formula del tipo ∀x, dove fr è una formula, è valida se fr lo è.

o Quantificatore universale (∀x fr): Indica che la formula è vera per ogni valore della variabile x. Una

formula è vera. Una formula del tipo ∃x(fr) è valida se fr lo è.

o Quantificatore esistenziale (∃x): Indica che esiste almeno un valore per la variabile x per cui la

3. Costanti:
o "Falso" (⊥): La costante "falso" è una formula che rappresenta un'affermazione sempre falsa.
o "Vero" (tt): La costante "vero" è una formula che rappresenta un'affermazione sempre vera.
4. Connettivi logici:
o Connettivo di congiunzione (&): La formula (fr1)&(fr2) è valida se entrambe lo sono.
o Connettivo di disgiunzione (∨): La formula (fr1)∨(fr2) è valida se almeno una tra fr1 e fr2 lo è.
o Connettivo di implicazione (→): La formula (fr1)→(fr2) è valida se, quando fr1 è vera, anche fr2 è
vera.
o Connettivo di negazione (¬): La formula ¬ è valida se fr è falsa.
IL QUANTIFICATORE UNIVERSALE VA SEMPRE CON L’IMPLICAZIONE
IL QUANTIFICATORE ESISTENZIALE VA SEMPRE CON IL CONNETTIVO DI CONGIUNZIONE

Esempi di Linguaggi e Formule

Linguaggio L: Se un linguaggio L è costituito da una costante s e dai predicati unari U(x) e M(x), le
formule ammesse saranno quelle formate da questi predicati e dalla costante s. Esempi di formule valide in
questo linguaggio:
 U(x)→M(x) (se x è un uomo, allora x è mortale)
 U(s) & M(s) (Socrate è un uomo ed è mortale)
Esempi di formule non valide:
 M(a) (poiché a non è una costante definita nel linguaggio)
 C(x,b) (poiché C non è un predicato nel linguaggio).
Linguaggio Predicativo Minimo: Un linguaggio senza costanti e con solo predicati 0-ari potrebbe essere
L′=(A,B,C), dove i predicati A, B, e C sono 0-ari, cioè non dipendono da variabili. Una formula possibile in
questo linguaggio potrebbe essere: A&B→C.
Linguaggio con Costanti e Predicati Arity 2: Un linguaggio predicativo che contiene la formula
A&B→C(c,y), con costante c e predicato binario C(x,y), sarà rappresentato come L′′=(c,A,B,C(x,y)), dove
C(x,y) è un predicato con due variabili.

Quando si scrivono le formule, la posizione delle parentesi è importante per determinare l'ordine di
applicazione dei connettivi e dei quantificatori. Le regole di precedenza sono:
1. Negazione, Quantificatori universale ed esistenziale: Hanno la precedenza più alta e si legano alla
formula immediatamente successiva.
2. Connettivi di disgiunzione (∨) e congiunzione (&): Si legano con una precedenza inferiore rispetto a
negazione e quantificatori.

¬, ∀, ∃ lega più di ∨, & lega più di →

3. Implicazione (→): Ha la precedenza più bassa.

 "(Tutti gli x tale che A(x)) o B": si scrive ∀x A(x)∨B.

Esempi di Scrittura con Parentesi:

 "Tutti gli x tale che (A(x) o B)": si scrive ∀x(A(x)∨B).

 "(Esiste un x tale che A(x)) implica (B o C)": si scrive ∃xA(x)→B∨C.
 "(Esiste un x tale che (A(x) implica B)), oppure C": si scrive ∃x(A(x)→B)∨C.

A cosa servono i predicati?

I predicati vengono utilizzati per formalizzare asserzioni generali che riguardano insiemi di oggetti e le loro proprietà.
Sono utili per rappresentare affermazioni generiche o universali, ad esempio, descrivendo caratteristiche di oggetti o
relazioni tra di essi. Attraverso l’uso di predicati, variabili, costanti e quantificatori, possiamo esprimere con precisione
concetti complessi e costruire deduzioni logiche.

Consideriamo l’asserzione:
"Tutti gli uomini sono mortali; Socrate è un uomo; quindi, Socrate è mortale."
Per formalizzare questa affermazione, introduciamo:
 Predicati:
M(x): "x è mortale"
U(x): "x è un uomo"
 Costante: s: "Socrate"

uomini sono mortali" come: ∀x(U(x)→M(x))

Utilizzando il quantificatore universale (∀) per esprimere "tutti", possiamo scrivere l'asserzione "Tutti gli

Inoltre, "Socrate è un uomo" e "Socrate è mortale" si formalizzano rispettivamente come U(s) e M(s).

∀x(U(x)→M(x)), U(s)⊢M(s)
L’intera deduzione si scrive quindi come:

dove ⊢ rappresenta la deduzione logica: da "Tutti gli uomini sono mortali" e "Socrate è un uomo",
deduciamo che "Socrate è mortale".

Formalizzazione di Altri Tipi di Asserzioni

"Qualche antenato di Mario è nobile."
o Predicati:
A(x, y): "x è antenato di y"
N(x): "x è nobile"
o Costante: m: "Mario"

∃ x(A(x,m) &N(x))
Usando il quantificatore esistenziale (∃), che rappresenta "esiste", l'asserzione si formalizza come:

1. "Qualche" — si usa il quantificatore esistenziale ∃x, che rappresenta "esiste almeno un x tale che...".
L'affermazione può essere scomposta come segue:

2. "antenato di Mario" — si esprime con il predicato A(x, m), in cui:

o x è la variabile che rappresenta l’antenato, poiché stiamo cercando un antenato generico.
o m è la costante che rappresenta "Mario", la persona specifica di cui cerchiamo un antenato.
3. "è nobile" — si usa il predicato N(x), che descrive la nobiltà di x, cioè dell'antenato generico.
Scrivendo A(x,m) anziché A(m,x) si rispetta l’ordine "x è antenato di y" indicato dalla definizione di A(x,y). Se invertissimo l'ordine
scrivendo A(m,x), significherebbe "Mario è antenato di x" che altera il significato dell'affermazione. Quindi, l’ordine delle variabili

Di conseguenza, la formalizzazione ∃x(A(x,m)∧N(x)) rispetta l'ordine logico e il significato dell’affermazione originaria.

nel predicato riflette il significato corretto dell'affermazione: A(x,m): "x è antenato di Mario," non "Mario è antenato di x."

Le seguenti espressioni logiche equivalgono a "Tutti i P(x) sono Q(x)": ∀x(P(x)→Q(x))

1. Tutti i P(x) sono Q(x)

Questa rappresentazione esprime l’idea che chiunque soddisfi P(x) soddisfa anche Q(x).
Traduce:
 Tutti i P(x) sono Q(x);  Un P(x) è un Q(x)  Se uno è P(x) allora è pure
 Chi è P(x) è pure Q(x)  Chiunque è P(x), è pure Q(x)
 Quelli che sono P(x)... Q(x)  Solo se uno è Q(x) allora è
sono Q(x)  Ogni P(x) è Q(x) pure P(x)
 I P(x) sono Q(x)  Soltanto i Q(x) sono P(x)

Questa affermazione si esprime come: ∃x(P(x)&Q(x))

2. Esiste un P(x) che è Q(x)

Traduzioni alternative includono: "C’è un P(x) che è Q(x)", "Qualche P(x) è Q(x)", "Esistono dei P(x) che
sono Q(x)".
3. Nessun P(x) è un Q(x)
Questa affermazione si esprime come: ¬∃x(P(x)&Q(x))
Traduzioni alternative includono: "Non esiste un P(x) che è Q(x)", "Non esistono P(x) che sono Q(x)".

Ecco alcuni esempi pratici di formalizzazioni logiche:

1. "Esiste un numero x tale che x è minore o uguale a 6."
o Predicati: N(x): "x è un numero"

Formalizzazione: ∃x(N(x)&x≤6)
o Relazione: x≤6: "x è minore o uguale a 6"

Alternativamente, se introduciamo un predicato per il confronto:

o Predicato: M(x,y): "x è minore o uguale a y"

Possiamo anche scriverla come: ∃x(N(x)&M(x,s))

o Costante: s=6

2. "Se Mario non mangia, allora non sta in piedi."

o Predicati:
 M(x): "x mangia"
 P(x): "x sta in piedi"
o Costante:
 m: "Mario"

"Chi non mangia non sta in piedi." Formalizzazione universale, poiché riguarda tutti: ∀x(¬M(x)→¬P(x))
Formalizzazione: ¬M(m)→¬P(m)

3. "Solo quelli che hanno il biglietto salgono sull’aereo."

o Predicati:
 B(x): "x ha il biglietto"

Formalizzazione: ∀x(S(x)→B(x))
 S(x): "x sale sull’ aereo"

4. "Non si dà il caso che nessun programma termini."

o Predicati:
 P(x): "x è programma"
 T(x): "x termina"
Formalizzazione: ¬¬∃x(P(x)&T(x))
4. "Nessun programma con un ciclo infinito termina."
o Predicati:
 P(x): "x è programma"
 T(x): "x termina"
 C(x,y): "y è ciclo di x"
Formalizzazione:
¬∃x((P(x)&∃y C(x,y))&T(x))

La frase "Nessun programma con un ciclo infinito termina" significa che non esiste nessun programma che:

 ha un ciclo infinito (espresso con ∃y C(x,y), dove y rappresenta il ciclo di x),

 è un programma (espresso con P(x),

 e termina (espresso con T(x).

L'ordine di x e y viene scelto in questo modo perché:
 x rappresenta il programma principale di cui stiamo parlando (oggetto di interesse principale).

Vincoliamo prima x e poi y: si cerca prima un programma x (con P(x) e poi si verifica se esiste un ciclo y per x (con ∃y C(x,y)
 y rappresenta il ciclo che appartiene a x. Per ogni programma x, possiamo cercare di trovare un y tale che sia un ciclo di x.

Formalizzazione: ∀x(P(x)&¬∃yC(x,y)→T(x)
5. "Un programma che non ha cicli termina."

Il trucco per tradurre frasi come "soltanto quelli che" o "solo quelli che" segue questi passaggi per ottenere la corretta
formalizzazione logica:
1. Riscrivere la frase senza "soltanto" o "solo" Eliminiamo le parole "soltanto" o "solo" per ottenere una frase più
semplice che esprima la stessa idea senza restrizioni.

forma logica usando una quantificazione universale. Di solito questa frase si esprime come: ∀x(fr1(x)→fr2(x)) che
2. Tradurre la frase ottenuta con quantificatore universale e implicazione Si scrive la frase senza "solo" in

significa "tutti gli x che soddisfano fr1(x) soddisfano anche fr2(x)."

3. Scambiare l'antecedente con il conseguente per riflettere il significato di "solo"

conseguente. Invece di "tutti quelli che sono fr1 sono anche fr2," si ottiene: ∀x(fr2(x)→fr1(x))
Per rappresentare la restrizione implicata da "solo" o "soltanto", scambiamo l’ordine di antecedente e

Questo significa "tutti quelli che sono fr2 devono anche essere fr1," che rappresenta correttamente il significato di
"solo quelli che sono fr1 sono fr2."

Consideriamo la frase: "Solo gli studenti sono ammessi."

2. Tradurre senza la restrizione di "solo": ∀x(Studente(x)→Ammesso(x)) che significa "tutti gli studenti sono ammessi."
1. Riscrivere senza "solo": "Gli studenti sono ammessi."

∀x(Ammesso(x)→Studente(x)) che ora significa "solo quelli ammessi sono studenti" o, in modo più chiaro, "solo gli studenti sono
3. Invertire antecedente e conseguente per riflettere "solo":

ammessi." Questo trucco assicura che "solo" implichi la necessità di appartenere al gruppo Studente(x) per essere Ammesso(x).

11.1.6 Nozione di Variabile Libera in Termini e Formule

Quando si introduce la logica dei quantificatori (universale ed esistenziale) nel linguaggio predicativo, appare la
distinzione tra variabili libere e variabili vincolate:
 Variabile libera: una variabile è libera in una formula se non è sottoposta a un quantificatore (cioè non cade sotto

 Variabile vincolata: una variabile è vincolata se si trova sotto l’influenza di un quantificatore (∀\ o ∃) nella
il "dominio" di un quantificatore). Questo significa che appare senza che sia specificato "per ogni" o "esiste".

formula.

Definiamo prima le variabili libere per i termini, che possono essere o variabili o costanti:
1. Se c è una costante, non ha variabili libere: VL(c)≡∅
2. Se x è una variabile, allora x è una variabile libera: VL(x)≡{x}
Definizione di Variabile Libera in Formule
Definiamo ora la nozione di variabile libera per le formule logiche. La notazione VL(fr) indica l’insieme delle variabili
libere nella formula fr.
 1. Formula falsa (⊥): VL(⊥)≡∅

3. Quantificatori universale ed esistenziale (∀y(fr) e ∃y(fr)):

2. Predicato atomico (Pk(t1,…,tm) termini: VL(Pk(t1,…,tm))≡VL(t1)∪⋯∪VL(tm)

Se fr è una formula con variabile y, allora y è vincolata: VL(∀/ ∃ y(fr))≡VL(fr)∖{y}

Connettivi logici: o Implicazione (fr1→fr2): VL(fr1→fr2)

o Congiunzione (fr1∧fr2): VL(fr1∧fr2) ≡VL(fr1)∪VL(fr2)
≡VL(fr1)∪VL(fr2) o Negazione (¬fr): VL(¬fr) ≡VL(fr)
o Disgiunzione (fr1∨fr2): VL(fr1∨fr2)
≡VL(fr1)∪VL(fr2)
Esempi di Calcolo delle Variabili Libere
1. Formula: VL(A(x)→∀zB(z,y))

o ∀zB (z,y) ha y come variabile libera, perché z è vincolata da ∀z.

o A(x) ha x come variabile libera.

o Quindi: VL(A(x)→∀zB(z,y))={x,y}

o Anche se x è vincolata in ∀xB(x,y), x rimane libera in A(x).

2. Formula: VL(A(x)→∀x B(x,y))

o Quindi: VL(A(x)→∀xB(x,y))={x,y}

o z è libera nel secondo disgiunto A(z,x), poiché il ∀z vincola solo B(z).

3. Formula: VL(∀z B(z)∨A(z,x))

o Quindi: VL(∀z B(z)∨A(z,x))={z,x}

o Qui il quantificatore ∀z vincola tutte le occorrenze di z all’interno delle parentesi.

4. Formula: VL(∀z(B(z)∨A(z,x)))

o Quindi, l’unica variabile libera è x: VL(∀z(B(z)∨A(z,x)))={x}

Osservazione Dire che una variabile w non è libera in una formula fr significa una di due cose:
1. W non compare affatto in fr.
2. w compare ma è vincolata da un quantificatore in fr.