Lógica multivaluada

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 20 de febrero de 2021; las comprobaciones requieren 19 ediciones .

La lógica multivaluada es la lógica en la que las expresiones lógicas pueden tomar valores de un conjunto que contiene más de dos elementos. Sin embargo, algunos de estos valores se consideran ciertos . En estas propiedades, la lógica multivaluada difiere de la lógica clásica de Aristóteles , en la que las expresiones lógicas pueden tomar solo uno de dos valores posibles: "verdadero" o "falso". Sin embargo, la lógica clásica de dos valores se puede extender a la lógica de n valores con n > 2. Las más populares en la literatura son la lógica de tres valores (por ejemplo, la lógica de Jan Lukasiewicz y Stephen Kleene , que toma los valores "verdadero", "falso" y "desconocido"), lógica de valores finitos (puede tener más de tres valores) y de valores infinitos (esto incluye la lógica probabilística con una escala continua de valores de verdad de 0 a 1, así como lógica difusa ).

Historia

El primer científico conocido que no aceptó completamente la ley del tercero excluido y no se basó en ella fue Aristóteles (quien, irónicamente, ha sido reconocido como "el padre de la lógica clásica"). Aristóteles reconoció el hecho de que sus leyes no siempre podían aplicarse a eventos futuros, pero no generalizó la lógica de dos valores al caso n-dimensional para eliminar imprecisiones.

Hasta finales del siglo XIX, los matemáticos siguieron las leyes de la lógica aristotélica , que se basaba en la ley del medio excluido . Sin embargo, en el siglo XX, comenzó a crecer el interés por la lógica polivalente. Entonces, por ejemplo, el matemático y filósofo polaco Jan Lukasiewicz comenzó a desarrollar el primer sistema de lógica multivaluada utilizando un tercer significado: "neutral" para superar la paradoja de una batalla naval formulada por Aristóteles . Mientras tanto, el matemático estadounidense Emil Post presentó un artículo que describía la posibilidad de introducir valores de verdad adicionales para . Un poco más tarde, Lukasiewicz, en colaboración con Alfred Tarski , pudo repetir el éxito de Post al formular los principios básicos de la lógica con valores n para . En 1932, Hans Reichenbach resumió estos principios con . $n>2$ $n>2$ ${\ estilo de visualización n \ flecha derecha \ infinito}$

En 1932, Kurt Gödel demostró que el cálculo intuicionista no es de dimensión finita e introdujo su propio sistema (Gödel calculus, ing. Gödel logic ) como nexo intermedio entre la lógica clásica y la intuicionista. El cálculo de Gödel más tarde se conoció como lógica "intermedia" (ing. lógica intermedia ).

Información básica

Artículos principales: Lógica de tres valores , Lógica de cuatro valores , Lógica de nueve valores

Para describir lógicas proposicionales polivalentes se utilizan las denominadas matrices lógicas [1] [2] , es decir, sistemas algebraicos de la forma , donde está el universo, son símbolos funcionales, es un símbolo de predicado de un solo lugar. Los elementos del universo corresponden a valores lógicos, y los símbolos funcionales corresponden a conectivos lógicos (operaciones), por lo que los términos característicos son fórmulas lógicas. Si la fórmula lógica es tal que , entonces se llama una tautología válida o de la matriz lógica dada, mientras que el predicado define un subconjunto de valores lógicos que se tratan como verdaderos. Así, se construyen representaciones matriciales de lógicas proposicionales: conjuntos de tautologías en un lenguaje que consta de nombres de variables y conectivos. ${\mathfrak {M}}=(V,f_{1},f_{2},...,f_{l},{\mathcal {D}})$ $V$ ${\ estilo de visualización f_{1},f_{2},...,f_{l))$ $\mathcal{D}$ ${\displaystyle\sigma ({\mathfrak{M}})}$ $A(x_{1},x_{2},...,x_{k})$ ${\mathfrak {M}}\modelos \forall {x_{1}}\forall {x_{2}}{..}\forall {x_{k}}{\mathcal {D}}(A( x_{1},x_{2},...,x_{k}))$ $\mathcal{D}$

