Semana 3 Cuantificadores lógicos - ejercicios para desarrollar PDF

Preview

Summary

Te servirá para el primer ciclo de tu carrera, ya sea cualquiera ingeniería o cualquier carrera que lleves ese curso. Te servirá mucho...

Description

LOGICA CUANTIFICACIONAL

Introducción La lógica de predicados es una extensión de la lógica de proposiciones, y a ella se extienden también los conectivos y operadores de la lógica proposicional. La lógica de predicados descompone la proposición en sus dos componentes básicas (sujeto y predicado) y cuantifica al sujeto, introduciendo símbolos para el sujeto, para el predicado y para los cuantificadores "todos" y "alguno", además de un símbolo de relación entre sujeto y predicado.

CUANTORES. Los cuantores o cuantificadores, son términos que indican la cantidad de una proposición categórica. Son de dos tipos: 1.1. Universalizador. Designa a un enunciado universal, ya sea afirmativo o negativo. En función a sus traducciones verbales se tienen 2 variantes: a) Afirmativo: ∀𝑥( ) Todos, cada uno, quienquiera que sea, cualquiera que sea, los, las, etc. b) Negativo: ∀𝑥( − ) Ninguno, nadie, ni siquiera uno, ni al menos uno, nada, etc. 1.2. Particularizador (Existencializador): ∃𝑥( ) Designa a un enunciado particular, ya sea afirmativo o negativo. Lo encontramos como, existen, hay, pocos, algunos, etc. PREDICADOS. Son términos que designan a una categoría o a una clase. Ejemplos: médico, futbolista, etc. 2.1. Monádicos. Son términos que solo se relacionan con otro predicado mediante un verbo copulativo. Se les simboliza utilizando la primera letra al lado de una x. Ejemplos: Contador (Cx), Ser vivo (Sx), Leche (Lx), etc. 2.2. Diádicos. Son términos que relacionan a dos o más predicados. También son llamados términos relacionantes. Se les simboliza utilizando la primera letra al lado de x, y (dependiendo de los predicados que relaciona). Ejemplos: Jugar (Jxy), Bailar (Bxy), etc.

FORMALIZACIÓN. Para formalizar un enunciado cuantificado se escribe el cuantificador correspondiente seguido del predicado del enunciado cuantificado. El predicado previamente se escribe con letras mayúsculas, seguido de dos puntos; entre comillas se agrega el enunciado afirmativo, utilizando el verbo principal en infinitivo. Ejemplo: los enunciados 1. Algunos son vegetales 2. Hay flores son existenciales o particulares. Para simbolizarlos lógicamente se determinan los predicados así: V: “ser vegetal” F: “ser flor” A: “ser animal” Simbólicamente los enunciados quedan como sigue: ∃𝑥(𝑉𝑥) se lee: “existe un 𝑥 tal que 𝑥 es un vegetal”, o “algún 𝑥 es un vegetal”. ∃𝑥(𝐹𝑥) se lee: “existe un 𝑥 tal que 𝑥 es una flor”, o “algún 𝑥 es una flor”. Ejemplo. Son enunciados universales 1) Todos son vegetales 2) Cualquier flor 3) Siempre son animales Para simbolizarlos lógicamente se determinan los predicados así: V: “ser vegetal” F: “ser flor” A: “ser animal” Simbólicamente los enunciados se expresan: ∀𝑥(𝑉𝑥) y se lee: para todo 𝑥, 𝑥 es un vegetal; cualquier 𝑥, 𝑥 es un vegetal o, siempre 𝑥 , es un vegetal. ∀𝑥(𝐹𝑥) y se lee: para todo 𝑥, 𝑥 es una flor; cualquier 𝑥, 𝑥 es una flor o, siempre 𝑥 , es una flor.

∀𝑥(𝐴𝑥) y se lee: para todo 𝑥, 𝑥 es un animal; cualquier 𝑥, 𝑥 es un animal o, siempre 𝑥, es un animal.

Ejemplos a) Existen políticos: ∃𝑥(𝑃𝑥) b) Todos son inteligentes: ∀𝑥(𝐼𝑥) c) Es mentira que hay puneños: ~∃𝑥(𝑃𝑥) d) Todos no son periodistas: ∀𝑥~(𝑃𝑥) e) Todos son no periodistas: ∀𝑥(~𝑃𝑥) f) Algunos son incorruptibles: ∃𝑥(~𝐶𝑥) g) No todos son mamíferos: ~∀𝑥(𝑀𝑥) h) No hay astronautas: ~∃𝑥(𝐴𝑥) i) Nadie es materialista: ∀𝑥~(𝑀𝑥) j) Casi no hay ermitaños: ∃𝑥(𝐻𝑥) Los ejemplos d) y e) aparentemente son iguales, sin embargo, cuando la negación antecede al verbo formalmente se debe simbolizar con el negador afuera del paréntesis y cuando la negación esta después del verbo la negación va dentro del paréntesis. En el ejemplo j) la palabra “casi no hay”, representa un cuantificador particular, sin negación.

