8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
1/76
MATEMÁTICAS DISCRETAS
Universidad de CuencaIngeniería Electrónica y Telecomunicaciones
Ciclo Marzo 2016 a Julio 2016
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
2/76
MATEMÁTICAS DISCRETASTEMA 1: RAZONAMIENTOS Y DEMOSTRACIONES
Lógica de Proposiciones
Razonamientos
Sub-Tema 1: Razonamiento
Sub-Tema 2: Razonamiento válido
Sub-Tema 3: Falacia
Inferencia
Sub-Tema 4: Regla de Inferencia
Sub-Tema 5: Reglas de Inferencia más usuales
Demostraciones
Sub-Tema 6: Teorema
Sub-Tema 7: Corolario
Sub-Tema 8: LemaSub-Tema 9: Demostración
Lógica de Predicados
Razonamientos y Cuantificadores
Sub-Tema 10: Razonamientos y Cuantificadores
Sub-Tema 11: Definiciones matemáticas
Sub-Tema 12: Regla de Particularización
Sub-Tema 13: Regla de Generalización
Métodos de demostración
Sub-Tema 14: Métodos de demostraciónSub-Tema 15: Demostración Vacía
Sub-Tema 16: Demostración Trivial
Sub-Tema 17: Demostración Directa
Sub-Tema 18: Demostración por la Contra recíproca
Sub-Tema 19: Demostración por Contradicción
Sub-Tema 20: Búsqueda de contraejemplos
Sub-Tema 21: Demostración por inducción matemática
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
3/76
Lógica de Proposiciones.
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
4/76
Proposiciones y Tablas de Verdad
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
5/76
Proposición:
Llamaremos de esta forma a cualquier afirmación que sea
verdadera o falsa, pero no ambas cosas a la vez.
Nota: Las proposiciones se denotan con letras minúsculas: p, q, r . . .
. . . La notación p: Tres mas cuatro es igual a siete se utiliza para
definir que p es la proposición “tres mas cuatro es igual a siete”.
Valor de Verdad:
Llamaremos valor verdadero o de verdad de una proposición a su
veracidad o falsedad. El valor de verdad de una proposiciónverdadera es verdad y el de una proposición falsa es falso.
Proposiciones y Tablas de Verdad
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
6/76
Proposiciones y Tablas de Verdad
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
7/76
Proposición Compuesta:
Si las proposiciones simples p1, p2, . . . , pn se combinan para formarla proposición P, diremos que P es una proposición compuesta de p1,
p2, . . . , pn.
Nota 1.2 La propiedad fundamental de una proposición compuesta
es que su valor de verdad esta completamente determinado por losvalores de verdad de las proposiciones que la componen junto con la
forma en que están conectadas.
Proposiciones y Tablas de Verdad
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
8/76
Variables de Enunciado:
Es una proposición arbitraria con un valor de verdad no
especificado, es decir, puede ser verdad o falsa
En el calculo lógico, prescindiremos de los contenidos delos enunciados y los sustituiremos por variables de
enunciado. Toda variable de enunciado p, puede ser
sustituida por cualquier enunciado siendo sus posibles
estados, verdadero o falso. El conjunto de los posibles
valores de una proposición p, los representaremos en lasllamadas tablas de verdad
Proposiciones y Tablas de Verdad
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
9/76
Tablas de Verdad
La tabla de verdad de una proposición compuesta P enumera todas las posiblescombinaciones de los valores de verdad para las proposiciones p1 , p2 , . . . , pn .
Proposiciones y Tablas de Verdad
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
10/76
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
11/76
Conjunción
Dadas dos proposiciones cualesquiera p y q, llamaremos conjunción de ambas
a la proposición compuesta “p y q” y la notaremos p ∧ q. Esta proposición será
verdadera únicamente en el caso de que ambas proposiciones lo sean.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
12/76
Disyunción
Dadas dos proposiciones cualesquiera p y q, llamaremos disyunción de ambas
a la proposición compuesta “p o q” y la notaremos p ∨ q. Esta proposición será
verdadera si al menos una de las dos p o q lo es.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
13/76
Disyunción Exclusiva
Dadas dos proposiciones cualesquiera p y q, llamaremos disyunción exclusiva de
ambas a la proposición compuesta “p o q pero no ambos” y la notaremos p Y q.
Esta proposición será verdadera si una u otra, pero no ambas son
verdaderas.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
14/76
Negación
Dada una proposición cualquiera, p, llamaremos “negación de p” a la
proposición “no p” y la notaremos ¬p. Sera verdadera cuando p sea falsa y
falsa cuando p sea verdadera.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
15/76
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
16/76
Tautologías y Contradicciones
Sea P una proposición compuesta de las proposiciones simples p1
, p2 , . . . , pn
P es una Tautología (“T ”) si es verdadera para todos losvalores de verdad que se asignen a p1 , p2 , . . . , pn .
P es una Contradicción (“C ” )si es falsa para todos los valores de
verdad que se asignen a p1 , p2 , . . . , pn .
Una proposición P que no es tautología ni contradicción se llama,
usualmente, Contingencia.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
17/76
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
18/76
Proposición Condicional
Dadas dos proposiciones p y q, a la proposición compuesta “si p, entonces q” se le llama
“proposición condicional” y se nota por
p → q
¬ p ∨ q
A la proposición “p” se le llama hipótesis, antecedente, premisa o condición
suficiente y a la “q” tesis, consecuente, conclusión o condición necesaria del
condicional. Una proposición condicional es falsa únicamente cuando siendo verdad
la hipótesis, la conclusión es falsa (no se debe deducir una conclusión falsa de una
hipótesis verdadera).
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
19/76
Proposición Condicional
Otras formulaciones equivalentes de la proposición condicional p → q son:
“p solo si q ”.
“q si p ”.
“p es una condición suficiente para q ”.
“q es una condición necesaria para p ”.
“q se sigue de p ”.
“q a condición de p ”.
“q es una consecuencia lógica de p ” .
“q cuando p ”.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
20/76
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
21/76
Proposición Reciproca
Dada la proposición condicional p → q, su reciproca es
la proposición, también condicional, q → p.
Proposición Contra recíproca
Dada la proposición condicional p → q, su contra
recíproca es la proposición, también condicional, ¬q →
¬p.
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
22/76
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
23/76
Proposición bicondicional
Dadas dos proposiciones p y q, a la proposición compuesta
“p si y solo si q”
se le llama “proposición bicondicional” y se nota por
p ←→ q
(p → q) ∧ (q → p)
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
24/76
Conexión entre Proposiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
25/76
Implicación
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
26/76
Implicación Lógica
Se dice que la proposición P implica lógicamente la proposiciónQ, y se escribe P ⇒ Q, si Q es verdad cuando P es verdad.
Implicación
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
27/76
Implicación Lógica y Proposición Condicional
La proposición P implica lógicamente la proposición Q si, y solosi la proposición condicional P → Q es una tautología.
P ⇒ Q solo si P → Q es una tautología
En efecto, supongamos que P implica lógicamente Q. Entonces, de
acuerdo con la definición, cuando P es verdad, Q también lo es y
cuando Q es falso, P es falso, por tanto, la tabla de verdad de P → Q
conteniendo únicamente estas opciones es:
Implicación
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
28/76
Implicación
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
29/76
Implicaciones Lógicas mas Comunes
Implicación
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
30/76
Equivalencia Lógica
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
31/76
Proposiciones Lógicamente Equivalentes
Las proposiciones compuestas P y Q son lógicamente
equivalentes y se escribe P ≡ Q o P Q cuando
ambas tienen los mismos valores de verdad.
Equivalencia Lógica y Proposición Bicondicional
La proposición P es lógicamente equivalente a la
proposición Q si, y solo si la proposición bicondicionalP ←→ Q es una tautología.
Equivalencia Lógica
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
32/76
Equivalencia Lógica
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
33/76
Equivalencias Lógicas mas Comunes
Equivalencia Lógica
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
34/76
Equivalencias Lógicas mas Comunes
Equivalencia Lógica
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
35/76
TEMA 1: RAZONAMIENTOS Y DEMOSTRACIONES
Razonamientos
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
36/76
Una demostración de una proposición significa
un argumento convincente de que la
proposición es verdadera.
Las demostraciones son una forma de
comunicación cuyo objetivo es convencer de la
veracidad de las afirmaciones que se hacen.
Sub-Tema 1: Razonamiento.
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
37/76
Razonamiento
Llamaremos de esta forma a cualquier proposición con la estructura:
P1 ᴧ P2 ᴧ · · · ᴧ Pn → Q
Siendo n un entero positivo.
A las proposiciones Pi, i = 1, 2, . . . , n se les llama premisas del razonamiento y a
la proposición Q, conclusión del mismo.
Sub-Tema 1: Razonamiento.
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
38/76
Razonamiento Valido
El razonamiento anterior se dice que es valido si la conclusión Q es verdadera cada vez
que todas las premisas P1, P
2, . . . , P
n lo sean.
Obsérvese que esto significa que las premisas implican lógicamente la conclusión, es
decir, un razonamiento será valido cuando
P1 ᴧ P2 ᴧ · · · ᴧ Pn ⇒ Q
También podemos decir que el razonamiento es valido si el condicional
P1 ᴧ P2 ᴧ · · · ᴧ Pn → Q
es una tautología. Esto, a su vez, nos permite aceptar como valido el razonamiento en el
caso de que alguna de las premisas sea falsa. En efecto, si alguna de las P i, i = 1, 2, . . . , n
es falsa, entonces P1 ᴧ P2 ᴧ · · · ᴧ Pn será falsa, luego el condicional P1 ᴧ P2 ᴧ · · · ᴧ
Pn→ Q es verdadero, independientemente del valor de verdad de la conclusión Q.
Sub-Tema 2: Razonamiento Valido
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
39/76
Razonamiento Valido
Disponemos de dos formas de probar si un
razonamiento es valido:
1)Comprobar que el condicional P1 ∧ P2 ∧ • • • ∧
Pn → Q es una tautología.
2)Comprobar que P1 ∧ P2 ∧ • • • ∧ Pn ⇒ Q.
Sub-Tema 2: Razonamiento Valido
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
40/76
Falacia
Llamaremos de esta forma a un razonamiento queno es valido.
Sub-Tema 3: Falacia
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
41/76
TEMA 1: RAZONAMIENTOS Y DEMOSTRACIONES
Inferencia
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
42/76
Inferencia
Dado que no siempre es factible construir una tabla de verdad para comprobar la
validez de un razonamiento (cuando el numero de proposiciones es elevado, la tablapuede ser excesivamente larga), utilizaremos únicamente el procedimiento de probar
que se da la implicación lógica.
Regla de Inferencia
Diremos que la proposición Q se infiere de las proposiciones P1 , P2 , . . . , Pn si Q es
verdad cuando todas las Pi , i = 1, 2, . . . , n lo sean, es decir, cuando P1 ∧ P2 ∧ • • • ∧Pn ⇒ Q.
Sub-Tema 4: Regla de Inferencia
Significa: Por lo tanto
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
43/76
Reglas de Inferencia mas Usuales
Sub-Tema 5: Reglas de Inferencia más usuales
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
44/76
Reglas de Inferencia mas Usuales
Sub-Tema 5: Reglas de Inferencia más usuales
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
45/76
TEMA 1: RAZONAMIENTOS Y DEMOSTRACIONES
Demostraciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
46/76
Teorema
Consiste en una proposición P , llamada hipótesis y otra
proposición Q que será la conclusión.
Corolario
Es un teorema que se deduce inmediatamente de otro teorema.
Lema
Es un teorema que no tiene especial interés en si mismo peroque es útil para probar algún otro teorema.
Sub-Tema 6: Teorema Sub-Tema 7: Corolario Sub-Tema 8: Lema Sub-Tema 9: Demostración
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
47/76
Demostración
Es un razonamiento que establece la veracidad de un teorema.
Sub-Tema 6: Teorema Sub-Tema 7: Corolario Sub-Tema 8: Lema Sub-Tema 9: Demostración
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
48/76
Lógica de Predicados
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
49/76
Definiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
50/76
El calculo proposicional no es suficientemente fuerte para hacer todas
las afirmaciones que se necesitan en matemáticas
Afirmaciones como “x = 5” ´o “x > y” no son proposiciones ya que
no son necesariamente verdaderas o falsas. Sin embargo, asignando
valores concretos a las variables x e y, las afirmaciones anteriores son
susceptibles de ser verdaderas o falsas, es decir, se convierten en
proposiciones.
En castellano también ocurren situaciones similares:
Ella es alta y rubia.
El vive en el campo.
Ella, el y el campo se utilizan como variables,
x es alta y rubia.
x vive en y
Definiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
51/76
Predicado
Es una afirmación que expresa una propiedad de un objeto o unarelación entre objetos. Estas afirmaciones se hacen verdaderas o falsas
cuando se reemplazan las variables (objetos) por valores específicos.
Definiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
52/76
Universo del Discurso
Llamaremos de esta forma al conjunto al cual pertenecen los valores quepuedan tomar las variables. Lo notaremos por U y lo nombraremos por
conjunto universal o, simplemente, universo. Debe contener, al menos, un
elemento.
Definiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
53/76
Predicados y Proposiciones
Si p(x1 , x2 , . . . , xn ) es un predicado constante con n variables y
asignamos los valores c1 , c2 , . . . , cn a cada una de ellas, el resultado es la
proposición p(c1 , c2 , . . . , cn ).
Para transformar un predicado en proposición, cada variable del predicado
debe estar “ligada”.
Definiciones
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
54/76
Cuantificadores
C ifi d
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
55/76
Otra forma de ligar las variables individuales es cuantificarlas.
Cuantificador Universal
Si p(x) es un predicado cuya variable es x, entonces la afirmación
“para todo x, p(x)”
es una proposición en la cual se dice que la variable x esta universalmente cuantificada.
La frase “para todo” se simboliza con ∀, símbolo que recibe el nombre de “cuantificador universal”.
Así pues, “para todo x, p(x)” se escribe “ ∀x, p(x)”. El símbolo ∀x puede interpretarse
también como: “para cada x”, “para cualquier x” y “para x arbitrario”.
Cuantificadores
C tifi d
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
56/76
Valor de Verdad del Cuantificador Universal
Sea p(x) un predicado cuya variable x toma valores en un universo del discurso U .
∀x, p(x) es verdad si el predicado p(x) es una proposición verdadera para todos los valores de xen el universo U.
∀x, p(x) es falsa si hay, al menos, un valor de x en U para el cual el predicado p(x) sea una
proposición falsa.
Cuantificadores
C tifi d
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
57/76
Cuantificador Existencial
Si p(x) es un predicado cuya variable es x, entonces la afirmación
“existe un x tal que p(x)”
es una proposición en la que diremos que la variable x está existencialmente
cuantificada.
La frase “existe [al menos]” se simboliza con ∃, símbolo que recibe el nombre de
cuantificador existencial.
Por tanto, “existe un x, tal que p(x)” se escribe “∃x : p(x)” y puede leerse
también como “para algún x, p(x)” o “existe, al menos, un x, tal que p(x)”.
Cuantificadores
C antificadores
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
58/76
Valor de Verdad del Cuantificador Existencial
Sea p(x) un predicado de variable x que toma valores en un universo del discurso U .
∃x : p(x) es verdadera, si el predicado p(x) es una proposición verdadera para, al menos, uno de losvalores de x en U.
∃x : p(x) es falsa, si el predicado p(x) es una proposición falsa para todos los valores de x en U.
Cuantificadores
Cuantificadores
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
59/76
Valores de verdad de los cuantificadores
Cuantificadores
Cuantificadores
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
60/76
Alcance de un Cuantificador
En una expresión ∀x [p(x) . . .] o ∃x : [p(x) . . .], la porción de la expresión a la
que se aplica ∀x o ∃x se llama alcance del cuantificador y se indicara entrecorchetes a menos que sea evidente.
Cuantificadores
Cuantificadores
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
61/76
Leyes de De Morgan Generalizadas
Cuantificadores
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
62/76
TEMA 1: RAZONAMIENTOS Y DEMOSTRACIONES
Razonamientos y Cuantificadores
Sub-Tema 10: Razonamientos y Cuantificadores
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
63/76
En casi todos los teoremas matemáticos aparecen de
forma natural los predicados y los cuantificadores, así
pues si queremos utilizar el procedimiento lógico
aprendido en los razonamientos para demostrar este tipode teoremas, habrá que utilizar proposiciones
cuantificadas en los razonamientos.
Sub-Tema 10: Razonamientos y Cuantificadores
Sub-Tema 11: Definiciones matemáticas
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
64/76
Definiciones Matemáticas
En las definiciones, y únicamente en las definiciones, un condicional puede leerse e
interpretarse correctamente como un bicondicional.
Sub Tema 11: Definiciones matemáticas
Sub-Tema 11: Definiciones matemáticas
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
65/76
Definiciones Matemáticas
Sub Tema 11: Definiciones matemáticas
Sub-Tema 12: Regla de Particularización
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
66/76
Regla de Particularización
Si un predicado se transforma en una proposición verdadera para
todos los elementos de un universo del discurso, entonces es una
proposición verdadera, en particular, para cada elemento del
universo.
Obsérvese que lo que decimos es que si ∀x, p(x) es verdad,
entonces p(a) es verdad para cada a en el universo del
discurso.
Sub Tema 12: Regla de Particularización
Sub-Tema 13: Regla de Generalización
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
67/76
Regla de Generalización
Si un predicado es una proposición verdadera para cualquier
elemento elegido de forma arbitraria en nuestro universo del
discurso, entonces es verdadera para todos los elementos del
universo.
Obsérvese que aquí decimos que si p(a) es verdadera, siendo aun elemento arbitrario del universo, entonces ∀x, p(x) es
verdad.
Obsérvese también que un elemento arbitrario o genérico del
universo ha de ser uno que tenga todas las características comunesde los elementos del universo de esta forma lo que probemos o
hagamos para a será aplicable a todos los elementos.
Sub Tema 13: Regla de Generalización
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
68/76
TEMA 1: RAZONAMIENTOS Y DEMOSTRACIONES
Métodos de demostración
Sub-Tema 14: Métodos de demostración
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
69/76
Una demostración era un razonamiento que establece la
veracidad de un teorema, es decir demostrar un teorema
equivale a probar que la proposición condicional P → Qes una tautología o lo que es igual probar que P⇒ Q.
Sub-Tema 15: Demostración Vacía
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
70/76
Demostración Vacía
Una demostración de este tipo se construye estableciendo que el valor de verdad
de la hipótesis P es falso.
En efecto, si podemos establecer la falsedad de P , entonces el condicional P
→ Q siempre es verdad independientemente del valor de verdad de la
conclusión Q, luego P → Q es una tautología y, consecuentemente, P ⇒ Q
Aunque parece que tiene poco valor, este método de demostración es importante
para establecer limitaciones o estudiar casos especiales.
Demostrar que es Falso
Sub-Tema 16: Demostración Trivial
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
71/76
Demostración Trivial
Se construye una demostración de este tipo, probando que el valor verdadero
de la conclusión Q es verdad.
Si es posible establecer la veracidad de la conclusión Q, entonces el
condicional P −→ Q será una tautología independientemente del valor de
verdad que tenga la hipótesis, luego P =⇒ Q, la demostración es correcta y el
teorema cierto.
Al igual que la demostración vacía, la demostración trivial tiene una aplicación
limitada y aun así es bastante importante. Se utiliza frecuentemente para
establecer casos especiales de afirmaciones.
Demostrar que es Verdadero
Sub-Tema 17: Demostración Directa
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
72/76
Demostración Directa
Una demostración de este tipo muestra que la verdad dela conclusión Q, se sigue lógicamente de la verdad de
la hipótesis P . La demostración empieza asumiendo
que P es verdad para después, utilizando cualquier
información disponible, así como teoremas probados conanterioridad, probar que Q es verdad. Asumir que
es Verdadero
Información disponible, así
como teoremas probados
Probar que es
Verdadero
Sub-Tema 18: Demostración por la Contra recíproca
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
73/76
Demostración por la Contra recíproca
La demostración de un teorema se dice que es por la contra reciproca cuando
suponiendo que la conclusión, Q, es falsa y utilizando la hipótesis P y otrosteoremas y equivalencias lógicas establecidas previamente, se concluye que P es
falso.
Está basada en la equivalencia lógica entre una proposición condicional y su
contra recíproca,
P → Q ¬Q → ¬P
Por lo tanto, si probamos que ¬Q → ¬P es una tautología, habremos
probado que P → Q también lo es, luego P⇒ Q.
Asumir que es Falso
Utilizando la hipótesis P y otros teoremas y
equivalencias lógicas
Probar que es Falso
Es una
Tautologia
Entonces es unaTautologia
Sub-Tema 19: Demostración por Contradicción
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
74/76
Demostración por Contradicción
La demostración de un teorema diremos que es por contradicción cuando suponiendo que
la conclusión, Q, es falsa y utilizando la hipótesis P , y otros teoremas y equivalencias
lógicas establecidas previamente, se llega a una contradicción.
Esta basada en la equivalencia lógica conocida como reducción al absurdo, es por ello
que este método de demostración es conocido, también, como demostración por reducción
al absurdo.
P → Q (P ∧ ¬Q) → C
Donde C es una contradicción. Por lo tanto, si probamos que (P ∧ ¬Q) → C es una
tautología tendremos que P → Q también lo es y, consecuentemente, P ⇒ Q.
Asumir que es Falso
Utilizando la hipótesis P y otros teoremas y
equivalencias lógicas
Se llega a una Contradicción
Es una
TautologiaEntonces es una
Tautologia
Sub-Tema 20: Búsqueda de contraejemplos
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
75/76
Búsqueda de contraejemplos
Este tipo de demostración, íntimamente relacionada con el cuantificador
universal, aparece cuando se quiere probar que una proposición del tipo ∀x, p(x)
es falsa. Normalmente diremos que se refuta la proposición ∀x, p(x).
En efecto, ∀x, p(x) será falsa cuando exista, al menos, un elemento a en el
universo del discurso para el cual p(a) sea una proposición falsa. Hemosencontrado, pues, un ejemplo que contradice el que ∀x, p(x) sea verdad por lo
cual le llamaremos contraejemplo.
En el caso de un teorema el planteamiento seria como sigue: ∀x [p(x) → q(x)]
es falso si existe un elemento a en el universo para el cual la proposición
condicional p(a) → q(a) sea falsa, es decir tal que p(a) sea verdad y, sinembargo, q(a) sea falsa.
Sub-Tema 21: Demostración por inducción matemática
8/17/2019 001-Tema 1 Razonamientos y Demostraciones v17
76/76
Demostración por inducción matemática
La técnica de demostración por inducción matemática es utilizada para probar
razonamientos de la forma ∀n [p(n) → q(n)], donde el universo del discurso es el
conjunto de los números naturales (N).
La demostración por la técnica de inducción matemática consiste de tres pasos:
1) Paso base: se demuestra la validez de la proposición p evaluada en el
caso base, donde dicho caso base puede ser un cero o un uno dependiendo
del punto de partida o condición inicial del problema que se estádemostrando.
2) Paso inductivo (o hipótesis de inducción): se asume que es verdadera la
proposición p evaluada en un número natural k.
3) Paso post-inductivo: apoyados en la suposición de validez de la
proposición p(k) se demuestra la validez de la proposición p(k + 1), es
decir, p(k) → p(k + 1).
Cuando se cumplen los tres casos de la técnica por inducción matemática, entonces se
ha demostrado que la proposición p(n) es verdadero para todo número natural n, es
decir se ha demostrado que ∀n p(n) es verdadero
Top Related