Negación lógica
En lógica y matemática, la negación, también llamada complemento lógico, es una operación sobre proposiciones, valores de verdad, o en general, valores semánticos. Intuitivamente, la negación de una proposición es verdadera cuando dicha proposición es falsa, y viceversa. En lógica clásica la negación normalmente se identifica con la función de verdad que cambia su valor de verdadero a falso y viceversa. En lógica intuicionista, de acuerdo a la interpretación de Brouwer–Heyting–Kolmogorov, la negación de una proposición p es la proposición cuyas pruebas son las refutaciones de p. Lógica de proposicionesSiendo el conjunto de proposiciones, y proposiciones de , se puede definir la operación unaria: negación (símbolo ¬), por la que a una variable de se le asigna el valor negado de la variable de . DefiniciónNo existe acuerdo en cuanto a la posibilidad de definir la negación, ni en cuanto a su estatus lógico, función y significado, ni tampoco a su ámbito de aplicación ..., y en cuanto a la interpretación de la sentencia negativa, (FH Heinemann 1944).[1] La negación clásica es una operación sobre un valor de verdad (generalmente, el valor de una proposición), que produce un valor de verdadero cuando su operando es falso, y un valor de falso cuando su operando es verdadero. Por tanto, si el enunciado A es verdadero, entonces ¬A (pronunciado "no A") sería consecuentemente falso; y lo contrario: si ¬A es verdadero, entonces A sería consecuentemente falso.[cita requerida] La tabla de verdad de ¬p es la siguiente:
La negación clásica se puede definir en términos de otras operaciones lógicas. Por ejemplo, ¬p se puede definir como p → F, donde "→" es una implicación lógica y F es una falsedad absoluta. Por el contrario, se puede definir F como p & ¬p para cualquier proposición p, donde "&" es una conjunción lógica. La idea aquí es que cualquier contradicción es falsa. Aunque estas ideas funcionan tanto en la lógica clásica como en la intuicionista, no funcionan en cambio en la lógica paraconsistente, donde las contradicciones no son necesariamente falsas.[cita requerida] En la lógica clásica, se tiene una identidad adicional: p → q se puede definir como ¬p ∨ q, donde "∨" es la disyunción lógica: "no p, o q".[cita requerida] algebraicamente, la negación clásica corresponde con el complemento en un álgebra booleana, y la negación intuicionista con la seudocomplementación en un álgebra de Heyting. Estas álgebras ofrecen una semántica para las lógicas clásica e intuicionista, respectivamente.[cita requerida] NotaciónLa negación de una proposición p se denota de diferentes maneras en varios contextos y campos de aplicación. Entre estas variantes, tenemos las siguientes:
En teoría de conjuntos \ también se utiliza para indicar 'no miembro de': U \ A es el conjunto de todos los miembros de U que no son miembros de A. Independientemente de la notación o simbolización utilizados, la negación ¬p / ~p se puede leer como "no es el caso que p", "no es cierto que p", o por lo común, simplemente (aunque no gramaticalmente) como "no p".[2] PropiedadesDoble negaciónDentro de un sistema de lógica clásica, la doble negación, esto es, la negación de la negación de una proposición p, es lógicamente equivalente a p. Expresado simbólicamente, ¬(¬p) ⇔ p. En lógica intuicionista, una proposición implica su doble negación, pero no al revés. Esto marca una importante diferencia entre la negación clásica e intuicionista. Algebraicamente, la negación clásica es llamada una involución de periodo dos. Sin embargo, en lógica intuicionista, sí tenemos la equivalencia entre ¬¬¬p y ¬p. Es más, en el caso proposicional, una oración es demostrable de forma clásica, si su doble negación es demostrable de manera intuicionista. Este resultado es conocido como el teorema de Glivenko. DualidadLas leyes de De Morgan proporcionan una forma de dualidad: la negación sobre la disyunción inclusiva equivale a la conjunción de negaciones; y recíprocamente, la negación de la conjunción es igual a la unión de las negaciones de las disyunciones inclusivas :
LinealidadEn el álgebra de Boole, una función lineal es una función tal que: Si existe a0, a1, ..., an {0,1} tal que f(b1, ..., bn) = a0 ⊕ (a1 b1) ⊕ ... ⊕ (an bn), para todo b1, ..., bn {0,1}. Otra forma de expresar esto es que cada variable siempre cambia su valor de verdad de la operación o nunca cambia. La negación es un operador lógico lineal. AutodualidadEn el álgebra de Boole, una función autodual es una función tal que: Si f(a1, ..., an) = ~f(~a1, ..., ~an) para todo a1, ..., an {0,1}. La negación es un operador lógico de autodualidad. Reglas de inferenciaHay varias formas equivalentes entre sí, de formular reglas para la negación. Una forma usual de formular la negación clásica, al establecer una deducción natural, es tomar como reglas primitivas de inferencia:
Las reglas para negación intuicionista se obtienen de la misma forma, pero excluyendo la eliminación de la doble negación. La introducción de la negación establece que si se puede obtener un absurdo como conclusión de p, entonces p no debe ser el caso (p es falso (clásico), o refutable (intuicionista), etc.). La eliminación de la negación establece que cualquier cosa se desprende de un absurdo. A veces, la negación de la elimincación es formulada usando el signo primitivo de absurdo ⊥. En este caso, la regla dice que dado p y ¬p concluimos en un absurdity. Junto a la eliminación de la doble negación, se puede inferir la regla originalmente formulada, a saber, que cualquier cosa que se desprende de un absurdo. Típicamente, la negación intuicionista ¬p de p se define como p→⊥. Entonces la introducción de la negación y la eliminación son sólo casos especiales de introducción de la implicación (prueba condicional) y eliminación (modus ponens). En este caso, podemos también agregar como regla primitiva ex falso quodlibet. ProgramaciónAsí como en matemática, la negación es ampliamente usada en ciencias de la computación para construir expresiones lógicas. if (!(r == t))
{
/*...sentencias ejecutadas cuando r NO ES IGUAL a t...*/
}
El signo "!" significa NO lógico en B, C, y otros lenguajes inspirados en la sintaxis de C como C++, Java, Perl, PHP, etc. "NOT" es el operador usado en ALGOL 60, BASIC, COBOL, y lenguajes inspirados en la sintaxis de ALGOL como Pascal, Ada, Seed7, etc. Algunos lenguajes (C++, Perl, etc.) proveen más de un operador para la negación. Algunos lenguajes como PL/I y Ratfor, usan ¬ para la negación. Algunas computadoras y sistemas operativos modernos muestran ¬ como ! en archivos condificados en ASCII. Existe también la negación a nivel de bits. Ésta toma el valor dado y lo invierte bit a bit: los 1 cambian a 0 y los 0 a 1. Esta operación se usa normalmente para generar el complemento a uno o "~" en C o C++ y el complemento a dos (sólo simplificado a "-" o el signo negativo ya que esto es equivalente a tomar el valor aritmético negativo del número) ya que básicamente genera el opuesto (valor negativo equivalente) o complemento matemático del valor (donde ambos valores se agregan juntos para crear un todo). Para obtener el valor absoluto (equivalente positivo) de un entero dado, el siguiente código trabajaría cambiando el signo de negativo a positivo (es negativo porque "x < 0" resulta verdadero) unsigned int abs(int x)
{
if (x < 0)
return -x;
else
return x;
}
Para demostrar la negación lógica: unsigned int abs(int x)
{
if (!(x < 0))
return x;
else
return -x;
}
Invirtiendo la condición y revirtiendo las salidas, se genera código que es lógicamente equivalente al código original, es decir, que obtendremos idénticos resultados para cualquier entrada. (Nota: Dependiendo del compilador utilizado, las instrucciones reales ejecutadas por la computadora pueden diferir). Véase también
Referencias
Lecturas adicionales
Enlaces externos
|