Cuantificadores con predicado compuesto Se llama enunciado compuesto a aquellos enunciados que tienen dos o más predicados Por ejemplo, (∀𝑥)(𝑃𝑥 → 𝑄𝑥 ): cualquier 𝑥 que cumple 𝑃 también cumple 𝑄. (∃𝑥)(𝑃𝑥 ∧ 𝑄𝑥 ): algún 𝑥 que cumple 𝑃 cumple 𝑄. Para usar correctamente el cuantificador tenga en cuenta lo siguiente: Los enunciados particulares utilizan la conjunción como conectivo principal porque lo atribuido a un predicado también se le atribuye al otro. Los enunciados universales utilizan el condicional como conectivo principal, porque lo

atribuido al primer predicado es condición suficiente de lo atribuido al segundo predicado. Ejemplos. a) Todos los animales son vertebrados b) Ningún político es corrupto

∀𝑥(𝐴𝑥 → 𝑉𝑥)

∀𝑥(𝑃𝑥 → ~𝐶𝑥)

c) No hay ingenieros que no tengan creatividad ~∃𝑥(𝐼𝑥 → ~𝐶𝑥) d) Nadie que es abogado no es profesional

∀𝑥(𝐴𝑥 → ~~𝑃𝑥)

e) Es mentira que existen historiadores que son investigadores ~∃𝑥(𝐻𝑥 ∧ 𝐼𝑥) f) Por lo menos un ingenuo no es no devoto g) Ni al menos un no político dice la verdad

∃𝑥(𝐼𝑥 ∧ ~~𝐷𝑥) ∀𝑥(~𝑃𝑥 → ~𝐷𝑥)

h) Los peruanos son cajamarquinos ∀𝑥(𝑃𝑥 → 𝐶𝑥) i) Solo los peruanos son cajamarquinos

∀𝑥(𝐶𝑥 → 𝑃𝑥)

Ojo al orden de las clases de la formalización, la palabra “SOLO LOS” invierte las clases. j) Todos son ricos a menos que sean pobres

∀𝑥(𝑅𝑥 ∨ 𝑃𝑥)

k) Todos son protestantes si y solo si son religiosos

∀𝑥(𝑃𝑥 ↔ 𝑅𝑥)

l) Algunos son estudiosos porque son responsables ∃𝑥(𝐸𝑥 ← 𝑅𝑥) m) El 100% son desinteresados al igual que apáticos

∀𝑥(~𝐼𝑥 ∧ 𝐴𝑥)

n) Es falso que algunos son trujillanos o solamente son limeños ~∃𝑥(𝑇𝑥 ⊕ 𝐿𝑥) o) Es falso que cada uno de los felinos sean tigres al menos que sean leones ~∀𝑥[𝐹𝑥 → (𝑇𝑥 ∨ 𝐴𝑥)] p) Todos los lógicos son reflexivos y estudiosos

∀𝑥[𝐿𝑥 → (𝑅𝑥 ∧ 𝐸𝑥)]

q) Todos los libros de mi estante están empastados o no están empastados ∀𝑥[𝐿𝑥 → (𝐸𝑥 ∨∼ 𝐸𝑥)] Ejemplo. Transcriba al lenguaje simbólico los enunciados 1 Hay flores rojas 2 Para toda flor roja 3 Algún hombre sin empleo es un delincuente en potencia Los enunciados 1 y 2 tienen los siguientes predicados: F:”ser flor” R:”ser roja”

