Logica proposizionale Proposizione

Logica proposizionale

Proposizione: frase compiuta che è sempre o vera o falsa.

Connettivi

Posti in ordine di precedenza: ¬not , ∧ and  , ∨ or , ⇒ implica , ⇔ doppia implicazione

Sintassi

Le proposizioni sono costituite da un alfabeto che  comprende:

• lettere enunciative: A, B, ...

• connettivi

• simboli ausiliari: (   ,   )

Spesso, si aggiungono alle lettere enunciative 

⊤=VERO=1, ⊥=FALSO=0

All'interno dell'alfabeto è possibile definire formule ben  formate (fbf), definite ricorsivamente:

• ogni lettera enunciativa è una fbf

• se A è una fbf anche  ¬A è una fbf

• se A e B sono fbf, anche 

 A∧B , A∨B  , A ⇒ B ,  A⇔ B sono fbf

• nient'altro è una fbf.

Semantica

Interpretazione: funzione v : fbf {0, 1} che calcola il valore di verità di una fbf.

Fissare un'interpretazione corrisponde ad attribuire un valore di verità a tutte le lettere enunciative e da questi passare  al valore di verità della fbf tramite le tavole di verità dei connettivi.

Modello: interpretazione (insieme di valori associati alle lettere enunciative) tale che la fbf assume valore 1.

Una fbf si dice:

• tautologia se ogni interpretazione è un modello

• soddisfacibile se almeno una sua interpretazione è un modello.

• insoddisfacibile se non ammette modelli

Sia  un insieme di fbf. Si dice modello di  un'interpretazione v t.c. v a=1 ∀ a∈ .  si dice 

soddisfacibile se ha almeno un modello, insoddisfacibile se esiste almeno una sua interpretazione che non è modello.

Si dice che A è conseguenza semantica di  e si scrive  ∣= A se ogni modello di  è un modello di A.

Se in una formula A si sostituisce una sottoformula B con una formula B' equivalente a B si ottiene una formula A'  equivalente ad A.

Ogni fbf ammette una fbf equivalente che usa solo uno degli insiemi di connettivi detti adeguati o funzionalmente  completi:  {¬ , ∧}^,{¬ , ∨}^,{¬ , ⇒ }

Equivalenze fondamentali

¬¬A≡ A A∧ A≡ A A∧ B≡B∧A

 A∧B∧C ≡A∧ B∧C  A∧ A∨B≡A A∧ B∨C≡ A∧B∨ A∧C 

¬ A∧B≡¬A∨¬B A ⇒ B≡¬A∨ B

A⇒ B≡¬ A∧¬B B≡¬A∧ A∨B

Teoria formale

Una teoria formale è definita quando sono fissati:

• un insieme di simboli (alfabeto)

• un insieme di stringhe privilegiate di simboli (fbf)

• un insieme privilegiato di fbf (assiomi)

• un insieme di regole di riscrittura (o di inferenza) che in presenza di un certo insieme di fbf permetta di scriverne  in modo algoritmico altre (dedotte dalle precedenti).

Data una teoria formale H definiamo:

• dimostrazione nella teoria formale H: una sequenza finita di fbf che siano assiomi o formule dedotte dalle  precedenti tramite le regole di inferenza

• teorema della teoria (si scrive ├HA ): una fbf A che sia l'ultima formula di una dimostrazione

Dato un insieme  di fbf diciamo che una formula A è deducibile in H da   (e scriviamo   ├HA ) se esiste  una sequenza finita di fbf che siano o assiomi o formule di  o formule dedotte dalle precedenti la cui ultima  formula sia A. Se  ├HA allora A deve essere vera tutte le volte che lo è  .

Teoria L

È una teoria che permette di ottenere come teoremi tutte e sole le tautologie e permette di dedurre da un insieme  di formule tutte e sole le conseguenze semantiche di 

Simboli di L

lettere enunciative: A, B, ...

connettivi:  ¬ , ⇒ parentesi:  (  ,  )

Formule ben formate di L

lettere enunciative

se A è una fbf anche ¬A è una fbf

se A e B sono fbf anche  A⇒ B è una fbf nient'altro è una fbf

(In realtà si accettano anche gli altri connettivi, ma  pensati come abbreviazioni di formule con solo ¬ , ⇒ )

Assiomi di L

A1. A ⇒ B⇒ A

