Negació lògica

De Viquipèdia
Dreceres ràpides: navegació, cerca

En lògica i matemàtica, la negació, també anomenada complement lògic, és una operació sobre proposicions, valors de veritat, o en general, valors semàntics. Intuïtivament, la negació d'una proposició és veritable quan aquesta proposició és falsa, i viceversa. En lògica clàssica la negació està normalment identificada amb la funció de veritat que canvia el seu valor de veritable a fals i viceversa. En Lògica intuicionista, d'acord a la interpretació BHK, la negació d'una proposició p és la proposició les proves són les refutacions de p. A la semàntica de Kripke, on els valors semàntics de les fórmules són conjunts de possibles mons, la negació de p, és la seva complement.

Definició[modifica | modifica el codi]

La negació clàssica és una operació sobre un valor de veritat, típicament, el valor d'una proposició, que produeix un valor de veritable quan seva operant és fals, i un valor de fals quan el seu operant és veritable. Per tant, si l'enunciat A és veritable, llavors ¬ A (pronunciat "no A") seria conseqüentment fals, i el contrari, si ¬ A és veritable, llavors A seria fals.

La taula de veritat de ¬p és la següent:

Taula de veritat de ¬ p
p ¬p
Veritable Fals
Fals Veritable

La negació clàssica es pot definir en termes d'altres operacions lògiques. Per exemple, ¬p es pot definir com pF, on "→" és una implicació lògica i F és una falsedat absoluta. Per contra, es pot definir F com p & ¬p per a qualsevol proposició p, on "&" és una conjunció lògica. La idea és que qualsevol contradicció és falsa. Mentre aquestes idees funcionen tant en la lògica clàssica com en la instuicionista, no funcionen a la Lògica paraconsistent, on les contradiccions no són necessàriament falses.

En lògica clàssica hi ha una identitat addicional:pq es pot definir com ¬pq, on "∨" és la disjunció lògica: "no p, o q".

Algebraicament, la negació clàssica correspon amb el complement en un àlgebra booleana, i la negació intuicionista al pseudocomplement en un àlgebra de Heyting. Aquestes àlgebres proveeixen una semàntica per a les lògiques clàssica i intuicionista respectivament.

Notació[modifica | modifica el codi]

La negació d'una proposició p es denota dediferentes maneres en diversos contextos i camps d'aplicació. Entre aquestes variants, tenim les següents:

Notació Verbalització
\lnot p No p
-p\, No p
 \sim p\, No p
 Np \, Gen p
 p '\ P prima,

complement de p

 \bar{p} P barra,

barra p

! P \ Exclamació p

Independentment de la notació o símbol utilitzats, la negació ¬p / ~p es pot llegir com "no és el cas que p", "no és cert que p ", o si més comú, simplement (encara que no gramaticalment) com " no p ".

Propietats[modifica | modifica el codi]

Doble negació[modifica | modifica el codi]

Dins d'un sistema de lògica clàssica, la doble negació, és a dir, la negació de la negació d'una proposició p, és lògicament equivalent a p. Expressat simbòlicament, ¬ (¬ p) ⇔ p. En lògica intuicionista, una proposició implica la seva doble negació, però no a l'inrevés. Això marca una important diferència entre la negació clàssica i intuicionista. Algebraicament, la negació clàssica és cridada una involució de període dos.

No obstant això, en lògica intuicionista, si tenim l'equivalència entre ¬ ¬ ¬ p i ¬ p. És més, en el cas proposicional, una oració és demostrable de forma clàssica, si el seu doble negació és demostrable de manera intuicionista. Aquest resultat és conegut com el teorema de Glivenko.

Distributiva[modifica | modifica el codi]

~  (a \equiv b) \equiv ( ~  a\equiv b)

Linealitat[modifica | modifica el codi]

En l'àlgebra de Boole, una funció lineal és una funció tal que:   Si hi ha a 0 , a 1 , ..., a n \in {0,1} tal que f (b 1 , ..., b n ) = a 0 ⊕ (a 1  \land b 1 ) ⊕ ... ⊕ (a n  \land b n ), per a tot b 1 , ..., b n  \in {0,1}.

Una altra forma d'expressar això és que cada variable sempre canvia el seu valor de veritat de l'operació o mai canvia. La negació és un operador lògic lineal.

Autodualitat[modifica | modifica el codi]

A l'àlgebra de Boole, una funció autodual és una funció tal que:

Si f (a 1 , ..., a n ) = ~ f (~ a 1 , ..., ~ a n ) per a tot a 1 , ..., a n  \in {0,1}. La negació és un operador lògic de autodualitat.

