Appunti Algebra e Logica

Logica

e

Algebra Lez. 1 - 01/03/2021

Generalità sugli insiemi raccolta =

Jef " "

" "

è

insieme di

collezione oggetti

una

un

: o

} }

{ {

Notazione ha proprietà

P a

P

1.2.3 oppure ne

= se

:

: : =

.

.

. . . .

-

elementi P

ai

insieme A a

'

a

A ;

' € s

; =

c- a

a a

a t

T

T t

appartiene

appartiene contiene

Non

non

contiene

Paradosso Russell

di : }

{ è E

2- t.ci

insieme

:-. . * 2-

Se 2-

2- 2-

¢

vale

non

E >

*

= > =

>

è

Se 2- insieme

• davvero allora

un >

=

, ' se 2- 2-

2-

2-

E vale > e

>

= =

*

"

Jef famiglia

Si " in indicizzato

dice indici

di

insieme

insieme

oggetti a

di dato da un

un

: ,

{ }

raccolta

" ti

ai

I A I

del tipo dove ai

una c- c-

; e =

, , , .

Inclusione tra insiemi "

f è '

A. Si

Def insiemi sottoinsieme

olice a di

B B

che O

: : è "

fa B

A "

EB a sourainsie

( a

di

> > B)

=

⇐ E

o

e me

.

Il

è

a in

contenuto B

a)

B contiene

N.BA è

E a

B Se incluso B

in

non B)

¢ a

B) Ito

c-

NON la

a >

B < ⇐ > Non >

e E c-

=

= a

. I

A

ao E B

¢

> Q

- = o

Note : "

"

e

ti ) al

1 a. insiemi a

a EB

B B B C

>

si ha < =

=

:

"

" esiste unico

un { }

=

2) indicato

"

insieme insieme

speciale anche

detto

- vuoto ;

o

con ,

,

.

. ha E

elemento insieme

E o

nessun ;

non c- { }

" I

l'

Def tl =

E

insieme F

PIE FE

insieme delle

si )

dice insieme

parti E

: : =

, ,

Esempi :

0

(1) PIE

PLE E E

)

E )

; }

}

{

E 0 0 il

PCE elementi

)

= >

(2) numero

= di

=

{ } { }

{ } è

0

e pie parti

insiemi

degli delle

e > ) e

= = una

= , }

{ } }

{ } {

{

{

} e

la

E la

PIE potenza 2

> e

e la ) di

= = = .

, , .

. .

,

. intersezione

a

ti

Operazioni tra insiemi

insiemi a. n

B

: B

}

{

A B)

(

intersezione B.

n A)

• ire

= le e e

se

^

: A B

" unione

" oppure = #

}

{

A B)

(y

(

4

unione a)

v13

• e ✓

y e

: =

: A B

{ }

A B)

(

differenza A)

( differenza

B ¢

2- 2-

n

2-

° E

: =

: ←

e

CE

complementare E

Ela

(A)

• =

: A

E)

di a in /

)

A

a

Differenza B

B A

B

simmetrica

• stesso

+ u

=

:

: .

cosa !

(

A ) ( an

B a ,

v13

: =

cioè

V-A.BE

Nota E

C-

A

PCE B

) se

: ,

BE

a

an B a

a UB PIE

④

113 )

;

; , { }

" b)

l'

"

Def ti B

insieme

a. aea.be

B

cartesiano

prodotto

B. insiemi dice

si : a.

✗ =

: -

più

definire

si

B insiemi

N n di

U per

✗ possono Owe

:

. , ,

Esempi : { }

be

Bxc Iaea

( CEC

A c) B

b.

• =

:

✗ a. .

, }

:{ NIKE

a) (

An )

Bnc B) C

° ^

ke

: see

se A disgiunti

:

"

"

Def A. an B

si disgiunti

B dicono

insiemi

Due se : =

: B

Proprietà in PIE

delle operazioni ) :

④

1) n Sono

U commutativa ovvero :

