CENTRO EDUCATIVO DE NIVEL TERCIARIO N° 2 INTRODUCCIÓN A LA LOGICA SIMBOLICA PRIMER AÑO GUIA DE TRABAJOS TEÓRICO PRACTICOS Nº3: LOGICA DE PREDICADOS 1.-Estructura de las proposiciones El desarrollo del cálculo proposicional se basa en entidades matemáticas representativas de unidades de información, cuya estructura se contempla como un todo, sin diferenciar sus componentes. Este planteamiento no permite representar matemáticamente determinadas estructuras deductivas, que, sin embargo, son correctas en el lenguaje usual. Así, por ejemplo, el razonamiento: Todos los hombres son mortales. Sócrates es hombre. Luego, Socrates es mortal. Esta estructura deductiva, tratada con la hipótesis que sirve de base al cálculo proposicional, tendría la siguiente representación matemática:

p q r Por tanto, ninguna de las proposiciones p, q, r, puede 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 este nivel de representación. Esto se debe a que 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, Socrates, en las otras), por ello, para tratar matemáticamente 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 componentes, es decir: 1 Lógica de Predicados

Lucía Hilal

• Qué se afirma. • De quién o quiénes se afirma El primer elemento se define como el predicado y el segundo, como los sujetos o términos. Así en la frase: • Juan es negro. “Es negro” es el predicado y “Juan” el sujeto o término de la proposición. Puede haber proposiciones con varios términos, por ejemplo: • Juanita está en clase entre Pedro y Manuela. En este caso el predicado es “-- está en clase entre -- y --” y los términos son Juanita, Pedro y Manuela. Los predicados que se refieren a un único término se denominan predicados absolutos o 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, etc.).

2.-Simbolización Una vez definidos los componentes de la proposición se plantea su representación matemática en base a 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. Para la simbolización de predicados se utiliza la notación funcional: f , g , h . . . Así, la proposición “Juan es negro”, que en la lógica proposicional se simboliza con p, en la lógica de predicados queda: f (a) o bien n (j) donde n: ser negro; j: Juan. De la misma manera: 2 Lógica de Predicados

Lucía Hilal

x es negro → n (x) Juanita está en clase entre Pedro y Manuela → f (a, b, c,) x está en clase entre y y z → f (x, y, z) donde los sujetos x, y ,z están indeterminados. Definición: 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 fijado (dominio de la variable) se transforma en proposición. Luego, la construcción de proposiciones requiere la definición previa de un dominio de términos posibles. 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 funciones proposicionales pueden aparecer negadas, como en el enunciado “Fulano no es americano”, que se simboliza ‘~Fx’. También pueden aparecer unidas mediante las conectivas proposicionales binarias con otras funciones proposicionales, o con enunciados singulares, como por ejemplo, “x es un número par pero y es un número primo”, que se simboliza ‘p(x) ∧ q(x)’. Si en una forma compuesta hay por lo menos una función proposicional como componente, toda la forma compuesta es una función proposicional.

Por ejemplo, ‘p(a) ∧(q(b) ∨ r(x))’ es una función proposicional porque

contiene a ‘r(x)’. Actividad 1: Simbolizar las siguientes formas proposicionales y proponer dos ejemplos de sustitución verdaderos y dos ejemplos de sustitución falsos para cada una de ellas: 1.1.- x es estudiante de la UCSE 3 Lógica de Predicados

Lucía Hilal

1.2.- x es alumno de Algebra I 1.3.- x es número impar. 1.4.- x es múltiplo de 2 Actividad 2: En cada uno de los siguientes enunciados deberá: *)Distinguir las formas proposicionales de las proposiciones. **)Señalar y simbolizar los sujetos y los predicados. ***)Traducirlos al lenguaje simbólico de la lógica de predicados. 2.1.- x es un número. 2.2.- x no es un número. 2.3.- 7 es un número impar. 2.4.- x es un número par. 2.5.- 5 es un número pero no es par. 2.6.- No se da el caso de que x sea un número par. 2.7.- No es cierto que 4 sea un número impar. 2.8.- La Matemática es exacta. 2.9.- La Matemática y la Lógica son exactas. 2.10.- La Lógica es exacta y bivalente. 2.11.- x es múltiplo de y. 2.12.- x es múltiplo de 3.

