stringtranslate.com

Lógica de múltiples valores

La lógica polivalente (también lógica multivaluada o lógica de múltiples valores ) es un cálculo proposicional en el que hay 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 bivaluada clásica 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"), las de cuatro valores , las de nueve valores , las de valor finito (de valor finito) con más de tres valores y las de valor infinito (de valor infinito), 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 tercio 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 tercio excluido, sino la universalidad del principio de bivalencia: admitió que este principio no se aplicaba en su totalidad a los eventos futuros ( De Interpretatione , cap. IX ), [2] pero no creó un sistema de lógica multivaluada para explicar esta observación aislada. Hasta la llegada del siglo XX, los lógicos posteriores siguieron la lógica aristotélica , que incluye o asume la ley del tercio excluido .

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 tratar 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 juntos formularon 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 muchos 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 3y la lógica sacerdotalPág. 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 bicondicional (K) vienen dadas por: [3]

La diferencia entre las dos lógicas radica en cómo se definen las tautologías . En K 3 sólo 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 I puede interpretarse como "subdeterminada", no siendo ni verdadera ni falsa, mientras que en la lógica de Priest I puede interpretarse como "sobredeterminada", siendo a la vez verdadera y falsa. K 3 no tiene ninguna tautología, mientras que P 3 tiene las mismas tautologías que la lógica clásica de dos valores. [4]

Lógica interna trivalente de Bochvar

Otra lógica es la lógica trivalente "interna" de Dmitry Bochvar , también llamada lógica trivalente débil de Kleene. A excepción de la negación y la bicondicionalidad, 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 (B4​)

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ógica de GödelG kyGRAMO∞

En 1932, Gödel definió [6] una familia de lógicas polivalentes, 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 un número infinito de 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 el 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 única implicación 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 única estructura de álgebra de Heyting completa en la red.

Lógica de ŁukasiewiczLv​yL ∞

La implicación y la negación fueron definidas por Jan Łukasiewicz a través de las siguientes funciones:

En un principio, Łukasiewicz utilizó estas definiciones 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 era 1. [7]

Al adoptar valores de verdad definidos de la misma manera que para las lógicas de Gödel , es posible crear una familia finita de lógicas , las mencionadas 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 productoP

En la lógica de productos tenemos valores de verdad en el intervalo , una conjunción y una implicación , definidas 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 adicional de la siguiente manera:

y luego .

Lógica de postesPm​

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

Lógica de la rosa

En 1951, Alan Rose definió otra familia de lógicas para sistemas cuyos valores de verdad forman redes . [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 verdaderas en conjunto, porque la aplicación de pasos válidos preserva la propiedad. Sin embargo, esa propiedad no tiene por qué ser la de la "verdad", sino que puede ser algún otro concepto.

Las lógicas multivaluadas tienen como objetivo preservar la propiedad de designación (o ser designado). Dado que hay más de dos valores de verdad, las reglas de inferencia pueden tener como objetivo preservar más que simplemente 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, números enteros positivos) y las reglas de inferencia preservan estos valores. Precisamente, un argumento válido será tal que el valor de las premisas tomadas en conjunto 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 . Por lo tanto, una proposición no es verdadera o falsa; en cambio, está justificada o es defectuosa. Una diferencia clave entre la justificación y la verdad, en este caso, es que la ley del tercio excluido no se cumple: una proposición que no es defectuosa no está necesariamente justificada; en cambio, solo no se prueba que sea defectuosa. La diferencia clave es la determinación de la propiedad preservada: uno puede probar que P está justificada, que P es defectuosa o ser incapaz de probar ninguna de las dos cosas. Un argumento válido preserva la justificación a través de las transformaciones, por lo que una proposición derivada de proposiciones justificadas sigue estando justificada. Sin embargo, hay pruebas en la lógica clásica que dependen de la ley del tercio excluido; dado que esa ley no es utilizable bajo este esquema, hay proposiciones que no se pueden probar de esa manera.

La tesis de Suszko

Completitud funcional de lógicas multivaluadas

La completitud funcional es un término utilizado 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 su conjunto de conectivas 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 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 o lógica de infinitos valores tiene esta propiedad. [11] [12]

Podemos definir una lógica de muchos 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 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 polivalente se pueden clasificar a grandes rasgos en dos grupos. [14] El primer grupo utiliza la lógica polivalente para resolver problemas binarios de forma 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 polivalente y convertirla en una función característica de salida única (específicamente, la función indicadora ). Otras aplicaciones de la lógica polivalente incluyen el diseño de matrices lógicas programables (PLA) con decodificadores de entrada, la optimización de máquinas de estados finitos , las pruebas y la 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 tienen varias ventajas teóricas sobre los circuitos binarios estándar. Por ejemplo, la interconexión dentro y fuera del chip se puede reducir si las señales en el circuito asumen cuatro o más niveles en lugar de solo dos. En el diseño de memorias, almacenar dos en lugar de un bit de información por celda de memoria duplica la densidad de la memoria en el mismo tamaño de chip . 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 ondulació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 multivaluados. Sin embargo, la viabilidad de estas ventajas potenciales depende en gran medida de la disponibilidad de realizaciones 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 polivalente se utiliza ampliamente para probar circuitos en busca de fallas y defectos. Básicamente, todos los algoritmos de generación automática de patrones de prueba (ATG) conocidos que se utilizan para probar circuitos digitales requieren un simulador que pueda resolver la lógica polivalente (0, 1, x, D, D'). [16] Los valores adicionales (x, D y D') representan (1) valores desconocidos/no inicializados, (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 en diseño y verificación digital. [17] También existe una Revista de Lógica de Valores Múltiples y Computación Suave . [18]

Véase también

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

Referencias

  1. ^ Hurley, Patrick. Una introducción concisa a la lógica , 9.ª edición. (2006).
  2. ^ Jules Vuillemin, Necesidad o contingencia , CSLI Lecture Notes, N°56, Stanford, 1996, pp. 133-167
  3. ^ (Gottwald 2005, pág. 19)
  4. ^ Humberstone, Lloyd (2011). Los conectores . Cambridge, Massachusetts: The MIT Press. pp. 201. ISBN. 978-0-262-01654-4.
  5. ^ ab (Bergmann 2008, pág. 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 retículos". Mathematische Annalen . 123 : 152–165. doi :10.1007/BF02054946. S2CID  119735870.
  10. ^ Smith, Nicholas (2012). Lógica: las leyes de la verdad . Princeton University Press. pág. 124.
  11. ^ ab Malinowski, Grzegorz (1993). Lógicas multivaluadas . Clarendon Press. págs. 26-27.
  12. ^ Church, Alonzo (1996). Introducción a la lógica matemática. Princeton University Press. ISBN 978-0-691-02906-1.
  13. ^ Post, 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. ^ Dubrova, Elena (2002). Síntesis y optimización de lógica de valores múltiples, en Hassoun S. y Sasao T., editores, Síntesis y verificación lógica , 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) . 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) desde el original el 9 de octubre de 2022 . Consultado el 3 de enero de 2016 .
  16. ^ 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.
  17. ^ "Simposio internacional IEEE sobre lógica de valores múltiples (ISMVL)". www.informatik.uni-trier.de/~ley .
  18. ^ "MVLSC home". Archivado desde el original el 15 de marzo de 2014. Consultado el 12 de agosto de 2011 .

Lectura adicional

General

Específico

Enlaces externos