Guía Practica - Unidad N3 - Lógica de Predicados PDF

Preview

Summary

Material de trabajo dado por el profesor de la materia....

Description

UNIVERSIDAD NACIONAL DE SANTIAGO DEL ESTERO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGÍAS

TRABAJO PRACTICO III

LÓGICA I CARRERA: LICENCIATURA EN SISTEMAS DE INFORMACIÓN

Dr. Maximiliano Celmo David Budán Prof. Ximena Villarreal

AÑO 2020

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

UNIVERSIDAD NACIONAL DE SANTIAGO DEL ESTERO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGÍAS CARRERAS: LICENCIATURA EN SISTEMAS DE INFORMACIÓN ASIGNATURAS: LÓGICA I PROGRAMACIÓN ANALÍTICA DEL CAPÍTULO Nº 4 CÁLCULO DE PREDICADOS Y TEORÍA DE LA CUANTIFICACIÓN. Formas Proposicionales. Definición. Componentes. Universo del discurso. Representación simbólica. Variables de individuo y variables de enunciado. Relación entre universo y conjunto de verdad de una forma proposicional. Fórmulas proposicionales y proceso de transformación en proposiciones singulares y generales. Formas proposicionales monádicas, diádicas y n-ádicas. Teoría de la Cuantificación. Cuantificador universal y cuantificador existencial. Alcance de un cuantificador. Variables libres y variables ligadas. Proposiciones generales complejas categóricas. Representación simbólica. Fórmulas Lógicas. Forma correcta de una fórmula lógica. Condiciones para que una fórmula lógica represente una proposición. Negación de proposiciones cuantificadas. Equivalencia de proposiciones cuantificadas universalmente y existencialmente: Ley de intercambio de cuantificadores. Leyes de distribución de cuantificadores. Ley de subalternación. COMPETENCIAS Desarrollar un lenguaje matemático lógico formal. Plantear y desarrollar los ejercicios propuestos con un espíritu creativo y crítico. Reconocer vínculos significativos entre conocimientos previos y conceptos nuevos. Demostrar la correcta interpretación de enunciados coloquiales y su adecuada transformación al lenguaje lógico matemático en cuestión. Participar en forma activa en clase, exponiendo resultados y formulando argumentaciones. Trabajar en grupo, realizando aportes pertinentes y valorando otras opiniones. Mostrar actitudes de solidaridad y compañerismo con sus pares. BIBLIOGRAFÍA “Lógica Simbólica y Elementos de Metodología de las Ciencias”. SALAMA, Alicia G. Ateneo. Primera Edición. Buenos Aires. 1996. “Lógica Simbólica”. COPI, Irving. Primera Edición. Continental. Mexico. 1996. “Matemática Elemental Moderna: Estructura y Método”. TREJO, César A.. Paidos. Buenos Aires. 2004. “Lógica Informática”. CUENA, José. Alianza Informática. Madrid, España. 2003. “Truth, deduction, and computation logic and semantics for computer science”. DAVIS, Ruth .E. . Freeman and Company. NewYork. 1989. 1

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

“A concise introduction to mathematical logic”. WOLFGANG Rautenberg. Tercera Edición. Springer. New York. 2010.

2

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

GUÍA DE TRABAJO TEÓRICO–PRÁCTICO Nº 3 TEMA: CÁLCULO DE PREDICADOS Y CUANTIFICADORES. 1. Lógica de Predicados: Motivación El desarrollo del cálculo proposicional se basa en unidades de información, cuya estructura se contempla como un todo, sin diferenciar sus componentes. Este planteamiento no permite representar lógicamente ciertos razonamientos deductivos, que, sin embargo, son correctos en el lenguaje coloquial; como por ejemplo: Todos los hombres son mortales. Sócrates es hombre. Luego, Sócrates es mortal. Este razonamiento, simbolizado con el lenguaje del cálculo proposicional, tiene la siguiente representación lógica: p q r Si se pretende probar su validez mediante el método del condicional asociado, se obtiene la fórmula p  q  r, cuya tabla de valores de verdad es una contingencia. Esto se debe a que ninguna de las proposiciones p, q, r, pueden describirse mediante partes de las mismas dotadas de significado propio, unidas por conectivas, que sean comunes en algunas de ellas y, la relación entre premisas y conclusión que hace la deducción correcta, no puede detectarse con el lenguaje y los métodos estudiados en la lógica proposicional. En este ejemplo de razonamiento, la relación entre las proposiciones está en la propia estructura interna de éstas, en efecto: se afirman en ellas las mismas propiedades o relaciones para distintas personas o conjuntos de personas (Las propiedades son “Ser Hombre”, “Ser mortal”; las personas objeto de atribución de estas propiedades son colectivos, en la primera proposición, e individuos concretos, Sócrates, en las otras). Para tratar lógicamente este tipo de estructuras deductivas es preciso crear una teoría que no tome como base la simbolización matemática de la proposición total sino la de sus 3

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

