Conector lógico

Entre los conectores lógicos de uso común se incluyen los siguientes. ^{[ 1 ]}

• Negación (no) :${\displaystyle \neg }$,${\displaystyle \sim }$,${\displaystyle N}$(prefijo) en el que${\displaystyle \neg }$es el más moderno y ampliamente utilizado, y${\displaystyle \sim }$también es común;
• Conjunción (y) :${\displaystyle \wedge }$,${\displaystyle \&}$,${\displaystyle K}$(prefijo) en el que${\displaystyle \wedge }$es el más moderno y de uso más extendido;
• Disyunción (o) :${\displaystyle \vee }$,${\displaystyle A}$(prefijo) en el que${\displaystyle \vee }$es el más moderno y de uso más extendido;
• Implicación (si...entonces) :${\displaystyle \to }$,${\displaystyle \supset }$,${\displaystyle \Rightarrow }$,${\displaystyle C}$(prefijo) en el que${\displaystyle \to }$es el más moderno y ampliamente utilizado, y${\displaystyle \supset }$también es común;
• Equivalencia (si y solo si) :${\displaystyle \leftrightarrow }$,${\displaystyle \subset \!\!\!\supset }$, ${\displaystyle \Leftrightarrow }$,${\displaystyle \equiv }$,${\displaystyle E}$(prefijo) en el que${\displaystyle \leftrightarrow }$es el más moderno y ampliamente utilizado, y${\displaystyle \subset \!\!\!\supset }$se usa comúnmente donde${\displaystyle \supset }$También se utiliza.

Por ejemplo, el significado de las afirmaciones está lloviendo (denotado por${\displaystyle p}$) y estoy en el interior (indicado por${\displaystyle q}$) se transforma cuando ambos se combinan con conectores lógicos:

• No está lloviendo (${\displaystyle \neg p}$);
• Está lloviendo y estoy dentro de casa (${\displaystyle p\wedge q}$);
• Está lloviendo o estoy en casa (${\displaystyle p\lor q}$);
• Si llueve, entonces estoy en casa (${\displaystyle p\rightarrow q}$);
• Si estoy en casa, entonces está lloviendo (${\displaystyle q\rightarrow p}$);
• Estoy en casa solo si está lloviendo (${\displaystyle p\leftrightarrow q}$).

También es común considerar que la fórmula siempre verdadera y la fórmula siempre falsa son conectivas (en cuyo caso son nulas ).

• Fórmula verdadera :${\displaystyle \top }$,${\displaystyle 1}$,${\displaystyle V}$(prefijo), o${\displaystyle \mathrm {T} }$;
• Fórmula falsa :${\displaystyle \bot }$,${\displaystyle 0}$,${\displaystyle O}$(prefijo), o${\displaystyle \mathrm {F} }$.

Esta tabla resume la terminología:

