Metodi Matematici per L'informatica (Logica Matematica) prof. Pietro Cenciarelli

L’esperimento sta nel dividere il segmento in tre parti scartando la parte centrale ed

iterare questo ragionamento all’infinito, in modo da ottenere segmenti sempre più

piccoli scartando sempre più parti.

Ottengo così una sequenza di insiemi incapsulati, in quanto ognuno è contenuto

nell’insieme precedente.

Prendendo l’intersezione di tutti questi insiemi ottengo un insieme C (polvere di

cantor) . Questo C è un insieme per forza non vuoto, in quanto anche se i segmenti

vengono diminuiti per ogni iterazione non vengono mai eliminati del tutto.

3

In particolare nell’insieme vi sono gli estremi dei segmenti, in quanto questi

rimangono sempre.

Supponendo che l’insieme di partenza “pesi” 1kg, ad ogni passaggio togliamo

2

3

¿

¿ kg.

¿

∞

1 ∑ ¿

3 k=0

Il limite per k che tende a infinito da 1. Quindi per iterazioni che tendono all’infinito il

peso della polvere di cantor tende a 0.

Quindi la polvere di cantor non pesa nulla nonostante ci siano degli elementi.

Oltre agli estremi, sono presenti altri elementi in C che si ottengono scendendo a

“zig-zag” tra i vari segmenti nelle iterazioni

Prendendo un numero qualsiasi e lo rappresento in binario (0,75 = 0,110000…) e

considerando questi 0 ed 1 come un’istruzione per scendere tra le varie iterazioni a

destra o a sinistra, posso associare ogni numeri di [0, 1] ad un numero di C. Essendo

ogni combinazione di 0 ed 1 differente, i due insiemi sono in corrispondenza iniettiva.

In particolare [0,1] è in corrispondenza iniettiva con C, quindi la sua cardinalità è

minore. Ma C è un sottoinsieme di [0,1], quindi la sua cardinalità è minore. Secondo il

teorema di cantor quindi i due insiemi sono equipotenti.

4

Funzioni

Una funzione f: D C è una relazione tra gli elementi di due insiemi D e C tali che ad



ogni elemento dell’insieme D corrisponde uno ed un solo elemento di C.

Una funzione ha:

Dominio: ovvero l’insieme in cui la funzione è definita

 Codominio: ovvero tutti i possibili valori che la funzione può assumere

 Immagine: ovvero l’insieme dei valori assunti dalla funzione sul proprio

 dominio

Controimmagine: ovvero l’insieme degli elementi del dominio che vengono

 mandati nel codominio dalla funzione

Una funzione può avere delle proprietà:

Iniettiva: quando elementi distinti del dominio hanno immagini distinte.

 Suriettiva: quando ogni elemento del codominio è immagine di almeno un

 elemento del dominio. In questo caso l’immagine e il codominio coincidono.

Biiettiva (o biunivoca): quando la funzione è sia iniettiva sia suriettiva.



Una funzione è invertibile se e solo se è biiettiva.

Funzioni non calcolabili

Una funzione si dice calcolabile se esiste un procedimento effettivo per calcolarla.

Church disse che tutto ciò che possiamo calcolare lo possiamo calcolare tramite una

macchina di Turing, ovvero un calcolatore che segue delle istruzioni e ha degli stati

interni. (Tesi di Church).

Le macchine di Turing costruibili (ovvero le funzioni calcolabili) sono ω, mentre le

funzioni in generale da una macchina di Turing hanno la potenza del continuo, quindi

ω .

2

Questo vuol dire che ci sono moltissime funzioni perfettamente definite ma che non

possono essere calcolate.

L’insieme dei naturali

L’insieme dei numeri naturali è legata all’antico procedimento del contare.

I numeri naturali vennero trattati come termini di un linguaggio e non come uno stato

metafisico solamente nel medioevo, così si cercò di porre degli assiomi.

Il primo a formulare veri assiomi matematici per l’insieme dei numeri naturali fu

Giuseppe Peano. Egli indicò dei concetti primitivi, ovvero lo zero, il numero ed il

successivo, definendo poi 5 assiomi:

Assioma Zero: I numeri formano una classe o insieme

 Lo zero è un numero

 Se a è un numero, il suo successivo è un numero

 Se S è una classe contenente lo zero ed a appartiene ad S e succ(a) appartiene

 ad S allora ogni numero naturale appartiene ad S (principio di induzione)

Se a e b sono due numeri e i loro successivi sono uguali, allora a e b sono uguali

 Se a è un numero, allora il suo successivo non è zero

 5

Principio di induzione

Il principio di induzione, ovvero il terzo assioma di Peano, è un metodo molto potente

per ragionare su successioni infinite tramite un metodo finito. Esso afferma che se una

proprietà P vale per un caso base e vale per il suo successivo, allora vale in ogni caso.

Algebre

Reticolo

Un reticolo è una particolare struttura algebrica, ovvero un insieme dotato di

operazioni che soddisfano alcune proprietà (commutativa, associativa, distributiva

ecc…)

Un reticolo è un insieme parzialmente ordinato S che presenta un estremo inferiore

ed un estremo superiore. Dove il sup tra due elementi è più grande di A, più grande di

B, ma è il più piccolo tra tutti gli elementi più grandi di A.

Un semireticolo è invece un insieme dotato di una relazione d’ordine (e quindi

parzialmente ordinato) che presenta un estremo superiore (o estremo inferiore).