, ,

,

fa B insiemi :

,

a

• Bna

nb = { { }

}

a yllyeb

)

v13

• A (y

Bua a)

(

B)

lye

a)

v13 =

y c- c-

= ✓ y

>

a 13=13

④ B)

a a

a

⑦ Bla

④

• D= )

> u (

Bla a

13 ⑦ )

> a B

u

=

2) n U ⑦ Sono associative :

,

.

la

• B) (

nc a Bn C)

=

n n

( (

a a

B) C)

• UC Bu

U = u

la B) ⑦ C

⑦ a ⑦ (

° ⑦ C)

B

=

3) a EPIE

elementi insieme

t.co

speciali )

.

è

A E

a elemento

E Era PIE )

neutro in

= n

= per

• n

a a va

• =

=

u 0--0=0

a

• sa

n 0

a ④ a

a

• ④ =

=

E

A Eva

° E = =

u Y insiemi

Proprietà a.

4) B.

distributiva C :

:

- (

( )

a (

B a C)

C )

B

a

n =

U u

n n

(B (

• C) (

ma Bsa ) Cna )

=

v u

(

a

' )

( (

a

Bs B

C) aw

= c )

U

u n

Ibn

e va ( (

C) Bua ) A)

C

= U

n Ma

' viceversa

a ④ la

IB il

C)

④ C)

B)

( an non

=

n n

Formule

5) Morgan

De

di :

a (

113

- B) (

al a

C) C)

\

=

u n

(

a al

( al

B) (

' 1 B C)

C) = u

n ti 2-

In 4 2-

particolare 4. × C-

× con

: ,

.

)

Cz ( Cz

v4 (Y)

)

(

(

✗ ×

= n

z

( 4)

Cz ( )

)

( ( Y

(

✗ n X u

2-

= 2- 04/03/2021

-

02

Lez.

Corrispondenze "

ti '

Def A. B qualunque

insiemi corrispondenza

dice Axb

B

si sottoinsieme

A

da di

un ;

: a

cioè P A

E B

✗

graficamente :

' b)

Q

Q ,

, b ,

> P

② 2 ba a

- B

>

-

-

- -

Q3 b

> }

ÉÌ l

P

Con fb

13

b) E

la < >

⇐ a

ai >

.

¥ f P

Def f a B si

a e

corrispondenza dice

B

: > :

✗

-

-

- ,

Dominio a

f

a) di : = B

b) f

Codominio di : = { }

' '

fa ' b '

Joie

ca immagine la

a =p

A p :(

B l

à e

b

c- :

per

di c-

ci : =

, ,

{ }

ti ' '

)

'

' '

' f-

' il

d) A b 113

B E )

il B b

B immagine

contro B

di per e :

:-. =

e

c-

a a.

- :

,

Esempio : }

{

'

' a as.ae

a

=

b

° . ,

.

' , }

q {

9

, b

la

' bc

bs

' )

ba = }

> ,

,

,

Q :b

} ac }

, b

> 4 {

' }

B bi

b

be

QS i

b = }

> ,

, ,

, }

{

'

f- ora

. (a) @

= a

,

Classi speciali il

Def a

corrispondenza B si

una dice

> :

: _

R a

relazione in B

a se

: = to

funzione be

A 9

B

B

F ao b

se

a :

E

:

: - E

a.

. . .

.

Esempi :

ti B)

a. PIA

0

1 A

insiemi B

B E

- ✗ ✗

,

, totale B

a

: = ✗

>

7 corrispondenza

>

= ' vuota 0

: =

insieme a relazione identica

corrispondenza stesso

2) data

di se

a in da :

÷

- ,

}

{ { "

} ' "

" a a

a ' '

Ida e

=

: a

a. a

e

= a

a =

a a ✗ .

, , a y

a #

= .

" "

Ida diagonale

si dice

I ) .

i

" "

insieme

lt la relazione inclusione

3) corrispondenza

E :

-

, ,

I

C- A

