Lógica de muchos valores

ImprimirCitar

Cálculo proposicional en el que hay más de dos valores de verdad

Lógica de muchos valores (también multi- o lógica de valores múltiples) se refiere a 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 clásica de dos valores puede extenderse a la lógica de nvalores para n mayor que 2. Los más populares en la literatura son los de tres valores. (por ejemplo, Łukasiewicz's y Kleene's, que aceptan los valores "verdadero", "falso" y "desconocido"), cuatro valuados, de nueve valores, los de valores finitos (de muchos valores finitos) con más de tres valores, y los de valores infinitos (de muchos valores infinitos), como la lógica difusa y la lógica de probabilidad.

Historia

Es equivocado que el primer lógico clásico conocido que no aceptó completamente la ley del tercero excluido fue Aristóteles (quien, irónicamente, también se considera generalmente como el primer lógico clásico y el &# 34;padre de la lógica [de dos valores]"). 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 a todos los eventos futuros (De Interpretatione, cap. IX), pero no creó un sistema de lógica multivaluada 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 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 polivalente 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. Posteriormente, Jan Łukasiewicz y Alfred Tarski formularon juntos una lógica sobre valores de verdad n donde n ≥ 2. En 1932, Hans Reichenbach formuló una lógica de muchos valores de verdad donde norte→∞. 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; tales lógicas se conocen como lógicas intermedias.

Ejemplos

Kleene (fuerte) K3 y lógica sacerdotal P3

La lógica de la indeterminación de Kleene $K 3$ (a veces $K_{3}^{S}$ ) y la "lógica de la paradoja" de Sacerdote añaden un tercer valor de verdad "indefinido" o "indeterminado" $I$ . La verdad funciona para la negación (¬), la conjunción (guardia), la disyunción (Ley), implicación (→K), y bicondicional (AdministraciónK) se dan por:

¬
$T$	$F$
$I$	$I$
$F$	$T$

∧	$T$	$I$	$F$
$T$	$T$	$I$	$F$
$I$	$I$	$I$	$F$
$F$	$F$	$F$	$F$

Alternativa	$T$	$I$	$F$
$T$	$T$	$T$	$T$
$I$	$T$	$I$	$I$
$F$	$T$	$I$	$F$

→K	$T$	$I$	$F$
$T$	$T$	$I$	$F$
$I$	$T$	$I$	$I$
$F$	$T$	$T$	$T$

AdministraciónK	$T$	$I$	$F$
$T$	$T$	$I$	$F$
$I$	$I$	$I$	$I$
$F$	$F$	$I$	$T$

La diferencia entre las dos lógicas radica en cómo se definen las tautologías. En $K 3$ solo $T$ es una verdad designada valor, mientras que en $P 3$ ambos $T$ y $I$ son (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 $Yo$ puede interpretarse como "indeterminado", siendo ni verdadero ni falso, mientras que en la lógica de Priest $I$ se puede interpretar como "sobredeterminado", siendo tanto verdadero como falso. $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.

La lógica interna de tres valores de Bochvar

Otra lógica es la lógica "interna" de Dmitry Bochvar. $B_{3}^{I}$ , también llamado la débil lógica trivalorada de Kleene. Excepto por la negación y la bicondición, sus tablas de verdad son diferentes de lo anterior.

∧+	$T$	$I$	$F$
$T$	$T$	$I$	$F$
$I$	$I$	$I$	$I$
$F$	$F$	$I$	$F$

Alternativa+	$T$	$I$	$F$
$T$	$T$	$I$	$T$
$I$	$I$	$I$	$I$
$F$	$T$	$I$	$F$

→+	$T$	$I$	$F$
$T$	$T$	$I$	$F$
$I$	$I$	$I$	$I$
$F$	$T$	$I$	$T$

El valor de verdad intermedio en el "interno" de Bochvar; la lógica se puede describir como "contagiosa" porque se propaga en una fórmula independientemente del valor de cualquier otra variable.

Lógica de Belnap (B4)

La lógica de Belnap $B 4$ combina $K 3$ y $P 3$ . El valor de verdad sobredeterminado se denota aquí como B y el valor de verdad subdeterminado como N.

$f \neg$
$T$	$F$
$B$	$B$
$N$	$N$
$F$	$T$

$f \land$	$T$	$B$	$N$	$F$
$T$	$T$	$B$	$N$	$F$
$B$	$B$	$B$	$F$	$F$
$N$	$N$	$F$	$N$	$F$
$F$	$F$	$F$	$F$	$F$

$f Alternativa$	$T$	$B$	$N$	$F$
$T$	$T$	$T$	$T$	$T$
$B$	$T$	$B$	$T$	$B$
$N$	$T$	$T$	$N$	$N$
$F$	$T$	$B$	$N$	$F$

Lógica Gödel Gk y G∞

En 1932 Gödel definió una familia $G_{k}$ de muchas lógicas valoradas, con valores finitos de verdad ${displaystyle 0,{tfrac {1}{k-1}},{tfrac {2}{k-1}},ldots{tfrac {k-2}{k-1}},1}$ , por ejemplo $G_{3}$ tiene los valores de la verdad ${displaystyle 0,{tfrac {1}{2}},1}$ y $G_{4}$ tiene ${displaystyle 0,{tfrac {1}{3}},{tfrac {2}{3}},1}$ . De manera similar definió una lógica con infinitamente muchos valores de verdad, $G_{infty }$ , en que los valores de la verdad son todos los números reales en el intervalo $[0,1]$ . El valor de verdad designado en estas lógicas es 1.

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

{displaystyle {begin{aligned}uwedge v&:=min{u,v}\uvee v&:=max{u,v}end{aligned}}}

Negación $neg _{G}$ e implicación $xrightarrow[G]{}$ se definen de la siguiente manera:

0end{cases}}\[3pt]umathrel {xrightarrow[{G}]{}} v&={begin{cases}1,&{text{if }}uleq v\v,&{text{if }}u>vend{cases}}end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">¬ ¬ Gu={}1,siu=00,siu■0u→Gv={}1,siu≤ ≤ vv,siu■v{displaystyle {begin{aligned}neg ################################################################################################################################################################################################################################################################ ¿Qué? v={begin{cases}1, limit{text{if }uleq vv, reducida{text{if }u {end{cases}}end{aligned}}}0end{cases}}\[3pt]umathrel {xrightarrow[{G}]{}} v&={begin{cases}1,&{text{if }}uleq v\v,&{text{if }}u>vend{cases}}end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d276c8d6a62bcba62243231f1ebf09984825b63d" style="vertical-align: -6.005ex; width:24.369ex; height:13.176ex;"/>

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 son demostrables. La implicación anterior es la implicación heyting única 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 heyting completa única en la red.

Lógica Lv y L∞ de Łukasiewicz

Implicación ${displaystyle {xrightarrow[{L}]{}}}$ y negación ${displaystyle {underset {L}{neg }}}$ fueron definidos por Jan Łukasiewicz a través de las siguientes funciones:

{displaystyle {begin{aligned}{underset {L}{neg }}u&:=1-u\umathrel {xrightarrow[{L}]{}} v&:=min{1,1-u+v}end{aligned}}}

Al principio Łukasiewicz utilizó estas definiciones en 1920 para su lógica de tres valores $L_{3}$ , con valores de verdad ${displaystyle 0,{frac {1}{2}},1}$ . En 1922 desarrolló una lógica con infinitos valores $L_{infty }$ , en que los valores de la verdad abarcaban los números reales en el intervalo $[0,1]$ . En ambos casos el valor de verdad designado era 1.

Adoptando valores de verdad definidos de la misma manera que para las lógicas de Gödel ${displaystyle 0,{tfrac {1}{v-1}},{tfrac {2}{v-1}},ldots{tfrac {v-2}{v-1}},1}$ , es posible crear una familia de lógicas de valor finito $L_{v}$ , el mencionado $L_{infty }$ y la lógica $L_{aleph _{0}}$ , en que los valores de la verdad son dados por los números racionales en el intervalo $[0,1]$ . El conjunto de tautologías en $L_{infty }$ y $L_{aleph _{0}}$ es idéntico.

Lógica del producto Π

En la lógica del producto tenemos valores de verdad en el intervalo $[0,1]$ , una conjunción $odot$ y una implicación ${displaystyle {xrightarrow[{Pi }]{}}}$ , definido como sigue

vend{cases}}end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">u⊙ ⊙ v:=uvu→▪ ▪ v:={}1,siu≤ ≤ vvu,siu■v{displaystyle {begin{aligned}uodot v. {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicroc {v}}}, {text{if}u}u}u}end{aligned}}vend{cases}}end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b78a241cc6af8f978b9fec3eb05a44d7d3a65b4" style="vertical-align: -4.005ex; width:25.536ex; height:9.176ex;"/>

