Matemática Discreta resumen

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Cuantificadores CONTENIDO Unidad 2: LÓGICA Y ALGORITMOS 2.3 Cuantificadores ▪ Introducción ▪ Funciones proposicionales ▪ Cuantificador universal ▪ Cuantificador existencial UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Cuantificadores Introducción En el capítulo 2.1 discutimos el análisis lógico de los enunciados compuestos, que están formados de enunciados simples unidos por los operadores ~, ∧, ∨, → y ↔ . Dicho análisis ilumina muchos aspectos del razonamiento humano, pero no se puede utilizar para determinar la validez en la mayoría de las situaciones cotidianas y matemáticas. Por ejemplo, el argumento: 𝑇𝑜𝑑𝑜𝑠 𝑙𝑜𝑠 ℎ𝑜𝑚𝑏𝑟𝑒𝑠 𝑠𝑜𝑛 𝑚𝑜𝑟𝑡𝑎𝑙𝑒𝑠. 𝑆ó𝑐𝑟𝑎𝑡𝑒𝑠 𝑒𝑠 𝑢𝑛 ℎ𝑜𝑚𝑏𝑟𝑒. ∴ 𝑆ó𝑐𝑟𝑎𝑡𝑒𝑠 𝑒𝑠 𝑚𝑜𝑟𝑡𝑎𝑙. se percibe intuitivamente como correcto. Sin embargo, su validez no puede deducirse utilizando los métodos descritos en la sesión anterior. Para determinar la validez de ejemplos como éste, es necesario separar los enunciados en partes de la misma manera que se separan las frases declarativas en sujetos y predicados. Y se debe analizar y comprender el papel especial que desempeñan las palabr as que denotan cantidades tales como “todos” o “algunos”. El análisis simbólico de los predicados y los enunciados cua ntificados se llama cálculo de predicados. El análisis simbólico de enunciados compuestos ordinarios se llama cálculo de enunciados (o cálculo proposicional). Funciones proposicionales Las siguientes oraciones son enunciados abiertos: 𝐸𝑠𝑡𝑎 ⏟ 𝑆𝑢𝑗𝑒𝑡𝑜 𝑒𝑠 𝑙𝑎 𝑐𝑎𝑝𝑖𝑡𝑎𝑙 𝑑𝑒𝑙 𝑃𝑒𝑟ú ⏟ 𝑃𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜 𝑥 + 2 ⏟ 𝑆𝑢𝑗𝑒𝑡𝑜 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 4 ⏟ 𝑃𝑟𝑒𝑑𝑖𝑐𝑎𝑑𝑜 Pues el valor de verdad dependerá del sujeto. Haciendo: • “ Esta = Lima ”, entonces tendremos que “ Lima es la capital de Perú ” (V) • x =1, entonces tendremos que “1+2 es mayor que 4” (F) Es por lo que a estos enunciados abiertos se les llama Función proposicional o se les dice predicado , pues su valor de verdad dependerá de quién sea el sujeto. El sujeto generalmente se representa como una variable 𝑥 . Sea 𝑃(𝑥) una oración abierta que incluye la variable 𝑥 y sea 𝐷 un conjunto. 𝑃(𝑥) se llama función proposicional o predicado (respecto de D ) si para cada 𝑥 en 𝐷 , 𝑃(𝑥) es una proposición. Simbolización de una Función proposicional : 𝑃(𝑥), 𝑥 ∈ 𝐷 UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 Ejemplo 1 𝑥 + 2 es mayor que 4  𝑃(𝑥) donde 𝑃 representa el predicado: “Es mayor que 4”. • Si 𝑥 = 1, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑃(1) 𝑒𝑠 𝐹𝑎𝑙𝑠𝑜 . • Si 𝑥 = 3, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑃(3) 𝑒𝑠 𝑉𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑜 . Ejemplo 2 𝑆𝑖 𝑥 ∈ 𝑅, 𝑥 2 > 𝑥  𝑃(𝑥) donde 𝑃 representa el predicado: "𝑥 2 > 𝑥" • Si 𝑥 = 2, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑃(2) 𝑒𝑠 𝑉𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑜 • Si 𝑥 = 1/2, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑃(1/2) 𝑒𝑠 𝐹𝑎𝑙𝑠𝑜 . Cuantificadores Considere las siguientes frases ( proposiciones generales ): • Todos los gatos tienen cola • Algunas personas les gusta la carne cruda • Todo el mundo tiene un descanso de vez en cuando A partir de funciones proposicionales es posible obtener proposiciones generales mediante un proceso llamado de cuantificación. Asociados a la variable 𝑥 , introducimos los símbolos: 𝐶𝑢𝑎𝑛𝑡𝑖𝑓𝑖𝑐𝑎𝑑𝑜𝑟 𝑈𝑛𝑖𝑣𝑒𝑟𝑠𝑎𝑙 ⏟ ∀ 𝐶𝑢𝑎𝑛𝑡𝑖𝑓𝑖𝑐𝑎𝑑𝑜𝑟 𝐸𝑥𝑖𝑠𝑡𝑒𝑛𝑐𝑖𝑎𝑙 ⏟ ∃ Cuantificador universal Sea P una función proposicional con dominio en D . Se dice que la afirmación: “ para toda 𝒙 ∈ 𝑫, 𝒄𝒖𝒎𝒑𝒍𝒆 𝑷(𝒙)” es una afirmación cuantificada universalmente Notación: Para todo 𝑥 en 𝐷 , se verifica 𝑃(𝑥) , se denota por : ∀ 𝑥 ∈ 𝐷, 𝑃(𝑥) La afirmación ∀ 𝑥 ∈ 𝐷, 𝑃(𝑥) es verdadera si 𝑃(𝑥) es verdadera para toda 𝑥 en 𝐷 . La afirmación ∀ 𝑥 ∈ 𝐷, 𝑃(𝑥) es falsa si 𝑃(𝑥) es falsa para al menos una 𝑥 en 𝐷 . Observación: Las palabras: todo , cada uno , todos y ninguno , son consideradas como cuantificadores universales. UPC –…