stringtranslate.com

Conectiva lógica

Diagrama de Hasse de conectivos lógicos.

En lógica , un conectivo lógico (también llamado operador lógico , conectivo oracional u operador oracional ) es una constante lógica . Los conectivos se pueden utilizar para conectar fórmulas lógicas. Por ejemplo, en la sintaxis de la lógica proposicional , el conectivo binario se puede utilizar para unir las dos fórmulas atómicas y , lo que da como resultado la fórmula compleja .

Los conectivos comunes incluyen negación , disyunción , conjunción , implicación y equivalencia . En los sistemas estándar de lógica clásica , estos conectivos se interpretan como funciones de verdad , aunque reciben una variedad de interpretaciones alternativas en lógicas no clásicas . Sus interpretaciones clásicas son similares a los significados de expresiones del lenguaje natural como "no", "o", "y" y "si" en inglés , pero no idénticas. 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 sólida .

Un conectivo lógico es similar, pero no equivalente, a una sintaxis comúnmente utilizada en lenguajes de programación llamada operador condicional . [1] [ se necesita una mejor fuente ]

Descripción general

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

Los conectores lógicos se pueden utilizar para unir cero o más enunciados, por lo que se puede hablar de conectores lógicos n - arios . Las constantes booleanas True y False se pueden considerar operadores cero-arios. La negación es un conector 1-ario, y así sucesivamente.

Lista de conectores lógicos comunes

Los conectivos lógicos más utilizados incluyen los siguientes: [2]

Por ejemplo, el significado de las afirmaciones está lloviendo (denotado por ) y estoy en casa (denotado por ) se transforma cuando las dos se combinan con conectores lógicos:

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 ).

Esta tabla resume la terminología:

Historia de las notaciones

Algunos autores usaron letras para conectivos: para conjunción ("und" en alemán para "y") y para disyunción ("oder" en alemán para "o") en los primeros trabajos de Hilbert (1904); [17] para negación, para conjunción, para negación alternativa, para disyunción, para implicación, para bicondicional en Łukasiewicz en 1929.

Redundancia

Un conectivo lógico como la implicación inversa " " 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 (notablemente, en la lógica clásica ), ciertas declaraciones compuestas esencialmente diferentes son lógicamente equivalentes . Un ejemplo menos trivial de una redundancia es la equivalencia clásica entre y . Por lo tanto, un sistema lógico basado en la clásica no necesita el operador condicional " " si " " (no) y " " (o) ya están en uso, o puede usar " " solo 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 y con salidas binarias de cuatro dígitos . [18] Estas corresponden a posibles elecciones de conectivos 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 consiste en elegir un conjunto mínimo y definir otros conectivos mediante alguna forma lógica, como en el ejemplo anterior con el condicional material. Los siguientes son los conjuntos mínimos funcionalmente completos de operadores en lógica clásica cuyas aridades no superan 2:

Un elemento
, .
Dos elementos
, , , , , , , , , , , , , , , , .​
Tres elementos
, , , , , .

