Fondamenti di informatica - Laurea triennale Informatica/Quantificatori

La logica proposizionale studiata in precedenza non basta per descrivere molte affermazioni di matematica e informatica, perché queste spesso contengono variabili. Per affrontare questo problema si introducono le funzioni proposizionali (o predicati) e i quantificatori.

Funzioni proposizionali e dominio del discorso

Una funzione proposizionale P(x) è un enunciato che contiene una variabile x, tale che, sostituendo a x un valore ammesso, si ottiene una proposizione vera o falsa.

L’insieme dei valori possibili di x si chiama dominio del discorso.

Per esempio, l’enunciato “x è un intero dispari” è una funzione proposizionale: se sostituiamo a x un intero positivo, otteniamo ogni volta una proposizione ben definita. Tuttavia, P(x) da sola non è né vera né falsa finché non si assegna un valore a x.

Quantificatore universale

Il simbolo ∀ significa “per ogni” o “per tutti”.

L’enunciato

∀xP(x)

significa che P(x) è vera per ogni elemento del dominio.

• È vero se P(x) vale per tutti gli elementi.
• È falso se esiste almeno un elemento per cui P(x) è falsa.

Un valore che rende falsa P(x) si chiama controesempio.

Per dimostrare che un enunciato universale è vero, bisogna mostrare che la proprietà vale per un elemento arbitrario del dominio.

Per dimostrare che è falso, basta trovare un controesempio.

Variabili libere e variabili vincolate

In una funzione proposizionale P(x), la variabile x è detta libera.

In un enunciato quantificato come ∀xP(x), la variabile x è detta vincolata dal quantificatore.

Un’espressione con variabili libere non è ancora una proposizione; un’espressione senza variabili libere, invece, ha un valore di verità ed è quindi una proposizione.

Quantificatore esistenziale

Il simbolo ∃ significa “esiste” o “per almeno un”.

L’enunciato

∃xP(x)

significa che P(x) è vera per almeno un elemento del dominio.

• È vero se esiste almeno un valore che rende vera P(x).
• È falso se P(x) è falsa per tutti gli elementi del dominio.

Per provare che un enunciato esistenziale è vero, basta esibire un esempio.

Per provarlo falso, bisogna mostrare che nessun elemento del dominio soddisfa la proprietà.

Pseudocodice e quantificatori

Esiste un’analogia tra quantificatori e algoritmi:

• Per verificare ∀xP(x), si controllano tutti gli elementi del dominio e si restituisce false appena si trova un controesempio; altrimenti si restituisce true.
• Per verificare ∃xP(x), si controllano gli elementi finché se ne trova uno che soddisfa P(x); in quel caso si restituisce true. Se nessuno la soddisfa, si restituisce false.

Negazione dei quantificatori: leggi di De Morgan generalizzate

E' possibile generalizzare le leggi di De Morgan utilizzando i quantificatori:

• La negazione di ∀xP(x) (ovvero ¬(∀xP(x)) ) è equivalente a ∃x¬P(x) cioè: “non è vero che tutti…” equivale a “esiste almeno uno che non…”.
• La negazione di ∃xP(x) (ovvero ¬(∃xP(x)) ) è equivalente a ∀x¬P(x) cioè: “non esiste alcuno che…” equivale a “tutti non…”.

Queste equivalenze sono molto utili per negare correttamente enunciati in linguaggio naturale.

Ambiguità fra logica e linguaggio naturale

Alcune frasi tipiche del linguaggio comune possono essere ambigue in ambito logico. Per esempio, la frase:

“Non tutto quel che luccica è oro”

non significa “ogni cosa che luccica non è oro”, ma piuttosto “esiste qualcosa che luccica e non è oro”.

La differenza dipende da dove si applica la negazione: al predicato oppure all’intera affermazione.

Quantificatori come generalizzazione di congiunzioni e disgiunzioni

Un enunciato universale ∀xP(x) può essere visto come una grande congiunzione:

P(x1​)∧P(x2​)∧P(x3​)∧…

Un enunciato esistenziale ∃xP(x) può essere visto come una grande disgiunzione:

P(x1​)∨P(x2​)∨P(x3​)∨…

In questo senso, i quantificatori estendono le operazioni logiche già viste.

Regole di inferenza con quantificatori

Esistono alcune regole di inferenza per ragionare con enunciati quantificati:

• Istanza universale: da ∀xP(x) si può dedurre P(d), se d appartiene al dominio.
• Generalizzazione universale: se P(d) vale per ogni elemento arbitrario d, allora si può concludere ∀xP(x).
• Istanza esistenziale: da ∃xP(x) si può considerare un elemento del dominio per cui P è vera.
• Generalizzazione esistenziale: da P(d) si può concludere ∃xP(x).

Queste regole si combinano con quelle della logica proposizionale, come modus tollens e sillogismo disgiuntivo.

Idee fondamentali da ricordare

• Le funzioni proposizionali diventano proposizioni solo quando la variabile viene quantificata o sostituita.
• ∀ richiede che la proprietà valga per tutti gli elementi.
• ∃ richiede che la proprietà valga per almeno un elemento.
• Per smentire un enunciato universale basta un controesempio.
• Per smentire un enunciato esistenziale bisogna mostrare che non esistono esempi.
• Le negazioni dei quantificatori seguono le leggi di De Morgan generalizzate.