• Negación: el símbolo${\displaystyle \neg }$apareció en Heyting en 1930 ^{[ 2 ] [ 3 ]} (compárese con el símbolo de Frege ⫟ en su Begriffsschrift ^{[ 4 ]} ); el símbolo${\displaystyle \sim }$apareció en Russell en 1908; ^{[ 5 ]} una notación alternativa es agregar una línea horizontal encima de la fórmula, como en${\displaystyle {\overline {p}}}$; otra notación alternativa es usar un símbolo de prima como en${\displaystyle p'}$.
• Conjunción: el símbolo${\displaystyle \wedge }$apareció en Heyting en 1930 ^{[ 2 ]} (compárese con el uso que hace Peano de la notación de intersección propia de la teoría de conjuntos)${\displaystyle \cap }$^{[ 6 ]} ); el símbolo${\displaystyle \&}$apareció al menos en Schönfinkel en 1924; ^{[ 7 ]} el símbolo${\displaystyle \cdot }$Proviene de la interpretación que Boole hizo de la lógica como un álgebra elemental .
• Disyunción: el símbolo${\displaystyle \vee }$apareció en Russell en 1908 ^{[ 5 ]} (compárese con el uso que hace Peano de la notación de unión propia de la teoría de conjuntos)${\displaystyle \cup }$); el símbolo${\displaystyle +}$También se utiliza, a pesar de la ambigüedad que proviene del hecho de que el${\displaystyle +}$de álgebra elemental ordinaria es un exclusivo o cuando se interpreta lógicamente en un anillo de dos elementos ; puntualmente en la historia un${\displaystyle +}$Peirce ha utilizado junto con un punto en la esquina inferior derecha . ^{[ 8 ]}
• Implicación: el símbolo${\displaystyle \to }$apareció en Hilbert en 1918; ^{[ 9 ] : 76}${\displaystyle \supset }$fue utilizado por Russell en 1908 ^{[ 5 ]} (compárese con la Ɔ de Peano, la C invertida);${\displaystyle \Rightarrow }$Apareció en Bourbaki en 1954. ^{[ 10 ]}
• Equivalencia: el símbolo${\displaystyle \equiv }$en Frege en 1879; ^{[ 11 ]}${\displaystyle \leftrightarrow }$en Becker en 1933 (no es la primera vez y para esto véase lo siguiente); ^{[ 12 ]}${\displaystyle \Leftrightarrow }$apareció en Bourbaki en 1954; ^{[ 13 ]} otros símbolos aparecieron puntualmente en la historia, como${\displaystyle \supset \subset }$en Gentzen , ^{[ 14 ]}${\displaystyle \sim }$en Schönfinkel ^{[ 7 ]} o${\displaystyle \subset \supset }$en Chazal, ^{[ 15 ]}
• Verdadero: el símbolo${\displaystyle 1}$proviene de la interpretación de Boole de la lógica como un álgebra elemental sobre el álgebra booleana de dos elementos ; otras notaciones incluyen${\displaystyle \mathrm {V} }$(abreviatura de la palabra latina "verum") que se encuentra en Peano en 1889.
• Falso: el símbolo${\displaystyle 0}$También proviene de la interpretación de Boole de la lógica como un anillo; otras notaciones incluyen${\displaystyle \Lambda }$(rotado${\displaystyle \mathrm {V} }$) que se encuentra en Peano en 1889.

Algunos autores utilizaron letras como conectores:${\displaystyle \operatorname {u.} }$para la conjunción (el alemán "und" para "y") y${\displaystyle \operatorname {o.} }$para la disyunción (del alemán "oder" para "o") en los primeros trabajos de Hilbert (1904); ^{[ 16 ]}${\displaystyle Np}$para la negación,${\displaystyle Kpq}$para conjunción,${\displaystyle Dpq}$para la negación alternativa,${\displaystyle Apq}$para la disyunción,${\displaystyle Cpq}$por implicación,${\displaystyle Epq}$para bicondicional en Łukasiewicz en 1929.

Un conector lógico como la implicación inversa${\displaystyle \leftarrow }$" es en realidad lo mismo que el condicional material con argumentos intercambiados; por lo tanto, el símbolo para la implicación inversa es redundante. En algunos cálculos lógicos (en particular, en la lógica clásica ), ciertas proposiciones compuestas esencialmente diferentes son lógicamente equivalentes . Un ejemplo menos trivial de redundancia es la equivalencia clásica entre${\displaystyle \neg p\vee q}$y${\displaystyle p\to q}$. Por lo tanto, un sistema lógico basado en la lógica clásica no necesita el operador condicional "${\displaystyle \to }$" si "${\displaystyle \neg }$" (no) y "${\displaystyle \vee }$" (o) ya están en uso, o pueden usar el "${\displaystyle \to }$"solo como un azúcar sintáctico para un compuesto que tiene una negación y una disyunción.