Otro enfoque consiste en utilizar conectivos de derechos iguales 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 "¬" puede reducirse a otros conectivos (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 conectivos 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, dichas expresiones son típicamente conjunciones gramaticales . Sin embargo, también pueden tomar la forma de complementadores , sufijos verbales y partículas . Las denotaciones de los conectores de los lenguajes naturales son 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 exactamente 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 al postular explicaciones pragmáticas de la exclusividad que crean la ilusión de no clasicidad. En tales explicaciones, la exclusividad se trata típicamente como una implicatura escalar . Los acertijos relacionados que involucran la disyunción incluyen las inferencias de libre elección , la restricción de Hurford y la contribución de la disyunción en preguntas alternativas .

Otras discrepancias aparentes 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, incluidos el condicional estricto , el condicional estricto variable , así como varios operadores dinámicos .

La siguiente tabla muestra las aproximaciones clásicamente definibles estándar para los conectivos 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:

Asociatividad
Dentro de una expresión que contiene dos o más de los mismos conectivos asociativos en una fila, el orden de las operaciones no importa siempre y cuando no se modifique la secuencia de los operandos.
Conmutatividad
Los operandos del conectivo se pueden intercambiar, preservando la equivalencia lógica con la expresión original.
Distributividad
Un conectivo denotado por · se distribuye sobre otro conectivo denotado por +, si a · ( b + c ) = ( a · b ) + ( a · c ) para todos los operandos a , b , c .
Idempotencia
Siempre que los operandos de la operación sean los mismos, el compuesto es lógicamente equivalente al operando.
Absorción
Un par de conectivos ∧, ∨ satisface la ley de absorción si para todos los operandos a , b .
Monotonía
Si f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) para todo a 1 , ..., a n , b 1 , ..., b n ∈ {0,1} tal que a 1b 1 , a 2b 2 , ..., a nb n . Por ejemplo, ∨, ∧, ⊤, ⊥.
Afinidad
Cada variable siempre hace una diferencia en el valor de verdad de la operación o nunca hace una diferencia. Por ejemplo, ¬, ↔, , ⊤, ⊥.
Dualidad
Leer las asignaciones de valores de verdad para la operación de arriba hacia abajo en su tabla de verdad es lo mismo que tomar el complemento de leer la tabla del mismo u otro conectivo de abajo hacia arriba. Sin recurrir a las tablas de verdad, se puede formular como a 1 , ..., ¬ a n ) = ¬ g ( a 1 , ..., a n ) . Por ejemplo, ¬.
Preservación de la verdad
La suma de todos esos argumentos es una tautología en sí misma. Por ejemplo, ∨, ∧, ⊤, →, ↔, ⊂ (ver validez ).
Preservación de la falsedad
El argumento compuesto "todos esos argumentos son contradicciones" es en sí mismo una contradicción. Por ejemplo, ∨, ∧, , ⊥, ⊄, ⊅ (ver validez ).
Involutividad (para conectivos unarios)
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 "...←..." para los compuestos lógicos pueden demostrarse como teoremas, y el símbolo "≤" significa que "...→..." para los compuestos lógicos es una consecuencia de los conectores "...→..." correspondientes para las variables proposicionales. Algunas lógicas polivalentes pueden tener definiciones incompatibles de equivalencia y orden (consecuencia).

Tanto la conjunción como la disyunción son asociativas, conmutativas e idempotentes en la lógica clásica, en la mayoría de las variedades de lógica polivalente y en la lógica intuicionista. Lo mismo es cierto en lo que respecta a la distributividad de la conjunción respecto de la disyunción y de la disyunción respecto de la conjunción, así como en lo que respecta a 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 forma de reducir la cantidad de paréntesis necesarios, se pueden introducir reglas de precedencia : ¬ tiene mayor precedencia que ∧, ∧ mayor que ∨ y ∨ mayor que →. Por ejemplo, es la abreviatura de .

A continuación se muestra una tabla que muestra una precedencia de operadores lógicos de uso común. [19] [20]

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

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 si y solo si siempre que se cumple, entonces también se cumple

Aplicaciones

Los conectores lógicos se utilizan en informática y en la teoría de conjuntos .

Ciencias de la Computación

Un enfoque de verdad funcional para los operadores lógicos se implementa como puertas lógicas en circuitos digitales . Prácticamente todos los circuitos digitales (la principal excepción es DRAM ) se construyen a partir de NAND , NOR , NOT y puertas de transmisión ; consulte más detalles en Función de verdad en informática . 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 conectivo lógico en programación informática tienen una semántica booleana. Por ejemplo, a veces se implementa una evaluación perezosa para P  ∧  Q y P  ∨  Q , por lo que estos conectivos no son conmutativos si una o ambas de las expresiones P , Q tienen efectos secundarios . Además, un condicional , que en cierto sentido corresponde al conectivo 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 totalidad es exitoso ≈ "verdadero" en tal caso). Esto se acerca más a las opiniones intuicionistas y constructivistas sobre el condicional material, en lugar de a las opiniones de la lógica clásica.

Teoría de conjuntos

Los conectivos lógicos se utilizan para definir las operaciones fundamentales de la teoría de conjuntos , [22] de la siguiente manera:

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

Véase también

