Matematica Discreta Lezione del giorno 19 novembre 2010 Equivalenza logica

Matematica Discreta

Lezione del giorno 19 novembre 2010 Equivalenza logica

Se sono dati due predicati P, Q, nelle stesse variabili, e se PQ ed anche QP, diremo che P, Q sono equivalenti (diremo anche: P se e solo se Q, o ancora: P è condizione necessaria e sufficiente per Q): in tale caso scriveremo PQ.

In questo caso i valori delle variabili che rendono vero P rendono vero anche Q e viceversa, quindi i valori delle variabili che rendono vero P sono esattamente gli stessi che rendono vero Q: possiamo dire che P, Q in pratica rappresentano la stessa affermazione da un punto di vista logico.

Esempio: nell’universo dei numeri interi positivi, i predicati P(x) = “x < 4”

Q(x) = “x

< 12”

sono equivalenti.

Infatti i valori della variabile x che rendono vero P sono x=1,2,3 e sono esattamente gli stessi valori della variabile x che rendono vero Q: si conclude che PQ.

Quindi (nell’universo dei numeri interi positivi) “x < 4” ed “x

< 12” sono la stessa affermazione dal punto di vista logico.

Notiamo che, se modifichiamo l’universo della variabile (pur lasciando invariati i predicati) essi possono anche non essere più equivalenti: per esempio (con P,Q come sopra) se l’universo è quello dei numeri razionali positivi, allora non è più vero che PQ (basta notare che P non implica Q perché per esempio il valore della variabile x=7/2 rende vero P ma falso Q).

Teoria degli insiemi

Studieremo la teoria “ingenua” degli insiemi (in contrapposizione alla cosiddetta teoria

“assiomatica”), in cui il concetto di insieme si considera primitivo, ossia non si definisce, intendendo immediatamente evidente il concetto di insieme come sinonimo di raccolta, collezione di elementi.

Gli elementi di un insieme possono avere natura arbitraria, ed anche natura diversa fra loro:

potremmo per esempio costruire un insieme che ha come elementi il numero 5, la città di Milano e il concetto astratto di bontà.

Se A è un insieme ed x un suo elemento, diremo che x appartiene ad A e scriveremo xA. Se invece x non è elemento dell’insieme A, diremo che x non appartiene ad A e scriveremo xA.

Un insieme può essere descritto in modo esplicito, elencando tutti i suoi elementi.

Per esempio possiamo costruire il seguente insieme di nome A:

A ={3, 5, 7, 9}

contenente i 4 numeri interi elencati fra parentesi.

Un insieme si distinguerà solo per gli elementi che contiene, che si considerano sempre distinti senza ripetizioni, e non per l’ordine in cui sono elencati.

Quindi lo stesso insieme A dell’esempio precedente può essere descritto in modo esplicito anche da A ={5, 9, 7, 3}.

Ovviamente tale modo esplicito di descrivere un insieme è esauriente solo nel caso di insiemi che

contengano un numero finito di elementi.

Oltre che in modo esplicito, un insieme può essere descritto anche in modo implicito, indicando le proprietà che caratterizzano i suoi elementi mediante un predicato.

Se P(x) è un predicato nella variabile x, possiamo costruire l’insieme di nome B:

B = { x / P(x) }

(si legge: “B è l’insieme di tutti gli x tali che P(x)”; il simbolo / può talvolta essere sostituito dal simbolo :); con tale simbologia si intende che gli elementi dell’insieme B sono esattamente tutti i valori della variabile x che rendono vero il predicato P(x).

Per esempio possiamo costruire il seguente insieme di nome B:

B = { x / x è un intero positivo pari }

(si legge: “B è l’insieme di tutti gli x tali che x è un intero positivo pari”).

In tale esempio il predicato che definisce l’insieme B è appunto P(x)=“x è un intero positivo pari” e gli elementi di B sono i valori di x che lo rendono vero (quindi tutti gli interi positivi pari).

Dato un insieme A, ed un elemento x, per verificare se xA:

- se A è definito in modo esplicito, basta verificare che x appaia nell’elenco degli elementi di A - se A è definito in modo implicito mediante un predicato P(x), basta verificare che x renda vero P(x)

Antinomia di Russell

Nella teoria “ingenua” degli insiemi, il fatto che la natura degli elementi sia completamente arbitraria può portare a dei problemi logici, che furono messi in evidenza da Russell.

Partiamo da alcuni esempi: costruiamo l’insieme A i cui elementi sono tutti gli insiemi che contengono più di 2 elementi

A = { x / x è un insieme che contiene più di 3 elementi }

Alcuni esempi di elementi di A sono gli insiemi {1,2,3,4}, {a,b,c,d,e}, {a,1,7,8,b,d}, {1,3,5,7}..

Poiché A stesso contiene più di 3 elementi si ha che A è elemento di sé stesso:

AA.

Invece se costruiamo l’insieme B i cui elementi sono tutti gli insiemi che contengono esattamente 2 elementi:

B = { x / x è un insieme che contiene esattamente 2 elementi } Esempi di elementi di B sono {1},{a}, {2} etc..

Poiché B stesso non contiene esattamente 2 elementi si ha che B non è elemento di sé stesso:

BB.

Abbiamo visto dunque che esistono insiemi che hanno sé stessi come elementi, ed insiemi che non hanno sé stessi come elementi.

Costruiamo allora l’insieme C i cui elementi sono tutti gli insiemi che non hanno sé stessi come elementi

C = { x / x è un insieme ed xx }

(un elemento di C è per esempio l’insieme B costruito sopra).

Domanda: CC oppure CC ?

Ma se CC allora dalla proprietà che caratterizza gli elementi di C segue che CC; viceversa se CC allora dalla dalla proprietà che caratterizza gli elementi di C segue che CC: siamo in presenza di una contraddizione logica (antinomia di Russell), perché un’affermazione è vera e falsa nello stesso tempo.

Per risolvere questi problemi logici legati alla teoria “ingenua” degli insiemi si può ricorrere alla

teoria “assiomatica” (più precisa dal punto di vista formale ma più complicata) oppure evitare

costruzioni del tipo “l’insieme di tutti gli insiemi tali che …….”: nel nostro corso sceglieremo

questa seconda modalità.