Cómo probar o declaraciones

Question

¿Cómo puedo demostrar afirmaciones de los siguientes tipos?

$A \text{ or } B \implies$ C

$A \implies B \text{ or } C$

No sé cómo demostrar este tipo de afirmaciones cuando tienen "o". ¿Puede alguien decirme diferentes maneras de demostrar tales afirmaciones? ¿Y tal vez darme algunos ejemplos básicos para ayudarme?

Gracias.

Answer 1

Para el primero, puede probar ambos $A\Rightarrow C$ y $B\Rightarrow C$ .

Ejemplo. Si $x=1$ o $x=2$ entonces $x^2-3x+2=0$ .

Prueba: Primero asuma $x=1$ . Entonces $x^2-3x+2=1^2-3\cdot 1+2=1-3+2=0$ como se iba a demostrar. Siguiente asumir $x=2$ . Entonces $x^2-3x+2=4-3\cdot 2+2=4-6+2=0$ como se iba a demostrar. Dado que ambos casos $x=1$ y $x=2$ llevar a $x^2-3x+2$ hemos terminado. $_\square$

Para la segunda, se puede, por ejemplo, demostrar $(A\land \neg B)\Rightarrow C$ .

Ejemplo. Si $a\cdot b=0$ entonces $a=0$ o $b=0$ .

Prueba: Supongamos que $ab=0$ y $a\ne 0$ . Desde $a\ne 0$ se nos permite dividir ambos lados de $ab=0$ por $a$ . De este modo, obtenemos $b=0$ como se iba a demostrar. $_\square$

Answer 2

Me encargaré de un diferentes tipo de objetivo declaración primero, a saber: $P\implies Q$ .

Para demostrar este tipo de afirmación se puede optar por:

1. Supongamos que $P$ es cierto, $(\cdots)$ , concluye $Q$ .
2. Demuestre la afirmación lógicamente equivalente $\neg Q\implies \neg P$ utilizando la misma técnica que la anterior: suponer $\neg Q$ es cierto, $(\cdots)$ , concluye $\neg P$ .
3. Supongamos que $P$ es cierto. Ahora supongamos, esperando encontrar una contradicción, que $Q$ es falso. Encuentra una contradicción y concluye que la última suposición que has hecho ( $\neg Q$ ) es falsa y concluye $Q$ .
4. Considere la tautología $\neg P\lor P$ y hacer una prueba por casos. Si $\neg P$ es cierto, que $P\implies Q$ es lógicamente cierto. Si $P$ es cierto, vuelves a 1.

Para demostrar una objetivo que se parece a $P\lor Q$ puedes probar:

1. Supongamos que $\neg P$ que sea cierto, $(\cdots)$ , concluye $Q$ o asumir $\neg Q$ , $(\cdots)$ , concluye $P$ .
2. A partir de las suposiciones que tengas trata de conseguir $P$ de donde $P\lor Q$ sigue o trata de conseguir $Q$ de donde $P\lor Q$ sigue.

---

Ahora hay algo que debes notar. En primer lugar, las declaraciones $\color{grey}(A\lor B\color{grey})\implies C$ y $A\implies \color{grey}(B\lor C\color{grey})$ son declaraciones del tipo $P\implies Q$ . Sólo en una fase posterior entra en juego la disyunción. Obsérvese el paréntesis fantasma.

Ahora bien, ten en cuenta que son muy, muy distintos. Uno de ellos tendrá finalmente una meta que es una disyunción mientras que el otro tiene la disyunción como hipótesis. Más arriba he tratado el caso en el que la meta es una disyunción.

Cuando tu hipótesis es una disyunción $P\lor Q$ y quieres probar $R$ . Puedes probar la prueba por casos: si tu hipótesis es cierta, entonces $P$ es verdadero o $Q$ es cierto:

1. Supongamos que $P$ es cierto, $(\cdots)$ , concluye $R$ .
2. Supongamos que $Q$ es cierto, $(\cdots)$ , concluye $R$ .

Finalmente concluir que $\color{grey}(P\lor Q\color{grey})\implies R$ .

---

Puedes encontrar muchos ejemplos y una explicación más detallada en este increíble libro: Cómo demostrarlo: Un enfoque estructurado , por D.J. Velleman .

Answer 3

Una versión más formal de otra respuesta ( #396261 ): Para el primero, \begin{align} & A \lor B \implies C \\ \iff & \;\;\;\;\;\text{"expand $\implies$"} \\ & \lnot (A \lor B) \lor C \\ \iff & \;\;\;\;\;\text{"De Morgan"} \\ & (\lnot A \land \lnot B) \lor C \\ \iff & \;\;\;\;\;\text{"distribute $\lor$ over $\land$"} \\ & (\lnot A \lor C) \land (\lnot B \lor C) \\ \iff & \;\;\;\;\;\text{"reintroduce $\implies$, twice"} \\ & (A \implies C) \land (B \implies C) \\ \end{align} En el caso de la segunda, la reescritura puede hacerse de varias maneras: una es \begin{align} & A \implies B \lor C \\ \iff & \;\;\;\;\;\text{"expand $\implies$"} \\ (*)\;\phantom\iff & \lnot A \lor B \lor C \\ \iff & \;\;\;\;\;\text{"reintroduce $\implies$ in a different way"} \\ & \lnot (\lnot A \lor B) \implies C \\ \iff & \;\;\;\;\;\text{"De Morgan"} \\ & A \land \lnot B \implies C \\ \end{align}

Actualización. Como bien indica un comentario, de $(*)$ tienes muchas alternativas. Además de la primera y la última expresión del último cálculo, tenemos las siguientes equivalencias:

• $\lnot B \implies \lnot A \lor C$
• $\lnot C \implies \lnot A \lor B$
• $A \land \lnot C \implies B$
• $\lnot B \land \lnot C \implies \lnot A$
• $A \land \lnot B \land \lnot C \implies \textrm{false}$

(Esto último es esencialmente una prueba por contradicción.) Todo esto se sigue por el hecho de que $\lor$ es conmutativo (simétrico) y asociativo.