Logica e teorie formali

Logica e teorie formali

Antonio Maida

La logica non formale

Un linguaggio è un sistema di comunicazione di fatti ed è costituito di un insieme di enti linguistici, i segni, significanti enti extralinguistici. Sono rilevanti i linguaggi verbali i cui segni sono parole, che sono linguaggi naturali (o lingue) e linguaggi artificiali.

L’originalità dei linguaggi verbali consiste nella proposta di considerare le parole come combinazioni di suoni elementari. Per Platone le parole sono nate ad imitazione di suoni naturali, per Aristotele l’origine delle parole è un fatto convenzionale. Le prime forme di scrittura riproducevano schematicamente oggetti e fatti. Il primo alfabeto fu probabilmente usato dai fenici.

Ogni lingua è creativa; la lingua orale è più libera, imprecisa ed adatta alla comunicazione; la lingua scritta è più chiara e precisa.

Lo studio ML di una lingua L ne costituisce il metalinguaggio o la grammatica. La ML si articola poi in morfologia, che studia tramite l’analisi grammaticale la forma e la classificazione delle parole, e sintassi, che analizza tramite l’analisi logica la struttura delle proposizioni e dei periodi. In un dato contesto scritto è spesso facile confondere segni linguistici e segni metalinguistici; ed un stesso segno, dipendentemente dal contesto, può interpretarsi nei due modi. Ad esempio, nei due enunciati Roma è una città e Roma è bisillaba, la parola Roma denota enti diversi. Tali confusioni si evitano evidenziando in qualche modo i termini linguistici menzionati in espressioni metalinguistiche. Le stesse non capitano però se il linguaggio oggetto è una lingua straniera mentre il suo metalinguaggio è la lingua madre. En

Un frammento rilevante di ogni lingua è il discorso enunciativo costituito delle cosiddette proposizioni dichiarative od enunciati, di quelle proposizioni cioè che sono vere o false, ed il cui logica non formale. En

studio è, in definitiva la Opportuni frammenti di sono i linguaggi non formali della matematica. En

L’analisi grammaticale classifica come alfabeto di quello costituito dalle seguenti categorie di segni:

• Nomi propri o costanti individuali
• Aggettivi
• Particelle fondamentali
• Segni ausiliari
• Nomi comuni
• Verbi
• Variabili individuali

Le particelle fondamentali sono le sette configurazioni linguistiche:

“non” “se allora” “o” “e” “se e solo se” “per ogni” “esiste”

indicate spesso coi soliti segni logici. Le variabili individuali (o soggettive) sono gli elementi di

N

⎨ ⎬ ⎨ ⎬

,

= x i∈ e generalizzano il discorso. I segni ausiliari sono gli elementi di = ( ) e

VS SA

/

i

rimpiazzano i segni di punteggiatura. I termini del discorso enunciativo sono definiti dalle clausole:

t₁) Costanti e variabili individuali sono termini.

t₂) Il risultato dell’applicazione di un nome comune a termini è un termine.

t₃) Niente altro è un termine.

Sono ad esempio termini, i nomi propri “Socrate”, “3”, “ ”, la variabile “x”, le espressioni “il

Ø

padre di Mario”, (3+5)(2-x).

L’analisi logica individua come elemento sintattico di base l’enunciato semplice, la cui struttura è predicato+soggetti. I predicati sono verbali, e cioè i verbi, oppure nominali, e cioè le sequenze copula+nome comune, copula+aggettivo. Fungono da soggetti i termini.

En

L’insieme degli enunciati è infine quello definito dalle clausole:

e₁) Gli enunciati semplici sono enunciati.

e₂) Se P e Q sono enunciati ed x è una variabile allora sono enunciati anche

(nonP) (P ⇒ Q) (P o Q) (P e Q)

⇔

(P ⇔Q)

(om x P) (ex x P)

e₃) Niente altro è un enunciato.

In (om x P), P è il campo d’azione di om x. Si conviene di eliminare in un enunciato le coppie di parentesi superflue. Una occorrenza della variabile x nell’enunciato P dicesi occorrenza vincolata se è immediatamente preceduta in P da om x, o se si trova in P nel campo d’azione di un om x; diversamente, essa dicesi occorrenza libera. La x dicesi variabile libera in P se ha occorrenze libere in P, dicesi variabile vincolata in P se ha occorrenze vincolate in P. Un enunciato P dicesi chiuso se non ha variabili libere, aperto altrimenti.

