• Non ci sono risultati.

Logica  Proposizionale   ¬ ~ ⇒ ∧ ∨ ⇔ a ~ ~, ~ g a g ∧ , ∨ , ⇒ , ⇔ () () ()= ()= ()= () () {} {} {} {} Τ ⊥ A f f f f f ∨ g , f ∧ g , f ⇒ g , f ⇔ g ~ stfmf stfmf stfmf A ∧ B ⇔ A f f A ∪ ∪ ⇒ stfmg g B ∨ A ∪ stfmh g ∧ hg ⎧⎨⎪⎪⎩⎪⎪ ∨ hg ⇒ hg ⇔ h

N/A
N/A
Protected

Academic year: 2021

Condividi "Logica  Proposizionale   ¬ ~ ⇒ ∧ ∨ ⇔ a ~ ~, ~ g a g ∧ , ∨ , ⇒ , ⇔ () () ()= ()= ()= () () {} {} {} {} Τ ⊥ A f f f f f ∨ g , f ∧ g , f ⇒ g , f ⇔ g ~ stfmf stfmf stfmf A ∧ B ⇔ A f f A ∪ ∪ ⇒ stfmg g B ∨ A ∪ stfmh g ∧ hg ⎧⎨⎪⎪⎩⎪⎪ ∨ hg ⇒ hg ⇔ h"

Copied!
6
0
0

Testo completo

(1)

Logica  Proposizionale  

µ Definizioni:  

Ø Proposizione:  enunciato  che  si  può  dire  se  è  vero  o  falso  in  modo  univoco.  Si  dice  atomica  se  è   formato  solo  da  un  oggetto  oppure  composta  se  è  formato  da  più  proposizioni  atomiche.  

 

µ Sintassi:  

Ø

Connettivi:  

§ NOT:  

~

,  ¬  

§ AND:  

.  

§ OR:  

.  

§ Implica:  

.  

§ Se  e  solo  se:  

.   Ø

Alfabeto:  

§ Lettere  enunciative:  A,  B,  C,…  

§ Connettivi.  

§ Simboli  ausiliari:  

( )

,  

 falso,  

Τ

 vero.  

Ø

Formule  ben  formate  (f.b.f.):  

§ Le  lettere  enunciative  sono  f.b.f.  

§ Se  

a

 è  una  f.b.f.  allora  lo  sarà  anche  

~ a

.  

§ Se  

f

 e  

g

 sono  f.b.f  allora  anche  

f ∨ g, f ∧ g, f ⇒ g, f ⇔ g

 lo  sono.  

§ Nient’altro  è  una  f.b.f.  

Ø

Precedenza  dei  connettivi:  

§

~, ∧,∨,⇒,⇔

.  

Ø

Creazione  sottoformule  (stfm):  

§ Se  

f

 è  una  lettera  enunciativa  

A

,  allora  

stfm f ( ) = A { }

.  

§ Se  

f

 è  

~ g

 allora  

stfm f ( ) = f { } ∪ g { }

.  

§ Se  

f

 è  

g ∧ h g ∨ h g ⇒ h g ⇔ h

⎨ ⎪⎪

⎪ ⎪

,  allora  

stfm f ( ) = f { } ∪ stfm g ( ) ∪ stfm h ( )

.  

Ø Albero  di  struttura:  si  individua  il  connettivo  principale  (ossia  quello  che  mettiamo  per  ultimo),   esso  sarà  la  radice,  poi  ci  si  allontana  seguendo  la  precedenza  dei  connettivi  e  delle  eventuali   parentesi.  

§ Esempio:  l’albero  di  struttura  della  formula  

~ A ( ∧ B ) ⇔ A ⇒ B ∨ A

 è  

     

(2)

µ Semantica:  

Ø

Interpretazione:

 sia  

ν : f .b.f { } → 0,1 { }

 una  funzione  che  associa  ad  una  f.b.m.  un  valore  

{ } 0,1

  e  sia  

f , g

 f.b.m.  

§

ν ⊥ ( ) = 0

.  

§

ν Τ ( ) = 1

.  

§

ν ~ f ( ) = 1− ν f ( )

.  

§

ν (

f ∧ g

)

= min

{ ν ( )

f ,

ν ( )

g

}

