Download Matemáticas Discretas, Lógica: Predicados y Cuantificadores

Predicados
Cuantificadores
Preguntas
Matemáticas Discretas, Lógica: Predicados
y Cuantificadores
Prof. Víctor Bravo1
1 Universidad
de los Andes
A-2008
Predicados
Cuantificadores
Preguntas
Licencia de Uso
Copyright (c), 2007. 2008, ULA.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free
Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no
Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section
entitled "GNU Free Documentation License".
Una copia de la licencia puede obtenerse en los siguientes sitios en Internet:
http://www.gnu.org/copyleft/fdl.html
http://www.fsf.org/licensing/licenses/fdl.html
Predicados
Cuantificadores
Agenda
1
Predicados
Tautologías y Contradicciones
Definiciones
2
Cuantificadores
Definiciones
Implicaciones y Equivalencias Lógicas
3
Preguntas
Preguntas
Predicados
Cuantificadores
Tautologías y Contradicciones
Tautologías útiles
Tautologías útiles
Ley del absurdo
Ley de la importación
Ley de la exportación
Ley del silogismo hipotético
Ley de la adjunción
Ley de la simplicación
Modus tollendo pollens
Modus tollendo tollens
Ley de la separación
(p → q ∧ ¬q) → ¬p
(p → (q → r )) → (p ∧ q → r )
(p ∧ q → r ) → (p → (q → r ))
(p → q) ∧ (q → r ) → (p → r )
p∧q →p∧q
p∧q →p
¬p ∧ (p ∨ q) → q
¬q ∧ (p → q) → ¬p
p ∧ (p → q) → p
Preguntas
Predicados
Cuantificadores
Preguntas
Tautologías y Contradicciones
Tipos de elementos en la lógica de Predicados
Constantes
Objetos concretos, formando un universo de discurso, un
conjunto U.
Variables
Objetos genéricos que normalmente denotamos con las letras
x, y, z, . . . y que podrán sustituirse por objetos de U.
Predicados
Cuantificadores
Preguntas
Tautologías y Contradicciones
Predicados
¿Qué es un predicado?
Los predicados son sentencias abiertas, en las que se incluyen
una o más variables. También se les llama función
proposicional.
Estos enunciados no son ni verdaderos ni falsos, si no se
especifican los valores de las variables.
Un predicado se convierte en una proposición cuando todas
las variables que aparecen en él, se remplazan por opciones
permisibles del universo de discurso.
Predicados
Cuantificadores
Preguntas
Tautologías y Contradicciones
Representación de predicados
¿Cómo se representan los predicados?
Los predicados se representan por símbolos del tipo p(x), q(x)
o p(x,y), q(x,y,z), etc.
Por ejemplo:
Si p(x) = x > 100, p(x) se convierte en proposición al sustituir x
por algún número natural.
p(101) es Verdadera.
p(50) es Falsa.
Predicados
Cuantificadores
Definiciones
Definición de cuantificador
¿Qué es un cuantificador?
Otra forma de crear una proposición o de cerrar una función
proposicional abierta, es la Cuantificación.
Una proposición abierta se cierra, si todas sus variables se
cuantifican.
Trataremos con dos tipos de cuantificadores:
1
Existencial
2
Universal
Preguntas
Predicados
Cuantificadores
Preguntas
Definiciones
Cuantificador Existencial
¿Qué es un cuantificador existencial?
Denota que existe “al menos” un elemento x del Universo, para
el cual p(x) es verdadera.
Notación:
∃x p(x) ó
∃x∃y p(x, y ) ↔ ∃x, y p(x, y )
Predicados
Cuantificadores
Preguntas
Definiciones
Cuantificador Existencial
En lenguaje natural decimos...
Formas de expresarlo:
“Hay un x”
“Para algún x”
“Para al menos un x”
“Existe un x tal que”
Resumiendo...
La proposición es Verdadera, si existe al menos un elemento x
del universo tal que p(x) sea verdadera. De lo contrario es
falsa.
Predicados
Cuantificadores
Preguntas
Definiciones
Cuantificador Existencial
Veamos un ejemplo
Si p(x) es “x < 100”
Tenemos...
Cerramos p(x) al escribir ∃x p(x), donde el universo consiste
en todos los números reales.
Importante
Siempre debemos denotar el universo del discurso, ya que
para algunos “universos” la proposición puede ser verdadera y
para otros “universos” es falsa.
Predicados
Cuantificadores
Definiciones
Cuantificador Universal
¿Qué es un cuantificador universal?
Indica que una proposición es Verdadera para todos los
valores de una variable en un “universo” en particular.
p(x) es verdadera, para todos los valores de x en el dominio.
Notación
∀x p(x) ó
∀x, ∀y p(x, y ) ↔ ∀x, y p(x, y )
Preguntas
Predicados
Cuantificadores
Preguntas
Definiciones
Cuantificador Universal
En lenguaje natural decimos...
Formas de expresarlo:
“Para todo x”
“Para cada x”
“Para cualquier x”
“Para todo x y y ”
“Para todo x,y ”
Resumiendo...
La proposición es Verdadera, si para cada reemplazo de x, p(x)
es verdadera. Es falsa, si existe al menos un x para el cual p(x)
es falsa.
Predicados
Cuantificadores
Definiciones
Traducciones de Cuantificadores
Frase de ejemplo
Todo estudiante de la clase de Matemáticas Discretas vive en
Mérida
Traducción:
Se define el dominio: todas las personas
p(x) : estudiante de la clase de Matemáticas Discretas
q(x) : vive en Mérida
Frase lógica
Para todo persona x, si la persona x es un estudiante de la
esta clase, entonces la persona x vive en Mérida.
Preguntas
Predicados
Cuantificadores
Preguntas
Definiciones
Traducciones de Cuantificadores
Lo que se traduce en:
∀x p(x) → q(x)
donde:
x : dominio: de todas las personas
p(x) : es estudiante de la clase de Matemáticas Discretas
q(x) : vive en Mérida
Predicados
Cuantificadores
Preguntas
Definiciones
Ejemplo 2 Cuantificadores
Frase en lenguaje natural
Algún venezolano es medallista olímpico
Se traduce en:
Existe al menos un venezolano que cumple con la condición de
ser medallista olímpico
Las variables
Existe al menos un venezolano x que cumple la condición que
x es medallista olímpico
Predicados
Cuantificadores
Definiciones
Ejemplo 2 Cuantificadores ...continúa...
Predicados
q(x) x es un futbolista
p(x) x es venezolano
Construyamos la proposición
El dominio es de todas las personas, entonces:
∃x(p(x) ∧ q(x))
Preguntas
Predicados
Cuantificadores
Preguntas
Implicaciones y Equivalencias Lógicas
¿Como funcionan las tautologías y contradicciones?
Si la implicación lógica p(x) → q(x) es verdadera para cada x
del universo, entonces se escribe:
Implicación
∀[p(x) → q(x)]
y se dice que p(x) implica lógicamente a q(x)
Predicados
Cuantificadores
Preguntas
Implicaciones y Equivalencias Lógicas
Equivalencias lógicas
Dos proposiciones p(x) y q(x) son lógicamente equivalente, si
se escribe:
Equivalencia
∀x[p(x) ↔ q(x)]
Cuando la bicondicional p(x) ↔ q(x) es verdadera para cada x
del universo.
Predicados
Cuantificadores
Preguntas
Preguntas, Dudas y Comentarios
Si un hombre se imagina una cosa, otro la tornará en
realidad.
Julio Verne