Resumen
Como lo que sigue es bastante largo, pensé en añadir este resumen.
Teniendo en cuenta lo siguiente:
- Un enunciado en lógica de proposiciones puede convertirse en una expresión aritmética sobre los enteros módulo 2 y viceversa.
- Una expresión aritmética puede simplificarse (sin cambiar su efecto).
- Estos dos hechos pueden utilizarse para simplificar un enunciado en la lógica de la proposición.
- Una declaración que se simplifica a $1$ o 'verdadero' es una tautología.
La pregunta: ¿es posible aplicar estas ideas también a la lógica de predicados? ¿Cómo? O, ¿por qué no?
Pregunta original
Descargo de responsabilidad: no soy matemático, así que posiblemente los siguientes conceptos sean erróneos o aburridos. También esto puede ser largo.
Representación de la lógica proposicional como aritmética
He pasado algún tiempo mirando cómo representar declaraciones lógicas como expresión aritmética módulo 2, con $0$ que representa "falso" y $1$ que representa "verdadero". Para la lógica de las proposiciones, esto no es tan difícil. Por ejemplo:
$$ a \wedge b \Rightarrow a \times b \text{ (mod 2)} \\ a \vee b \Rightarrow a + b + ab \text{ (mod 2)} \\ \neg a \Rightarrow a + 1 \text{ (mod 2)} \\ a \rightarrow b \Rightarrow 1 + a + ab \text{ (mod 2)} $$
Ejemplos
Utilizando estas reglas, cualquier afirmación de la lógica de proposiciones puede representarse como una expresión aritmética. Por ejemplo,
$$ a \vee b \rightarrow \neg ( \neg a \wedge \neg b ) \tag{1} $$
se convierte a través de
$$ a \vee b \rightarrow \neg ( \neg a \wedge \neg b ) \\ 1 + (a \vee b) + (a \vee b)(\neg ( \neg a \wedge \neg b )) \\ 1 + (a + b + ab) + (a + b + ab)(\neg ( \neg a \wedge \neg b )) \\ 1 + (a + b + ab) + (a + b + ab)(( \neg a \wedge \neg b ) + 1) \\ 1 + (a + b + ab) + (a + b + ab)(( (\neg a)(\neg b)) + 1) \\ 1 + (a + b + ab) + (a + b + ab)(( (a + 1)(b + 1)) + 1) \\ $$
Bajo el módulo 2 esto se reduce a $1$ o "verdadero", lo que indica que el enunciado lógico original es una tautología, lo que es efectivamente el caso. Otro ejemplo, $a \rightarrow (a \wedge b)$ se reduce a $1 + a + ab$ o $a \rightarrow b$ , lo que también es correcto.
Representación de la lógica de predicados como aritmética
Como se ha demostrado, estas reglas pueden utilizarse para simplificar los enunciados lógico-propositivos y para comprobar las tautologías. Ahora estoy tratando de extender a la lógica de predicados. Encontrar operadores aritméticos coincidentes para los cuantificadores no es muy difícil: (supongamos $x$ como abreviatura de $x \in X$ con $X$ algún conjunto)
$$ \forall x, P x \Rightarrow \prod_x P x \\ \exists x, P x \Rightarrow ( \prod_x P x + 1 ) + 1 $$
Alternativas que utilizan sumas en lugar de productos:
$$ \forall x, P x \Rightarrow 2^{\sum_{x} P x + 1} \\ \exists x, P x \Rightarrow 2^{\sum_{x} P x} + 1 $$
Tenga en cuenta que estas alternativas sólo funcionan si $\forall x, Px \in \{0,1\}$ , lo que supone una desviación de las reglas para la proposición, que funcionan independientemente (sólo importa la paridad de los enunciados atómicos). Debido a esto no estoy seguro de que estas ecuaciones que utilizan sumas sean las mejores soluciones, por lo que he estado utilizando las que utilizan productos.
Ejemplos
Podemos utilizar estas reglas para representar un enunciado en lógica de predicados en forma aritmética. Por ejemplo:
$$ (\exists x, P x) \rightarrow \neg (\forall x, \neg P x) $$
Este es el predicado equivalente al enunciado proposicional 1 . También es una tautología. Escribirlo como aritmética usando las reglas dadas da como resultado:
$$ (\exists x, P x) \rightarrow \neg (\forall x, \neg P x) \\ 1 + (\exists x, P x) + (\exists x, P x)(\neg (\forall x, \neg P x)) \\ 1 + ((\prod_x \neg P x) + 1) + ((\prod_x \neg P x) + 1) ((\prod_x \neg P x) + 1) \\ 1 + ((\prod_x P x + 1) + 1) + ((\prod_x P x + 1) + 1) ((\prod_x P x + 1) + 1) \\ $$
De nuevo, esto se reduce a $1$ bajo el módulo 2, aunque este es un ejemplo trivial porque definimos las versiones aritméticas de $\exists x, P x$ y $\neg (\forall x, \neg P x)$ para ser iguales. Un caso más complejo:
$$ (\forall x, P x \rightarrow Q x) \wedge (\exists x, P x) \rightarrow (\exists x, Q x) \tag{2} $$
Los rendimientos de la conversión:
$$ 1 + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1) + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1)((\prod_x Q x + 1) + 1) \tag{3} $$
Aquí es donde me quedo atascado y donde radica mi pregunta. No he encontrado una manera de reducir esto a $1$ como debe ser. Ya lo he hecho, véase la actualización más abajo.
Reducción de productos multiplicados
Encontré lo siguiente:
$$ (\prod_{x \in X} P x)(\prod_{x \in X} Q x) = \sqrt{ \prod_{x \in X} \prod_{y \in X} P x Q y } \tag{4} $$
De manera más general:
$$ \underbrace{(\prod_{x \in X} P x)(\prod_{x \in X} Q x) \ldots (\prod_{x \in X} R x)}_{n\text{ products over }n\text{ predicates}} = \sqrt[2^{n-1}]{ \underbrace{ \prod_{x \in X} \prod_{y \in X} \ldots \prod_{z \in X} }_{n\text{ products}} \underbrace{ P x Q y \ldots R z }_{n\text{ predicates}} } $$
(es decir, el $2^{n-1}$ raíz) Dado que la reducción adicional de la expresión 3 resultados en muchos productos multiplicados, pensé que esto sería útil. Sin embargo, todavía no me ha servido de nada, sobre todo porque las diferentes variables introducidas ( $x$ , $y$ , $z$ ...), aunque iteren sobre el mismo conjunto, no pueden intercambiarse (es decir, $PxPy \ne (Px)^2$ que ayudaría mucho a reducir la expresión). Véase la actualización más abajo para conocer nuevas ideas al respecto.
La pregunta
Aquí es donde estoy hasta ahora. Mi pregunta es: ¿cómo puedo representar cualquier enunciado de la lógica de predicados como aritmética, al igual que puedo hacer con cualquier enunciado de la lógica de proposiciones, de manera que pueda reducirlos y encontrar tautologías? (en particular el enunciado 2 , actualización: hecho esto, ver abajo para continuar con las preguntas ) ¿Es esto posible? Si no, ¿por qué? ¿Algunas de mis suposiciones o conclusiones anteriores son en realidad erróneas? Se agradece cualquier comentario.
Además, ¿es posible esta representación/reducción a la aritmética para toda la lógica de orden superior? ¿Por qué (no)?
¡Gracias por adelantado!
Actualización: Revisión de los productos multiplicados
He estado trabajando en esto un poco más y me he dado cuenta de dos cosas, la segunda de las cuales me ha permitido hacer algunos progresos.
Raíz de los productos
En primer lugar, me di cuenta de que para $a \in \{0,1\}$ :
$$ \sqrt{a} = a \text{ (mod 2)} $$
Esto significa que el enunciado de la ecuación 4 puede simplificarse aún más:
$$ \prod_{x \in X} \prod_{y \in X} P x Q y $$
Productos multiplicados simplificados
Esto me llevó a darme cuenta de que, de hecho, la siguiente simplificación es posible:
$$ (\prod_{x \in X} P x)(\prod_{x \in X} Q x) = \prod_{x \in X} P x Q x $$
Lógicamente esto tiene sentido, porque por supuesto, si para todos $x$ , $P x$ es cierto, y también para todos los $x$ , $Q x$ es verdadera, entonces para todo $x$ , $P x$ y $Q x$ son ciertas.
Saber esto nos permite simplificar la declaración 2 hasta el valor $1$ :
$$ (\forall x, P x \rightarrow Q x) \wedge (\exists x, P x) \rightarrow (\exists x, Q x) \tag{2} $$ $$ 1 + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1) + (\prod_x 1 + P x + P x Q x)((\prod_x P x + 1) + 1)((\prod_x Q x + 1) + 1) \tag{3} $$ $$ 1 + (\prod_x 1 + P x + P x Q x)(\prod_x Q x) + (\prod_x 1 + P x + P x Q x)(\prod_x P x + 1)(\prod_x Q x + 1) \\ 1 + (\prod_x (1 + P x + P x Q x)(Q x)) + (\prod_x (1 + P x + P x Q x)(P x + 1)(Q x + 1)) \\ 1 + (\prod_x 1 + P x + Q x + P x Q x) + (\prod 1 + P x + Q x + P x Q x) \\ 1 + 2(\prod_x 1 + P x + Q x + P x Q x) \\ 1 $$
(este último paso funciona porque $2a = 0 \text{ (mod 2)}$ )
Como otro ejemplo: $(\forall_x, P x \rightarrow Q x) \rightarrow (\exists_x, Q x)$ se simplifica a $(\prod_x P x + Q x + P x Q x + 1) + 1$ o $\exists_x, P x \vee Q x$ . Aunque no es intuitivo (para mí), las tablas de verdad muestran que estas dos fórmulas lógicas son, de hecho, equivalentes.
La pregunta sigue en pie
Así que eso es bastante bueno, algunos enunciados de predicado ahora pueden ser simplificados y comprobados para las tautologías. Sin embargo, este truco no funciona para todas las afirmaciones. Por ejemplo, el siguiente enunciado:
$$ \forall_x, \forall_y, R(x,y) $$
Aquí, las dos variables introducidas $x$ y $y$ tener alguna interacción. El enunciado no puede separarse y escribirse en la forma $(\forall_x, \ldots)(\forall_x, \ldots)$ . Parece que, cuando hay "interacción" entre las variables, el truco de la multiplicación no se puede aplicar, ya que algo como $\prod_x R(x,x)$ no serían equivalentes.
Ahora me estoy centrando en intentar reducir el siguiente enunciado a $1$ (como debe ser):
$$ (\exists_x, \forall_y, R(x,y)) \rightarrow (\forall_x, \exists_y, R(y,x)) \tag{5} $$
Mi pregunta original se mantiene, pero ahora dirigida a la declaración 5 .
1 votos
Una duda : Lógica de predicados monádica es decidible, mientras que el caso general no lo es. Si es así, creo que una "reducción" del caso general a la aritmética binaria no será posible, de lo contrario podemos calcular la fórmula correspondiente para comprobar validez ...
1 votos
Creo que quieres "Eliminación de la Cuantificación" en Wikipedia. Pensé que los alogitmos detrás de ella fueron elaborados en los primeros días de las computadoras para la "Prueba de Teoremas".