Referencias

  1. ^ Cogwheel. "¿Cuál es la diferencia entre el operador /lógico y el condicional?". Stack Overflow . Consultado el 9 de abril de 2015 .
  2. ^ Chao, C. (2023).数理逻辑形式化方法的应用[ Lógica matemática: aplicaciones del método de formalización ] (en chino). Beijing: preimpresión. págs. 15-28.
  3. ^ ab Heyting, A. (1930). "Die formalen Regeln der intuitionistischen Logik". Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse (en alemán): 42–56.
  4. ^ Denis Roegel (2002), Un breve estudio de las notaciones lógicas del siglo XX (ver el cuadro en la página 2).
  5. ^ Frege, G. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens . Halle a/S.: Verlag von Louis Nebert. pag. 10.
  6. ^ abc Russell (1908) Lógica matemática basada en la teoría de tipos (American Journal of Mathematics 30, p222–262, también en De Frege a Gödel editado por van Heijenoort).
  7. ^ Peano (1889) Arithmetices principia, nova método exposita .
  8. ^ ab Schönfinkel (1924) Über die Bausteine ​​der mathematischen Logik , traducido como Sobre los componentes básicos de la lógica matemática en De Frege a Gödel editado por van Heijenoort.
  9. ^ Peirce (1867) Sobre una mejora en el cálculo lógico de Boole.
  10. ^ Hilbert, D. (1918). Bernays, P. (ed.). Prinzipien der Mathematik . Apuntes de conferencias en la Universität Göttingen, semestre de invierno, 1917-1918; Reimpreso como Hilbert, D. (2013). "Prinzipien der Mathematik". En Ewald, W.; Sieg, W. (eds.). Lecciones de David Hilbert sobre los fundamentos de la aritmética y la lógica 1917-1933 . Heidelberg, Nueva York, Dordrecht y Londres: Springer. págs. 59-221.
  11. ^ Bourbaki, N. (1954). Teoría de los conjuntos . París: Hermann & Cie, Éditeurs. pag. 14.
  12. ^ Frege, G. (1879). Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens (en alemán). Halle a/S.: Verlag von Louis Nebert. pag. 15.
  13. ^ Becker, A. (1933). Die Aristotelische Theorie der Möglichkeitsschlösse: Eine logisch-philologische Untersuchung der Kapitel 13-22 von Analytica priora I de Aristóteles (en alemán). Berlín: Junker und Dünnhaupt Verlag. pag. 4.
  14. ^ Bourbaki, N. (1954). Théorie des ensembles (en francés). París: Hermann & Cie, Éditeurs. pag. 32.
  15. ^ Gentzen (1934) Untersuchungen über das logische Schließen .
  16. ^ Chazal (1996): Elementos de lógica formal.
  17. ^ Hilbert, D. (1905) [1904]. "Über die Grundlagen der Logik und der Arithmetik". En Krazer, K. (ed.). Verhandlungen des Dritten Internationalen Mathematiker Kongresses en Heidelberg del 8 al 13 de agosto de 1904 . págs. 174-185.
  18. ^ Bocheński (1959), Resumen de lógica matemática , passim.
  19. ^ O'Donnell, John; Hall, Cordelia; Page, Rex (2007), Matemáticas discretas utilizando una computadora, Springer, pág. 120, ISBN 9781846285981.
  20. ^ Allen, Colin; Hand, Michael (2022). Introducción a la lógica (3.ª ed.). Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-54364-4.
  21. ^ Jackson, Daniel (2012), Abstracciones de software: lógica, lenguaje y análisis, MIT Press, pág. 263, ISBN 9780262017152.
  22. ^ Pinter, Charles C. (2014). Un libro de teoría de conjuntos . Mineola, Nueva York: Dover Publications, Inc., págs. 26-29. ISBN 978-0-486-49708-2.
  23. ^ ab "Operaciones con conjuntos". www.siue.edu . Consultado el 11 de junio de 2024 .
  24. ^ abcde "1.5 Lógica y conjuntos". www.whitman.edu . Consultado el 11 de junio de 2024 .
  25. ^ "Conjunto de teorías". mirror.clarkson.edu . Consultado el 11 de junio de 2024 .
  26. ^ "Inclusión y relaciones entre conjuntos". autry.sites.grinnell.edu . Consultado el 11 de junio de 2024 .
  27. ^ "Complemento y diferencia de conjuntos". web.mnstate.edu . Consultado el 11 de junio de 2024 .
  28. ^ Cooper, A. «Operaciones con conjuntos y subconjuntos: fundamentos de las matemáticas» . Consultado el 11 de junio de 2024 .
  29. ^ ab "Conceptos básicos". www.siue.edu . Consultado el 11 de junio de 2024 .
  30. ^ Cooper, A. «Operaciones con conjuntos y subconjuntos: fundamentos de las matemáticas» . Consultado el 11 de junio de 2024 .
  31. ^ Cooper, A. «Operaciones con conjuntos y subconjuntos: fundamentos de las matemáticas» . Consultado el 11 de junio de 2024 .

Fuentes

Enlaces externos