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