3.-Conjunto de verdad. El papel de las variables se ha comparado acertadamente muchas veces con el de los espacios vacíos de los cuestionarios:

Una función proposicional no se convierte en

proposición hasta no insertar constantes en los lugares de las variables.

Si como

resultado de reemplazar constantes en lugar de variables (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 función proposicional dada. 4 Lógica de Predicados

Lucía Hilal

El conjunto formado por las constantes que satisfacen la función 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

El conjunto de verdad de la forma proposicional p(x) es, P = { 2, 4} Se debe observar que mientras p(x) está escrito en lenguaje lógico, P = { 2, 4} está escrito en lenguaje de la teoría de conjuntos Actividad 3: Simbolizar las siguientes formas proposicionales y determinar sus respectivos conjuntos de verdad: 3.1.- U = N ; x + 3 = 8 3.2.- U = Z ; 3 - x = 8 3.3.- U = N ; x2 = 25 3.4.- U = Z ; x2 = 25 3.5.- U = Z ; x + 2 = 8 3.6.- U = R ; |x + 2| = 8 3.7.- U = R ; x2 + 2 = 0 3.8.- U = R ; |x| < 5 3.9.- U = R ; |x| ≥ 3

4.-Cuantificadores Consideremos el siguiente ejercicio: 5 Lógica de Predicados

Lucía Hilal

• Dado el conjunto universal U = { x / x proposicionales:

es un nro. dígito } y las funciones

a) p (x) : x ≤ 9 b) q (x) : x > 9 c) r (x) : x < 5 Encontrar el conjunto de verdad correspondiente. a) En este caso, se trata de una función proposicional que contiene una variable, “x” y que es satisfecha por cualquier número perteneciente a U; si colocamos constantes numéricas cualesquiera en lugar de fórmula verdadera.

“x”

obtenemos siempre una

O sea que si llamamos P al conjunto de verdad de p (x)

tenemos que: P = { 0, 1, . . ., 9} = U. Expresamos este hecho del siguiente modo: “Para todo número x del universo, x ≤ 9”. La expresión así obtenida es una proposición y, más aún, 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 universal, se verifica la

propiedad p” En el lenguaje corriente no se hace uso, por lo general, de variables sino de ciertas palabras que están estrechamente relacionadas con los cuantificadores; son, entre otras: cada, todo, cualquiera, cualesquiera, cada uno, etc. b) Analizando esta situación, vemos que ningún elemento del universal transforma a la función proposicional en proposición verdadera. Si llamamos Q al conjunto de verdad de q(x) tendremos: Q={ }

Expresamos: “Para todo número x del universo, se verifica x > 9” y simbolizamos: ∀x ∈ U : ~ p(x)

o bien

∀x : ~ p(x)

En lenguaje corriente otras expresiones son: ninguno, ningún, nadie, nada, etc. Estas tienen una doble función, cuantificar universalmente y negar. 6 Lógica de Predicados

Lucía Hilal

c) En este caso, algunos elementos del conjunto universal satisfacen r (x). Su conjunto de verdad es: R = { 1, 2, 3, 4 } o sea R ⊂ U Enunciamos: “Existe un x del universo tal que verifica x < 5” Simbolizamos: ∃ x ∈ U : r (x)

∃x : r (x)

o bien

El operador ∃ se denomina cuantificador existencial y transforma a la función proposicional en una proposición existencial ya que al anteponer el cuantificador, tiene sentido decir que es V o F. Otras expresiones que originan proposiciones existenciales son : algo, alguien, hay, unos, alguno, hay cosas, algún, etc. Mientras que una función proposicional no es verdadera ni falsa, las proposiciones existenciales son verdaderas cuando hay por lo menos un caso de sustitución que sea verdadero y son falsas cuando no hay ningún caso de sustitución que la haga verdadera.

5.-Cuantificación Simple Se denominan proposiciones generales simples las proposiciones que tienen un único predicado, y son universales o existenciales. Las

proposiciones

generales

simples

pueden

unirse

mediante

