Fondamenti di informatica - Laurea triennale Informatica/Quantificatori annidati

Ii quantificatori annidati sono espressioni logiche che contengono più quantificatori uno dentro l’altro, come:

• ∀x ∀y P(x,y)
• ∀x ∃y P(x,y)
• ∃x ∀y P(x,y)
• ∃x ∃y P(x,y)

L’idea principale è che, quando una proposizione dipende da più variabili, servono più quantificatori per descriverla in modo preciso.

Significato dei principali tipi di quantificatori annidati

∀x ∀y P(x,y)

Vuol dire: per ogni x e per ogni y, P(x,y) è vera.

Esempio:

Nota: se dentro la formula c’è un’implicazione, la sua negazione va trattata correttamente.

Un gioco logico come esempio

Questo "gioco logico" consente di capire intuitivamente il valore di verità di una proposizione con quantificatori:

• se il quantificatore è ∀, sceglie l’avversario;
• se il quantificatore è ∃, scegli tu.

Dopo che tutti i valori sono stati scelti, si controlla se P è vera o falsa.

L’idea è:

• se puoi sempre vincere, la proposizione è vera;
• se l’avversario può sempre costringerti a perdere, la proposizione è falsa.

Questo metodo aiuta a capire bene il significato operativo dei quantificatori.

Suggerimenti pratici per le dimostrazioni

• per ∀∀, bisogna ragionare con elementi arbitrari;
• per mostrare che ∀∀ è falsa, basta un controesempio;
• per ∀∃, si prende un elemento arbitrario x e si cerca un y adatto;
• per negare formule con quantificatori annidati, si scambiano i quantificatori e si nega la parte interna.
• Idea centrale del capitolo

Punti chiave

• l’ordine dei quantificatori cambia il significato;
• ogni forma ha un preciso criterio di verità o falsità;
• i controesempi sono fondamentali;
• le negazioni si ottengono scambiando ∀ con ∃ e negando la proposizione;
• questi concetti possono essere interpretati anche con algoritmi e con un gioco logico.