.  

§

ν (

f ∨ g

)

= max

{ ν ( )

f ,

ν ( )

g

}

.  

§

ν (

f ⇒ g

)

= max 1−

{ ν ( )

f ,

ν ( )

g

}

.  

§

ν f ⇔ g ( ) = min max 1− { { ν f ( ) , g } , max f ,1 { ν g ( ) } }

.  

Ø

Tavole  di  verità:

Ø Sia  

ν

 interpretazione  e  

f

 una  f.b.f.:  

 

§

ν

 modello  per  

f

 se  e  solo  se  

ν f ( ) = 1

.  

§

f

 tautologia  

 ( )

 se  e  solo  se    

ν f ( ) = 1

 per  ogni  interpretazione.  

§

f

 insoddisfacibile  se  e  soltanto  se  

ν f ( ) = 0

 per  ogni  interpretazione,  altrimenti  è   soddisfacibile.  

§ Oss:  

f

 è  tautologia  se  e  soltanto  se  

~ f

 è  insoddisfacibile.  

Ø Sia  

Γ

 un  insieme  di  f.b.f.:  

§ Sia  

ν

 interpretazione,  

ν

 è  un  modello  per  

Γ

 se  è  un  modello  per  tutte  le  formule  che   appartengono  a  

Γ

.  

§

Γ

 è  soddisfacibile  se  esiste  un  modello  per  

Γ

.   Ø Sia  

Γ

 insieme  di  f.b.f.  e  

f

 una  f.b.f.:  

§

f

 è  conseguenza  semantica  di  

Γ

 

Γ  f ( )

 se  e  solo  se  ogni  modello  per  

Γ

 è  modello  per  

f

  (potrebbe  capitare  che  

Γ = 0

 e  

f = 1

,  non  c’è  nessun  problema).  

Ø Siano  

f , g

 f.b.f.:  

§

f ≡ g

 semanticamente  equivalenti  se  tutti  i  modelli  di  

f

 sono  tutti  e  soli  modelli  

g

 (è  una   forma  ancora  più  forte  della  conseguenza  semantica).  

§

f ≡ g

 se  e  solo  se  

f ⇔ g

 tautologia.  

 

µ Teoremi:  

Ø

Th  Deduzione  semantica:  

§ Sia  

Γ

 insieme  di  f.b.f.,  

g, f

 f.b.f.  Allora  

Γ ∪ g { }  f

 se  e  solo  se  

Γ  g ⇒ f

.    

• In  parole:  

f

 è  conseguenza  semantica  di  

Γ ∪ g { }

 se  e  solo  se  

g ⇒ f

 è  conseguenza   semantica  di  

Γ

.  

• Diversa  versione:  

g  f ⇔  g ⇒ f

.  NB:  se  

 è  preceduta  da  una  f.b.m.  allora  significa   conseguenza  semantica,  altrimenti  significa  tautologia.  

§ Dimostrazione:  

(3)

( ) ⇒

 Hp:  

Γ ∪ g  f

.  Th:  

Γ  g ⇒ f

.  Sia  

ν

 un  modello  per  

Γ

.  

♦ 1°  Caso:  

ν

 modello  per  

g

.  

Allora  

ν

 è  un  modello  per  

Γ ∪ g { }

.  

Per  ipotesi,  

ν

 è  un  modello  anche  per  

f

 (infatti  

f

 è  conseguenza  semantica  di  

Γ ∪ g { }

).  

Pertanto  abbiamo  che  

ν g ⇒ f ( ) = 1

.  

♦ 2°  Caso:  

ν

 non  è  un  modello  per  

g

.  

Abbiamo  già  concluso  perché  se  

g

 falso  possiamo  dedurre  qualsiasi  cosa,  infatti  per  

definizione  di  implica  abbiamo:  

ν f ⇒ g ( ) = max 1− ν f ( )

0

  

1

 ,ν g ( )

⎨ ⎪⎪

⎩ ⎪

⎬ ⎪⎪

⎭ ⎪

= 1

 

( ) ⇐

Hp:  

Γ  g ⇒ f

.  Th:  

Γ ∪ g  f

.  

♦ Sia  

ν

 un  modello  per  

Γ ∪ g { }

,  allora  

ν

 è  modello  per  