Cualquier función , incluida la expresada por una fórmula lógica multivaluada, donde , puede representarse como una forma normal disyuntiva perfecta (PDNF) de lógica multivaluada, de la siguiente manera [2] : $f:E_{n+1}^{k}\rightarrow E_{n+1}$ ${\displaystyle E_{n+1}=\{0,1,2,...,n\))$

f(x_{1},x_{2},..,x_{k})=\bigvee_{(a_{1},a_{2},..,a_{k})\en E_ {n+1}^{k}}f(a_{1},a_{2},..,a_{k})\cuña \left(\bigcuña _{m=1,..,k}J_{ a_{m}}(x_{m})\derecha)

donde está la operación de conjunción : ${\ estilo de visualización \ cuña}$

x\cuña y=min(x,y),

el símbolo representa la operación de disyunción : $\vee$

x\vee y=max(x,y),

y los operadores de Rosser-Turquette: ${\ estilo de visualización J_ {i} (x)}$

J_{i}(x)={\begin{casos}n,&x=i,\\0,&x\neq i.\end{casos))

K 3 Lógica Kleene y P 3 Lógica sacerdotal

La lógica de la indeterminación de Kleene (a veces denominada ) y la "lógica de la paradoja" de Priest introducen un tercer significado "indefinido" o "intermedio" de I. Tablas de verdad para negación (¬), conjunción (˄), disyunción ( ˅), implicación (→) y equivalentes (↔), se ven así: $K_{3}$ ${\displaystyle K_{3}^{S))$

¬
T	F
yo	yo
F	T

∧	T	yo	F
T	T	yo	F
yo	yo	yo	F
F	F	F	F

∨	T	yo	F
T	T	T	T
yo	T	yo	yo
F	T	yo	F

→k	T	yo	F
T	T	yo	F
yo	T	yo	yo
F	T	T	T

↔k	T	yo	F
T	T	yo	F
yo	yo	yo	yo
F	F	yo	T

La diferencia entre las dos lógicas radica en la diferente definición de la tautología del álgebra de proposiciones (La tautología es una proposición idénticamente verdadera que es invariante con respecto a los valores de sus componentes). En B , solo T se define como verdadera, mientras que tanto T como I se definen como verdaderas. En la lógica de Kleene, I es una cantidad "indeterminada" que no es "verdadera" o "falsa"; en la lógica de Priest, I es una cantidad "redefinida" que es tanto "verdadera" como "falsa". no contiene tautologías, pero contiene las mismas tautologías que la lógica clásica de dos valores. $K_{3}$ $P_{3}$ $K_{3}$ $P_{3}$

La lógica interna de tres valores de Bochvar

Otro ejemplo es la lógica de tres valores “interna” de Bochvar , obtenida en 1938 por Dmitry Anatolyevich Bochvar. También se llama lógica débil de Kleene de tres valores. Las tablas de verdad para la negación y la equivalencia siguen siendo las mismas, pero para las otras tres operaciones toman la forma: $B_{3}^{yo}$

∧+	T	yo	F
T	T	yo	F
yo	yo	yo	yo
F	F	yo	F

∨+	T	yo	F
T	T	yo	T
yo	yo	yo	yo
F	T	yo	F

→+	T	yo	F
T	T	yo	F
yo	yo	yo	yo
F	T	yo	T

En la lógica interna de Bochvar, I puede ser descrito como "independiente" porque su valor no depende de los valores de T y F.

La lógica de Belnap B 4

La lógica propuesta por Nuel Belnap combina y . Un valor "sobredeterminado" se denota con B y un valor "infradeterminado" con N. $K_{3}$ $P_{3}$

f ¬
T	F
B	B
norte	norte
F	T

f ∧	T	B	norte	F
T	T	B	norte	F
B	B	B	F	F
norte	norte	F	norte	F
F	F	F	F	F

f ∨	T	B	norte	F
T	T	T	T	T
B	T	B	T	B
norte	T	T	norte	norte
F	T	B	norte	F

Lógica de Gödel G k y G ∞

En 1932, Gödel definió una familia de lógicas multivaluadas con un conjunto finito de valores: $G k}$ $0,{\frac {1}{k-1)),{\frac {2}{k-1)),...,{\frac {k-2}{k-1)), una$