componentes. Así, la lógica de predicados estudia las frases declarativas con mayor grado de detalle, considerando la estructura interna de las proposiciones. Se tomara como elemento básico los objetos y las relaciones entre dichos objetos. Es decir, se distingue:



Qué se afirma (predicado o relación).



De quién o quiénes se afirma (sujeto, término u objeto).

El primer elemento se define como el predicado y el segundo, como los sujetos o términos. Así en la frase: “Ana es estudiosa”; “es estudiosa” es el predicado, y “Ana”, el sujeto o término de la proposición. Asimismo, puede haber proposiciones con varios términos, por ejemplo: “Cuatro está entre tres y cinco”. En este caso el predicado es “… está entre … y …”, y los términos son: cuatro, tres y cinco. Los predicados que se refieren a un único término se denominan predicados monádicos. Los que se refieren a varios sujetos se denominan predicados de relación o poliádicos. Según el número de términos pueden ser diádicos, triádicos, … , n-ádicos. La lógica de predicados estudia las frases declarativas considerando la estructura interna de las proposiciones compuesta por los predicados (propiedades que caracterizan un sujeto) y los sujetos (objeto asociado a una determinada propiedad).

A continuación se introducirá los elementos claves del sistema formal de predicados, en donde se identificará: el alfabeto, la sintaxis y la semántica de predicados. Estos elementos se introducirán gradualmente de manera de que sea posible comprender adecuadamente el uso de cada componente del sistema. 2. Simbolización: Alfabeto y Sintaxis Una vez definidos los componentes de la proposición se plantea su representación simbólica sobre la base de términos y predicados. Para la simbolización de términos se supone como base de referencia un dominio genérico, no vacío. Los términos se representan por variables o constantes, cuyos valores posibles forman parte del dominio anterior. x, y, z, t, . . . letras de variables, representan cualquier elemento del dominio. a, b, c, d, . . . letras de constantes, representan elementos concretos del dominio.

4

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

f , g , h . . .o bien, p, q, r,.... , para la simbolización de predicados se utiliza la notación funcional. Así, la proposición “Ana es estudiosa”, que en la lógica proposicional se simboliza con p, en la lógica de predicados se simboliza: p(a), donde p: x es estudiosa; a: Ana. Se denomina forma proposicional o función proposicional, a una expresión que contiene una o más indeterminadas que, al ser reemplazadas por elementos de un conjunto, llamado universo del discurso, se transforma en proposición. Así, la construcción de proposiciones requiere la definición previa de un dominio de términos posibles, es decir un conjunto de elementos de los cuales sea posible obtener los remplazos de las indeterminadas que se encuentran en una forma proposicional. Ejemplo:

U = { 1, 2, 3, 4}

universo de discurso

p(x) : x es par

forma proposicional donde x está indeterminada y puede tomar los valores del conjunto fijado U, así si x = 1, p(x) se convierte en:

p(a) :1 es par

proposición falsa

p(b) : 2 es par

proposición verdadera

