INTRODUCCION A LA LOGICA MATEMATICA
Con esta introducción de la Lógica pretendemos estudiar ciertos principios importantes para el estudio de la matemática.
Definicion. Una proposición es una oración declarativa completa con un significado bien definido y de la cual podemos decir que es verdadera o falsa.
Por ejemplo las oraciones: “el oro es un metal precioso”, 2+3=5, 2+3=8 son proposiciones.
Consideraremos proposiciones en su forma más simple (atómicas) y las proposiciones compuestas, como aquellas formadas por proposiciones simples mediante términos de enlace. Una proposición simple es una proposición sin términos
de enlace. Los términos de enlace se usan para formar nuevas proposiciones a partir de proposiciones atómicas.
Por ejemplo, consideremos las siguientes proposiciones atómicas,
Hoy es Domingo.
No hay clase.
Mediante un término de enlace podemos formar una nueva proposición compuesta. Por ejemplo
Hoy es Domingo y no hay clase
El termino de enlace que hemos utilizado es “y”. Cuando tenemos una proposición molecular es importante determinar las proposiciones atómicas que la componen.
TERMINOS DE ENLACE
Los términos de enlace entre proposiciones que utilizaremos son: ¿ y À, ¿ o À,¿ no À, ¿ si..., entonces À .
Simbólicamente representaremos estos términos de enlace por ∧, ∨, ∼, =⇒, respectivamente.
Claramente al utilizar un término de enlace entre dos o más proposiciones atómicas obtendremos proposiciones
Compuestas.
Observemos que el termino de enlace ¿ no À actúa sobre una sola proposición, mientras que los demás términos de enlaces actúan sobre dos proposiciones.
Algunos ejemplos en las que utilizan los términos de enlace son los siguientes
Si estamos en diciembre entonces pronto llegara la Navidad
Hoy es lunes y hay clases
El viento arrasara las nubes o lloverá con seguridad.
No tendremos clase en el día de hoy.
Vamos a simbolizar cualquier proposición con las letras p, q, r, s, t, etc..
La regla fundamental de la lógica es,
1La ley del medio excluido. Toda proposición debe ser verdadera o falsa,
pero no puede ser ambas cosas, ni puede ser ninguna de las dos cosas.
Vamos a comenzar con algunas proposiciones cuyo valor de verdad es intuitivamente claro.
1. Si p no es cierta, claramente ∼p es verdadera. Si p es cierta entonces ∼p es falsa. (La ley del medio excluido).
2. p ∧ q es verdadera si y solo si ambas son verdaderas.
3. p ∨ q es verdadera si y solo si p es verdadera o q es verdadera.
4. La proposición p ⇒ q (p implica q) se conoce como proposición condicional; a p se le llama antecedente y a q el consecuente.
Se acostumbra con esta implicación decir que es condición suficiente para q;
q es condición necesaria para p.
También podemos decir que p es la hipótesis y q es la conclusión.
Diremos que p ⇒ q es falsa cuando ´únicamente en el caso donde p es verdadera y q es falsa.
La proposición q ⇒ p se le llama la reciproca de la proposición p ⇒ q.
Es necesario que nos demos cuenta de que p ⇒ q no garantiza que q ⇒ p.
Por ejemplo,
x = 3 =⇒ x
2
= 9
es verdadera, pero la reciproca
x
2
= 9 =⇒ x = 3
es falsa.
PROPOSICION BICONDICIONAL
Es la proposición expresada simbólicamente por
p ⇐⇒ q
es una combinación de las dos proposiciones condicionales p =⇒ q y q =⇒ p. El símbolo de enlace ⇐⇒ se lee “si y
Solo si “o “necesario y suficiente”
La proposición p ⇐⇒ q Sera verdadera si p y q son verdaderas o p y q son falsas.
Por ejemplo,
Un trianguló tiene tres lados iguales ⇐⇒el trianguló es equilátero.
INFERENCIA LOGICA
La idea de inferencia se puede expresar diciendo que de proposiciones verdaderas (premisas verdaderas) se obtienen
solo conclusiones que son verdaderas. Es decir de premisas verdaderas, entonces las conclusiones que se derivan de
Ellas lógicamente, han de ser verdaderas.
Se dice q es consecuencia lógica de p, (p ⇒ q) si p verdadera implica q es verdadera
Se dice que un razonamiento es válido si la conclusión es consecuencia lógica de las premisas.
2REGLAS DE INFERENCIA
Cada una de las premisas que se dan a continuación se consideran verdaderas y por lo tanto sus conclusiones
también son verdaderas.
Regla 1 (PP) Regla 2 (TT)
(Modus Ponendo Ponens) (Modus Tollendo Tollens)
P1: p =⇒ q
P2: p
Conclusión: q
P1: p =⇒ q
P2:∼ q
Conclusión : ∼ p
Regla 3 (TP)
Modus Tollendo Ponens
P1: p ∨ q
P2:∼ p
Conclusion: q
P1: p ∨ q
P2:∼ q
Conclusion : p
Regla 4 (S)
Simplificacion
P1: p ∧ q
Conclusion: p
P1: p ∧ q
Conclusion: q
Regla 5 (DN)
Doble negación
P1:∼ (∼ p)
Conclusión: p
Regla 6 (A)
Ley de Adjunción
P1: p
P2: q
Conclusion: p ∧ q
P1: q
P2: p
Conclusion : q ∧ p
Regla 7 (HS) Regla 8 (DP)
Silogismo Hipotético Simplificacion disyuntiva
P1: p ⇒ q
P2: q ⇒ r
Conclusion : p ⇒ r
P1: p ∨ p
Conclusion : p
Regla 9 (De Morgans)
P1:∼ (p ∧ q)
Conclusion: ∼ p∨ ∼ q
P1:∼ (p ∨ q)
Conclusión: ∼ p∧ ∼ q
Regla 10
Leyes conmutativas
P1: p ∧ q
Conclusion: q ∧ q
P1: p ∨ q
Conclusión: q ∨ p
:
3PROPOSICION ABIERTA
Una proposición abierta P(x) es un enunciado sobre una variable x que se convierte en una proposición cada vez que
la variable x se sustituye por un valor particular xo.
Ejemplo 1 P(x) : 2x + 3 ≤ 0 es una proposición abierta. Se convierte en proposición para cada número definido xo.
En particular P(−2) es cierta mientras que P(0) es falsa.
Ejemplo 2 A(x) : x
2
≤ 0. Si suponemos que x toma valores reales, claramente A(x0) es falsa para todo x0 = 0 6 ,
mientras que P(0) es verdadera.
CUANTIFICADORES LOGICOS
Frecuentemente las proposiciones abiertas se utilizan con ciertas expresiones llamadas cuantificadores, con los cuales
se determina el valor de verdad de la proposición resultante.Los siguientes serán los cuantificadores que usaremos:
1. Cuantificador universal, para todo x, representado simbólicamente por ∀x.
2. Cuantificador existencial, para algún x, representado simbólicamente por ∃x.
3. Cuantificador de existencia y unicidad, existe un ´único x, representado simbólicamente por ∃!x.
Observaci´on 1. La frase “para cada x” se usa en el mismo sentido que la frase “para todo x”.
Observación 2. Si una propiedad es compartida por todos los elementos de un conjunto B, escribiremos:
“Todo x en B tiene la propiedad P ”, Simbólicamente, ∀x ∈ C, P(x)
Observación 3. Si una propiedad es compartida por uno o varios elementos de un conjunto C, escribiremos:
“Algún x en C tiene la propiedad P ”, Simbólicamente, ∃x ∈ C, P(x)
Ejemplo 1. ∀x(x
2
≥ 0) es una proposición verdadera.
Ejemplo 2. Para todo x existe algún y tal que x + y = 0, simbólicamente esta proposición es
(∀x) (∃y)(x + y = 0)
Esta proposici´on es verdadera, ya que dado x arbitrario tomamos y = −x.
Observaci´on 3. Hay que tener cuidado con expresiones del tipo (∀x) (∃y) y (∃y) (∀x) las cuales no tienen el mismo
significado. Por ejemplo si H representa los seres humanos, podríamos decir:
Para todo x ∈ H existe y ∈ H tal que y es la madre de x. Simbólicamente se representa por
(∀x ∈ H) (∃y ∈ H)(y = m(x))
Ahora estudiemos la proposición
Existe y ∈ H tal que para todo x ∈ H, y es la madre x. Simbólicamente se representa por
(∃y ∈ H) (∀x ∈ H) (y = m(x))
Observemos que la primera proposición es cierta mientras que la segunda es falsa.
Observación 4. La negación de la proposición “Todo x en B tiene la propiedad P ”, simbólicamente ∼ (∀x ∈
C, P(x)), es “Existe algún x en B que no tiene la propiedad P ”, Simbólicamente, ∃x ∈ C, ∼ P(x).
Observación 5. La negación de la proposición “Existe x en C tiene la propiedad P ”, simbólicamente ∼ (∃x ∈
C, P(x)), es “Para todo x en C, x que no tiene la propiedad P ”, Simbólicamente, ∀x ∈ C, ∼ P(x).
Por ejemplo, las negaciones de las siguientes proposiciones son:
4Todos los hombres son mortales. Su negación es Algún hombre es inmortal.
Algún hombre es inmortal Su negación es Todos los hombres son mortales.
Métodos de demostración
Demostración directa
Tratamos de demostrar lo siguiente:
Si H entonces T
Donde, H es la hipótesis y T es la conclusión.
La demostración directa consiste en comenzar con algo conocido y proceder paso por paso usando las leyes de
Inferencia y de otros resultados conocidos hasta llegar al resultado esperado. Podemos decir que una demostración
directa es una cadena de proposiciones de la forma:
Po : H (Hipótesis)
P1 : H =⇒ q1
P2 : q1 =⇒ q2
.
.
.
Pn : qn−1 =⇒ qn
Pn+1 : qn =⇒ T (conclusion)
Las reglas de inferencia garantizan la validez de la conclusi´on T.
Ejemplo. Demostrar que la multiplicación de un numero entero par por un entero impar es un entero par. Es de la
Forma Si H entonces T, esto es, si m es par y n es impar entonces mn es par.
Su demostración directa es como sigue:
Po : m es par y n es impar
P1 : m es par y n es impar =⇒ m = 2r, y n = 2s + 1 para enteros ´únicos r y s.
P2 : m = 2r, y n = 2s + 1 =⇒ mn = 2r(2s + 1)
P3 : mn = 2r(2s + 1) =⇒ mn = 2[r(2s + 1)]
P4 : mn = 2[r(2s + 1)] =⇒ mn es par
T : mn es par (la conclusión a la queríamos llegar)
Observemos que hemos utilizado repetidamente la regla de inferencia 1.
Demostración indirecta
Algunas veces la demostración directa tiene algunas dificultades y se opta por establecer la demostración utilizando una formula equivalente. Mencionaremos dos tipos de demostración indirecta.
51. Demostración por la contrarec´iproca conocida también como demostración por contraposición. Utilizamos la
Propiedad
(H =⇒ T) ⇐⇒ (∼ T =⇒∼ H)
Consiste en demostrar la validez de ∼ T =⇒∼ H usando la demostración directa; la equivalencia implicara la
Validez de H =⇒ T.
Ejemplo. Para que el producto de dos números enteros sea par es necesario que por lo menos uno de los dos sea
par.
Escribiendo en la forma H =⇒ T tenemos que si mn es un entero par, entonces m es par o n es par.
Teniendo en cuenta que ∼ (p ∨ q) ⇐⇒∼ p∧ ∼ q (Ley de Morgans). La contra-reciproca se leerá:
Si m es impar y n es impar entonces mn es impar.
La demostración directa es como sigue:
m = 2s + 1 y n = 2t + 1 =⇒ mn = (2s + 1)(2t + 1) = 2h + 1 donde h = 2ts + t + s.
Entonces queda demostrado que mn es impar.
Demostración por contradicción
Este tipo de demostración tiene su sustentación en las siguientes equivalencias lógicas
1. ∼ (H =⇒ T) ⇐⇒ H∧ ∼ T
2. H∧ ∼ T =⇒ R∧ ∼ R ⇐⇒ H =⇒ T
El método consiste en suponer que el contenido del teorema es falso. Según 1, esto significa que siendo la hipótesis
H verdadera la conclusión T puede ser falsa. En todo razonamiento las premisas se toman como verdaderas. Por
eso se escribe el supuesto H∧ ∼ T.
Este supuesto tiene como consecuencia lógica la contradicción R∧ ∼ R y según 2 esto implicaría que H =⇒ T es
Verdadera, lo cual finaliza la demostración.
Ejemplo. Demostrar que el cuadrado de la razón de dos enteros no puede ser exactamente 2.
La proposición dice que si a y b son dos enteros entonces (
a
b
)
2
= 2 6 . Para demostrar esta proposición demostraremos
que su negativa es falsa. En consecuencia tenemos que demostrar que si a y b son dos enteros entonces (
a
b
)
2
= 2 no
es posible.
Vamos a suponer sin pérdida de generalidad que a y b no tienen factores comunes. Vamos a suponer que la negación
de la proposición es cierta es decir que
(
a
b
)
2
= 2
Entonces
a
2
= 2b
2
.
El segundo termino implica que a
2
es un entero par y por la demostración anterior a es par. O sea
a = 2s
donde s es algún entero. Substituyendo el valor de a obtenemos 4s
2
= 2b
2
, lo cual implica que b
2
Es par y por lo
Tanto b es par, esto es, b = 2t. El hecho que a = 2s y b = 2t significa que a y b tiene como factor común 2, en contra
de la suposición de que a/b no tiene factores comunes. Consecuentemente no es cierto que (
a
b
)
2
= 2. Esto completa
la demostración.
Demostración por disyunción de casos
Aplicando la regla de inferencias podemos mostrar la validez del siguiente razonamiento
6P1 : p ∨ q
P2 : p =⇒ r
P3 : q =⇒ r
Conclusion: r
Hacemos uso de este razonamiento en teoremas cuya hipótesis puede partirse en casos mutuamente excluyentes, cada
uno de los cuales conduce igualmente a la conclusión prevista.
Ejemplo. El cuadrado de todo entero, o es un múltiplo de 4 o difiere de un múltiplo de 4 en 1. Esto es,
n entero =⇒ n
2
= 4t o n
2
= 4t + 1 para algún entero t.
Puesto que n es entero la separamos en dos casos:
n es par o n es impar (p ∨ q)
(i) Si n es par ⇒ n = 2s para algún entero s. =⇒ n
2
= 4s
2
, es decir n
2
es múltiplo de 4.
(ii) Si n es impar ⇒ n = 2t + 1 para algún entero t. =⇒ n
2
= 4t
2
+ 4t + 1 = 4u + 1, es decir n
2
difiere de un
múltiplo de 4. en 1.
Demostración por contraejemplo
Cuando hemos probado la validez de la implicación p =⇒ q, frecuentemente se trata de investigar la validez de la
Reciproca q =⇒ p. Empezamos analizando casos particulares que satisfagan la hipótesis q y confrontamos la validez o
No de la conclusión p. Si damos un ejemplo donde la conclusión resulta falsa, tenemos que q∧ ∼ p es verdadera. Puesto
Que ∼ (q =⇒ p) ⇐⇒ q∧ ∼ p se sigue por las reglas de inferencia que ∼ (q =⇒ p) es verdadera y por lo tanto q =⇒ p
es falsa.
El determinar la falsedad de q =⇒ p mediante un caso particular se denomina un contraejemplo.
Ejemplo. Si n es un entero primo entonces n es impar. Es una implicación falsa por que n = 2 es primo y sin
Embargo es par. En este caso, n = 2 es un contraejemplo.
No hay comentarios:
Publicar un comentario