A2.  A⇒ B ⇒ C⇒ A⇒ B⇒ A ⇒C 

A3. ¬A ⇒¬B ⇒¬A⇒ B⇒ A

Regola di inferenza di L

Modus Ponens (MP): dalle due formule A e  A⇒ B  si riscrive  B

Teorema di correttezza e completezza

La teoria formale L è corretta (tutti i suoi teoremi sono tautologie), completa (tutte le tautologie sono teoremi di L) e  decidibile (esiste un algoritmo che con un numero finito di passi permette di decidere se una data formula è un 

teorema o non è un teorema della teoria).

Teorema di correttezza e completezza forte: sia  un insieme di fbf.  ∣= A se e solo se  ├LA Teorema di deduzione (sintattica): sia  =∪

{

}

Risoluzione

• Letterale: una lettera enunciativa o la negazione di una lettera enunciativa

• Clausola: disgiunzione (finita) di letterali

•  Clausola vuota: una clausola che non contiene letterali. Si indica con □

• una fbf si dice in forma a clausole se è scritta come congiunzione di clausole (forma POS, prodotto di somme) ed  in tal caso sarà denotata come insieme di insiemi; ogni formula ammette una formula equivalente in forma a  clausole.

Date le clausole C1, C2 ed R si dice che R è una risolvente di C1 e C2 se esiste un letterale  L ∈C₁ tale che 

¬L ∈C₂ e  R=C₁∖

{

}

{

}

Una derivazione per risoluzione  ├RC  della clausola C da  è una sequenza di clausole di cui l'ultima è C e  che o stanno in  o sono ottenute come risolvente da clausole precedenti.

TEO: Un insieme di clausole  è insoddisfacibile se e solo se  ├R□

Una formula A è semanticamente deducibile da  (si scrive ∣=A ) se e solo se   ∪

{

}

Linguaggio del I ordine

Alfabeto

• costanti: a, b, ...

• variabili: x, y, ...

• lettere funzionali: fin (con i,n interi naturali)

• lettere predicative: Ain (con i,n interi naturali)

• connettivi: ¬, ∧ , ∨ , ⇒ , ⇔

• quantificatori:  ∀ x universale , ∃ x esistenziale

• simboli ausiliari: ( , )

Con questi simboli definiamo ricorsivamente i termini:

• ogni costante è un termine

• ogni variabile è un termine

• se t1, t2,...,tn sono termini anche fin(t1, t2, ..., tn) è un  termine

Con i simboli e i termini possiamo costruire delle frasi  dette, formule atomiche, del tipo Ajm(t1, t2, ..., tm).

Formule ben formate:

• ogni formula atomica è una fbf

• se A è una fbf, anche  ¬A , ∀ x A ,∃ x A sono  fbf.

• se A e B sono fbf anche

 A∧B , A∨B  , A ⇒ B ,  A⇔ B sono fbf.

I quantificatori hanno precedenza immediatamente  successiva alla negazione.

Data una formula che contenga un quantificatore, la  sottoformula a cui quel quantificatore si riferisce è detta  campo d'azione del quantificatore.

Una variabile x si dice vincolata se è nel campo d'azione di un quantificatore su x. Altrimenti si dice libera.

Una formula senza occorrenze libere di variabili si dice chiusa. Facendo precedere una formula non chiusa con  quantificatori sulle variabili libere si può ottenere la chiusura universale ( ∀ ) o esistenziale ( ∃ ).

Interpretazione: un insieme D (dominio) e una legge che associa ad ogni costante un elemento di D, ad ogni lettera  funzionale con apice n un'operazione di arità n su D, ad ogni lettera predicativa una relazione su D.

Una fbf A si dice logicamente valida se è vera in ogni interpretazione.

Una formula si dice esempio di tautologia se è ottenuta da una tautologia sostituendo formule del primo ordine alle  lettere enunciative della tautologia. Un esempio di tautologia è sempre una formula logicamente valida.

Due formule si dicono semanticamente equivalenti se in ogni interpretazione sono soddisfatte dagli stessi  assegnamenti di valori alle variabili.

Forma normale prenessa

Si dice in forma normale prenessa una formula in cui tutti i quantificatori sono posti in testa.

A[y/x] = A[x] in cui le occorrenze libere di x sono sostituite da y.

Per ottenere una formula in forma normale premessa si utilizzano ripetutamente queste equivalenze:

¬∀ x A  è equivalente a ∃ x ¬A ¬∃ x A  è equivalente a  ∀ x ¬A

∀ x A x ⇒ B  è equivalente a ∃ y A[ y/ x]⇒ B ∃ x A x⇒ B  è equivalente a ∀ y A [y/ x]⇒ B

B ⇒∀ x A x è equivalente a ∀ y B ⇒ A[ y/ x] B ⇒∃ x A x è equivalente a ∃ y B⇒ A[ y/ x]

Forma di Skolem

Una formula si dice in forma di Skolem se è in forma normale prenessa e senza quantificatori esistenziali.

• portare A in forma prenessa

• eliminare i quantificatori esistenziali in testa e sostituire le relative variabili con constanti

• eliminare i restanti quantificatori esistenziali e sostituire le relative variabili con funzioni delle variabili dei  quantificatori universali che li precedono. Es:  ∀ x ∀ y∃ z∀ w A₁⁴ x , y , z , w diventa 

∀ x ∀ y∀ w A₁⁴ x , y , f₁² x , y ,w

Una forma di Skolem non è semanticamente equivalente alla formula da cui deriva.

Teoria formale K per logiche del I ordine

È una teoria corretta ├ A ⇒ ∣= A  e completa  ∣= A ⇒ ├ A

Simboli

• lettere enunciative: A, B, ...

• connettivi: ¬, ⇒

• quantificatore universale:  ∀ x universale

• parentesi: ( , )

Formule ben formate

• lettere enunciative

• se A è una fbf anche (~A) è fbf

• se A è una fbf anche  ∀ x A è fbf

• se A e B sono fbf anche  A ⇒ B è fbf

• nient'altro è una fbf

Assiomi logici su K

A1.  A⇒B ⇒ A

A2.   A ⇒B ⇒C ⇒ A ⇒ B ⇒ A ⇒C 

A3.  ¬A⇒ ¬B⇒ ¬A⇒ B⇒ A

A4.  ∀ x A x⇒ A[t / x] dove t è termine libero per x  in A(x)

A5.  ∀ x A⇒ B ⇒ A⇒ ∀ x B purché non ci siano  occorrenze libere di x in A.

Regole di inferenza di K

• Modus Ponens (MP) 

Dalle due formule  A  ed  A⇒ B  si riscrive  B

• Generalizzazione (Gen). Dalla formula A si riscrive 

∀ x A

Una teoria K del I ordine può avere degli assiomi propri (possono essere visti come un insieme  di schemi da  prendere come premesse)

Un calcolo dei predicati del I ordine è una teoria del I ordine senza assiomi propri.

Ogni calcolo dei predicati del I ordine è consistente, ovvero non esiste una formula A tale che nel calcolo dei  predicati del primo ordine si possa dedurre sia A sia ~A.

In ogni teoria del I ordine K possono essere dimostrate tutte le formule che si deducono da teoremi di L  sostituendo ordinatamente lettere enunciative uguali con le stesse fbf del primo ordine. Cioè, ogni esempio di  tautologia è un teorema di K.

A è un teorema di una teoria del I ordine sse lo è anche la sua chiusura universale.

Un calcolo predicativo del I ordine K è corretto (teorema => fbf logicamente valida) e completo (fbf log val => teo).

Non è decidibile, cioè non è possibile stabilire algoritmicamente se una data formula è un teorema della teoria.

Si dice modello ogni interpretazione in cui ogni assioma proprio della teoria sia vero.

Teoria del I ordine con identità

Viene così definita una teoria del primo ordine in cui sia presente un predicato A12 interpretato come uguaglianza e  con gli schemi A6 e A7 come assiomi propri.

A6.  ∀ x A₁² x , x

A7.  A₁² x , y⇒ A x , x⇒ A x ,[ y/ x] dove A(x,x) indica una qualsiasi formula con occorrenze libere di x (il fatto  che x sia ripetuto due volte indica che le occorrenze libere di x sono suddivise arbitrariamente in due gruppi) ed  A(x,[y/x]) indica che in A(x,x) le occorrenze libere di x del secondo gruppo sono state sostituite con y.

Le strutture algebriche possono essere presentate come teorie del primo ordine con identità in cui si introducono tante  lettere funzionali quante sono le operazione di  .

Le proprietà di cui godono le varie strutture dovranno essere date come assiomi propri della teoria insieme agli  assiomi A6 e A7.