Γ

 e  

ν g ( ) = 1

.  

Per  ipotesi  

ν f ( ) = 1

.  

Ø

Th  senza  nome:  

§ Sia  

Γ

 insieme  di  f.b.f.  e  

f

 f.b.f.:  

Γ  f

 se  e  solo  se  

Γ ∪ ~ f { }

 è  insoddisfacibile.  

§ Dimostrazione:  

( ) ⇒

 Hp:  

Γ  f

,  Th:  

Γ ∪ ~ f { }

 insoddisfacibile.  

♦ 1°  Caso:  Sia  

ν

 un  modello  per  

Γ

.  Per  ipotesi,  

ν f ( ) = 1

.  Quindi  

ν ~ f ( ) = 0

.  Quindi  

Γ ∪ ~ f { }

 insoddisfacibile.  

♦ 2°  Caso:  

ν

 non  è  modello  per  

Γ

.  Allora  non  lo  sarà  neppure  per  

Γ ∪ ~ f { }

.  

( ) ⇐

 Hp:  

Γ ∪ ~ f { }

 insoddisfacibile.  Th:  

Γ  f

.  

♦ Sia  

ν

 un  modello  per  

Γ

.  Per  Hp,  

v ~ f ( ) = 0

.  Segue  

ν f ( ) = 1

.  Allora  abbiamo   dimostrato  il  teorema.  

Ø

Th  di  compattezza:  

§ Sia  

Γ

 insieme  di  f.b.f.,  allora  

Γ

 è  soddisfacibile  se  e  solo  se  ogni  sottoinsieme  finito  di  

Γ

 è   soddisfacibile.  

 

µ Proprietà  dei  connettivi:  

Ø

~ ~ A ( ) ≡ A

.  

Ø

A ∧ A ≡ A

       

A ∨ A ≡ A

.   Ø

A ∧ B ≡ B ∧ A

     

A ∨ B ≡ B ∨ A

.  

Ø

A ∧ B ∧ C ( ) ≡ A ∧ B ( ) ∧ C

   

A ∨ B ∨ C ( ) ≡ A ∨ B ( ) ∨ C

.  

Ø

A ∧ A ∨ B ( ) ≡ A

       

A ∨ A ∧ B ( ) ≡ A

.  

Ø

A ∧ B ∨ C ( ) ≡ A ∧ B ( ) ∨ A ∧ C ( )

 

A ∨ B ∧ C ( ) ≡ A ∨ B ( ) ∧ A ∨ C ( )

.  

Ø

~ A ( ∧ B ) ≡~ A∨ ~ B

     

~ A ( ∨ B ) ≡~ A∧ ~ B

.  

Ø

A ⇒ B ≡~ A ∨ B

     

A ⇒ B ≡~ A∧ ~ B ( )

.  

Ø

~ A ∧ A

( )

   

∨ B ≡ B

     

~ A ∨ A

( )

T

     ∧ B ≡ B

.   Ø

A ⇔ B ≡ A ⇒ B ( ) ∧ B ⇒ A ( )

.  

(4)

Ø Tutte  le  formule  possono  essere  scritte  usando  solo  questi  insiemi  di  connettivi  

{ } ~,∧ , ~, { } , ~,⇒ { }

,  che  sono  detti  funzionalmente  completi  (o  insiemi  adeguati)  .  Ci  sono  altri   connettivi  funzionalmente  completi:  

§ NOR:  

|

.  

A ∨ B ≡ A | B ( ) | A | B ( )

.  

§ NAND:  

.  

A ∧ B ≡ A ↓ B ( ) ↓ A ↓ B ( )

.  

Ø Per  trasformare  una  formula  in  modo  da  costruire  una  f.b.f.  equivalente  alla  data  e  che  sia  “più   semplice”  o  perché  utilizza  un  numero  minore  di  connettivi,  o  un  numero  minore  di  tipi  di   connettivi,  si  utilizzano  le  seguenti  osservazioni:  

§ Sia  

f

 una  f.b.f.,  

g ∈Stfm f ( )

.  

g≡ g'

 à  

f ≡ f '

.  In  parole  se  si  sostituisce  in  blocco  la  formula  

g

 con  

g '

 nella  formula  

f