las

conectivas

proposicionales diádicas con enunciados singulares, con funciones proposicionales, y con otras proposiciones generales. Simbolizaremos los siguientes ejemplos: a) Todo es perecedero. p(x) : x es perecedero ∀x : p(x) b) No todo es perecedero. ~ ∀x : p(x) c) Nada se mueve. m(x) : x se mueve ∀x : ~ m(x) d) Alguien no es perfecto. 7 Lógica de Predicados

Lucía Hilal

q(x) : x es perfecto ∃x : ~ q(x) e) Si Marta llega, todos saldremos. f(a) : Marta llega

g(x): x sale

f(a) ⇒ ∀x : g(x) Actividad 4: Simbolizar las siguientes proposiciones que contienen cuantificadores considerando como universo el conjunto de alumnos de este curso: 4.1. Todos llegaron a tiempo 4.2. Algunos estudian pero otros no 4.3. Hay alumnos estudiosos 4.4. Ninguno fuma en clase 4.5. Todos estudian aunque algunos no aprueban 4.6. Unos preparan la teoría o todos se reúnen por las tardes

6.-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 función ‘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)’. En cambio, 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 variables dentro de los paréntesis caen bajo el alcance del cuantificador, y en la forma ‘(∃x)[( p(x)⇒q(x))vh(x)]’ las tres variables dentro de los corchetes también. Se llaman variables ligadas las variables que caen bajo el alcance de un cuantificador; y se llaman variables libres aquellas que o bien no tienen un cuantificador correspondiente, o bien no caen bajo el alcance de un cuantificador Podemos ahora definir función proposicional como aquella forma cuantificacional que tiene, por lo menos, una variable libre.

8 Lógica de Predicados

Lucía Hilal

Actividad 5: Dadas las siguientes formas cuantificacionales, indicar cuáles representan funciones proposicionales, y marcar sus variables libres: 5.1.- ∀x : p(x) ^ q(x) 5.2.- ∀x : (p(x) ^ q(x)) 5.3.- ∃ x / x < 5 v x + 2 = 7 5.4.- ∃ x / (x > 2 ^ x ≤ 9) ⇒ x = 10 5.5.- ∀x : (p(x) ^ q(x)) v q(x) 5.6.- ∀x : x > 3 ⇒ x + y = 9 5.7.- ∃ y ∀x : x + y = 2

7.-Las proposiciones generales complejas categóricas Las proposiciones generales complejas son aquellas proposiciones universales o existenciales que poseen más de una letra de predicado bajo el alcance de un cuantificador universal o existencial. En este parágrafo nos ocuparemos de un tipo de proposiciones generales complejas, que son las que la lógica tradicional denominaba proposiciones categóricas. Hay cuatro tipos de proposiciones categóricas: 1)

Tipo A, o universales afirmativas.

Son ejemplos de este tipo los siguientes

enunciados, que poseen un mismo significado: Todas las hormigas son insectos. Cualquier hormiga es insecto. Las hormigas son insectos. Si algo es hormiga, entonces es insecto. Pueden darse también otras formulaciones equivalentes. Todos ellos pueden parafrasearse mediante la expresión ‘para todo x, si x es hormiga, entonces x es insecto’ y son simbolizados mediante la forma ‘∀x : (p(x)⇒q(x))’, que es la cuantificación universal de la función proposicional condicional ‘si x es hormiga, entonces x es insecto’, o sea, ‘p(x)⇒q(x)’. Las proposiciones de este tipo son verdaderas cuando todos los casos de sustitución de la función proposicional ‘p(x)⇒q(x)’ son verdaderos, y es falsa cuando hay por lo menos un caso de sustitución que es falsa. Son los llamados 9 Lógica de Predicados

Lucía Hilal

