LÓGICA MATEMÁTICA
-
Upload
daniela-mansilla -
Category
Documents
-
view
33 -
download
0
description
Transcript of LÓGICA MATEMÁTICA
![Page 1: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/1.jpg)
Á L G E B R A
LÓGICA MATEMÁTICA
![Page 2: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/2.jpg)
LÓGICA PROPOSICIONAL
![Page 3: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/3.jpg)
LÓGICA PROPOSICIONAL
• Estudiaremos brevemente un lenguaje no contradictorio ni ambivalente que nos permitirá introducirnos a la Matemática: la Lógica Matemática, que estudia las leyes que regulan el razonamiento.
• En la lógica proposicional consideraremos dos elementos básicos: Proposiciones, Conectivos.
![Page 4: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/4.jpg)
PROPOSICIONES.
• Son “frases” sobre las cuales podemos decidir, unívocamente, sobre la verdad(V) o falsedad(F) de ellas.
• Así entonces, una proposición es una frase que es V o F, no existiendo la posibilidad de obtener ambas decisiones conjuntamente.
• Las proposiciones las denotamos por letras minúsculas p, q, r, etc. , que resumirán, en si mismo, el significado particular que tengan al interior de una situación concreta.
![Page 5: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/5.jpg)
PROPOSICIÓN
• EJEMPLOS.1) “p” resumirá, al interior de éste ejemplo, a la proposición : “Hoy es Martes 10 de Mayo“, y denotamos p: “Hoy es Martes 10 de Mayo”2) Las siguientes “frases” son proposiciones:• q : x + 4 = 9 y x = 5 (es V)• r: Si x es un número real, entonces su cuadrado es
no negativo (es V)• Observación :
No son proposiciones los interrogativos y los imperativos
![Page 6: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/6.jpg)
CONECTIVOS
• Símbolos que, junto con las proposiciones básicas, nos permiten crear nuevas proposiciones, son:
• ~ : se lee “no”
• ∧ : se lee “y”
• ∨ : se lee “ o”
• ⇒ : se lee “ ...implica ...” ó “si, ....entonces, ......”
• ⇔ : se lee “ ... equivalente con ....”
• Observación:
• El conectivo “ ~ ” se usa antes de una proposición, y los restantes conectivos se usan entre dos proposiciones.
![Page 7: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/7.jpg)
CONECTIVOS
• Ejemplo :
Si p, q, r son proposiciones, entonces también son proposiciones:
1. ~ p
2. p ∧ q
3. p ∨ q
4. p ⇒ q
5. p ⇔ q
6. p ∧ (q ∨ r)
7. [(~ p) ∧ (q ∨ r)]⇒ q
![Page 8: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/8.jpg)
TABLAS DE VERDAD
• Las proposiciones compuestas, es decir, aquellas que contienen al menos un conectivo tienen, naturalmente, un valor veritativo, y para las proposiciones compuestas básicas ese valor veritativo lo damos en las siguientes “tablas de verdad”:
p q �⋀� � ∨ � � ⇒ � � ⇔ �
V V V V V V
V F F V F F
F V F V V F
F F F F V V
![Page 9: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/9.jpg)
TABLAS DE VERDAD
• Tabla de verdad de la negación (∼)
Dada la proposición básica " p" , existe la negación de ella, denotada ~ p , que se lee “no p”, proposición que tiene la siguiente tabla de verdad.
p ~ p
V F
F V
![Page 10: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/10.jpg)
TABLAS DE VERDAD
• Observación:
Es claro que el valor veritativo de ∼ p es el contrario de p
Por ejemplo, si " p" es : p : “ Hoy llueve “, entonces ~ p es : ~ p : “ Hoy no llueve “
![Page 11: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/11.jpg)
TABLAS DE VERDAD
• Determine el valor veritativo de:
~ (p ∧ q)⇔[(~ p)∨ (~ q)]
• Solución :
• Su tabla de verdad es:
p q p ∧∧∧∧ q ~ ( p ∧∧∧∧ q) ~ p ~ q (~ p) ∨∨∨∨ (~ q) ~ (p ∧∧∧∧ q)⇔⇔⇔⇔[(~ p)∨∨∨∨ (~ q)]
V V V F F F F V
V F F V F V V V
F V F V V F V V
F F F V V V V V
![Page 12: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/12.jpg)
TAUTOLOGÍA
Definición
• Una proposición compuesta que siempre es VERDADERA, es una tautología.
• Una tautología la denotamos por I.
![Page 13: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/13.jpg)
TAUTOLOGÍA
Ejemplo :
• Demuestre que p ∨ (~ p) es tautología.
• Demostración:
Debemos encontrar su tabla de verdad y verificar que siempre es verdadera:
p ~ p p ∨∨∨∨ (~ p)
V F V
F V V
![Page 14: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/14.jpg)
TAUTOLOGÍA
• Notamos que si “p” significa, “Esta sala tiene 40 alumnos” entonces p ∨ (~ p) significa “Esta sala tiene 40 alumnos o no tiene 40 alumnos”, lo que siempre verdadero.
A EJERCITAR!
1. Demuestre que: ~ (~ p) ⇔ p es tautología.
2. Demuestre que: {p ⇒[(q ∧ (~ q)]}⇒ (~ p) es tautología
![Page 15: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/15.jpg)
CONTRADICCIÓN
• Definición
Una proposición que siempre es FALSA, es una contradicción. Una contradicción la denotamos por 0.
![Page 16: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/16.jpg)
CONTRADICCIÓN.
• Ejemplo.
Demuestre que p ∧ (~ p) es una contradicción.
• Demostración
Debemos encontrar la tabla de verdad de la proposición y verificar que siempre es falsa
p ~ p p ∧∧∧∧ (~ p)
V F F
F V F
![Page 17: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/17.jpg)
CONTINGENCIA
• Definición
• Una proposición que no es tautología ni contradicción se llama contingencia.
![Page 18: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/18.jpg)
CONTINGENCIA.
• Ejemplo:
• Demuestre que [p ∧ (q ∨ r)]⇒ r es una contingencia
• Concluimos que [p ∧ (q ∨ r)]⇒ r es una contingencia.
p q r q ∨∨∨∨ r p ∧∧∧∧ (q ∨∨∨∨ r) [p ∧∧∧∧ (q ∨∨∨∨ r)]⇒⇒⇒⇒ r
V V V V V V
V V F V V F
V F V V V V
V F F F F V
F V V V F V
F V F V F V
F F V V F V
F F F F F V
![Page 19: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/19.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Identidad
a) p ∧ V ⇔ p
b) p ∨ F ⇔ p
c) p ∧ F⇔ F
d) p ∨ V ⇔ V
![Page 20: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/20.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Idempotencia
a) p ∧ p ⇔ p
b) p ∨ p ⇔ p
• Involución
a) ∼ (∼ p) ⇔ p
![Page 21: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/21.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Complemento
a) ~ F⇔ V
b) ~ V ⇔ F
c) p ∧ (~ p )⇔ F
d) p ∨ (~ p )⇔ V
![Page 22: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/22.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Conmutatividad
a) p ∧ q ⇔ q ∧ p
b) p ∨ q ⇔ q ∨ p
• Asociatividad
a) p ∧ (q ∧ r)⇔ ( p ∧ q) ∧ r
b) p ∨ (q ∨ r)⇔ ( p ∨ q) ∨ r
![Page 23: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/23.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Distributividad
a) p ∧ (q ∨ r)⇔ ( p ∧ q) ∨ ( p ∧ r)
b) p ∨ (q ∧ r)⇔ ( p ∨ q) ∧ ( p ∨ r)
• De Morgan
a) ~ ( p ∧ q)⇔ (~ p) ∨ (~ q)
b) ~ ( p ∨ q) ⇔ (~ p) ∧ (~ q)
![Page 24: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/24.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Una ley fundamental, muy importante es:
( p ⇒ q) ⇔ ((~ p) ∨ q)
![Page 25: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/25.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Ejemplos:
• 1) Si definimos ∇ y ∆ como:
I. p∇q = (~ p) ∧ (~ q)
II. p∆q = (~ p) ∨ (~ q)
Demuestre, sin usar tablas de verdad que:
a) p∇p ⇔ ~ p
b) p ∧ q ⇔ ~ (p∆q)
c) p ∨ q ⇔ ~ (p∇q)
![Page 26: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/26.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Demostración:
a) p∇p ⇔ (~ p) ∧ (~ p) ⇔ ~ p
b) ~ ( p∆q)⇔ ~ [(~ p) ∨ (~q)]⇔ ~ (~ p) ∧ ~ (~ q)⇔ p ∧ q
c) ~ ( p∇q) ⇔ ~ [(~ p) ∧ (~q)]⇔ ~ (~ p) ∨ ~ (~ q)⇔ p ∨ q
![Page 27: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/27.jpg)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• A TRABAJAR!
Sin usar tablas de verdad
1. Demuestre que: p ∨ [(~ p) ∧ q]⇔ p ∨ q
2. Demuestre que: p⇒ ( p ∨ q) es una tautología
3. Demuestre que: [p ∧ ( p ⇒ q)]⇒ q es una tautología
4. Demuestre, sin usar tablas:
{[( p ∧ q) ∨ r]∧ ~ q}∨ q ⇔ (r ∨ q)
![Page 28: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/28.jpg)
LÓGICA FUNCIONAL
ÁLGEBRA
![Page 29: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/29.jpg)
FUNCIÓN PROPOSICIONAL.
• Podemos observar que la expresión “x < 3”no es una proposición. Sin embargo, se puede considerar como una función proposicional (x es una variable).
• Denotemos por p(x) a “x < 3”y consideremos como dominio de p(x) a R (conjunto de los números reales). Luego, si x = 2 se obtiene p(2) : “2 < 3”que es una proposición con valor de verdad V . En cambio si x = 8 se obtiene p(8) : ”8 < 2”que es una proposición con valor de verdad F.
![Page 30: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/30.jpg)
CUANTIFICADORES
• 2) Anteponiendo a la FP un símbolo que responde a la pregunta ¿Cuántos elementos de D verifican p(x) ?
• Estos símbolos, llamados Cuantificadores, son:
∀ : significa : “todos”
∃ : significa : “algunos”
∃! : significa : “un único”
![Page 31: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/31.jpg)
FUNCIONES PROPOSICIONALES
• Sea D el dominio de una función proposicional p (en general este dominio se da explícitamente o bien se infiere del contexto).
• Un método de hacer de una función proposicional una proposición, es substituyendo elementos de D en p, como vimos. Un segundo método se denomina cuantificación.
![Page 32: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/32.jpg)
CUANTIFICADORES
• Básicamente hay dos formas de cuantificar una función proposicional. La primera es anteceder la función proposicional con “Para todo x en D tal que”. La notación es:
∀ x en D , p(x):
• La segunda es anteceder la función proposicional con “Existe un x en D tal que”. La notación es:
∃ x en D / p(x) ó ∃ x en D tal que p(x):
![Page 33: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/33.jpg)
CUANTIFICADORES
• ∀ se denomina cuantificador universal
• ∃ se denomina cuantificador existencial.
• Observación : El valor de verdad de una función proposicional cuantificada depende del dominio utilizado.
![Page 34: LÓGICA MATEMÁTICA](https://reader033.fdocumento.com/reader033/viewer/2022051100/56d6bd2f1a28ab30168cf7a5/html5/thumbnails/34.jpg)
LEYES DE CUANTIFICADORES
• Se cumple:
• 1) ~ [∀ x ∈ D : p(x)]⇔ ∃ x ∈ D : ~ p(x)
• 2) ~ [∃ x ∈ D : p(x)]⇔∀ x ∈ D : ~ p(x)