Pruebas de lógica proposicional - Necesito ayuda para demostrar que todo subconjunto adecuado de mi conjunto es satisfacible.

Question

Por favor, ayude con la siguiente prueba:

Dejemos que $S =$ { $A_1, (A_1\to A_2), (A_2 \to A_3), (A_3 \to A_4), (¬A_4)$ }. Demostrar que cualquier subconjunto adecuado de $S$ es satisfacible.

Sólo con mirar el conjunto S, puedo ver que la afirmación es cierta. La única forma que veo de demostrarlo es ir caso por caso. ¿Alguien ve una forma mejor de demostrarlo? También, por favor, comparta cualquier consejo general para demostrar esta afirmación para diferentes valores de $S$ .

Answer 1

Si $T\subset S$ no contiene $A_1$ , haciendo entonces que todos los $A_i$ false satisfará todas las fórmulas de $T$ . Si $T\subseteq S$ no contiene $\neg A_4$ y, a continuación, establecer todos los $A_i$ verdadero satisfará todas las fórmulas de $T$ . Si $A_1$ y $\neg A_4$ son ambos en $T$ , entonces dejemos que $i$ sea cualquier número entero tal que $A_{i}\to A_{i+1}$ es no en $T$ ; tal $i$ debe existir, con $1\leq i\leq 3$ . A continuación, la configuración de todos los $A_k$ con $k\leq i$ cierto y todo $A_k$ con $k\gt i$ false satisfará todas las fórmulas de $T$ (la única fórmula de $S$ que es falso bajo esta asignación es $A_i\to A_{i+1}$ que no está en $T$ ).