Por ejemplo, para los valores serán $G_{3}$ $0,{\frac{1}{2)),1$

Para el valor tomará la forma: ${\ Displaystyle G_ {4}}$ $0,{\frac{1}{3)),{\frac{2}{3)),1$

De manera similar, Gödel definió la lógica con un número infinito de valores . Todos los valores en son números reales pertenecientes al intervalo [0, 1]. La verdad en esta lógica es 1. ${\displaystyle G_{\infty ))$ ${\displaystyle G_{\infty ))$

La conjunción (˄) y la disyunción (˅) se definen como el valor mínimo/máximo de las siguientes expresiones:

{\begin{alineado}u\cuña v&:=\min\{u,v\}\\u\vee v&:=\max\{u,v\}\end{alineado))

La negación (¬) y la implicación (→) se definen de la siguiente manera:

{\begin{alineado}\neg_{G}u&={\begin{casos}1,&{\text{si}}u=0\\0,&{\text{si}}u> 0\end{casos}}\\u{\xrightarrow[{G}]{}}v&={\begin{casos}1,&{\text{if }}u\leq v\\v,&{\ texto{si}}u>v\end{casos}}\end{alineado}}

La lógica de Gödel es completamente axiomatizable, por lo que es posible definir un cálculo lógico en el que se pueden demostrar todas las tautologías.

La lógica de Lukasiewicz L v y L ∞

Implicación (→) y negación (¬) fueron definidas por Łukasiewicz con las siguientes funciones:

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

Lukasiewicz utilizó por primera vez estas definiciones en 1920 al describir la lógica con valores . $L_{3}$ $0,{\frac{1}{2)),1$

En 1922, describió una lógica de valores infinitos , todos cuyos valores estaban en el intervalo [0, 1] y eran números reales . En ambos casos, 1 era cierto. $L_{{\infty ))$

Describiendo valores de una manera similar a Gödel, a saber: uno puede crear una familia de lógicas de valores finitos , así como lógica , en la que los valores también están representados por números racionales y se encuentran en el intervalo [0, 1 ]. Muchas tautologías en y son idénticas. $0,{\frac {1}{v-1)),{\frac {2}{v-1)),...,{\frac {v-2}{v-1)), una$ $L_{v}$ ${\ estilo de visualización L_ {N_ {0}}}$ $L_{{\infty ))$ ${\ estilo de visualización L_ {N_ {0}}}$

La lógica resultante Π

En la lógica resultante, tenemos valores pertenecientes al intervalo [0,1], para los cuales la conjunción (ʘ) y la implicación (→) se definen de la siguiente manera:

{\begin{aligned}u\odot v&:=uv\\u{\xrightarrow[{\Pi }]{}}v&:={\begin{cases}1,&{\text{if }} u\leq v\\{\frac {v}{u}},&{\text{if }}u>v\end{casos}}\end{alineados}}

Un valor falso en esta lógica es 0. A través de él, es posible definir las operaciones de negación (¬) y conjunción por adición (˄):

{\begin{alineado}{\underset {\Pi }{\neg }}u&:=u{\xrightarrow[{\Pi }]{}}{\overline {0}}\\u{\underset {\Pi }{\cuña }}v&:=u\odot (u{\xrightarrow[{\Pi }]{}}v)\end{alineado}}

Lógica de post P m

En 1921 Post definió una familia de lógicas con significados: ${\ Displaystyle P_ {m}}$

$0,{\frac {1}{m-1)),{\frac {2}{m-1)),...,{\frac {m-2}{m-1)), una$ . (similar a las lógicas y ). La negación (¬), la conjunción (˄) y la disyunción (˅) se definen de la siguiente manera: $L_{v}$ $G k}$

{\begin{alineado}{\underset {P}{\neg }}u&:={\begin{cases}1,&{\text{if }}u=0\\u-{\frac { 1}{m-1)),&{\text{if }}u\not =0\end{cases}}\\u{\underset {P}{\wedge }}v&:=\min\{u ,v\}\\u{\underset {P}{\vee }}v&:=\max\{u,v\}\end{alineado}}

La lógica de Rose

En 1951, Alan Rose describió una familia de lógicas para sistemas cuyos valores forman redes .

Semántica

Semántica matricial (matrices lógicas)

