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
eg
sono f.b.f allora anchef ∨ 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 enunciativaA
, allorastfm f ( ) = A { }
.§ Se
f
è~ g
allorastfm 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
è
µ Semantica:
Ø
Interpretazione:
siaν : f .b.f { } → 0,1 { }
una funzione che associa ad una f.b.m. un valore{ } 0,1
e siaf , 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 ef
una f.b.f.:§
ν
modello perf
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. ef
una f.b.f.:§
f
è conseguenza semantica diΓ
Γ f ( )
se e solo se ogni modello perΓ
è modello perf
(potrebbe capitare cheΓ = 0
ef = 1
, non c’è nessun problema).Ø Siano
f , g
f.b.f.:§
f ≡ g
semanticamente equivalenti se tutti i modelli dif
sono tutti e soli modellig
(è una forma ancora più forte della conseguenza semantica).§
f ≡ g
se e solo sef ⇔ 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 seg ⇒ 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:
•
( ) ⇒
Hp:Γ ∪ g f
. Th:Γ g ⇒ f
. Siaν
un modello perΓ
.♦ 1° Caso:
ν
modello perg
.Allora
ν
è un modello perΓ ∪ g { }
.Per ipotesi,
ν
è un modello anche perf
(infattif
è conseguenza semantica diΓ ∪ g { }
).Pertanto abbiamo che
ν g ⇒ f ( ) = 1
.♦ 2° Caso:
ν
non è un modello perg
.Abbiamo già concluso perché se
g
falso possiamo dedurre qualsiasi cosa, infatti perdefinizione 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. ef
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 ( )
.Ø 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 formulag
cong '
nella formulaf
, 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 teoriaH
una f.b.f. (|-
Ha
) che sia l’ultima formula di una dimostrazione.§ Dato un insieme di f.b.f.
Γ
, diciamo chea
è deducibile inH
daΓ
se esiste una sequenza finita di f.b.f. la cui ultima siaa
. In modo formale si scriveΓ|-
ha
.• 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
,Γ|-
Ha
.♦ Esiste Γ' ⊆ Γ,Γ'finito tale che
Γ'|-
Ha
.♦ Per ogni Γ'' ⊇ Γ,
Γ''
insieme di f.b.f. valeΓ''|-
Ha
.µ 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 teoriaL
à~ f
è ancora una f.b.f.§ Se
f , g
sono f.b.f. della teoriaL
à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)
.Ø Regola di inferenza (Modus ponens (MP)):
§ Da
a
e a⇒ b, dovea,b
sono f.b.f., si riscriveb
.Ø 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 teoriaL
, allora|-
La
(teorema della teoriaL
) 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
. Sen = 1
abbiamo subitoa
che siccome dobbiamo dimostrare un teorema, che significa che la nostra formula deve essere l’ultimo passaggio della dimostrazione, e sappiamo chea
è un assioma e gli assiomi sappiamo che sono tautologie à sempre vera. Dimostrato.♦ Ora prendiamo
n > 1
. Supponiamo vera la tesi per ognim < n
, dobbiamo dimostrare che è vera anche pern
.Ø
Teorema di correttezza e completezza forte:
§
Γ
insieme di f.b.f. diL
,a
f.b.f. diL
àΓ|-
La
se e solo seΓ a
. ØTeorema di deduzione sintattica:
§
Γ
insieme di f.b.f. diL
;a,b
f.b.f. diL
àΓ ∪ b { } |-
La
se e solo seΓ|-
Lb ⇒ 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 sec
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 clausoleperché è 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 diC
1 eC
2 se esiste un letteraleL ∈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 diR
.§ 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 proprioD
. 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).Γ |-
RC
.§ 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
ijrisolvente delle clausole C
i,C
jdi Γ
C}
. (Risolvente)•
Ris
n( ) Γ
C= Ris Ris (
n−1( ) Γ
C)
,Ris* ( ) Γ
C=
n>0Ris
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.