Download - LÓGICA MATEMÁTICA
Á L G E B R A
LÓGICA MATEMÁTICA
LÓGICA PROPOSICIONAL
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.
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.
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
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.
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
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
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
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 “
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
TAUTOLOGÍA
Definición
• Una proposición compuesta que siempre es VERDADERA, es una tautología.
• Una tautología la denotamos por I.
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
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
CONTRADICCIÓN
• Definición
Una proposición que siempre es FALSA, es una contradicción. Una contradicción la denotamos por 0.
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
CONTINGENCIA
• Definición
• Una proposición que no es tautología ni contradicción se llama contingencia.
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
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Identidad
a) p ∧ V ⇔ p
b) p ∨ F ⇔ p
c) p ∧ F⇔ F
d) p ∨ V ⇔ V
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Idempotencia
a) p ∧ p ⇔ p
b) p ∨ p ⇔ p
• Involución
a) ∼ (∼ p) ⇔ p
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Complemento
a) ~ F⇔ V
b) ~ V ⇔ F
c) p ∧ (~ p )⇔ F
d) p ∨ (~ p )⇔ V
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
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)
LEYES FUNDAMENTALES DEL
ÁLGEBRA DE PROPOSICIONES
• Una ley fundamental, muy importante es:
( p ⇒ q) ⇔ ((~ p) ∨ q)
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)
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
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)
LÓGICA FUNCIONAL
ÁLGEBRA
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.
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”
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.
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):
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.
LEYES DE CUANTIFICADORES
• Se cumple:
• 1) ~ [∀ x ∈ D : p(x)]⇔ ∃ x ∈ D : ~ p(x)
• 2) ~ [∃ x ∈ D : p(x)]⇔∀ x ∈ D : ~ p(x)