API Ripasso di logica Davide Martinenghi

(1)

API

Ripasso di logica

Davide Martinenghi

Politecnico di Milano

API Davide Martinenghi (1/30)

(2)

Logica proposizionale - sintassi

I L`e un linguaggio della logica proposizionale

I L’alfabetodi L`e composto da

I Un insieme numerabile (finito o infinito) diproposizioni(simboli di relazione nullaria): A,B,C,. . .

I I seguenticonnettivi: ¬,∧,∨,→,↔

I Isimboli di punteggiatura: (,)

I I simboli dell’alfabeto sono privi di significato (assegnarne uno `e compito della “semantica”)

(3)

Logica proposizionale - sintassi

I L’insieme di formuledi L`e il pi`u piccolo insieme tale che:

I Ogni proposizione `e una formula

I SeF eG sono formule, allora(¬F ),(F ∧ G ),(F ∨ G ),(F → G )e (F ↔ G )sono formule

I Le parentesi sono omesse ovunque possibile usando la precedenza:

¬ > ∧ > ∨ >→>↔

I Se A`e una proposizione, allora Ae ¬Asono dettiletterali

I A`e dettoletterale positivo;¬Aletterale negativo

I Se L`e un letterale,L¯`e illetterale complementare definito come¬A seL = A, o AseL = ¬A

(4)

Logica proposizionale - sintassi

I Informalmente, unasotto-formula `e una formula inclusa in un’altra formula

I L’insieme T (F ) delle sotto-formule diF `e definito come il pi`u piccolo insieme di formule tale che

I F ∈ T (F )

I se¬G ∈ T (F )alloraG ∈ T (F )

I seG ∧ H,G ∨ H,G → H oG ↔ H appartengono aT (F ), allora H, G ∈ T (F )

(5)

Logica proposizionale - semantica

I La semantica `e introdotta per assegnare unsignificatoalle formule

I Nella logica proposizionale, ogni formula pu`o corrispondere a un solo valore di verit`a: overoo falso

I E una logica a` due valori; altre logiche introducono valori di verit`a aggiuntivi

I Un’interpretazione I `e una funzione totale dall’insieme di proposizioni ai valori di verit`a

I Ogni interpretazione pu`o essere convenientemente rappresentata come l’insieme delle proposizioni vere

(6)

Logica proposizionale - semantica

I Un’interpretazione pu`o essere estesa all’insieme delle formule

I I |= F significa cheI rende veraF

I |= A sse I (A) =vero(A `e una proposizione)

I |= ¬F sse I 6|= F

I |= F ∧ G sse I |= F e I |= G I |= F ∨ G sse I |= F o I |= G I |= F → G sse I 6|= F o I |= G I |= F ↔ G sse I |= F → G e I |= G → F

I Esempio: I₁ = {A, C }, I2 = {C , D}, F = (A ∨ B) ∧ (C ∨ D) alloraI₁|= F ma I₂6|= F

(7)

Logica proposizionale - semantica

I L’interpretazione dei connettivi pu`o anche essere esplicitata mediante unatabella di verit`a

F G ¬F F ∧ G F ∨ G F → G F ↔ G

vero vero falso vero vero vero vero

vero falso falso falso vero falso falso

falso vero vero falso vero vero falso

falso falso vero falso falso vero vero

(8)

Logica proposizionale - semantica

I Se I |= F, allora diciamo che I `e unmodello di F. Questa nozione pu`o essere estesa agli insiemi di formule

I F `evalida(o una tautologia) sse per ogni interpretazione I vale che I |= F

I In questo caso si pu`o anche scrivere|= F

I F `esoddisfacibilesse esiste un’interpretazione I tale che I |= F

I F `efalsificabile sse esiste un’interpretazione I tale che I 6|= F

I F `einsoddisfacibile sse per ogni interpretazione I vale cheI 6|= F

I F `econtingente sse `e sia soddisfacibile sia falsificabile

I Esempi: A ∨ ¬A`e valida; A ∨ B `e sia soddisfacibile sia falsificabile;

A ∧ ¬A `e insoddisfacibile

I Ogni formula del tipo F ∧ ¬F `e una contraddizione, spesso indicata con⊥; la formulaF ∨ ¬F `e dettaprincipio del terzo escluso, spesso scritta come>

(9)

Logica proposizionale - semantica

I Un insieme di formule F comporta logicamente una formulaG (oG

`

e una conseguenza logicadi F) se ogni modello di F `e anche un modello di G. Si scriveF |= G

I Esempio: {A, A → B} |= B,{A, A → B} |= B ∨ C, {A, A → B} 6|= C

I Per determinare sistematicamente se una formula segua da un insieme di formule si possono usare le tabelle di verit`a.

I Si devono considerare tutte le possibili combinazioni di valori di verit`a per ogni proposizione

(10)

Logica proposizionale - forme normali

I Due formule F e G sono (semanticamente) equivalentisse vale sia F |= G sia G |= F

I Si scrive F ≡ G

(11)

Logica proposizionale - forme normali

I Equivalenze notevoli:

(F ∧ F ) ≡ F idempotenza di∧

(F ∨ F ) ≡ F idempotenza di∨

(F ∧ G ) ≡ (G ∧ F ) commutatività di ∧ (F ∨ G ) ≡ (G ∨ F ) commutatività di ∨ (F ∧ (G ∧ H)) ≡ ((F ∧ G ) ∧ H) associatività di∧ (F ∨ (G ∨ H)) ≡ ((F ∨ G ) ∨ H) associatività di∨

((F ∧ G ) ∨ F ) ≡ F assorbimento

((F ∨ G ) ∧ F ) ≡ F assorbimento

(F ∧ (G ∨ H)) ≡ ((F ∧ G ) ∨ (F ∧ H)) distributivit`a (F ∨ (G ∧ H)) ≡ ((F ∨ G ) ∧ (F ∨ H)) distributivit`a

(¬(¬F )) ≡ F doppia negazione

(¬(F ∧ G )) ≡ (¬F ∨ ¬G ) legge di de Morgan (¬(F ∨ G )) ≡ (¬F ∧ ¬G ) legge di de Morgan

(F ↔ G ) ≡ (F → G ) ∧ (G → F ) equivalenza

(F → G ) ≡ (¬F ∨ G ) implicazione materiale (F → G ) ≡ (¬G → ¬F ) contronominale

(12)

Logica proposizionale - forme normali

I Equivalenze notevoli (senza parentesi ridondanti):

F ∧ F ≡ F idempotenza di ∧

F ∨ F ≡ F idempotenza di ∨

F ∧ G ≡ G ∧ F commutatività di∧ F ∨ G ≡ G ∨ F commutatività di∨ F ∧ (G ∧ H) ≡ (F ∧ G ) ∧ H associatività di∧ F ∨ (G ∨ H) ≡ (F ∨ G ) ∨ H associatività di∨

F ∧ G ∨ F ≡ F assorbimento

(F ∨ G ) ∧ F ≡ F assorbimento

F ∧ (G ∨ H) ≡ F ∧ G ∨ F ∧ H distributivit`a F ∨ G ∧ H ≡ (F ∨ G ) ∧ (F ∨ H) distributivit`a

¬¬F ≡ F doppia negazione

¬(F ∧ G ) ≡ ¬F ∨ ¬G legge di de Morgan

¬(F ∨ G ) ≡ ¬F ∧ ¬G legge di de Morgan F ↔ G ≡ (F → G ) ∧ (G → F ) equivalenza

F → G ≡ ¬F ∨ G implicazione materiale

F → G ≡ ¬G → ¬F contronominale

(13)

Logica proposizionale - forme normali

I Quando sostituiamo una sotto-formulaG di F con una formula H, la formula risultante viene indicata conF [G \H]

Teorema della sostituzione

Se G `e una sotto-formula diF e G ≡ H allora F ≡ F [G \H]

I In base alle equivalenze date, non tutti i connettivi sono strettamente necessari

I Un insieme di connettivi `e funzionalmente completosse qualunque formula proposizionale pu`o essere trasformata in una formula

semanticamente equivalente che contiene solo connettivi dell’insieme

I Esempio: {¬, ∧}`e funzionalmente completo

I Si possono definire altri connettivi booleani che, singolarmente, sono funzionalmente completi: nande nor

(14)

Logica proposizionale - forme normali

I Il teorema di sostituzione e le equivalenze notevoli possono essere utilizzate per introdurre le cosiddetteforme normali

I Una formula `e in forma normale negativasse `e composta solo da letterali, congiunzioni e disgiunzioni

I Una formula `e in forma normale congiuntiva(CNF) sse ha la forma C₁∧ C₂∧ . . . ∧ C_n dove ogniC_i `e una disgiunzione di letterali

I Una formula `e in forma normale disgiuntiva(DNF) sse ha la

formaD₁∨ D₂∨ . . . ∨ D_n dove ogniD_i `e una congiunzione di letterali

I C₁∧ C₂∧ . . . ∧ C_n ≡ C₁∧ C₂∧ . . . ∧ C_n∧ >, quindi possiamo dire che>`e in CNF prendendo n = 0

I D₁∨ D₂∨ . . . ∨ D_n ≡ D₁∨ D₂∨ . . . ∨ D_n∨ ⊥, quindi possiamo dire che⊥`e in DNF prendendo n = 0

I IC_i sono detti clausole; iD_i sono detti clausole duali; di solito si usa una notazione insiemistica

(15)

Logica proposizionale - sistemi formali (calculi)

I Ci chiediamo ora se le conseguenze logiche possono essere calcolate meccanicamente

I Un sistema formale (assiomatico-deduttivo), calculus in inglese, consiste di un insieme di assiomie un insieme di regole d’inferenza che producono conseguenze logiche all’interno di una logica

I Questi elementi definiscono una relazione di derivabilit`a (anche detta dimostrabilit`a) tra un insieme di formule F e una formulaG.

I Scriviamo F ` G seG pu`o essere ottenuto da F applicando solo regole di inferenza e assiomi.

I Idealmente, la relazione di derivabilità dovrebbe essere corretta(cioè, seF ` G allora F |= G) e completa(cioè, seF |= G allora F ` G)

I Se una formulaF pu`o essere derivata in una teoriaF usando gli assiomi e le regole d’inferenza di un sistema, allora diciamo cheF `e unteorema

(16)

Logica del prim’ordine (FOL) - sintassi

I La logica proposizionale (PL) ha molte applicazioni, ma il suo potere espressivo `e ristretto

I Frasi quali “tutti gli esseri umani sono mortali” e “ogni figlio ha dei genitori” possono essere espresse come proposizioni in un modo che non cattura le relazioni sottintese tra esseri umani, mortali, figli e genitori

I Frege ha sviluppato la cosiddettalogica del prim’ordine (FOL, nota anche come logica dei predicati) nel 1879, estendendo la logica proposizionale con funzioni, variabili e quantificatori

I Dal punto di vista epistemologico (stati della conoscenza), sia PL sia FOL considerano verit`ae falsit`a

I Dal punto di vista ontologico (ci`o che esiste), PL considera fatti, mentre FOL considera anche

I oggetti: persone, case, numeri, corsi, ...

I propriet`aerelazioni: essere rosso, essere felice, essere primo, ..., essere pi`u grande di, essere parte di, ...

I funzioni: padre di, et`a di, successore di, ...

(17)

FOL - sintassi

I L’alfabetodi un linguaggio della FOL L`e composto da

I Un insieme infinito numerabile divariabili: X,Y,Z,. . .

I Un insieme di simboli difunzione: f,g,. . .

I Un insieme di simboli dipredicati(orelazioni): p,q,r,. . .

I I seguenticonnettivi: ¬,∧,∨,→,↔

I I seguentiquantificatori: ∃, ∀

I Isimboli di punteggiatura: (,)e le virgole

I Ogni simbolo di funzione e relazione ha una ariet`afissata che indica il numero di argomenti associati ad esso

I Le funzioni nullarie sono dette costanti; i predicati nullari sono detti proposizioni

I I simboli dell’alfabeto sono privi di significato (assegnarne uno `e compito della “semantica”)

(18)

FOL - sintassi

I Itermini denotano tutti gli oggetti di cuiLpu`o parlare. Sono definiti induttivamente come segue:

I Ogni variabile `e un termine

I Sef `e un simbolo di funzionen-aria et1,. . .,t_n sono termini, allora f (t1, . . . , t_n)`e un termine

I I termini generici sono tipicamente indicati con s,t,. . .

I Una funzione nullariac() `e semplicemente scritta come c

(19)

FOL - sintassi

I L’insieme di formule della FOL`e definito induttivamente come il pi`u piccolo insieme tale che:

I Sep`e un simbolo di relazionen-aria e t1,. . .,t_n sono termini, allora p(t1, . . . , t_n)`e una formula dettaformula atomica oatomo

I SeF eG sono formule eX `e una variabile, allora (¬F )

(F ∨ G ) (F ∧ G ) (F → G ) (F ↔ G ) (∃XF ) (∀XF ) sono formule

I Un predicato nullariop()`e scritto semplicemente comep

(20)

FOL - sintassi

I Iletteralisono atomi (letterali positivi) o atomi negati (letterali negativi)

I Le parentesi sono omesse ove possibile mediante il seguente ordine di precedenza: ∃, ∀ > ¬ > ∧ > ∨ >→>↔

I Per convenienza

I (∃X₁(. . . (∃X_n(F )) . . .)`e abbreviato come(∃X₁, . . . , X_n(F ))e

I (∀X1(. . . (∀X_n(F )) . . .)`e abbreviato come(∀X1, . . . , X_n(F ))

(21)

FOL - sintassi

I Esempi di possibili traduzioni in FOL di frasi espresse in linguaggio naturale:

I “tutti gli esseri umani sono mortali” diventa (∀X (h(X ) → m(X )))

I “ogni figlio ha dei genitori” diventa

∀X (c(X ) → (∃Y ∃Z p(X , Y , Z ))))

(22)

FOL - sintassi

Osservazioni sulla traduzione verso FOL

I Il connettivo principale usato con∀ `e →

I Esempio: “al Polimi sono tutti brillanti” si pu`o tradurre cos`ı

∀X (at(X , polimi ) → smart(X ))

I Notare che la formula

∀X (at(X , polimi ) ∧ smart(X ))

significa che tutti sono al Polimi e tutti sono brillanti!

I Analogamente, il connettivo principale da usare con ∃`e∧

I Esempio: “al Polimi qualcuno `e brillante” si pu`o tradurre cos`ı

∃X (at(X , polimi ) ∧ smart(X ))

I Notare che la formula

∃X (at(X , polimi ) → smart(X ))

significa che c’è qualcuno che o non è al Polimi o è brillante (o entrambe le cose)!

(23)

FOL - sintassi

I Se QX (F )`e una formula eQ un quantificatore, alloraF si dice ambito di Q, e Q `e applicatoa F

I Un’occorrenza di una variabile in una formula `e legatasse la sua occorrenza `e entro l’ambito di un quantificatore che impiega quella variabile

I E legata al quantificatore di ambito pi`` u piccolo che la rende legata

I Altrimenti `e libera

I Esempio: ∀X (∀Y (p(X , Y ) ∧ q(X , Y )))

I Una formula `e chiusa sse non contiene occorrenze libere di variabili

(24)

FOL - semantica

I Come per PL, anche FOL ha una semantica a due valori di verit`a basata sulla nozione di interpretazione

I Un’interpretazione I di un alfabetoA`e undominio non vuotoD (anche indicato |I|) e una funzione che associa

I ogni costantec ∈ A a un elementocI ∈ D

I ogni simbolon-ario di funzionef ∈ Aa una funzionefI : Dⁿ 7→ D

I ogni simbolon-ario di predicatop ∈ Aa una relazione pI ⊆

n volte

z }| {

D × . . . × D

I Tuttavia, prima di assegnare un significato alle formule, va definito il significato dei termini

I Poich´e i termini possono contenere variabili, occorre unavalutazione (ostato), ossia una funzione dalle variabili di Aa |I|

I Il significatoφI(t)di un terminet nell’interpretazione I e valutazione φ`e quindi definito induttivamente come

I cI se t`e una costantec

I φ(X )se t`e una variabileX

I fI(φ_I(t₁), . . . , φ_I(t_n))se t`e della formaf (t1, . . . , t_n)

(25)

FOL - semantica

I Esempio: si consideri il termineg (f (c), X )

I SiaI un’interpretazione con|I| = Ne tale che

I Costanti: c_I = 0

I Funzioni: fI(x ) = 1 + x (successore),gI(x , y ) = x + y (addizione)

I Siaφ una valutazione tale cheφ(X ) = 0

I Allora

φI(g (f (c), X )) = φI(f (c)) + φI(X )

= (1 + φI(c)) + φ(X )

= (1 + 0) + 0

= 1

I Lo stesso termine pu`o avere significati diversi. Per esempio:

I |I| =persone nella Bibbia

I c_I =Abele

I f_I(x ) =padre dix,g_I(x , y ) =primogenito dix ey

I e una valutazioneφtale cheφ(X ) =Eva

I Alla fine si ottieneφI(g (f (c), X )) = Caino

(26)

FOL - semantica

I Siaφ una valutazione,X una variabile,I un’interpretazione e cI ∈ |I|

I Alloraφ[X 7→ cI]`e una valutazione identica a φa parte per il fatto che manda X in cI

I Il significato di una formula è un valore di verità che è definito induttivamente come segue

I Scriviamo I |=_φ F per indicare cheF `e vero rispetto aI eφ I |=_φ p(t₁, . . . , tn) sse hφI(t1), . . . , φI(tn)i ∈ pI

I |=_φ (¬F ) sse I 6|=_φ F

I |=_φ (F ↔ G ) sse I |=_φ (F → G ) e I |=_φ (G → F ) I |=_φ (∀X (F )) sse I |=_{φ[X 7→c}_I_] F per ogni c_I ∈ |I|

I |=_φ (∃X (F )) sse I |=_{φ[X 7→c}_I_] F per qualche cI ∈ |I|

(27)

FOL - semantica

I IfF `e una formula chiusa, il suo significato dipende solo dall’interpretazione

I La valutazione sar`a quindi omessa quando si considerano formule chiuse

I Un’interpretazione I`e dettamodello perF, indicato conI |= F, sse per ogni valutazioneφ si ha cheI |=_φ F

I Se F è un insieme di formule, un’interpretazione è unmodello di F sse è un modello per ogni F ∈ F

(28)

FOL - semantica

I Esempio (continuazione)

I SiaI un’interpretazione con|I| = Ne tale che

I Costanti: cI = 0

I Funzioni: fI(x ) = 1 + x (successore)

I Predicati: pI = {h1i, h3i, h5i, . . .}

I Allora il significato della formula p(c) ∧ p(f (c))in I `e come segue I |= p(c) ∧ p(f (c)) sse I |= p(c) e I |= p(f (c))

sse hφI(c)i ∈ pI e hφI(f (c))i ∈ pI

sse hφI(c)i ∈ pI e h1 + φI(c)i ∈ pI

sse h0i ∈ pI e h1i ∈ pI

I Ora, h1i ∈ pI mah0i 6∈ pI, quindiI non `e un modello per la formula

(29)

FOL - semantica

I La relazione di conseguenza logica|= tra insiemi di formule e formule pu`o essere esteso a FOL

I cos`ı come i concetti divalidità,soddisfacibilità,falsificabilità, contingenza einsoddisfacibilità

(30)

FOL - semantica

Equivalenze

I Le equivalenze mostrate per PL si possono estendere a FOL

I Ecco alcune equivalenze aggiuntive per FOL:

∀X (F ) ≡ ¬(∃X (¬F )) dualit`a dei quantificatori 1 (1)

∃X (F ) ≡ ¬(∀X (¬F )) dualit`a dei quantificatori 2 (2)

∀X (F ) ∧ (∀X )G ≡ ∀X (F ∧ G ) (3)

∃X (F ) ∨ (∃X )G ≡ ∃X (F ∨ G ) (4)

(∀X )(∀Y )F ≡ (∀Y )(∀X )F (5)

(∃X )(∃Y )F ≡ (∃Y )(∃X )F (6)

(∀X (F )) ∧ G ≡ ∀X (F ∧ G )^∗ (7)

(∀X (F )) ∨ G ≡ ∀X (F ∨ G )^∗ (8)

(∃X (F )) ∧ G ≡ ∃X (F ∧ G )^∗ (9)

(∃X (F )) ∨ G ≡ ∃X (F ∨ G )^∗ (10)

∗ si applica solo seX non `e libera inG