Conectivo lógico

Diagrama de Hasse de conexiones lógicas.

En lógica, una lógica conectividad (también llamado a operador lógico, conectividad centílica, o centinela operator) es una constante lógica. Se pueden utilizar para conectar fórmulas lógicas. Por ejemplo en la sintaxis de la lógica proposicional, la conectividad binaria Alternativa Alternativa {displaystyle lor } se puede utilizar para unirse a las dos fórmulas atómicas P{displaystyle P} y Q{displaystyle Q}, renderizando la fórmula compleja PAlternativa Alternativa Q{displaystyle Plor Q}.

Los conectores comunes incluyen negación, disyunción, conjunción e implicación. En los sistemas estándar de la lógica clásica, estos conectivos se interpretan como funciones de verdad, aunque reciben una variedad de interpretaciones alternativas en la lógica no clásica. Sus interpretaciones clásicas son similares a los significados de las expresiones del lenguaje natural como 'no', 'o', 'y' y 'si'.;, pero no idénticos. Las discrepancias entre los conectivos del lenguaje natural y los de la lógica clásica han motivado enfoques no clásicos del significado del lenguaje natural, así como enfoques que combinan una semántica compositiva clásica con una pragmática robusta.

Un conectivo lógico es similar, pero no equivalente, a una sintaxis comúnmente utilizada en lenguajes de programación llamada operador condicional.

Resumen

En los lenguajes formales, las funciones de verdad se representan mediante símbolos inequívocos. Esto permite que las declaraciones lógicas no se entiendan de manera ambigua. Estos símbolos se denominan conectivos lógicos, operadores lógicos, operadores proposicionales o, en lógica clásica, conectivos funcionales de verdad. Para conocer las reglas que permiten construir nuevas fórmulas bien formadas uniendo otras fórmulas bien formadas usando conectivos veritativo-funcionales, véase fórmula bien formada.

Los conectores lógicos se pueden usar para vincular cero o más declaraciones, por lo que se puede hablar de conectores lógicos n-arios. Las constantes booleanas Verdadero y Falso se pueden considerar como operadores cero-arios. La negación es un conectivo 1-ario, y así sucesivamente.

Conectores lógicos comunes

Lista de conectores lógicos comunes

Los conectores lógicos de uso común incluyen:

• Negación (no): ¬, N (prefijo), ~
• Conjunción (y): ∧, K (prefix), &, ∙
• Disyunción (o): ∨, A (prefijo)
• implicación material (si... entonces): →, C (prefijo), ⇒, ≤
• Bicondicional (si y sólo si): ↔, E (prefijo), ≡, =

Los nombres alternativos para bicondicional son iff, xnor y bi-implicación.

Por ejemplo, el significado de las afirmaciones está lloviendo (indicado por P) y estoy dentro (indicado por Q) es transformado, cuando los dos se combinan con conectores lógicos:

• Es no lluvia (¬ ¬ {displaystyle neg }P)
• Está lloviendo. y Estoy dentro (P∧ ∧ Q{displaystyle Pwedge Q})
• Está lloviendo. o Estoy dentro (PAlternativa Alternativa Q{displaystyle Plor Q})
• Si Está lloviendo, entonces Estoy dentro (P→ → Q{displaystyle Prightarrow Q})
• Si Estoy dentro, entonces está lloviendo (Q→ → P{displaystyle Qrightarrow P})
• Estoy dentro si está lloviendo (PAdministración Administración Q{displaystyle Pleftrightarrow Q})

También es común considerar que la fórmula siempre verdadero y la fórmula siempre falso son conectivas:

• Verdadera fórmula (⊤, 1, V [prefijo], o T)
• Fórmula falsa (⊥, 0, O [prefijo], o F)

Historia de las notaciones