Linguaggi formali ed enti

Il concetto di segno è primitivo ed un alfabeto E è un insieme non vuoto di segni. Nella pratica gli alfabeti saranno riconducibili al finito. Se E⊂E’ allora E’ è una estensione di E.

Una parola di E è una sequenza finita di segni di E; fra le parole di E vi è sempre la parola vuota ∆. Si indica con WE l’insieme delle parole di E.

La giustapposizione di due parole P e Q è la parola (PQ) ottenuta scrivendo di seguito i segni di P e Q. La parola P è sottoparola della parola Q, in simboli P ⊂ Q, se esistono le parole R ed S tali che Q=((RP)S).

Si hanno le: ∆P=P∆=P ∆

⊂ ⊂ ⊂ ⇒ ⊂ ⊂ ⊂ ⇔

P P Q R P R P R P P=R.

(PQ)R=P(QR)

I concetti di occorrenza di un segno s nella parola P e di lunghezza lP di P sono ovvi. Una produzione di E è una coppia <P,Q> di parole di E. Un linguaggio artificiale è una coppia <E,L> essendo L ⊂ WE. Particolari linguaggi artificiali saranno i linguaggi formali della matematica.

Gli enti matematici sono classificabili in individui, relazioni fra individui e funzioni di individui in individui. Sono individui le entità singole, e cioè i punti, i numeri, gli insiemi, i segni, ecc.

Sono relazioni o regole gli insiemi R=R₁× … ×Rₙ di n-ple (n≥1) di individui. Per ogni R, si definisce in modo usuale

domR codR univocità (o funzionalità) di R biunivocità (o ingettività) di R.

Se R è una relazione, si scriverà ⇒

b₁ …bₕ a₁

{a₁}⊂{b₁} Ra₁ …aₙ.

se esistono individui distinti a₁,…,aₙ₋₁,…,b₁,…,bₕ tali che

1 n-1 1 h

Un insieme X dicesi chiuso per una regola R=R₁× … ×Rₙ se:

n-1

(R₁× …×Rₙ<x₁, x₂,…, xₙ>∈Xₙ)⇒(xₙ∈X).

L’insieme X dicesi chiuso per un insieme R di regole se esso è chiuso per ogni R∈R.

Una derivazione da X ed R è una sequenza a₁, …, aₕ di individui, nella quale, per ogni i, si abbia uno dei due casi:

aᵢ∈X

⇒

…aᵢ₋₁aᵢ.

Esiste R∈R tale che: a₁ … aᵢ₋₁ R aᵢ

Nel primo caso, si dirà che aᵢ è una ipotesi, o premessa, o assunzione. Gli elementi terminali delle derivazioni diconsi derivabili da X ed R.

La chiusura di X per R è l’insieme

X =⎨x x è derivabile da X ed R⎬.

R

Si hanno le seguenti proprietà della chiusura:

/ ⊂Y

⊂

X =min⎨H/X H H è chiuso per R⎬ X⊂Y⇒X .

R R R

…x y, dette funzioni, si indicano con lettere f, g, h, ecc. Si scriverà

Le relazioni univoche R=R₁× … ×Rₙ

1

y=fx₁ …xₙ al posto di fx₁ …xₙ y.

n n

1 1 ⊂

Se X è un insieme, si dice che f è una funzione parziale in X se domf⊂X; se in particolare domf=X si dirà allora che f è una funzione totale in X.

Se X ed Y sono insiemi, si dirà che f è una funzione di X in Y, e si scriverà f:X→Y, se domf=X e codf ⊂Y.

Se f:X→Y e codf=Y, allora la f:X→Y dicesi surgettiva. Se f:X→Y è surgettiva ed ingettiva allora essa dicesi bigettiva. Se esiste una bigezione f:X→Y allora X ed Y diconsi equipotenti.

Schemi, diagrammi di Venn e tavole di verità

CL=⎨→ ∀⎬,

I segni di detti segni logici o costanti logiche, sono rispettivamente il connettivo della negazione, il connettivo dell’implicazione ed il quantificatore universale.

SA∪VS∪CL

Se E, essendo E un alfabeto, per P,Q∈WE ed x∈VS, le parole

∀x

→ → → →

P Q (P Q) P (P Q)∧(Q P)

