Matematica Logica Appunti Del Corso Di Logica Matematica Martini

download Matematica Logica Appunti Del Corso Di Logica Matematica Martini

of 77

Transcript of Matematica Logica Appunti Del Corso Di Logica Matematica Martini

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    1/77

    A p p u n t i d e l c o r s o d i L o g i c a M a t e m a t i c a

    d e l p r o f . S i m o n e M a r t i n i

    A . A . 1 9 9 3 / 9 4

    F a u s t o S p o t o

    D i p a r t i m e n t o d i I n f o r m a t i c a

    U n i v e r s i t a d i P i s a

    e { m a i l : s p o t o @ d i . u n i p i . i t

    w w w { a d d r e s s : w w w . d i . u n i p i . i t / s p o t o / i n t r o . h t m l

    G i a c o m o P i c c i n e l l i

    D i p a r t i m e n t o d i I n f o r m a t i c a

    U n i v e r s i t a d i P i s a

    e { m a i l : p i c c i n e l @ c l i . d i . u n i p i . i t

    w w w { a d d r e s s : w w w . c l i . d i . u n i p i . i t / p i c c i n e l / i n t r o . h t m l

    F e b b r a i o 1 9 9 6

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    2/77

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    3/77

    N e s s u n o p o t r a m a i r a p i r c i d a l p a r a d i s o c h e C a n t o r

    h a c r e a t o p e r n o i .

    p r o f . D a v i d H i l b e r t

    D a v i d H i l b e r t l a v o r a v a a l l ' U n i v e r s i t a d i G u t t i n -

    g a , a l l ' e p o c a u n a d e l l e p i u r i n o m a t e q u a n t o a s t u d i

    m a t e m a t i c i , p o i s f a s c i a t a d a i n a z i s t i

    p r o f . S i m o n e M a r t i n i

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    4/77

    Q u e s t i a p p u n t i n o n p r e t e n d o n o a s s o l u t a m e n t e d i s o s t i t u i r e u n c o r s o d i l o g i c a

    m a t e m a t i c a p o i c h e e s s i s o n o i n c o m p l e t i e p r i v i d e l n e c e s s a r i o t o n o i n t r o d u t t i v o n e -

    c e s s a r i o a c h i s i a v v i c i n a p e r l a p r i m a v o l t a a d u n a m a t e r i a s c i e n t i c a c o s a r t i c o l a t a .

    E s s i p o s s o n o i n v e c e e s s e r e d i o t t i m o s u s s i d i o d u r a n t e l a f r e q u e n z a d i u n c o r s o s u i

    f o n d a m e n t i d e l l a l o g i c a m a t e m a t i c a .

    U n r i n g r a z i a m e n t o p a r t i c o l a r e v a a l p r o f e s s o r e S i m o n e M a r t i n i , c h e m o l t o p a -

    z i e n t e m e n t e e c o n g r a n d e p r o f e s s i o n a l i t a h a e s p o s t o g l i a r g o m e n t i q u i b r e v e m e n t e

    r a c c o l t i , e c h e m i h a f o r n i t o l ' a i u t o d i c u i a v e v o b i s o g n o p e r i m p a g i n a r e q u e s t o d o c u -

    m e n t o c o n L

    A

    T

    E

    X . G r a z i e i n o l t r e a G i a c o m o P i c c i n e l l i , c h e s i e i m p e g n a t o a f o r n i r m i

    g l i a p p u n t i d e l c o r s o q u a n d o , s e g u e n d o l e z i o n i b e n m e n o u t i l i , n o n h o p o t u t o e s s e r e

    p r e s e n t e a q u e l l e d i l o g i c a m a t e m a t i c a .

    P i s a , e s t a t e 1 9 9 4

    F . S .

    L a r e v i s i o n e d i q u e s t i a p p u n t i h a c o m p o r t a t o l a c o r r e z i o n e d i u n g r a n n u m e r o d i

    e r r o r i p r e s e n t i n e l l a p r i m a s t e s u r a ; s o n o s t a t i i n o l t r e a g g i u n t i d u e c a p i t o l i r e l a t i v i a l

    { c a l c o l o e a l l e R e t i d i P e t r i , i n t e g r a l m e n t e d o v u t i a G i a c o m o P i c c i n e l l i .

    P i s a , f e b b r a i o 1 9 9 6

    G . P . e F . S .

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    5/77

    I n d i c e

    1 L a l o g i c a m a t e m a t i c a 3

    1 . 1 P a t o l o g i e d e l p r o c e s s o d e d u t t i v o c l a s s i c o : : : : : : : : : : : : : : : : 3

    1 . 2 A p p l i c a z i o n i d e l l a l o g i c a m a t e m a t i c a a l l ' i n f o r m a t i c a : : : : : : : : : : 3

    2 I S i s t e m i f o r m a l i 5

    2 . 1 I s i s t e m i f o r m a l i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5

    2 2 C L : u n e s e m p i o d i s i s t e m a f o r m a l e : : : : : : : : : : : : : : : : : : : 7

    3 I l c a l c o l o p r o p o s i z i o n a l e 9

    3 . 1 I l s i s t e m a f o r m a l e P

    0

    : : : : : : : : : : : : : : : : : : : : : : : : : : : 9

    3 . 2 I l t e o r e m a d i d e d u z i o n e e l e s u e c o n s e g u e n z e : : : : : : : : : : : : : : 1 0

    3 . 3 S e m a n t i c a d i P

    0

    : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 4

    3 . 4 C o r r e t t e z z a e c o m p l e t e z z a d i P

    0

    : : : : : : : : : : : : : : : : : : : : : 1 5

    3 . 5 I t a b l e a u x p r o p o s i z i o n a l i : : : : : : : : : : : : : : : : : : : : : : : : : 1 8

    4 I l c a l c o l o d e i p r e d i c a t i 2 9

    4 . 1 I l l i n g u a g g i o d e i p r e d i c a t i : : : : : : : : : : : : : : : : : : : : : : : : 2 9

    4 . 2 S o s t i t u z i o n i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 2

    4 . 3 I l s i s t e m a f o r m a l e P L : : : : : : : : : : : : : : : : : : : : : : : : : : 3 6

    4 . 4 C o r r e t t e z z a e c o m p l e t e z z a d i P L : : : : : : : : : : : : : : : : : : : : 4 2

    4 . 5 I t a b l e a u x p e r p r e d i c a t i : : : : : : : : : : : : : : : : : : : : : : : : : 4 6

    5 E l e m e n t i d i t e o r i a d e i m o d e l l i 5 1

    5 . 1 I t e o r e m i d i S k o l e m : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 1

    5 . 2 I m m e r s i o n i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 2

    6 I n t r o d u z i o n e a l { c a l c o l o n o n t i p a t o 5 7

    6 . 1 M o t i v a z i o n i s t o r i c h e : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 7

    6 . 2 D e n i z i o n e d e l { c a l c o l o : : : : : : : : : : : : : : : : : : : : : : : : : 5 7

    6 . 3 F o r m a l i z z a z i o n e d e l { C a l c o l o : : : : : : : : : : : : : : : : : : : : : : 6 1

    6 . 4 C o m b i n a t o r i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 4

    6 . 5 T u r i n g { e q u i v a l e n z a : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 5

    6 . 6 C o n c l u s i o n i : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 9

    7 I n t r o d u z i o n e a l l e R e t i d i P e t r i 7 1

    7 . 1 T e o r i a e l e m e n t a r e d e l l e R e t i d i P e t r i : : : : : : : : : : : : : : : : : : 7 1

    1

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    6/77

    2 I N D I C E

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    7/77

    C a p i t o l o 1

    L a l o g i c a m a t e m a t i c a

    I l p r o c e d i m e n t o t r a m i t e i l q u a l e s i p a s s a d a c o s e v e r e a c o s e v e r e e d e t t o i n f e r e n z a

    N o i s i a m o i n t e r e s s a t i a d e d u r r e d e l l e a r g o m e n t a z i o n i c o r r e t t e , c i o e d e r i v a b i l i s e c o n d o

    d e i p u r i m e c c a n i s m i d i t r a s f o r m a z i o n e s i n t a t t i c a ; i n n e a q u e s t o g i o c o d i s i m b o l i

    v o g l i a m o a s s o c i a r e u n s i g n i c a t o l a s e m a n t i c a , f a t t a d i s t r u t t u r e m a t e m a t i c h e . D a t a

    u n a s i n t a s s i v o g l i o c h e l e s u e t r a s f o r m a z i o n i a b b i a m o u n v a l o r e s e m a n t i c o c o r r e t t o

    ( c o r r e t t e z z a o v a l i d i t a ) ; i n v e r s a m e n t e p o t r e i r i c h i e d e r e c h e i l c a l c o l o s i n t a t t i c o s i a

    s u c i e n t e m e n t e p o t e n t e d a p o t e r d e s c r i v e r e q u a l s i a s i p r o b l e m a p e r c u i e s t a t o s c r i t t o

    ( c o m p l e t e z z a )

    O g g e t t o d e l c o r s o : l a d e d u z i o n e n a t u r a l e .

    M e t o d o : u n a p a r t e r i s t r e t t a d e l l a m a t e m a t i c a .

    N o n c i p r e o c c u p e r e m o c e r t o d e g l i a s p e t t i f o n d a z i o n a l i d e l l a l o g i c a m a t e m a t i c a .

    1 . 1 P a t o l o g i e d e l p r o c e s s o d e d u t t i v o c l a s s i c o

    N e l c o r s o d e i s e c o l i , m a p a r t i c o l a r m e n t e n e l n o s t r o , s i s o n o p r e s e n t a t e d e l l e i n -

    c o n g r u e n z e n e l p r o c e s s o d e d u t t i v o c l a s s i c o c h e h a n n o s p i n t o g l i s t u d i o s i a c e r c a r e

    u n a f o r m a l i z z a z i o n e d e l l o s t e s s o , n e l l a c o n v i n z i o n e c h e e s s a a v r e b b e e s c l u s o d e n i -

    t i v a m e n t e t a l i f e n o m e n i p a t o l o g i c i . I l t e n t a t i v o s a r a d e s t i n a t o a f a l l i r e m a n o n p e r

    q u e s t o l o s t u d i o d e l l a l o g i c a m a t e m a t i c a v a c o n s i d e r a t o i n u t i l e , c o m e a v r e m o m o d o

    d i o s s e r v a r e i n s e g u i t o . F r a i p a r a d o s s i p i u n o t i c i t i a m o :

    i l p a r a d o s s o d i R u s s e l : d i c i a m o c h e u n i n s i e m e X e n o r m a l e s e e s o l o s e X 6 X

    S i a N = f X X e n o r m a l e g . C i c h i e d i a m o : N N ? D i s t i n g u i a m o d u e c a s i :

    { N N : a l l o r a N e n o r m a l e e q u i n d i N 6 N , a s s u r d o ;

    { N 6 N : a l l o r a N n o n e n o r m a l e e q u i n d i N N , a s s u r d o ;

    i l p a r a d o s s o d e l m e n t i t o r e ( o d e l b a r b i e r e ) : Q u e s t a f r a s e e f a l s a : h o d e t t o i l

    v e r o o i l f a l s o ?

    1 . 2 A p p l i c a z i o n i d e l l a l o g i c a m a t e m a t i c a a l l ' i n f o r m a t i c a

    L ' i n f o r m a t i c o g u a r d a a l l a l o g i c a m a t e m a t i c a c o m e a d u n o s t r u m e n t o : p u r d i r a g -

    g i u n g e r e i n i p e r c u i l a h a s t u d i a t a n o n s i p r e o c c u p a d i c a m b i a r e p u n t o d i v i s t a o

    s c u o l a d i p e n s i e r o .

    L e a p p l i c a z i o n i t i p i c h e d e l l a l o g i c a m a t e m a t i c a a l l ' i n f o r m a t i c a s o n o :

    p r o g r a m m a z i o n i l o g i c a ;

    3

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    8/77

    4 C A P I T O L O 1 . L A L O G I C A M A T E M A T I C A

    i n t e l l i g e n z a a r t i c i a l e ( l o n e s i m b o l i c o ) ;

    d i m o s t r a z i o n e d i c o r r e t t e z z a d e i p r o g r a m m i : w e a k e s t p r e c o n d i t i o n s . . .

    c a r a t t e r i z z a z i o n e d e l l e c l a s s i c o m p u t a z i o n a l i ;

    t e o r e m i l i m i t a t i v i d i C h u r c h e G o d e l ;

    t e o r i a d e l l a d i m o s t r a z i o n e .

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    9/77

    C a p i t o l o 2

    I S i s t e m i f o r m a l i

    2 . 1 I s i s t e m i f o r m a l i

    D e n i z i o n e 2 . 1 U n s i s t e m a f o r m a l e D e d a t o d a :

    u n i n s i e m e n u m e r a b i l e S ( a l f a b e t o o r i s e r v a d i s i m b o l i ) ;

    u n i n s i e m e d e c i d i b i l e W S

    ( i n s i e m e d e l l e f o r m u l e b e n f o r m a t e ( f b f ) ) ;

    u n i n s i e m e A x W ( i n s i e m e d e g l i a s s i o m i ) ; s e A x e d e c i d i b i l e , i l s i s t e m a

    f o r m a l e e d e t t o r i c o r s i v a m e n t e a s s i o m a t i z z a t o ;

    u n i n s i e m e R = f R

    i

    g

    i 2 I

    , c o n R

    i

    W

    n

    i

    i

    c o n I e d n

    i

    2 n i t i ( i n s i e m e n i t o

    d i r e g o l e n i t a r i e ) .

    L a c o p p i a < S ; W > e d e t t a l i n g u a g g i o f o r m a l e .

    D e n i z i o n e 2 . 2 D i c e s i d e n i z i o n e e s p l i c i t a l a d e n i z i o n e d i u n t e r m i n e c h e v i e n e

    a g g i u n t o a l l ' a l f a b e t o d e l l i n g u a g g i o p e r s i g n i c a r n e u n ' e s p r e s s i o n e .

    N o t a z i o n e : s e R W

    3

    a l l o r a s c r i v e r o R ( ; ; ) n e l l a f o r m a

    D e n i z i o n e 2 . 3 D a t o u n i n s i e m e M d i f b f n e l s i s t e m a f o r m a l e D , u n a D - d e r i v a z i o n e

    ( p r o v a , d i m o s t r a z i o n e ) a p a r t i r e d a M e u n a s u c c e s s i o n e n i t a d i f b f

    1

    ; : : : ;

    n

    d i

    D t a l e c h e , p e r o g n i i = 1 ; : : : ; n s i a b b i a :

    i

    2 A x o p p u r e

    i

    2 M o p p u r e

    (

    h

    1

    ; : : : ;

    h

    n

    j

    ) 2 R

    j

    p e r q u a l c h e j 2 I

    i

    =

    h

    n

    j

    e h

    1

    ; : : : ; h

    n

    j

    1

    < i

    D e n i z i o n e 2 . 4 U n a f o r m u l a e d e r i v a b i l e n e l s i s t e m a f o r m a l e D a p a r t i r e d a

    u n i n s i e m e d i i p o t e s i M s e e s o l o s e e s i s t e u n a D - d e r i v a z i o n e a p a r t i r e d a M l a

    c u i u l t i m a f b f e . S c r i v e r e m o a l l o r a M

    D

    e l e g g e r e m o : M d e r i v a ( p r o v a ) n e l

    s i s t e m a f o r m a l e D

    S e M e v u o t o s c r i v e r e m o

    D

    e l e g g e r e m o : e u n t e o r e m a i n D ( o d i D )

    M 6

    D

    s e e s o l o s e n o n v a l e M

    D

    D e n i z i o n e 2 . 5 S i a R l ' i n s i e m e d e l l e r e g o l e d i u n s i s t e m a f o r m a l e D ; u n a r e g o l a

    R

    1

    ; : : : ;

    k

    k + 1

    R 62 R , e d e t t a d e r i v a b i l e i n D s e e s o l o s e p e r t u t t e l e f b f

    1

    ; : : : ;

    k

    c h e s o d d i s f a n o R s i h a :

    1

    ; : : : ;

    k

    D

    k + 1

    R e d e t t a a m m i s s i b i l e ( o e l i m i n a b i l e ) i n D s e e s o l o s e d a

    D f R g

    s e g u e

    D

    , d o v e D f R g d e n o t a i l s i s t e m a f o r m a l e o t t e n u t o d a D c o n l ' a g g i u n t a d e l l a

    r e g o l a R

    5

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    10/77

    6 C A P I T O L O 2 . I S I S T E M I F O R M A L I

    P r o p o s i z i o n e 2 . 1 O g n i r e g o l a d e r i v a b i l e e a m m i s s i b i l e .

    D i m o s t r a z i o n e : D a t a u n a d e r i v a z i o n e :

    D f R g

    , p o s s o s o s t i t u i r e o g n i a p p l i c a -

    z i o n e d e l l a r e g o l a R c o n l a c o r r i s p o n d e n t e d e r i v a z i o n e c h e e s i s t e i n D p o i c h e R e

    d e r i v a b i l e .

    O s s e r v a z i o n e : l ' i n v e r s o n o n e v e r o e n e v e d r e m o u n e s e m p i o i n s e g u i t o ( t e o r e m a

    3 . 8 )

    O s s e r v a z i o n e : u n a t e c n i c a c h e s i u t i l i z z a p e r d i m o s t r a r e l a r e c i p r o c a n o n d e r i v a b i -

    l i t a d i u n i n s i e m e d i a s s i o m i e l a s e g u e n t e : p r e n d e n d o c o m e e s e m p i o P

    0

    , p o t r e m m o

    c e r c a r e u n a p r o p r i e t a I c h e v a l g a p e r d u e e s o l o d u e d e i s u o i t r e a s s i o m i , n o n c h e

    i n v a r i a n t e r i s p e t t o a l l ' a p p l i c a z i o n e d e l m o d u s p o n e n s ; i l t e r z o a s s i o m a , p e r c u i n o n

    v a l e I , n o n p o t r a c h e e s s e r e i n d i p e n d e n t e d a i p r i m i d u e : i n c a s o c o n t r a r i o , i n f a t -

    t i , s a r e b b e d e r i v a t o d a e s s i p e r ( r i p e t u t a ) a p p l i c a z i o n e d e l m o d u s p o n e n s , e p e r l e

    p r o p r i e t a d i I I d o v r e b b e v a l e r e a n c h e p e r e s s o , i l c h e e p e r i p o t e s i f a l s o .

    P r o p o s i z i o n e 2 . 2 S e M

    D

    a l l o r a e s i s t e N M N n i t o , p e r i l q u a l e s i h a :

    N

    D

    . Q u i n d i l e d i m o s t r a z i o n i s o n o e s p o n i b i l i i n t e m p o n i t o .

    D i m o s t r a z i o n e : M

    D

    s e e s o l o s e e s i s t e u n a s e q u e n z a

    1

    ; : : : ;

    n

    c h e e u n a

    d e r i v a z i o n e ; s o l o u n n u m e r o m i n o r e o u g u a l e a d n , e q u i n d i n i t o , d e l l e

    i

    a p p a r t i e n e

    a d M , p e r c u i b a s t a p r e n d e r e N = M \ f

    1

    ; : : : ;

    n

    g p e r o t t e n e r e l a t e s i .

    P r o p o s i z i o n e 2 . 3 S e M

    D

    1

    ; : : : ; M

    D

    n

    e f

    1

    ; : : : ;

    n

    g

    D

    , a l l o r a s i a v r a M

    D

    D i m o s t r a z i o n e : p e r i p o t e s i s o c h e e s i s t e u n a D - d e r i v a z i o n e

    1

    ; : : : ;

    k

    d i a

    p a r t i r e d a f

    1

    ; : : : ;

    n

    g ; s e p e r q u a l c h e i e j s i h a

    i

    =

    j

    , s o s t i t u i s c o

    i

    c o n l a

    D - d e r i v a z i o n e M

    D

    j

    . C o s f a c e n d o o t t e n g o u n a D - d e r i v a z i o n e c o n i p o t e s i s o l o i n

    M

    O s s e r v a z i o n e : q u i n d i i l e m m i , t e o r i c a m e n t e , n o n s o n o n e c e s s a r i .

    D e n i z i o n e 2 . 6 U n s i s t e m a f o r m a l e D e d e t t o c o n s i s t e n t e s e e s o l o s e e s i s t e u n a

    f b f d i D t a l e c h e 6

    D

    ; s e D n o n e c o n s i s t e n t e e d e t t o i n c o n s i s t e n t e .

    D e n i z i o n e 2 . 7 ( I n s i e m e d e l l e c o n s e g u e n z e ) S i a u n i n s i e m e n i t o d i f b f d i

    u n s i s t e m a f o r m a l e D ; C o n

    D

    ( ) = f 2 W g

    D e n i z i o n e 2 . 8 S i a u n i n s i e m e n i t o d i f b f d i u n s i s t e m a f o r m a l e D

    e d e t t o c o n s i s t e n t e ( r i s p e t t o a D ) s e e s o l o s e e s i s t e 2 W t a l e c h e 6

    D

    ( o v v e r o s e e s o l o s e C o n

    D

    ( ) 6= W ) ;

    e d e t t o i n c o n s i s t e n t e ( r i s p e t t o a D ) o c o n t r a d d i t t o r i o ( r i s p e t t o a D ) s e e

    s o l o s e n o n e c o n s i s t e n t e .

    O s s e r v a n d o c h e C o n

    D

    ( ) , s i h a :

    D e n i z i o n e 2 . 9 ( T e o r i a ) U n i n s i e m e d i f b f d i u n s i s t e m a f o r m a l e D e d e t t o

    t e o r i a i n D s e e s o l o s e e c h i u s o r i s p e t t o a l l a r e l a z i o n e

    D

    ( o v v e r o s e e s o l o s e

    C o n

    D

    ( ) = , o v v e r o a n c o r a s e e s o l o s e d a

    D

    s e g u e 2 )

    D e n i z i o n e 2 . 1 0 ( T e o r i a p u r a ) L a t e o r i a p u r a d i u n s i s t e m a f o r m a l e D e l ' i n s i e m e

    C o n

    D

    ( ; ) = C o n

    D

    ( A x )

    O s s e r v a z i o n e : u n a t e o r i a p u r a e u n a t e o r i a .

    O s s e r v a z i o n e : p u o c a p i t a r e c h e s i a b b i a 6= e c i o n o n o s t a n t e c h e C o n

    D

    ( ) = C o n

    D

    ( )

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    11/77

    2 . 2 . C L : U N E S E M P I O D I S I S T E M A F O R M A L E 7

    2 2 C L : u n e s e m p i o d i s i s t e m a f o r m a l e

    D e n i z i o n e 2 . 1 1 ( I l s i s t e m a f o r m a l e C L ) C h i a m i a m o s i s t e m a f o r m a l e C L i l s i -

    s t e m a f o r m a l e c o s d e n i t o :

    S = f k ; s ; ( ) = g ( a l f a b e t o ) ;

    W = f P = Q P Q 2 g d o v e e l ' i n s i e m e d e i t e r m i n i c o s d e n i t o :

    1 k 2 d 2 ;

    2 . s e P Q 2 a l l o r a ( P Q ) 2 ;

    3 . n i e n t ' a l t r o e u n t e r m i n e ;

    A x : p e r o g n i P ; Q ; R 2 i s e g u e n t i s o n o s c h e m i d i a s s i o m a :

    { ( ( k P ) Q ) = P ( A x k ) ;

    { P = P ( a s s i o m a d i r i e s s i v i t a ) ;

    { ( ( ( s P ) Q ) R ) = ( ( P R ) ( Q R ) ) ( A x s ) ;

    { n i e n t ' a l t r o e u n a s s i o m a . ( S i n o t i c h e u n o s c h e m a d i a s s i o m a e u n m o d o

    p e r d e s c r i v e r e u n n u m e r o e v e n t u a l m e n t e i n n i t o d i a s s i o m i c o n u n ' u n i c a

    e s p r e s s i o n e ) .

    R = f R

    1

    R

    2

    R

    3

    R

    4

    g d o v e :

    { R

    1

    = f ( P = Q Q = P ) P Q 2 g W

    2

    o v v e r o :

    P = Q

    Q = P

    ;

    { R

    2

    = f ( P = Q Q = R P = R ) P ; Q ; R 2 g W

    3

    o v v e r o :

    P = Q Q = P

    P = R

    ( T R A N S ) ;

    { R

    3

    = f ( R = R ( P R ) = ( Q R ) ( P R ) = ( Q R ) ) P ; Q ; R ; R 2 g

    o v v e r o :

    R = R ( P R ) = ( Q R )

    ( P R ) = ( Q R )

    ( C O N G R 1 ) ;

    { R

    4

    = f ( R = R ( R P ) = ( R Q ) ( R P ) = ( R Q ) ) P ; Q ; R ; R 2 g

    o v v e r o :

    R = R ( R P ) = ( R Q )

    ( R P ) = ( R Q )

    ( C O N G R 2 )

    E s e m p i o : u n a d e d u z i o n e i n C L : d i m o s t r i a m o c h e

    C L

    ( ( ( s k ) k ) k ) = k

    1 . ( ( ( s k ) k ) k ) = ( ( k k ) ( k k ) ) A x s

    2 . ( ( k k ) ( k k ) ) = k A x k c o n P k e Q ( k k )

    3 k T R A N S ( 1 2 )

    O s s e r v a z i o n e : s i s a r e b b e p o t u t o m o s t r a r e , p i u g e n e r i c a m e n t e , c h e p e r o g n i M 2

    s i h a :

    C L

    ( ( ( s k ) k ) M ) = M

    I n t r o d u c i a m o l a s e g u e n t e d e n i z i o n e e s p l i c i t a : I = ( ( s k ) k )

    O s s e r v a z i o n e : q u i n d i h o a p p e n a m o s t r a t o c h e

    C L

    ( I M ) = M

    E s e m p i o : d i m o s t r i a m o c h e

    C L

    ( ( ( s I ) I ) M ) = ( M M ) p e r o g n i M 2

    1 . ( ( ( s I ) I ) M ) = ( ( I M ) ( I M ) ) A x s

    2 ( I M ) = M e s e m p i o p r e c e d e n t e

    3 . ( ( I M ) ( I M ) ) = ( ( I M ) ( I M ) ) a s s i o m a d i r i e s s i v i t a

    4 . ( ( I M ) ( I M ) ) = ( M ( I M ) ) C O N G R 1 ( 2 3 )

    5 . ( ( I M ) ( I M ) ) = ( M M ) C O N G R 2 ( 2 4 )

    6 . ( ( ( s I ) I ) M ) = ( M M ) T R A N S ( 1 5 )

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    12/77

    8 C A P I T O L O 2 . I S I S T E M I F O R M A L I

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    13/77

    C a p i t o l o 3

    I l c a l c o l o p r o p o s i z i o n a l e

    3 . 1 I l s i s t e m a f o r m a l e P

    0

    C h i a m i a m o p r o p o s i z i o n i d e l l e e s p r e s s i o n i e l e m e n t a r i s u s c e t t i b i l i d i p o s s e d e r e u n

    v a l o r e d i v e r i t a ; c h i a m i a m o i n v e c e v a r i a b i l i p r o p o s i z i o n a l i d e l l e v a r i a b i l i c h e s t a n n o

    p e r p r o p o s i z i o n i : d i s o l i t o l e i n d i c h e r e m o c o n p ; q ; r ; : : : . U n a s s e g n a m e n t o p r o p o s i -

    z i o n a l e e u n a f u n z i o n e c h e a s s o c i a a d o g n i v a r i a b i l e p r o p o s i z i o n a l e u n v a l o r e d i v e r i t a

    ( 0 1 ) ; c h i a m e r e m o t a u t o l o g i a u n a f b f i l c u i v a l o r e d i v e r i t a , c a l c o l a t o s e c o n d o l e

    o p p o r t u n e r e g o l e p e r i c o n n e t t i v i i n e s s a p r e s e n t i , e s e m p r e 1 , i n d i p e n d e n t e m e n t e

    d a l l ' a s s e g n a m e n t o p r o p o s i z i o n a l e s c e l t o .

    I l c a l c o l o p r o p o s i z i o n a l e e u n s i s t e m a f o r m a l e i c u i t e o r e m i s o n o t u t t e e s o l e l e

    t a u t o l o g i e .

    D e n i z i o n e 3 . 1 I l s i s t e m a f o r m a l e P

    0

    ( c a l c o l o p r o p o s i z i o n a l e ) e i l s e g u e n t e s i s t e -

    m a f o r m a l e :

    S : e f o r m a t o d a l l ' u n i o n e f r a u n i n s i e m e n u m e r a b i l e d i v a r i a b i l i p r o p o s i z i o n a l i :

    p ; q ; r ; s ; : : : , l ' i n s i e m e d e i c o n n e t t i v i ! e : ( i m p l i c a e n o t ) e l ' i n s i e m e d e i d u e

    s i m b o l i a u s i l i a r i ( e ) ;

    W : l ' i n s i e m e d e l l e f b f e c o s d e n i t o :

    1 . o g n i v a r i a b i l e p r o p o s i z i o n a l e e u n a f b f ;

    2 . s e e s o n o f b f a l l o r a l o s o n o a n c h e ( ! ) e ( : ) ;

    3 . n i e n t ' a l t r o e u n a f b f .

    I n t r o d u c i a m o l e s e g u e n t i d e n i z i o n i e s p l i c i t e : _ ( ( : ) ! )

    : ( ( : ) _ ( : ) ) e $ ( ! ) ( ! )

    E s i s t e u n a c o n v e n z i o n e d i p r e c e d e n z a f r a i c o n n e t t i v i : : ( _ ) ! . Q u i n d i

    ! : ( ( ) ! ( : ) )

    A x :

    { ! ( ! ) ( A k )

    { ( ! ( ! ) ) ! ( ( ! ) ! ( ! ) ) ( A S )

    { ( : ! : ) ! ( ( : ! ) ! ) ( A : )

    R = f M P g d o v e M P ( m o d u s p o n e n s ) e l a r e g o l a :

    !

    I l n o s t r o s c o p o s a r a a d e s s o q u e l l o d i s t u d i a r e C o n

    P

    0

    ( ; ) c i o e l ' i n s i e m e d e i t e o r e m i

    d e l c a l c o l o p r o p o s i z i o n a l e ( a v o l t e d e t t o a n c h ' e s s o P

    0

    )

    9

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    14/77

    1 0 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    P r o p o s i z i o n e 3 . 1

    P

    0

    !

    D i m o s t r a z i o n e :

    1 ( ! ( ( ! ) ! ) ! ( ( ! ( ! ) ) ! ( ! ) ) A S

    2 ! ( ( ! ) ! ) A k c o n !

    3 ( ! ( ! ) ) ! ( ! ) M P ( 1 2 )

    4 ! ( ! ) A k c o n

    5 ! M P ( 3 4 )

    3 . 2 I l t e o r e m a d i d e d u z i o n e e l e s u e c o n s e g u e n z e

    T e o r e m a 3 . 1 ( d i d e d u z i o n e , H e r b r a n d a n n i ' 3 0 ) D a t o u n i n s i e m e d i f b f i n

    P

    0

    s i h a :

    P

    0

    ! s e e s o l o s e

    P

    0

    D i m o s t r a z i o n e :

    ( ) )

    1 i p o t e s i

    k ! e s p a n s i o n e d i

    P

    0

    !

    k + 1 M P ( 1 k )

    Q u i n d i

    P

    0

    ( ( ) C o s t r u i a m o i n d u t t i v a m e n t e u n a d e r i v a z i o n e d i

    P

    0

    ! a p a r t i r e d a u n a

    d e r i v a z i o n e d i

    P

    0

    . S i a d u n q u e

    1

    ; : : : ;

    n

    l a d e r i v a z i o n e

    P

    0

    b a s e : n = 1 : l a d e r i v a z i o n e s i r i d u c e a : ; q u i n d i :

    { e u n a s s i o m a o u n ' i p o t e s i i n :

    1 ! ( ! ) A k

    2 i p o t e s i o a s s i o m a

    3 ! M P ( 1 2 )

    { : s a p p i a m o d a l l a p r o p o s i z i o n e 3 . 1 c h e

    P

    0

    ! , i l c h e i m p l i c a l a

    t e s i .

    i n d . : S u p p o n i a m o d i s a p e r s c r i v e r e u n a d e r i v a z i o n e d e l l a f o r m a

    P

    0

    ! a

    p a r t i r e d a u n a d e r i v a z i o n e

    P

    0

    d i l u n g h e z z a m i n o r e o u g u a l e a d n 1

    e s i a

    P

    0

    d i l u n g h e z z a n ; n > 1 ; s e

    n

    e u n a s s i o m a , u n a i p o t e s i i n

    o p p u r e l a t e s i s e g u e c o m e n e l c a s o b a s e . S e i n v e c e

    n

    e o t t e n u t o p e r m o d u s

    p o n e n s d a

    i

    e

    j

    i ; j < n , s i n o t i c h e p e r i p o t e s i i n d u t t i v a s o c o s t r u i r e l e

    d e r i v a z i o n i

    P

    0

    !

    i

    e

    P

    0

    !

    j

    ; p o i c h e

    n

    e o t t e n u t a p e r m o d u s

    p o n e n s d a

    i

    e

    j

    i

    a v r a l a f o r m a :

    i

    j

    !

    n

    . C o s t r u i s c o a l l o r a u n a

    d e r i v a z i o n e

    P

    0

    ! !

    n

    1 ( ! (

    j

    !

    n

    ) ) ! ( ( !

    j

    ) ! ( !

    n

    ) ) A S

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    15/77

    3 . 2 . I L T E O R E M A D I D E D U Z I O N E E L E S U E C O N S E G U E N Z E 1 1

    k ! (

    j

    !

    n

    ) e s p a n s i o n e d i

    P

    0

    !

    i

    k + 1 ( !

    j

    ) ! ( !

    n

    ) M P ( 1 k )

    h !

    j

    e s p a n s i o n e d i

    P

    0

    !

    j

    h + 1 !

    n

    ! M P ( k + 1 h )

    P r o p o s i z i o n e 3 . 2

    P

    0

    ! ( : ! )

    D i m o s t r a z i o n e : p e r i l t e o r e m a d i d e d u z i o n e b a s t a r i u s c i r e a m o s t r a r e c h e :

    P

    0

    1 ! ( : ! ) A k

    2 i p o t e s i

    3 : ! M P ( 1 2 )

    4 : ! ( : ! : ) A k

    5 : i p o t e s i

    6 : ! : M P ( 4 5 )

    7 ( : ! : ) ! ( ( : ! ) ! ) A :

    8 ( : ! ) ! M P ( 6 7 )

    9 M P ( 3 8 )

    P r o p o s i z i o n e 3 . 3 ( t r a n s i t i v i t a d i ! ) ! !

    P

    0

    !

    D i m o s t r a z i o n e : p e r i l t e o r e m a d i d e d u z i o n e b a s t a r i u s c i r e a m o s t r a r e c h e !

    !

    P

    0

    1 ! i p o t e s i

    2 i p o t e s i

    3 M P ( 1 2 )

    4 ! i p o t e s i

    5 M P ( 3 4 )

    E s e r c i z i o 3 . 1 D i m o s t r a r e l a p r e c e d e n t e p r o p o s i z i o n e s e n z a u s a r e i l t e o r e m a d i d e -

    d u z i o n e ( b a s t a r i e s e g u i r e i p a s s i d i t a l e t e o r e m a ) .

    P r o p o s i z i o n e 3 . 4 : !

    P

    0

    D i m o s t r a z i o n e :

    1 ( : ! : ) ! ( ( : ! ) ! ) A :

    2 : ! : p r o p o s i z i o n e 3 . 1

    3 ( : ! ) ! M P ( 1 2 )

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    16/77

    1 2 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    4 : ! i p o t e s i

    5 M P ( 3 4 )

    P r o p o s i z i o n e 3 . 5 ! ( ! )

    P

    0

    !

    D i m o s t r a z i o n e : p e r i l t e o r e m a d i d e d u z i o n e b a s t a r i u s c i r e a m o s t r a r e c h e !

    ( ! ) ; ;

    P

    0

    1 ! ( ! ) i p o t e s i

    2 i p o t e s i

    3 ! M P ( 1 2 )

    4 i p o t e s i

    5 M P ( 3 4 )

    P r o p o s i z i o n e 3 . 6 : :

    P

    0

    D i m o s t r a z i o n e :

    1 : : ! ( : ! : : ) A k

    2 : : i p o t e s i

    3 : ! : : M P ( 1 2 )

    4 ( : ! : : ) ! ( ( : ! : ) ! ) A :

    5 ( : ! : ) ! M P ( 3 4 )

    6 : ! : p r o p o s i z i o n e 3 . 1

    7 M P ( 5 6 )

    P r o p o s i z i o n e 3 . 7 :

    P

    0

    !

    D i m o s t r a z i o n e : p e r i l t e o r e m a d i d e d u z i o n e b a s t a r i u s c i r e a m o s t r a r e c h e :

    P

    0

    , e q u e s t o e g i a s t a t o m o s t r a t o ( p r o p o s i z i o n e 3 . 2 ) .

    P r o p o s i z i o n e 3 . 8

    P

    0

    ! : :

    D i m o s t r a z i o n e : p e r i l t e o r e m a d i d e d u z i o n e b a s t a r i u s c i r e a m o s t r a r e c h e

    P

    0

    : :

    1 ! ( : : : ! ) A k

    2 ( : : : ! : ) ! ( ( : : : ! ) ! : : ) A :

    3 : : ( : ) ! : p r o p o s i z i o n e 3 . 6

    4 ( : : : ! ) ! : : M P ( 2 3 )

    5 i p o t e s i

    6 : : : ! M P ( 1 5 )

    7 : : M P ( 4 6 )

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    17/77

    3 . 2 . I L T E O R E M A D I D E D U Z I O N E E L E S U E C O N S E G U E N Z E 1 3

    P r o p o s i z i o n e 3 . 9

    P

    0

    ( : : ! : : ) ! ( : ! : )

    D i m o s t r a z i o n e : p e r i l t e o r e m a d i d e d u z i o n e b a s t a m o s t r a r e c h e : : ! : : :

    P

    0

    :

    1 ( : : ! : : : ) ! ( ( : : ! : : ) ! : ) A :

    2 : ! : : : p r o p o s i z i o n e 3 . 8

    3 : i p o t e s i

    4 : : : M P ( 2 3 )

    5 : : : ! ( : : ! : : : ) A k

    6 : : ! : : : M P ( 4 5 )

    7 ( : : ! : : ) ! : M P ( 1 6 )

    8 : : ! : : i p o t e s i

    9 : M P ( 7 8 )

    P r o p o s i z i o n e 3 . 1 0 !

    P

    0

    : ! :

    D i m o s t r a z i o n e :

    1 : : ! p r o p o s i z i o n e 3 . 6

    2 ! i p o t e s i

    3 : : ! ( p r o p o s i z i o n e 3 . 3 ) T R A N S ( 1 2 )

    4 ! : : p r o p o s i z i o n e 3 . 8

    5 : : ! : : T R A N S ( 3 4 )

    6 ( : : ! : : ) ! ( : ! : ) p r o p o s i z i o n e 3 . 9

    7 : ! : M P ( 5 6 )

    P r o p o s i z i o n e 3 . 1 1 : ( ! )

    P

    0

    D i m o s t r a z i o n e :

    1 ( : ! ( ! ) ) ! ( : ( ! ) ! : : ) p r o p o s i z i o n e 3 . 1 0

    2 : ! ( ! ) p r o p o s i z i o n e 3 . 7

    3 : ( ! ) ! : : M P ( 1 2 )

    4 : ( ! ) i p o t e s i

    5 : : M P ( 3 4 )

    6 : : ! p r o p o s i z i o n e 3 . 6

    7 M P ( 5 6 )

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    18/77

    1 4 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    P r o p o s i z i o n e 3 . 1 2 : ( ! )

    P

    0

    :

    D i m o s t r a z i o n e :

    1 ( ! ( ! ) ) ! ( : ( ! ) ! : ) p r o p o s i z i o n e 3 . 1 0

    2 ! ( ! ) A k

    3 : ( ! ) ! : M P ( 1 2 )

    4 : ( ! ) i p o t e s i

    5 : M P ( 3 4 )

    T e o r e m a 3 . 2 U n i n s i e m e d i f b f d i P

    0

    e c o n t r a d d i t t o r i o ( c i o e , e q u i v a l e n t e m e n t e ,

    C o n

    P

    0

    ( ) = W ) s e e s o l o s e e s i s t e u n a f b f t a l e c h e

    P

    0

    e

    P

    0

    :

    D i m o s t r a z i o n e :

    ( ) ) O v v i o :

    P

    0

    p e r o g n i 2 W

    ( ( ) P e r l a p r o p o s i z i o n e 3 . 2 s a p p i a m o c h e :

    P

    0

    p e r o g n i . D a

    P

    0

    e

    P

    0

    : e d a l l a p r o p o s i z i o n e 2 . 3 c o n c l u d i a m o q u i n d i c h e

    P

    0

    p e r o g n i

    C o r o l l a r i o 3 . 1 P

    0

    e i n c o n s i s t e n t e s e e s o l o s e e s i s t e u n a f b f d i P

    0

    t a l e c h e

    P

    0

    e

    P

    0

    :

    D i m o s t r a z i o n e : p o r r e = ; n e l p r e c e d e n t e t e o r e m a .

    T e o r e m a 3 . 3 S i a u n i n s i e m e c o n s i s t e n t e d i f b f d i P

    0

    e s i a q u i n d i t a l e c h e

    6

    P

    0

    f : g e c o n s i s t e n t e .

    D i m o s t r a z i o n e : s e p e r a s s u r d o f : g f o s s e i n c o n s i s t e n t e , s i a v r e b b e :

    P

    0

    ; p e r i l t e o r e m a d i d e d u z i o n e s i a v r e b b e q u i n d i

    P

    0

    : ! . S a p p i a m o p e r o

    c h e : !

    P

    0

    ( p r o p o s i z i o n e 3 . 4 ) e p e r l a t r a n s i t i v i t a d i

    P

    0

    ( p r o p o s i z i o n e 2 . 3 )

    a v r e i a l l o r a

    P

    0

    , i l c h e e a s s u r d o .

    C o r o l l a r i o 3 . 2 S e f g e c o n t r a d d i t t o r i o a l l o r a

    P

    0

    :

    D i m o s t r a z i o n e : s e e i n c o n s i s t e n t e e o v v i o ; s i a a l l o r a c o n s i s t e n t e ; s e p e r a s -

    s u r d o f o s s e 6

    P

    0

    : , p e r i l t e o r e m a p r e c e d e n t e f : : g s a r e b b e c o n s i s t e n t e ; m a

    p e r l a p r o p o s i z i o n e 3 . 8 o g n i d e r i v a z i o n e f g

    P

    0

    p u o e s s e r e t r a s f o r m a t a i n u n a

    d e r i v a z i o n e f : : g

    P

    0

    ; q u i n d i a n c h e f : : g s a r e b b e c o n t r a d d i t t o r i o , i l

    c h e e a s s u r d o .

    3 . 3 S e m a n t i c a d i P

    0

    D e n i z i o n e 3 . 2 U n a s s e g n a m e n t o p r o p o s i z i o n a l e B e u n a f u n z i o n e B v a r i a b i l i

    p r o p o s i z i o n a l i ! f 0 1 g

    D e n i z i o n e 3 . 3 U n a s s e g n a m e n t o p r o p o s i z i o n a l e B e e s t e s o p e r i n d u z i o n e a d u n a

    v a l u t a z i o n e B d e l l i n g u a g g i o d i P

    0

    n e l m o d o s e g u e n t e :

    B ( p ) = B ( p ) p e r o g n i v a r i a b i l e p r o p o s i z i o n a l e p ;

    B ( ! ) =

    0 s e e s o l o s e B ( ) = 1 e B ( ) = 0 ;

    1 a l t r i m e n t i ;

    B ( : ) = 1 B ( )

    D e n i z i o n e 3 . 4 U n a f b f d i P

    0

    e d e t t a e s s e r e :

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    19/77

    3 . 4 . C O R R E T T E Z Z A E C O M P L E T E Z Z A D I P

    0

    1 5

    u n a t a u t o l o g i a s e e s o l o s e p e r o g n i a s s e g n a m e n t o p r o p o s i z i o n a l e B s i h a

    B ( ) = 1 ;

    ( p r o p o s i z i o n a l m e n t e ) s o d d i s f a c i b i l e s e e s o l o s e e s i s t e u n a s s e g n a m e n t o p r o p o -

    s i z i o n a l e B t a l e c h e B ( ) = 1 ;

    c o n t r a d d i t t o r i a s e e s o l o s e n o n e s o d d i s f a c i b i l e .

    U n i n s i e m e d i f b f d i P

    0

    e d e t t o s o d d i s f a c i b i l e s e e s o l o s e e s i s t e u n a s s e g n a -

    m e n t o p r o p o s i z i o n a l e B t a l e c h e B ( ) = 1 p e r o g n i 2

    P r o p o s i z i o n e 3 . 1 3 U n a f b f d i P

    0

    e u n t a u t o l o g i a s e e s o l o s e : e c o n t r a d d i t -

    t o r i a .

    D i m o s t r a z i o n e : d i r e t t a m e n t e d a l l a d e n i z i o n e d i B p e r i l c o n n e t t i v o :

    P r o p o s i z i o n e 3 . 1 4 S e e ! s o n o t a u t o l o g i e , a n c h e e u n a t a u t o l o g i a .

    D i m o s t r a z i o n e : o v v i o d a l l a d e n i z i o n e d i B

    L e m m a 3 . 1 D a t a u n a f b f d i P

    0

    B ( ) d i p e n d e s o l o d a l v a l o r e a s s e g n a t o d a B

    a l l e v a r i a b i l i p r o p o s i z i o n a l i p r e s e n t i i n

    D i m o s t r a z i o n e : o v v i o d a l l a d e n i z i o n e d i B

    T e o r e m a 3 . 4 D a t a u n a f b f d i P

    0

    , e d e c i d i b i l e s e e u n a t a u t o l o g i a .

    D i m o s t r a z i o n e : b a s t a c o s t r u i r e l a t a b e l l a d i v e r i t a p e r , c h e a v r a u n n u m e r o d i

    c o l o n n e n i t o g r a z i e a l l e m m a p r e c e d e n t e , e q u i n d i c o n t r o l l a r e s e p e r o g n i r i g a s i h a

    B ( ) = 1 .

    D e n i z i o n e 3 . 5 ( c o n s e g u e n z a t a u t o l o g i c a ) D a t a u n a f b f d i P

    0

    e u n i n s i e m e

    d i f b f d i P

    0

    , s i d i c e c h e e c o n s e g u e n z a t a u t o l o g i c a d i s e e s o l o s e p e r o g n i

    a s s e g n a m e n t o p r o p o s i z i o n a l e B s i h a c h e : s e p e r o g n i f b f 2 v a l e B ( ) = 1 a l l o r a

    B ( ) = 1 . S c r i v e r e m o a l l o r a : =

    3 . 4 C o r r e t t e z z a e c o m p l e t e z z a d i P

    0

    T e o r e m a 3 . 5 ( d i c o r r e t t e z z a o d i v a l i d i t a o d i s o u n d n e s s ) S i a n o u n i n s i e -

    m e d i f b f d i P

    0

    e u n a f b f i n P

    0

    ; s i h a c h e :

    s e

    P

    0

    a l l o r a =

    D i m o s t r a z i o n e : p e r i n d u z i o n e s u l l a l u n g h e z z a d e l l a d e r i v a z i o n e

    1

    ; : : : ;

    n

    c o n

    n

    b a s e : n = 1 p u o e s s e r e :

    { u n a s s i o m a : t u t t i g l i a s s i o m i d i P

    0

    s o n o t a u t o l o g i e , e q u i n d i = ; p r o -

    v i a m o a d i m o s t r a r l o p e r l ' a s s i o m a A S , c i o e p e r l a f b f : ( ! ( ! ) ) !

    ( ( ! ) ! ( ! ) )

    ! ! ( ! ) ( ! ) ! ( ! ) A S

    0 0 0 1 1 1 1

    0 0 1 1 1 1 1

    0 1 0 0 1 1 1

    0 1 1 1 1 1 1

    1 0 0 1 1 1 1

    1 0 1 1 1 1 1

    1 1 0 0 0 0 1

    1 1 1 1 1 1 1

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    20/77

    1 6 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    { u n ' i p o t e s i i n : s i a v r a o v v i a m e n t e =

    i n d . : n > 1 ; s e e u n a s s i o m a o u n ' i p o t e s i i n l a t e s i s e g u e c o m e n e l c a s o b a s e ;

    s e i n v e c e e o t t e n u t o p e r m o d u s p o n e n s d a

    i

    e

    j

    , c o n i ; j < n

    j

    a v r a l a

    f o r m a :

    j

    i

    !

    n

    e i n o l t r e , p e r i p o t e s i i n d u t t i v a : =

    i

    e =

    j

    ; s e p e r

    a s s u r d o n o n f o s s e = , e s i s t e r e b b e u n a s s e g n a m e n t o p r o p o s i z i o n a l e B c h e

    s o d d i s f a m a n o n ; m a p e r l ' i p o t e s i i n d u t t i v a B s o d d i s f a

    i

    e

    j

    e q u i n d i ,

    p e r l a d e n i z i o n e d i B s u l c o n n e t t i v o ! , s i a v r a B ( ) = 1 , a s s u r d o . Q u i n d i

    =

    C o r o l l a r i o 3 . 3 P

    0

    e c o n s i s t e n t e .

    D i m o s t r a z i o n e : s e f o s s e i n c o n s i s t e n t e , p e r i l c o r o l l a r i o 3 . 1 e s i s t e r e b b e t a l e c h e

    P

    0

    e

    P

    0

    : ; p e r i l t e o r e m a d i c o r r e t t e z z a e : s a r e b b e r o t a u t o l o g i e , a s s u r d o

    p e r l a d e n i z i o n e d i a s s e g n a m e n t o p r o p o s i z i o n a l e s u l c o n n e t t i v o :

    P r o p o s i z i o n e 3 . 1 5 S i a u n i n s i e m e d i f b f d i P

    0

    ; s e e s o d d i s f a c i b i l e a l l o r a e

    c o n s i s t e n t e .

    D i m o s t r a z i o n e : s a p p i a m o c h e e s i s t e u n a s s e g n a m e n t o p r o p o s i z i o n a l e B c h e s o d -

    d i s f a ; s e p e r a s s u r d o f o s s e i n c o n s i s t e n t e , e s i s t e r e b b e u n a f b f t a l e c h e

    P

    0

    e

    P

    0

    : ; p e r i l t e o r e m a d i c o r r e t t e z z a s i d o v r e b b e q u i n d i a v e r e : B ( ) = 1 e

    B ( : ) = 1 , i l c h e e a s s u r d o p e r l a d e n i z i o n e d i B s u l c o n n e t t i v o :

    D e n i z i o n e 3 . 6 U n i n s i e m e d i f b f d i P

    0

    e c o n s i s t e n t e m a s s i m a l e s e e s o l o s e :

    e c o n s i s t e n t e ;

    s e e e c o n s i s t e n t e a l l o r a = ( o v v e r o : 62 i m p l i c a c h e f g

    e i n c o n s i s t e n t e ) .

    E s e m p i o : s i a d a t o u n a s s e g n a m e n t o p r o p o s i z i o n a l e B ; d e n i a m o l ' i n s i e m e :

    B

    =

    f B ( ) = 1 g

    B

    e c o n s i s t e n t e m a s s i m a l e p o i c h e :

    e c o n s i s t e n t e g r a z i e a l l a p r o p o s i z i o n e 3 . 1 5 ;

    e m a s s i m a l e : s e 62

    B

    a l l o r a B ( ) = 0 , p e r c u i B ( : ) = 1 e q u i n d i : 2

    B

    q u i n d i

    B

    P

    0

    e

    B

    P

    0

    : , o v v e r o

    B

    f g e i n c o n s i s t e n t e .

    L e m m a 3 . 2 ( d e l c o m p l e t a m e n t o d i L i n d e n b a u m ) S i a d a t o u n i n s i e m e c o n s i -

    s t e n t e d i f b f d i P

    0

    ; e s i s t e u n i n s i e m e c o n s i s t e n t e m a s s i m a l e

    t a l e c h e

    e e e t t i v a m e n t e c a l c o l a b i l e a p a r t i r e d a

    D i m o s t r a z i o n e : s s i a m o u n ' e n u m e r a z i o n e

    1

    ; : : :

    n

    ; : : : d i t u t t e l e f b f d i P

    0

    ( s i

    p u o p e n s a r e d i a s s o c i a r e a d o g n i f b f l a s e q u e n z a d e i c o d i c i A S C I I d e i s u o i c a r a t t e r i

    e p o i d i n o r m a l i z z a r e l a n u m e r a z i o n e e l i m i n a n d o i b u c h i ; i l p r o c e s s o e c h i a r a m e n t e

    e e t t i v o ) .

    P o n i a m o :

    0

    =

    n + 1

    =

    n

    f

    n

    g s e

    n

    f

    n

    g e c o n s i s t e n t e ;

    n

    a l t r i m e n t i ;

    =

    S

    n 0

    n

    S i n o t i c h e l a d e n i z i o n e d i

    n

    e e e t t i v a p o i c h e e d e c i d i b i l e i l p r o b l e m a d i d i r e

    s e u n i n s i e m e d i f b f d i P

    0

    e c o n s i s t e n t e

    1

    S i o s s e r v i a d e s s o c h e :

    1

    Q u e s t o s a r a o v v i o d o p o l a d i m o s t r a z i o n e d e l l e m m a d i s o d d i s f a c i b i l i t a , p e r l a q u a l e n o n s e r v e

    l ' e e t t i v i t a d e l c a l c o l o d i

    ( n o n c ' e q u i n d i u n c i r c o l o v i z i o s o ) .

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    21/77

    3 . 4 . C O R R E T T E Z Z A E C O M P L E T E Z Z A D I P

    0

    1 7

    1

    n

    n + 1

    p e r o g n i n ( o v v i o ) ;

    2

    n

    e c o n s i s t e n t e p e r o g n i n ( o v v i o p e r i n d u z i o n e s u n )

    3

    e c o n s i s t e n t e : s e n o n l o f o s s e , e s i s t e r e b b e t a l e c h e

    P

    0

    e

    P

    0

    :

    t a l i d e r i v a z i o n i s a r a n n o f o r m a t e d a u n n u m e r o n i t o d i f b f d i

    ( p r o p o s i z i o n e

    2 . 2 ) e q u i n d i , p e r i l p u n t o 1 , e s i s t e u n i n t e r o m t a l e c h e

    m

    P

    0

    e

    m

    P

    0

    :

    o v v e r o

    m

    e i n c o n s i s t e n t e , a s s u r d o p e r i l p u n t o 2 ;

    4

    e m a s s i m a l e : s i a 62

    e s i s t e c e r t a m e n t e p o i c h e

    e c o n s i s t e n t e ; s a r a

    k

    p e r u n c e r t o k ; i n o l t r e s i s a r a o p e r a t o a l p a s s o k i n m o d o t a l e c h e

    k + 1

    =

    k

    a l t r i m e n t i , s e

    k + 1

    =

    k

    f

    k

    g , s i a v r e b b e

    k

    2

    , i l c h e e c o n t r o

    l a n o s t r a i p o t e s i i n i z i a l e ; q u i n d i

    k

    f

    k

    g e i n c o n s i s t e n t e e , p e r i l p u n t o 1 ,

    a n c h e

    f g l o e . Q u e s t o p r o v a c h e

    e m a s s i m a l e .

    O s s e r v a z i o n e : I l p r e c e d e n t e l e m m a , p u r d i m o d i c a r e l a d i m o s t r a z i o n e d e l p u n t o

    3 , e v a l i d o a n c h e p e r g e n e r i c i s i s t e m i f o r m a l i e , c a m b i a n d o t o t a l m e n t e l a d i m o s t r a -

    z i o n e , a n c h e p e r l i n g u a g g i t r a n s n i t i ( c i o e c o n W d i c a r d i n a l i t a n o n n u m e r a b i l e ) .

    P r o p o s i z i o n e 3 . 1 6 U n i n s i e m e c o n s i s t e n t e m a s s i m a l e d i f b f d i P

    0

    g o d e d e l l e

    s e g u e n t i p r o p r i e t a :

    i e u n a t e o r i a ;

    i i . p e r o g n i f b f d i P

    0

    2 s e e s o l o s e : 62 ;

    i i i . p e r o g n i c o p p i a d i f b f d i P

    0

    e ! 2 s e e s o l o s e d a 2 s e g u e

    2

    D i m o s t r a z i o n e :

    i . B a s t a m o s t r a r e c h e 2 s e e s o l o s e

    P

    0

    ( ) ) O v v i o .

    ( ( ) S e p e r a s s u r d o 62 f g s a r e b b e i n c o n s i s t e n t e p o i c h e e m a s s i m a l e ;

    p e r i l c o r o l l a r i o 3 . 2 a v r e i

    P

    0

    : , a s s u r d o p o i c h e p e r i p o t e s i

    P

    0

    e p e r

    l a c o n s i s t e n z a d i .

    i i . ( ) ) S e f o s s e 2 e : 2 a l l o r a s a r e b b e i n c o n s i s t e n t e , i l c h e e a s s u r d o .

    ( ( ) S e p e r a s s u r d o : 62 e 62 , p e r l a m a s s i m a l i t a d i g l i i n s i e m i f g

    e f : g s a r e b b e r o i n c o n s i s t e n t i ; q u i n d i :

    P

    0

    e

    P

    0

    : ; p e r

    l a p r o p o s i z i o n e 3 . 4 e p e r m o d u s p o n e n s a v r e i

    P

    0

    e

    P

    0

    : , a s s u r d o

    p o i c h e e c o n s i s t e n t e .

    i i i . ( ) ) D a ! 2 e 2 s e g u e c h e

    P

    0

    ! e

    P

    0

    ; p e r m o d u s

    p o n e n s , q u i n d i ,

    P

    0

    e q u i n d i , p e r i l p u n t o i , 2

    ( ( ) S e p e r a s s u r d o s i a v e s s e c h e d a 2 s e g u e 2 p e r e t a l i c h e

    ! 62 , p e r i l p u n t o i i s i a v r e b b e c h e : ( ! ) 2 ; p e r l e p r o p o s i z i o n i

    3 . 1 1 e 3 . 1 2 e p e r m o d u s p o n e n s s i a v r e b b e

    P

    0

    e

    P

    0

    : e , p e r i l p u n t o

    i 2 e : 2 ; m a p e r i p o t e s i d a 2 s e g u e 2 e q u i n d i , p e r i l p u n t o

    i i : 62 , a s s u r d o .

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    22/77

    1 8 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    L e m m a 3 . 3 ( d i s o d d i s f a c i b i l i t a ) D a t o u n i n s i e m e d i f b f i n P

    0

    s e e c o n s i -

    s t e n t e a l l o r a e s o d d i s f a c i b i l e .

    D i m o s t r a z i o n e : d a t o e s i s t e , p e r i l l e m m a d i L i n d e n b a u m , u n i n s i e m e

    d i f b f

    d i P

    0

    c o n s i s t e n t e e m a s s i m a l e t a l e c h e

    ; d e n i a m o B ( p ) = 1 p e r t u t t i e s o l i i

    s i m b o l i p r o p o s i z i o n a l i p 2

    ; d i m o s t r i a m o c h e B ( ) = 1 s e e s o l o s e 2

    ; q u e s t o

    i m p l i c h e r a l a t e s i :

    p c o n p s i m b o l o p r o p o s i z i o n a l e : p e r d e n i z i o n e s i a v r a B ( p ) = B ( p ) = 1 ;

    : 2

    s e e s o l o s e : 2

    s e e s o l o s e ( p u n t o i i d e l l a p r e c e d e n t e

    p r o p o s i z i o n e ) 62

    s e e s o l o s e ( i p o t e s i i n d u t t i v a , p o i c h e e p i u s e m p l i c e d i

    ) B ( ) = 0 ; q u i n d i B ( ) = 1 B ( ) = 1 ;

    ! 2

    s e e s o l o s e ! 2

    s e e s o l o s e ( p e r i l p u n t o i i i

    d e l l a p r e c e d e n t e p r o p o s i z i o n e ) d a 2

    s e g u e 2

    , s e e s o l o s e ( i p o t e s i

    i n d u t t i v a , p o i c h e e s o n o p i u s e m p l i c i d i ) d a B ( ) = 1 s e g u e B ( ) = 1 ,

    s e e s o l o s e B ( ! ) = 1 .

    T e o r e m a 3 . 6 ( d i c o m p l e t e z z a ) S i a u n i n s i e m e d i f b f d i P

    0

    e u n a f b f d i P

    0

    ;

    s i h a c h e :

    d a = s e g u e

    P

    0

    D i m o s t r a z i o n e : p e r c o n t r a p p o s i z i o n e , d i m o s t r i a m o c h e 6

    P

    0

    i m p l i c a 6 =

    S e i n f a t t i 6

    P

    0

    f : g e c o n s i s t e n t e ( t e o r e m a 3 . 3 ) ; p e r i l l e m m a d i s o d d i s f a c i -

    b i l i t a , q u i n d i , e s i s t e u n a s s e g n a m e n t o p r o p o s i z i o n a l e B p e r i l q u a l e B ( f : g ) = 1 ,

    o v v e r o B ( ) = 1 e B ( ) = 0 ; n e s e g u e c h e 6 =

    C o r o l l a r i o 3 . 4 S i a u n i n s i e m e d i f b f d i P

    0

    e u n a f b f d i P

    0

    ; s i h a c h e :

    = s e e s o l o s e

    P

    0

    D i m o s t r a z i o n e : d a i t e o r e m i d i c o r r e t t e z z a e c o m p l e t e z z a .

    C o r o l l a r i o 3 . 5 D a t a u n a f b f d i P

    0

    , e d e c i d i b i l e i l p r o b l e m a d i d i r e s e e u n

    t e o r e m a d i P

    0

    ( p r o b l e m a d e l l a d e c i s i o n e o E n t s c h e i d u n g s p r o b l e m ) .

    D i m o s t r a z i o n e : g r a z i e a l p r e c e d e n t e c o r o l l a r i o , i n f a t t i , e r i c o n d u c i b i l e a l p r o b l e m a

    d i d i r e s e e u n a t a u t o l o g i a , c h e e a s u a v o l t a d e c i d i b i l e ( t e o r e m a 3 . 4 ) .

    3 . 5 I t a b l e a u x p r o p o s i z i o n a l i

    S t u d i a m o a d e s s o u n s i s t e m a f o r m a l e c h e p e r m e t t e d i s e m p l i c a r e l e d e r i v a z i o n i d i

    P

    0

    ; c o m e s i s a r a n o t a t o , i n f a t t i , t a l i d e r i v a z i o n i s o n o i n g e n e r e l o n t a n e d a l n a t u r a l e

    m e c c a n i s m o m e n t a l e d e g l i e s s e r i u m a n i , i n q u a n t o v a n n o c o s t r u i t e a p a r t i r e d a u n

    i n s i e m e m i n i m o d i a s s i o m i e p r o s e g u e n d o i n m a n i e r a p o c o p r e v e d i b i l e d a u n o c c h i o

    i n e s p e r t o . C o n i t a b l e a u x p r o p o s i z i o n a l i a v r e m o i n v e c e u n s i s t e m a f o r m a l e l e c u i

    d e r i v a z i o n i s e g u o n o l o s c h e m a m e n t a l e d e g l i e s s e r i u m a n i , e l a c u i e s p r e s s i v i t a e

    d i m o s t r a b i l m e n t e e q u i v a l e n t e a q u e l l a d e l c a l c o l o p r o p o s i z i o n a l e , s e c i l i m i t i a m o a d

    i n s i e m i n i t i d i f b f d i P

    0

    N o n d e n i r e m o i t a b l e a u x p r o p o s i z i o n a l i c o m e u n v e r o e p r o p r i o s i s t e m a f o r m a l e ,

    i n q u a n t o l e s u e d e r i v a z i o n i p o s s o n o e s s e r e m e g l i o c o m p r e s e s e e s p r e s s e c o n u n

    f o r m a l i s m o b i d i m e n s i o n a l e p i u t t o s t o c h e l i n e a r e ; d e v e e s s e r c h i a r o , p e r o , c h e l a

    d e n i z i o n e p o t e v a e s s e r e d a t a i n m a n i e r a p i u a d e r e n t e a q u e l l a d i s i s t e m a f o r m a l e ,

    e c o n p o c h e m o d i c h e r i s p e t t o a q u e l l a c h e d a r e m o s o t t o .

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    23/77

    3 . 5 . I T A B L E A U X P R O P O S I Z I O N A L I 1 9

    D e n i z i o n e 3 . 7 U n t a b l e a u e u n a l b e r o o r i e n t a t o , n i t o e c o n n o d i e t i c h e t t a t i ; l e

    e t i c h e t t e s o n o i n s i e m i n i t i d i f b f d i P

    0

    ; l e f o g l i e s o n o d e t t e n o d i t e r m i n a l i ; u n r a m o

    e u n c a m m i n o r a d i c e { f o g l i a .

    D e n i z i o n e 3 . 8 U n t a b l e a u p r o p o s i z i o n a l e e u n t a b l e a u c o s t r u i t o t r a m i t e l e s e g u e n -

    t i r e g o l e :

    b a s e : s e e u n i n s i e m e n i t o d i f b f d i P

    0

    a l l o r a u n n o d o e t i c h e t t a t o c o n e

    u n t a b l e a u p r o p o s i z i o n a l e ;

    ! : d a t o u n t a b l e a u p r o p o s i z i o n a l e e u n s u o n o d o t e r m i n a l e n , s e n e l r a m o c u i

    a p p a r t i e n e t a l e n o d o c o m p a r e u n a f b f d e l t i p o ! , a l l o r a e u n t a b l e a u p r o -

    p o s i z i o n a l e a n c h e i l t a b l e a u o t t e n u t o a g g i u n g e n d o a l n o d o n d u e g l i e t i c h e t t a t i

    c o n : e :

    !

    n

    )

    P

    P

    PPq

    :

    : ! : d a t o u n t a b l e a u p r o p o s i z i o n a l e e u n s u o n o d o t e r m i n a l e n , s e n e l r a m o

    c u i a p p a r t i e n e t a l e n o d o c o m p a r e u n a f b f d e l t i p o : ( ! ) , a l l o r a e u n

    t a b l e a u p r o p o s i z i o n a l e a n c h e i l t a b l e a u o t t e n u t o a g g i u n g e n d o a l n o d o n u n

    g l i o e t i c h e t t a t o c o n : :

    : ( ! )

    n

    ?

    :

    : : : d a t o u n t a b l e a u p r o p o s i z i o n a l e e u n s u o n o d o t e r m i n a l e n , s e n e l r a m o c u i

    a p p a r t i e n e t a l e n o d o c o m p a r e u n a f b f d e l t i p o : : , a l l o r a e u n t a b l e a u p r o p o -

    s i z i o n a l e a n c h e i l t a b l e a u o t t e n u t o a g g i u n g e n d o a l n o d o n u n g l i o e t i c h e t t a t o

    c o n :

    : :

    n

    ?

    U n t a b l e a u p r o p o s i z i o n a l e e d e t t o e s s e r e u n t a b l e a u p r o p o s i z i o n a l e p e r s e e s o l o

    s e e l ' e t i c h e t t a d e l l a s u a r a d i c e .

    O s s e r v a z i o n e : g i a d a l l a d e n i z i o n e e e v i d e n t e c o m e i t a b l e a u x p r o p o s i z i o n a l i p e r -

    m e t t a n o d e r i v a z i o n i g o a l d i r e c t e d , a d i e r e n z a d i P

    0

    ; i n o l t r e , s e u t i l i z z o u n a s o l o

    v o l t a o g n i f b f , h o u n n u m e r o n i t o d i r e g o l e a p p l i c a b i l i a d o g n i p a s s o .

    E s e m p i o : u n t a b l e a u p r o p o s i z i o n a l e p e r p ! p

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    24/77

    2 0 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    p ! p

    )

    P

    P

    PPq

    : p p

    @@R @@R

    : p p : p p

    d a q u i p o t r e i p r o s e g u i r e a d l i b i t u m .

    D e n i z i o n e 3 . 9 I n u n t a b l e a u p r o p o s i z i o n a l e u n r a m o e d e t t o c h i u s o s e e s o l o s e

    f r a l e s u e e t i c h e t t e c o m p a i o n o p e : p p e r q u a l c h e v a r i a b i l e p r o p o s i z i o n a l e p ; d i r e m o

    a l l o r a c h e p e : p s o n o u s a t e p e r c h i u d e r e t a l e r a m o ; i n d i c h e r e m o u n r a m o c h i u s o

    c o n i l s i m b o l o

    J

    p o s t o s o t t o l a s u a f o g l i a . U n t a b l e a u p r o p o s i z i o n a l e e d e t t o c h i u s o ,

    o v v e r o e d e t t o e s s e r e u n a c o n f u t a z i o n e , s e e s o l o s e t u t t i i s u o i r a m i s o n o c h i u s i .

    D e n i z i o n e 3 . 1 0 U n i n s i e m e d i f b f d i P

    0

    e d e t t o c o n f u t a b i l e s e e s o l o s e e s i s t e

    u n t a b l e a u p r o p o s i z i o n a l e c h i u s o l a c u i r a d i c e e m a r c a t a c o n

    N o t a z i o n e : q u a n d o u s i a m o u n a f b f i n u n r a m o d i u n t a b l e a u p r o p o s i z i o n a l e ( c i o e

    l a u s i a m o s e c o n d o l e r e g o l e p r e c e d e n t e m e n t e e l e n c a t e p e r g i u s t i c a r e l a c o s t r u z i o n e

    i n d u t t i v a d e l l ' a l b e r o ) , m a r c h e r e m o t a l e f b f c o n i l s i m b o l o

    p

    O s s e r v a z i o n e : q u a n d o s i u s a u n a f b f e b e n e u s a r l a o v u n q u e s e r v a e n o n u s a r l a

    p i u ( e u n c r i t e r i o p e r m a n t e n e r e o r d i n a t e l e d e r i v a z i o n i f a t t e t r a m i t e i t a b l e a u x

    p r o p o s i z i o n a l i ) .

    P r o p o s i z i o n e 3 . 1 7 : A k , i s t a n z i a t o c o n v a r i a b i l i p r o p o s i z i o n a l i , e c o n f u t a b i l e .

    D i m o s t r a z i o n e :

    : ( p ! ( q ! p ) )

    p

    p : ( q ! p )

    p

    q : p

    J

    P r o p o s i z i o n e 3 . 1 8 : A S , i s t a n z i a t o c o n v a r i a b i l i p r o p o s i z i o n a l i , e c o n f u t a b i l e .

    D i m o s t r a z i o n e :

    : ( ( p ! ( q ! r ) ) ! ( ( p ! q ) ! ( p ! r ) ) )

    p

    p ! ( q ! r )

    p

    : ( ( p ! q ) ! ( p ! r ) )

    p

    p ! q

    p

    : ( p ! r )

    p

    p : r

    )

    P

    P

    PPq

    : p q ! r

    J

    )

    P

    P

    PPq

    : q r

    )

    P

    P

    PPq

    J

    : p q

    J J

    P r o p o s i z i o n e 3 . 1 9 : A : , i s t a n z i a t o c o n v a r i a b i l i p r o p o s i z i o n a l i , e c o n f u t a b i l e .

    D i m o s t r a z i o n e :

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    25/77

    3 . 5 . I T A B L E A U X P R O P O S I Z I O N A L I 2 1

    : ( ( : p ! q ) ! ( ( : p ! : q ) ! p ) )

    p

    : p ! q

    p

    : ( ( : p ! : q ) ! p )

    p

    : p ! : q : p

    )

    P

    P

    PPq

    : : p q

    p

    H

    HHj

    J

    : : p : q

    J J

    L e m m a 3 . 4 S e u n a s s e g n a m e n t o p r o p o s i z i o n a l e B s o d d i s f a t u t t e l e f b f d i u n r a m o

    d i u n t a b l e a u p r o p o s i z i o n a l e a l l o r a B s o d d i s f a t u t t e l e f b f :

    1 . d e l n u o v o r a m o o t t e n u t o d a l p r e c e d e n t e c o n l ' a p p l i c a z i o n e d i u n a d e l l e r e g o l e

    : : e : ! ;

    2 . d i a l m e n o u n o d e i d u e r a m i o t t e n u t i d a l p r e c e d e n t e c o n l ' a p p l i c a z i o n e d e l l a

    r e g o l a !

    D i m o s t r a z i o n e :

    1 . P e r l a r e g o l a : :

    : :

    s o c h e 1 = B ( : : ) = 1 B ( : ) = 1 1 + B ( ) , q u i n d i d e v e e s s e r e B ( ) = 1 .

    P e r l a r e g o l a : !

    : ( ! )

    :

    s o c h e 1 = B ( : ( ! ) ) = 1 B ( ! ) =

    8

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    26/77

    2 2 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    L e m m a 3 . 5 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    ; s e e c o n f u t a b i l e a l l o r a n o n e

    s o d d i s f a c i b i l e .

    D i m o s t r a z i o n e : s i a d a t o u n t a b l e a u p r o p o s i z i o n a l e d i c o n f u t a z i o n e p e r ; s e p e r

    a s s u r d o f o s s e s o d d i s f a c i b i l e , p e r i l l e m m a p r e c e d e n t e e s i s t e r e b b e u n a s s e g n a m e n t o

    p r o p o s i z i o n a l e B c h e r e n d e v e r e t u t t e l e f b f d i u n r a m o d i t a l e t a b l e a u ; m a p o i c h e i l

    t a b l e a u e d i c o n f u t a z i o n e , i n o g n i r a m o e p r e s e n t e p e : p p e r u n ' o p p o r t u n a v a r i a b i l e

    p r o p o s i z i o n a l e p ; q u i n d i s i d o v r e b b e a v e r e : 1 = B ( p ) = B ( : p ) , i l c h e e a s s u r d o .

    T e o r e m a 3 . 7 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e u n a f b f d i P

    0

    ; s e f : g e

    c o n f u t a b i l e a l l o r a =

    D i m o s t r a z i o n e : p e r c o n t r a p p o s i z i o n e b a s t a m o s t r a r e c h e s e 6 = a l l o r a f : g

    n o n e c o n f u t a b i l e ; a t a l n e , g r a z i e a l l e m m a p r e c e d e n t e , p e r c o n t r a p p o s i z i o n e , b a s t a

    m o s t r a r e c h e s e 6 = a l l o r a f : g e s o d d i s f a c i b i l e . Q u e s t ' u l t i m a i m p l i c a z i o n e e

    c h i a r a m e n t e v e r a : s e 6 = a l l o r a e s i s t e u n a s s e g n a m e n t o p r o p o s i z i o n a l e B t a l e c h e

    B ( ) = 1 m a B ( ) = 0 , o v v e r o B ( : ) = 1 ; q u i n d i B ( f : g ) = 1 , o v v e r o f : g

    e s o d d i s f a c i b i l e .

    D e n i z i o n e 3 . 1 1 P o s s i a m o i n t r o d u r r e l e s e g u e n t i r e g o l e d e r i v a t e :

    _ :

    _

    )

    P

    P

    PPq

    p o i c h e :

    _ : !

    )

    P

    P

    PPq

    : :

    : _ :

    : ( _ ) : ( : ! ) )

    : :

    :

    p o i c h e :

    : ( : _ : )

    : : : :

    : :

    : ( )

    )

    P

    P

    PPq

    : :

    p o i c h e :

    : ( ) : : ( : _ : )

    : _ :

    )

    P

    P

    PPq

    : :

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    27/77

    3 . 5 . I T A B L E A U X P R O P O S I Z I O N A L I 2 3

    E s e m p i o : u n a d e r i v a z i o n e t r a m i t e q u e s t e r e g o l e d e r i v a t e :

    : ( ( ! ( _ ) ) ! ( ! ) _ ( ! ) )

    p

    ! ( _ )

    p

    : ( ( ! ) _ ( ! ) )

    p

    : ( ! )

    p

    : ( ! )

    :

    :

    )

    P

    P

    PPq

    : _

    J

    H

    HHj

    J J

    D e n i z i o n e 3 . 1 2 U n r a m o d i u n t a b l e a u p r o p o s i z i o n a l e c h e t e r m i n a c o n u n a f o g l i a

    e t i c h e t t a t a c o n u n i n s i e m e d i f b f c o n f u t a b i l e , e d e t t o e s s e r e c o m e s e f o s s e c h i u s o ( a s

    g o o d a s c l o s e d ) .

    P r o p o s i z i o n e 3 . 2 0 S e u n r a m o d i u n t a b l e a u p r o p o s i z i o n a l e c o n t i e n e , f r a l e e t i c h e t -

    t e d e i s u o i n o d i , e : p e r u n a o p p o r t u n a f b f d i P

    0

    , q u e l r a m o e c o m e s e f o s s e

    c h i u s o .

    D i m o s t r a z i o n e : p e r i n d u z i o n e s u l l a s t r u t t u r a d i

    p , c o n p v a r i a b i l e p r o p o s i z i o n a l e : i l r a m o e c h i u s o e , q u i n d i , a n c h e c o m e

    s e f o s s e c h i u s o ;

    : : i l r a m o c o n t i e n e c i o e : e : : ; q u i n d i p o s s o e s p a n d e r l o , t r a m i t e l a

    r e g o l a : : , i n m o d o d a o t t e n e r e ; e s s o c o n t i e n e e : e q u i n d i , p e r i p o t e s i

    i n d u t t i v a , e c o m e s e f o s s e c h i u s o ;

    ! : p o s s o e s t e n d e r e f a c i l m e n t e i l r a m o :

    !

    : ( ! ) :

    ( i l r a m o n i v a q u i )

    :

    )

    P

    P

    PPq

    :

    J J

    P o s s o c o n s i d e r a r e i l r a m o c h i u s o p o i c h e , p e r i p o t e s i i n d u t t i v a , e p e r m e t t o n o

    d i c h i u d e r e u n r a m o i n c u i s o n o p r e s e n t i s i a p o s i t i v a m e n t e c h e n e g a t i v a m e n t e .

    D e n i z i o n e 3 . 1 3 I n t r o d u c i a m o l a r e g o l a d e l t e r z o e s c l u s o ( T E o E M ) p e r i t a b l e a u x

    p r o p o s i z i o n a l i :

    )

    P

    P

    PPq

    :

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    28/77

    2 4 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    L e m m a 3 . 6 S i a n o e d u e i n s i e m i n i t i d i f b f d i P

    0

    ; s e e c o n f u t a b i l e a n c h e

    e c o n f u t a b i l e .

    D i m o s t r a z i o n e : p o s s o u s a r e l a s t e s s a c o n f u t a z i o n e c h e h o p e r , s e n z a s f r u t t a r e

    l e i p o t e s i a g g i u n t i v e i n .

    L e m m a 3 . 7 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e u n a f b f d i P

    0

    ; s e : : e

    c o n f u t a b i l e a n c h e e c o n f u t a b i l e .

    D i m o s t r a z i o n e : S e n e l l a r e f u t a z i o n e d i : : n o n h o u t i l i z z a t o : : i l r i s u l t a t o

    e o v v i o ; a l t r i m e n t i l ' u n i c o m o d o i n c u i p o s s o a v e r e u t i l i z z a t o t a l e f b f e t r a m i t e l a

    r e g o l a : : ; o t t e n g o u n a r e f u t a z i o n e d i t r a s f o r m a n d o l a r e f u t a z i o n e d i : : n e l

    m o d o s e g u e n t e :

    n

    ( q u i h o a p p l i c a t o l a r e g o l a : : a : : )

    B

    B

    BB

    d i v e n t a :

    n

    B

    B

    BB

    L e m m a 3 . 8 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e d u e f b f d i P

    0

    ; s e !

    e c o n f u t a b i l e a n c h e : e s o n o c o n f u t a b i l i .

    D i m o s t r a z i o n e : S e n e l l a c o n f u t a z i o n e d i ! n o n h o m a i u t i l i z z a t o ! i l

    r i s u l t a t o e o v v i o ; a l t r i m e n t i l ' u n i c a r e g o l a c h e p o s s o a v e r a p p l i c a t o a d ! e q u e l l a

    d e l l ' ! ; o t t e n g o u n a r e f u t a z i o n e d i : a p a r t i r e d a q u e l l a d i ! s o s t i t u e n d o

    l ' e t i c h e t t a d i t a l e a l b e r o c o n : e d e s e g u e n d o l a s e g u e n t e t r a s f o r m a z i o n e :

    ( q u i h o a p p l i c a t o l a r e g o l a d e l l ' ! a d ! )

    )

    P

    P

    PPq

    :

    B

    B

    BB

    B

    B

    BB

    d i v e n t a :

    B

    B

    BB

    O t t e n g o u n a r e f u t a z i o n e d i a p a r t i r e d a q u e l l a d i ! s o s t i t u e n d o

    l ' e t i c h e t t a d i t a l e a l b e r o c o n e d e s e g u e n d o l a s e g u e n t e t r a s f o r m a z i o n e :

    ( q u i h o a p p l i c a t o l a r e g o l a d e l l ' ! a d ! )

    )

    P

    P

    PPq

    :

    B

    B

    BB

    B

    B

    BB

    d i v e n t a :

    B

    B

    BB

    L e m m a 3 . 9 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e f b f d i P

    0

    ; s e : ( ! )

    e c o n f u t a b i l e a n c h e : e c o n f u t a b i l e .

    D i m o s t r a z i o n e : s e n e l l a c o n f u t a z i o n e d i : ( ! ) n o n h o m a i u t i l i z z a t o : ( !

    ) i l r i s u l t a t o e o v v i o ; a l t r i m e n t i l ' u n i c a r e g o l a c h e p o s s o a v e r a p p l i c a t o a l l a f b f

    : ( ! ) e q u e l l a d e l : ! ; o t t e n g o u n a r e f u t a z i o n e d i : d a q u e l l a d i

    : ( ! ) s o s t i t u e n d o l a r a d i c e d i t a l e a l b e r o c o n : e d e e t t u a n d o l a

    s e g u e n t e t r a s f o r m a z i o n e :

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    29/77

    3 . 5 . I T A B L E A U X P R O P O S I Z I O N A L I 2 5

    ( q u i h o a p p l i c a t o l a r e g o l a d e l : ! a : ( ! ) )

    :

    B

    B

    BB

    d i v e n t a :

    B

    B

    BB

    L e m m a 3 . 1 0 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e p u n a v a r i a b i l e p r o p o s i z i o n a l e ;

    s e s i a p c h e : p s o n o c o n f u t a b i l i a n c h e e c o n f u t a b i l e .

    D i m o s t r a z i o n e : s e n o n u s i a m o p n e l l a c o n f u t a z i o n e d i p o n o n u s i a m o : p n e l l a

    c o n f u t a z i o n e d i : p i l r i s u l t a t o e o v v i o ; s u p p o n i a m o q u i n d i d i u s a r l i e n t r a m b i ;

    l ' u n i c a p o s s i b i l i t a e q u e l l a d i a v e r l i u s a t i p e r c h i u d e r e a l c u n i r a m i ; q u i n d i n e l l a

    r e f u t a z i o n e d i p h o a l m e n o u n a i s t a n z a d i : p e n e l l a r e f u t a z i o n e d i : p h o a l m e n o

    u n a i s t a n z a d i p . S e d a l l e r a d i c i d i t a l i r e f u t a z i o n i e l i m i n o p o , r i s p e t t i v a m e n t e ,

    : p , o t t e n g o d e i t a b l e a u x p r o p o s i z i o n a l i n o n p i u c h i u s i , m a i c u i u n i c i r a m i a p e r t i

    t e r m i n a n o c o n : p o , r i s p e t t i v a m e n t e , c o n p

    B

    B

    BB

    : p : : : : p

    e

    B

    B

    BB

    p : : : p

    O t t e n g o q u i n d i u n a c o n f u t a z i o n e d i a p p l i c a n d o i l s e c o n d o t a b l e a u a l l e f o g l i e

    c h e t e r m i n a n o c o n : p d e l p r i m o .

    L e m m a 3 . 1 1 ( d i e l i m i n a z i o n e ) S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e u n a f b f

    d i P

    0

    ; s e s i a c h e : s o n o c o n f u t a b i l i a n c h e e c o n f u t a b i l e .

    D i m o s t r a z i o n e : p e r i n d u z i o n e s u l l a s t r u t t u r a d i

    p c o n p v a r i a b i l e p r o p o s i z i o n a l e : d i r e t t a m e n t e d a l l e m m a p r e c e d e n t e ;

    : : s o c h e : e : : s o n o c o n f u t a b i l i ; p e r i l l e m m a 3 . 7 a n c h e

    e c o n f u t a b i l e e p e r i p o t e s i i n d u t t i v a e c o n f u t a b i l e ;

    ! : s o c h e ! e : ( ! ) s o n o c o n f u t a b i l i ; q u i n d i :

    ! c o n f u t a b i l e

    + : ( ! )

    ( l e m m a 3 . 8 ) c o n f u t a b i l e

    c o n f u t a b i l e +

    + ( l e m m a 3 . 9 )

    ( l e m m a 3 . 6 ) :

    ; ; c o n f u t a b i l e c o n f u t a b i l e

    | { z }

    +

    ( i p o t e s i i n d u t t i v a )

    c o n f u t a b i l e

    !

    c o n f u t a b i l e

    +

    ( l e m m a 3 . 8 )

    :

    c o n f u t a b i l e

    | { z }

    +

    ( i p o t e s i i n d u t t i v a )

    c o n f u t a b i l e .

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    30/77

    2 6 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

    T e o r e m a 3 . 8 E M e u n a r e g o l a a m m i s s i b i l e : d a t o u n i n s i e m e n i t o d i f b f d i P

    0

    s e e s i s t e u n a r e f u t a z i o n e d i c h e u t i l i z z a l a r e g o l a E M a l l o r a e s i s t e u n a r e f u t a z i o n e

    d i c h e n o n u t i l i z z a l a r e g o l a E M

    D i m o s t r a z i o n e : s i a d a t a u n a r e f u t a z i o n e d i c h e u t i l i z z a l a r e g o l a E M ; s i a k i l

    l i v e l l o m a s s i m a l e d i a p p l i c a z i o n e d i t a l e r e g o l a :

    ( l i v e l l o k )

    )

    P

    P

    PPq

    :

    B

    B

    BB

    B

    B

    BB

    S i a l ' i n s i e m e d e l l e f b f p r e s e n t i s u l r a m o c h e d a l l a r a d i c e a r r i v a a q u e s t a a p p l i -

    c a z i o n e d e l l a r e g o l a E M ; p e r d e n i z i o n e d i k , p o s s o c o s t r u i r e u n a c o n f u t a z i o n e d i

    e : s e n z a u s a r e l a r e g o l a E M : b a s t a e t i c h e t t a r e i s o t t o a l b e r i s o p r a r a p p r e -

    s e n t a t i r i s p e t t i v a m e n t e c o n e : . P e r i l l e m m a d i e l i m i n a z i o n e , q u i n d i , e s i s t e

    u n a l b e r o d i r e f u t a z i o n e d i c h e n o n u t i l i z z a l a r e g o l a E M ; a p p l i c a n d o t a l e a l b e r o

    n e l n o d o i n c u i s i e e t t u a v a l a p r e c e d e n t e a p p l i c a z i o n e d e l l a r e g o l a E M , o t t e n g o

    u n a n u o v a r e f u t a z i o n e d i c h e u t i l i z z a u n n u m e r o d i v o l t e s t r e t t a m e n t e i n f e r i o r e l a

    r e g o l a E M r i s p e t t o a l l a r e f u t a z i o n e c h e a v e v a m o p e r i p o t e s i ; r i a p p l i c o i l p r o c e d i -

    m e n t o i t e r a t i v a m e n t e n c h e , p o i c h e l ' a l b e r o d i r e f u t a z i o n e o r i g i n a r i o d i e n i t o e

    c o n t i e n e q u i n d i u n n u m e r o n i t o d i a p p l i c a z i o n i d e l l a r e g o l a E M , n o n o t t e r r o u n a

    r e f u t a z i o n e d i c h e n o n u t i l i z z a l a r e g o l a E M

    O s s e r v a z i o n e : E M n o n e c h i a r a m e n t e u n a r e g o l a d e r i v a t a .

    T e o r e m a 3 . 9 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e u n a f b f d i P

    0

    S e

    P

    0

    a l l o r a : e c o n f u t a b i l e .

    D i m o s t r a z i o n e : p e r i n d u z i o n e s u l l a l u n g h e z z a d e l l a d e r i v a z i o n e

    1

    ; : : : ;

    n

    c o n

    n

    n = 1 : s i d a n n o d u e c a s i :

    1 e u n a s s i o m a : p e r l e p r o p o s i z i o n i 3 . 1 7 , 3 . 1 8 e 3 . 1 9 , t u t t i g l i a s s i o -

    m i i s t a n z i a t i c o n v a r i a b i l i p r o p o s i z i o n a l i s o n o r e f u t a b i l i ; g r a z i e a l l a p r o -

    p o s i z i o n e 3 . 2 0 o t t e n i a m o i l r i s u l t a t o a n c h e s e e s s i n o n s o n o i s t a n z i a t i

    s o l a m e n t e c o n v a r i a b i l i p r o p o s i z i o n a l i .

    2 2 : q u i n d i : c o n t i e n e e : e d e f a c i l m e n t e c o n f u t a b i l e t r a m i t e

    l a r e g o l a E M

    :

    ( u t i l i z z o l a r e g o l a E M )

    )

    P

    P

    PPq

    :

    J J

    P e r i l t e o r e m a 3 . 8 , : e c o n f u t a b i l e a n c h e s e n z a u t i l i z z a r e l a r e g o l a

    E M

    n > 1 : s e

    n

    e u n a s s i o m a o u n ' i p o t e s i i n l a d i m o s t r a z i o n e p r o s e g u e c o m e

    n e l c a s o b a s e ; a l t r i m e n t i

    n

    e o t t e n u t a p e r m o d u s p o n e n s d a

    i

    e

    j

    i ; j < n

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    31/77

    3 . 5 . I T A B L E A U X P R O P O S I Z I O N A L I 2 7

    i

    !

    n

    j

    i

    n

    . P e r i p o t e s i i n d u t t i v a :

    i

    e :

    j

    s o n o c o n f u t a b i l i ; i n d i c o

    t a l i a l b e r i d i r e f u t a z i o n e r i s p e t t i v a m e n t e c o n

    B

    B

    BB e

    B

    B

    BB . C o s t r u i s c o q u i n d i

    u n a r e f u t a z i o n e d i :

    n

    c h e u t i l i z z a l a r e g o l a E M

    :

    n

    ( u t i l i z z o l a r e g o l a E M )

    )

    P

    P

    PPq

    i

    !

    n

    : (

    i

    !

    n

    ) :

    j

    H

    HHj

    :

    i

    n

    B

    B

    BB

    J

    B

    B

    BB

    P e r i l t e o r e m a 3 . 8 s o c h e e s i s t e u n a c o n f u t a z i o n e d i :

    n

    c h e n o n u s a l a

    r e g o l a E M , e q u i n d i i l t e o r e m a e d i m o s t r a t o .

    C o r o l l a r i o 3 . 6 S i a u n i n s i e m e n i t o d i f b f d i P

    0

    e u n a f b f d i P

    0

    ; s i h a c h e :

    P

    0

    s e e s o l o s e = s e e s o l o s e : e c o n f u t a b i l e

    D i m o s t r a z i o n e : d i r e t t a m e n t e d a l l a c o r r e t t e z z a e c o m p l e t e z z a d i P

    0

    e d a i t e o r e m i

    3 . 7 e 3 . 9 .

    P r o p o s i z i o n e 3 . 2 1 S i a n o e d u e f b f d i P

    0

    ; s i h a : :

    P

    0

    : ( ! )

    D i m o s t r a z i o n e : G r a z i e a l c o r o l l a r i o p r e c e d e n t e , b a s t a m o s t r a r e c h e : : : ( !

    ) e c o n f u t a b i l e :

    : : : ( ! )

    !

    )

    P

    P

    PPq

    :

    J J

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    32/77

    2 8 C A P I T O L O 3 . I L C A L C O L O P R O P O S I Z I O N A L E

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    33/77

    C a p i t o l o 4

    I l c a l c o l o d e i p r e d i c a t i

    N e l c a l c o l o p r o p o s i z i o n a l e n o n s i a m o c a p a c i d i e s p r i m e r e u n a r e l a z i o n e f r a p i u p r o -

    p o s i z i o n i : s e v o g l i o d i r e c h e i l s u c c e s s o r e d i u n n u m e r o p a r i e u n n u m e r o d i s p a r i

    p o s s o a l p i u s c r i v e r e : p a r i x ! d i s p a r i x + 1 , m a s i a m o b e n l o n t a n i d a q u e l c h e

    v o r r e m m o e s p r i m e r e ; i n o l t r e n o n p o s s o i n d i c a r e e s i s t e n z a o u n i v e r s a l i t a ; e b e n g i u -

    s t i c a t a , q u i n d i , l a r i c h i e s t a d i s t u d i a r e u n n u o v o s i s t e m a f o r m a l e , c h e s i a u n c a l c o l o

    p i u p o t e n t e d i P

    0

    ; q u e s t o c a l c o l o s a r a i l c a l c o l o d e i p r e d i c a t i .

    4 . 1 I l l i n g u a g g i o d e i p r e d i c a t i

    D e n i z i o n e 4 . 1 U n a s e g n a t u r a e u n a c o p p i a f o r m a t a d a u n i n s i e m e d i s i m b o l i d i

    f u n z i o n e e u n i n s i e m e d i s i m b o l i d i p r e d i c a t o .

    N o t a z i o n e : a g g i u n g i a m o u n e s p o n e n t e i n t e r o a d o g n i s i m b o l o d i f u n z i o n e o d i p r e -

    d i c a t o q u a n d o v o g l i a m o s p e c i c a r n e l ' a r i t a ; q u a l o r a e s s a r i s u l t i c h i a r a d a l c o n t e s t o

    e v i t e r e m o t a l e a p p e s a n t i m e n t o s i n t a t t i c o .

    E s e m p i o :

    P O

    = f ; f

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    34/77

    3 0 C A P I T O L O 4 . I L C A L C O L O D E I P R E D I C A T I

    { i c o n n e t t i v i p r o p o s i z i o n a l i : e ! ;

    { u n s i m b o l o d i q u a n t i c a z i o n e u n i v e r s a l e : 8 ;

    { d u e s i m b o l i a u s i l i a r i : ( e ) ;

    { e v e n t u a l m e n t e , u n s i m b o l o d i u g u a g l i a n z a : = ; s e e s s o e p r e s e n t e , i l

    l i n g u a g g i o e d e t t o e s s e r e c o n u g u a g l i a n z a .

    S i n o t i c h e t u t t i i p r e c e d e n t i i n s i e m i d e v o n o e s s e r e d e c i d i b i l i e d i s t i n t i .

    i n s i e m e d e l l e f b f : W F b f

    d o v e F b f

    e c o s d e n i t o :

    { s e t

    1

    ; : : : ; t

    n

    2 T e r m

    e P

    n

    e u n s i m b o l o d i p r e d i c a t o n - a r i o d i , a l l o r a

    P ( t

    1

    ; : : : ; t

    n

    ) 2 F b f

    ( f b f a t o m i c h e ) ;

    { s e 2 F b f

    a l l o r a ! 2 F b f

    e : 2 F b f

    ;

    { s e 2 F b f

    e x e u n a v a r i a b i l e i n d i v i d u a l e , a l l o r a ( 8 x ) 2 F b f

    ;

    { s e i l l i n g u a g g i o e u n l i n g u a g g i o c o n u g u a g l i a n z a e t

    1

    t

    2

    2 T e r m

    a l l o r a

    t

    1

    = t

    2

    2 F b f

    ( e q u a z i o n i : a n c h ' e s s e f a n n o p a r t e d e l l e f b f a t o m i c h e ) ;

    { n i e n t ' a l t r o e i n F b f

    L a p o r t a t a d i u n q u a n t i c a t o r e d e l t i p o : 8 x e l a f b f

    E s e m p i o : F b f

    P O

    c o n t i e n e l e s e g u e n t i f b f :

    : (

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    35/77

    4 . 1 . I L L I N G U A G G I O D E I P R E D I C A T I 3 1

    N o t a z i o n e : d ' o r a i n p o i e v i t e r e m o d i s p e c i c a r e l a s t r u t t u r a e i l l i n g u a g g i o d e i

    p r e d i c a t i a c u i c i r i f e r i a m o , q u a n d o e s s i r i s u l t e r a n n o c h i a r i d a l c o n t e s t o .

    D e n i z i o n e 4 . 7 U n ' i n t e r p r e t a z i o n e p e r t e r m i n i s u u n a s t r u t t u r a A

    e u n a f u n z i o -

    n e :

    ] ]

    A

    T e r m

    E N V

    A

    ! j A

    t a l e c h e :

    1 x = ( x ) p e r o g n i x 2 v a r i a b i l i i n d i v i d u a l i

    L

    ;

    2 f

    n

    ( t

    1

    ; : : : ; t

    n

    ) =

    ~

    f

    n

    ( t

    1

    ; : : : ; t

    n

    ) p e r o g n i t

    1

    ; : : : ; t

    n

    2 T e r m

    D e n i z i o n e 4 . 8 U n ' i n t e r p r e t a z i o n e p e r f b f s u u n a s t r u t t u r a A

    e u n a f u n z i o n e :

    ] ]

    A

    F b f

    E N V

    A

    ! f 0 1 g

    t a l e c h e :

    1 P

    n

    ( t

    1

    ; : : : ; t

    n

    ) =

    ~

    P

    n

    ( t

    1

    ; : : : ; t

    n

    ) ;

    2 ! = 1 s e e s o l o s e d a = 1 s e g u e = 1 ;

    3 : = 1 s e e s o l o s e = 0 ;

    4 8 x = 1 s e e s o l o s e p e r o g n i a 2 A

    s i h a

    a

    x

    = 1 ; d o v e

    a

    x

    2 E N V

    A

    e c o s d e n i t o :

    a

    x

    ( y ) =

    ( y ) s e x 6 y

    a a l t r i m e n t i ;

    5 . ( s e i l l i n g u a g g i o e c o n u g u a g l i a n z a ) t = t = 1 s e e s o l o s e t e t

    s o n o l o s t e s s o e l e m e n t o d i A

    D e n i z i o n e 4 . 9 S i a 2 F b f

    e A

    u n a s t r u t t u r a ; d i r e m o c h e :

    i e s o d d i s f a c i b i l e i n A

    s e e s o l o s e e s i s t e 2 E N V

    A

    p e r c u i s i a b b i a

    = 1 ;

    i i e v e r a i n A

    ( o v v e r o e v a l i d a i n A

    ) s e e s o l o s e p e r o g n i 2 E N V

    A

    s i h a = 1 ; s c r i v e r e m o a l l o r a A

    = ; c h i a m e r e m o t e o r i a d i A

    S

    i g m a

    l ' i n s i e m e : T h ( A

    ) = f A

    = g ;

    i i i . e s o d d i s f a c i b i l e s e e s o l o s e e s i s t e u n a s t r u t t u r a A

    c h e s o d d i s f a ;

    i v e v a l i d a ( o v e r a ) s e e s o l o s e p e r o g n i s t r u t t u r a A

    s i h a A

    = ;

    v e c o n t r a d d i t t o r i a s e e s o l o s e n o n e s o d d i s f a c i b i l e .

    O s s e r v a z i o n e : s i a 2 F b f

    s e n o n e s o d d i s f a c i b i l e e c o n t r a d d i t t o r i a e v i c e v e r -

    s a ; s e e v a l i d a a l l o r a e s o d d i s f a c i b i l e .

    D e n i z i o n e 4 . 1 0 S i a F b f

    e A

    u n a s t r u t t u r a ; A

    e d e t t a e s s e r e u n m o d e l l o

    d i s e e s o l o s e o g n i 2 e v e r a i n A

    , o v v e r o s e e s o l o s e p e r o g n i 2 s i h a

    A

    = . S c r i v e r e m o a l l o r a : A

    =

    D e n i z i o n e 4 . 1 1 I n t r o d u c i a m o l a s e g u e n t e d e n i z i o n e e s p l i c i t a :

    ( 9 x ) : ( 8 x : )

  • 7/27/2019 Matematica Logica Appunti Del Corso Di Logica Matematica Martini

    36/77

    3 2 C A P I T O L O 4 . I L C A L C O L O D E I P R E D I C A T I

    P r o p o s i z i o n e 4 . 1 S i a A

    u n a s t r u t t u r a ; A

    = 9 x s e e s o l o s e p e r o g n i 2

    E N V

    A

    e s i s t e a 2 A

    t a l e c h e

    a

    x

    = 1 ; a e d e t t o t e s t i m o n e d e l l ' e s i s t e n z i a l e .

    D i m o s t r a z i o n e : A

    = 9 x s e e s o l o s e A

    = : ( 8 x : ) , s e e s o l o s e p e r o g n i

    2 E N V

    A

    s i h a : ( 8 x : ) = 1 , s e e s o l o s e p e r o g n i 2 E N V

    A

    s i h a

    8 x : ] ] = 0 , s e e s o l o s e p e r o g n i 2 E N V

    A

    e s i s t e a 2 A

    t a l e c h e :

    a

    x

    = 0

    s e e s o l o s e p e r o g n i 2 E N V

    A

    e s i s t e a 2 A

    t a l e c h e

    a

    x

    = 1

    D e n i z i o n e 4 . 1 2 S i a F b f

    e s i a 2 F b f

    ; d i r e m o c h e :

    e c o n s e g u e n z a l o g i c a d i s e e s o l o s e p e r o g n i s t r u t t u r a A

    e p e r o g n i

    2 E N V

    A

    d a ] ] = 1 s e g u e