,  abbiamo  ancora  una  tabella  di  verità  identica.  

 

µ Teoria  formale  (Sistema  Deduttivo):  

Ø Una  teoria  formale  è  definita  quando  sono  definite:  

§ Alfabeto.  

§ F.b.f.  

§ Assiomi  che  non  sono  altro  che  un  insieme  privilegiato  di  f.b.f.  

§ Regole  di  inferenza:  ci  permette  in  modo  algoritmico  di  scrivere  nuove  formule  e  di  giungere   ad  una  conclusione  che  a  noi  interessa.  

Ø Sia  

H

 teoria  formale  

§ Una  dimostrazione  della  teoria  formale  

H

 è  una  sequenza  di  f.b.f.  Le  formule  di  questa   sequenza  sono  degli  assiomi  o  delle  formule  dedotte  utilizzando  le  regole  di  inferenza.  

§ Chiamiamo  

a

 Teorema  della  teoria  

H

 una  f.b.f.  (

|-

H

a

)  che  sia  l’ultima  formula  di  una   dimostrazione.  

§ Dato  un  insieme  di  f.b.f.  

Γ

,  diciamo  che  

a

 è  deducibile  in  

H

 da  

Γ

 se  esiste  una  sequenza   finita  di  f.b.f.  la  cui  ultima  sia  

a

.  In  modo  formale  si  scrive  

Γ|-

h

a

.  

• Oss:  un  teorema  di  

H

 è  una  formula  deducibile  da  un  insieme  vuoto  di  f.b.f.  

Γ

insieme  di  f.b.f.,  

a

 f.b.f.  

H

,  

Γ|-

H

a

.  

♦ Esiste  Γ' ⊆ Γ,Γ'finito  tale  che  

Γ'|-

H

a

.  

♦ Per  ogni  Γ'' ⊇ Γ,  

Γ''

 insieme  di  f.b.f.  vale  

Γ''|-

H

a

.    

µ Teoria  formale   L :  

Ø Alfabeto:  

§ Lettere  enunciative:  A, B,C,....  

§ Connettivi:  

~,⇒

.  

§ Simboli  ausiliari:  

( ) ,

.   Ø F.b.f.:  

§ Le  lettere  enunciative  sono  f.b.f.  della  teoria  

L

.  

§

f

 è  una  f.b.f.  della  teoria  

L

 à  

~ f

 è  ancora  una  f.b.f.  

§ Se  

f , g

 sono  f.b.f.  della  teoria  

L

 à  

f ⇒ g

 è  una  f.b.f.  

§ Nient’altro  è  una  f.b.f.  

Ø Assiomi:  

§

( ) A1

 à  

a ⇒ b ⇒ a ( )

.  

§

( ) A2

 à  

(

a⇒ b ⇒ c

( ) )

⇒ a ⇒ b

( ( )

⇒ a ⇒ c

( ) )

.  

§

( ) A3

 à  

(

~ a⇒~ b

)

⇒ ~ a ⇒ b

( ( )

⇒ a

)

.  

(5)

Ø Regola  di  inferenza  (Modus  ponens  (MP)):  

§ Da  

a

 e  a⇒ b,  dove  

a,b

 sono  f.b.f.,  si  riscrive  

b

.  

Ø La  teoria  formale  

L

 appena  definita  ha  le  seguenti  caratteristiche:  

§ È  corretta:  tutti  i  suoi  teoremi  sono  tautologie.  

§ È  completa:  tutte  le  sue  tautologie  sono  teoremi.  

§ È  deducibile:  attraverso  un  numero  finito  di  passi  è  possibile  verificare  se  una  formula  è  un   teorema  o  no  della  teoria.  

Ø

Teorema  di  correttezza  e  completezza:  

§ Se  

a

 è  una  f.b.f.  della  teoria  

L

,  allora  

|-

L

a

 (teorema  della  teoria  

L

)  se  e  solo  se  

 a

  (tautologia).  

§ Dimostrazione:  

( ) ⇒

 dimostriamo  il  teorema  di  correttezza.  Premessa:  tutti  gli  schemi  degli  assiomi  sono   delle  tautologie.  Il  modus  ponens  “fa  passare”  da  tautologia  a  tautologia.  