• Negación: el símbolo ¬ apareció en Heyting en 1929 (compare al símbolo de Frege ⫟ en su Begriffsschrift); el símbolo ~ apareció en Russell en 1908; una notación alternativa es añadir una línea horizontal en la parte superior de la fórmula, como en P̄ ̄ {displaystyle {fn}}}; otra notación alternativa es usar un símbolo principal como en P'.
• Conjunción: el símbolo ∧ apareció en Heyting en 1929 (compare al uso de Peano de la notación teórica de la intersección the), el símbolo " apareció al menos en Schönfinkel en 1924; el símbolo. viene de la interpretación de Boole de la lógica como un álgebra elemental.
• Disyunción: el símbolo ∨ apareció en Russell en 1908 (comparar el uso de Peano de la notación teórica de unión fija set); el símbolo + también se utiliza, a pesar de la ambigüedad que viene del hecho de que el + de álgebra elemental ordinaria es un exclusivo o cuando se interpreta lógicamente en un anillo de dos elementos; puntualmente en la historia un + junto con un punto en la esquina inferior derecha ha sido utilizado
• Implicación: el símbolo → se puede ver en Hilbert en 1917; φ fue utilizado por Russell en 1908 (compare a la notación C invertida de Peano); ⇒ fue utilizado en Vax.
• Bicondicional: el símbolo ≡ fue utilizado por lo menos por Russell en 1908; ↔ fue utilizado por lo menos por Tarski en 1940; α fue utilizado en Vax; otros símbolos aparecieron puntualmente en la historia, como φ⊃ en Gentzen, ~ en Schönfinkel o ⊂ ilumina en Chazal.
• Verdadero: el símbolo 1 viene de la interpretación de Boole de la lógica como un álgebra elemental sobre el álgebra booleano de dos elementos; otras notaciones incluyen ⋀ ⋀ {textstyle bigwedge } (que se encuentra en Peano).
• Falso: el símbolo 0 viene también de la interpretación de Boole de la lógica como anillo; otras notaciones incluyen ⋁ ⋁ {textstyle bigvee } (que se encuentra en Peano).

Algunos autores utilizaron letras para conectores en algún momento de la historia: u. para conjunción (el alemán 'und" para "y") y o. para disyunción (alemán's "oder" para "o") en obras anteriores de Hilbert (1904); Np para negación, Kpq para conjunción, Dpq para negación alternativa, Apq para disyunción, Xpq para negación conjunta, Cpq por implicación, Epq por bicondicional en Łukasiewicz (1929); cf. notación polaca.

Redundancia

Un conectivo lógico como la implicación inversa "←" es en realidad lo mismo que material condicional con argumentos intercambiados; por tanto, el símbolo de la implicación inversa es redundante. En algunos cálculos lógicos (en particular, en la lógica clásica), ciertas declaraciones compuestas esencialmente diferentes son lógicamente equivalentes. Un ejemplo menos trivial de redundancia es la equivalencia clásica entre ¬P ∨ Q y P → Q. Por lo tanto, un sistema lógico de base clásica no necesita el operador condicional "→" si "¬" (no) y "∨" (o) ya están en uso, o pueden usar el "→" sólo como un azúcar sintáctico para un compuesto que tiene una negación y una disyunción.

Hay dieciséis funciones booleanas que asocian los valores de verdad de entrada P y Q con salidas binarias de cuatro dígitos. Estos corresponden a posibles elecciones 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 conectivos.

Un enfoque es elegir un conjunto mínimo y definir otros conectores mediante alguna forma lógica, como en el ejemplo anterior con el material condicional. Los siguientes son los conjuntos mínimos funcionalmente completos de operadores en lógica clásica cuyas aridades no exceden de 2:

Un elemento

{↑} {↓}.

Dos elementos

{}Alternativa Alternativa ,¬ ¬ }{displaystyle {veeneg}}, {}∧ ∧ ,¬ ¬ }{displaystyle {wedgeneg}}, {}→ → ,¬ ¬ }{displaystyle {toneg}, {}← ← ,¬ ¬ }{displaystyle {getsneg}, {}→ → ,⊥ ⊥ }{displaystyle {tobot}}, {}← ← ,⊥ ⊥ }{displaystyle {getsbot}}, {}→ → ,↮ ↮ }{displaystyle {tonleftrightarrow}}, {}← ← ,↮ ↮ }{displaystyle {getsnleftrightarrow}}, {}→ → ,↛ ↛ }{displaystyle {tonrightarrow}}, {}→ → ,↚ ↚ }{displaystyle {tonleftarrow}}, {}← ← ,↛ ↛ }{displaystyle {getsnrightarrow}}, {}← ← ,↚ ↚ }{displaystyle {getsnleftarrow}}, {}↛ ↛ ,¬ ¬ }{displaystyle {nrightarrowneg}}, {}↚ ↚ ,¬ ¬ }{displaystyle {nleftarrowneg}}, {}↛ ↛ ,⊤ ⊤ }{displaystyle {nrightarrowtop {}}, {}↚ ↚ ,⊤ ⊤ }{displaystyle {nleftarrowtop}}, {}↛ ↛ ,Administración Administración }{displaystyle {nrightarrowleftrightarrow}}, {}↚ ↚ ,Administración Administración }{displaystyle {nleftarrowleftrightarrow}}.

