stringtranslate.com

Lógica multivalor

La lógica multivaluada (también lógica multivaluada o 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 , sólo había dos valores posibles (es decir, "verdadero" y "falso") para cualquier proposición . La lógica clásica de dos valores puede extenderse a la lógica de n valores para n mayor que 2. Las más populares en la literatura son las de tres valores (por ejemplo, las de Łukasiewicz y Kleene , que aceptan los valores "verdadero", "falso" y " desconocido"), de cuatro valores , de nueve valores , de valores finitos (de valores finitos) con más de tres valores, y de valores infinitos (de valores infinitos), como la lógica difusa y la lógica de probabilidad .

Historia

Es un error que el primer lógico clásico conocido que no aceptó plenamente la ley del tercero excluido fuera Aristóteles (quien, irónicamente, también es considerado generalmente como el primer lógico clásico y el "padre de la lógica [de dos valores]" [1 ] ). De hecho, Aristóteles no cuestionó la universalidad de la ley del tercero excluido, sino la universalidad del principio de bivalencia: admitió que este principio no se aplicaba en todos los casos a los acontecimientos futuros ( De Interpretatione , cap. IX ), [2] pero No creó un sistema de lógica multivalor para explicar este comentario aislado. Hasta la llegada del siglo XX, los lógicos posteriores siguieron la lógica aristotélica , que incluye o asume la ley del tercero excluido .

El siglo XX recuperó la idea de la lógica multivalor. 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 la batalla naval de Aristóteles . 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 de valores finitos 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 Priest logic P 3

La "(fuerte) lógica de la indeterminación" K 3 de Kleene (a veces ) y la "lógica de la paradoja" de Priest añaden un tercer valor de verdad "indefinido" o "indeterminado" I . La verdad funciona para negación (¬), conjunción (∧), disyunción (∨), implicación (k), y bicondicional (k) están dados por: [3]

La diferencia entre las dos 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 tanto T como I lo son (una fórmula lógica se considera una tautología si se evalúa como un valor de verdad designado). En la lógica de Kleene puedo ser interpretado como "subdeterminado", no siendo ni verdadero ni falso, mientras que en la lógica de Priest puedo ser interpretado como "sobredeterminado", siendo tanto verdadero como falso. K 3 no tiene tautologías, mientras que P 3 tiene las mismas tautologías que la lógica clásica de dos valores. [4]

La lógica interna de tres valores de Bochvar

Otra lógica es la lógica de tres valores "interna" de Dmitry Bochvar , también llamada lógica débil de tres valores de Kleene. A excepción de la negación y el 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 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 familia de lógicas polivaluadas, con un número finito de valores de verdad , por ejemplo tiene los valores de verdad y tiene . De manera similar definió una lógica con infinitos valores de verdad, en la que los valores de verdad son todos los números reales en el intervalo . El valor de verdad designado en estas lógicas es 1.

La conjunción y la disyunción se definen respectivamente como el mínimo y máximo de los operandos:

La negación y la implicación se 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 suprema y mínima forman una red completa con una ley distributiva infinita, que define una estructura de álgebra de Heyting completa y única en la red.

Lógicas de Łukasiewicz L v y L ∞

Jan Łukasiewicz definió la implicación y la negación mediante las siguientes funciones:

Estas definiciones las utilizó inicialmente Łukasiewicz en 1920 para su lógica trivalente , con valores de verdad . En 1922 desarrolló una lógica con infinitos valores , en la que los valores de verdad abarcaban los números reales en el intervalo . En ambos casos el valor de verdad designado fue 1. [7]

Al adoptar valores de verdad definidos de la misma manera que para la lógica de Gödel , es posible crear una familia de lógicas de valores finitos , la mencionada anteriormente y la lógica , en la que los valores de verdad están dados por los números racionales en el intervalo . El conjunto de tautologías en y es idéntico.

Lógica del producto Π

En lógica de producto tenemos valores de verdad en el intervalo , una conjunción y una implicación , definidos de la siguiente manera [8]

Además, hay 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 adicional de la siguiente manera:

y luego .

Post lógicas P m

En 1921 Post definió una familia de lógicas con (como en y ) los valores de verdad . La negación , la conjunción y la disyunción se definen de la siguiente manera:

Lógicas 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 lógica clásica , esta propiedad es "verdad". En un argumento válido, la verdad de la proposición derivada está garantizada si las premisas son conjuntamente verdaderas, porque la aplicación de pasos válidos preserva la propiedad. Sin embargo, esa propiedad no tiene por qué ser la de "verdad"; en cambio, puede ser algún otro concepto.

Las lógicas de valores múltiples tienen como objetivo preservar la propiedad de la designación (o de ser designado). Dado que hay más de dos valores de verdad, las reglas de inferencia pueden tener como objetivo preservar más que el que corresponde (en el sentido relevante) a la verdad. Por ejemplo, en una lógica de tres valores, a veces se designan los dos valores de verdad más grandes (cuando se representan, por ejemplo, como números 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 tomadas en conjunto será siempre menor o igual a la conclusión.

Por ejemplo, la propiedad preservada podría ser la justificación , el concepto fundacional de la lógica intuicionista . Por tanto, una proposición no es verdadera ni falsa; más bien, está justificado o es defectuoso. 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 defectuosa no está necesariamente justificada; en cambio, simplemente no está demostrado que sea defectuoso. La diferencia clave es la determinación de la propiedad preservada: uno puede probar que P está justificado, que P es defectuoso o no poder probar ninguna de las dos cosas. Un argumento válido preserva la justificación a través de transformaciones, por lo que una proposición derivada de proposiciones justificadas todavía está justificada. Sin embargo, existen pruebas en lógica clásica que dependen de la ley del tercero excluido; dado que esa ley no es utilizable bajo este esquema, hay proposiciones que no pueden probarse de esa manera.

La tesis de Suszko.

Completitud funcional de lógicas multivaluadas.

La integridad funcional es un término utilizado para describir una propiedad especial de las lógicas y álgebras finitas. Se dice que un conjunto de conectivos de una lógica es funcionalmente completo o adecuado si y sólo si su conjunto de conectivos puede usarse para construir una fórmula correspondiente a cada función de verdad posible . [10] Un álgebra adecuada es aquella en la que cada mapeo finito de variables puede expresarse mediante alguna composición de sus operaciones. [11]

Lógica clásica: CL = ({0,1}, ¬ , →, ∨, ∧, ↔) es funcionalmente completa, mientras que ninguna lógica de Łukasiewicz o lógica de valores infinitos tiene esta propiedad. [11] [12]

Podemos definir una lógica de valores finitos 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 sea 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 lógica multivaluada para resolver problemas binarios de manera más eficiente. Por ejemplo, un enfoque bien conocido para representar una función booleana de salida múltiple es tratar su parte de salida como una única variable de muchos valores y convertirla en una función característica de salida única (específicamente, la función indicadora ). Otras aplicaciones de la lógica de muchos valores incluyen el diseño de matrices lógicas programables (PLA) con decodificadores de entrada, 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 multivalor, circuitos aritméticos y conjuntos de puertas programables en campo (FPGA). Los circuitos multivaluados tienen una serie de ventajas teóricas sobre los circuitos binarios estándar. Por ejemplo, la interconexión del chip dentro y fuera se puede reducir si las señales en el circuito asumen cuatro o más niveles en lugar de sólo dos. En el diseño de memoria, almacenar dos bits de información en lugar de uno por celda de memoria duplica la densidad de la memoria en el mismo tamaño de matriz . Las aplicaciones que utilizan circuitos aritméticos a menudo se benefician del uso de alternativas a los sistemas numéricos binarios. Por ejemplo, los sistemas numéricos residuales y redundantes [15] pueden reducir o eliminar los acarreos de propagación que están involucrados en la suma o resta binaria normal, lo que da como resultado operaciones aritméticas de alta velocidad. Estos sistemas numéricos tienen una implementación natural utilizando circuitos de muchos valores. Sin embargo, la viabilidad de estas ventajas potenciales depende en gran medida de la disponibilidad de realizaciones de circuitos, que deben ser compatibles o competitivos con las tecnologías estándar actuales. Además de ayudar en el diseño de circuitos electrónicos, la lógica multivalor 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 pruebas 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.

Lugares de investigación

Desde 1970 se celebra anualmente un Simposio Internacional IEEE sobre Lógica de Valores Múltiples (ISMVL). Se centra principalmente en aplicaciones de diseño y verificación digitales. [17] También hay un Journal of Multiple-Valued Logic and Soft Computing . [18]

Ver también

Lógica matemática
Lógica filosófica
Lógica digital

Referencias

  1. ^ Hurley, Patricio. Una introducción concisa a la lógica , novena edición. (2006).
  2. ^ Jules Vuillemin, Necesidad o contingencia , CSLI Lecture Notes, N°56, Stanford, 1996, págs. 133-167
  3. ^ (Gottwald 2005, pag.19)
  4. ^ Humberstone, Lloyd (2011). Los Conectivos . Cambridge, Massachusetts: Prensa del MIT. págs.201. ISBN 978-0-262-01654-4.
  5. ^ ab (Bergmann 2008, pag.80)
  6. ^ Godel, Kurt (1932). "Zum intuitionistischen Aussagenkalkül". Anzeiger der Akademie der Wissenschaften en Viena (69): 65 y siguientes.
  7. ^ Kreiser, Lothar; Gottwald, Sigfrido; Stelzner, Werner (1990). Nichtklassische Logik. Eine Einführung . Berlín: Akademie-Verlag. págs. 41 y 45 y siguientes. ISBN 978-3-05-000274-3.
  8. ^ Hajek, Petr: Lógica difusa . En: Edward N. Zalta: The Stanford Encyclopedia of Philosophy , primavera de 2009. ([1])
  9. ^ Rose, Alan (diciembre de 1951). "Sistemas de lógica cuyos valores de verdad forman celosías". Annalen Matemáticas . 123 : 152-165. doi :10.1007/BF02054946. S2CID  119735870.
  10. ^ Smith, Nicolás (2012). Lógica: Las leyes de la verdad . Prensa de la Universidad de Princeton. pag. 124.
  11. ^ ab Malinowski, Grzegorz (1993). Lógicas de muchos valores . Prensa de Clarendon. págs. 26 y 27.
  12. ^ Iglesia, Alonso (1996). Introducción a la Lógica Matemática. Prensa de la Universidad de Princeton. ISBN 978-0-691-02906-1.
  13. ^ Correo, Emil L. (1921). "Introducción a una Teoría General de Proposiciones Elementales". Revista Estadounidense de Matemáticas . 43 (3): 163–185. doi :10.2307/2370324. hdl : 2027/uiuo.ark:/13960/t9j450f7q . ISSN  0002-9327. JSTOR  2370324.
  14. ^ Dubrová, Elena (2002). Síntesis y optimización de lógica de valores múltiples, en Hassoun S. y Sasao T., editores, Logic Synthesis and Verification , Kluwer Academic Publishers, págs. 89-114
  15. ^ 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) . Transacciones IEEE sobre circuitos y sistemas I: artículos habituales . 56 (9) (publicado el 9 de septiembre de 2009): 1893–1907. doi :10.1109/TCSI.2009.2025803. S2CID  5465045. Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 3 de enero de 2016 .
  16. ^ Abramovici, Mirón; Breuer, Melvin A.; Friedman, Arthur D. (1994). Ensayos de Sistemas Digitales y Diseño Comprobable . Nueva York: Computer Science Press. pag. 183.ISBN 978-0-7803-1062-9.
  17. ^ "Simposio internacional IEEE sobre lógica de valores múltiples (ISMVL)". www.informatik.uni-trier.de/~ley .
  18. ^ "Inicio de MVLSC". Archivado desde el original el 15 de marzo de 2014 . Consultado el 12 de agosto de 2011 .

Otras lecturas

General

Específico

enlaces externos