Existen dieciséis funciones booleanas que asocian los valores de verdad de entrada.${\displaystyle p}$y${\displaystyle q}$con salidas binarias de cuatro dígitos . ^{[ 17 ]} Estas corresponden a posibles opciones de conectores lógicos binarios para la lógica clásica . Diferentes implementaciones de la lógica clásica pueden elegir diferentes subconjuntos funcionalmente completos de conectores.

Un enfoque consiste en elegir un conjunto mínimo y definir otros conectores mediante alguna forma lógica, como en el ejemplo anterior con el condicional material. A continuación se presentan los conjuntos mínimos funcionalmente completos de operadores en lógica clásica cuyas aridades no superan 2:

Un elemento

${\displaystyle \{\uparrow \}}$,${\displaystyle \{\downarrow \}}$.

Dos elementos

${\displaystyle \{\vee ,\neg \}}$,${\displaystyle \{\wedge ,\neg \}}$,${\displaystyle \{\to ,\neg \}}$,${\displaystyle \{\gets ,\neg \}}$,${\displaystyle \{\to ,\bot \}}$,${\displaystyle \{\gets ,\bot \}}$,${\displaystyle \{\to ,\nleftrightarrow \}}$,${\displaystyle \{\gets ,\nleftrightarrow \}}$,${\displaystyle \{\to ,\nrightarrow \}}$,${\displaystyle \{\to ,\nleftarrow \}}$,${\displaystyle \{\gets ,\nrightarrow \}}$,${\displaystyle \{\gets ,\nleftarrow \}}$,${\displaystyle \{\nrightarrow ,\neg \}}$,${\displaystyle \{\nleftarrow ,\neg \}}$,${\displaystyle \{\nrightarrow ,\top \}}$,${\displaystyle \{\nleftarrow ,\top \}}$,${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$,${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$.

Tres elementos

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$,${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$,${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$,${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$,${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$,${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$.

Otro enfoque consiste en utilizar conectores con derechos iguales de un conjunto conveniente y funcionalmente completo, pero no mínimo . Este enfoque requiere más axiomas proposicionales , y cada equivalencia entre formas lógicas debe ser un axioma o demostrable como teorema.

La situación, sin embargo, es más compleja en la lógica intuicionista . De sus cinco conectores, {∧, ∨, →, ¬, ⊥}, solo la negación "¬" puede reducirse a otros conectores (véase Falso (lógica) §  Falso, negación y contradicción para más información). Ni la conjunción, ni la disyunción, ni el condicional material tienen una forma equivalente construida a partir de los otros cuatro conectores lógicos.

Un enfoque veritativo-funcional para operadores lógicos se implementa como puertas lógicas en circuitos digitales . Prácticamente todos los circuitos digitales (la principal excepción es la DRAM ) se construyen a partir de puertas NAND , NOR , NOT y de transmisión ; consulte más detalles en la función de verdad en ciencias de la computación . Los operadores lógicos sobre vectores de bits (que corresponden a álgebras booleanas finitas ) son operaciones bit a bit .

Pero no todos los usos de un conector lógico en programación informática tienen una semántica booleana. Por ejemplo, la evaluación perezosa se implementa a veces para P ∧ Q y P ∨ Q , por lo que estos conectores no son conmutativos si una o ambas expresiones P , Q tienen efectos secundarios . Además, un condicional , que en cierto sentido corresponde al conector condicional material , es esencialmente no booleano porque para if (P) then Q;, el consecuente  Q no se ejecuta si el antecedente  P es falso (aunque un compuesto en su conjunto es exitoso ≈ "verdadero" en tal caso). Esto se acerca más a las perspectivas intuicionistas y constructivistas sobre el condicional material, que a las perspectivas de la lógica clásica.

Los conectores lógicos se utilizan para definir las operaciones fundamentales de la teoría de conjuntos , ^{[ 21 ]} de la siguiente manera:

Esta definición de igualdad de conjuntos es equivalente al axioma de extensionalidad .