Download GUÍA PRÁCTICA Nº 2
Document related concepts
Transcript
1 GUÍA PRÁCTICA Nº 2. LÓGICA PROPOSICIONAL Y LÓGICA DE PREDICADOS Sintaxis de la lógica proposicional: Introducción: Lenguaje Es una construcción a partir de ciertas unidades llamadas signos (marcas – letras) a partir de las cuales se construyen expresiones (sucesión finita de signos sin significado) y entre las cuales se destacan las fórmulas bien formadas (expresiones con significado) Observación: el lenguaje en conjunción con axiomas y reglas de inferencia constituyen lo que se denomina un sistema deductivo formal (sintaxis) Lenguaje de la lógica proposicional: Consta de: Alfabeto de signos: o Variables proposicionales: p, q, r, s,… (simbolizan proposiciones simples) o Conectivos lógicos u operadores lógicos: negación (), disyunción no excluyente (), conjunción (), condicional () y bicondicional () entre otros enlazan variables proposicionales para formar formas proposicionales compuestas. o Signos auxiliares: true (constante de verdad), false (constante de falsedad), “(“, “)” (paréntesis). Fórmulas proposicionales (fórmulas bien formadas, definidas en forma inductiva) Notación: A, B, C, … (letras metalingüísticas) o Las variables proposicionales son fórmulas bien formadas (base de la definición). o Si A y B son fórmulas proposicionales entonces: A, (A B), (A B), (A B) y (A B) son fórmulas proposicionales (paso inductivo). o El conjunto de fórmulas proposicionales (F) es el generado por las reglas anteriores (cláusula de cierre). 1) Dadas p y q: variables proposicionales, indicar cuáles de las siguientes expresiones son fórmulas bien formadas: a) p q b) (p q) c) p q r d) (p q) r e) ((p q) r) f) (true p) 2 g) (p p q) h) p = q 2) Eliminar los paréntesis innecesarios de las siguientes fórmulas bien formadas (fórmulas proposicionales) según criterios de reducción de paréntesis: a) ((( p) q) (p (r q))) b) ( (((p q) (q r)) ((( p) q) (p ( r))))) c) ((p (( p) q)) (( q) ( (p q)))) Observación: La eliminación de paréntesis está sujeto a los siguientes criterios de reducción de paréntesis: o se pueden eliminar los paréntesis externos. o la precedencia de asociación de conectivos es: , , , , (alcance de conectivos). o si un conectivo se usa repetidamente, se asocia según la siguiente tabla de asociatividad: izquierda izquierda derecha derecha 3) Indicar los árboles de análisis (o árboles de formación) de las fórmulas proposicionales dadas en el ejercicio anterior. Observación: Tener en cuenta las siguientes reglas de inscripción: A A B A A A B A, B: fórmulas proposicionales : conectivo binario Semántica de la lógica proposicional: Hasta ahora las fórmulas proposicionales son meras combinaciones de símbolos que responden a ciertas reglas de formación pero sin sentido alguno. Ahora se dotará al lenguaje de un poder de expresión a través de una interpretación. La semántica hace referencia fundamentalmente a la manera en que se asignan valores de verdad a las expresiones del cálculo. 3 Semántica clásica (lógica bivaluada o bivalente – semántica basada en tablas de verdad) Hay dos valores de verdad posible: verdadero (V - 1) y falso (F - 0) el signo true false se interpreta como 1 0 “no” y se llama negación “y” y se llama conjunción “o” (no excluyente) y se llama disyunción “si…entonces” y se llama condicional “….si y sólo si…” y se llama condicional El valor de verdad de una fórmula proposicional depende del valor de verdad de las variables proposicionales que intervienen en la fórmula. p 0 1 p 1 0 p 0 0 1 1 q 0 1 0 1 pq 0 0 0 1 pq 0 1 1 1 pq 1 1 0 1 pq 1 0 0 1 4) Analizar si las siguientes oraciones son proposiciones. a) Prolog. es un lenguaje declarativo basado en las reglas de la lógica. b) ¿Vienes hoy a clase? c) Visite las playas de Pinamar. d) Visité las playas de Pinamar. e) 5 es múltiplo de 2. f) Pascal es un lenguaje de procedimientos. g) Si Borges no hubiera nacido, Sábato sería el mejor escritor argentino. h) x + 4 = 10. i) Hay números enteros que satisfacen la ecuación x +4 = 10. j) Si estudias hoy podrás salir mañana. k) En la última década ha habido un creciente énfasis en el uso de métodos formales para el desarrollo de sistemas hardware y software. 4 5) Asignar letras a las proposiciones simples (átomos) y expresar, mediante el uso de conectivos, las siguientes proposiciones: a) Iré al médico aunque me siento bien. b) No serán sancionados si la notificación llegó con retraso y tampoco serán sancionados si tienen justificativo médico. c) No cometió el crimen si no pudo comprar un revolver. d) El cuadro es de valor de verdad si solo tiene por lo menos 600 años. e) Es suficiente que deje de fumar para que mi rendimiento físico mejore. f) Es necesario que deje de fumar para que mi rendimiento físico mejore. g) Es necesario y suficiente que no tenga deudas para que salga de garante. Dado el condicional: A B, además del giro idiomático asociado; “Si A entonces B” otros giros asociados son: A sólo si B B si A A es condición suficiente para B B es condición necesaria para A 6) Construir las tablas de verdad de las siguientes fórmulas proposicionales: a) (p q) q b) (p q) p c) ( p q) ( p q) d) p (p q) p e) p p q f) (p q) (p q) Observaciones: O1) Una fórmula proposicional es una tautología o ley lógica ó verdad lógica, si para toda asignación de valores de verdad de las componentes simples resulta ser verdadera. Si para toda asignación resulta ser falsa, es una contradicción. Finalmente una fórmula que no es ni tautología ni contradicción, es una contingencia. 5 O2) Si un condicional (A B) o (A B) es tautológico, se dice que el antecedente implica lógicamente el consecuente. Se indica: (A B) 03) Si un bicondicional (A B) es tautológico, se dice que una de sus componentes equivale lógicamente a la otra. Se indica: (A B) o (A B) 7) Determinar el valor de verdad de las siguientes fórmulas proposicionales a partir de la siguiente valuación: v(p) = v(s) = V y v(q) = v(r) = F a) (p q) r b) ( p) (( (q s)) r s) c) (q s) (r s) Una valuación (v) es una función que asigna valores de verdad a las variables proposicionales: v: V {0, 1} (V: conjunto de variables proposicionales que intervienen en la fórmula proposicional dada) 8) Dada la fórmula A : (r ( p)) ( q) a) Si v(A) = V, v(q) = V y v(p) = F, hallar v(r) b) Si v(A) = F, v (r) = V y v(p) = F, hallar v(q) 9) Justificar si la información indicada es suficiente, en cada caso, para determinar el valor de verdad de la fórmula proposicional indicada: a) (p q) (p r) b) (( p) ( q )) (p q) c) (p q) r v (p) = V y v(r) = F v (p) = V v (r p) = V Semántica basada en el concepto de satisfactibilidad Dada una valuación (v) y una fórmula proposicional A, se define que “v satisface A” y se indica v ⊨ A en forma inductiva: v ⊨P si v (P) = 1 v ⊨ true v ⊭ false (no es cierto que v ⊨ false) v ⊨ A B sii v ⊨ A y v ⊨ B v ⊨ A B sii v ⊨ A o v ⊨ B v ⊨ A B sii v ⊭A o v ⊨ B v ⊨ A B sii (v ⊨ A sii v ⊨ B) 6 En función de esto se dice que: A es tautologia si toda valuación v la satisface (v ⊨ A, cualquiera sea v) se indica ⊨ A A es contradicción si ninguna valuación v la satisface (v ⊭ A, cualquiera sea v) A es contradicción si A ni es tautología ni es contradicción (alguna valuación la satisface y alguna no) 10) Obtener una fórmula proposicional más simple equivalente a la dada en cada caso. Indicar las leyes lógicas aplicadas: a) ( p q) ( p q) b) ( (p q ) (q p) c) ((p q) ( p q)) p d) ((p (q q) ( r r)) p ( r) 11) Verificar que las siguientes fórmulas son tautológicas mediante el uso de leyes lógicas: a) ((p q) r) b) ((p q) r) y (p (q r)) y ((p r) (q r)) 12) Ídem 11) pero a través de una “tabla simplificada”: a) (p (q r)) ( p q) b) ((p q) (q p)) ((p q) (p q) Observación: A los efectos de analizar si una fórmula proposicional es tautologia, contradicción o contingencia, en lugar de hacer una tabla completa, se puede hacer una tabla simplificada o abreviada. La misma consiste : 7 en el caso de que sea tautología en descartar la posibilidad de que la tabla arroje algún resultado falso en descartar la posibilidad de que la tabla arroje algún resultado verdadero en mostrar una valuación que satisfaga la fórmula y otra que no la satisfaga en el caso de que sea contradicción en el caso de que sea contingencia 13) Determinar la relación de fuerza entre los siguientes pares de fórmulas: a) true, false b) (p q) (p q) e) p,(p q) f) p,(p q) c) true, true g) p, (p q) d) false, false h) (pq), (p q) Se dice que una fórmula proposicional A es más fuerte que una fórmula B (o que A fuerza B) cuando ⊨ A B ¿ Hay una fórmula más fuerte que todas las demás? ¿ Hay una fórmula más débil que todas las demás? 14) Factorizar y reducir las siguientes fórmulas proposicionales: a) (p q r) (p q) (p ( r)) b) (p q) (p r) (p (q ( r)) c) (( p) r) (( p) ( r)) 15) Hallar en cada caso una fórmula proposicional, cuya tabla de verdad arroje el resultado indicado, en su forma normal disyuntiva (FND) o bien en su forma normal conjuntiva (FNC), según convenga. p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 f (p ,q, r) 1 1 0 0 1 0 0 0 g (p ,q, r) h (p ,q, r) 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 Así como dada una fórmula proposicional se puede confeccionar una única tabla de verdad correspondiente (salvo el orden en que arman las filas), dada una tabla de verdad arbitraria, se puede hallar una fórmula proposicional (standard) asociada a la misma 8 16) Hallar una fórmula proposicional equivalente a la dada usando sólo los conectivos de los siguientes conjuntos adecuados de conectivos: {, , }, {}, {} a) ((p q) (p)) ((p q)) b) (p q) ((p q)) c) (p q) ((p q)) Observaciones: O1) Se dice que {, , } es un conjunto adecuado o completo de conectivos ya que toda proposición compuesta se puede expresar usando únicamente los conectivos de dicho conjunto O2) Se puede decir lo mismo de los conjuntos {, }; {, } y {, } Hay dos conectivos que merecen especial atención por las consecuencias en el diseño y estudio de computadoras. Estos son el conectivo NOR (negación de disyunción), denotado por y caracterizado por el giro idiomático “ni ...ni” (negación conjunta) y el conectivo NAND (negación de conjunción), denotado por | y caracterizado por el giro idiomático “o no... o no...” (negación alternativa). Observación: los giros idiomáticos que caracterizan a las operaciones NOR y NAND, tienen que ver con las equivalencias: (p q) (p q) p q (p | q) (p q) p q y llevan naturalmente a las tablas: p 0 0 1 1 q 0 1 0 1 pq 1 0 0 0 p|q 1 1 1 0 17) Demostrar, en la forma indicada, que los siguientes condicionales son verdaderos: en forma directa: a) Si un número entero es múltiplo de 6 entonces dicho número es múltiplo de 2 y múltiplo de 3. b) El producto de dos enteros impares es impar. 9 en forma indirecta o por contrarecíproco: 1. Si el cuadrado de un número entero es impar, dicho número es impar 2. Si al multiplicar un número entero por cinco y a dicho resultado se le suma tres se obtiene un entero par, el número dado es impar. por absurdo: 1. Si un número entero es menor que otro, necesariamente el primero es menor o igual que el sucesor del segundo. 2. Un número entero es impar sólo si su sucesor es par. 18) Refutar las siguientes afirmaciones: a) la suma de dos naturales pares es un natural impar. b) el producto de dos naturales impares es un natural par c) La suma de dos múltiplos de 3 es un número par. d) La suma de un múltiplo de 3 y de un múltiplo de 2 nunca es múltiplo de 3. 19) Demostrar o refutar (según corresponda) las siguientes afirmaciones: a) Si un número natural es múltiplo de 100 entonces es múltiplo de 10. b) Si un número natural es múltiplo de 10 entonces es múltiplo de 100. c) Si n = 3 k + 2 con k ∈ N , entonces n es impar. d) Si n = 3 k + 2 con k ∈ N , entonces n es divisible por 3. e) Si n = 3 k + 2 con k ∈ N , entonces n es divisible por 2.