logo

Logica dei predicati

La logica dei predicati si occupa dei predicati, che sono proposizioni, costituiti da variabili.

Logica del predicato - Definizione

Un predicato è un'espressione di una o più variabili determinate su un dominio specifico. Un predicato con variabili può essere reso una proposizione autorizzando un valore alla variabile o quantificando la variabile.

Di seguito sono riportati alcuni esempi di predicati.

  • Consideriamo che E(x, y) denoti 'x = y'
  • Consideriamo X(a, b, c) denotato 'a + b + c = 0'
  • Consideriamo che M(x, y) denoti 'x è sposato con y'.

Quantificatore:

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

Quantificatore esistenziale:

Se p(x) è una proposizione sull'universo U. Allora è indicato come ∃x p(x) e letto come 'Esiste almeno un valore nell'universo della variabile x tale che p(x) è vero. Il quantificatore ∃ è chiamato quantificatore esistenziale.

Esistono diversi modi per scrivere una proposizione, con un quantificatore esistenziale, ovvero

(∃x∈A)p(x) o ∃x∈A tale che p (x) o (∃x)p(x) o p(x) sia vero per qualche x ∈A.

Quantificatore universale:

Se p(x) è una proposizione sull'universo U. Allora viene indicato come ∀x,p(x) e letto come 'Per ogni x∈U,p(x) è vero.' Il quantificatore ∀ è chiamato quantificatore universale.

Esistono diversi modi per scrivere una proposizione, con un quantificatore universale.

∀x∈A,p(x) o p(x), ∀x ∈A Oppure ∀x,p(x) o p(x) è vero per ogni x ∈A.

Negazione delle proposizioni quantificate:

Quando neghiamo una proposizione quantificata, cioè quando una proposizione universalmente quantificata viene negata, otteniamo una proposizione quantificata esistenzialmente, e quando una proposizione quantificata esistenzialmente viene negata, otteniamo una proposizione quantificata universalmente.

Le due regole per la negazione della proposizione quantificata sono le seguenti. Queste sono anche chiamate Legge di DeMorgan.

Esempio: negare ciascuna delle seguenti proposizioni:

1.∀x p(x)∧ ∃ y q(y)

Sole: ~.∀x p(x)∧ ∃ y q(y))
≅~∀ x p(x)∨∼∃yq (y) (∴∼(p∧q)=∼p∨∼q)
≅ ∃ x ~p(x)∨∀y∼q(y)

2. (∃x∈U) (x+6=25)

Sole: ~( ∃x∈U) (x+6=25)
≅∀ x∈U~ (x+6)=25
≅(∀ x∈U) (x+6)≠25

ankita dave

3. ~( ∃ x p(x)∨∀ y q(y)

Sole: ~( ∃ x p(x)∨∀ y q(y))
≅~∃ x p(x)∧~∀ y q(y) (∴~(p∨q)= ∼p∧∼q)
≅ ∀ x ∼ p(x)∧∃y~q(y))

Proposizioni con quantificatori multipli:

La proposizione avente più di una variabile può essere quantificata con più quantificatori. I molteplici quantificatori universali possono essere disposti in qualsiasi ordine senza alterare il significato della proposizione risultante. Inoltre, i molteplici quantificatori esistenziali possono essere disposti in qualsiasi ordine senza alterare il significato della proposizione.

La proposizione che contiene sia quantificatori universali che esistenziali, l'ordine di tali quantificatori non può essere scambiato senza alterare il significato della proposizione, ad esempio, la proposizione ∃x ∀ y p(x,y) significa 'Esiste qualche x tale che p (x, y) è vero per ogni y.'

Esempio: Scrivi la negazione per ciascuno dei seguenti. Determina se l'affermazione risultante è vera o falsa. Supponiamo U = R.

1.∀ x ∃ m(x2

Sole: Negazione di ∀ x ∃ m(x22≧m). Il significato di ∃ x ∀ m (x2≧m) è che esiste per qualche x tale che x2≧m, per ogni m. L'affermazione è vera perché esiste un x maggiore tale che x2≧m, per ogni m.

2. ∃ m∀ x(x2

Sole: Negazione di ∃ m ∀ x (x22≧m). Il significato di ∀ m∃x (x2≧m) è che per ogni m esiste per qualche x tale che x2≧m. L'affermazione è vera poiché per ogni m esiste un x maggiore tale che x2≧m.