Logica e teorie formali

Logica e teorie formali

Antonio Maida

1 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 un 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.

1

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

2

t ) Niente altro è un termine.

3

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.

1

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

2 (nonP) (P Q) (P o Q) (P e Q)

⇒

⇔Q)

(P (om x P) (ex x P)

e ) Niente altro è un enunciato.

3

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.

2. 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=Rx …x di n-ple (n≥1) di individui. Per ogni R, si definisce

1 n

in modo usuale

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

di R.

Se R è una relazione, si scriverà ⇒

b …b a

1 h R

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

se esistono individui distinti ,…,a ,…,b tali che 1 n-1

1 n-1 1 h

Un insieme X dicesi chiuso per una regola R=Rx …x se:

1 n ∈X).

n-1

(Rx …x <x , x ,…, x >∈X )⇒(x

,

1 n 1 2 n−1 n

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

1 h

di individui, nella quale, per ogni i, si abbia uno dei due casi:

∈X

a i ⇒

…a a .

Esiste R∈R tale che: a 1 i-1 R i

Nel primo caso, si dirà che a è una ipotesi, o premessa, o assunzione. Gli elementi terminali delle

i

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=Rx n

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.

3. 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 della 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

i i v

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 Σn Σ

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 .

1 2 n

n

Σn

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

1 h

∧…∧B

B

1 n

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

⎤

i i

i i h

Σn −1)

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

∨…∨C

C

1 k

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 ∧ Σn.

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

i

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

Σn, ∪ ⎬

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

K K⊂⎨ 1 h

Σn.

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

i

Funzioni e tavole di verità.

Ogni funzione W →W

n

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 Fn si indica l’insieme delle funzioni di verità sulle prime n variabili.

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

h

Gli elementi di Fn 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