P

P (E) (E) IR

: > =

-

-

- .

{ }

" '

E "

' PLE

E PCE E

) E

E )

Oleata E c-

oca :-. x

,

Costruzioni sulle corrispondenze

'

1) "

Costruzioni insiemi sti che : U Capo

tra

corrispondenze n

tra a B possiamo operare •

con

e : + ,

, . .

f

Inversione f PIA

2) a P

B B)

E

-

: -

-

-

: ✗

' '

f- '

"

f- a)

A PIB

B detto corrispondenza inversa

e

>

- - ✗

-

-

: , .

. }

{ b)

"

l b a)

( B e

A

E c-

a.

✗

: = , '

P f-

NOTA corrispondenza corrispondenza

: '

funzione

9 f- funzione

# uguali

Ti

t

Composizione a O

t

3) :B

corrispondenze B

di c

: -

: - -

-

- -

-

- ,

! 0 te a

0 C

Corrispondenza Gta

I

= da

>

o * -

: -

- -

- ,

{ c)

60 la b.

b)

3- O

Te b

a t c-

B

io E C

C) E

:

E

: = n

×

. . ,

'

ti A'

l' ha

a

B A

N E immagine si

per di

: :

. , { }

) C

' )

) '

' A

O T

IO

0oz a

a '

= te =

C)

io

e

c E

a e : o

- . .

Proprietà composizione

notevoli della :

t

è

la

1) a B

0

composizione C D

t B

associativa C

U -

:

> -

: :

-

: -

-

- -

- , ,

)

(

IO )

I I

U 0

U = o

o o

o ) T

U 0 o

°

V00

g

T Y id

b- C

a - -

- -

> - -

- - -

-

- - - 7 7

0 T

o U 0 I

o ☐

Elementi

2) neutri

À il :

È ha dis

P

f 9

Id

si p I

> =

: =

a

-

_

- .

: .

,

.

.

. . . idb

Ida analogo

N B 1

×

o =

✗ ×

: ×

=

a : ;

+ .

- cioè

l' è 0oz

3) Non T

=/

generale

composizione 0

commutativa

in

di

operazione o

,

I

Può ] io

che )

contrario

il

anche essere zo (

Te o

ma o

t

Inversione Got

7 a

a o

4) C

B

t :B c

-

:

>

-

-

: : = -

-

-

-

-

- -

- ,

' '

' - g-

:(

Si I

_

ha )

o o

z =

o 08/03/2021

-

03

Lez. "

fp

funzione cioè

NOTA 9 A B )

PLB

corrispondenza le stesse

contiene

una

- : >

>

: -

-

-

: -

,

'

-

informazioni e

di { }

fpia li

' tratto

PLB '

=p )

a c- b

a

) : >

}

{

' =p "

Q

i ' b come

a a un

> > " '

b

> elemento

solo

" f

f famiglia

Def =

insieme funzione E

- E indicizzato

dice

si di in ogni

oggetti I :

da >

: - .

. { } ti

fii

Si famiglia )

la lei

descrive Con

> li

anche I

ie c-

: =

:

I

Esempio :

{ È È

È }

ès { }

{ }

E

f E

funzione I

alla *

corrispondono I 1.2 3,4 0

con ×

:

- =

:-.

: , ,

.

.

, . , ,

I E

>

1 :*

2 { }

° 1mL

: f) * o

= ,

3 ✗

4

Funzioni speciali

funzione f.

Def a dice

si

B

una > :

: " { } " "

fa '

f ' '

fia fica

fb "

Iniettiva ha b

1) B 1

si =/ ) )

a a

e =/

@ >

: =

, .

' { } {

f- }

fb In (f)

1

ha b fra

2) A

B Si b

Suriettiva B B

c- E a

= c-

: - > =

: ' { }

f- 1

BEB

Biettivo b

suriettiva =

3) iniettiva contemporaneamente

e ;

:

.

ti f. A

Prop ha

B si

>