Oppure un insieme dotato di proprietà come l’idempotenza, commutatività ed

associatività. L’unione dei due semireticoli rispetto al Meet e al Join crea un reticolo

(algebra di Boole).

Esso è inoltre dotato di due operazioni (Join e Meet / Or e And) che soddisfano le

proprietà associativa, commutativa e di idempotenza.

Sia A un insieme, il suo insieme delle parti P(A) ordinato per contenenza è un reticolo.

Infatti dati B e C appartenenti a P(A) il sup sarà l’unione tra i due insiemi men tre l’inf

sarà la loro intersezione.

In un reticolo le funzioni (a,b) sup(a,b) ed (a,b) sono due operazioni,

 inf(a,b)

rispettivamente il join ed il meet. (Che corrispondono quindi all’unione e

all’intersezione).

Il complemento di a è un elemento b tale che a and b = Bottom, a or b = Top

Un reticolo è detto limitato se ammette massimo e minimo

Un reticolo è detto distributivo se gode della proprietà distributiva (sia sull’and che

sull’or)

Gli insiemi delle parti sono sempre reticoli distributivi.

I reticoli distributivi ammettono solamente un complemento, cosa che non è vera

per i reticoli non distributivi. Esistono però reticoli non distributivi con un solo

complemento, ma non se ne conosce un esempio.

Algebra di Boole

L’algebra di Boole è un particolare reticolo limitato e distributivo, ovvero che gode

della proprietà distributiva, che è limitato da un minimo e massimo e che

aggiunge alla nozione di reticolo l’operatore unario di complemento (che è unico).

L’insieme potenza di un insieme è un’algebra di Boole.

6

Le cui variabili in un’algebra di Boole possono assumere solamente i valori Vero o

Falso, che saranno rispettivamente il massimo ed il minimo del insieme.

Le proprietà di un’algebra di Boole sono le seguenti, dove il + è l’or logico ed il * l’and

logico. a+b = b+a a*b = b*a

 Commutativa:

a+(b+c)=(a+b)+c a*(b*c)=(a*b)*c

Associativa:

 a+(a*b)=a a*(a+b)=a

Assorbimento:

 a+a=a a*a=a

Idempotenza:

 a*(b+c)=(a*b)+(a*c) a+(b*c)=(a+b)*(a+c)

 Distributiva:

a Join Bottom = a a Meet Top = a

Identità:

 a Join b =Top a Meet b =Bottom

Esistenza del complemento:



Una qualunque funzione f da A in B che rispetta tutte e tre le operazioni dell’algebra

si chiama omomorfismo.

Non esistono algebre di Boole astratte in quanto (teorema di rappresentazione

delle algebre di Boole) ogni algebra di Boole è isomorfa ad un’algebra di insiemi.

Questo vuol dire che ciò che abbiamo chiamato algebre di Boole catturano

esattamente il comportamento dell’algebra degli insiemi. E’ vero anche il viceversa.

Gli elementi che costituiscono l’algebra dei sottoinsiemi che rappresenta l’algebra di

Boole sono tutti gli omomorfismi dell’algebra di Boole nell’algebra 2, ovvero l’algebra

di Boole costituita dai soli elementi Top e Bottom.

In un reticolo distributivo se due elementi b e c si comportano esattamente nello

stesso modo con il join ed il meet rispetto ad a, allora questi due elementi sono uguali.

Algebra di Heyting

Un’algebra di Heyting è un reticolo distributivo con minimo e massimo elemento tale

che l’implicazione sia definita per ogni coppia di elementi. Da questo si deduce che se

un reticolo possiede un’operazione di implicazione, esso è distributivo.

Relazione tra algebra di Boole e algebra di Heyting

L’implicazione può essere scritta in termini di complemento e connettivi per l’algebra

di Boole, infatti: AB = not(B) or B.

Nelle algebre di Heyting non esiste un connettivo di negazione logica, vi è però

un’approssimazione, infatti ¬A ≡ A → ⊥.

Ogni algebra di Boole è un’algebra di Heyting ma non vale il viceversa, in quanto

possono esistere elementi dell’algebra di Heyting che non presentano il complemento.

Esistono inoltre algebre di Heyting in cui non è vero che la doppia negazione di una

proposizione è equivalente alla proposizione stessa.

L’implicazione è una proposizione puramente intuizionista mentre la negazione è una

proposizione puramente classica. L’implicazione, nella logica classica, viene chiamata

“conseguenza semantica”, indicata con il doppio tornello. E significa che, se il modello

m soddisfa A, allora soddisfa anche B.

Nella logica intuizionista non esiste la negazione in quanto non può essere mai

certificata la falsità di una proposizione. 7

Logica classica vs Logica intuizionista

Per un classico una proposizione è vera quando corrisponde ad uno stato della

realtà.

Per un intuizionista una proposizione diventa vera solamente nel momento in cui ne

possiedo una prova. Nella logica intuizionista quindi possiamo esprimere il fato che

una proposizione sia vera, ma non c’è modo per esprimere che una proposizione sia

falsa.

Logica proposizionale

In logica viene definita sintassi l’insieme delle espressioni ben formate. Viene definita

semantica l’interpretazione M che viene data ad un linguaggio.

Alfabeto

L’alfabeto della logica proposizionale è formato da:

Insieme d simboli proposizionali: p, q, r…

 I simboli dei connettivi logici

 Le par