Tres elementos

{}Alternativa Alternativa ,Administración Administración ,⊥ ⊥ }{displaystyle {lorleftrightarrowbot}}, {}Alternativa Alternativa ,Administración Administración ,↮ ↮ }{displaystyle {lorleftrightarrownleftrightarrow}}, {}Alternativa Alternativa ,↮ ↮ ,⊤ ⊤ }{displaystyle {lornleftrightarrowtop {}}, {}∧ ∧ ,Administración Administración ,⊥ ⊥ }{displaystyle {landleftrightarrowbot}}, {}∧ ∧ ,Administración Administración ,↮ ↮ }{displaystyle {landleftrightarrownleftrightarrow}}, {}∧ ∧ ,↮ ↮ ,⊤ ⊤ }{displaystyle {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ {}}.

Otro enfoque es usar con los mismos derechos conectores de un cierto 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 un teorema.

La situación, sin embargo, es más complicada en la lógica intuicionista. De sus cinco conectivos, {∧, ∨, →, ¬, ⊥}, sólo la negación "¬" se puede reducir a otros conectores (ver Falso (lógica) § Falso, negación y contradicción para obtener 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.

Lenguaje natural

Los conectores lógicos estándar de la lógica clásica tienen equivalentes aproximados en las gramáticas de los lenguajes naturales. En inglés, como en muchos idiomas, tales expresiones suelen ser conjunciones gramaticales. Sin embargo, también pueden tomar la forma de complementos, sufijos verbales y partículas. Las denotaciones de los conectores del lenguaje natural es un tema importante de investigación en semántica formal, un campo que estudia la estructura lógica de los lenguajes naturales.

Los significados de los conectores del lenguaje natural no son precisamente idénticos a sus equivalentes más cercanos en la lógica clásica. En particular, la disyunción puede recibir una interpretación exclusiva en muchos idiomas. Algunos investigadores han tomado este hecho como evidencia de que la semántica del lenguaje natural no es clásica. Sin embargo, otros mantienen la semántica clásica postulando explicaciones pragmáticas de exclusividad que crean la ilusión de no clasicismo. En tales cuentas, la exclusividad se trata típicamente como una implicatura escalar. Los acertijos relacionados que involucran la disyunción incluyen inferencias de libre elección, la restricción de Hurford y la contribución de la disyunción en preguntas alternativas.

Otras aparentes discrepancias entre el lenguaje natural y la lógica clásica incluyen las paradojas de la implicación material, la anáfora del burro y el problema de los condicionales contrafácticos. Estos fenómenos se han tomado como motivación para identificar las denotaciones de los condicionales del lenguaje natural con operadores lógicos que incluyen el condicional estricto, el condicional estricto variable, así como varios operadores dinámicos.

La siguiente tabla muestra las aproximaciones estándar clásicamente definibles para los conectores ingleses.

Propiedades

Algunos conectivos lógicos poseen propiedades que pueden expresarse en los teoremas que contienen el conectivo. Algunas de esas propiedades que puede tener un conectivo lógico son:

Associativity

Dentro de una expresión que contiene dos o más de los mismos conectores asociativos en una fila, el orden de las operaciones no importa mientras no se cambie la secuencia de los operandos.

Commutativity

Los operandos del conector se pueden cambiar, preservando la equivalencia lógica a la expresión original.

Distribución

Un conector denotado por · distribuye sobre otro conector denotado por +, si a · (b + c) =a · b) + (a · c) para todos los operandos a, b, c.

Idempotence

Siempre que los operandos de la operación son los mismos, el compuesto es lógicamente equivalente al operado.

Absorción

Un par de conectores ∧, ∨ satisfies la ley de absorción si a∧ ∧ ()aAlternativa Alternativa b)=a{displaystyle aland (alor b)=a} para todos los operandos a, b.

Monotonicity

Si f()a₁,... a_n≤ f()b₁,... b_n) para todos a₁,... a_n, b₁,... b_n tal que a₁ ≤ b₁, a₂ ≤ b₂,... a_n ≤ b_n. E.g., ∨, ∧, ⊥, ⊥.

Afinidad

Cada variable siempre marca una diferencia en el valor de la verdad de la operación o nunca marca una diferencia. E.g., ¬, ↔, ↮ ↮ {displaystyle nleftrightarrow }, ⊤, ⊥.