El numeral 1 se simboliza logicamente (∃𝑥)(𝐹𝑥 ∧ 𝑅𝑥) El numeral 2 se simboliza logicamente (∀𝑥)(𝐹𝑥 → 𝑅𝑥) El enunciado del numeral 3 lleva los siguientes predicados: H:”ser hombre” T:”tener empleo” D:”ser un delincuente en potencia” La expresión transcrita al lenguaje simbólico es (∃𝑥 )((𝐻𝑥 ∧ ~𝑇𝑥) ∧ 𝐷𝑥 ) que se leería en lenguaje corriente: “hay un 𝑥 tal que x es un hombre que no tiene empleo y es un delincuente en potencia”. Negación de cuantificadores Para negar un enunciado cuantificado, basta con cambiar el cuantificador y negar la afirmación o predicado. En la negación del predicado deberá utilizar las leyes del álgebra proposicional. ~(∀𝑥)(𝑃𝑥) ⇔ (∃𝑥)(~𝑃𝑥): algunos 𝑥 no cumplen 𝑃 . ~(∃𝑥)(𝑃𝑥) ⇔ (∀𝑥)(~𝑃𝑥): ningún 𝑥 cumple 𝑃 . ~(∃𝑥)(𝑃𝑥 ∧ 𝑄𝑥) ⇔ (∀𝑥)(𝑃𝑥 → ~𝑄𝑥): ningún 𝑥 que cumple 𝑃 cumple 𝑄. ~(∀𝑥)(𝑃𝑥 → 𝑄𝑥) ⇔ (∃𝑥)(𝑃𝑥 ∧ ~𝑄𝑥): algún 𝑥 que cumple 𝑃 no cumple 𝑄.

En resumen

3.1. Proposiciones en formas típicas. a) Universal afirmativa: Todo S es P ∀𝑥(𝑆𝑥 → 𝑃𝑥) b) Universal negativa: Ningún S es P ∀𝑥(𝑆𝑥 → ~𝑃𝑥) c) Particular afirmativa: Algunos S son P ∃𝑥(𝑆𝑥 ∧ 𝑃𝑥) d) Particular negativa: Algunos S no son P ∃𝑥(𝑆𝑥 ∧∼ 𝑃𝑥) 3.2. Proposiciones predicativas y relacionales. Ejemplos: • Milagritos ingresó a la UNT • Edwin y Félix son ingenieros • Milagros y Jhonson son compadres 3.3. Un predicado.

Im 𝐼𝑒 ∧ 𝐼𝑓 Cmj

Ejemplos: • Varios son artesanos • Todos son académicos • Ninguno es nihilista

∃𝑥(𝐴𝑥) ∀𝑥(𝐴𝑥 ) ∀𝑥(~𝐴𝑥)

EQUIVALENCIAS. Son las mismas de la lógica proposicional con el adicional que si el negador se aplica al cuantor, este cambia. Ejemplos:

Def. del implicador ∀𝑥(𝑆𝑥 → 𝑃𝑥 ) ∀𝑥(~𝑆𝑥 ∨ 𝑃𝑥)

Conmutación

De Morgan

∃𝑥(𝑆𝑥 ∧∼ 𝑃𝑥) ∃𝑥(∼ 𝑃𝑥 ∧ 𝑆𝑥)

∼ ∃𝑥(𝑆𝑥 ∧ 𝑃𝑥) ∀𝑥(~𝑆𝑥 ∨∼ 𝑃𝑥)

Negación del implicador ∼ ∀𝑥(𝑆𝑥 → 𝑃𝑥)

De Morgan

De Morgan

∃𝑥(𝑆𝑥 ∧ ~𝑃𝑥)

∼ ∃𝑥(𝑆𝑥)

∼ ∀𝑥(∼ 𝑆𝑥)

∀𝑥(∼ 𝑆𝑥)

∃𝑥(𝑆𝑥)

∃𝑥(𝑃𝑥) ≡ ~∀𝑥~(𝑃𝑥) ∃𝑥~(𝑃𝑥) ≡ ~∀𝑥(𝑃𝑥) ~∃𝑥(𝑃𝑥) ≡ ∀𝑥~(𝑃𝑥) ~∃𝑥~(𝑃𝑥) ≡ ∀𝑥(𝑃𝑥) ~∀𝑥~(𝑃𝑥) ≡ ∃𝑥(𝑃𝑥) ∀𝑥~(𝑃𝑥) ≡ ~∃𝑥(𝑃𝑥) ∀𝑥(𝑃𝑥) ≡ ~∃𝑥~(𝑃𝑥)

Ejemplo.

La proposición “Existen políticos” es equivalente a ∃𝑥(𝑃𝑥) ≡ ~∀𝑥~(𝑃𝑥). Es decir, es equivalente a “Es falso que todos no son políticos”

INFERENCIAS. Se basan en una interpretación en base a descomposición. La universal se descompone con “∧” y la particular con “∨” Ejemplos ∀𝑥(𝑆𝑥 ∧ 𝑃𝑥)

∀𝑥(𝐴𝑥)

∀𝑥(∼ 𝐻𝑥)

∀𝑥(𝑆𝑥) ∧ ∀𝑥(𝑃𝑥)

𝐴𝑎 ∧ 𝐴𝑏 ∧ 𝐴𝑐 …

~𝐻𝑎 ∧∼ 𝐻𝑏 ∧∼ 𝐻𝑐 …