condicionales generalizados donde el condicional surge al analizarse la estructura interna de las proposiciones, y no como una conectiva que liga dos proposiciones, tal como se da en la lógica proposicional. En este tipo de enunciados, así como en los que seguiremos presentando, no coincide el predicado gramatical con el predicado lógico, pues ‘ser hormiga’ es para la lógica un predicado, tanto como ‘ser insecto’, mientras que gramaticalmente ‘hormiga’ es sujeto. La lógica tradicional simboliza este tipo de enunciados mediante el esquema ‘Todo S es P’, coincidiendo con el análisis gramatical. Al igual que las proposiciones generales simples, los enunciados de tipo A pueden darse negados, como por ejemplo; ‘No todos los elefantes son africanos’, que se simboliza ‘~∀x : (p(x)⇒q(x))’ 2) Tipo E, o universales negativas. Son ejemplos de este tipo los enunciados. Ninguna hormiga es insecto. Las hormigas no son insectos. Nada que sea hormiga es insecto. y otros giros equivalentes, que pueden parafrasearse ‘para todo x, si x hormiga, entonces x no es insecto’, y son simbolizados por la forma ‘∀x : (p(x)⇒ ~q(x))’. Tanto el condicional como la negación surgen del análisis interno de las proposiciones. Como con los de tipo A, estos enunciados son verdaderos cuando todos los casos de sustitución de la función proposicional ‘p(x)⇒ ~q(x)”son verdaderos, y son falsos cuando hay por lo menos un caso de sustitución falso. La lógica tradicional los simbolizaba mediante el esquema ‘Ningún S es P”. También pueden darse, negados como el enunciado ‘No es cierto que ningún elefante es asiático’, que se simboliza ~ ‘∀x : (p(x)⇒ ~q(x))’. 3) Tipo I, o particulares afirmativos. Como los enunciados existenciales: Algunos perros son negros. Ciertos perros son negros. Algún perro es negro. Hay perros negros. 10 Lógica de Predicados

Lucía Hilal

y otras posibles formulaciones que tengan el mismo significado. Todas ellas pueden parafrasearse mediante ‘existe por lo menos un x tal que x es perro y x es negro’, y se los simboliza ‘∃x : (p(x) ∧ q(x))’. Son la cuantificación existencial de la función proposicional compuesta ‘p(x) ∧ q(x)’. La conjunción es la conectiva que registra más adecuadamente el significado de este tipo de proposiciones, y no el condicional, pues el sentido de estos enunciados no es, por ejemplo, afirmar que ‘existe por lo menos un x, tal que si es perro entonces es negro’, sino más bien que ‘hay por lo menos un x que es a la vez perro y negro’. En cuanto a las condiciones que los hacen verdaderos, son verdaderos cuando hay por lo menos un caso de sustitución de la función proposicional p(x) ∧ q(x) que es verdadera, y son falsos cuando no hay ningún caso de sustitución que los hace verdaderos. La lógica tradicional los representaba mediante la forma ‘Algún S es P’. Si aparecen negados, como en el enunciado ‘No es cierto que hay vacas rojas’ se los simboliza mediante ‘~∃x : (p(x) ∧ q(x))’. 4) Tipo O, o particulares negativos. Como los enunciados: Algunos perros no son negros. Ciertos perros no son negros. Algún perro no es negro. Hay perros que no son negros. que pueden parafrasease mediante ‘existe por lo menos un x tal que x es perro y x no es negro’, y se simbolizan ∃x : (p(x) ∧ ~ q(x)), donde tanto la conjunción como la negación surgen del análisis interno de los enunciados. Son verdaderos cuando hay por lo menos un caso de sustitución de la función proposicional p(x) ∧ ~ q(x), que es verdadera, y son falsos cuando no hay ninguno de ellos que sea verdadero. La lógica tradicional los simboliza mediante ‘Algún S no es P’. Pueden darse negados, como el enunciado ‘No hay pájaros que no vuelen’, que se simboliza ~ ∃x : (p(x) ∧ ~ q(x)).

11 Lógica de Predicados

Lucía Hilal

Actividad 6: Simbolizar los siguientes enunciados e indicar a que tipo corresponden: a) Algunos trabajos son insalubres. b) Hay osos blancos. c) No todas las tortugas son acuáticas. d) Ningún ruiseñor vive en cautiverio. e) Algunos caminos no han sido reparados. f) Ningún mal dura cien años. g) Todo número entero es múltiplo de 3. h) Todos los números pares son divisibles por 2. i) Algunos números naturales pares son múltiplos de 3. j) Cualquier número natural par es múltiplo de 2 pero algunos son múltiplos de 6. k) Todos los números negativos son menores que cero. l) No todos los números son positivos.