Conexión con la lógica clásica

La lógica es un sistema con un conjunto de reglas diseñadas para preservar las propiedades de las oraciones bajo varias transformaciones. En lógica clásica, esta propiedad es "verdadera".

La lógica multivaluada está diseñada para preservar la propiedad de notación. Dado que hay más de dos valores "verdaderos", se pueden aplicar reglas de inferencia para almacenar datos adicionales que pueden no ser ciertos. Por ejemplo, la lógica de tres valores puede tener dos valores correspondientes a "verdadero" de diferentes gradaciones (por ejemplo, pueden ser números enteros positivos), y las reglas de inferencia conservan estos valores.

Por ejemplo, una propiedad almacenada podría ser una confirmación, desempeñando un papel importante en la lógica intuicionista . No consideramos su verdad o falsedad; en cambio, trabajamos con conceptos como exposición y falibilidad.

La diferencia clave entre confirmación y verdad es que la ley del tercero excluido no se cumple en este caso: una declaración que no es falsa no necesariamente será confirmada; en cambio, solo se ha probado que no es erróneo. La diferencia clave es la certeza de la propiedad retenida: se puede demostrar que P está validada, que P es incorrecta o que no lo es. Un argumento válido conserva su validez bajo transformaciones, por lo que una declaración derivada de afirmaciones válidas sigue siendo válida. Sin embargo, hay demostraciones en lógica clásica que dependen directamente de la ley del tercero excluido; dado que esta ley no se aplica en el marco de este régimen, hay afirmaciones que no pueden probarse de esta manera.

La tesis de Sushko

Artículo principal: Principio de bivalencia

El siglo XX estuvo marcado por el rápido desarrollo de los sistemas de lógica polivalente, que en la actualidad están representados por una gran cantidad de estudios y artículos. Sin embargo, a medida que aumentó el número de sistemas formales diferentes, surgió la pregunta sobre la interpretación de los resultados obtenidos. Los científicos se han dado cuenta agudamente de la necesidad de reducir (reducir) las lógicas de muchos valores a una sola base.

La lógica clásica ordinaria puede servir como una de las variantes de tal base. El representante más destacado de este enfoque es el lógico polaco Roman Sushko , quien propuso su algoritmo para reducir cualquier lógica de valores múltiples a la lógica clásica de dos valores y formuló el principio, que más tarde se conoció como "tesis de Sushko". De acuerdo con este principio, para cualquier lógica multivaluada, se puede obtener una semántica bivalente que describa esta lógica.

Completitud funcional de la lógica polivalente

La completitud funcional es un término utilizado para describir propiedades especiales de álgebras y lógicas finitas.

Un conjunto lógico es funcionalmente completo si y solo si el conjunto de operaciones de este conjunto puede usarse para describir una fórmula correspondiente a todas las posibles funciones de verdad .

Un álgebra funcionalmente completa es un álgebra en la que cada aplicación finita se puede expresar en términos de una composición de las operaciones introducidas en ella.

Lógica clásica: es funcionalmente completa, mientras que la lógica de Lukasiewicz o lógica de valores infinitos no tiene esta propiedad. $CL=(\{0,1\}\ \neg \ \rightarrow \land \ \lor \longleftrightarrow)$

Podemos definir la lógica de valores finitos de la siguiente manera: , donde y n pertenece al conjunto de los números naturales. Emil Post en 1921 demostró que si la lógica es capaz de producir una función de orden m-ésimo, entonces hay una combinación de operadores que producirá una función de orden m+1. $L_{n}(\{1,2,...,n\},\f_{1},...,f_{m})$ ${\ estilo de visualización n \ geq 2}$ $L_{n}$

Lógicas de valores infinitos

La lógica de valores infinitos se puede introducir así:

el valor de verdad está en el segmento de los números reales del 0 al 1;
la negación se define como: ¬A = 1−A;
la conjunción se define como: A∧B = min(A, B);
la disyunción se define como: A∨B = max(A, B).

Los sistemas de funciones R de VL Rvachev [3] se pueden clasificar como sistemas formales de lógica de valores infinitos .

Teoría de la probabilidad y lógica polivalente