⎤ ⎤ ⎤ ⎤ ⎤

si indicheranno con ∃xP ⇔ Q.

P∨Q P∧Q P ∀xP,

Si è convenuto di eliminare le coppie di parentesi superflue; ad esempio, quelle esterne. In P è

∀x. ∨, ∧, ∃

⇔

il campo d’azione di I nuovi segni logici ed sono rispettivamente il connettivo della disgiunzione, il connettivo della congiunzione, il connettivo della equivalenza ed il quantificatore esistenziale.

Si definiscono le seguenti quattro regole, essendo P,Q∈WE ed x∈VS:

→ →

R =⎨<P, P>⎬ R =⎨<P,Q,P Q>⎬ Mp=⎨<P,P Q,Q>⎬ Gen=⎨<P,∀xP>⎬.

⎤

⎤ →

Le Mp, Gen sono il modus-ponens e la generalizzazione. Le regole di

RF=⎨R , R , Gen⎬ RD=⎨Mp, Gen⎬

⎤ →

Sono rispettivamente le regole di formazione, e le regole di deduzione o di inferenza o di dimostrazione. N N

W=⎨1,0⎬ ⎨ ⎬ ⎨ ⎬

v A

Con si indica l’insieme dei due valori di verità. I segni di /i∈ e /i∈ sono le variabili per valori di verità e le lettere enunciative. Con u, v e w si indicheranno le prime e con

i

A.

A, B e C le prime i

Gli schemi

N

⎨ ⎬ Σ

A

Gli elementi della chiusura /i∈ sono gli schemi. Si indica con l’insieme degli schemi

RF

i Σⁿ Σ

privi di occorrenze di quantificatori (schemi elementari) e con l’insieme degli elementi di nei quali occorrono esattamente le n lettere enunciative A₁, A₂,…, Aₙ.

n

Σⁿ

Sono forme congiuntive di gli h=2 schemi S₁,…,Sₕ del tipo

B₁ ∧…∧Bₙ

essendo per ogni i, Bᵢ=Aᵢ oppure Bᵢ= Aᵢ.

⎤

i i h

Σⁿ −1)

Sono forme canoniche (fc) di i (2 schemi del tipo

C₁∨…∨Cₖ

essendo ogni C una forma congiuntiva e 1≤k≤h. Per k=1 si hanno le forme congiuntive e per k=h

i ∨…∨S ∧…∧A ∧ Σⁿ.

si ha la forma canonica 1=S . Posto 0=A A , l’insieme fc∪⎨0⎬ è la base di

⎤

1 h 1 n 1

Diagrammi di Venn

N

Per ogni n∈ è sempre possibile disegnare, dentro un rettangolo 1, n linee chiuse Aᵢ tali che

n

⎨ ⎬ V

l’insieme S₁,…,Sₕ delle h=2 superfici individuate costituisca una partizione di 1. Tale figura n

1 h

è il diagramma di Venn relativo ad n. Le h superfici rappresentano gli schemi in forma

h

Σⁿ, ∪ ⎬

congiuntiva di mentre le 2 unioni al variare di S₁,…,Sₕ rappresentano gli schemi della

K K⊂⎨

Σⁿ.

base di In particolare 1=∪S mentre 0=∪Ø è il rettangolo vuoto.

i

Funzioni e tavole di verità

Ogni funzione Wⁿ→W

y=fv₁…vₙ:

1 n n

è una funzione di verità. Rappresentando le (n+1)-ple di f su righe si ottiene una matrice (2ⁿ,n+1)

W W

su che è la tavola di verità di f. Viceversa ogni tavola di verità su individua univocamente una funzione di verità. Si parla perciò indifferentemente di funzione o tavola di verità, se ne indica con F il relativo insieme, e con Fⁿ si indica l’insieme delle funzioni di verità sulle prime n variabili.

Se è sempre fᵢ=1 allora la f è una tautologia; se è sempre fᵢ=0 allora la f è una contraddizione.

h

Gli elementi di Fⁿ sono 2 e fra essi vi è una sola tautologia 1 ed una sola contraddizione 0. Infine, l’ultima colonna di una tavola ne è la colonna principale.

Sono particolari le cinque funzioni di verità seguenti con le rispettive tavole:

1→0=0 0∨0=0 1∧1=1

u≠u u⇔u=1