Se observa que en “1 es par” y en “2 es par” el predicado se atribuye a sujetos determinados del universo, en estos casos, las proposiciones se denominan proposiciones singulares. Las formas proposicionales pueden aparecer negadas, como en el enunciado “x no es par”, que se simboliza “~p(x)”. También pueden aparecer unidas mediante las conectivas proposicionales binarias con otras formas proposicionales, o con proposiciones, como por ejemplo, “x es un número par, pero y es un número primo”, que se simboliza como “p(x)  q(y)”. Si en una forma compuesta hay por lo menos una forma proposicional como componente, toda la forma compuesta es una forma proposicional. Por ejemplo, “p(a)  (q(b)  r(x))” es una forma proposicional porque contiene a “ r(x) ”. Una forma proposicional es una expresión que contiene una o más indeterminadas que, al ser reemplazadas por elementos de un conjunto, llamado universo del discurso, se transforma en proposición. Las formas proposicionales pueden ser singulares o compuestas (conformadas por una o más singulares). 5

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

Actividad 1: Considerando el concepto y la definición de forma proposicional, responda los siguientes ítems: 1.1. ¿Qué son y que función cumplen las indeterminadas en una expresión? 1.2. ¿Qué es el conjunto universal, y que función cumple dentro de la lógica de predicados? 1.3. ¿Cuál es el procedimientos de reemplazo de indeterminadas por constantes y que efectos produce dentro de una expresión en la lógica de predicados? Actividad 2: Proponga dos ejemplos de sustitución verdaderos y dos ejemplos de sustitución falsos para cada una de ellas: 2.1. x es un buen abogado. 2.2. x es mayor o igual que y. 2.3. x es número par múltiplo de 6. 2.4. x es divisor de pero no de z. 2.5. x2 + 2 = 11. Actividad 3: En cada uno de los siguientes enunciados deberá: a) Distinguir entre sujetos y predicados. b) Simbolizarlos. c) Clasificar las formas proposicionales. 3.1. x es un número. 3.2. 8 es par. 3.3. 5 es un número pero no es par. 3.4. No se da el caso de que x sea par. 3.5. No es cierto que 4 sea impar. 3.6. La Matemática es exacta. 3.7. La Matemática y la Lógica son ciencias formales. 3.8. 2 es par y primo. 3.9. 4 es par o 5 es primo. 3.10. Si 6 es mayor que 3 y 3 es mayor que 2, entonces, 6 es mayor que 2. 3.11. Si x es par, entonces es múltiplo de 2. 3.12. Juan baila el tango. 3.14. x está entre y y z. 3.15. Si Santiago del Estero está al norte de Córdoba entonces está al norte de La Pampa. 6

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

3. Semántica: Conjunto de verdad Una forma proposicional se convierte en proposición al insertar constantes en los lugares de las variables. Si como resultado de reemplazar las variables por constantes (y naturalmente, de constantes iguales en lugar de variables iguales), se obtiene una proposición verdadera, diremos que los objetos designados por esas constantes satisfacen la forma proposicional dada. El conjunto formado por las constantes que satisfacen la forma proposicional dada, se denomina conjunto de verdad. O sea: P = { a  U / p(a) es V } En el ejemplo presentado anteriormente: U = { 1, 2, 3, 4 }

universo de discurso

p(x) : x es par

forma proposicional

p(a) :1 es par

proposición falsa

p(b) : 2 es par

proposición verdadera

p(c) : 3 es par

proposición falsa

p(d) : 4 es par

proposición verdadera

Luego, el conjunto de verdad de la forma proposicional p(x) es P = { 2 , 4 } El conjunto formado por las constantes que satisfacen la forma proposicional dada, se denomina conjunto de verdad. Observar que: mientras p(x) está escrito en lenguaje lógico, P = { 2 , 4 } está escrito en lenguaje de la teoría de conjuntos. Conjunto de verdad de la forma proposicional p(x): P { a  U / p(a) es V } = { a  U / p(a) es F } = { a  U / a  P } = P Conjunto de verdad de la forma proposicional p(x)  q(x): P  Q Sea Q = { a  U / q(a) es V } el conjunto de verdad de q(x). { a  U / p(a)  q(a) es V } = { a  U / p(a) es V  q(a) es V } = ={ a  U / a  P  a  Q } = P  Q Conjunto de verdad de la forma proposicional p(x)  q(x): P  Q { a  U / p(a)  q(a) es V } = { a  U / p(a) es V  q(a) es V } = ={aU/aP  aQ} = PQ 7

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