Regles d'inferència[modifica | modifica el codi]

Hi ha diverses formes equivalents entre si, de formular regles per a la negació. Una forma usual de formular la negació clàssica, en establir una deducció natural, és prendre com regles primitives d'inferència:

  • Introducció de la negació (Si p implica q i ¬ q, inferim ¬ p; aquesta regla també es diu reductio ad absurdum),
  • Eliminació de la negació (Atès p i ¬ p inferim q; aquesta regla també es diu ex fals quodlibet),
  • Eliminació de la doble negació (Atès ¬ ¬ p inferim p).

Les regles per negació intuicionista s'obtenen de la mateixa manera, però excloent l'eliminació de la doble negació.

La introducció de la negació estableix que si es pot obtenir un absurd com conclusió p, llavors p no ha de ser el cas ( p és fals (clàssic), o refutable (intuicionista) , etc.). L'eliminació de la negació estableix que qualsevol cosa es desprèn d'un absurd. De vegades, la negació de la elimincación és formulada usant el signe primitiu d'absurd ⊥. En aquest cas, la regla diu que donat p i ¬ p concloure en un absurdity. Al costat de l'eliminació de la doble negació, es pot inferir la regla originalment formulada, és a dir, que qualsevol cosa que es desprèn d'un absurd.

Típicament, la negació intuicionista ¬ p de p es defineix com p → ⊥. Llavors la introducció de la negació i l'eliminació són només casos especials d'introducció de la implicació (prova condicional) i eliminació (modus ponens). En aquest cas, podem també afegir com a regla primitiva ex fals quodlibet.

Programació[modifica | modifica el codi]

Així com en matemàtica, la negació és àmpliament usada en computació per construir expressions lògiques.

    if (! (r == t))
    {
         / * ... Sentències executades quan r NO ÉS IGUAL a t ... * /
    }

El signe "!" significa NO lògic en B, C, i altres llenguatges inspirats en la sitaxis de C com C++, Java, Perl, PHP, etc. "NOT" és l'operador usat en ALGOL 60, BASIC, COBOL, i lenguanes inspirats en la sintaxi de ALGOL com Pascal, Ada, Seed7, etc. Alguns llenguatges (C++, Perl, etc.) Proveeixen més d'un operador per la negació. Alguns llenguatges com PL/I i Ratfor, usen ¬ per la negació. Algunes computadores i sistemes operatius moderns mostren ¬ com! en arxius condificados a ASCII.

Existeix també la negació a nivell de bits. Aquesta pren el valor donat, i canvia tot el binari; els 1 canvien a 0 i els 0 a 1. Aquesta operació és usada normalment per generar el complement a un o "~" en C o C++ i el complement a dos (només simplificat a "- "o el signe negatiu, ja que això és equivalent a prendre el valor aritmètic negatiu del nombre) ja que bàsicament genera l'oposat (valor negatiu equivalent) o complement matemàtic del valor (on tots dos valors s'agreguen junts per crear un tot).

Per obtenir el valor absolut (equivalent positiu) d'un sencer donat, el codi treballaria canviant el signe de negatiu a positiu (és negatiu perquè "x <0" cas té raó)

    unsigned int abs (int x)
    {
        if (x <0)
            return-x;
        else
            return x;
    }

Per demostrar la negació lògica:

    unsigned int abs (int x)
    {
        if (! (x <0))
            return x;
        else
            return-x;
    }

Invertint la condició i revertint les sortides, es genera codi que és lògicament equivalent al codi original, és a dir, que obtindrem idèntics resultats per qualsevol entrada. (Nota: Segons el compilador utilitzat, les instruccions reals executades per l'ordinador poden diferir).

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  • Gabbay, Dov, and Wansing, Heinrich, eds., 1999. What is Negation? Kluwer. ( En anglès)
  • Horn, L., 2001. A Natural History of Negation. Univ of Chicago Press. ( En anglès)
  • G. H. von Wright, 1953-59, "On the Logic of Negation", Commentationes physico-Mathematicae 22. ( En anglès)
  • Wansing, Heinrich, 2001, "Negation," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell. ( En anglès)
  • Marc Tettamanti, Rosa Manenti - Pasquale A. Della Rosa - Andrea Falini - Daniela Perani - Stefano F. Cappa and Andrea Moro (2008) "Negation in the brain. Modulating action representation." NeuroImage Volume 43, Issue 2, 1 novembre 2008, Pages 358-367. http://dx.doi.org/10.1016/j.neuroimage.2008.08.004 ( en anglès)

Enllaços externs[modifica | modifica el codi]