♦ Dimostriamo  la  premessa.  Ipotesi:  

 a

 a ⇒ b

,  Teorema:  

 b

,  sono  simboli  di  tautologia.  

Ø Dim:  sia  

ν

 interpretazione.  

1=

ν (

a⇒ b

)

= max 1−

{ ν ( )

a ,

ν ( )

b

}

= max 0,v b

{ ( ) }

=

ν ( )

b  sapendo  che  per   ipotesi  abbiamo  che  

ν a ( ) = 1

.  

♦ Dimostriamo  per  induzione.  Prendiamo  

n = 1

.  Se  

n = 1

 abbiamo  subito  

a

 che   siccome  dobbiamo  dimostrare  un  teorema,  che  significa  che  la  nostra  formula  deve   essere  l’ultimo  passaggio  della  dimostrazione,  e  sappiamo  che  

a

 è  un  assioma  e  gli   assiomi  sappiamo  che  sono  tautologie  à  sempre  vera.  Dimostrato.  

♦ Ora  prendiamo  

n > 1

.  Supponiamo  vera  la  tesi  per  ogni  

m < n

,  dobbiamo  dimostrare   che  è  vera  anche  per  

n

.  

Ø

Teorema  di  correttezza  e  completezza  forte:  

§

Γ

 insieme  di  f.b.f.  di  

L

,  

a

 f.b.f.  di  

L

 à  

Γ|-

L

a

 se  e  solo  se  

Γ  a

.   Ø

Teorema  di  deduzione  sintattica:  

§

Γ

 insieme  di  f.b.f.  di  

L

;  

a,b

 f.b.f.  di  

L

 à  

Γ ∪ b { } |-

L

a

 se  e  solo  se  

Γ|-

L

b ⇒ a

.   Ø Letterale:  

A

 o  

~ A

 si  chiamano  letterale.  

Ø Clausola:  disgiunzione  finita  di  zero  o  più  letterali.  

§ Esempio:  

A∨ ~ B ∨ C

 à  

{ A, ~ B,C }

.  

§ Clausola  vuota:  clausola  che  non  contiene  letterato,  il  simbolo  è  

.   Ø Forma  a  clausole  di  una  f.b.f.:  

§ Abbiamo  determinato  le  clausole  

c

1

, c

2

,..., c

n,  la  f.b.f.  si  definisce  in  forma  a  clausole  se  

c

1

∧ c

2

∧ ...∧ c

n  e  si  scrive  

( )

f C.  

§ Esempio:  

( (

A⇒ B

)

∧ A ⇔ C

( ) )

∨ ~ B.  Devo  trasformare  utilizzando  le  equivalenze  in  modo   tale  che  vi  siano  solo  

{ ∧,∨,~ }

.  

( (

~ A∨ B

)

∧ A ⇒ C

( )

∧ C ⇒ A

( ) )

∨ ~ B  à  

~ A∨ B

( )

∧ ~ A ∨ C

( )

∧ ~ C ∨ A

( )

( )

∨ ~ B  à

~ A∨ B∨ ~ B

( )

∧ ~ A ∨ C∨ ~ B

( )

∧ ~ C ∨ A∨ ~ B

( )

( )

 ecco  la  nostra  forma  a  clausole  

perché  è  una  congiunzione  di  disgiunzioni  (congiunzione  di  clausole).  

S = ~ A, B,~ B { { } , ~ A,C, ~ B { } , ~ C, A, ~ B { } } = f ( )

C.  

Ø Sia  

C

1

,C

2

, R

 clausole:  

R

 si  dice  risolvente  di  

C

1  e  

C

2  se  esiste  un  letterale  

L ∈C

1  tale  che  

~ L ∈C

2  e  R= C

(

1\ L

{ } )

∪ C

(

2 \ ~ L

{ } )

.  

§ Oss:  

C

1

,C

2

 R

 ossia  sono  conseguenza  semantica  di  

R

.  

(6)

§ Esempio:  

{ ~ A ,C, ~ B } , ~ C, A , ~ B { }

 à  

{ B, ~ B } ∪ ~ C,~ B { }

 à  

{ B, ~ B, ~ C }

.  

Ø Derivazione  per  risoluzione  di  una  clausola  

D

 da  un  insieme  di  f.b.f.  

