Tipos de Pruebas – Lógica de Predicados | Matemáticas discretas

Introducción:
La forma más básica de lógica es la lógica proposicional. Las proposiciones, que no tienen variables, son las únicas afirmaciones que se consideran. Como no hay variables en las proposiciones, son siempre verdaderas o siempre falsas.
Ejemplo –

1. P : 2 + 4 = 5. (Siempre Falso) es una proposición.
2. P : y * 0 = 0. (Siempre cierto) es una proposición.

La mayoría de las conclusiones matemáticas se expresan como implicaciones: P y Q : P ⇒ Q
Sabemos que –
 

PAGS	q	P ⇒ Q
T	T	T
T	F	F
F	T	T
F	F	T

Tipos de pruebas:
Digamos que queremos probar la implicación P ⇒ Q. Aquí hay algunas opciones para que consideres.

1. Prueba trivial: 
si sabemos que Q es verdadero, entonces P ⇒ Q es verdadero sin importar cuál sea el valor de verdad de P.
Ejemplo: 
si hay 1000 empleados en una organización geeksforgeeks, entonces 3 ² = 9.
Explicación:  
Sea P: hay 1000 empleados en una organización geeksforgeeks & Q: 3 ² = 9.
Sabemos que Q siempre es verdadera y está en la tabla de verdad podemos ver que siempre que Q es verdadero, P ⇒ Q es verdadero, cualquiera que sea el valor verdadero de P.

2. Prueba vacía: 
si P es una conjunción (ejemplo: P = A ^ B ^ C) de otras hipótesis y sabemos que una o más de estas hipótesis es falsa, entonces P es falsa y, por lo tanto, P → Q es vagamente verdadera independientemente de el valor de verdad de q.

Ejemplo: 
si 5! = 100, luego 3 ! = 6.
Explicación –  
Sea P : 5 ! = 100, y P : 3 ! = 6.
Sabemos que P siempre es falsa y en la tabla de verdad podemos ver que siempre que P es Falsa, P ⇒ Q es verdadera, cualquiera que sea el valor de verdad de Q.

3. Prueba directa: 
suponga P, luego demuestre Q usando reglas de inferencia, axiomas, definiciones y equivalencias lógicas.
Ejemplo: 
para todos los números enteros p y q, si p y q son números enteros impares, entonces p + q es un número par.
Sea P denota : p y q son enteros impares
Q : p + q es un entero par
Para probar : P ⇒ Q
Prueba – 
Como p & q son enteros impares, se pueden representar como :
Supongamos : p = 2m + 1 y q = 2n + 1, donde m & n también son números enteros.
Entonces: p + q = 
= (2m + 1) + (2n +1) (Ley de Sustitución)
= am + 2n + 2 (ley asociativa y conmutativa de la suma)
= 2(m + n + 1) (ley distributiva) 
= Número divisible por 2 y por lo tanto un número par.

4. Prueba por contradicción:  
comenzamos con la suposición de que las hipótesis son correctas y la conclusión es incorrecta, y tratamos de encontrar una contradicción. 
La prueba por contradicción es legítima porque:
¬(P ∧ ¬Q) es equivalente a P ⇒ Q 
Si podemos demostrar que (P ∧ ¬Q) es falsa, entonces ¬(P ∧ ¬Q) es verdadera, y el enunciado equivalente P ⇒ Q es igualmente cierto.

Ejemplo: 
sean x e y números reales. Si 5a + 25b = 156, entonces a o b no es un número entero.
Prueba – 
Sea P : 5a + 25b = 156 & Q :   a o b no es un número entero
¬Q : a o b es un número entero
Entonces, asumimos que tanto a como b son números enteros (¬Q) ⇒ 5(a + 5b ) = 156 (ley distributiva) 
 ⇒ Dado que a y b son números enteros, esto implica que 156 es divisible por 5. 
