Prueba directa (Lógica)

Question

Necesito ayuda, tengo que dar por resolución una prueba directa de

He hecho una conjunción y he conseguido:

¿Cómo puedo dar una prueba directa por resolución?

Answer 1

Para aplicar Resolución a :

$\alpha, \beta \vDash \delta$ --- (*)

hay que tener en cuenta la fórmula :

$\alpha \land \beta \land \lnot \delta$ --- (§)

es decir, considerar la conjunción de todos los locales y la negación de la sentencia a probar.

Esto es así porque (*) es válido si $\alpha \land \beta \rightarrow \delta$ válido y esto es válido si su negación, que es (§) es contradictorio o idénticamente falso.

Pero (§) es contradictoria si el conjunto de fórmulas $\Sigma = \{ \alpha, \beta, \lnot \delta \}$ es insatisfactible .

Así, la sentencia (§) se transforma en un forma normal conjuntiva con los conjuntos vistos como elementos de un conjunto $\Sigma$ de cláusulas, donde un cláusula es una disyunción finita de literales .

---

Así, si aplicamos el procedimiento a nuestro ejemplo, tenemos :

(i)

$(\lnot P \land \lnot S) \lor Q$

que, por distributividad es :

$(\lnot P \lor Q) \land (\lnot S \lor Q)$ .

Entonces tenemos :

(ii)

$P \lor Q \lor \lnot R$

que ya es una cláusula.

Finalmente la negación de la conclusión :

(iii)

$\lnot (\lnot R \lor Q)$

que es :

$R \land \lnot Q$ .

Ahora formamos la conjunción de todas las cláusulas :

$(\lnot P \lor Q) \land (\lnot S \lor Q) \land (P \lor Q \lor \lnot R) \land R \land \lnot Q$ .

A partir de ella, obtenemos el conjunto

$\Sigma = \{ \lnot P \lor Q, \lnot S \lor Q, P \lor Q \lor \lnot R, R, \lnot Q \}$ .

Ahora aplicamos el norma de resolución

se aplica a todos los posibles pares de cláusulas que contienen literales complementarios. Después de cada aplicación de la regla de resolución, la frase resultante se simplifica eliminando los literales repetidos. Si la frase contiene literales complementarios, se descarta (como tautología). En caso contrario, y si aún no está presente en el conjunto de cláusulas $\Sigma$ se añade a $\Sigma$ y se tiene en cuenta para realizar nuevas inferencias de resolución.

(i) Considere : $P \lor Q \lor \lnot R$ y $R$ y simplificar a $P \lor Q$ que debe añadirse a $\Sigma$ .

(ii) Considere $P \lor Q$ y $\lnot P \lor Q$ y simplificar a $Q$ añadiéndolo a $\Sigma$ .

(iii) Considere $Q$ y $\lnot Q$ y simplificar a la cláusula vacía : $\square$ .

La cláusula vacía es insatisfactible por lo que también $\Sigma$ es.

Habiendo demostrado que

$\alpha \land \beta \land \lnot \delta$

es insatisfactible, podemos conluir con :

$\alpha, \beta \vDash \delta$ .

---

Comentario

El primer punto clave del método es la simplificación de $A \lor P$ y $B \lor \lnot P$ en $A \lor B$ .

Esto equivale simplemente a $A \lor P, B \lor \lnot P \vDash A \lor B$ que no es más que una aplicación de silogismo : $\lnot A \rightarrow P, P \rightarrow B \vDash \lnot A \rightarrow B$ .

Así, los pasos de simplificación equivalen a partir de la fórmula $\alpha \land \beta \rightarrow \lnot \delta$ , reescríbalo como un conjunto de cláusulas $\Sigma$ y luego simplificar $\Sigma$ aunque la regla de resolución.

El otro punto clave del método es la simplificación de $Q$ y $\lnot Q$ para producir el cláusula vacía : $\square$ .

Olvídate del "cuadrado" y reescribe $\Sigma$ como la conjunción de las cláusulas que contiene.

Obtenemos :

$[Q \land (\lnot S \lor Q) \land \lnot Q] \equiv [(Q \land \lnot Q) \land (\lnot S \lor Q)]$ .

Pero $Q \land \lnot Q$ es un contradicción es decir, siempre es falso por lo que la última fórmula es simplemente :

$False \land (\lnot S \lor Q)$

y $False \land A \equiv False$ , para $A$ lo que sea, y esto es suficiente para concluir que $\Sigma$ es insatisfactible (para demostrar la conclusión con el método anterior, tenemos que producir el cláusula vacía y no para transformar $\Sigma$ en el conjunto vacío ...).

Answer 2

Partiendo de la respuesta de Mauro tenemos 1. ¬P∨Q, 2. ¬S∨Q, y 3. P∨Q $\lor$ ¬R. Aplicando la resolución a 1. y 3. obtenemos

Q $\lor$$ \no $R, which is your conclusion. If you need to get to the empty clause, then you can assume R and $ \no $Q, since $ \no $($ \no $R$ \N - El cloruro de calcio $Q) is logically equivalent to R$ \N - La tierra $$\lnot$ Q.