6.4: Reducción a Casos

Hecho\(\PageIndex{1}\)

Se mantiene la siguiente equivalencia lógica:

\ begin {ecuación*} (s_1\ lor s_2\ lor\ cdots\ lor s_m)\ fila derecha t\;\ Izquierda fila\; (s_1\ fila derecha t)\ tierra (s_2\ fila derecha t)\ tierra\ cdots\ tierra (s_m\ fila derecha t)\ texto {.} \ end {ecuación*}

Idea de prueba

Esta es solo una versión extendida de Example 2.2.3.

Si

\ comenzar {ecuación*} C_1\ or C_2\ lor\ cdots\ lor C_m\ final {ecuación*}

es una tautología, entonces

\ begin {ecuación*} P\;\ Leftrightarrow\; P\ land (C_1\ lor\ cdots\ lor C_m)\;\ Leftrightarrow\; (P\ land C_1)\ lor\ cdots\ lor (P\ land C_m)\ text {.} \ end {ecuación*}

Por sustitución y hecho\(\PageIndex{1}\),

\ comenzar {ecuación*} P\ fila derecha Q\;\ Izquierda fila\; (P\ tierra C_1\ fila derecha Q)\ tierra\ cdots\ tierra (P\ tierra C_m\ fila derecha Q). \ end {ecuación*}

Una conjunción sólo es verdadera si cada “factor” en la conjunción es verdadero, por lo que la conjunción de la derecha anterior sólo puede ser una tautología si cada condicional\(P \land C_1 \rightarrow Q\) es una tautología. Por lo tanto, cuando tenemos una colección de declaraciones\(C_1,\ldots ,C_m\) para que

\ comenzar {ecuación*} C_1\ or C_2\ lor\ cdots\ lor C_m\ final {ecuación*}

es una tautología, podemos probar\(P \rightarrow Q \) probando en su lugar cada\(P \land C_i \Rightarrow Q\) una de una a la vez. Esto también es válido para declaraciones universales, ya que\(\forall\) distribuye sobre\(\land\) (Proposición 4.2.2).

Ahora bien, tener que probar muchas declaraciones un poco más complicadas\(P \land C_i \Rightarrow Q\) parece mucho más trabajo que solo probar la simple declaración única\(P \rightarrow Q\) — ¿por qué querríamos ir a todo este esfuerzo extra?

Idea\(\PageIndex{1}\)

Cada declaración de caso\(C_i\) proporciona información extra que se puede combinar con la suposición que\(P\) es verdadera para llegar a la conclusión que también\(Q\) debe ser cierta.

Procedimiento\(\PageIndex{1}\): Reduction to cases

• Para probar\(P\Rightarrow Q\text{,}\) determinar un conjunto de casos\(C_1, C_2, \ldots , C_m\) tal que\(C_1 \lor C_2 \lor \cdots \lor C_m\) sea cierto, luego proporcionar una prueba separada de cada implicación lógica\(P \land C_i \Rightarrow Q\text{.}\)
• Para probar\((\forall x)(P(x)\Rightarrow Q(x))\text{,}\) determinar un conjunto de casos\(C_1(x), C_2(x), \ldots , C_m(x)\) tales que
  \ comenzar {ecuación*} (\ forall x) (C_1 (x)\ lor C_2 (x)\ lor\ cdots\ lor C_m (x))\ final {ecuación*}
  es cierto, luego proporcionar una prueba separada de cada implicación lógica universalmente cuantificada\((\forall x)(P(x) \land C_i(x) \Rightarrow Q(x))\text{.}\)

Ejemplo\(\PageIndex{1}\)

\(n^2 - n\)El espectáculo siempre es parejo.

Solución

Dejar\(P(n)\) representar el predicado “\(n\)es un entero” y vamos a\(Q(n)\) representar el predicado “\(n^2 - n\)es par”, cada uno con dominio los enteros. Tenga en cuenta que en realidad\(P(n)\) es cierto para cada uno\(n\) en el dominio, ya que nuestra declaración original no hace ninguna premisa adicional\(n\) además de su dominio.

Supongamos que\(n\) es un entero. Irrumpir en los casos con base en si\(n\) es par o impar; en cada caso, proceder por prueba directa.

Caso\(n\) incluso. Si\(n\) es par, entonces existe un entero\(m\) tal que\(n = 2m\text{.}\) Entonces,

\ comenzar {ecuación*} n^2 - n = n (n-1) = 2m (2m - 1)\ final {ecuación*}

también es parejo.

Caso\(n\) impar. Si\(n\) es impar, entonces\(n - 1\) es par, entonces existe un entero\(m\) tal que\(n - 1 = 2m\text{,}\) o\(n = 2m + 1\text{.}\) Entonces,

\ comenzar {ecuación*} n^2 - n = n (n-1) = (2m+1) (2m)\ final {ecuación*}

es parejo.

Advertencia\(\PageIndex{1}\)

¡Asegúrate de que tus maletas cubran todas las posibilidades! (Aunque no es necesario que sus casos no se superpongan.)

Comprueba tu comprensión. Intento de Ejercicio 6.12.7.