Dualidad

Para leer las asignaciones de valor de verdad para la operación de arriba a abajo en su tabla de verdad es el mismo que tomar el complemento de leer la tabla de la misma u otra conectividad de abajo a arriba. Sin recurrir a tablas de verdad se puede formular como #(a₁, ¬a_n) = ¬g()a₁,... a_n). Por ejemplo, ¬.

Verdadero conservación

El compuesto todos esos argumentos son tautologies es una tautología misma. E.g., ∨, ∧, ∧, →, ↔, ⊂ (ver validez).

Falsehood-preserving

El compuesto todos esos argumentos son contradicciones es una contradicción misma. E.g., latitud, ∧, ↮ ↮ {displaystyle nleftrightarrow }, ⊥, ⊄, ⊅ (ver validez).

Involutividad (para conectores no deseados)

f()f()a) = a. Por ejemplo, la negación en la lógica clásica.

Para la lógica clásica e intuicionista, el "=" símbolo significa que las implicaciones correspondientes "...→..." y "...←..." porque los compuestos lógicos pueden probarse como teoremas, y el "≤" símbolo significa que "...→..." para compuestos lógicos es una consecuencia de la correspondiente "...→..." Conectivos para variables proposicionales. Algunas lógicas multivaluadas pueden tener definiciones incompatibles de equivalencia y orden (implicación).

Tanto la conjunción como la disyunción son asociativas, conmutativas e idempotentes en la lógica clásica, la mayoría de las variedades de lógica polivalente y lógica intuicionista. Lo mismo ocurre con la distributividad de la conjunción sobre la disyunción y la disyunción sobre la conjunción, así como con la ley de absorción.

En la lógica clásica y en algunas variedades de la lógica polivalente, la conjunción y la disyunción son duales, y la negación es autodual; esta última también es autodual en la lógica intuicionista.

Orden de precedencia

Como una manera de reducir el número de paréntesis necesarios, se puede introducir reglas de precedencia: ¬ tiene mayor precedencia que ∧, ∧ higher than ∨, y Alternativa higher than →. Por ejemplo, PAlternativa Alternativa Q∧ ∧ ¬ ¬ R→ → S{displaystyle Pvee Qwedge {neg R}rightarrow S} es corto para ()PAlternativa Alternativa ()Q∧ ∧ ()¬ ¬ R)))→ → S{displaystyle (Pvee (Qwedge (neg R))).

Aquí hay una tabla que muestra una precedencia de operadores lógicos de uso común.

Operador	Precedencia
¬ ¬ {displaystyle neg }	1
∧ ∧ {displaystyle land }	2
Alternativa Alternativa {displaystyle lor }	3
→ → {displaystyle to }	4
Administración Administración {displaystyle leftrightarrow }	5

Sin embargo, no todos los compiladores usan el mismo orden; por ejemplo, también se ha utilizado un orden en el que la disyunción tiene una precedencia menor que la implicación o la biimplicación. A veces, la precedencia entre la conjunción y la disyunción no se especifica, lo que requiere proporcionarla explícitamente en la fórmula dada entre paréntesis. El orden de precedencia determina qué conectivo es el "conectivo principal" al interpretar una fórmula no atómica.

Ciencias de la computación

Se implementa un enfoque funcional de verdad para operadores lógicos como puertas lógicas en circuitos digitales. Prácticamente todos los circuitos digitales (la principal excepción es DRAM) se construyen a partir de puertas NAND, NOR, NOT y de transmisión; ver más detalles en Función de verdad en informática. Los operadores lógicos sobre vectores de bits (correspondientes a álgebras booleanas finitas) son operaciones bit a bit.

Pero no todos los usos de un conector lógico en la programación de computadoras tienen una semántica booleana. Por ejemplo, la evaluación perezosa a veces se implementa 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 material condicional conectivo, 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 como un todo es exitoso ≈ "verdadero" en tal caso). Esto está más cerca de los puntos de vista intuicionistas y constructivistas sobre el condicional material, en lugar de los puntos de vista de la lógica clásica.

Tabla y diagrama de Hasse

Los 16 conectores lógicos se pueden ordenar parcialmente para producir el siguiente diagrama de Hasse. El orden parcial se define declarando que x≤ ≤ Sí.{displaystyle xleq y} si x{displaystyle x} sostiene que así lo hace Sí..{displaystyle y.}