Appunti Elementi di matematica computazionale

Q

R[ ]).

⇐ /

P (esempio pag70,

slide 69/93)

Usando le leggi ogni proposizione può essere trasformata in una forma

normale, ne esistono di 2 tipi: forma normale congiuntiva ((P P

⋁ ⋁

1 2

…) (Q Q …) …), forma normale disgiuntiva ((P P

⋀ ⋁ ⋁ ⋀ ⋀

1 2 1 2

…) (Q Q …) …), utili per le dimostrazioni, ma

⋀ ⋁ ⋀ ⋀ ⋁

1 2

spesso ridurre a forma normale aumenta la dimensione della formula.

Il principio di Risoluzione, ci permette di semplificare una formula in

forma nomale congiuntiva; è il meccanismo di calcolo alla base della

programmazione logica.

In generale, possiamo rapprensentare con delle formule proposizionali

delle tecniche di dimostrazione: saranno corrette se e solo se la

formula è una tautologia.

Dimostrazione per assurdo : Per dimostrare che P è una tautologia,

 basta mostrare che ¬P è una contraddizione

Dimostrazione per controposizione: Per dimostrare P Q, basta

 ⇒

mostrare che ¬Q ¬P

⇒

Dimostrazione per casi: Per dimostrare Q, basta mostrare che per un

 certo P, valgono sia P Q, che ¬P Q ((P Q) (¬P Q)

⇒ ⇒ ⇒ ⋀ ⇒

Q) oppure per dimostrare che P R Q S, basta fornire

⋀ ⇒ ⋀

≡

due prove separate per P Q e R S ((P Q) (R S)

⇒ ⇒ ⇒ ⋀ ⇒

(P R Q S))

⇒ ⋀ ⇒ ⋀

Riassumendo!

Per dimostrare che da una ipotesi P segue una conseguenza Q, possiamo

dimostrare che:

P Q è una tautologia, ¬Q ¬P è una tautologia, P ¬Q F è

⇒ ⇒ ⋀ ⇒

una tautologia, o come strategia alternativa, per dimostrare P Q,

⇒

partiamo da Q e cerchiamo di dimostrare che è vero sotto l'ipotesi, da

usare come giustifcazione in qualche passaggio, che P sia vero.

* Ricordiamoci infatti che il caso critico dell'implicazione P Q è

⇒

dimostrare che Q è vero quando P è vero. Quando P è

falso l'implicazione vale sempre.

Ci sono altre tautologie che rappresentano tecinche di dimostrazione :

LOGICA DEL PRIMO ORDINE

Le formule proposizionali possono descrivere relazioni logiche tra un

numero finito di enunciati, la Logica del Primo Ordine (LPO) estende il

calcolo proposizionale.

Con le formule di LPO si possono: denotare esplicitamente gli elementi del

dominio, esprimere proprietà di individui e relazioni tra due o più individui

(usando i predicati) e si può quantificare una formula.

Nella logica del primo ordine ci sono due categorie sintattiche e

semantiche diferenti:

i termini, che sono passati come argomenti dei predicati e denotano

 elementi del dominio di riferimento

le formule, costruite a partire dai predicati, assumono valore booleano

 ,

Un alfabeto del primo ordine comprende: insieme delle variabili;

V

insieme delle costanti; insieme delle funzionioni (ognuno con la

C F

sua arietà (numero di argomenti)); insieme dei predicati (ognuno

P

con la sua arietà); i connettivi logici , , ;

⋀ ⋁ ⟹ ⟸,

¬, , ≡

i quanitficatori ; i simboli “(”, “)”, ”,”, “.”;

∀ ,∃

In una formula quantificata come ( x.P) o ( y.P) la sottoformula P è

∀ ∃

detta la portata del quantificatore. Una occorrenza di variabile x è

legata se compare nella portata di un quantificatore altrimenti è detta

libera.

Il nome di una variabile legata può essere cambiato grazie alle leggi di

ridenominazione:

Una formula che contiene occorrenze di variabili libere è detta aperta,

mentre una formula senza variabili libere è detta chiusa.

La semantica di una formula chiusa si determina rispetto ad una

interpretazione, che assegna la semantica ad una formula chiusa

fissando il significato dei simboli che compaiono (il dominio di interesse, a

quali elementi del dominio corrispondono le costanti, a quali funzioni, a

quali proprietà o relazioni corrispondono i predicati).

Dato un linguaggio del primo ordine, ovvero fissato un alfabeto V ,C , F , P

e una interpretazione è costituita da:

=( )

I D , α

Un insieme , detto dominio dell’interpretazione

 D

Una funzione di interpretazione che associa: ad ogni costante

 α

del linguaggio un elemento , rappresentato da , ad

∈ (c)

c C D α

n

ogni funzione di arietà una funzione che data una n-upla

∈ (f )

f F α

di elementi di restituisce un elemento di (ovvero

D D n

), ad ogni predicato di arietà una funzione

n (

p∈ P α p)

(f ):

α D → D n-upla

che data una di elementi di restiruisce un valore di verità

D

(ovvero .

n

(p): {T }

α D → , F

Un assegnamento è una funzione che associa ad ogni variabile un

ρ

elemento del dominio ( ), possiamo rappresentare un

ρ :V → D

assegnamento anche come un insieme di coppie (es. ={x,y,z},

V D=N

, , allora .

↦ ↦ ↦ }

ρ={ x 0, y 3, z 1

)=0, )=3,

