Appunti riassuntivi di Logica

4) CONSEGUENZA LOGICA (CONSEGUENZA TAUTOLOGICA)

F è conseguenza logica di G ( G |= F ) se F è vera su tutte le circostanze in cui G è vera.

F è conseguenza tautologica di G se la colonna di F ha valore 1 in tutte le righe in cui la colonna di

G ha valore 1 nella tavola di verità congiunta.

Es: A B |= A v B

∧

A B A B A v B

∧

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 1

PRINCIPIO DI RISOLUZIONE

Due disgiunzioni di letterali che contengono due letterali complementari (come B e B) hanno per

¬

conseguenza logica la disgiunzione formata dall’unione dei letterali, tolti i due complementari. In

ogni circostanza infatti abbiamo o L o L ma non entrambi insieme:

¬

- Se L è vero allora L è falso e quindi affinchè sia vera deve essere vero almeno Q ( 1< i <k ),

¬ i

quindi è vera anche la conseguenza;

- Se è vera L allora L è falso e quindi deve essere vero anche un P ( 1< i <n ), quindi è vera

¬ i

anche la conseguenza.

L v P v … v P

1 n

L v Q v … v Q

¬ 1 k

P v … v P v Q v … v Q

1 n 1 k

PRINCIPIO DI SOSTITUZIONE

≡ ≡

Se si sa che F G (sono logicamente equivalenti) allora S(F) S(G)

Proprietà

COMMUTATIVITA’

≡

P v Q Q v P

≡

P Q Q P

∧ ∧

ASSOCIATIVITA’

≡

P v ( Q v R ) ( P v Q ) v R

≡

P ( Q R ) ( P Q ) R

∧ ∧ ∧ ∧

IDEMPOTENZA

≡

P v P v Q P v Q

≡

P P Q P Q

∧ ∧ ∧

DISTRIBUTIVITA’

≡

P ( Q v R ) ( P Q ) v ( P R )

∧ ∧ ∧

≡

P ( Q R ) ( P Q ) ( P R )

v ∧ v ∧ v

FORMA NORMALE NEGATA (FNN)

Una formula F è in forma normale negata quando in F la negazione si applica solo ad atomi.

FORMA NORMALE CONGIUNTA (FNC)

Una formula F è in forma normale congiunta quando è una congiunzione di disgiunzioni di letterali.

FORMA NORMALE DISGIUNTA (FND)

Una formula F è in forma normale disgiunta quando è una disgiunzione di congiunzioni di letterali.

LIMITAZIONI DEL METODO DELLE TAVOLE DI VERITA’

1) Permette di riconoscere solo conseguenze tautologiche, non conseguenze logiche in generale;

n

2) Con n variabili proposizionali si creano 2 configurazioni.

DEDUZIONE NATURALE

Le prove si possono rappresentare come alberi.

SOTTOPROVE: pezzi di prova all’interno di altre prove.

CAMMINO:

In una sequenza di archi [(v ,v ), (v ,v ), (v ,v ), (v ,v )] per ogni i >= 1 il nodo v d’arrivo dell’arco i-esimo è

1 2 2 3 i i+1 n-1 n 1



il nodo sorgente dell’arco (i+1)esimo CONCATENAZIONE

ALBERO

Grafo diretto (con archi orientati) dove c’è un vertice distinto detto “radice” con la proprietà che per ogni

altro vertice esiste ed è unico il cammino dalla radice al vertice. Negli alberi i vertici si chiamano nodi.



A radice



C nodo



B sottoalbero



D E F foglie

Il sottoalbero è una parte di un albero che è a sua volta un albero.

REITERAZIONE

In una prova è permesso ripetere una formula (premessa o derivata).

PROVE COME ALBERI

- I nodi sono etichettati da formule

- La radice è etichettata dalla conclusione

- Le foglie sono etichettate dalle premesse

- Le sottoprove sono sottoalberi

SCARICARE LE PREMESSE

 Si possono scaricare premesse assunte come ipotesi temporanee quando la sottoprova che le

assume è conclusa;

 Non è permesso usare formule di una sottoprova completata le cui premesse sono state scaricate,

al di fuori della sottoprova stessa.

REGOLE / CRITERI PER COSTRUIRE LE PROVE



STRATEGIE DI PROVA da dimostrazioni automatiche



TATTICHE DI PROVA da dimostrazioni interattive

1- Chiedersi se la congettura sia vera (umano);



2- Cercare un controesempio (umano) se si trova allora si scarta la congettura e si può cercare di

dimostrare la negazione della congettura;



3- Partire dalle congetture (meccanico) goals.

CONNETTIVI LOGICI NEL LINGUAGGIO NATURALE

La logica è un linguaggio formale, molto più semplice di un linguaggio naturale. Ci sono infatti congiunzioni

appartenenti al linguaggio naturale che non corrispondono a connettivi logici. Anche quando sembra

esserci corrispondenza, essa è solo parziale.

Es1: 