Conjunto de verdad de la forma proposicional p(x)  q(x): 𝐏  Q { a  U / p(a)  q(a) es V } = { a  U / p(a)  q(a) es V } = = { a  U / p(a) es V  q(a) es V } = { a  U / a  P  a  Q } =  PQ - Compruebe que el conjunto de verdad de la forma proposicional p(x)  q(x) es   P)   Q)  (Q (P

o bien

) (P  Q)  (PQ

Actividad 4: Considere el conjunto universal correspondiente a una forma proposicional dada y analice el conjunto de verdad relacionado a dicha forma. 4.1. ¿Qué relación hay entre el conjunto universal y el conjunto de verdad? 4.2. ¿Qué diferencia tiene el conjunto de verdad de una forma proposicional monádica con el conjunto de verdad de una forma proposicional diádica y con una n-ádica? Actividad 5: Simbolice las siguientes formas proposicionales y determine sus respectivos conjuntos de verdad: 5.1. U = N ; x + 5 = 8 5.2. U = N ; x2 = 49 5.3. U = Z ; x2 = 49 5.4. U = R ; |x| = 5 5.5. U = R ; |x| < 3 5.6. U = R ; |x|  4 5.7. U = R ; |x + 2| = 4 5.8. U = R ; |x + 2| ≤ 5 5.9. U = R ; |x – 2| > 4 5.10. U = R ; |2x + 6|  10 5.11. U = R ; Si 2x + 3 = 7, entonces |x| ≤ 3 5.12. U = R ; |2x + 1| < 5 y 0  x  4 5.13. U = R ; O bien |x| ≤ 2, o bien |x|  2 5.14. U = R ; |2x| = 10 sí y sólo sí x = 5 ó x = –5 5.15. U = R ; Si 2x + 2 = 4, entonces |x| 4 4. Simbolización Cuantificadores: Alfabeto, Sintaxis y Conjunto de Verdad Considere el siguiente ejercicio, dado el conjunto universal U = { 1, 2, 3, 4, 5} y las formas proposicionales: 8

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

a) p (x) : x  5 b) q (x) : x > 5 c) r (x) : x < 4 d) s (x) : x no es par Encuentre el conjunto de verdad correspondiente. a) En este caso, si se reemplaza la variable “x” por constantes numéricas cualesquiera de U, se obtiene siempre una fórmula verdadera. O sea que si P es el conjunto de verdad de p(x), se tiene que: P = { 1, 2, 3, 4, 5 } = U. Este hecho se expresa del siguiente modo: “Para todo número “x” del universo, x  5”. La expresión así obtenida es una proposición y, más aún, es una proposición verdadera, y se la denomina proposición universal. Para simbolizarla, la lógica usa un operador llamado cuantificador universal: x  U : p(x), o bien x : p(x), que se lee “para todo x del universo, se verifica la propiedad p”. En el lenguaje corriente las palabras que están estrechamente relacionadas con el cuantificador universal son, entre otras: cada, todo, cualquiera, cualesquiera, cada uno, etc. b) En esta situación, vemos que ningún elemento del universo transforma a la forma proposicional en una proposición verdadera. Si se denomina Q al conjunto de verdad de q(x), se tiene que: Q = { }. Se expresa: “Para ningún número x del universo, se verifica que x > 5”, y simbolizamos: x  U : ~q(x); o bien: x : ~q(x). En lenguaje corriente, otras expresiones son: nada, ninguno, ningún, nadie, etc. Estas expresiones tienen una doble función, cuantificar universalmente y negar. Así, puede entenderse como el contrario de una fórmula universal afirmativa. Mientras que las formas proposicionales no son verdaderas ni falsas, las proposiciones universales son verdaderas cuando todos los casos de sustitución son verdaderos, y son falsas cuando hay por lo menos un caso de sustitución falso. c) En este caso, algunos elementos del conjunto universal satisfacen r (x). Su conjunto de verdad es: R = {1, 2, 3 }; o sea, R  U. Se expresa: “Existe un x del universo, tal que verifica que x < 4”. Se simboliza: x  U : r(x); o bien, x : r(x). El operador  se denomina cuantificador existencial y transforma a la forma proposicional en una proposición existencial, ya que al anteponer el cuantificador, tiene sentido decir que la expresión es V o F. 9

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

