Mostrar con resolución la prueba de que la expresión es una tautología.

Question

Tengo la expresión booleana:

$$ ((\neg A \lor B) \land (\neg B \lor \neg C))\implies (A\implies \neg C) $$

Me han dado nueva forma a esta tan lejos que no la equivalencia y la no implicación es incluido. Que yo sepa, es importante para la resolución de que la función Booleana es en CNF. Mi transformación, a continuación, fluye en esta expresión: $$ ((\neg A \lor B) \land (\neg B \lor \neg C))\implies (A\implies \neg C) $$ $$ ((\neg A \lor B) \land (\neg B \lor \neg C))\implies (\neg A \lor \neg C) $$ $$ \neg((\neg A \lor B) \land (\neg B \lor \neg C))\lor (\neg A \lor \neg C) $$ $$ (\neg(\neg A \lor B) \lor \neg(\neg B \lor \neg C))\lor (\neg A \lor \neg C) $$ $$ ((A \land \neg B) \lor (B \land C))\lor (\neg A \lor \neg C) $$ Que aún no está CNF, a la derecha? Mi pregunta es, por lo tanto, alguien puede ir a que me la transformación pasos? Cómo llegar a la CNF forma?

Si yo tuviera la CNF forma, yo podría mostrar una tautología con la resolución. Para esto necesito la cláusula conjunto de la CNF.

Answer 1

Para entrar en CNF, distribuir $\lor$'s $\land$'s. Así:

$$ ((A \land \neg B) \lor (B \land C))\lor (\neg A \lor \neg C) \Leftrightarrow$$

$$ (((A \land \neg B) \lor B) \land (A \land \neg B) \lor C))) \lor (\neg A \lor \neg C) \Leftrightarrow$$

$$ ((A \lor B) \land (\neg B \lor B) \land (A \lor C) \land (\neg B \lor C)) \lor (\neg A \lor \neg C) \Leftrightarrow$$

$$ ((A \lor B) \land \top \land (A \lor C) \land (\neg B \lor C)) \lor (\neg A \lor \neg C) \Leftrightarrow$$

$$ ((A \lor B) \land (A \lor C) \land (\neg B \lor C)) \lor (\neg A \lor \neg C) \Leftrightarrow$$

$$ ((A \lor B) \lor (\neg A \lor \neg C)) \land ((A \lor C) \lor (\neg A \lor \neg C)) \land ((\neg B \lor C) \lor (\neg A \lor \neg C)) \Leftrightarrow$$

$$ (A \lor B \lor \neg A \lor \neg C) \land (A \lor C \lor \neg A \lor \neg C) \land (\neg B \lor C \lor \neg A \lor \neg C) \Leftrightarrow$$

$$ \top \land \top \land \top \Leftrightarrow$$

$$\top$$

Hmmm....

OK, por lo que hemos tomado de la declaración es y probado que esto es una tautología!

... pero no a través de la resolución ...

De hecho, usted tiene el mal set-up! Para probar esta afirmación a ser una tautología a través de la resolución, primero debe anular la declaración, y luego lo puso en CNF, por lo tanto en las cláusulas, y a continuación se derivan de la cláusula vacía a través de la resolución:

$$ \neg (((\neg A \lor B) \land (\neg B \lor \neg C))\to (A\to \neg C)) \Leftrightarrow$$

$$ ((\neg A \lor B) \land (\neg B \lor \neg C))\land \neg (A \to \neg C) \Leftrightarrow$$

$$ (\neg A \lor B) \land (\neg B \lor \neg C)\land A \land C$$

Esto es ahora en CNF! ... y usted encontrará que la resolución que ahora es trivial

Answer 2

Para probar que$(X\wedge Y)\to Z$ es una tautología, por resolución , busca probar que$(X\wedge Y\wedge\neg Z)$ es una contradicción (es decir, falsa). Después de todo, si la unión de$X$ y$Y$ implica$Z$, entonces deberá contradecir$\neg Z$.

Entonces, dado que la negación de$A\to\neg C$ es$A\wedge\neg\neg C$, por lo tanto, para probar$((\neg A\vee B)\wedge(\neg B\vee\neg C))\to(A\to\neg C)$, simplemente debe demostrar que$((\neg A\vee B)\wedge(\neg B\vee\neg C))\wedge(A\wedge\neg\neg C)$ es una contradicción.

Es decir, que la forma de la cláusula$\{(\neg A, B),(\neg B,\neg C),(A),(\neg\neg C)\}$ puede resolverse en un conjunto vacío.