La lógica multivaluada (también llamada lógica multivaluada ) es un cálculo proposicional en el que existen más de dos valores de verdad . Tradicionalmente, en el cálculo lógico de Aristóteles , solo había dos valores posibles (es decir, verdadero y falso ) para cualquier proposición . La lógica clásica bivaluada puede extenderse a la lógica n - valuada para n mayor que 2. Las más populares en la literatura son la trivaluada (por ejemplo, la de Łukasiewicz y la de Kleene , que aceptan los valores verdadero , falso y desconocido ), la tetravaluada , la heptvaluada , la nonvaluada , la finita (con un número finito de valores) con más de tres valores, y la infinita (con un número infinito de valores), como la lógica difusa y la lógica de probabilidad .
Historia
Aristóteles , el «padre de la lógica [bivalente]», [ 1 ] aceptó el principio del tercero excluido , pero hizo una distinción importante sobre el principio de bivalencia. En ( De Interpretatione , cap. IX ), [ 2 ] argumentó que las afirmaciones sobre eventos futuros no siempre pueden ser definitivamente verdaderas o falsas. Sin embargo, no desarrolló esta idea en una lógica multivalente sistemática; permaneció como una excepción específica dentro de su marco clásico. Los lógicos siguieron esta tradición lógica aristotélica hasta el siglo XX, utilizando consistentemente el principio del tercero excluido, aunque reconociendo sus preocupaciones sobre los contingentes futuros. Las alternativas sistemáticas a la lógica clásica surgieron recién en la época moderna.
El siglo XX trajo de vuelta la idea de la lógica multivaluada. El lógico y filósofo polaco Jan Łukasiewicz comenzó a crear sistemas de lógica multivaluada en 1920, utilizando un tercer valor, posible , para abordar la paradoja de Aristóteles de la batalla naval . Mientras tanto, el matemático estadounidense Emil L. Post (1921) también introdujo la formulación de grados de verdad adicionales con n ≥ 2, donde n son los valores de verdad. Más tarde, Jan Łukasiewicz y Alfred Tarski formularon juntos una lógica sobre n valores de verdad donde n ≥ 2. En 1932, Hans Reichenbach formuló una lógica de muchos valores de verdad donde n →∞. Kurt Gödel en 1932 demostró que la lógica intuicionista no es una lógica multivaluada finita , y definió un sistema de lógicas de Gödel intermedio entre la lógica clásica y la intuicionista; Estas lógicas se conocen como lógicas intermedias .
Ejemplos
Kleene (fuerte) K 3 y lógica del sacerdote P 3
La "lógica (fuerte) de indeterminación" de Kleene K 3 (a veces) y la "lógica de la paradoja" de Priest añaden un tercer valor de verdad indefinido o indeterminado I. Las funciones de verdad para la negación (¬), la conjunción (∧), la disyunción (∨), la implicación ( → K ) y la bicondicional ( ↔ K ) vienen dadas por: [ 3 ]
La diferencia entre ambas lógicas radica en cómo se definen las tautologías . En K 3, solo T es un valor de verdad designado , mientras que en P 3 lo son tanto T como I. (Una fórmula lógica se considera una tautología si se evalúa a un valor de verdad designado). En la lógica de Kleene, I puede interpretarse como subdeterminada , es decir, no es ni verdadera ni falsa, mientras que en la lógica de Priest, I puede interpretarse como sobredeterminada , es decir, es verdadera y falsa a la vez. K 3 no tiene tautologías, mientras que P 3 tiene las mismas tautologías que la lógica clásica bivalente. [ 4 ]
La lógica trivalente interna de Bochvar
Otra lógica es la lógica trivalente interna de Dmitry Bochvar., también llamada lógica trivalente débil de Kleene. Excepto por la negación y la bicondicional, sus tablas de verdad son todas diferentes a las anteriores. [ 5 ]
El valor de verdad intermedio en la lógica interna de Bochvar puede describirse como contagioso porque se propaga en una fórmula independientemente del valor de cualquier otra variable. [ 5 ]
Lógica de Belnap ( B 4 )
La lógica B 4 de Belnap combina K 3 y P 3 . El valor de verdad sobredeterminado se denota aquí como B y el valor de verdad subdeterminado como N .
Lógicas de Gödel G k y G ∞
En 1932 Gödel definió [ 6 ] una familiade lógicas multivaluadas, con un número finito de valores de verdad, Por ejemplotiene valores de verdadytiene. De manera similar definió una lógica con infinitos valores de verdad,, en el que los valores de verdad son todos los números reales en el intervaloEl valor de verdad designado en estas lógicas es 1.
La conjuncióny la disyunciónse definen respectivamente como el mínimo y el máximo de los operandos:
Negacióny sus implicacionesse definen de la siguiente manera:
Las lógicas de Gödel son completamente axiomatizables; es decir, es posible definir un cálculo lógico en el que todas las tautologías sean demostrables. La implicación anterior es la implicación única de Heyting definida por el hecho de que las operaciones de supremo y mínimo forman un retículo completo con una ley distributiva infinita, que define una estructura de álgebra de Heyting completa y única sobre el retículo.
Lógicas de Łukasiewicz L v y L ∞
Implicacióny negaciónJan Łukasiewicz las definió mediante las siguientes funciones:
Al principio, Łukasiewicz utilizó estas definiciones en 1920 para su lógica trivalente., con valores de verdadEn 1922 desarrolló una lógica con infinitos valores., en el que los valores de verdad abarcaban los números reales en el intervaloEn ambos casos, el valor de verdad designado fue 1. [ 7 ]
Al adoptar valores de verdad definidos de la misma manera que para las lógicas de GödelEs posible crear una familia de lógicas con valores finitos., el mencionado anteriormentey la lógica, en el que los valores de verdad están dados por los números racionales en el intervalo. El conjunto de tautologías enyes idéntico.
Lógica del producto Π
En la lógica de producto tenemos valores de verdad en el intervalo, una conjuncióny una implicación, definido de la siguiente manera [ 8 ]
Además, existe un valor designado negativo.que denota el concepto de falso . A través de este valor es posible definir una negación.y una conjunción adicionalcomo sigue:
y luego.
Lógica de publicación P m
En 1921, Post definió una familia de lógicas.con (como eny) los valores de verdadNegacióny conjuncióny disyunción se definen de la siguiente manera:
Lógicas de rosas
En 1951, Alan Rose definió otra familia de lógicas para sistemas cuyos valores de verdad forman retículos . [ 9 ]
Relación con la lógica clásica
Las lógicas suelen ser sistemas destinados a codificar reglas para preservar alguna propiedad semántica de las proposiciones a través de transformaciones. En la lógica clásica , esta propiedad es la verdad . En un argumento válido, la verdad de la proposición derivada está garantizada si las premisas son conjuntamente verdaderas, ya que la aplicación de pasos válidos preserva la propiedad. Sin embargo, esa propiedad no tiene por qué ser la de la verdad ; en su lugar, puede ser algún otro concepto.
Las lógicas multivaluadas buscan preservar la propiedad de designación (o de ser designado). Dado que existen más de dos valores de verdad, las reglas de inferencia pueden estar diseñadas para preservar más que solo el que corresponde (en el sentido relevante) a la verdad. Por ejemplo, en una lógica trivaluada, a veces se designan los dos mayores valores de verdad (cuando se representan como, por ejemplo, enteros positivos) y las reglas de inferencia preservan estos valores. Precisamente, un argumento válido será aquel en el que el valor de las premisas consideradas conjuntamente siempre será menor o igual que la conclusión.
Por ejemplo, la propiedad preservada podría ser la justificación , el concepto fundamental de la lógica intuicionista . Así, una proposición no es verdadera ni falsa; en cambio, está justificada o es errónea. Una diferencia clave entre justificación y verdad, en este caso, es que la ley del tercero excluido no se cumple: una proposición que no es errónea no está necesariamente justificada; simplemente no se demuestra que sea errónea. La diferencia clave reside en la determinación de la propiedad preservada: se puede demostrar que P está justificada, que P es errónea, o no poder demostrar ninguna de las dos. Un argumento válido preserva la justificación a través de transformaciones, por lo que una proposición derivada de proposiciones justificadas sigue estando justificada. Sin embargo, existen demostraciones en la lógica clásica que dependen de la ley del tercero excluido; dado que dicha ley no es utilizable bajo este esquema, hay proposiciones que no pueden demostrarse de esa manera.
La tesis de Suszko
Completitud funcional de lógicas multivaluadas
La completitud funcional es un término que se utiliza para describir una propiedad especial de las lógicas y álgebras finitas. Se dice que el conjunto de conectivas de una lógica es funcionalmente completo o adecuado si y solo si dicho conjunto puede utilizarse para construir una fórmula que corresponda a cada posible función de verdad . [ 10 ] Un álgebra adecuada es aquella en la que toda aplicación finita de variables puede expresarse mediante alguna composición de sus operaciones. [ 11 ]
La lógica clásica: CL = ({0,1}, ¬ , →, ∨, ∧, ↔) es funcionalmente completa, mientras que ninguna lógica de Łukasiewicz ni lógicas con infinitos valores posee esta propiedad. [ 11 ] [ 12 ]
Podemos definir una lógica multivaluada finita como L n ({1, 2, ..., n } ƒ 1 , ..., ƒ m ) donde n ≥ 2 es un número natural dado. Post (1921) demuestra que, suponiendo que una lógica es capaz de producir una función de cualquier modelo de orden m , existe alguna combinación correspondiente de conectivos en una lógica adecuada L n que puede producir un modelo de orden m+1 . [ 13 ]
Aplicaciones
Las aplicaciones conocidas de la lógica multivaluada se pueden clasificar a grandes rasgos en dos grupos. [ 14 ] El primer grupo utiliza la lógica multivaluada para resolver problemas binarios de manera más eficiente. Por ejemplo, un enfoque conocido para representar una función booleana de múltiples salidas consiste en tratar su parte de salida como una única variable multivaluada y convertirla en una función característica de una sola salida (específicamente, la función indicadora ). Otras aplicaciones de la lógica multivaluada incluyen el diseño de matrices lógicas programables (PLA) con decodificadores de entrada, la optimización de máquinas de estados finitos , pruebas y verificación.
El segundo grupo se centra en el diseño de circuitos electrónicos que emplean más de dos niveles discretos de señales, como memorias multivaluadas, circuitos aritméticos y matrices de puertas programables en campo (FPGA). Los circuitos multivaluados presentan varias ventajas teóricas sobre los circuitos binarios estándar. Por ejemplo, la interconexión dentro y fuera del chip puede reducirse si las señales del circuito asumen cuatro o más niveles en lugar de solo dos. En el diseño de memorias, almacenar dos bits de información por celda de memoria, en lugar de uno, duplica la densidad de la memoria en el mismo tamaño de chip . Las aplicaciones que utilizan circuitos aritméticos suelen beneficiarse del uso de alternativas a los sistemas numéricos binarios. Por ejemplo, los sistemas numéricos de residuos y redundantes [ 15 ] pueden reducir o eliminar los acarreos de propagación que intervienen en la suma o resta binaria normal, lo que resulta en operaciones aritméticas de alta velocidad. Estos sistemas numéricos tienen una implementación natural mediante circuitos multivaluados. Sin embargo, la viabilidad de estas ventajas potenciales depende en gran medida de la disponibilidad de implementaciones de circuitos, que deben ser compatibles o competitivas con las tecnologías estándar actuales. Además de ayudar en el diseño de circuitos electrónicos, la lógica multivaluada se utiliza ampliamente para probar circuitos en busca de fallas y defectos. Básicamente, todos los algoritmos conocidos de generación automática de patrones de prueba (ATG) utilizados para la prueba de circuitos digitales requieren un simulador que pueda resolver lógica de 5 valores (0, 1, x, D, D'). [ 16 ] Los valores adicionales —x, D y D'— representan (1) desconocido/no inicializado, (2) un 0 en lugar de un 1 y (3) un 1 en lugar de un 0.
Una tercera área de aplicación se encuentra en el procesamiento de información cuántica , donde la unidad computacional natural no es necesariamente un cúbit binario . Un qudit es un sistema cuántico con d > 2 niveles discretos, y los protocolos de comunicación cuántica que utilizan qudits pueden lograr mayores capacidades de canal y garantías de seguridad más sólidas que los protocolos basados en cúbits. La estructura algebraica de las operaciones de qudit se describe naturalmente mediante lógica multivaluada sobre el mismo número de niveles, y varios grupos de investigación han explorado la síntesis y optimización de circuitos cuánticos de qudits utilizando conceptos de lógica multivaluada como base. Las plataformas fotónicas, en particular, admiten la codificación de alta dimensión en grados de libertad como frecuencia, momento angular orbital y intervalos de tiempo, lo que convierte a la comunicación cuántica basada en qudits en un área activa de desarrollo experimental. [ 17 ]
Lugares de investigación
El Simposio Internacional IEEE sobre Lógica Multivaluada (ISMVL) se celebra anualmente desde 1970. Se centra principalmente en aplicaciones de diseño y verificación digital. [ 18 ] También existe una revista sobre lógica multivaluada y computación blanda . [ 19 ]
Véase también
- Lógica matemática
- Grados de verdad
- lógica difusa
- Lógica de Gödel
- Lógica de siete valores de Jaina
- Lógica de Kleene
- Álgebra de Kleene (con involución)
- Lógica de Łukasiewicz
- La lógica de Belnap
- MV-álgebra
- Lógica de la publicación
- Principio de bivalencia
- Un anterior
- Lógica de relevancia
- Lógica digital
- MVCML , lógica de modo actual multivalor
- IEEE 1164, un estándar de nueve valores para VHDL
- IEEE 1364, un estándar de cuatro valores para Verilog.
- Lógica de tres estados
- Lógica basada en ruido
Referencias
- ↑ Hurley, Patrick. Una introducción concisa a la lógica , 9.ª edición. (2006).
- ↑ Jules Vuillemin, Necesidad o contingencia , Apuntes de clase del CSLI, n.° 56, Stanford, 1996, págs. 133-167
- ↑ ( Gottwald 2005 , p. 19)
- ↑ Humberstone, Lloyd (2011). The Connectives . Cambridge, Massachusetts: The MIT Press. 201 págs . ISBN 978-0-262-01654-4.
- 1 2 ( Bergmann 2008 , pág. 80)
- ↑ Gödel, Kurt (1932). "Zum intuitionistischen Aussagenkalkül". Anzeiger der Akademie der Wissenschaften en Viena (69): 65 y siguientes.
- ↑ Kreiser, Lothar; Gottwald, Sigfrido; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung . Berlín: Akademie-Verlag. págs. 41 y siguientes: 45 y siguientes. ISBN 978-3-05-000274-3.
- ↑ Hajek, Petr: Lógica difusa . En: Edward N. Zalta: La enciclopedia de filosofía de Stanford , primavera de 2009. ()
- ↑ Rose, Alan (diciembre de 1951). "Sistemas de lógica cuyos valores de verdad forman retículos". Mathematische Annalen . 123 : 152–165 . doi : 10.1007/BF02054946 . S2CID 119735870 .
- ↑ Smith, Nicholas (2012). Lógica: Las leyes de la verdad . Princeton University Press. pág. 124.
- 1 2 Malinowski, Grzegorz (1993). Lógicas multivaluadas . Clarendon Press. págs. 26–27 .
- ↑ Church, Alonzo (1996). Introducción a la lógica matemática . Princeton University Press. ISBN 978-0-691-02906-1.
- ↑ Post, Emil L. (1921). "Introducción a una teoría general de proposiciones elementales". American Journal of Mathematics . 43 (3): 163– 185. doi : 10.2307/2370324 . hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN 0002-9327 . JSTOR 2370324 .
- ↑ Dubrova, Elena (2002). Síntesis y optimización de lógica multivaluada , en Hassoun S. y Sasao T., editores, Síntesis y verificación de lógica , Kluwer Academic Publishers, pp. 89-114
- ↑ Meher, Pramod Kumar; Valls, Javier; Juang, Tso-Bing; Sridharan, K.; Maharatna, Koushik (22 de agosto de 2008). "50 años de CORDIC: algoritmos, arquitecturas y aplicaciones" (PDF) . IEEE Transactions on Circuits & Systems I: Regular Papers . 56 (9) (publicado el 9 de septiembre de 2009): 1893–1907 . doi : 10.1109 /TCSI.2009.2025803 . S2CID 5465045. Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 3 de enero de 2016 .
- ↑ Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Pruebas de sistemas digitales y diseño comprobable . Nueva York: Computer Science Press. pág . 183. ISBN 978-0-7803-1062-9.
- ↑ Erhard, Manuel; Krenn, Mario; Zeilinger, Anton (2020). "Avances en el entrelazamiento cuántico de alta dimensión". Nature Reviews Physics . 2 (7): 365– 381. arXiv : 1911.10006 . doi : 10.1038/s42254-020-0193-5 .
- ↑ "Simposio Internacional IEEE sobre Lógica Multivaluada (ISMVL)" . www.informatik.uni-trier.de/~ley . Archivado del original el 20 de abril de 2011. Consultado el 16 de abril de 2011 .
- ↑ "Página principal de MVLSC" . Archivado del original el 15 de marzo de 2014. Consultado el 12 de agosto de 2011 .
Lecturas adicionales
General
- Augusto, Luis M. (2017). Lógicas multivaluadas: Una introducción matemática y computacional. Londres: College Publications. 340 páginas. ISBN 978-1-84890-250-3. Página web
- Béziau J.-Y. (1997), ¿Qué es la lógica multivaluada ? Actas del 27º Simposio Internacional sobre Lógica Multivaluada , IEEE Computer Society, Los Alamitos, pp. 117–121.
- Malinowski, Gregorz, (2001), Lógicas multivaluadas, en Goble, Lou, ed., The Blackwell Guide to Philosophical Logic . Blackwell.
- Bergmann, Merrie (2008), Introducción a la lógica difusa y multivaluada: semántica, álgebras y sistemas de derivación , Cambridge University Press, ISBN 978-0-521-88128-9
- Cignoli, RLO, D'Ottaviano, I, ML , Mundici, D., (2000). Fundamentos algebraicos del razonamiento multivaluado . Kluwer.
- Malinowski, Grzegorz (1993). Lógicas multivaluadas . Clarendon Press. ISBN 978-0-19-853787-8.
- S. Gottwald , Tratado sobre lógicas multivaluadas. Estudios en lógica y computación, vol. 9, Research Studies Press: Baldock, Hertfordshire, Inglaterra, 2001.
- Gottwald, Siegfried (2005). "Lógicas multivaluadas" (PDF) . Archivado del original el 3 de marzo de 2016.
{{cite journal}}: La cita de la revista requiere|journal=( ayuda ) CS1 maint: bot: estado de la URL original desconocido ( enlace ) - Miller, D. Michael; Thornton, Mitchell A. (2008). Lógica multivaluada: conceptos y representaciones . Conferencias de síntesis sobre circuitos y sistemas digitales. Vol. 12. Morgan & Claypool Publishers. ISBN 978-1-59829-190-2.
- Hájek P. , (1998), Metamatemáticas de la lógica difusa . Kluwer. (Lógica difusa entendida como lógica multivaluada sui generis ).
Específico
- Alexandre Zinoviev , Problemas filosóficos de la lógica multivaluada , D. Reidel Publishing Company, 169 págs., 1963.
- Prior A. 1957, Tiempo y modalidad. Oxford University Press , basado en sus conferencias John Locke de 1956.
- Goguen JA 1968/69, La lógica de los conceptos inexactos , Synthese, 19, 325–373.
- Chang CC y Keisler HJ 1966. Teoría de modelos continuos , Princeton, Princeton University Press.
- Gerla G. 2001, Lógica difusa: herramientas matemáticas para el razonamiento aproximado , Kluwer Academic Publishers, Dordrecht.
- Novák, V., Perfilieva, I., Močkoř, J., (1999), Principios matemáticos de la lógica difusa . Kluwer, Boston.
- Pavelka J. 1979, Sobre lógica difusa I: Reglas de inferencia multivaluadas , Zeitschr. f. math. Logik und Grundlagen d. Math., 25, 45–52.
- Metcalfe, George; Olivetti, Nicola; Dov M. Gabbay (2008). Teoría de la demostración para lógicas difusas . Springer. ISBN 978-1-4020-9408-8.También abarca la teoría de la demostración de lógicas multivaluadas, siguiendo la tradición de Hájek.
- Hähnle, Reiner (1993). Deducción automatizada en lógicas multivaluadas . Clarendon Press. ISBN 978-0-19-853989-6.
- Azevedo, Francisco (2003). Resolución de restricciones sobre lógicas multivaluadas: aplicación a circuitos digitales . IOS Press. ISBN 978-1-58603-304-0.
- Bolc, Leonard; Borowik, Piotr (2003). Lógicas multivaluadas 2: Razonamiento automatizado y aplicaciones prácticas . Springer. ISBN 978-3-540-64507-8.
- Stanković, Radomir S.; Astola, Jaakko T.; Moraga, Claudio (2012). Representación de funciones lógicas multivaluadas . Morgan & Claypool Publishers. doi : 10.2200/S00420ED1V01Y201205DCS037 . ISBN 978-1-60845-942-1.
- Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1994). Pruebas de sistemas digitales y diseño comprobable . Nueva York: Computer Science Press. ISBN 978-0-7803-1062-9.
Enlaces externos
- Gottwald, Siegfried (2022). "Lógica multivaluada" . En Zalta, Edward N. (ed.). La enciclopedia de filosofía de Stanford (edición de verano de 2022) .
- Shramko, Yaroslav y Wansing, Heinrich (2021). "Valores de verdad" . En Zalta, Edward N. (ed.). La enciclopedia de filosofía de Stanford (edición de invierno de 2021) .
- Comité Técnico de Lógica Multivaluada de la Sociedad de Computación del IEEE
- Recursos para la lógica multivaluada por Reiner Hähnle, Universidad de Chalmers
- Servidor W3 de lógica multivaluada (archivado)
- Yaroslav Shramko; Heinrich Wansing (2020). "La tesis de Suszko" . Enciclopedia de filosofía de Stanford .
- Carlos Caleiro, Walter Carnielli, Marcelo E. Coniglio y João Marcos, Two's company: "The humbug of many logical values" Archivado el 29 de septiembre de 2014 en Wayback Machine en Jean-Yves Beziau, ed. (2007). Logica Universalis: Towards a General Theory of Logic (2.ª ed.). Springer Science & Business Media. pp. 174–194 . ISBN 978-3-7643-8354-1.
- Lógica multivaluada