Otras expresiones que originan proposiciones existenciales son: algo, alguien, hay, unos, alguno, hay cosas, algún, etc. d) En este caso, algunos elementos del conjunto universal satisfacen ~r (x). Su conjunto de verdad es: R = {1, 3, 5}; o sea, R  U. Se expresa: “Existe un x del universo, tal que verifica que x no es par”. Se simboliza: x  U : ~r(x); o bien, x : ~r(x). Estas expresiones tienen una doble función, cuantificar existencialmente y negar. Así, puede entenderse como el subcontrario de una fórmula existencial afirmativa. Mientras que las formas proposicionales no son verdaderas ni falsas, las proposiciones existenciales son verdaderas cuando hay por lo menos un caso de sustitución verdadero, y son falsas cuando todos los casos de sustitución son falsos.

A continuación distinguiremos las proposiciones generales simples y aquellas que se denominan proposiciones generales complejas donde analizaremos algunos aspectos formales que son importantes analizar. Cuantificación Simple Se denominan proposiciones generales simples a las proposiciones que tienen un único predicado, y son universales o existenciales. Por ejemplo: Alguno estudia. Todos cantan. Las proposiciones generales simples pueden unirse mediante las conectivas proposicionales diádicas con enunciados singulares, con funciones proposicionales, o con otras proposiciones generales. Por ejemplo: Alguno estudia pero todos aprueban. Si todos cantan entonces nadie escucha. Actividad 6: Simbolice los siguientes ejemplos: a) Todo es perecedero.

b) No todo es perecedero.

c) Nada es perecedero.

d) Algo no es perecedero.

e) Si Marta llega, todos saldremos.

f) Nadie canta.

g) Alguien llega tarde.

h) Nadie contesta.

i) Cualquiera escucha música.

j) Cada uno mira su celular. 10

Lógica I – Guías N° 3 – Licenciatura en Sistemas de Información

k) Si unos escriben, otros miran.

l) x canta aunque todos estudian.

m) Todo cambia.

n) No todos escuchan.

o) Nadie atiende.

p) Algunos son primos.

q) Si x grita, todos saldremos.

r) Nadie pasa al pizarrón.

Alcance de un cuantificador. Variables libres y ligadas. Si un cuantificador no va seguido por un signo de puntuación (paréntesis, corchete o llave), su alcance llega hasta la(s) variable(s) correspondiente(s) a la primera letra de predicado a su derecha. Por ejemplo, en la forma x : p(x) el alcance del cuantificador llega hasta la x de la forma ‘p(x)’, y en la forma x : p(x)  q(x) llega hasta la x de ‘p(x)’, y no a la x de ‘q(x)’. Si el cuantificador va seguido de un signo de puntuación izquierdo, su alcance llegará hasta el signo de puntuación derecho, o sea, que su alcance se extenderá a toda la expresión encerrada dentro de los paréntesis, corchetes o llaves. Por ejemplo, en la forma x : (p(x)  q(x)) las dos veces que la variable se encuentra dentro de los paréntesis cae bajo el alcance del cuantificador. En la forma x: [(p(x)  q(x)) v h(x)] las tres variables dentro de los corchetes están en el alcance. Se llaman variables ligadas las variables que caen bajo el alcance de un cuantificador; y se llaman variables libres aquellas que no caen bajo el alcance de un cuantificador. Se puede ahora definir forma o función proposicional como aquella forma cuantificacional que tiene por lo menos una variable libre. Si un cuantificador no va seguido por un signo de puntuación (paréntesis, corchete o llave), su alcance llega hasta la(s) variable(s) correspondiente(s) a la primera letra de predicado a su derecha. Se llaman variables ligadas las variables que caen ...