∃𝑥(𝑆𝑥 ∨ 𝑃𝑥 ) ∃𝑥(𝑆𝑥) ∨ ∃𝑥(𝑃𝑥)

∃𝑥(𝑀𝑥) 𝑀𝑎 ∨ 𝑀𝑏 ∨ 𝑀𝑐 …

∃𝑥(∼ 𝑇𝑥) ~𝑇𝑎 ∨∼ 𝑇𝑏 ∧∼ 𝑇𝑐 …

Combinación de cuantificadores Algunos enunciados cuantificados llevan combinación de cuantificadores que se diferencian por el orden en que se disponen, con el fin de conformar una expresión. Con el propósito de aclarar el significado mediante el simbolismo lógico de cada expresión, se recomienda poner paréntesis. (∀𝑥 )(∀𝑦)(afirmación) (∀𝑥 )(∃𝑦)(afirmación) (∃𝑥 )(∀𝑦 )(afirmación) (∃𝑥 )(∃𝑦)(afirmación)

Ejemplo. Determine si los siguientes enunciados son equivalentes

“Para todo número racional diferente de cero hay otro racional tal que el producto entre ellos es 1”. “Hay un número racional diferente de cero que al multiplicarlo por otro racional el resultado es 1”. Para darle solución a este problema se sugiere escribir ambos enunciados en lenguaje simbólico y luego determinar el valor de verdad de cada uno. En efecto, escribamos simbólicamente la afirmación del primer enunciado.

(∀𝑥𝜖ℚ − {0})((∃𝑦𝜖ℚ): 𝑥 ∙ 𝑦 = 1)) Ahora, escribamos el segundo enunciado (∃𝑥𝜖ℚ − {0})((∀𝑦𝜖ℚ): 𝑥 ∙ 𝑦 = 1)) Si analizamos el primer enunciado se puede deducir que este es verdadero, porque basta con multiplicarlo por su inverso multiplicativo a cualquier racional; por ejemplo, 5*(1/5)=1 ó (-12)*(1/(-12))=1; en general, si y= 1/x se tiene que x*(1/x)=1 para todo entero x≠0. En el segundo caso se tiene que es falso, porque no hay un número racional tal que al multiplicarlo por cualquier racional resulte 1; por ejemplo, 5 y 4 son números racionales y 5*4≠1. Efectivamente, los enunciados no son lógicamente equivalentes. Por consiguiente, del anterior ejemplo nos permite concluir que en general (∀𝑥 )(∃𝑦)(afirmación) no siempre es equivalente a (∃𝑦)(∀𝑥 )(afirmación)

Observe que el orden del cuantificador en el enunciado es importante para determinar el valor de verdad. ¿Qué se puede decir del enunciado: “cualquier número natural se resta cualquiera otro número natural se obtiene otro número natural”? Este enunciado transcrito al lenguaje lógico es (∀𝑥𝜖ℕ)((∀𝑦𝜖ℕ)(𝑥 − 𝑦𝜖ℕ)). ¿Es equivalente (∀𝑦𝜖ℕ)((∀𝑥𝜖ℕ)(𝑥 − 𝑦𝜖ℕ))? Ejemplo. Determine el valor de verdad de los siguientes enunciados:

a) Para todo número real se tiene otro número real que al sumarlos su resultado es cero. b) Hay números reales que al sumarles cualquier número real resulta cero. Solución Tenga en cuenta que inicialmente debe transcribirlos al lenguaje simbólico. En efecto, la primera expresión se simboliza (∀𝑥𝜖ℝ)(∃𝑦𝜖ℝ)(𝑥 + 𝑦 = 0) la cual es verdadera; basta con adicionarle el inverso aditivo y se logra el resultado. La segunda expresión se simboliza (∃𝑥𝜖ℝ)(∀𝑦𝜖ℝ)(𝑥 + 𝑦 = 0) la cual es falsa pues no existe un número que al adicionarle cualquier otro número resulte cero. Ejemplo. Exprese en palabras y determine el valor de verdad de las siguientes proposiciones cuantificadas, en donde 𝑥, 𝑦𝜖ℝ. a) ∃𝑥∃𝑦(𝑥 + 𝑦 = 17) b) ∀𝑥∃𝑦(𝑥 + 𝑦 = 17) c) ∃𝑥∀𝑦(𝑥 + 𝑦 = 17) d) ∀𝑥∀𝑦(𝑥 + 𝑦 = 17) Solución. a) En palabras: para algún 𝑥 , existe un 𝑦 tal que 𝑥 + 𝑦 = 17. En este caso es posible hallar, al menos, un par 𝑥, 𝑦 tal que 𝑥 + 𝑦 = 17 (por ejemplo el par 𝑥 = 7, 𝑦 = 10). Como ambos cuantificadores son existenciales, un ejemplo es suficiente para concluir que el valor de verdad de esta proposición es verdadero. b) En palabras: para todo 𝑥 , existe un 𝑦 tal que 𝑥 + 𝑦 = 17. En este caso también es posible hallar, para cada 𝑥 , un 𝑦 tal que satisfaga la propiedad, y que está dado por 𝑦 = 17 − 𝑥. Esto es, cada x tiene asegurado un y (único en cada caso) y, por eso, el valor de verdad de esta proposición es verdadero. c) En palabras: para algún 𝑥 , y para todo 𝑦, debe ser 𝑥 + 𝑦 = 17. Debería existir un 𝑥 tan particular que sumándole cualquier 𝑦 diera siempre 17. Pero esto no es posible, por lo que el valor de verdad de esta proposición es falsa.