Además hay un valor designado negativo ${overline {0}}$ que denota el concepto de falso. A través de este valor es posible definir una negación ${displaystyle {underset {Pi }{neg }}}$ y una conjunción adicional ${displaystyle {underset {Pi }{wedge }}}$ como sigue:

{displaystyle {begin{aligned}{underset {Pi }{neg }}u&:=umathrel {xrightarrow[{Pi }]{}} {overline {0}}\umathbin {underset {Pi }{wedge }} v&:=uodot left(umathrel {xrightarrow[{Pi }]{}} vright)end{aligned}}}

y luego ${displaystyle umathbin {underset {Pi }{wedge }} v=min{u,v}}$ .

Publicar lógica PM

En 1921 Post define una familia de lógicas $P_m$ con (como en $L_{v}$ y $G_{k}$ ) los valores de la verdad $0,{tfrac 1{m-1}},{tfrac 2{m-1}},ldots{tfrac {m-2}{m-1}},1$ . Negación ${displaystyle {underset {P}{neg }}}$ y conjunción ${displaystyle {underset {P}{wedge }}}$ y disyunciones ${displaystyle {underset {P}{vee }}}$ se definen de la siguiente manera:

{displaystyle {begin{aligned}{underset {P}{neg }}u&:={begin{cases}1,&{text{if }}u=0\u-{frac {1}{m-1}},&{text{if }}unot =0end{cases}}\umathbin {underset {P}{wedge }} v&:=min{u,v}\umathbin {underset {P}{vee }} v&:=max{u,v}end{aligned}}}