Sin embargo, el número entero 156 no es divisible por 5. Esta contradicción da el resultado.
Implica que (P ∧ ¬Q) es falso como P es falso
entonces ¬(P ∧ ¬Q) es verdadero y el enunciado equivalente P ⇒ Q es igualmente verdadero.

5.   Prueba por Contrapositiva – 
Podemos probar P ⇒ Q indirectamente mostrando que ¬Q ⇒ ¬P . Suponga ¬Q y luego demuestre ¬P usando reglas de inferencia, axiomas, definiciones y equivalencias lógicas.

Ejemplo: para todos los enteros a y b, si a*b es par, entonces a es par o b es par.
Demostración: Probamos la contrapositiva del enunciado: 
Sea P: a*b es par & Q: a es un entero par o b es un entero par. Entonces:  
¬P: a*b es impar
¬Q: a y b son enteros impares 

Digamos que ¬Q es verdadero, es decir, a y b son ambos enteros impares
a = 2m + 1 yb = 2n + 1; donde m y n son números enteros. 
Entonces:
a*b= (2m + 1)(2n + 1) (por sustitución)
= 4mn + 2m + 2n + 1 (por leyes asociativas, conmutativas y distributivas)
= ​​2(2mn + m + n) + 1 (por Ley distributiva)

Dado que a*b es el doble de un número entero (Como: 2mn + m + n también es un número entero) más 1, a*b es impar.
Entonces muestra que ¬Q ⇒ ¬P. Por lo tanto P ⇒ Q

P. Demuestre que: n puede ser impar si y sólo si n ² es impar.
Solución. 
Debemos probar dos implicaciones para probar esta afirmación:

1. Si n es impar, n ² es impar
2. Si n ² es impar, n es impar

Asumir – 
P : n es impar & Q : n2 es impar. 

1. P ⇒ P :

Estamos usando prueba directa para demostrarlo.
Suponga que n es un entero impar.
Entonces: n= 2p+ 1; para algún entero p.
Entonces n ² = (2p+ 1) ² = 4p ² + 4p+ 1 =2(2p ² + 2a) + 1,; que es 2*(algún entero) + 1.  
Por lo tanto, podemos decir que n ² es impar. Así P ⇒ Q

2. Q ⇒ P :
Estamos usando una prueba contrapositiva aquí.
¬Q : n ² es par y ¬P : n es par.
Necesitamos probar: ¬P ⇒ ¬Q (¬P ⇒ ¬Q significa que Q ⇒ P)
Supongamos que n es un entero par,
Entonces n= 2 ; para algún entero p.
Entonces n2= (2p) ² = 4p ² = 2(2p ² ), que es un entero par ya que es divisible por 2.

De (1.) P ⇒ Q y de (2) Q ⇒ P, n puede ser impar si y solo si n2 es impar.

2. Si un número es divisible por 4, entonces también es divisible por 2.
Solución: 
Usando prueba directa:
Suponga: x es divisible por 4
Entonces: x = k * 4; donde k es un número entero (por definición de división)
Entonces, x = k * (2 * 2)
Entonces, x = (k * 2 )* 2 (Propiedad asociativa de la multiplicación)
Entonces, x = P * 2 donde P = k * 2 ; es un número entero.
Por lo tanto, podemos decir que x también es divisible por 2.

3. Usando la contradicción, demuestre que: Si y + y = y entonces y = 0.
Solución: 
Sea P: y +y = y & Q: y = 0
 Para probar: (P ∧ ¬Q) es falso como (P ∧ ¬Q) es falso, entonces ¬(P ∧ ¬Q) es verdadero, y el enunciado equivalente P ⇒ Q es igualmente verdadero.
P : y + y= y y ¬Q : y~= 0.
(P ∧ ¬Q) significa : Entonces 2y =y y como y ~= 0 podemos dividir ambos lados por y.
Como resultado, obtenemos: 2 = 1, lo cual es una contradicción.
Entonces, (P ∧ ¬Q) es falso y por lo tanto P ⇒ Q es verdadero.