Pregunta sobre Implicación lógica

Question

Supongamos que $A$ es un conjunto de fórmulas proposicionales, y supongamos que $\varphi$ es una fórmula proposicional. En mi libro de texto escriben $A \models \varphi$ si para cada asignación de verdad $w$ tal que $w(\psi) = 1$ por cada $\psi \in A$ también tenemos $w(\varphi)=1$ .

Ahora me piden que demuestre que $\emptyset\models \varphi$ si y sólo si $\varphi$ es una tautología. ¿Pero cómo puedo demostrarlo? La definición no nos dice nada sobre el vacío $A$ ?

Answer 1

Supongamos que $A = \varnothing$ . Entonces, para cualquier asignación de valores de verdad $w$ , $w(\psi) = 1$ (vacuamente) para todos y cada uno de los $\psi \in A = \varnothing$

¿Por qué?
Porque hay no son $\psi \in A = \varnothing$ . Así que la hipótesis se satisface vacuamente, porque es no es posible para que haya existe cualquier $\psi \in \varnothing$ tal que $w(\psi) \neq 1$ .

Por lo tanto, $\varnothing \models \varphi$ si y sólo si para cada asignación de valor de verdad $w$ , $w(\varphi) = 1$ También. Esto se cumple si y sólo si $\varphi$ es una tautología.

Answer 2

Esta es una buena oportunidad para ilustrar al principiante el papel de estrategias de prueba en el razonamiento matemático de las afirmaciones lógicas.

Obsérvese, en primer lugar, que la definición de vinculación $\models$ si se pone en términos negativos, dice que para demostrar que $A\models\varphi$ no se mantiene uno tiene que encontrar alguna asignación de verdad $v$ que satisface simultáneamente $A$ y no satisface $\varphi$ . Además, recuerda que $v$ se dice que satisface un determinado conjunto de fórmulas $A$ si $v(\psi)=1$ por cada $\psi\in A$ Así que.., contrapositivamente podemos decir que $A$ es no satisfecho por $v$ si hay algún $\psi\in A$ que no se satisface con $v$ , es decir, tal que $v(\psi)=0$ .

[Lemma] Cualquier asignación de verdad $v$ satisface el conjunto vacío de fórmulas.
Prueba. Para afirmar que el conjunto vacío $\emptyset$ no se satisface con una asignación de verdad dada $v$ nos exigiría en primer lugar encontrar alguna fórmula $\psi$ en $\emptyset$ con una determinada propiedad (a saber, la propiedad de no ser satisfecha por $v$ ). Pero esto es una tarea imposible, ya que hay no ¡fórmulas en el conjunto vacío!
(Por cierto, esto es precisamente lo que significa decir que una determinada propiedad es vacuamente cierto .)

[Reclamación principal: una dirección] ( $\emptyset\models \varphi$ ) implica que ( $\varphi$ es una tautología).
Prueba. Supongamos, por contraposición que $\varphi$ no es un tautología es decir, supongamos que hay alguna asignación de verdad $w$ tal que $w(\varphi)=0$ . Por el lema anterior, ya sabemos que $w$ satisface el conjunto vacío $\emptyset$ . Así, por la definición de vinculación, $\emptyset\models \varphi$ no se sostiene.

[Reclamación principal: otra dirección] ( $\varphi$ es una tautología) implica que ( $\emptyset\models \varphi$ ).
Prueba. Supongamos que $\varphi$ es una tautología, es decir, suponer que $v(\varphi)=1$ para cada asignación de verdad $v$ . Supongamos ahora por reducción que $\emptyset\models \varphi$ no se sostiene. De ello se desprende, en particular que hay alguna asignación de verdad $w$ tal que $w(\varphi)=0$ (el fracaso de $\emptyset\models \varphi$ también implica, en particular, que dicha $w$ satisface $\emptyset$ pero que es inocuo y se sabe de todos modos que es verdadero, a partir del lema anterior), es decir, se nos da una asignación de verdad que no satisface $\varphi$ . Esto contradice inmediatamente la suposición sobre el carácter tautológico de $\varphi$ .

P.D.: La exhaustiva cantidad de detalles en las pruebas anteriores suele reducirse a algo así como argumentos de una o dos líneas a medida que los estudiantes adquieren más y más experiencia en su elaboración.