: : ' funzione

è

fbiiettiua f-

la a

< corrispondenza :B >

inversa una

-

-

-

-

' { } { }

f-

f ^

Dim {

b f f-

}

biettivo BEB Contro

1 b

immagine b

di

= di immagine

per per

: < > ;

=

. ,

^ è funzione

⇐ f-

> la una

corrispondenza .

NOTAZIONE :

f f

- iniettiva A B

-

: :

f

f

- B

suriettiva a

:

: > >

f f

biieltiua

' a B

-

:

: '

f- è

f funzione

è

Nota a

se :B

allora biettivo

ed

a

biiettiua suo volto

B >

: >

: a

-

-

- .

.

, .

* " è

If f-

' è

Infatti funzione

-

f- Per

biiettio proposizione

la

: >

= .

* '

f-

( (

b a) f

< b)

e E

> a.

=

, "

"

f ^

( f-

a)

(

b) b. E

E <

a. >

= '

te _

'

cioè

Questo

' è

vale =p

a

anche B

: -

- -

- ,

10/03/2021

-

04

Lez.

Noto funzioni è

h a la

:B

B corrispondenza a-

koh c

K c sua

> composta

: a

>

:

>

. -

-

,

, Ya

funzione ( Kohtla ) a

)

volta Klhla

con

una = e

) '

f f

Def funzione :B

funzione

a invertibile tale

a

B

una dice

si se che

> una

-

: >

: '

'

f' funzione f

Tale

fof f

of idp si inversa

* dice

iota = di

= e . '

' è

è f f

'

f

Se f

invertibile allora invertibile

N.B. inversa

anche con =

: , ,

' è

f è

f f

:D f

Nota a

invertibile

B inversa

:B

se di

allora unica

: - >

, , .

FL

fi funzioni

Infatti da proprietà

se Bo le allora

A con

e :

*

. ,

off

fi

fio

' iaaofj.FI

' fi

of fà

'

f f fof

idpg >

= = =

=

= =

o

, a

, " f

sè

"

E

Def funzione

insieme dice E

si E

stesso

in E invertibile

permutazione ogni

di

: >

:

.

{ } "

5 "

(E) simmetrico

= E

permutazioni

: = su

di gruppo '

f

f. proprietà è

ti

proposizione f

In

le

a seguenti inversa la

tal

valenti

qui

B ( caso di

- sono :

: ,

f ^

è f-

invertibile )

1) inversa

corrispondenza

f è biettivo

2) . " è

f

la funzione

3) inversa

corrispondenza una

(3)

(2)

I

11

Dim Dimostriamo 3=>1

3

2

: 1=>2

< > ; ;

=

(1) Già visto biiettiuo

def di

i )

.

. ' f' '

f è

f fof

è f

of infatti

] t.co Allora

iota

la :B a iniettiva

(2) io

invertibile

Per 11 > =

> e = B

= . . ,

'

'

fica '

'

floi

" f-

( (

f

f- " "

) "

)

fia

f-

( of

)

)

(

" alla

A) la fla

' Ida

è se "

l

allora '

la io )

)

A )

) =

=

) '

Q = =

) a

c- a = . a

= =

= )

☐

, , )

' f'

(

( f

) )

fof (

è perchè b

f )

suriettiva (

fla

fb ] b

infatti =

b b

.ca area

idb

B b)

(

e )

c- =

a = =

:

, , ,

' '

' è perchè

f-

f- è f

f. of

funzione Infatti

funzione Ida

Per inversa

(3) tale

3) =

allora

una per ,

, , (

' '

' ' f- f-

(

f- f- f-

f- fo

)

( f) (b)

(a) '

fa perchè /

fla fb b)

( =

f- f- )

a ( B

Ida )

(b) =

(

= E

=

o io

=

=

c- ;

=

) a

a }

☐ , ,

f- b

(a) IOIB

= =

= { } { }

)

( f

Def E

2 b insieme 2

funzione

E E

funzione

dic