“perché” Essendo una congiunzione che introduce una causale non si può costruire una tavola di verità,

perciò non ha connettivi in logica.

Es2:

L’implicazione nel linguaggio naturale non segue la tavola di verità costruita per l’implicazione logica.

BI-CONDIZIONALE (condizionale bi-direzionale, equivalenza, doppia

implicazione) P Q



“P se e solo se Q” , “P è equivalente a Q”, …

Relazione binaria con proprietà:

- RIFLESSIVA

- SIMMETRICA

- TRANSITIVA

- SOSTITUTIVA

TEOREMA DI DEDUZIONE P |- Q

Dimostrazione di Q da P, fatta per dimostrare che Q è conseguenza logica di P ( P |= Q ). Scrivere ‘P |= Q’

vuol dire che in tutte le circostanze in cui P è vero anche Q è vero. 

P |- Q se e solo se |= P Q



P |- Q se e solo se |= P Q

P |= Q 

In tutte le circostanze in cui P è vera allora Q è vera, quindi ‘ P Q ’ è vera. In tutte le circostanze in cui P è

  

falsa, ‘ P Q ’ è vera. ‘ P Q ’ è vera in tutte le circostanze (‘|= P Q ’).



|= P Q

 

‘ P Q ’ è vera in tutte le circostanze, per ogni circostanza in cui P è vera, ‘ P Q ’ è vera, perché è vera in

tutte le circostanze (‘ P |= Q ’ ).

IMPLICATURE CONVERSAZIONALI

1) La disgiunzione viene letta come ESCLUSIVA quando non lo è

Un’implicazione nel linguaggio naturale non è una vera implicazione, ma un’implicatura conversazionale, se

la conversazione può continuare in un modo che nega l’implicazione.

Es: “Con il panino si ha diritto ad una insalata o ad una zuppa.”

2) “A meno che” viene letto come “se e solo se”

Es: “Aldo è a casa a meno che Chiara sia in biblioteca.”



¬InBiblioteca(chiara) Acasa(Aldo) ___________ CORRETTA IN LOGICA



¬InBiblioteca(chiara) Acasa(Aldo) _________ NON CORRETTA IN LOGICA

3) “Solo se” viene letto come “se e solo se”

Es: “Puoi mangiare il dolce solo se prima finisci la minestra.”



Mangiare(dolce) Finita(minestra) ___________ CORRETTA IN LOGICA



Mangiare(dolce) Finita(minestra) _________ NON CORRETTA IN LOGICA



Finita(minestra) Mangiare(dolce) Mangiare(dolce) Finita(minestra)

0 0 1

0 1 0

1 0 1

1 1 1

ADEGUATEZZA O COMPLETEZZA VERO-FUNZIONALE DEI CONNETTIVI

1) QUANTI CONNETTIVI POSSIAMO AVERE IN UN LINGUAGGIO LOGICO?

|A| = n , |B| = k , allora :

 

A B = { f | f: A B }

 n

|A B| = k

2) QUALI SONO GLI INSIEMI DI CONNETTIVI ADEGUATI O COMPLETI?

Non conviene minimizzare l’insieme dei connettivi perché eliminandone alcuni è molto più complicato

costruire prove.

Es: ELIMINAZIONE DELLA CONGIUNZIONE

∧

P Q Intro

∧

P Q ∧

Con l’uso dell’introduzione della congiunzione si può creare “P Q” in un solo passaggio. Se non si potesse usare

questo connettivo: ⊥ ⊥

¬ Intro ¬ Intro

P P Q Q

⊥ ⊥ v elim

¬P v ¬Q ⊥ ¬ Intro

¬(¬P v ¬Q)

La prova risulta notevolmente appesantita senza l’uso del connettivo logico ‘∧’.

Esempi di insiemi completi: ∧,

{ ¬ }

∧,

{ ¬ }

{ v , ¬ }

 ⊥

{ , }

PROPRIETA’ IMPLICAZIONE

 

P Q ≡ ¬Q ¬P Contropositivo



P Q ≡ ¬P v Q

 ∧

¬ (P Q) ≡ P ¬Q

  

∧ (Q P)

P Q ≡ (P Q)

 ∧ ∧

P Q ≡ (P Q) v (¬P ¬Q)

DOPPIA IMPLICAZIONE

Introduzione

P Q

Π Π

Q P  Intro



P Q

Eliminazione 

P P Q  Elim

Q

Oppure 

P P Q  Elim

P SISTEMA DI DEDUZIONE F

, ,

∧, ⊥,

- Regole di introduzione ed eliminazione di V, ¬, = ;

- Ragionamento valido: se tutte le premesse sono vere allora la conclusione è vera;

- Ragionamento corretto: ragionamento valido le cui premesse sono vere;

- Insieme di connettivi completi/adeguati: quando permettono di esprimere qualsiasi altro

connettivo;

PROPRIETA’ DI UN SISTEMA DI DEDUZIONE

 Un sistema di deduzione si dice corretto quando da delle premesse (P) si arriva a una conclusione

