Appunti di Logica e algebra sulla logica proposizionale

• TEOREMA = f è iniettiva sse f ammette inversa dx (cns affinché f ammetta inv dx è che f iniettiva)

• TEOREMA = f è suriettiva sse f ammette inversa sx (cns affinché ammetta inv sx è che f sia suriettiva )

• TEOREMA = se f ammette inversa dx • h e inversa sx• k allora h=K (se funzione ammette inversa sinistra e destra

queste coincidono) (k f) e

h

DIM k (f iB

N h)

- h

iA

: - =

-

=

=

= - = .

.

• TEOREMA = una funzione f ammette inversa sx e dx sse è biunivoca e in tal caso l’inversa è unica e coincide con la

relazione inversa di f funzione)

Equivalenza

FUNZIONI di

RELAZIONI di Concetto

del

(applicazione

e 1

dati A,B insiemi generici, e f:A—>B, L’insieme {f (b)| b∈B} degli insiemi delle controimmagini degli elementi di B è una

-

partizione di A e quindi è l’insieme delle classi di equivalenza di una relazione di equivalenza su A che chiamiamo ker f.

> per ogni a1,a2 A (a1,a2)∈ker f sse f(a1) = f(a2).

∈ d'equivalenza

gEAXA relazione

g A

A insieme su

> proiezione canonica : ,

, [XSg

TIg [g(x)

Atal EA

Ettg : =

proprietà proiezione canonica

- è una funzione ( ad ogni elemento di x corrisponde un’unica immagine, ogni elemento di x sta in una sola

classe di equivalenza

- è suriettiva (ha sempre una contro immagine)

- la relazione ker π (hanno la stessa classe di equivalenza)

f

=

3

> I° teorema di fattorizzazione delle applicazioni :

• Siano f : A→ B una funzione e hker f : A→ A/ker f la proiezione canonica di A su A/ker f.

• Allora esiste un’unica funzione g : A/ker f→ B tale che π g = f.ovvero g rende commutativo il seguente diagramma •

⋅

verf

• Inoltre g è iniettiva : in particolare f è suriettiva se e solo se g è biunivoca

• inoltre g è inietttiv ed è biunivoca sse f è suriettiva

DIM #[XSkegEA/Keng Secondo

del

BEN immagine

POSTA sse

DEFINIZIONE

RICORDA

Kenf)

g([x] f(x) :

= rappresentante

in del

varia scelta

base alla

elemento mon

)

[X [xa]

e t

ben Siano

posta XzEA

dig X1 avora

definizione c

=> :

: =

,

. .

, Kenf Kelf

5) *

g(x f(x) f(xz) g(eSkef rappresentante

immagine

( del

dipende

= scelta

non dava

immagine

, hanno =

stessa

la

tun

= = neg)

g(itkef(x)) g([x] f(x)

g)(x)

FXEA (Tren

late

Inoltre : =

: =

=

=> , - g([xis) g([x2])

Ge f(x) f(x2) (x

quindi

iniettiva +2) Ekey

Inoltre [x2]

Siano Sheng

dim X2EA [X

=> 41

- =

=

: : : kelf

= 1

= =

,

,

di INSIEME

CARDINALITÀ UN

Diciamo che due insiemi A e B hanno la stessa cardinalità e scriviamo |A| = |B| se esiste una corrispondenza biunivoca f :

→

A B

essendo biunivoca, anche l’inversa è biunivoca e allora :

• |A| = |A|,

• se |A| = |B| allora |B| = |A|;

• se |A| = |B| e |B| = |C| allora |A| = |C|.

Diciamo che A ha cardinalità inferiore a B e scriviamo che |A|≤|B| se esiste una applicazione iniettiva da A a B (il che

equivale a dire che A è in corrispondenza biunivoca con un sottoinsieme di B).

Diciamo che A ha cardinalità strettamente inferiore a B e scriviamo |A|<|B| se |A|≤|B| ma |A|≠|B|

(cioè se esiste una funzione iniettiva da A a B ma non esiste una funzione biunivoca da A a B).

Diciamo che l’insieme A è finito ed ha cardinalità n se ha la stessa cardinalità di {1,2,…,n}.

Diciamo che A è infinito se non è finito, ovvero se non ha cardinalità n per alcun n intero positivo—> inoltre è infinito

sse può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio.

Un insieme infinito ha la potenza del numerabile se ha la stessa cardinalità di N, ha la potenza del continuo se ha la

stessa cardinalità di R.

Esistono insiemi con cardinalità superiore alla potenza del continuo? La risposta è data dal seguente teorema che nel

nostro contesto è importante anche per la tecnica dimostrativa che utilizza.

Teorema di Cantor: Ogni insieme A ha cardinalità strettamente inferiore al suo insieme delle parti P (A).

IPCA)

LAKIPCADI LAIPCA) 1/A

= +

Dim.

Esiste ovviamente un’applicazione iniettiva da A a P (A): basta considerare l’applicazione h che manda ogni a∈A

nell’insieme {a}∈ P (A). →

Supponiamo per assurdo che esista una applicazione biunivoca g : A P(A) e consideriamo l’insieme B = {a∈A| a∉g(a)}.>

Poiché B∈ P (A), B ammette una controimmagine ã∈A cioè g(ã) = B.

Supponiamo ora che ã∈B. Allora, per come è definito B, si ha che ã∉g(ã) = B che è assurdo in quanto stavamo

supponendo che ã∈B. Segue che ã∉B con B = g(ã). Allora si ha che ã∉g(ã) e quindi, per come è definito B, segue che ã∈B

che è assurdo in quanto stavamo supponendo che ã∉B. Abbiamo quindi un assurdo che dipende dall’ipotesi di esistenza di

g. Il teorema sostanzialmente afferma che c’è una sequenza infinita di infiniti.

COMPOSIZIONE

LEGGI di

Dati gli insiemi A1, A2,…, An, A, una funzione ω : A1×A2×…×An→A si dice legge di composizione

n-aria (o di arità n) di A1, A2,…, An a valori in A. Per ogni (a1,a2,…,an)∈ A1×A2×…×An l’elemento a = ω (a1,a2,…,an)

(che esiste ed è unico) è detto il risultato della composizione ω della n-upla (a1,a2,…,an).

Se A1 = A2 = … = An = A, diremo che ω è una legge di composizione (o operazione) interna n-aria (o di arità n) su A.

Siamo interessati soprattutto alle operazioni interne n-arie con n = 1 (unarie) ed n = 2 (binarie).

Per le operazioni interne binarie su un insieme A useremo la notazione infissa, indicando il risultato della composizione * di

(a,a’) con a * a’.

Se A è un insieme finito i risultati di una operazione binaria interna su A possono essere rappresentati tramite la tavola di

composizione (detta spesso tavola di moltiplicazione)illustrata di seguito con un esempio (generalizzazione ovvia della

tavola pitagorica)

composizione

tavola di : PROPOSIZIONALE

LOGICA

Una proposizione può essere:

• atomica —> (oggi piove: sono quelle base)

• composta: cioè costruita a partire da proposizioni atomiche usando connettivi (oggi piove allora uso ombrello)

I connettivi che consideriamo sono:

~ (not), (and), (or), (implica), (se e solo se).

∧ ∨

Per indicare l'ordine in cui i connettivi sono applicati si utilizzano parentesi aperte e chiuse.

sintassi

Per costruire le proposizioni usiamo quindi un linguaggio il cui alfabeto è costituito da:

• lettere enunciative: A,B,…,

• connettivi: , , , ,

∼, ∧ ∨

• simboli ausiliari: ( , )

N.B. Spesso si aggiungono alle lettere enunciative altri due simboli e T(true, sempre vere).

⊥