ρ( x ρ( y ρ( z)=1 [ ]

d

Se è un assegnamento, con denotiamo l’assegnamneto che

ρ

ρ x

x d

associa alla variabile il valore , e sulle altre variabili si comporta come

{ =

d se x y

/ ]=

ρ[d x

, quindi .

ρ ( )

ρ y else

Data una intrpretazione e un assegnamento , la

=(D ) ρ :V → D

I , α

semantica della formula , denotata , è defnita per induzione

Φ

strutturale dalle regole S1-S9:

Sia un’interpretazione e una formula chiusa, se è vera in ,

I Φ Φ I

diciamo che è un modello di e scriviamo . Se è un

⊨Φ

I Φ I Γ

insieme di formule con intendiamo che è un modello di tutte le

⊨

I Γ I

formule in . Se una formula è vera in tutte le interpretazioni di

Γ Φ

dice che è valida ( )(tautologia), se è vera in almeno una

⊨Φ

interpretazione si dice che è soddisfacibile altrimenti è

insoddisfacibile (contraddizioni).

Diciamo che è una conseguenza logica di ( ) se e

⊨Φ

Φ Γ Γ

soltanto se è vera in tutti i modelli di .

Φ Γ

Dato un insieme di formule Δ, un sistema di dimostrazione (o proof

system) per Δ è un insieme di Regole di Inferenza. Ciascuna regola di

inferenza consente di derivare una formula (conseguenza) da un insieme

δ ,. . . , δ

di formule (premesse). Una regola di inferenza ha la forma: ,

1 k

δ

dove sono le premesse e è la conseguenza, e sono tutte

δ , . .. , δ δ

1 k

formule in Δ.

Una dimostrazione di una formula a partire da un insieme di

Φ

premesse è una sequenza di formule tale che ogni formula

Φ , .. . , Φ

Γ 1 n

di è un elemento di oppure è ottenuta applicando una regola di

Φ Γ

i

inferenza a partire dalle premesse e e coincide con

Φ , .. . , Φ Φ

Γ 1 i−1 n

. Se esiste una dimostrazione di a partire da scriviamo ⊢Φ

Φ Φ Γ Γ

.

Un proof system è corretto se quando esiste una dimostrazione di una

formula da un insieme di premesse allora è una

Φ Γ Φ

conseguenza logica di , cioè : se allora .

⊢Φ ⊨Φ

Γ Γ Γ

Un proof system è completo se quando una formula è

Φ

conseguenza logica di un insieme di premesse , allora esiste una

Γ

dimostrazione di da , cioè: se allora .

⊨Φ ⊢Φ

Φ Γ Γ Γ

Nota: Il calcolo proposizionale è un proof system corretto e anche

completo che usa come regole di inferenza i principi di sotituzione di

equivalenza e implicazione, ora estenderemo i proof system al calcolo del

primo ordine.

Generaliziamo il principio di sostituzione dell’equivalenza:

*La generalizzazione consiste nel far riferimento ad un

insieme di premesse . Se P e Q sono logicamente

Γ

equivalenti nelle premesse

, allora il fatto che R e R[Q/P] sono equivalenti è

Γ

dimostrabile da Γ

Generaliziamo il principio di sostituzione dell’implicazione:

*P occorre positivamente in x.P e in x.P, quindi:

∀ ∃

Sappiamo che per dimostrare che P Q è una tautologia basta

⇒

dimostrare Q usando P come ipotesi, ora possiamo giustificare tale

tecnica tramite il Teorema di Deduzione:

, ovvero per dimostrare un’implicazione è

⊢ ⇒Q

Γ P se e solo se Γ , P⊢ Q

possibile costruire una dimostrazione per Q usando sia le leggi generali

(formule valide) che P come ipotesi.

Rivediamo anche alcune leggi per i quantificatori:

(nelle seguenti formule, t è un termine chiuso e P[t/x] è ottenuto da P

sostituendo le occorrenze libere di x in P con t) [ ]

t t

Elim- : Intro- : ⇒(∃

(∀ ]

x . P)⇒ P[ P x . P)

∀ ∃

x x

De Morgan: Annidamento: ( ) ( )

( ) ( ) ( ) ( )

∀ ∃ ∀ ∀ ∀ ∀

¬ x . P ≡ x .¬ P x . y . P ≡ y . x . P

( ) ( )

( ) ( )

∃ ∃ ∃ ∃

( ) ( )

∃ ∀ x . y . P ≡ y . x . P

¬ x . P ≡ x .¬ P

: : : :

( ) ( ) ( ) ( ) ( )

∀ ∧ ∀ ∧Q ∀ ∧(∀ ∀ ∨ ∀ ∨ ∀ ⇒ ∀

x . P ≡ x . P x .Q) x . P x .Q x . P∨ Q

: : : :

( ) ( ) ( )

( )

∃ ∧ ∃ ∧Q ⇒ ∃ ∧(∃ ∃ ∨ ∃ ∨(∃

∃ ∨Q

x . P x . P x . Q) ≡ x . P x . Q)

x . P

Distrib- : Distrib- :

( ) ( ) ( ) ( )

∀ ∃

∀ ∨Q ∀ ∨Q ∃ ∨Q ∃ ∨Q

x . P ≡ x . P x . P ≡ x . P

( ) ( ) ( ) ( )

∀ ∧Q ∀ ∧Q ∃ ∧Q ∃ ∧Q

x . P ≡ x . P x . P ≡ x . P

Dominio: ( ) ( ) ( )

∀ ∧Q ⇒ ∀ ⇒ ∧ ∀

x . P R ≡ x . P R x . Q⇒ R

( ) ( ) ( )

∃ ∃ ∧ ∨ ∃

x .(P∨ Q)∧ R ≡ x . P R x . Q∧ R

PROLOG

Prolog acronimo di Programming in Logic è un linguaggio di

programmazione degli anni 70/80 ideato da Robert Kowalski. È un

linguaggio di programmazione diverso dagli altri: è dichiarativo e non

procedurale, lavora con la ricorsione e non con i cicli (for o while), si b