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

(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

Γ ∪ g { }

se e solo se

g ⇒ f

Γ

.

• 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

Γ ∪ 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.

•

( ) ⇒

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).

•

( ) ⇒

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

₁

, c

₂

,..., c

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

c

₁

∧ 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

₁

,C

₂

, R

clausole:

R

si dice risolvente di

C

₁ e

C

₂ se esiste un letterale

L ∈C

1 tale che

~ L ∈C

2 e R= C

(

₁\ L

{ } )

^{∪ C}

(

² ^{\ ~ L}

^{{ }} )

^.

§ Oss:

C

¹

,C

₂

 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

ⁿ

( ) Γ

^C

^{= Ris Ris} (

ⁿ⁻¹

( ) ^Γ

^C

)

^,

^Ris* ^{( )} ^Γ

^C

^{= }

_n_>0

^Ris

ⁿ

^{( )} ^Γ

^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.