Matematica discreta - Logica predicativa

Predicate Logic si occupa di predicati, che sono proposizioni contenenti variabili.

Logica del predicato - Definizione

Un predicato è un'espressione di una o più variabili definite su un dominio specifico. Un predicato con variabili può essere proposto sia assegnando un valore alla variabile sia quantificando la variabile.

Di seguito sono riportati alcuni esempi di predicati:

  • Sia E (x, y) "x = y"
  • Sia X (a, b, c) "a + b + c = 0"
  • Sia M (x, y) "x è sposato con y"

Formula ben formata

Well Formed Formula (wff) è un predicato che contiene uno dei seguenti:

  • Tutte le costanti proposizionali e le variabili proposizionali sono wffs

  • Se x è una variabile e Y è un wff, $ \ forall x Y $ e $ \ esiste x Y $ sono anche wff

  • Il valore di verità e i valori falsi sono wffs

  • Ogni formula atomica è un wff

  • Tutti i connettivi che collegano wffs sono wffs

Quantificatori

La variabile dei predicati viene quantificata da quantificatori. Esistono due tipi di quantificatori nella logica dei predicati: quantificatore universale e quantificatore esistenziale.

Quantificatore universale

Il quantificatore universale afferma che le dichiarazioni all'interno del suo ambito sono vere per ogni valore della variabile specifica. È indicato dal simbolo $ \ forall $.

$ \ forall x P (x) $ viene letto come per ogni valore di x, P (x) è vero.

Example - "L'uomo è mortale" può essere trasformato nella forma proposizionale $ \ forall x P (x) $ dove P (x) è il predicato che denota x è mortale e l'universo del discorso è tutto uomini.

Quantificatore esistenziale

Il quantificatore esistenziale afferma che le dichiarazioni all'interno del suo ambito sono vere per alcuni valori della variabile specifica. È indicato dal simbolo $ \ esiste $.

$ \ esiste x P (x) $ viene letto come per alcuni valori di x, P (x) è vero.

Example - "Alcune persone sono disoneste" può essere trasformato nella forma proposizionale $ \ esiste x P (x) $ dove P (x) è il predicato che denota x è disonesto e l'universo del discorso è alcune persone.

Quantificatori annidati

Se utilizziamo un quantificatore che appare nell'ambito di un altro quantificatore, viene chiamato quantificatore annidato.

Example

  • $ \ forall \ a \: \ esiste b \: P (x, y) $ dove $ P (a, b) $ denota $ a + b = 0 $

  • $ \ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c) $ dove $ P (a, b) $ $ denota $ a + (b + c) = ( a + b) + c $

Note - $ \ forall \: a \: \ esiste b \: P (x, y) \ ne \ esiste a \: \ forall b \: P (x, y) $