Demostrar que la proposición es una tautología.

Question

Tengo dos preguntas sobre los deberes que he estado luchando con. Para el primer necesito demostrar que

$((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$

es una tautología.

He probado los dos enfoques. Primero traté de sustituir a otros lógicamente equivalentes consolidados por los de las proposiciones en el lado izquierdo. Una vez que no, he intentado suponiendo que el lado izquierdo es verdadera y traté de mostrar el lado derecho también debe ser cierto. Yo no era capaz de hacer eso. No hay nada que decir que no puedo usar una tabla de verdad, pero yo preferiría que no. Cualquier ayuda se agradece.

La segunda cuestión es decidir si

$\forall x \exists y(P(x) \to P(y)) \to \exists y \forall x(P(x) \to P(y))$

es lógicamente válido o no. Hace lógicamente válido decir tautología? Si es así, yo no sé ni por dónde empezar.

EDIT: Esta pregunta se pidió originalmente para probar la segunda expresión de la verdad, que era incorrecta.

Answer 1

Una forma de desglosar la primera pregunta es recordar que$s\implies t\equiv \neg s\lor t$. Entonces $$ \begin{align*} [(p \lor q) \land (\lnot p \lor r)] \to (q \lor r) &\equiv \neg[(p\lor q)\land (\neg p\lor r)]\lor(q\lor r)\\ &\equiv (\neg p\land\neg q)\lor(p\land \neg r)\lor (q\lor r)\\ \end {align *} $$ por las leyes de De Morgan. Si$(q\lor r)\equiv\top$, entonces has terminado. De lo contrario,$(q\lor r)\equiv\bot$, entonces$\neg q\equiv\neg r\equiv\top$. Entonces, solo tiene que verificar los casos donde$p\equiv\top$ y donde$p\equiv\bot$, lo cual no es tan malo ya que se trata de una disyunción.

Answer 2

Para la primera pregunta, se observa que la $$(p \lor q) \land (\lnot p \lor r)\Leftrightarrow (p \land \lnot p) \lor (p\land r)\lor (q\land \lnot p)\lor (q\land r)$$ y que $(p\land \lnot p)$ es siempre falso. He omitido el paréntesis por conveniencia debido a que $\lor$ es asociativa, pero si aún no has probado esto, entonces usted debe incluir en ellos (no debería causar un problema).

Para el segundo caso, yo siempre he oído lógicamente válido usado para significar "siempre fiel" o en este caso en concreto, "se cumple para cualquier P". Bajo esta interpretación la segunda pregunta me parece que para ser falso, ya que podríamos tener un diferente $y$ por cada $x$ tal que $P(x)\to P(y)$, y así no $y$ la declaración $\forall x(P(x)\to P(y))$ cierto.

Answer 3

La siguiente es una semántica (modelo teórico) argumento de los cuantificadores pregunta. (No puedo proporcionar un argumento sintáctico, ya no sé qué axiomas, reglas de inferencia se utilizan en el curso. Existe una amplia variabilidad). Vamos a utilizar el siguiente criterio: Una oración en un lenguaje determinado, $L$ es válido si es cierto en todos los $L$estructura $M$. Tenga en cuenta que un $L$-la estructura que tiene, por definición, no está vacío conjunto subyacente.

Vamos a suponer que $P$ tiene sólo uno libre de ocurrencia de una variable. Si en un $L$estructura $M$ para el idioma adecuado $L$, realmente hay un $b$ tal que $P(b)$ que es verdad en $M$, $\exists y\forall x(P(x)\to P(y))$ que es verdad en $M$, ya que el $\forall x(P(x)\to P(b))$ que es verdad en $M$. Así, la frase se le preguntó acerca de que es verdad en $M$. El antecedente es irrelevante.

Si no es $n$ $M$ tal que $P(n)$ es cierto, entonces de nuevo $\exists y\forall x(P(x)\to P(y))$ que es verdad en $M$. Para dejar $b$ ser algún elemento fijo de $M$. Tenga en cuenta que $P(b)$ es falso en $M$. Pero para cualquier $m$ en $M$, $P(m)$ es falso en $M$. De ello se deduce que para cualquier $m$, $P(m)\to P(b)$ es cierto en $M$. Así que de nuevo la frase que le preguntó acerca de que es verdad en $M$, y de nuevo el antecedente es irrelevante.

Comentario: La cosa se basa en el hecho de que $X\to Y$ es verdadera siempre que $Y$ es cierto, y también cada vez que se $X$ es falso. El conectivo "implica" en inglés ordinario, no es simplemente la verdad-funcional. Que es una fuente frecuente de confusión.

Agregado: Para la primera parte, vamos a utilizar una variante de uno de los métodos que se han probado. Se trató de mostrar que si el lado izquierdo es cierto, entonces el lado derecho es la verdad. Que se puede hacer. Pero para mí es algo más fácil de mostrar (en este caso) que si el lado derecho de la implicación es falsa, entonces el lado izquierdo es falso.

Queremos mostrar que $$((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$$ es tautologous. Piense en su oración como una implicación $A \to B$. Para que esto sea falso, necesitamos $q\lor r$ falso y $(p \lor q) \land (\lnot p \lor r)$ cierto. Para $q\lor r$ son falsas, necesitamos $q$ falso y $r$ falso. Así que supongamos $q$ $r$ son falsas.

La única forma entonces para $p\lor q$ a ser verdad, si $p$ es cierto. La única manera para $\lnot p \lor q$ a ser verdad, si $p$ es falso. Así que para ambos de ellos para ser verdad, necesitamos $p$ ser a la vez verdadero y falso! Llegamos a la conclusión de que si $p$ $q$ son falsos, a continuación, $(p \lor q) \land (\lnot p \lor r)$ es falso, por lo que la implicación es siempre cierto.