Lógica de rosas

En 1951, Alan Rose definió otra familia de lógicas para sistemas cuyos valores de verdad forman redes.

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 las 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 conserva 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 multivaluadas están destinadas a preservar la propiedad de designación (o ser designado). Dado que hay más de dos valores de verdad, las reglas de inferencia pueden estar destinadas a preservar más de lo 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 conservan estos valores. Precisamente, un argumento válido será tal que el valor de las premisas tomadas en conjunto será siempre menor o igual que la conclusión.

Por ejemplo, la propiedad preservada podría ser justificación, el concepto fundamental de la lógica intuicionista. Así, una proposición no es verdadera ni falsa; en cambio, está justificado o es defectuoso. Una diferencia clave entre la justificación y la 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, solo no se prueba 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 puede probar ninguna de las dos cosas. Un argumento válido conserva 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 demostraciones en lógica clásica que dependen de la ley del tercero excluido; como esa ley no es usable bajo este esquema, hay proposiciones que no pueden probarse de esa manera.

La tesis de Suszko

Integridad funcional de lógicas polivalentes

La completitud funcional es un término que se usa para describir una propiedad especial de la lógica finita y las álgebras. Se dice que el conjunto de conectivos de una lógica es funcionalmente completo o adecuado si y solo si su conjunto de conectivos se puede usar para construir una fórmula correspondiente a cada posible función de verdad. Un álgebra adecuada es aquella en la que cada aplicación finita de variables puede expresarse mediante alguna composición de sus operaciones.

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.

Podemos definir una lógica de muchos valores finitos como L_n ({1, 2,..., n} ƒ ₁,..., ƒ_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 m^th orden, existe alguna combinación correspondiente de conectivos en una lógica adecuada L_n que puede producir un modelo de orden m+1.

Aplicaciones

Las aplicaciones conocidas de la lógica de muchos valores se pueden clasificar aproximadamente en dos grupos. El primer grupo usa la lógica de muchos valores 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 de indicador). Otras aplicaciones de la lógica de muchos valores incluyen el diseño de arreglos lógicos programables (PLA) con decodificadores de entrada, optimización de máquinas de estados finitos, pruebas y verificación.

El segundo grupo tiene como objetivo el diseño de circuitos electrónicos que emplean más de dos niveles discretos de señales, como memorias de muchos valores, circuitos aritméticos y arreglos de puertas programables en campo (FPGA). Los circuitos de muchos valores tienen una serie de ventajas teóricas sobre los circuitos binarios estándar. Por ejemplo, el chip de encendido y apagado de la interconexión 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 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 dado. 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 de números residuales y redundantes 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 de muchos valores. Sin embargo, la practicidad 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 de muchos valores se usa 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) utilizados para la prueba de circuitos digitales requieren un simulador que pueda resolver la lógica de 5 valores (0, 1, x, D, D'). Los valores adicionales (x, D y D') representan (1) desconocido/sin inicializar, (2) un 0 en lugar de un 1 y (3) un 1 en lugar de un 0.

Lugares de investigación

Desde 1970 se lleva a cabo anualmente un simposio internacional de IEEE sobre lógica de valores múltiples (ISMVL). Su objetivo principal son las aplicaciones de diseño y verificación digital. También hay una Journal of Multiple-Valued Logic and Soft Computing.

Contenido relacionado

Más resultados...