Γ

:  dobbiamo  costruire  una   sequenza  di  clausole  di  cui  l’ultima  clausola  deve  essere  proprio  

D

.  E  quelle  precedenti  devono   essere  clausole  che  vengono  da  

Γ

 e  le  posso  combinare  tra  loro  tramite  le  regole  di  inferenza   dette  precedentemente.  Per  indicare  che  tutte  le  f.b.f.  di  

Γ

 sono  formate  da  clausole  lo  indichiamo   con  il  simbolo  

Γ

C  (chiamate  clausole  di  input).  

Γ |-

R

C

.  

§ Se  riusciamo  ad  utilizzare  solo  le  clausole  di  input  durante  la  derivazione  per  risoluzione,  si  dice   soluzione  lineare  di  input.  Ma  non  è  sempre  possibile.  

§ Per  derivare  per  risoluzione  si  può  usare  l’albero  di  derivazione.  

Ø Teorema:  Sia  

Γ

 insieme  di  f.b.f.,  

Γ

 è  un  insieme  insoddisfacibile,  se  e  solo  se  

Γ |-

R

.  

§ Ricordiamo  che  

Γ  f

 se  e  solo  se  

Γ ∪ ~ f { }

 insoddisfacibile.  Quindi  possiamo  utilizzare   questo  teorema  per  verificare  che  

Γ ∪ ~ f { }

 insoddisfacibile.  Per  far  ciò  bisogna  verificare   che  

Γ ∪ ~ f { } |-

R

.  

• Caso  particolare:  

 f

 se  e  solo  se  

~ f

 insoddisfacibile  se  e  solo  se  

~ f { } |-

R

.   Ø Metodo  di  risoluzione.  

Γ

 insieme  di  f.b.f.:  

§ Premesse:  

• Ris  

( ) Γ

C

= Γ

C

∪ C {

ij

: C

ij

risolvente delle clausole C

i

,C

j

di Γ

C

}

.  (Risolvente)  

Ris

n

( ) Γ

C

= Ris Ris (

n−1

( ) Γ

C

)

,  

Ris* ( ) Γ

C

= 

n>0

Ris

n

( ) Γ

C .  

§  

Γ  f

.  

Γ

C  

( )

~ f C  

S := ΓC ∪ ~ f

( )

C  ora  ripetiamo  questa  procedura  finchè  

S = F

 oppure  

∈S

 

F : = S

.  

S : = Ris F ( )

.  

• Se  

∈S

 allora  

Γ  f

 altrimenti  

Γ  f

.  

Ø Clausola  di  Horn:  quando  vi  è  una  clausola  al  più  positivo.  Esempio:  

{ ~ A, ~ B, ~ C }

 o  

{ ~ B,C }

.  

§ La  derivazione  lineare  per  input  è  completa  quando  l’insieme  di  clausole  di  partenza  è  

costituito  da  clausole  di  Horn.  Questo  significa  cha  da  un  insieme  di  clausole  di  Horn  possiamo   ricavare  la  clausola  vuota  se  e  solo  se  la  possiamo  ricavare  tramite  una  risoluzione  lineare  per   input.  

 

Riferimenti

Documenti correlati

Usando il fatto che la funzione logaritmo in base 10 e’ strettamente crescente, si dia l’approssimazione agli interi di log 10 ( 1234

Per semplicita’ di seguito ci limitiamo a considerare funzioni continue, anzi, affinche’ abbiano senso tutte le formule seguenti, ci limitiamo a considerare funzioni derivabili

[r]

&#34;Produzione di energia da fonti rinnovabili (Cod. 39-40-41)&#34; e 3.1.2.A &#34;Sostegno all'adozione. Struttura di riferimento Regione Autonoma della

Bosco essere applicati esclusivam ente allo

Questo processo di atresia, che sembra essere dominante durante tutta la vita, ha significati ben precisi: innanzitutto determina l’eliminazione della maggior parte delle

By looking at Table 1.B it can easily be seen that the introduction of a minimum wage (which has been chosen to be the 20 per-cent higher then the competitive wage) 30 boosts

L’appoggio bipodalico statico mostra le pressioni plantari esercitate dal paziente in 100 livelli per evidenziare le differenti intensità di carico in percentuale della