(S). Perciò si potrà dire che la conclusione è conseguenza logica delle premesse. Ogni dimostrazione

in F è un ragionamento valido;

es: se P |- S allora P |= S

 Un sistema di deduzione F si dice completo quando esiste l’implicazione opposta, cioè si riesce a

dimostrare una cosa vera;

es: se P |= S allora P |- S

 S è conseguenza tautologica di P quando nella tavola di verità congiunta S è vera ovunque dove P è

vera. QUANTIFICATORI

Nel linguaggio naturale sono elementi che determinano una quantità.

ES: “ognuno”, “tutti”, “ciascuno”, “tre”, “la maggior parte”

Nella logica al primo ordine ci sono:

∀

 

“ ” “per ogni”;

∃

 

“ ” “esiste”;

QUANTIFICATORI E VARIABILI

Una variabile si dice: ∀x

- LEGATA se cade nel campo di applicazione di un quantificatore; Piccolo(x)

- LIBERA se non cade nel campo di applicazione di un quantificatore; Piccolo(x)

OCCORRENZA DELLE VARIABILI

Se una variabile è legata, non ha importanza come si chiami perché l’importante è il quantificatore.

Data una formula F:

 Var(F) : variabili che occorrono in F;

 Libere(F) : variabili libere in F;

 Legate(F) : variabili legate in F;

es:

F Var(F) = Libere(F)

∧

Libere(F G) Libere(F) U Libere(G)

Libere(∀x F) Libere(F) – {x}

INTERPRETAZIONE DI VARIABILI LEGATE

∀xF soddisfatta se esiste almeno un elemento nel dominio del modello per cui F è soddisfatta;

∃xF soddisfatta se per tutti gli elementi nel dominio del modello è soddisfatta;

Si dice formula universale soddisfatta a vuoto se l’antecedente è falsa, quindi l’implicazione è vera.

4 FORMULE QUANTIFICATE UNIVERSALMENTE

1. Tutti i P sono Q

2. Alcuni P sono Q

3. Nessun P è Q

4. Alcuni P non sono Q

Perché si chiama logica al primo ordine?

Si chiama così perché i quantificatori non si applicano a funzioni e predicati ma solo a oggetti e individui.

∅

ENUNCIATO: formula dove tutte le variabili sono quantificate. Libere(F) =

FORMA VERO-FUNZIONALE DI UNA FORMULA

Si ottiene sostituendo le sottoformule quantificate e gli atomi con atomi proporzionali.



∀x

Es: Cubo(x) v Piccolo(x) A v B

TAUTOLOGIA

Un enunciato è una tautologia se e solo se la sua formula vero funzionale è una tautologia.

LOGICA PROPOSIZIONALE LOGICA AL PRIMO ORDINE GENERALE

Tautologia Validità al primo ordine Verità logica

Conseguenza tautologica Conseguenza logica al primo ordine Conseguenza logica

Equivalenza tautologica Equivalenza logica al primo ordine Equivalenza logica

Solo con assiomi si possono riconoscere tautologie in logica al primo ordine.

ASSIOMI DELL’IDENTITA’

∀x

1) x = x 

∀x,∀y

2) x = y y = x



∀x,∀y,∀z ∧

3) x = y y = z x = z



∀x,∀y

4) x = y P(x) = P(y)

METODO ASSIOMATICO: scrivere formule che si assumono vere e che descrivono il significato dei predicati.

POSTULATI DI SIGNIFICATO: assiomi che descrivono il significato di un predicato.

IL SIGNIFICATO DEI QUANTIFICATORI



∀ ∧

infiniti (congiunzione possibilmente infinita)



∃ ∨

infiniti (disgiunzione possibilmente infinita)

Poiché una formula è finita non possiamo scrivere una congiunzione che dica che ogni elemento di S

soddisfa la proprietà P.

LEGGI DI DE MORGAN

∃x

¬(∀x F[x]) ≡ ¬F[x]

∀x

¬(∃x F[x]) ≡ ¬F[x]

N.B: i nomi delle variabili quantificate non hanno rilevanza!

QUANTIFICATORI NULLI

∀x F ≡ F

∃x F ≡ F

Se x non compare in F è inutile il quantificatore.

FORMA NORMALE PRENESSA

Formata da prefisso e matrice, dove il prefisso è una sequenza Q x Q x Q x … Q x e la matrice è una

1 1 2 2 3 3 n n

formula senza quantificatori.

Es: ∀x ∃x [¬P(x) v Q(y)]

REGOLE DI INTRODUZIONE ED ELIMINAZIONE DEI QUANTIFICATORI

∃

INTRODUZIONE DI

∃

ELIMINAZIONE DI Dove c deve essere una costante nuova che non appare nella

dimostrazione.

∀

INTRODUZIONE DI

Dove c deve essere una costante nuova che non appare nella dimostrazione.

∀

ELIMINAZIONE DI REGOLE PER UNA CORRETTA DIMOSTRAZIONE