8.-Leyes de la lógica cuantificacional Las leyes de la lógica son formas de enunciados cuyos casos de sustitución son siempre enunciados verdaderos. Las leyes de la lógica cuantificacional difieren en las leyes de la lógica proposicional en que estas últimas coincidían con las tautológicas, mientras que las leyes cuantificacionales no. En primer lugar son leyes de la lógica cuantificacional las correspondientes de la lógica proposicional, para formas cuantificacionales. Por ejemplo, la ley de identidad de la lógica proposicional, ‘p ⇒ p’ y ‘p ≡ p’, tiene en la lógica cuantificacional las siguientes leyes: Fa ⇒ Fa, ∀x Fx ⇒ Fx, (∃x) Fx ⇒ (∃x) Fx, ... Fa ≡ Fa, ∀x Fx ≡ Fx, (∃x) Fx ≡ (∃x) Fx, ... En segundo lugar están las leyes propias de la lógica cuantificacional que no se corresponden con ninguna ley proposicional y son las que involucran como parte esencial a los cuantificadores. 12 Lógica de Predicados

Lucía Hilal

Enumeraremos las más importantes: • Leyes de Intercambio de cuantificadores ∀x : f(x) ≡ ∼ ∃x : ∼ f(x) ∀x : ∼ f(x) ≡ ∼ ∃x : ∼ f(x) ∃x : f(x) ≡ ∼ ∀x : ∼ f(x) ∃x : ∼ f(x) ≡ ∼ ∀x : f(x) • Leyes de Distribución de cuantificadores ∀x : (f(x) ∧ g(x) ) ≡ ( ∀x : f(x) ∧ ∀x : g(x) ) ∃x : ( f(x) ∨ g(x) ) ≡ ( ∃x : f(x) ∨ ∃x : g(x) ) En los otros casos no se cumplen las equivalencias (∀x : f(x) ∨ ∀x : g(x) ) ⇒ ∀x : ( f(x) ∨ g(x) ) ∃x : ( f(x) ∧ g(x) ) ⇒ ( ∃x : f(x) ∧ ∃x : g(x) )

El hexágono de la conmutatividad de los cuantificadores (o de Prior) La cuantificación de funciones diádicas simples (predicados que se refieren a dos sujetos) da lugar a ocho fórmulas posibles de combinación de cuantificadores, generan entre sí una serie de relaciones de deducibilidad que pueden resumirse en un hexágono que se abre con la ley de la conmutación para los cuantificadores universales homogénea y se cierra con la de los cuantificadores existenciales homogéneos (cuantificadores del mismo tipo). ∀x ∀y : f(x,y) ≡ ∀x ∀y: f(x,y)

∃x ∀y : f(x,y) ∀y ∃x: f(x,y)

∃y ∀x : f(x,y) ∀x ∃y : f(x,y)

∃y ∃x : f(x,y) ≡ ∃x ∃y : f(x,y) 13 Lógica de Predicados

Lucía Hilal

Actividad 7: Simbolizar cada enunciado, negar la expresión obtenida y retraducirla al lenguaje coloquial: 7.1. Todo el que la conoce, la admira. 7.2. Algunos números naturales son primos. 7.3. Las proposiciones compuestas contienen términos de enlace. 7.4. Hay personas honestas y otras son indiferentes. 7.5. Si cada alumno cumple sus obligaciones, entonces todos aprobarán el parcial. Actividad 8: Transformar las siguientes fórmulas, siempre que sea posible, mediante la distribución de los cuantificadores: 8.1.- ∃ x / (p(x) v - q(x)) 8.2.- ∀x : (p(x) ^ q(x) ^ r(x)) 8.3.- ∀x : (-p(x) v -q(x)) 8.4.- ∃ x / (p(x) ^ q(x)) 8.5.- ∀x : p(x) ^ ∀x :(q(x) ⇒ r(x)) 8.6.- ∀x : p(x) v ∀x : q(x)

14 Lógica de Predicados

Lucía Hilal