d) En palabras: para todo 𝑥 debería ser posible sumarle cualquier 𝑦 siempre dar 17. Esto no es posible, por lo que el valor de verdad de esta proposición es falso. Observación. En general se tiene que ∃𝑥∃𝑦𝑃(𝑥, 𝑦) ≡ ∃𝑦∃𝑥𝑃(𝑥, 𝑦)

conmutan

∀𝑥∀𝑦𝑃(𝑥, 𝑦) ≡ ∀𝑦∀𝑥𝑃(𝑥, 𝑦)

conmutan

∀𝑥∃𝑦𝑃(𝑥, 𝑦) ≡ ∃𝑦∀𝑥𝑃(𝑥, 𝑦)

no conmutan

Negación de combinaciones de cuantificadores Para negar proposiciones donde intervienen más de un cuantificador, se emplea sucesivamente las reglas de negación para proposiciones con un único cuantificador. Ejemplo. Negar la proposición

∃𝑥∀𝑦𝑃(𝑥, 𝑦)

Solución. ~(∃𝑥∀𝑦𝑃(𝑥, 𝑦)) ≡ ∀𝑥~(∀𝑦𝑃(𝑥, 𝑦)) ≡ ∀𝑥∃𝑦~𝑃(𝑥, 𝑦)) Para determinar si ∀𝑥∀𝑦𝑃(𝑥, 𝑦) es verdadera o falsa recorremos todos los valores 𝑥 e 𝑦 de la siguiente manera. Para cada 𝑥 analizamos todos los valores de 𝑦. Si determinamos que 𝑃(𝑥, 𝑦) es verdadera en todos los casos, la conclusión inevitable es que ∀𝑥∀𝑦𝑃(𝑥, 𝑦) es verdadera. Si por el contrario, cuando encontramos el primer par de valores 𝑥 e 𝑦 tal que 𝑃(𝑥, 𝑦) es falsa, es suficiente para concluir que ∀𝑥∀𝑦𝑃(𝑥, 𝑦) es falsa. Propiedades de los Cuantificadores 1) (∀𝑥 )(𝑃𝑥 ∧ 𝑄𝑥) ⇔ (∀𝑥 )(𝑃𝑥) ∧ (∀𝑥 )(𝑄𝑥) El cuantificador universal es distribuible por la conjunción de predicados. 2) (∀𝑥 )(𝑃𝑥 → 𝑄𝑥) ⇒ (∀𝑥 )(𝑃𝑥) → (∀𝑥 )(𝑄𝑥) El cuantificador universal es distribuible en el condicional de predicados. 3) (∀𝑥 )(𝑃𝑥 ↔ 𝑄𝑥) ⇒ (∀𝑥 )(𝑃𝑥) ↔ (∀𝑥 )(𝑄𝑥) El cuantificador universal es distribuible en el bicondicional de predicados.

4) (∀𝑥 )(𝑃𝑥) ∨ (∀𝑥)(𝑄𝑥) ⇒ (∀𝑥 )(𝑃𝑥 ∨ 𝑄𝑥 ) Ley de distribución del cuantificador universal por la disyunción de predicados 5) (∃𝑥 )(𝑃𝑥 ∧ 𝑄𝑥) ⇒ (∃𝑥)(𝑃𝑥) ∧ (∃𝑥 )(𝑄𝑥) Ley de distribución del cuantificador particular por la conjunción de predicados. 6) (∃𝑥 )(𝑃𝑥 ∨ 𝑄𝑥) ⇔ (∃𝑥 )(𝑃𝑥) ∨ (∃𝑥)(𝑄𝑥) Ley de distribución del cuantificador particular por la disyunción de predicados....