Puede parecer que la teoría de la probabilidad es muy similar a la lógica de valores infinitos: la probabilidad corresponde a un valor de verdad (1=verdadero, 0=falso), la probabilidad de que no ocurra ningún evento corresponde a la negación, la probabilidad de que ocurra dos eventos simultáneamente corresponde a una conjunción, y la probabilidad de al menos uno de dos eventos corresponde a una disyunción.

Sin embargo, existe una diferencia fundamental entre la lógica multivaluada y la teoría de la probabilidad: en la lógica, el valor de verdad de cualquier función está totalmente determinado por el valor de verdad de sus argumentos, mientras que en la teoría de la probabilidad la probabilidad de un evento compuesto depende no solo de las probabilidades de los eventos que lo componen, sino también de su dependencia entre sí (que se expresa en términos de sus probabilidades condicionales ).

Esto se manifiesta, en particular, en el hecho de que en la teoría de la probabilidad se cumple el equivalente a la “ley del tercero excluido”: la probabilidad de que un evento ocurra o no ocurra es siempre igual a uno, mientras que en la lógica polivalente la ley del tercero excluido no se cumple.

En la teoría de la probabilidad, también se cumple el equivalente de la " ley de la contradicción ": la probabilidad de que algún evento ocurra y no ocurra al mismo tiempo es siempre 0, mientras que en la lógica polivalente la ley de la contradicción no se cumple.

Al mismo tiempo, existe cierta conexión entre los valores de verdad de la lógica de valores infinitos anterior y las probabilidades de la teoría de la probabilidad, a saber:

si a es la probabilidad de algún evento, entonces la probabilidad de que ese evento no ocurra es 1 − a ;
si a y b son las probabilidades de algunos dos eventos, entonces la probabilidad de la ocurrencia conjunta de estos dos eventos no excede min( a , b );
si a y b son las probabilidades de algunos dos eventos, entonces la probabilidad de que ocurra al menos uno de estos dos eventos es mayor o igual a max( a , b ).

Aplicaciones

Las aplicaciones de la lógica de muchos valores se pueden dividir aproximadamente en dos grupos.

El primer grupo usa lógica multivaluada para resolver de manera efectiva el problema de una representación binaria de alguna entidad. Por ejemplo, representar una función booleana con múltiples salidas es tratar su salida como una sola variable que depende de múltiples argumentos. Se llevan a cabo más transformaciones con él: se transforma en una función característica con una salida (en particular, una función de indicador ).

Otras aplicaciones de la lógica multivaluada incluyen el diseño de lógicos programables (PLA), optimización de máquinas de estado, pruebas y validación.

El segundo grupo está dirigido a la creación y diseño de circuitos electrónicos utilizando más de dos niveles discretos. Estos incluyen: memoria multivalor, unidades lógicas aritméticas y matrices de puertas programables en campo (FPGA). Los esquemas multivaluados tienen varias ventajas teóricas serias sobre los esquemas binarios estándar. Entonces, por ejemplo, la interconexión en el chip y fuera del chip puede ser más pequeña si las señales en el circuito pueden manejar cuatro niveles en lugar de solo dos. En el diseño de la memoria, el almacenamiento de dos bits de información en lugar de uno por celda de memoria duplica la densidad de la memoria y mantiene el mismo tamaño del chip.

Las aplicaciones de software que usan unidades lógicas aritméticas a menudo se benefician del uso de alternativas a los sistemas numéricos binarios. Entonces, por ejemplo, los sistemas numéricos residuales y redundantes (ing. representación binaria redundante ) pueden reducir o eliminar a través de transferencias (ing. ripple-carry ), que tienen lugar en la suma o resta binaria ordinaria, lo que conduce a operaciones aritméticas de alta velocidad. Dichos sistemas numéricos tienen una implementación natural utilizando esquemas multivaluados.

