Logica dei predicati: la negazione

Definizioni

Osservazione 1: Sia data una proposizione . Sappiamo dalla logica proposizionale che lecito considerare la sua negazione (overline{q}); dal momento per che in logica dei predicati 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

; si chiama negazione di e si indica con il simbolo (overline{p}) un nuovo predicato tale che (overline{p}(x)) se e soltanto se la propriet espressa da non vale per la variabile .

Osservazione 2: La definizione 1 dice, in buona sostanza, che se un certo predicato

non vale per , allora per vale un altro predicato (overline{p}), il quale esprime la propriet per non vale . Il fatto che un determinato predicato non valga cio esso stesso un predicato.

Definizione 2: Negazione del quantificatore universale.
Siano dati un insieme

e un predicato ; come sappiamo essi possono essere utilizzati per scrivere la formula (forall xin A,p(x)). Per tutte le formule di questo tipo vale lequivalenza seguente:
[
overline{forall xin A, p(x)}leftrightarrowexists xin A:overline{p}(x)
]

Definizione 3: Negazione del quantificatore esistenziale.
Siano dati un insieme

e un predicato ; come sappiamo essi possono essere utilizzati per scrivere la formula (exists xin A:p(x)). Per tutte le formule di questo tipo vale lequivalenza seguente:
[
overline{exists xin A:p(x)}leftrightarrowforall xin 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 vale per tutti gli elementi di equivale a dire che esiste almeno un elemento di per cui non vale . Per contro, la formula della definizione 3 afferma: Il fatto che non sia vero che esista almeno un elemento di per cui vale equivale a dire che non vale per nessun elemento di . 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 linsieme delle mele e i tre predicati e corrispondenti alle eventualit che la variabile mela abbia la propriet di essere rossa, verde o gialla.
La prima affermazione si traduce facilmente come (forall xin M,r(x)). La negazione di questa formula si trova come semplice applicazione della regola fornita nella definizione 2: avremo dunque (overline{forall xin M,r(x)}leftrightarrowexists xin M:overline{r}(x)), e il secondo termine dellequivalenza 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 lidea di alcuni, dal momento che essa imprecisa e quindi inadatta al nostro linguaggio formale. Daltro canto, dire che alcune mele sono verdi o gialle equivale a dire che esiste almeno una mela che verde o gialla; quindi scriveremo (exists xin 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 xin M:[v(x)vee g(x)]}leftrightarrowforall xin 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 xin M,overline{v(x)}wedgeoverline{g(x)}); questa si legge come ogni mela non-verde e non-gialla, cio nessuna mela verde e nessuna mela gialla.

In merito allultima 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 xin M, [v(x)
ightarrowoverline{r}(x)]). Passiamo adesso alla negazione: usando ancora la definizione 2 scriveremo
[
overline{forall xin M,[v(x)
ightarrowoverline{r}(x)]}leftrightarrowexists xin M:overline{[v(x)
ightarrowoverline{r}(x)]}
]
Ricordando dalla logica proposizionale che ((p
ightarrow q)leftrightarrow(overline{p}vee q)), scriveremo lultima formula come (exists xin M:overline{[overline{v}(x)veeoverline{r}(x)]} ) col che, applicando ancora la seconda legge di De Morgan, risulta (exists xin M: [v(x)wedge r(x)]). Concludiamo cos che la negazione della terza affermazione esiste una mela che sia verde che rossa.