¿Cuántas refutaciones se necesitan para completar un gráfico de implicación?

Question

Tengo 4 posibles propiedades de un tipo de objeto matemático, y quiero demostrar sus implicaciones. He demostrado $P_1 \rightarrow P_2$ , $P_2 \rightarrow P_3$ y, por tanto, también $P_1 \rightarrow P_3$ .

Ahora bien, creo que no son posibles otras implicaciones entre ellas, y de hecho pueden refutar todas las demás implicaciones. ¿Cuál es el menor número de implicaciones que necesito refutar para refutarlas todas?

¿Existe un algoritmo general para esta pregunta? ¿Dado un grafo dirigido de implicaciones entre propiedades, y preguntando cuántas implicaciones hay que refutar para demostrar que no existen otras flechas en el grafo? Pues sí, si el algoritmo se limita a comprobar exhaustivamente todas las posibilidades. Pero, ¿hay alguno más eficiente?

En respuesta a bof, Aquí sólo pregunto sobre la refutación de las flechas de la forma $P_n \rightarrow P_m$ y no de la forma más general $P_n \wedge P_m \rightarrow P_k$ Aunque eso podría ser una buena extensión del problema.

Después de buscar un poco, creo que una manera formal de plantear la pregunta es: dado un grafo dirigido $G$ con vértices $V$ y su cierre transitivo es $G_t$ . Encuentre un conjunto mínimo (el más pequeño en número) de aristas dirigidas "prohibidas", tal que $G_t$ es el único grafo dirigido transitivo con vértices $V$ que contiene $G$ y no contiene ninguna de las aristas dirigidas prohibidas.

Answer 1

Dejemos que $X$ sea el conjunto de nuestros objetos matemáticos. Para demostrar que $P_4$ no está implícito en todos ellos, nos gustaría encontrar un ejemplo $x$ tal que $\alpha(x) \land \neg P_4(x)$ donde $\alpha$ es $P_1, P_2, P_3$ . Sin embargo, debido a las implicaciones que ha demostrado, es suficiente para mostrar $x$ tal que $P_1(x) \land \neg P_4(x)$ Es decir $P_1 \not\to P_4$ .

Pero esto no es todo, para demostrar que $P_4$ es independiente también tenemos que encontrar $x$ tal que $P_4(x) \land \neg \alpha(x)$ . Observe que también ha demostrado $\neg P_3(x) \to \neg P_2(x)$ y $\neg P_2(x) \to \neg P_1(x)$ para todos $x \in X$ , por lo que es suficiente con encontrar $x$ con $P_4(x) \land \neg P_3(x)$ es decir $P_4 \not\to P_3$ .

Eso puede parecer todo, pero no lo es. Estamos olvidando $P_2 \not\to P_1$ y $P_3 \not\to P_2$ y $P_3 \not\to P_1$ . Para ello necesitamos un $x$ tal que $P_2(x) \land \neg P_1(x)$ y algunos diferentes $x$ tal que $P_3(x) \land \neg P_2(x)$ .

En cuanto a si existe tal algoritmo, definitivamente sí: para todos los subconjuntos de implicaciones posibles se puede comprobar si ese subconjunto es suficiente para demostrar el estado de cada implicación. Sin embargo, eso sería bastante lento, así que ahora la pregunta es, ¿podemos hacerlo más rápido? Mi opinión es que sí, pero actualmente no tengo pruebas.

Espero que esto ayude $\ddot\smile$

Editar: Gracias a @bof por descubrir un fallo en el algoritmo que sugerí.

Editar 2:

He aquí un segundo intento de algoritmo. Empezaré con un cambio de terminología, para que sea más concreto y, por tanto, quizá más sencillo.

Dejemos que $V = \{1,2,3,\ldots,n\}$ sea el conjunto de vértices y añada una arista dirigida $i \to j$ si $P_i \to P_j$ . Además, para cada vértice $v \in V$ crear conjuntos $A_v = \{i \in V \mid P_i \to P_v\}$ En particular $v \in A_v$ . Estos conjuntos tienen la propiedad de que $$P_i \to P_j \iff A_i \subseteq A_j,$$ es decir $$P_i \not\to P_j \iff A_i \not\subseteq A_j \iff \exists v \in V.\ v \in A_i \land v \notin A_j.$$

