Logica dei predicati: la negazione

Definizioni

Osservazione 1: Sia data una proposizione $q$. Sappiamo dalla logica proposizionale che è lecito considerare la sua negazione \(\overline{q}\); dal momento però che in logica dei predicati $q$ può possedere una struttura interna complessa, con uno o più predicati e/o quantificatori, occorre scoprire in che modo negare tutti questi nuovi simboli.

Definizione 1: Negazione di un predicato.
Si consideri un generico predicato $p$; si chiama negazione di $p$ e si indica con il simbolo \(\overline{p}\) un nuovo predicato tale che \(\overline{p}(x)\) se e soltanto se la proprietà espressa da $p$ non vale per la variabile $x$.

Osservazione 2: La definizione 1 dice, in buona sostanza, che se un certo predicato $p$ non vale per $x$, allora per $x$ vale un altro predicato \(\overline{p}\), il quale esprime la proprietà “per $x$ non vale $p$”. Il fatto che un determinato predicato non valga è cioè esso stesso un predicato.

Definizione 2: Negazione del quantificatore universale.
Siano dati un insieme $A$ e un predicato $p$; come sappiamo essi possono essere utilizzati per scrivere la formula \(\forall x\in A,p(x)\). Per tutte le formule di questo tipo vale l’equivalenza seguente:
\[
\overline{\forall x\in A, p(x)}\leftrightarrow\exists x\in A:\overline{p}(x)
\]

Definizione 3: Negazione del quantificatore esistenziale.
Siano dati un insieme $A$ e un predicato $p$; come sappiamo essi possono essere utilizzati per scrivere la formula \(\exists x\in A:p(x)\). Per tutte le formule di questo tipo vale l’equivalenza seguente:
\[
\overline{\exists x\in A:p(x)}\leftrightarrow\forall x\in A,\overline{p}(x)
\]
Osservazione 3: Come vediamo dalle definizioni 2 e 3, si potrebbe dire in termini imprecisi ed intuitivi che la negazione del quantificatore universale è il quantificatore esistenziale, e viceversa.
La formula data nella definizione 2 asserisce che: “il fatto che non sia vero che $p$ vale per tutti gli elementi di $A$ equivale a dire che esiste almeno un elemento di $A$ per cui non vale $p$”. Per contro, la formula della definizione 3 afferma: “Il fatto che non sia vero che esista almeno un elemento di $A$ per cui vale $p$ equivale a dire che $p$ non vale per nessun elemento di $A$”. Tali fatti costituiscono il fondamento della logica dei predicati.

Esempi

Esempio 1: Si convertano le seguenti affermazioni nel linguaggio della logica dei predicati, quindi se ne trovino le negazioni:

  • tutte le mele sono rosse;
  • alcune mele sono verdi o gialle;
  • nessuna mela che sia verde è rossa.

Introduciamo in primo luogo l’insieme $M$ delle mele e i tre predicati $r,v$ e $g$ corrispondenti alle eventualità che la “variabile mela” abbia la proprietà di essere rossa, verde o gialla.
La prima affermazione si traduce facilmente come \(\forall x\in M,r(x)\). La negazione di questa formula si trova come semplice applicazione della regola fornita nella definizione 2: avremo dunque \(\overline{\forall x\in M,r(x)}\leftrightarrow\exists x\in M:\overline{r}(x)\), e il secondo termine dell’equivalenza si potrebbe leggere come “esiste almeno una mela che non è rossa”.

Prima di convertire la seconda affermazione, occorre ragionare un po’. In logica non esiste alcun quantificatore che traduca l’idea di “alcuni”, dal momento che essa è imprecisa e quindi inadatta al nostro linguaggio formale. D’altro canto, dire che alcune mele sono verdi o gialle equivale a dire che esiste almeno una mela che è verde o gialla; quindi scriveremo \(\exists x\in M:[v(x)\vee g(x)]\). In tal caso il predicato “essere verde o gialla” è scritto come disgiunzione dei due predicati “essere verde” ed “essere gialla”. Procediamo adesso alla negazione; adoperando la definizione 3 potremo scrivere
\[
\overline{\exists x\in M:[v(x)\vee g(x)]}\leftrightarrow\forall x\in M,\overline{v(x)\vee g(x)}
\]
A questo punto non resta che applicare la seconda legge di De Morgan per concludere che la negazione della seconda affermazione è \(\forall x\in M,\overline{v(x)}\wedge\overline{g(x)}\); questa si legge come “ogni mela è non-verde e non-gialla”, cioè “nessuna mela è verde e nessuna mela è gialla”.

In merito all’ultima affermazione, ragioneremo come segue: dire che nessuna mela che sia verde è rossa equivale a dire che ogni mela che è verde non è rossa; ciò è lo stesso che dire che, data una mela, se questa è verde non è rossa, e ciò vale per tutte le mele. Dunque la frase va scritta come \(\forall x\in M, [v(x)\rightarrow\overline{r}(x)]\). Passiamo adesso alla negazione: usando ancora la definizione 2 scriveremo
\[
\overline{\forall x\in M,[v(x)\rightarrow\overline{r}(x)]}\leftrightarrow\exists x\in M:\overline{[v(x)\rightarrow\overline{r}(x)]}
\]
Ricordando dalla logica proposizionale che \((p\rightarrow q)\leftrightarrow(\overline{p}\vee q)\), scriveremo l’ultima formula come \(\exists x\in M:\overline{[\overline{v}(x)\vee\overline{r}(x)]} \) col che, applicando ancora la seconda legge di De Morgan, risulta \(\exists x\in M: [v(x)\wedge r(x)]\). Concludiamo così che la negazione della terza affermazione è “esiste una mela che è sia verde che rossa”.

 

Commenti

commenti