Sin embargo, la practicidad de estas posibles ventajas teóricas depende en gran medida de la disponibilidad de implementaciones especiales que deben ser compatibles y competitivas con las tecnologías estándar actuales. Además de su uso en el diseño de circuitos electrónicos, la lógica multivaluada se usa ampliamente para probar circuitos en busca de fallas y defectos. Casi todos los algoritmos conocidos de generación automática de secuencias de prueba (ATG) utilizados para probar circuitos digitales requieren un simulador que pueda manejar una lógica de 5 valores (0, 1, x, D, D'). Los valores adicionales -x, D y D'- representan desconocido/no inicializado (valor x), 0 en lugar de 1 (valor D) y 1 en lugar de 0 (valor D').

Computador de lógica ternaria

La computadora ternaria "Setun" fue creada y puesta en funcionamiento en la Facultad de Mecánica y Matemáticas de la Universidad Estatal de Moscú en 1958.

A diferencia del enfoque clásico utilizado en las computadoras modernas, Setun utilizó un código ternario con los números −1, 0, 1. Este enfoque tiene una serie de ventajas al realizar operaciones aritméticas y representar un número en la memoria de la máquina: no hay necesidad de códigos imperfectos. códigos de números adicionales, directos o inversos, el redondeo se realiza simplemente cortando los dígitos menos significativos, las operaciones de cambio son únicas, el código de números es uniforme.

Sitios de investigación

El Simposio Internacional sobre Problemas y Cuestiones que Surgen de la Investigación en Aplicaciones de la Lógica Multivaluada (ISMVL) se lleva a cabo anualmente desde 1970. Las principales áreas de trabajo del simposio son el mantenimiento de diversas aplicaciones digitales y problemas de verificación.

Además, hay una revista dedicada a la lógica multivaluada y sus aplicaciones en el ámbito digital.

Notas

↑ Karpenko A. S. Lukasiewicz lógica y números primos. Moscú: Nauka, 2000.
↑ 1 2 Kovalev S.P., "Fundamentos matemáticos de la aritmética informática", Matem. tr., 8:1 (2005), 3-42; Siberiano Adv. Matemáticas, 15:4 (2005), 34-70. Consultado: 19/06/2021
↑ Rvachev V. L. Teoría de las funciones R y algunas de sus aplicaciones. - Kyiv: Nauk. pensamiento 1982.

Enlaces

Literatura

Yablonsky SV Introducción a las matemáticas discretas. 2ª ed. M.: Nauka, 1986. 384 págs. (enlace caído) (enlace caído desde el 13/05/2013 [3454 días]) Capítulo 2.
Lógicas polivalentes y sus aplicaciones: Cálculo lógico, álgebras y propiedades funcionales. ed. Finna V.K. Volumen 1. M.: URSS, 2008. 416 p.
Lógicas multivalor y sus aplicaciones: Lógica en sistemas de inteligencia artificial. ed. Finna V.K. Volumen 2. M.: URSS, 2008. 240 p.
Karpenko A. S. Lógicas multivaluadas. Lógica y computación. Tema. 4. M.: Nauka, 1997. 223 p.
Karpenko A. S. Lukasiewicz lógica y números primos. M.: Nauka, 2000. 319s.
Kondakov N. I. Diccionario lógico / Gorsky D. P. - M . : Nauka, 1971. - 656 p.
Artículos sobre lógicas multivaluadas en arxiv.org
Levin VI Lógica de valores infinitos en problemas de cibernética. Moscú: Radio y comunicación, 1982. 176 p.
Rescher, N. "Lógica de muchos valores", Mc. Graw-Hill, Nueva York, 1969.
Rosser, JB, Turquette, AR "Lógicas de muchos valores", Holanda Septentrional, Ámsterdam, 1952.

Lógicas

Filosofía • Semántica • Sintaxis • Historia

Grupos lógicos

lógica clásica	lógica aristotélica Lógica proposicional Lógica de primer orden Lógica de segundo orden lógica de orden superior
lógica matemática	teoría de conjuntos Teoría del modelo teoría de la computabilidad Teoría de la prueba y matemáticas constructivas lógica lineal sistema formal conclusión natural cálculo de secuencias Álgebra de la lógica Lógica relevante lógica deóntica lógica intuicionista cálculo de Lambek
Lógica no clásica	intuicionismo lógica difusa Lógica subestructural lógica Descripción lógica Lógica multivaluada Síntesis lógica Lógica vinculante Lógica temporal Lógica modal ( Lógica híbrida ) lógica epistémica
lógica filosófica	Pensamiento crítico lógica informal razonamiento deductivo

Componentes

Lista de símbolos booleanos