Además, digamos que $A_i$ es un sucesor de $A_j$ si $A_j \subsetneq A_i$ y para todos $k$ tal que $A_j \subseteq A_k \subseteq A_i$ tenemos $k = j$ o $k = i$ (intuitivamente, $A_i$ está un paso por delante de $A_j$ ). De la misma manera, $A_i$ es un predecesor de $A_j$ si $A_j$ es un sucesor de $A_i$ (intuitivamente $A_i$ es un paso antes de $A_j$ ).

El algoritmo:

1. Dejemos que $D$ sea el conjunto de todas las parejas que aún no se han liquidado, es decir $$D \gets \{ (i,j) \in V \times V\mid A_i \not\subseteq A_j \land A_j \not\subseteq A_i\}$$
2. Elija cualquier par de este tipo $$(i,j) \gets \operatorname{any}(D)$$ Observe que $i \in A_i$ pero $i \notin A_j$ . No intentaremos encontrar un par alternativo con una propiedad similar.
3. Dejemos que $i'$ sea cualquier predecesor de $i$ tal que $i' \notin A_j$ o $i$ si no existe tal predecesor y asignar $i'$ a $i$ \begin {align} &i' \gets \operatorname {cualquiera} {k} \in \operatorname {pred}(i) \mid k \notin A_j \ ~ -} \\ & \mathtt {si} {si} \neq \bot : \\ & \quad i \gets i' \end {align}
4. Haga lo mismo con $j$ es decir, encontrar un sucesor adecuado: \begin {align} &j' \gets \operatorname {cualquiera} {k} \in \operatorname {succ}(j) \mid i \notin A_k \N - en el caso de que se trate de una persona con un problema de salud mental.} \\ & \mathtt {si}\año j' \neq \bot : \\ & \quad j \gets j' \end {align}
5. Repita los pasos $4$ o $5$ hasta que no sea posible ningún otro cambio.
6. Prueba $P_i \not\to P_j$ (es decir, la salida de ese par como uno de los que tenemos que probar).
7. Eliminar de $D$ cualquier par que esté implícito en $P_i \not\to P_j$ .
8. Repetir desde el paso $2$ hasta $D$ se vacía.

Algunos puntos importantes:

• Como el grafo es un DAG, los pasos 3 y 4 no pueden repetirse infinitamente.

• Si $(i,j) \in D$ , entonces después de los pasos $3$ y $4$ la nueva pareja $(i,j)$ sigue en $D$ .

  • Supongamos lo contrario y dejemos que $(i',j')$ sea el nuevo par. Recuerde que $i' \in A_{i'} \subseteq A_i$ y $i' \notin A_{j'} \supseteq A_j$ porque así es como ese nuevo par se construyó. Si $(i',j')\notin D$ Entonces tuvo que ser retirado de $D$ en algún momento y tuvo que haber un par $(i'',j'')$ tal que $i'' \in A_{i''} \subseteq A_{i'} \subseteq A_i$ y $i'' \notin A_{j''} \supseteq A_{j'} \supseteq A_j$ pero eso implica $(i,j) \notin D$ .

• Así, cada vez que llegamos al paso 7 se elimina al menos un par, por lo que el algoritmo termina en tiempo finito.

• Cuando terminemos el paso $5$ , la pareja $(i,j)$ tiene la propiedad de que ninguna declaración $P_{i'} \not\to P_{j'}$ para algún otro par $(i',j')$ podría implicar $P_i \not\to P_j$ .

  • Supongamos, por otra parte, que existe tal par $(i', j')$ . Esto significa que $i' \in A_{i'} \subseteq A_i$ y $i' \notin A_{j'} \supseteq A_j$ pero eso implica paso $5$ no pudo terminar porque $(i',j)$ o $(i,j')$ es un cambio válido.

• Por lo tanto, cada par que el algoritmo produce tiene que ser probado.

• Como el algoritmo sólo termina cuando $D$ está vacío, se imprimirán todos los pares necesarios.

Espero no haberme perdido nada esta vez.

Answer 2

Podemos suponer que se han identificado enunciados equivalentes, de modo que la relación de implicación es antisimétrica, además de reflexiva y transitiva, es decir, es un orden parcial. Así, el problema puede plantearse de la siguiente manera:

Dejemos que $V$ sea un conjunto finito parcialmente ordenado por una relación $R.$ ¿Cuál es el conjunto más pequeño $D\subseteq(V\times V)\setminus R$ tal que toda relación transitiva $T\subseteq V\times V,$ que contiene $R$ y es disjunta de $D,$ es igual a $R?$

Evidentemente, cualquier conjunto de este tipo $D$ debe contener cualquier par $(a,b)\in(V\times V)\setminus R$ tal que $R\cup\{(a,b)\}$ es una relación transitiva; en caso contrario $T=R\cup\{(a,b)\}$ sería una relación transitiva que contiene $R$ y disjuntos de $D$ y desigual a $R.$ Dejemos que $D_0$ sea el conjunto de todos esos pares:

$$D_0=\{(a,b)\in(V\times V)\setminus R:R\cup\{(a,b)\}\text{ is transitive}\}.$$

Afirmo que $D_0$ es el conjunto deseado. Sea $T\subseteq V\times V$ sea una relación transitiva tal que $R\subseteq T$ y $T\cap D_0=\emptyset;$ Tengo que demostrar que $T=R.$ Supongamos para una contradicción que $T\setminus R\ne\emptyset.$ Elija un mínimo (con respecto al orden parcial $R$ ) elemento $a\in V$ tal que $(a,y)\in T\setminus R$ para algunos $y,$ y luego elegir un elemento maximul $b\in V$ tal que $(a,b)\in T\setminus R.$ Es fácil ver que $R\cup\{(a,b)\}$ es transitivo, por lo que $(a,b)\in D_0,$ contradice nuestra suposición de que $T\cap D_0=\emptyset.$

En otras palabras, escribir $x\le y$ para $(x,y)\in R,$ podemos describir $D_0$ como el conjunto de pares ordenados $(a,b)\in(V\times V)$ que satisfagan las condiciones:

$$a\not\le b$$ $$\forall x\in V\ (x\lt a\implies x\le b);$$ $$\forall x\in V\ (b\lt x\implies a\le x.$$

Para $a\in V$ dejar $F(a)$ sea el conjunto de todos los elementos maximales de $\{x:x\lt a\},$ y que $G(a)$ sea el conjunto de todos los elementos mínimos de $\{x:b\lt x\}.$ Si queremos calcular $D_0,$ podríamos empezar por calcular los conjuntos $F(a)$ y $G(a)$ para cada $a\in V;$ entonces, para cada par ordenado $a\not\le b,$ sólo tenemos que comprobar las desigualdades $x\le b$ para $x\in F(a),$ y $a\le x$ para $x\in G(b).$

Ejemplo. Si $V=\{v_0,v_1,v_2,v_3\}$ y $R=\{(v_0,v_0),(v_0,v_1),(v_1,v_1),(v_2,v_2),(v_2,v_3),(v_3,v_3)\},$ entonces $D_0=\{(v_0,v_3),(v_1,v_0),(v_2,v_1),(v_3,v_2)\}.$

Answer 3

Aquí está el algoritmo exhaustivo implementado en Mathematica:

exhaustiveAlgorithm[vertices_, inEdges_] := 
 Module[{v = vertices, i = inEdges, g, e},
  g = Graph[v, i];
  e = EdgeList@GraphComplement@TransitiveClosureGraph@g;
  {EdgeList@TransitiveReductionGraph@g, 
   SelectFirst[
     a \[Function] 
      AllTrue[Complement[e, a], 
       l \[Function] 
        AnyTrue[a, 
         EdgeQ[TransitiveClosureGraph@EdgeAdd[g, l], #] &]]]@Subsets@e}
  ]

Uso:

exhaustiveAlgorithm[{P1, P2, P3, P4}, {P1 -> P2, P2 -> P3}]

devolverá

{{P1 -> P2, P2 -> P3}, {P1 -> P4, P2 -> P1, P3 -> P2, P4 -> P3}}

diciéndole que debe mostrar

$$P_1 \to P_2, P_2 \to P_3, \lnot(P_1 \to P_4), \lnot(P_2 \to P_1), \lnot(P_3 \to P_2), \lnot(P_4 \to P_3).$$

Sé que esto no responde a tu pregunta, pero espero que te ayude. Habría escrito esto como un comentario pero no cabía en el límite de caracteres.