Download R - Universidad Autónoma de Guerrero

UNIVERSIDAD AUTÓNOMA DE
GUERRERO
UNIDAD ACADÉMICA DE INGENIERÍA
ACADEMIA DE COMPUTACIÓN
APUNTES DE LÓGICA INFORMÁTICA
LÓGICA INFORMÁTICA
ANGELINO FELICIANO MORALES
Enero de 2012
Elaboró:afmorales
Introducción
La elaboración de estos apuntes de Lógica Informática tiene como única finalidad el
proporcionar a los estudiantes que cursan ésta Unidad de Aprendizaje que se imparte
el Programa Educativo de Ingeniería en Computación de la Unidad Académica
Ingeniería, sea un material de apoyo para reforzar las actividades académicas
enseñanza − aprendizaje.
de
en
de
de
Dado que, la mayoría de estudiantes vienen de distintos lugares de nuestro estado, los
cuales representan un alto porcentaje de la población escolar que asiste a la Unidad
Académica son de escasos recursos económicos y considerando que el costo de los libros
es elevado, el estudiante no tienen la oportunidad de poder dotarse de una buena
bibliografía personal que les permita satisfacer sus necesidades de consulta. Por tanto,
estas notas son una alternativa para cubrir dicha necesidad.
Por otro lado se sabe que la educación es de vital importancia para el desarrollo integral
del ser humano y esto se logra precisamente alcanzando un buen nivel académico. Con
esta formación se tiene la posibilidad ser útil y contribuir en el desarrollo de la sociedad.
De ninguna manera se pretende que el material sea un trabajo terminado, porque se
puede mejorar con las aportaciones, críticas de los profesores y estudiantes. Se espera
que los estudiantes contribuyan con sus aportaciones, debido a que ellos son los que les
toca padecer las deficiencias que en algunas ocasiones se presentan en la práctica
docente.
ANGELINO FELICIANO MORALES
Elaboró:afmorales
ÍNDICE
PRIMER CAPÍTULO
1.0 CONCEPTOS GENERALES
1.1 Introducción
1.2 Proposiciones simples
1.3 Proposiciones compuestas y conectivos lógicos
1.4 Propuestas de equivalencias de los conectivos lógicos
1.5 Lenguaje
1.6 Expresiones del Lenguaje
1.7 Reglas de prioridad
1.8 Fórmulas bien formadas
1.9 Formalización de enunciados
1.10 Fórmulas proposicionales y tablas de verdad
1.11Tablas de verdad de los conectivos lógicos
1.12 Clasificación de tablas de verdad
1.13 Tablas Semánticas
Problemas propuestos
SEGUNDO CAPÍTULO
2.0 MÉTODOS DE DEDUCCIÓN NATURAL
2.1 Introducción
2.2 Método directo
2.3 Método indirecto(Método de Reducción al Absurdo)
Problemas propuestos
TERCER CAPÍTULO
3.0 LÓGICA DE PREDICADOS
3.1 Introducción
3.2 El lenguaje de la lógica de predicados
3.3 El universo del discurso
3.4 Formalización de enunciados
3.5 Sintaxis de fórmulas bien formadas
3.6 Esquema de formalización de enunciados
3.7 Negación de cuantificadores
3.8 Procedimiento para la deducción en el cálculo de predicados
Problemas propuestos
CUARTO CAPÍTILO
4.0 RELACIONES Y GRAFOS
4.1 Introducción
4.2 Producto Cartesiano
4.3 Relaciones
01
02
02
03
04
04
05
05
06
08
09
11
12
19
19
24
29
30
32
34
37
39
42
43
51
51
53
Elaboró:afmorales
4.4.Dominios y rangos
4.5 Algunas operaciones
4.6 Propiedades de las relaciones
4.7 Cerradura de relaciones
4.4 Grafos
BIBLIOGRAFÍA
Elaboró:afmorales
56
57
59
64
65
Conceptos Generales
PRIMER CAPÍTULO
1.0 CONCEPTOS GENERALES
“No hay un camino real para la lógica y las ideas realmente
valiosas sólo se pueden obtener brindando atención cuidadosa”.
Charles Sanders Peirce
1.1. Introducción
El lenguaje, como instrumento de comunicación del conocimiento humano, está
constituido por frases de tipo interrogativo, imperativo, exclamativo y declarativo;
éstas últimas constituyen el elemento básico de la descripción del conocimiento.El
conocimiento puede producirse por constataciones de hechos o ideas, que tienen su
reflejo en frases de tipo declarativo, como por deducción, a partir de una serie de
declaraciones, de otras nuevas cuya afirmación se sigue necesariamente de las
declaraciones previas.
En una primera aproximación al concepto de lógica se tiene que iniciar con algo que
todos conocen, por ejemplo a nadie se le escapa el significado que tienen las
palabras cuando se dice: el argumento de esta película es ilógico. Se quiere decir
simplemente, que la película en cuestión carece de orden interno, o que el desenlace
no concuerda con la parte inicial, que hay una falta de coherencia o congruencia
entre las distintas escenas. En este mismo sentido se dice que una persona no es
lógica cuando sus razonamientos son desordenados, es decir, no se encuentra
conexión alguna entre lo que dijo primero y lo que dijo o hizo después.
En cambio, se llamalógica a la persona, la conducta o expresión que presenta
coherencia, orden, concordancia consigo misma. Este es el sentido que se utilizará
durante el curso. Se ha visto que la palabra lógica tiene un sentido usual en nuestro
lenguaje común. Lógica natural es una aptitud para razonar que todo hombre posee
en mayor o menor grado. La lógica científica es una serie de conocimientos teóricos,
enlazados rigurosamente, y que perfeccionan esa aptitud natural. La aptitud lógica
natural es capaz de desarrollo y perfeccionamiento y con el estudio de la lógica
científica se pretende un progreso en la capacidad innata de razonamiento.
La deducción, como proceso mental capaz de generar elementos de conocimiento a
partir de otros, es el objeto de estudio de la lógica formal, cuya estructura planteada
como una enumeración de formas deductivas correctas. Una de las principales
tareas de la lógica es el de proporcionar las reglas por medio de las cuales podemos
determinar cuando un razonamiento o argumento es válido. La lógica estudia las
formas de los argumentos más que los argumentos mismos. Estas reglas deben ser
independientes de argumentos o disciplinas particulares, además de ser
independientes del lenguaje. Cualquier teoría o conjunto de reglas debe expresarse
en un lenguaje. Como en el lenguaje natural se presentan muchas ambigüedades, se
debe desarrollar un lenguaje formal o lenguaje objeto, en el que la sintaxis esté bien
formada.
Elaboró: afmorales
1
Conceptos Generales
Toda disciplina científica desarrolla su propio lenguaje objeto, el cual consiste de
ciertos términos bien definidos y las formas específicas de utilizarlos. Con el fin de
evitar ambigüedades, en el lenguaje formal se deben usar símbolos claramente
definidos, debido a esto, a la lógica se llama lógica simbólica.
1.2 Proposiciones simples
Las unidades básicas, a partir de las cuales articulamos nuestros discursos
argumentativos, se denominan proposiciones simples o atómicas (primitivas). Estas
consisten de expresiones declarativas que no pueden dividirse o analizarse por
medio de expresiones declarativas más sencillas y además, solo puede decirse de
ellas que son verdaderas o falsas. En consecuencia, en el estudio de la lógica solo
se admiten expresiones declarativas.
Ejemplos
1.
2.
3.
4.
5.
6.
7.
La tierra es redonda.
Todas las personas casadas viven juntas.
Ciertas personas son desinhibidas.
cos 2 x + sen 2 x = 1
El triángulo equilátero es isósceles
Un programa es una formulación concreta de un algoritmo.
La estructura de un algoritmo depende de la estructura de los datos.
1.3 Proposiciones compuestas y Conectivos Lógicos
Es evidente que en el proceso de argumentación, no solo se utilizan proposiciones
simples, sino que también se usan proposiciones compuestas, las cuales se forman
uniendo dos o más proposiciones simples con símbolos especiales llamados
conectivos lógicos.
Ejemplos de proposiciones compuestas
1. Si la ballena es un mamífero, entonces la ballena tiene respiración pulmonar.
2. El hombre es responsable si y sólo si el hombre es libre.
3. Los programas son formulaciones concretas de algoritmos abstractos basados en
ciertas representaciones y estructura de datos.
4. La estructura y selección de los algoritmos con frecuencia dependen mucho de la
estructura de los datos subyacentes.
5. Si los datos preceden a los algoritmos, entonces se deben estudiar primero antes
de hacer operaciones con ellos.
6. Un programa es legible solamente si está bien estructurado.
7. Si el producto escalar de dos vectores es cero, entonces los vectores son
ortogonales.
8. Cuando Lorena oye a Cristina Aguilera, se le ilumina la mirada, se le encienden
las mejillas y no puede dejar de bailar.
Elaboró: afmorales
2
Conceptos Generales
Conectivos lógicos
Los conectivos que se han utilizado en las proposiciones compuestas son:
no(negación); y(conjunción); o(disyunción) ; sí ... entonces (condicional o implicación
material); sí y solo sí(bicondicional).
Estas conectivas serán simbolizadas de la siguiente manera.
CONECTIVA
Lenguaje común
NOMBRE
Lenguaje lógico
LECTURA
¬
Negación
no
∧
Conjunción
y
∨
Disyunción
o
→
condicional o implicación
material
↔
Bicondicional
si ..., entonces
si y sólo si
NOTA: Es obvio que se necesita un lenguaje apropiado que permita resolver el
problema de la formalización de enunciados compuestos.
1.4 Propuesta de equivalencias semánticas de conectivos
En la siguiente tabla se mencionan algunas equivalencias semánticas posibles de los
conectivos lógicos para la formalización de enunciados.
NOMBRE DEL
CONECTIVO
CONJUNCIÓN
DISYUNCIÓN
NOTA
CIÓN
∧
∨
LECTURA
Y
O
EQUIVALENCIAS FRECUENTES
además, también, pero, aún, aunque,
sin embargo, “,”, no obstante, a pesar
de que, igualmente, tanto. . . como, e, lo
mismo que, incluye, aún así, ...
o p o q o ambas cosas, al menos p o q,
como mínimo p o q, u, en otro caso, de
otra manera, ya sea que..., elija entre,
...
Elaboró: afmorales
3
Conceptos Generales
NOMBRE DEL
CONECTIVO
NOTA
CIÓN
LECTURA
EQUIVALENCIAS FRECUENTES
NEGACIÓN
¬
NO
no es cierto que, no es el caso que, es
falso que, no es verdad que, ni... ni,
ningún, no ocurre que, tampoco, ...
IMPLICACION
→
DOBLE
IMPLICACION.
↔
p solo si q, q si p, q necesario para p, p
suficiente para q, no p a menos que q,
SI ENTONCES por lo tanto, como consecuencia, así
que..., siempre y cuando…, dado que
..., en la medida que...
p necesario y suficiente para q, p es
SI Y SÓLO SI equivalente a q, igual a, lo mismo que,
cuando y sólo cuando,…
1.5 Lenguaje
El alfabeto de un lenguaje
elementos:
de la lógica proposicional consta de los siguientes
1. Letras para simbolizar proposiciones simples.
P, Q, R, S, T, U,. . . o bien
P, q, r, s, t, u,. . . o
bien con subíndices
y se les llama variables proposicionales.
2. Conectivos: negación, conjunción, disyunción, condicional o implicación
material y bicondicional.
3. Símbolos auxiliares.
paréntesis por la izquierda (, [, {
paréntesis por la derecha ),], }
para evitar ambigüedades semánticas.
1.6 Expresiones del lenguaje
P ∨ ¬Q
((T → P ) ∧ T ) → P
(P → Q ) ∧ (Q → R ) → (P → R )
[(P → Q ) ∧ (R → S )] → [(¬Q ∨ ¬S ) → (¬P ∨ ¬R )]
[(P → Q ) ∧ (R → S )] → [(¬Q ∧ ¬S ) → (¬P ∧ ¬R )]
Elaboró: afmorales
4
Conceptos Generales
1.7 Reglas de prioridad
Muy poca gente trabaja con expresiones completamente entre paréntesis porque
tales expresiones son largas y con frecuencia difíciles de leer. En particular, los
paréntesis externos de una expresión son casi siempre omitidos. Por tanto, en lugar
de ( P ∧ Q) , uno escribe P ∧ Q , y el lugar de (( P ∧ Q) → ( P ∨ Q)) se escribe
( P ∧ Q) → ( P ∨ Q) . Los paréntesis que estén dentro de una expresión también
pueden ser omitidos, utilizando las reglas de prioridad. Generalmente, cada conexión
tiene una prioridad, y las conexiones con una prioridad más alta introducen una unión
más fuerte que las conexiones con una prioridad más baja. La conexión ¬ tiene
siempre la prioridad más alta, es decir ¬ P ∨ Q debe ser comprendida como
(¬ P) ∨ Q , y no como ¬ ( P ∨ Q) . En el caso de las conexiones binarias, la prioridad
más alta se la da a ∧ , seguida por ∨ , → y ↔ , respectivamente.
En la expresión
, la ∧ tiene la prioridad sobre ∨ , es decir, debe ser
entendida como
. Similarmente, la expresión
debe ser
entendida como:
. De igual forma la expresión
se debe
entender como
1.8 Fórmulas bien formada(FBF)
A la expresión del lenguaje se le llama fórmula bien formada (fbf) en los siguientes
casos:
a Toda letra (variable) proposicional de
es una fórmula.
b Si P es una fórmula bien formada, entonces ¬ P es una fórmula bien formada.
c Si P y Q son fórmulas bien formadas, entonces las expresiones:
,
también son fórmulas bien formadas.
,
d Una expresión simbólica que contenga variables proposicionales, conectivos y
paréntesis es una fórmula bien formada si puede obtenerse aplicando los
criterios (a), (b) y (c), un número finito de veces.
Ejemplos de fbf:
1.
2.
3.
4.
Elaboró: afmorales
5
Conceptos Generales
5.
6.
[(P → Q ) ∧ (R → S )] → [(¬Q ∨ ¬S ) → (¬P ∨ ¬R )]
7.
[(P → Q ) ∧ (R → S )] → [(¬Q ∧ ¬S ) → (¬P ∧ ¬R )]
1.9 Formalización de enunciados
Para formalizar un enunciado es necesario seguir una estrategia para intentar
garantizar una mejor traducción de cada uno de los enunciados con los que se
trabajará durante el curso, para ello se propone el siguiente procedimiento.
Comprender el enunciado
 lee una o varias veces el enunciado hasta asegurarte que lo comprendes, es
decir que puedes expresarlo con tus propias palabras y que puedes identificar
los conectivos lógicos implícitos y explícitos que aparecen en ella.
Analizar el enunciado
 Determinar que proposiciones simples están asociadas a los conectivos de
acuerdo con su sentido semántico.
Representar enunciados y conectivos
 Si ya se han identificado la asociación de proposiciones simples y compuestas,
así como los conectivos, entonces lo que se debe hacer es asignar símbolos a
las proposiciones y a los conectivos identificados. Una vez que se han asignado
símbolos a proposiciones y conectivos, entonces se deben agrupar para
construir la fórmula proposicional, de acuerdo con la definición de FBF.
Verificar la fórmula proposicional obtenida
 El proceso no termina con la representación de la proposición, es necesario
asegurarse que la fórmula construida sea verdaderamente una FBF. Para hacer
esta verificación, es necesario preguntarse lo siguiente: ¿La fórmula construida
respeta el sentido del enunciado original? ¿Se estructuro la fórmula de acuerdo
a las reglas de construcción de las fbf? ¿No sobran o faltan paréntesis? ¿No hay
paréntesis abiertos que no se cierran? ¿Los paréntesis realmente delimitan el
alcance de conectivos y proposiciones?
Elaboró: afmorales
6
Conceptos Generales
De manera general, se puede representar el procedimiento del proceso de traducción
en el siguiente esquema.
ACCIONES
COMPRENDER EL
ENUNCIADO
ANALIZAR EL
ENUNCIADO
REPRESENTAR LOS
ENUNCIADOS Y
CONECTIVOS
VERIFICAR LA
FORMULA
PROPOSICIONAL
OPERACIONES
 Leerlo varias veces.
 Expresarlo con tus propias palabras.
 Identificar conectivos lógicos explícitos e implícitos.
 Identificar las proposiciones simples de acuerdo a
su sentido semántico.
 Analizar el alcance de los conectivos tomando como
referencia explícitas los signos de puntuación y el
sentido global de las proposiciones.
 Reescribir Las proposiciones haciendo explicita su
asociación con los conectivos, respetando su
significado original.
 Asignar símbolos estándar a las proposiciones
simples: P, Q, R, . . .
 Asignar símbolos estándar a los conectivos lógicos.
;
;
;
;
.
 Agrupar proposiciones y conectivos, para construir
la fórmula proposicional, de acuerdo con la
definición de FBF.
 Comparar la agrupación de la fórmula resultante con
las reglas de asociación de los conectivos dadas en
la definición de las fórmulas bien formadas.
 Revisar la agrupación de la fórmula en términos de
su delimitación por paréntesis.
 Verificar que la FBF respete el sentido del
enunciado original.
OBTENIDA
Ejemplos de traducción de enunciados:
1. Sean:
P: Marcos es rico
Q: Marcos es feliz
Expresar simbólicamente las siguientes proposiciones.
a.
b.
c.
d.
Marcos es pobre pero feliz.
Marcos es rico e infeliz.
Marcos no es rico ni feliz.
Marcos es pobre o es ambos rico e infeliz.
Elaboró: afmorales
7
Conceptos Generales
2. Obténgase la formalización de los siguientes enunciados.
a.
b.
c.
No es cierto que la lógica sea difícil.
Oí un ruido, escuché atentamente, me agazape.
Si vienes nos la pasaremos estupendamente, pero nos aburriremos si no
vienes.
d. Ni puedo tolerarlo ni puedo prohibirlo.
e. La riqueza ayuda a ser feliz, pero la cultura no.
f.
O se queda o se marcha: no es posible que se quede y se marche.
g. Estos problemas no son muy difíciles para mí, aunque he tardado en
resolverlos.
h. Es agradable caminar bajo la lluvia, siempre que se tenga algo
suficientemente triste en que pensar.
i.
Dedícate al amor libre y verás como te sorprende la muerte en plena felicidad.
j.
Dentro de las convenciones que reconocemos en computación, las que aportó
Wirth son desconocidas mientras que las de Warnier son las más usuales.
k. Martha es prima de Pedro y Juan es primo de Martha, o bien Nancy es la
novia de Pedro y Juan está enamorado de Lucía.
l.
Ni Cristina es novia de Pedro ni José está enamorado de Lucía, pero Martha
es prima de Pedro o José no es primo de Martha.
m. La educación escolar seguirá siendo mala, a menos que los pedagogos
progresistas influyan en los educadores y los convenzan para desarrollar
nuevos métodos, y éstos propicien una capacidad crítica y no sean
fuertemente represores.
1.10 Fórmulas proposicionales y tablas de verdad
Si una proposición es una expresión declarativa entonces su valor de verdad puede
ser: verdadera o falsa. Este valor de verdad de la fórmula proposicional depende de
los valores de verdad de las variables proposicionales que en ellas aparecen.Tabla
de verdad: es un procedimiento gráfico que permite determinar los posibles valores
de verdad de una proposición compuesta. Para construir una tabla de verdad, es
necesario tomar en cuenta el número de proposiciones que intervienen en el
razonamiento y así poder obtener el número de renglones que debe tener dicha
tabla.
En toda tabla de verdad, de cualquier proposición compuesta, se debe anotar en
primer lugar los posibles valores de verdad de las proposiciones simples que en ella
intervienen. Si en la proposición compuesta sólo existe una proposición simple (
),
entonces se tienen dos posibles valores de verdad. Si en la proposición compuesta
hay dos proposiciones simples (
), entonces habrá cuatro posibles
combinaciones de sus valores de verdad. Si en la proposición compuesta hay tres
proposiciones simples (
), entonces serán ocho las posibles combinaciones
de sus valores de verdad. En general, el número de combinaciones de los valores de
verdad de proposiciones simples se puede determinar de acuerdo con la fórmula: 2 n ,
Elaboró: afmorales
8
Conceptos Generales
donde n es el número de proposiciones simples que intervienen en una proposición
compuesta(o en un diagrama de árbol).
Por otro lado, se debe considerar que no existen reglas fijas para llevar a cabo la
formalización del lenguaje común en términos del lenguaje de la lógica de
enunciados, es decir; el lenguaje común es más rico, variado y expresivo que el
lenguaje de la lógica de enunciados siempre habrá que tener en cuenta las
limitaciones que ello impone e intentar retomar, en la medida de lo posible, el sentido
de lo expresado en el lenguaje común.
1.11
Tablas de verdad de los conectivos lógicos
Negación: (
)
La negación de una proposición P es una proposición que es verdadera cuando P es
falsa y falsa cuando P es verdadera.
La tabla de verdad de la negación se presenta a continuación:
¬P
F
V
P
V
F
Ejemplos.
1. El profesor de lógica es impuntual.
2. Pedro es inaguantable.
3. Jorge no ama a María.
Conjunción:
La conjunción de dos proposiciones
es verdadera cuando y sólo cuando
ambas proposiciones son verdaderas y es falsa en cualquier otro caso. Las comas,
en algunos casos, aunque no se tengan también se deben considerar como
conjunción.
La tabla de verdad de la conjunción se muestra a continuación.
V V
V F
P∧Q
V
F
F V
F F
F
F
P Q
Elaboró: afmorales
9
Conceptos Generales
Ejemplos.
1. Susana es rubia e Inés es morena.
2. Sonó el timbre, me dirigí a la puerta, la abrí
3. A María le encantan los caballos, pero a Martha
Disyunción:
La disyunción de dos proposiciones P y Q es verdadera si al menos una de ellas es
verdadera y falsa cuando ambas son falsas.
La tabla de verdad de la disyunción se presenta a continuación.
P
Q
V
V
F
F
V
F
V
F
P∨Q
V
V
V
F
Ejemplos.
1. Se necesitan personas que sepan inglés o francés.
2. O Carmen o Pedro lo conseguirán.
3. Sales o entras
Condicional (Implicación):
La implicación entre dos proposiciones P y Q es verdadera en todos los casos,
excepto cuando el antecedente es verdadero y el consecuente es falso.
Simbólicamente se expresa como:
donde P es el antecedente y Q el
consecuente, representa la relación de causa a efecto que puede construirse en el
leguaje usual de varias formas:
La tabla de verdad del condicional se muestra enseguida.
P
Q
V
V
F
F
V
F
V
F
P→Q
V
F
V
V
Elaboró: afmorales
10
Conceptos Generales
Ejemplos:
1.
2.
3.
4.
5.
6.
Si te gusta, te lo regalaré.
Cuando vengas, te lo mostraré.
Pagaré, solamente si vale la pena.
Siempre que vienes, te enfadas
Pienso, luego existo.
Será absuelto si tiene buen abogado.
Bicondicional (Equivalencia):
El bicondicional es verdadero cuando ambas proposiciones tienen el mismo valor de
verdad, en otro caso es falso. El bicondicional es una simplificación de la fórmula:
La tabla de verdad de la bicondicional se ilustra a continuación.
P
Q
V
V
F
F
V
F
V
F
P↔Q
V
F
F
V
Ejemplos.
1. Aprobaré el curso sí y sólo sí me compran mi computadora.
2. Los estudiantes son felices sí y sólo sí sus profesores son impuntuales.
1.12
Clasificación de las tablas de verdad
Las tablas de verdad de una fórmula bien formada se clasifican de acuerdo al
resultado de la evaluación.
a
b
c
Si los valores de verdad son siempre verdaderos, sin importar cuales sean
los valores de verdad de las variables proposicionales que en ella
intervienen, a esta fórmula se le llama tautología.
Si los valores de verdad son siempre falsos, sin importar cuales sean los
valores de verdad de las variables proposicionales que en ella intervienen, a
este tipo de fórmulas se les llama contradicción.
Si los valores de verdad de la fórmula son, en algunos casos verdaderos y en
otros falsos, a estas fórmulas se les llama contingencia.
Elaboró: afmorales
11
Conceptos Generales
Ejemplos:
(P → Q ) ∧ (Q → R ) → (P → R )
1.
2.
3.
4.
5.
6.
7.
(P → H ) ∧ ¬(P → H )
(P → Q ) ↔ (¬ P ∨ Q )
(P → Q ) ∨ R
(P → Q ) ∧ ((Q ∧ ¬ R ) → (P ∨ R ))
8.
9.
10.
(S ∨ G → P ) ∧ ¬ A ∧ ( P → A ) → ¬ S
1.12 Método de Tablas Semánticas
La técnica se caracteriza por operar con un conjunto reducido de reglas y tienen la
ventaja de ser absolutamente mecánico y facilita la solución de problemas
deductivos. Para ilustrar la validación de una fórmula bien formada, seguiremos el
criterio semántico, mediante la aplicación de las siguientes reglas:
Reglas de implicación
Verdad de la de implicación
(1)
A→ B ≅
¬A
Falsedad de la implicación
(2) ¬ (A→ B) ≅ A
¬B
B
Regla de negación
Doble negación
(3)
¬¬A≅A
Reglas de la conjunción
Vedad de la conjunción
(4) A ∧ B ≅ A
B
Falsedad de la conjunción
(5) ¬ (A ∧ B)≅
¬A
Reglas de la disyunción
Verdad de la disyunción
(6) A ∨ B ≅
A
¬B
Falsedad de la disyunción
(7) ¬ (A ∨ B) ≅¬ A
¬B
B
Elaboró: afmorales
12
Conceptos Generales
Reglas de la doble implicación
Verdad de la doble implicación
(8) A↔B ≅
A
B
Falsedad de la doble implicación
(9) ¬ (A ↔ B) ≅
¬A
¬B
A
¬B
¬A
B
Procedimiento
Para construir la tabla semántica correspondiente a un argumento, se colocan en
columna, las premisas iníciales y la negación de la conclusión. En seguida se
procede a la aplicación de reglas a las distintas premisas, dando preferencia,
mientras sea posible, a las reglas que no propicien bifurcación. Después de haber
agotado éstas posibilidades se aplicarán las reglas que involucren una bifurcación.
Al bifurcarse, la tabla queda escindida en dos subtablas, cualquiera de las cuales
puede a su vez escindirse en otras dos, y así sucesivamente. El análisis de cada una
de las subtablas debe ser tramitado independientemente de las otras, salvo en lo que
respecta al tronco o rama común de donde procedan. Si el análisis de una de las
fórmulas pertenecientes al tronco o rama exigiese una nueva bifurcación, esta se
introduciría en todas y cada una de las subtablas, cuya tramitación se encuentre en
marcha.
La escisión de la tabla en subtablas obliga a distinguir diversas trayectorias en el
curso de la deducción, cuantas ramas se introducen por razón de las bifurcaciones.
Una trayectoria quedará definida por el recorrido de las líneas que componen el
tronco común y determinadas ramas y subramas, cuando las haya, siempre que este
recorrido se efectúe de forma continua y en sentido descendente. El proceso de
construcción de la tabla se puede representar esquemáticamente mediante un árbol
lógico.
Ejemplos
1. Demuestra que la siguiente fbf es una tautología.
p→q
r → ¬q
r → ¬p
Elaboró: afmorales
13
Conceptos Generales
Solución
6. ¬P
X
7.
¬R
X
Q
(r1, R1 ) y C (5,6)
¬Q (r2 , R1 )
X C(4,7) y C(6,7)
En la trayectoria que va de las premisas 1 a 6, hay contradicción entre (5 y 6); en la
trayectoria que va 1 a 7, existe contradicción entre las premisas (4 y 7); y (6 y 7)
Toda trayectoria termina en contradicción. Por tanto, el argumento analizado es tiene
una estructura lógica de una tautología. Toda trayectoria quedará cerrada o
clausurada tan pronto surja una contradicción. En señal de ello se marca una X bajo
la línea final del recorrido. Si todas las trayectorias quedan cerradas, se dice que la
tabla está totalmente cerrada o clausurada, lo cual será una prueba de que el
argumento analizado es válido. En caso contrario, se dice que la tabla queda abierta.
2.
3.
4.
5.
6.
7.
8.
9.
( s → p ) ∧ (r ∨ ¬ p ) ∧ (t → ¬ r ) → ¬ s ∨ ¬ t
( p → q ∨ r ) ∧ (q → ¬ p) ∧ ( s → ¬ r ) → ¬ ( p ∧ s)
(P → Q ) ∧ (R → P ∧ S ) ∧ ((Q ∧ S ) → ( P ∧ T ) ) ∧ ¬T → (P → ¬ R )
(¬ r → ¬ s ) ∧ (t ∧ r ↔ ¬ s ) → r
Si 10 es primo, 10 no puede ser igual a 2 por 5. 10 es igual a 2 por 5. Por lo tanto,
10 no puede ser primo.
10.Si estudio o soy un genio, entonces aprobaré el curso. Si apruebo el curso,
entonces me permitirán realizar un viaje. Por consiguiente, si no realice el viaje,
entonces no soy un genio.
11.Si obtengo la diputación y me mantengo en la curul, entonces compraré automóvil
nuevo. Si compro carro nuevo, seré feliz. No soy feliz. En consecuencia, no
obtuve la diputación o no me mantuve en la curul.
12.Si el triángulo tiene tres ángulos, un cuadrado tiene cuatro ángulos rectos. Un
triángulo tiene tres ángulos y su suma vale dos ángulos rectos. Si los rombos
tienen cuatro ángulos rectos, lo cuadrados no tienen cuatro ángulos rectos. Por lo
tanto, los rombos no tienen cuatro ángulos rectos.
Elaboró: afmorales
14
Conceptos Generales
13.Si la amante es atractiva, el galán sonreirá abiertamente o será infeliz. Si no es
feliz no procreará en tales condiciones. Por consiguiente, si la amante es
atractiva, entonces, si el galán no sonríe abiertamente, no procreará.
14.Si Elvira opina que hay que hacer lo posible para ser feliz, abandonará a su
amante o se dedicará a su profesión, Si se dedica a su profesión, no dejará a su
marido. En conclusión, si Elvira opina que hay que hacer lo posible para ser feliz,
entonces, dejará a su marido aunque no abandone a su amante.
15.Si Pedro lleva pareja de reyes, lleva treinta y una o gana. Si lleva treinta y una, no
lleva pareja de reyes. Si no sabe jugar al mus, no ganará. En conclusión, si Pedro
lleva pareja de reyes, sabe jugar al mus.
Elaboró: afmorales
15
Conceptos Generales
Problemas propuestos
1. Traduzca las siguientes oraciones compuestas a notación simbólica usando
variables proposicionales en vez de oraciones atómicas.
a No se trabaja, no hay paga.
b María es alta, pero Jaime es pequeño y ágil.
c Si Usted recibe una clase de computación y no entiende de recursividad, Usted
no aprobará.
d Si Micaela gana las olimpiadas, todos la admirarán y ella será rica; pero si no
gana, todo su esfuerzo fue en vano.
e Las mercancías compradas en esta tienda pueden ser devueltas solo si están
en buenas condiciones y solo si el cliente trae la factura.
2. Dadas las siguientes fórmulas bien formadas y los respectivos razonamientos,
determinar por medio de tablas de verdad si son tautologías, contradicciones o
contingencias.
a
(R → S ) ∧ (S → Q ) ∧ (R ∨ ( S ∧ T )) → (¬Q → T ∧ S )
b
(R → S ) ∧ (S → Q ) ∧ (R ∧ T ) → (Q → T ∧ S )
c
(P → Q ) ∧ (¬S ∨ R ) ∧ (¬T ∨ ¬Q ) ∧ (S ∧ T ) → (P → R ∧ S )
d Los estudiantes están contentos si y solo si no hay clases. Si los estudiantes
están contentos, entonces el profesor es impuntual. Si el profesor es impuntual,
no está en condiciones de evaluar, y si no está en condiciones de evaluar,
habrá clases. Por lo tanto, los estudiantes están tristes.
e Si sigue lloviendo, entonces el río crecerá. Si sigue lloviendo y el río crece,
entonces el puente será arrastrado por las aguas. Si la continuación de la lluvia
hace que el puente sea arrastrado por las aguas, entonces no será suficiente
un solo camino para toda la ciudad. O bien un solo camino es suficiente para
toda la ciudad o bien los ingenieros cometieron un error. Por lo tanto, los
ingenieros cometieron un error.
Elaboró:afmorales
17
Conceptos Generales
3. Construye la tabla de verdad de cada una de las siguientes expresiones.
a
b
c
d
e
f
¬ (P ∧ Q)
¬ P ∧¬ Q
¬ (P ∨ Q)
(¬ P ∨¬ Q)
¿tienen los mismos valores las fórmulas? ¬ (P ∧ Q) y ¬ P ∨¬ Q
¿tienen los mismos valores las fórmulas? ¬ (P ∨ Q) y ¬ P ∧¬ Q
4. Como quedan las tablas de verdad de las siguientes expresiones.
a ¬ (P ∧ Q ∧ R) y (¬ P ∧¬ Q ∧¬ R)
b ¬ (P ∨ Q ∨ R) y (¬(P ∨¬ Q ∨¬ R)
5. Puedes anticipar que sucederá al construir las tablas de verdad de las fórmulas.
a ¬ (P1∧ P2∧…∧Pn) y (¬ P1∧¬ P2∧¬…∧¬Pn )
b ¬ (P1∨ P2∨…∨Pn) y (¬ P1∨¬ P2∨¬…∨¬Pn )
6. Utilizando tablas
razonamientos.
a
b
c
semánticas,
demostrar
si
son
válidos
los
siguientes
(R → ¬P ) ∧ (( R ∧ S ) ∨ T ) ∧ (T → Q ∨ U ) ∧ (¬Q ∧ ¬U ) → ¬ P
(E ∨ F → ¬H ) ∧ (J → E ) ∧ (K → F ) ∧ (J ∨ K ) → (G ∨ ¬H )
¬(P ∨ ¬R ) ∧ (Q ∨ P ) ∧ (R → S ) ∧ ((Q ∧ S ) → (T ∧ S ) ) → (T ∧ S )
d Los estudiantes están contentos si y solo si no hay clases. Si los estudiantes
están contentos, entonces el profesor es impuntual. Si el profesor es impuntual,
no está en condiciones de evaluar, y si no está en condiciones de evaluar,
habrá clases. Por lo tanto, los estudiantes están tristes
e Si sigue lloviendo, entonces el río crecerá. Si sigue lloviendo y el río crece,
entonces el puente será arrastrado por las aguas. Si la continuación de la lluvia
hace que el puente sea arrastrado por las aguas, entonces no será suficiente
un solo camino para toda la ciudad. O bien un solo camino es suficiente para
toda la ciudad o bien los ingenieros cometieron un error. Por lo tanto, los
ingenieros cometieron un error.
f O bien el amor es ciego y los hombres no son conscientes del hecho de que el
amor es ciego, o bien el amor es ciego y las mujeres sacan ventaja de ello. Si
los hombres no son conscientes de que el amor es ciego, entonces el amor no
es ciego. En conclusión, las mujeres sacan ventaja de ello.
Elaboró:afmorales
18
Deducción Natural
SEGUNDO CAPÍTULO
2.0 DEDUCCION NATURAL
“Como el lenguaje es confuso, lo mismo que difuso e inexacto,
cuando se aplica a la lógica es absolutamente necesario un
simbolismo lógico para un tratamiento exacto de nuestro objeto”.
Bertrand Russell
2.1Introducción
Como ya se ha comentado, que una de las principales funciones de la lógica es el de
proporcionar reglas de razonamiento, lo que permite inferir una conclusión a partir de
ciertas premisas. Al proceso de obtener una conclusión, a partir de ciertas premisas,
reglas de razonamiento (reglas de inferencia), se le llama demostración ó prueba
formal (CRITERIO SINTÁCTICO). Las reglas de inferencia, son criterios que
permiten construir una secuencia de estructuras lógicas para decidir la validez de un
argumento. Estas reglas, no dependen de las proposiciones particulares ni de sus
valores de verdad. En una argumentación, la conclusión se admite como verdadera,
probando que las premisas son verdaderas.
2.2 Método directo (Método de deducción natural)
Definición: Sean A y B dos fórmulas proposicionales, se dice que B se deduce
lógicamente de A, o que B es una conclusión válida (consecuencia) de la premisa A,
si y sólo si
es una tautología, esto se expresará como:𝐴𝐴 ⟹ 𝐵𝐵
En general la definición anterior, se puede escribir como: de un conjunto de premisas
se deduce lógicamente la conclusión “C”, sí y sólo sí:
es una tautología.
Lo que se escribirá como:
Ahora se indicará el proceso de derivación por medio del cual se hará la verificación
si una fórmula particular es una consecuencia lógica de un conjunto dado de
premisas. Partiendo de las premisas se construirá una sucesión de fórmulas, usando
reglas de inferencia ó equivalencias. Las implicaciones y equivalencias son fórmulas
tautológicas. A continuación se muestran las implicaciones y equivalencias que
pueden ser utilizados en el proceso de demostración de la validez de un argumento.
Elaboró:afmorales
19
Deducción Natural
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
I13
I14
I15
I16a
I16b
I17
I18
I19
I20
I21
I22
IMPLICACIONES
P∧Q⇒P
P∧Q⇒Q
P⇒ P ∨ Q
Q⇒P∨Q
¬ P ⇒ P→ Q
Q ⇒ P→ Q
¬ (P→ Q) ⇒ P
¬ (P→ Q) ⇒¬ Q
P, Q ⇒ P ∧ Q
¬ P, P ∨ Q ⇒ Q
P, P→ Q ⇒ Q
¬ Q, P→ Q ⇒¬ P
P→ Q, Q → R ⇒ P → R
P ∨ Q, P → R, Q → S ⇒ R ∨ S
P ∨ Q, P → R, Q → R ⇒ R
P→Q, P→ ¬ Q⇒¬ P
P→Q, ¬P→ Q⇒ Q
P→Q, P →(Q→ R) ⇒ P → R
P, P→Q, P →(Q→ R) ⇒ R
P⇒ Q→P ∧ Q
P → R, Q → R ⇒ P ∨ Q → R
(P→ Q)∧(R →S) ⇒ (P∨R)→(Q∨S)
(P→ Q)∧(R →S) ⇒ (P∧R)→(Q∧S)
Elaboró:afmorales
20
Deducción Natural
EQUIVALENCIAS
E1
E2
E3
E4
E5
E6
E7
E8
E9
E10
E11
E12
E13
E14
E15
E16
E17
E18
E19
E20
E21
E22
E23
E24
E25
E26
¬¬ P ⇔ P
P∧Q⇔Q∧P
P∨Q⇔Q ∨ P
(P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R)
(P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R)
P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)
¬ (P ∧ Q) ⇔¬P ∨¬ Q
¬ (P ∨ Q) ⇔¬P ∧¬ Q
P∨ P⇔ P
P∧P⇔P
R ∨ (P ∧¬ P) ⇔ R
R ∧ (¬ P ∨ P) ⇔ R
R ∨ (P ∨¬ P) ⇔T
R ∨ (P ∨¬ P) ⇔T
P→ Q ⇔¬P ∨ Q
¬ (P→ Q) ⇔ P ∧¬ Q
P→ Q ⇔¬ Q→¬ P
P→ (Q→ R) ⇔ (P ∧ Q) → R
¬ (P ↔ Q) ⇔ P ↔¬Q
P ↔ Q ⇔ (P→ Q) ∧ (Q → P)
P ↔ Q ⇔ (P ∧ Q) ∨ (¬P ∧¬ Q)
(P→ Q) ⇔ ¬ (P∧¬ Q)
P ∧ Q ⇔ ¬ (P→¬ Q)
(P→R) ∧ (Q → R) ⇔ P ∨ Q → R
(P→Q) ∧ (P → R) ⇔ P→(Q ∧ R)
Elaboró:afmorales
21
Deducción Natural
Ejemplos.
1. Demostrar que S es una inferencia válida de las premisas: R → S , R
Solución
Líneas
derivación
1. R → S
2. R
3. S
de Premisas
empleadas
P1
P2
I11(1,2)
y
reglas
Por tanto, (R → S)∧ R ⇒ S(es una tautología)
2. Probar que de las premisas P ∨ Q, P → R, Q → R se deduce lógicamente R.
Solución
Líneas
derivación
1.
2.
3.
4.
P∨Q
P→R
Q→R
R
de Premisas
empleadas
P1
P2
P3
I15(1,2,3)
y
reglas
Por tanto: (P ∨ Q)∧(P → R) ∧ (Q → R) ⇒ R(es una tautología)
3. Demostrar que R es una inferencia válida de las premisas: P → Q , Q → R , P
Solución
Líneas
derivación
1.
2.
3.
4.
5.
P→Q
Q→R
P
Q
R
de Premisas
empleadas
y
reglas
P1
P2
P3
I11(1,3)
I11(2,4)
Por tanto: (P → Q) ∧ (Q → R) ∧ P ⇒ R(es una tautología)
4. Demostrar que R ∨ S se deduce lógicamente de las premisas.
C ∨ D, (C ∨ D) →¬ H, ¬ H → (A ∧¬ B), (A ∧¬ B) → (R ∨ S)
Elaboró:afmorales
22
Deducción Natural
5. Demostrar que R ∧ (P ∨ Q) es una conclusión válida de las premisas.
P ∨ Q, Q → R, P → M, ¬ M
6. Demuestre que S ∨ R, se implica tautológicamente de:
(P∨ Q) ∧ (P → R) ∧ (Q → S)
7.
8.
9.
10.
11.Si no hay subsidios del gobierno para la agricultura, entonces hay controles
gubernativos sobre la agricultura. Si hay controles gubernativos sobre la
agricultura, entonces no hay depresión agrícola. Hay depresión o sobreproducción
agrícola. Es un hecho que no hay sobreproducción. Entonces hay subsidios del
gobierno para la agricultura.
12.Si A gana, entonces se colocarán B o C. Si se coloca B, entonces A no ganará. Si
D se coloca, entonces C no se coloca. En consecuencia, Si A gana, D no se
coloca.
13.Si aumenta la productividad, entonces aumenta la exportación. Si no aumenta la
productividad y no aumenta la exportación, entonces si disminuyen las divisas
habrá un aumento en el endeudamiento. Es falso que la disminución de divisas
genere un incremento de la exportación. Por lo tanto, aumentará el
endeudamiento
14.Si voy a primera clase mañana tendré que madrugar y si voy al baile está noche
me acostaré tarde. Si me acuesto tarde y madrugo tendré que vivir durmiendo
solo cinco horas. No puedo vivir durmiendo solo cinco horas. Por lo tanto, ó no
voy a mi primera clase mañana ó no voy al baile está noche.
15.Si el cometa Halley pasa cerca de la tierra, podremos observarlo con telescopio.
Pero no pasará cerca de la tierra, si las condiciones no son propicias. Si se envía
una sonda espacial a su encuentro, las condiciones serán propicias. Si pasa cerca
de la tierra y las condiciones son propicias, podremos apreciar la belleza del
Halley. O las condiciones no son propicias o podremos observar el Halley con un
telescopio. Así pues, si el cometa Halley pasa cerca de la tierra o se envía una
sonda espacial a su encuentro, podremos apreciar la belleza del cometa Halley.
Elaboró:afmorales
23
Deducción Natural
2.3 Método indirecto o (Reducción al absurdo)
Definición: se dice que un conjunto de fórmulas.
es consistente, si la conjunción tiene el valor de verdad verdadero para cualquier
asignación de valores de verdad de las variables atómicas.
Definición: se dice que un conjunto de fórmulas
es inconsistente, si al menos una de las fórmulas es falsa.
El conjunto de fórmulas
implica una contradicción, esto es:
es inconsistente, si la conjunción
donde R es una fórmula.
Con la finalidad de demostrar que la conclusión C se deduce lógicamente de las
premisas:
Se supone que C es falsa, luego, se agrega la
donde se admite que la
es verdadera.
como una premisa adicional,
Si el nuevo conjunto de premisas es inconsistente; entonces la suposición de que
es verdadera no es cierta simultáneamente con:
De modo que C es verdadera cuando:
es verdadera.
Por tanto, se concluye que C se deduce lógicamente de las premisas:
La técnica para determinar la consistencia de una estructura lógica consiste, en
deducir una contradicción. La deducción de la contradicción, se aborda en la misma
Elaboró:afmorales
24
Deducción Natural
forma como se realizó en la demostración de la validez de la conclusión de una
estructura lógica por el Método Directo y este procedimiento permite deducir
cualquier contradicción.
Ejemplos:
1. Demostrar que el siguiente conjunto de premisas es inconsistente.
{P → Q, P → R, Q → ¬ R, P}
Solución
Líneas
derivación
1.
2.
3.
4.
5.
6.
7.
8.
P→Q
P→R
Q→¬R
P
P →¬ R
¬R
R
R ∧¬ R
de Premisas
empleadas
P1
P2
P3
P4
I13(1,3)
I11(4,6)
I11(2,4)
I9(6,7)
y
reglas
{ P → Q, P → R, Q →¬ R, P } es inconsistente.
2. Utilizando el Método de Reducción al Absurdo, demostrar la validez de las
siguientes estructuras lógicas.
a. �(𝑆𝑆 ∨ 𝐺𝐺 → 𝑃𝑃) ∧ ¬ 𝐴𝐴 ∧ (𝑃𝑃 → 𝐴𝐴)� → ¬ 𝑆𝑆
Líneas
derivación
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
S ∨ G→ P
¬A
P→A
¬( ¬ S)
S
S∨G
P
A
A ∧¬ A
S→ A ∧¬ A
¬S
de Premisas
empleadas
P1
P2
P3
¬C(PA)
EI(4)
I3(5)
I11(1,6)
I11(3,7)
I9(8,2)
I6(5,9)
RRA(10)
y
Elaboró:afmorales
reglas
25
Deducción Natural
b (¬ 𝑃𝑃) ∧ (¬ 𝑄𝑄) → ¬(𝑃𝑃 ∨ 𝑄𝑄)
c �(𝑃𝑃 → 𝑄𝑄 ∨ 𝑅𝑅) ∧ (𝑄𝑄 → ¬ 𝑃𝑃) ∧ (𝑇𝑇 → ¬ 𝑅𝑅)� ⇒ (𝑃𝑃→¬T)
d �(𝑆𝑆 ∨ 𝐺𝐺 → 𝑃𝑃) ∧ (𝑃𝑃 → 𝐴𝐴)� → (¬ A →¬G)
e �(𝑃𝑃 → 𝑄𝑄 ∧ 𝑅𝑅) ∧ (𝑄𝑄 ∨ 𝑆𝑆 → 𝑇𝑇) ∧ (𝑃𝑃 ∨ 𝑆𝑆)� → 𝑇𝑇)
f ( P → (Q → R) ) ∧ ( P ∨ ¬ S ) ∧ Q ⇒ ( S → R )
g
( P → Q ∧ R ) ∧ ( R → S ) ∧ ( ¬ ( Q ∧ S ) ) → (¬ P )
3. Prueba que el siguiente razonamiento es consistente: Si el contrato es válido,
entonces Horacio está jurídicamente obligado. Si Horacio está jurídicamente
obligado, quebrará. Si el banco le presta dinero, no quebrará. De hecho, el
contrato es válido y el banco le presta dinero.
Elaboró:afmorales
26
Deducción Natural
Problemas propuestos
Dados los siguientes razonamientos demuestra que son válidos o en todo caso su
invalidez. Usar letras para denotar las variables proposicionales.
1. Si los precios son altos, entonces los salarios son altos. Los precios son altos, o
hay control de precios. También, si hay control de precios, entonces no hay
inflación. Sin embargo, hay inflación. En consecuencia, los salarios son altos.
2. O la lógica es difícil o no les gusta a muchos estudiantes. Si las matemáticas son
fáciles, entonces la lógica no es difícil. En consecuencia, si a muchos estudiantes
les gusta la lógica, las matemáticas no son fáciles.
3. Si se elevan los precios o los salarios, habrá inflación. Si hay inflación, entonces
el Congreso debe regularla, o el pueblo sufrirá. Si el pueblo sufre, los congresistas
se harán impopulares. El Congreso no regulará la inflación y los congresistas no
se volverán impopulares. En consecuencia no subirán los precios.
4. Si Algernon está en la cárcel, entonces no es una molestia para su familia. Si no
está en la cárcel, entonces no es una calamidad. Si no es una calamidad,
entonces está en el ejército. Si está borracho, es una molestia para su familia. En
consecuencia, o no está borracho, o está en el ejército.
5. O Juan y Enrique son de la misma edad, o Juan es de más edad que Enrique. Si
Juan y Enrique son de la misma edad, entonces Elizabeth y Juan no son de la
misma edad. Si Juan es de más edad que Enrique, entonces Juan es de más
edad que María. En consecuencia, o Elizabeth y Juan no son de la misma edad o
Juan es de más edad que María.
6. Mariana opinaba que el coronel Brandon era demasiado viejo para casarse. Si la
conducta de Mariana fuera siempre consistente con sus opiniones y si opinaba
que el coronel Brandon era demasiado viejo para casarse, entonces no se casaría
con el coronel Brandon. Pero Mariana se caso con el coronel Brandon. En
consecuencia, la conducta de Mariana no era siempre consistente con sus
opiniones.
7. Si María es una verdadera amiga, entonces Juan está diciendo la verdad. Si Juan
está diciendo la verdad, entonces Elena no es una verdadera amiga. Si Elena no
es una verdadera amiga, entonces no está diciendo la verdad. Si Elena está
diciendo la verdad, entonces María es una verdadera amiga. Pero si María es
una verdadera amiga, entonces Elena no es una verdadera amiga. En
consecuencia, Elena no está diciendo la verdad.
8. Si María entrega su proyecto, entonces Juan no lo terminará. Si María entrega su
proyecto, entonces Raúl tampoco lo terminará. Juan y Raúl definitivamente no
terminaron su proyecto. Por tanto, María entregó su trabajo.
Elaboró:afmorales
27
Deducción Natural
9. El contrato se satisface si y sólo si el edificio se termina para noviembre 30. El
edificio se termina si y sólo si el subcontratista de la instalación eléctrica termina
su trabajo para noviembre 10. El banco pierde dinero si y sólo si el contrato no se
cumple. No obstante, el subcontratista de la instalación eléctrica termina su
trabajo para noviembre 10 si y sólo si el banco pierde dinero.
Demuéstrese, por reducción al absurdo:
10.Si Juan juega primera base y Smith lanza contra nosotros, ganará Winsocki. O.
Winsocki no ganará, o entonces la novena terminará a la cola de la liga. La
novena no terminará a la cola de la liga. Además Juan jugará primera base. En
consecuencia, Smith no lanzará contra nosotros.
11.Si el hedonismo no es correcto, entonces el erotismo no es virtuoso. Si el
erotismo no es virtuoso, entonces o el deber no es la virtud más alta, o el supremo
deber es la prosecución del placer. Pero el supremo deber no es la prosecución
del placer. En consecuencia, o el deber no es la virtud más alta, o el hedonismo
es correcto.
12.Si una declaración de guerra es una estrategia adecuada, entonces o cincuenta
divisiones están acantonadas en la frontera, o veinte a las de bombarderos de
largo alcance están listas para atacar. Pero no están acantonadas en la frontera
cincuenta divisiones. En consecuencia, si no están listas para atacar veinte a las
de bombarderos de largo alcance, entonces, o una declaración de guerra no es
una estrategia adecuada, o hay armas secretas disponibles.
13.O la lógica es difícil o no les gusta a muchos estudiantes. Si las matemáticas son
fáciles, entonces la lógica no es difícil. En consecuencia, si a muchos estudiantes
les gusta la lógica, las matemáticas no son fáciles.
14.O Juan y Enrique son de la misma edad, o Juan es de más edad que Enrique. Si
Juan y Enrique son de la misma edad, entonces Elizabeth y Juan no son de la
misma edad. Si Juan es de más edad que Enrique, entonces Juan es de más
edad que María. En consecuencia, o Elizabeth y Juan no son de la misma edad o
Juan es de más edad que María.
15. Si la tormenta continúa o anochece, nos quedaremos a cenar o a dormir. Si nos
quedamos a cenar o a dormir no iremos mañana al concierto. Pero si iremos
mañana al concierto. Así pues, la tormenta no continúa.
Elaboró:afmorales
28
Cálculo de Predicados
TERCER CAPÍTULO
3.0 CÁLCULO DE PREDICADOS
“Así como uno puede sentirse seguro de que una cadena es
resistente cuando cada eslabón por separado es de buen material
y se enlaza sólidamente con los dos eslabones vecinos, así
también podemos estar seguros de la exactitud del razonamiento
cuando su materia es buena, esto es, cuando no hay en él
elementos dudosos y cuando la forma consiste en una
concatenación de verdades que no dejan grietas”.
Gottfried Leibniz
3.1 Introducción
El desarrollo de 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. Por ejemplo, el siguiente razonamiento:
Todos los humanos son mortales. Rodolfo es humano. Por lo tanto, Rodolfo 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:
h∧r⇒m
Por tanto, la conclusión no se puede deducir lógicamente de las premisas h y r al
aplicar las reglas de inferencia o equivalencia. Ninguna de las proposiciones h, r, m
puede describirse mediante partes de las mismas, dotadas de significado propio,
unidas por conectivas, que sean comunes en algunas de ellas y, por tanto, 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 humano” y “ser mortal”. A las personas se les hace la
atribución de estas propiedades y relaciones, son colectivos definidos a su vez por
propiedades y relaciones, así en la primera proposición son individuos de un conjunto
universal, mientras que en la segunda es un individuo concreto (Rodolfo).
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.
Elaboró: afmorales
29
Cálculo de Predicados
La Lógica de Primer Orden (LPO) o Lógica de Predicados se utiliza para modelar el
mundo en términos de:
 Sujetos: son personas con características individuales
 Objetos: los cuales son cosas (materiales, abstractas) con entidades
individuales.
 Propiedades: de sujetos u objetos, que permiten distinguirlos unos de otros.
 Relaciones: que se dan entre sujetos u objetos.
 Funciones: las cuales son subconjuntos de relaciones en las que hay sólo un
“valor” para cualquier “entrada” dada.
Ejemplos:
Sujetos: Juan, Pedro, estudiantes, trabajadores, jóvenes, niños,…
Objetos: cursos, compañías, coches, libros, temas,...
Propiedades: ser responsable, ser audaz, ser alegre, ser estudiante, ser alto, ser
bajo, ser caballero, ser escudero, ser ladrón, ser pícaro, ...
Relaciones: hermano de, más grande que, fuera de, parte de, ocurre después de,
pertenece a, es amigo de, visita a, precede a,...
Elabora una lista de 10 elementos de:
Sujetos:
Objetos:
Propiedades:
Relaciones:
3.2 El lenguaje de la Lógica de Predicados
Los elementos constitutivos del lenguaje de la Lógica de Predicados son:
Un alfabeto que consta de los siguientes símbolos:
a Símbolos de términos o individuos constituidos por letras de variables
(últimas letras del alfabeto, x, y, z, t, w, etc.), letras de constantes (primeras
letras del alfabeto, a, b, c, d, etc.). Un conjunto numerable de ellas y además,
ambas pueden tener subíndices (x1, x2,...; a1, a2,...).
b Símbolos de predicado, se emplearán las letras mayúsculas del alfabeto: P,
Q, R, S,..., o secuencias finitas de ellas OM, COM, PT, o secuencias indexadas
Q1, Q2, Q3,... (Un conjunto numerable de cada una de ellas).
Elaboró: afmorales
30
Cálculo de Predicados
c Símbolos de conectivos y paréntesis idénticos a los utilizados en el cálculo
proposicional: ¬,∨, ∧, →, ↔, ( )
d Símbolos de cuantificación:
Cuantificación universal ∀
Cuantificador existencial ∃
Una vez definidos los componentes del enunciado dado, se plantea su
representación, basándose en: términos, predicados, conectivos, cuantificadores y
paréntesis.
Para la simbolización de términos se supone como base de referencia un dominio
genérico no vacío.
 Los términos o individuos se representan con variables o constantes cuyos
valores posibles forman parte del dominio.
 x, y, z, t,
variables (representan cualquier elemento del dominio).
 a, b, c, d,
constantes,(representan elementos concretos del dominio).
Para la notación de predicados se utiliza la notación funcional:
Esto puede hacerse de dos formas:
 Por sustitución, en este caso se asigna a cada plaza del predicado un símbolo
de término que puede ser constante o variable.
Por ejemplo: en lugar de P ( p1 , p2 ,..., pn ) se debe escribir P ( x1 , x2 ,..., xn ) ...,
(1)
Las variables que aparecen en (1) se llaman variables libres.
 Por cuantificación, en este caso se asigna a cada plaza un conjunto de
elementos del dominio y se tienen dos posibilidades:
a Si se asigna a una plaza todos los elementos del dominio se simboliza
mediante la letra de variable situada en la plaza correspondiente cuantificada
universalmente fuera de la fórmula.
Por ejemplo, si a la plaza , se le asigna todo el dominio, se escribiría:
(2)
∀x1 P ( x1 , x2 , a3 ,..., xn )
b Si se asigna a una plaza un subconjunto del dominio no especificado, se
simboliza mediante una letra de variable situada en la plaza correspondiente
cuantificada existencialmente. Por ejemplo:
(3)
∃x1 P ( x1 , x2 , a3 ,..., xn )
Elaboró: afmorales
31
Cálculo de Predicados
Las variables afectadas por cuantificadores se denominan variables ligadas (ya sea
universal o existencial). De acuerdo con las definiciones anteriores, al ligar una
variable libre, mediante un cuantificador, se modifica el contenido de información de
la frase de forma que las propiedades o relaciones atribuidas a la variable libre en
singular se atribuyen a conjuntos (subconjuntos totales o parciales del dominio de
referencia según el tipo de cuantificador. Las fórmulas (1), (2), (3) del cálculo de
predicados son “formas” de frases en el lenguaje usual.
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.).
Para la formalización matemática, es importante definir el conjunto universo o
dominio de definición con el cual se van a formular el o los predicados, porque existe
la posibilidad de asignar fórmulas distintas a las mismas frases del lenguaje natural,
si no se ha especificado el dominio de definición.
Por ejemplo, la frase:
“Todas las águilas vuelan alto” se representa de la siguiente “forma”:
∀xV ( x) donde V ( x) =
x vuela alto
En esta formalización, el dominio de definición es: el conjunto de las águilas.
Sin embargo, si se define como dominio el conjunto de las aves, entonces se
requiere considerar un nuevo predicado:
A ( x ) = x es águila
En este caso la frase anterior se representa, como:
∀x [ A( x) → V ( x) ]
3.3 El universo del discurso
Todo predicado tiene un contexto en el cual se puede aplicar y verificar si este es
válido; es decir, todo predicado debe estar asociado a un conjunto universo (dominio)
para poder sustituir los elementos con la o sus variables correspondientes. La
definición del universo es importante, ya que permite por un lado, simplificar fórmulas
y por otro indicar si las proposiciones que surgen al sustituir los elementos del
universo en las variables del predicado son verdaderas o falsas sobre dicho universo.
Elaboró: afmorales
32
Cálculo de Predicados
Ejemplos:
1. Sea el predicado Q(x ) : x es menor que 5 .
Si el universo es:
a. {− 1, 0, 1, 2, 3, 4}
b. {− 3, − 2, 1, 2, 3, 4, 5}
Analizar los cuantificadores con cada uno de los conjuntos y determinar la
veracidad o falsedad del predicado.
[
]
2. Dada la expresión ∀x x 2 > 10 cuyo dominio es el conjunto de los números
naturales.
Determinar la veracidad o falsedad de la expresión.
3. Sean los predicados; P( x ) : x es par; Q( x ) : x 2 es par.
Dominio: números enteros
Analizar la veracidad de las fórmulas: ∀x[P( x) → Q( x)]
∀x[P( x) ∧ Q( x)]
4. La expresión: “Dado un entero positivo, existe un positivo mayor”.
Dominio: números reales
P( x ) : x es un entero positivo.
P( y ) : y es entero positivo mayor.
M ( y, x ) : y es mayor que x .
Analizar la veracidad o falsedad de la fórmula:
5. Considérese la proposición: “Todos los lenguajes de programación son medios
para resolver problemas”.
Los predicados asociados son:
L( x ) : x es un lenguaje de programación.
M ( x ) : x es un medio para resolver problemas.
Si el universo es: U = {Pascal, “C”, Ada, monitor VGA}.
Determinar si la proposición es verdadera o falsa sobre U.
Analicemos las siguientes fórmulas predicativas.
Elaboró: afmorales
33
Cálculo de Predicados
6. Consideremos la proposición: “Algunos lenguajes de programación son de bajo
nivel”.
Donde:
L( x ) : x es un lenguaje de programación.
B( x ) : x es un lenguaje de bajo nivel.
Si el universo es: U = {Pascal, “C”, Ada, monitor VGA}.
Determinar si la proposición es verdadera o falsa sobre U.
Analicemos las siguientes fórmulas predicativas.
3.4 Formalización de enunciados
Para facilitar el proceso de traducción-verificación se tendrá que descomponer de
manera natural en los siguientes subprocesos: Enunciado-Representación, Análisis
Sintáctico, Representación-Enunciado. Una forma para abordar este proceso es
identificando los elementos constitutivos de cada lenguaje y llevar a cabo el proceso
de asociación o correlación entre cada uno de ellos en dicho enunciado y así poder
realizar la traducción deseada. Dado que la traducción se hace de un lenguaje con
mayor capacidad de expresión (lenguaje natural) a uno de menor expresión (lenguaje
de LPO) entonces, habrá varios elementos del primer lenguaje que no podrán ser
representados en el segundo lenguaje, de tal forma que solo se considerarán para la
traducción cierto tipo de enunciados. Por tanto, el problema de traducción o
formalización de enunciados del lenguaje natural o común, al lenguaje de la LPO se
puede plantear de la siguiente forma.
 ¿qué elemento del lenguaje de la lógica de predicados le corresponde a cada
componente del enunciado en lenguaje común? O en la otra dirección:
 ¿qué componente del lenguaje común se puede representar con un individuo
(término), con un predicado, con un conectivo, con un delimitador de conectivo
o cuantificador?
Elaboró: afmorales
34
Cálculo de Predicados
El esquema se vería así:
ENUNCIADO en lenguaje común
Componente
1
Componente
2
¿?
...
¿?
Término
individuo
genérico
concreto
Componente
n
¿?
o
Conectivo
o
Cuantificador
Predicado
Delimitador
de conectivo o
cuantificador
Elementos del lenguaje de la LPO
Usando la sintaxis de las sentencias en el lenguaje de la lógica de predicados, se
escribe la expresión (o fórmula) que le corresponde al enunciado del lenguaje
común. Este esquema sólo es un auxiliar para el proceso de traducción, la dificultad
que hace difícil la traducción es la ambigüedad del lenguaje común y la variabilidad
de las formas de hacer referencia a los conectivos, los cuantificadores y los
delimitadores de cada uno de ellos. Pero una reflexión orientada puede favorecer el
desarrollo adecuado de una habilidad que permita conseguir objetivo planteado.
En el siguiente cuadro se presenta una guía que podría ser útil al trabajar los
problemas de traducción, analízala y trata de usarla durante el proceso de la
traducción de enunciados.
ACCIONES
COMPRENDER
ENUNCIADO
OPERACIONES
EL
 Leerlo varias veces.
 Expresarlo con tus propias palabras.
 Identificar palabras desconocidas o expresiones
desconocidas.
 Identificar los predicados de acuerdo a su sentido
semántico.
 Identificar un posible universo
Elaboró: afmorales
35
Cálculo de Predicados
ACCIONES
ANALIZAR
ENUNCIADO
OPERACIONES
EL
REPRESENTAR LOS
PREDICADOS,
CUANTIFICADORES
Y CONECTIVOS
VERIFICAR
LA
FORMULA DE LOS
PREDICADOS
 Analizar el tipo de predicado que aparece (unario,
binario,...,).
 Identificar conectivos lógicos explícitos e implícitos.
 Identificar cuantificadores explícitos o implícitos.
 Analizar el alcance de los cuantificadores y los
conectivos como referencias explicitas los signos de
puntuación y el sentido global de los predicados.
 Analizar cuál es el universo adecuado para el
enunciado de acuerdo a los predicados que en
intervienen.
 Rescribir los predicados haciendo explícita su
asociación con los conectivos y cuantificadores,
respetando su significado original
 Asignar símbolos estándar a los predicados (P, Q, R,
S, T, etc.,), a los cuantificadores
y a los
objetos de dominio
.
 Asignar símbolos estándar a los conectivos lógicos
.
 Agrupar predicados y conectivos para construir la
fórmula de predicados, de acuerdo con la definición
de FBF.
 Comparar la agrupación de la fórmula resultante con
las reglas de asociación de los conectivos y
cuantificadores dadas en la definición de las FBF.
 Revisar la agrupación de la fórmula en términos de
su delimitación por paréntesis.
 Verificar que la FBF respete el sentido del enunciado
original.
En la ejercitación, es necesario un sistema de preguntas que permitan realizar una
realimentación constante y reflexionar antes y después de cada acción realizada en
cada una de las fases enmarcadas en el cuadro anterior.
Elaboró: afmorales
36
Cálculo de Predicados
PROPUESTA DE EQUIVALENCIAS SEMANTICAS DE LOS CONECTIVOS:
NOMBRE DEL
CONECTIVO
NOTA SE LEE COMO
CIÓN
CONJUNCIÓN
∧
Y
DISYUNCIÓN
∨
O
NEGACIÓN
¬
NO
IMPLICACION
DOBLE
IMPLICACION.
→
↔
EQUIVALENCIAS FRECUENTES
además, también, pero, aún, aunque,
sin embargo, “,”, no obstante, a pesar
de que, igualmente, tanto. . . como, e,
lo mismo que, incluye, aún así, ...
o p o q o ambas cosas, al menos p o
q, como mínimo p o q, u, en otro caso,
de otra manera, ya sea que, elija entre,
…
no es cierto que, no es el caso que, es
falso que, no es verdad que, ni... ni,
ningún, no ocurre que, tampoco, ...
p solo si q, q si p, q necesario para p, p
suficiente para q, no p a menos que q,
.por lo tanto, como consecuencia, así
que...,siempre y cuando…, dado que
SI ENTONCES ..., en la medida que...,
p necesario y suficiente para q, p es
SI Y SÓLO SI equivalente a q, igual a, lo mismo que,
cuando y sólo cuando, …
3.5 Sintaxis de construcción de fórmulas
Con base a los conocimientos estructurales existentes en el lenguaje usual puede
definirse formalmente como en el cálculo proposicional una sintaxis, de igual manera
para el cálculo de predicados se define de la forma siguiente.
Una fórmula constituye una sucesión de símbolos del alfabeto que verifica las reglas
de formación siguientes:
a Toda proposición es una fórmula.
b Si p es una letra de predicado de n plazas
símbolos de términos.
c Si
es una fórmula que contiene libre la variable
, es una fórmula, siendo
:
∀x1 ( x1 , x2 ,..., xn )
∃x1 ( x1 , x2 ,..., xn )
Elaboró: afmorales
37
Cálculo de Predicados
d Si A y B son fórmulas.
¬ A, ¬ B, A ∧ B, A ∨ B, A → B son fórmulas.
e Sólo se consideran fórmulas, aquellas que están construidas según los
conceptos (a) hasta (d).
Las reglas (a), (b), (c) y (d) permiten analizar en forma inductiva las fórmulas del
cálculo de predicados.
Evidentemente, de acuerdo con el planteamiento de la sintaxis, toda fórmula del
cálculo proposicional es una fórmula sintácticamente correcta en cálculo de
predicados.
Para la colocación de paréntesis se tendrán en cuenta las prioridades definidas para
las distintas conectivas ya trabajadas en el primer capítulo, a los que hay que añadir
los cuantificadores, según sea necesario.
Por ejemplo la fórmula:
el cuantificador universal sólo afecta a la primera x , la segunda x está libre, en
caso de afectar a ambas, se debe utilizar un paréntesis de la siguiente forma:
Cuando se trate de fórmulas con varios cuantificadores, se considerará que el
proceso de cuantificación se realiza en el orden de mayor a menor proximidad a la
fórmula cuantificada. Es decir:
debe entenderse en la forma:
Por tanto, a partir de la fórmula con todas las variables libres se construye
primeramente la frase en que a S se atribuye un subconjunto indefinido representado
por ∃s . En la fórmula resultante se sustituye z por todo el dominio, etc.
El cambio de orden de cuantificación puede alterar el significado de la frase. En
efecto, las frases siguientes no tienen el mismo significado.
 Para cualquier número
existe al menos otro
se representa por la fórmula:
∀x∃yM ( x, y )
 Existe al menos un número
; tal que
tal que para cualquier
Elaboró: afmorales
,
, cuya estructura
, cuya estructura es:
38
Cálculo de Predicados
3.6 Esquema de formalización de predicados.
Para la traducción de enunciados no puede definirse un procedimiento mecánico que
permita obtener la fórmula que representa la estructura de una frase del lenguaje
común. En cada caso debe modificarse la redacción de la frase, sin alterar su
significado hasta conseguir una expresión lingüística que contenga elementos de
fácil traslación a expresiones con cuantificadores y conectivas, elementos de base de
la formalización; es decir que: de manera intuitiva podemos pensar que los
predicados se asocian a ciertos objetos descritos o mencionados en un enunciado,
de tal forma que si analizamos un enunciado, podemos identificar el dominio o
universo preguntándonos ¿de quién se habla? Y los predicados los
identificamos al responder a la pregunta ¿qué se dice de ellos?
A continuación se presentan algunos ejemplos de formalización de frases simples y
compuestas.
Las frases simples son aquellas que están constituidas por proposiciones atómicas;
es decir, constan de un sólo predicado cuantificado o no. Las frases compuestas son
aquellas que están constituidas por expresiones cuantificadas en las que intervienen
los conectivos. Además las frases simples son de atribución de propiedades y
relaciones, pero las frases compuestas tienen gran variedad de estructuras, como la
conjunción o disyunción de propiedades y relaciones con elementos del dominio de
referencia.
Ejemplos
1. Analiza los siguientes ejemplos de formalización de enunciados
El hombre
locuras
comete
Toda persona no es joven
muchas Dominio: personas;
Predicados: H(x): x es hombre
L(x): x comete muchas locuras
Traducción ∀x[H (x ) → L( x )]
Universo: personas;
Predicado: J(x): x es joven;
Traducción ∀x¬J ( x )
Algún joven es mentiroso
Dominio: personas;
Predicados: J(x): x es joven
M(x): x es mentiroso
Traducción ∃x(J(x) ∧ M(x))
Alguien es joven y alguien es Universo: personas;
mentiroso
Predicados: J(x): x es joven;
M(x): x es mentiroso;
Traducción ∃xJ(x) ∧∃yM(y)
Elaboró: afmorales
39
Cálculo de Predicados
Alguien es amigo de Juan
Dominio: Personas;
Predicados: A(x,y): x es amigo de y;
Juan≡j
Traducción ∃xA(x,j)
Algún joven tiene algún amigo
Dominio: personas;
Predicados: A(x,y): x es amigo de y;
J(x): x es joven;
Traducción ∃x∃y(J(x) ∧ A(x,y))
Los mentirosos son ladrones
Dominio: personas;
Predicados: J(x): x es ladrón
M(x): x es mentiroso
Traducción ∀x(M(x) → L(x))
Los caballeros tienen algún Dominio: personas;
escudero
Predicados: C(x): x es caballero
E(y,x): y es escudero de x;
Traducción ∀x(C(x) →∃yE(y,x)) o
Traducción
∀x∃y(C(x) → E(y,x))
Ningún muñeco de peluche es Dominio: juguetes;
venenoso.
Predicados: M(x): x es muñeco;
P(x): x está hecho de peluche;
V(x): x es venenoso.
Traducción ∀x[(M(x) ∧ P(x)) → ¬V(x)]
2. Para cada uno de los siguientes enunciados, indicar cuál es el dominio o universo
que le asociaría y los predicados que propondría de tal manera que la fbf que se
le asocia es la indicada.
Ninguna rubia es peligrosa
Dominio o universo:
Predicados:
Traducción ∀x[R( x ) → ¬ P( x )]
Hay profesores que no saben Dominio o universo:
explicar.
Predicados:
Traducción: ∃x∃y(E(x,y) ∧ ¬∃zA(x,z))
No es cierto que los caballeros Dominio o universo:
no sean jóvenes
Predicados:
Traducción: ¬∀x(C(x) → ¬J(x))
Elaboró: afmorales
40
Cálculo de Predicados
Si Carlos es amigo de algún Dominio o universo:
artista, entonces Carlos es Predicados:
admirador de ese artista
Traducción:∀x[(A(x) ∧ AM(c,x)) → AD(c,x)]
Los admiradores de artistas son Dominio o universo:
amigos de artistas
Predicados:
Traducción: ∀x[∃y(A(y)∧AD(x,y))→AM(x,y)]
Eva tiene un amante al que ella Dominio o universo:
no quiere.
Predicados:
Traducción: ∃x(A(x,e) ∧ ¬Q(e,x))
3. Realiza las diferentes actividades para obtener la traducción de los siguientes
enunciados.
a Algunos mexicanos son ricos.
b Todo árbol tiene un nodo raíz.
c Todos son responsables.
d Juan es amigo de todos.
e Todos los programas en Pascal empiezan con la palabra reservada program.
f
Existe un algoritmo de búsqueda para realizar búsquedas eficientes en listas
ordenadas.
g Cualquier número entero, diferente de cero, es positivo o negativo.
h Algunos árboles son árboles binarios completos.
i
En toda pareja de vecinos existe algún envidioso.
j
Algunos aspirantes a la Maestría en Ciencias de la Computación del CENIDET
tienen amigos aficionados a la lógica.
Elaboró: afmorales
41
Cálculo de Predicados
k No todos los administrativos están en el mismo lugar donde están todos los
programadores.
l
Los caballeros las prefieren rubias, pero se casan con las morenas.
m Hay genios, pero no todos los poetas son genios.
n Todos los estudiantes de tercer semestre salen con alguien de primer
semestre.
o Nadie respeta a quien no se respeta a si mismo.
p Todo aquél cuyo padre es el Sr. López tiene el pelo negro.
q Juan, Pedro y Carlos son alpinistas. A los alpinistas no les gusta la nieve. Los
miembros del Club Alpino o son alpinistas o esquiadores. A Juan le disgusta
todo lo que a Miguel le gusta y a Miguel le disgusta todo lo que a Juan le gusta.
A Pedro le gusta la nieve siempre y cuando no llueva.
3.7
Negación de cuantificadores
Considerando universos de conjuntos finitos. Por ejemplo, sea
se tiene:


de donde se obtienen las siguientes equivalencias:
las cuales representan la negación de los cuantificadores (universal y existencial).
Ejemplos.
1. Obtener la negación de las siguientes fórmulas:
a. ∀x ( P ( x ) → ¬Q ( x ) )
b. ∃x ( P ( x ) ∨ Q ( x ) )
c. ∃x ( P ( x ) ∧ Q ( x ) )
d. ∀x ( P ( x ) ∧ ¬Q ( x ) )
e. ∀x∃y ( P ( x, y ) ∧ Q ( x, y ) → R ( x, y ) )
Elaboró: afmorales
42
Cálculo de Predicados
2. La negación de: “Todos los programas en Pascal comienzan con la palabra
reservada program”
Es: “Existe un programa es Pascal que no comienza con la palabra reservada
program”.
3. Obtener la negación de: Sólo los tontos se dejan engañar por su novia.
4. Obtener la negación de: Ninguno de los seguidores de Aristóteles estima a los
filósofos idealistas.
5. Obtener la negación de: Algunos tíos de Martín le envían regalos de
cumpleaños.
6. Obtener la negación de: Todos los que son vecinos se odian entre sí.
7. Obtener la negación de: Martha no ama a ninguno de sus amigos.
8. Obtener la negación de: Algunos estudiantes de informática sólo son amigos de
los aficionados a la lógica.
9. Obtener la negación de: Todos los que ayudan a Martín trabajan en casa de
Nora.
3.8 Procedimiento para la deducción en el Cálculo de Predicados
En esta sección se establecerán los criterios que se emplearán en el proceso de
deducción del cálculo de predicados. Se asume que las fórmulas de predicados
contienen: variables proposicionales, predicados y “variables objeto”. Las variables
objeto pertenecen a algún conjunto universo ó dominio.
Las fórmulas de predicados que involucren cuantificadores y no tengan variables
libres, se considerarán como fórmulas del cálculo proposicional. En general, una
tautología del cálculo proposicional permanece como fórmula válida del cálculo de
predicados cuando se sustituyen (instancia de sustitución) fórmulas primitivas
(atómicas) de predicados en las variables proposicionales. De esta forma, las
fórmulas utilizadas (implicaciones y equivalencias) en el cálculo proposicional serán
utilizadas en el cálculo de predicados, sustituyendo en ellas por fórmulas primitivas
(atómicas) de predicados.
Las siguientes fórmulas, nos permiten remover o añadir cuantificadores durante el
curso de la demostración.
Sea
una fórmula proposicional, donde “ x ” es una variable objeto particular,
entonces se tiene:
Especificación universal
∀xA( x) ⇒ A( x)
EU
Especificación existencial
EE
Elaboró: afmorales
43
Cálculo de Predicados
Generalización universal
GU
Generalización existencial
A( x ) ⇒ ∃xA( x )
GU
Durante el proceso de deducción se podrán emplear las reglas de generalización
universal y existencial, para introducir cuantificadores, así como las reglas de
especificación universal y existencial para eliminar cuantificadores.
Ejemplos: Demuestra la validez de las siguientes expresiones.
1. ∀x[E( x ) ∨ P( x ) → ¬U ( x )] ∧ U ( x ) ⇒ ∀x¬E( x )
Solución:
Líneas de derivación
Premisas y reglas empleadas
1. ∀x [ E ( x) ∨ P( x) → ¬U ( x) ]
2. U ( x)
3. E ( x) ∨ P( x) → ¬U ( x)
4. ¬ ( E ( x) ∨ P( x) )
P1
P2
EU (1)
I12 (2,3)
5. ¬E ( x) ∧ ¬P( x)
6. ¬E ( x)
7. ∀x¬E ( x)
E9 (4)
I1 (5)
GU (6)
2. ∀x[A( x) → M ( x)] ∧ ∀x[H ( x) → A( x)] ⇒ ¬∀x[H ( x) ∧ ¬M ( x)]
3. ∃x[F ( x) ∧ S ( x)] → ∀x[M ( x) → W ( x)] ∧ ∃x[M ( x) ∧ ¬W ( x)] ⇒ ∀x[F ( x) → ¬S ( x)]
∀x ( R( x) → P( x) )
4.
∀x ( P( x) → ¬S ( x) )
∀x ( R( x) ∧ Q( x) → S ( x) )
∀x ( R( x) → ¬( P( x) → Q( x)) )
5. Solo los tontos se dejan engañar por los vendedores ambulantes. Antonio se deja
engañar por Juan. Antonio no es tonto. Por lo tanto, Juan no es un vendedor
ambulante.
Elaboró: afmorales
44
Cálculo de Predicados
6. Ningún pato quiere bailar. No hay ningún oficial que no quiera bailar. Todas mis
aves de corral son patos. En consecuencia, ninguna de mis aves de corral son
oficiales.
7. A ningún pescador le gustan los paletos. Todos los habitantes del pueblo son
paletos. Por lo tanto, a ningún pescador le gustan los habitantes del pueblo.
8. Solo las buenas personas ayudan a los pobres. Ninguna buena persona es
aficionada a la filosofía. Antonio ayuda a Juan. Antonio es aficionado a la filosofía.
En consecuencia, Juan no es pobre.
9. Algunos mexicanos son amigos de todos los españoles. Ningún mexicano es
amigo de los aficionados a la lógica. Por lo tanto, ningún español es aficionado a
la lógica.
10.Ana es madre de Ernesto. José es padre de Ana. Un abuelo de una persona es
alguien que es padre del padre o de la madre de esa persona. Por lo tanto, José
esdabueloddedErnesto.
Elaboró: afmorales
45
Cálculo de Predicados
Problemas Propuestos
Primera parte: construye la fórmula bien formada de cada uno de los siguientes
argumentos.
1. Algunas alumnas del último semestre que gustan del inglés no son bonitas.
2. Ningún alumno de último semestre es aficionado al ajedrez y a las matemáticas
simultáneamente.
3. Todos los alumnos del último semestre solo salen a pasear con alumnas de
primer semestre.
4. Hay alumnos de último semestre que son aficionados al ajedrez pero no a las
matemáticas.
5. Martín sale a pasear con novatas solamente si son bonitas.
6. Sólo los médicos titulados pueden cobrar por un tratamiento
7. Un niño señalo con el dedo al culpable.
8. El resfriado común nunca es mortal.
9. Solo los ciudadanos mexicanos pueden votar en las elecciones de México.
10.No todos los aspirantes fueron aceptados.
11.Ningún aspirante fue aceptado.
12.El Sr. López es padre de Guillermo.
13.Todos los perros pueden matar a cualquier gato.
14.O el Sr. Gómez lleva a Pedro en el coche o llegará tarde a la cita.
15.Si Juan no es hermano de María o María no es la cuñada de Juan, entonces el Sr.
Pérez no es el padre de Antonio y Antonio es el primo de María.
Elaboró: afmorales
47
Cálculo de Predicados
Segunda parte: Construya una prueba formal de la validez o invalidez de cada uno
de los siguientes argumentos.
1.
2.
3.
4.
5.
6.
7.
∃x[C ( x) ∧ ¬(D( x) → E ( x) )]
∀x[C ( x) ∧ D( x) → F ( x)]
∃x[C ( x) ∧ ¬(D( x) → C ( x) )]
¬∀x[(F ( x) → E ( x) ) ∨ C ( x)]
8. Ningún existencialista aprecia a los positivistas. Todos los miembros del
Círculo de Viena son positivistas. Por lo tanto, ningún existencialista aprecia a
ningún miembro del Círculo de Viena.
Elaboró: afmorales
48
Cálculo de Predicados
9. Arturo es un muchacho que no tiene carro. María sale a pasear solo con
muchachos que tienen carro. Por lo tanto María no sale a pasear con Arturo.
10. Cualquiera que trabaje en la fábrica, está sindicalizado o tiene puesto de
confianza. Antonio no está sindicalizado y tampoco tiene puesto de confianza.
Por lo tanto, Antonio no trabaja en la fábrica.
11. Los empleados son entusiastas o fracasados. Los empleados no son todos
fracasados. Por lo tanto hay, empleados entusiastas.
12. Todos los científicos son racionalistas. Ningún filósofo es racionalista. En
consecuencia, ningún filósofo es científico.
Elaboró: afmorales
49
Relaciones y grafos
4.0 RELACIONES Y GRAFOS
La conclusión es que sabemos muy poco y sin embargo es
asombroso lo mucho que conocemos. Y más asombroso todavía
que un conocimiento tan pequeño pueda dar tanto poder
Bertrand Arthur William Russell
RELACIONES
4.1 Introducción
Las bases de datos relacionales utilizan relaciones n − arias para su almacenamiento
y acceso a ellos. Las relaciones binarias son conjuntos de pares y aparecen en
numerosos contextos. Los métodos gráficos son útiles para visualizar relaciones y
para realizar operaciones matemáticas que incluyan relaciones, es conveniente
representarlas como matrices. Existe cierto número de operaciones que afectan a las
relaciones, como es la composición de 2 relaciones; además todas las operaciones
disponibles para conjuntos están también disponibles para las relaciones.
En esta sección se estudiará formalmente las parejas de objetos que comparten
algunas características o propiedades en común. La estructura matemática para
agrupar estas parejas en conjuntos es la teoría de relaciones binarias. Las relaciones
son fundamentales en el área de computación. Una estructura compuesta de datos,
tal como un arreglo, lista, o árbol, es generalmente usada para representar
simultáneamente a un conjunto de datos y a una relación que se cumple entre los
elementos del conjunto. Para poder introducir el concepto de relación binaria se
necesita precisar lo que significa un par ordenado de objetos y definir el producto
cartesiano de dos conjuntos.
4.2 Producto cartesiano
Se puede dar un tratamiento formal a estas ideas con la definición de producto
cartesiano. Se llama par ordenado ( x, y ) , al par, cuya primera componente
pertenece al conjunto
y cuya segunda componente pertenece al conjunto B . Las
parejas ordenadas se representan entre paréntesis, lo cual significa, que además de
los elementos, también importa su orden.
Definición: El conjunto, cuyos elementos son las parejas ordenadas que se formar al
y como segunda
elegir como primera componente a los elementos del conjunto
componente a los elementos del conjunto B ; se llama conjunto producto o producto
cartesiano de
; se representa por
y se lee “ A cruz B ;aentonces:
.
Es decir:
.
Elaboró: afmorales
51
Relaciones y grafos
4.2.1 Representación gráfica
El producto cartesiano se puede representar gráficamente utilizando diagramas de
Venn o mediante un sistema de ejes coordenados.
1. Graficar el conjunto:
A× B =
{(1, 1) ; (1, 2 ) ; (1, 3) ; ( 2, 1) ; ( 2, 2 ) ; ( 2, 3) ; ( 3, 1) ; ( 3, 2 ) ; ( 3, 3) ; ( 4, 1) ; ( 4, 2 ) ; ( 4, 3)}
Utilizando los diagramas de Venn,
al contar las líneas que unen los
elementos de ambos conjuntos, se
verifica que son 12.
Figura 4.1
Utilizando los ejes coordenados, se
representan en el eje horizontal los
elementos del primer conjunto y en
el eje vertical los elementos del
segundo conjunto. Cada pareja
estará representado por el punto
donde se intersectan las rectas
paralelas a los ejes.
Figura 4.2
D = { − 2, 4 } y
; calcúlese D × E y representarlo
gráficamente.
3. Sí A = { − 3, 1, 2 }, determina el producto cartesiano de A × A y representarlo
geométricamente.
2. Si
La definición de producto cartesiano, también es aplicable al conjunto de los números
reales R ; esto es R × R o bien R 2 . Cada elemento de R × R corresponde a un
punto del plano y cada punto del plano le corresponde una pareja de R 2 .
Elaboró: afmorales
52
Relaciones y grafos
4. Si A = {x : x ∈ R ; − 1 ≤ x ≤ 3
}y
B = { 2 } ; obténgase A × B .
Solución
A × B = {( x, y ) : x ∈ A, y ∈ B} = {( x, 2 ) : − 1 ≤ x ≤ 3, x ∈ R}
Gráficamente, se tiene:
Figura 4.3
5. Dado
; Obténgase B × A .
y
6. Sea A = {x : x ∈ R ; − 2 ≤ x ≤ 3
}
y
B = {y : y ∈ R ; − 1 ≤ y ≤ 2 } .
4.3 Relaciones
Para determinar una relación, se necesitan dos conjuntos A y B y una proposición
abierta en dos variables, esta proposición es la regla que permite determinar el
conjunto R de las parejas que se forman en A × B . Formalmente las relaciones
binarias se definen como:
Definición: Sean A y B dos conjuntos diferentes del conjunto vacío. Una relación de
A en B es un conjunto de pares ( x, y ) :
. Si ( x, y ) ∈ R ; se dice que x
está relacionado con y : Para expresar que R es una relación de A en B ; se
representa como:
.
Al conjunto A , se le llama dominio de R , sus elementos se representan por " x" , el
conjunto B , es el codominio de R y sus elementos que son la segunda componente
se llama imagen y los elementos se representan por " y" . Una relación, es un
subconjunto del producto cartesiano ( R ⊆ A × B ) . De hecho A × B es en sí mismo una
relación. La relación universal contiene todos los pares posibles. El opuesto de la
relación universal es la relación vacía, que no contiene ningún par. Todas las demás
relaciones deben estar entre estos dos casos extremos.
Elaboró: afmorales
53
Relaciones y grafos
Ejemplos:
1. Sea A el conjunto de proveedores y B el conjunto de productos. Supóngase que
los proveedores son S1 y S 2 y los productos son P1 , P2 y P3 .
Sean A = {S1 , S 2 } y B = {P1 , P2 , P3 }
El producto cartesiano de A y B es:
A × B = {(S1 , P1 ); (S1 , P2 ); (S1 , P3 ); (S 2 , P1 ); (S 2 , P2 ); (S 2 , P3 )}
Ahora defínase una relación R como los pares ( x, y ) , donde " x" es un suministrador,
" y" es un producto; luego " x" tiene en existencia al producto " y"
Sea:
S1 tiene P1 y P3
S 2 tiene P2 y P3
R = {( S1 , P1 ) ; ( S1 , P3 ) ; ( S 2 , P2 ) ; ( S 2 , P3 )}
∴ R ⊂ A× B
xRy ≡ (x, y ) ∈ R ; es decir; S1 RP1 ; S1 RP3 ; S 2 RP2 S 2 RP3
2. Sean A = {Susana, Rosa, Vicente, Augusto, Laura}
B = {Díaz, Contreras, Gil , Estrada, Muñoz, Juárez, Pérez}
Obténgase una relación con la siguiente característica: que el número de letras
del nombre sea igual al número de letras de apellido.
3. Una línea aérea proporciona servicio a cinco ciudades C1, C2, C3, C4, C5 la tabla
muestra el costo (en dólares) del viaje de Ci a C j .
De / A
C1
C2
C3
C4
C5
C1
190
110
190
200
C2
140
180
200
100
C3
100
200
120
200
C4
150
160
190
C5
200
220
250
150
150
Defina la relación R sobre A = {C1 , C 2 , C3 , C 4 , C5 } tal que Ci RC j si y sólo si el
costo de ir de Ci a C j es menor o igual a 150 dólares.
Elaboró: afmorales
54
Relaciones y grafos
4. Sea: A = {1, 2, 3, 4, 5}. Defina la relación R (menor que) en el conjunto A .
5. Si A = { 3, 4, 5, 6} y B = { 4, 5, 6} . Obténgase R = {( x, y ) : x > y}
6. Sea
. Obténgase una relación R , de modo que a divide a
b.
7. Sea
, defina una relación R ,de modo que:
.
R = {(x, y ) : 2 x + y > 3} con x, y ∈ R .
9. R = ( x, y ) : x 2 + y 2 = 1 con x, y ∈ R .
8.
{
10. R = {(x, y ) : 9 x
}
2
}
+ 4 y = 36 con x, y ∈ R .
2
4.3.1 Gráfica de una relación
De forma similar que el producto cartesiano de dos conjuntos, una relación puede
representarse geométricamente con diagramas de Venn o en un sistema de ejes
coordenados. La gráfica de una relación R : A → B es el conjunto G de todos los
puntos del plano que representan los pares ordenados del producto cartesiano A × B ,
con la propiedad de que el punto de coordenadas ( x, y ) pertenece a la gráfica si y
sólo si el par ordenado es un elemento de la relación; es decir, la gráfica de una
relación es el conjunto.
G = {( x, y ) ∈ R × R}
En la práctica, la relación se utiliza especificando únicamente la regla que la define,
admitiendo de forma implícita que son relaciones de R en R .
Ejemplos: graficar las siguientes relaciones
1. 2 x + 3 y = 1
Despejando la variable " y" y construyendo la tabla con algunos valores, se
obtiene:
3y = 1 − 2x
1 − 2x
y=
3
y
x
3
−4
−1
2
1
−1
5
−3
Figura 4.4
Elaboró: afmorales
55
Relaciones y grafos
2.
x2 − y2 = 1.
x
−3
−2
−1
0
y
1
2
3
Figura 4.5
4.4.
Dominios y rangos
Sea R ⊆ A × B una relación de A en B , al conjunto A se le llama dominio y B se le
denomina rango. El dominio de R (relación) es el conjunto de elementos de A que
están relacionados con algún elemento de B . De modo similar, el rango de R es el
conjunto de todos los elementos de B que están relacionados con algún elemento de
A , formalmente se expresa en la siguiente definición.
Definición: Sea R una relación de A en B . El dominio de R se denota por domR , es
el conjunto de todos los elementos de x ∈ A , que aparecen en, al menos, un par
( x, y ) ∈ R . El cual se expresa como: domR =
{ x : ∃y ( x, y ) ∈ R}
Definición: El rango de R , denotado por ranR , es el conjunto de todos los elementos
y ∈ B que aparecen, en al menos un par ( x, y ) ∈ R . Esto se expresa simbólicamente
como: ranR =
{ y : ∃x ( x, y ) ∈ R}
Ejemplos: Calcular el dominio, el rango y graficar las siguiente relaciones.
1.
R = {( 2, c ), ( 1, d ), ( 3, d ), ( 2, a )}
Solución
domR = {1, 2, 3 }
ranR = { a, c, d }
Figura 4.6
Elaboró: afmorales
56
Relaciones y grafos
2.
3.
4.
5.
6.
R = {( 1, r ), ( 2, s )( 3, r )}
R = {( 1, 2), ( 1, 3), ( 1, 4), ( 1, 5), ( 2, 3), ( 2, 4), ( 2, 5), ( 3, 4 ), ( 3, 5), ( 4, 5)}
R = {( x, y ) : xRy si y sólo si x = y} con x ∈ R y y ∈ R .
R = {( x, y ) : xRy si y sólo si x divide a y} con x ∈ Z + y y ∈ Z + .
{
}
R = ( x, y ) : y 2 + 20 x + 2 y − 39 = 0


x
y2
+
= 1
7. R = (x, y): xRy si y sólo si
4
9


2
2
8. R = {( x, y ) : 9 x − 4 y − 54 x + 8 y + 113 = 0}
2
4.5 Algunas operaciones entre relaciones
4.5.1 Relación inversa
Toda relación R de A en B , se puede asociar una relación inversa R -1 de B en A .
Esencialmente, la relación inversa tiene el par ( y, x ) , donde la relación original tiene
el par ( x, y ) , tal como se indica en la siguiente definición.
Definición: Si R : A → B es una relación, entonces la relación inversa R −1 : B → A , se
define como {( y, x ) : ( x, y ) ∈ R} . Por lo tanto se puede expresar como:
Si, xRy, entonces yR −1 x .
Ejemplos: determinar la relación inversa en cada uno de los siguientes ejercicios.
1. 𝑅𝑅 = {(−2, −5); (−1, −3); (0, −1); (1, 1); (2, 3); (3, 5); (4, 7)}
Solución
𝑅𝑅−1 = {(−5, −2); (−3, −1); (−1, 0); (1, 1); (3, 2); (5, 3); (7, 4)}
2. R = {( x, y ) : xRy si y sólo si x < y}
Solución
R −1 = {( y, x ) : yRx si y sólo si x > y}
3. S = {( x, y ) : xRy si y sólo si x es padre de y}
4.5.2 Composición de relaciones.
Matemáticamente la composición de dos relaciones está dada por:
Definición: Sea R : A → B y R : B → C dos relaciones. La composición de R y S , se
denotan como R  S , contiene los pares ( x, z ) si y sólo si existe un objeto intermedio
" y" tal que: ( x, y ) está en R y ( y, z ) está en S .
∃y ( xRy ∧ yRz ) .
Simbólicamente se expresa como: x ( R  S ) z =
Elaboró: afmorales
57
Relaciones y grafos
Esta definición implica que ( x, z ) está en la composición de las relaciones hermana y
padre, si existe un individuo " y" tal que " x" es hermana de " y" e " y" es padre de
" z" . A esta relación se le denomina “relación tía”. Por tanto la relación tía es la
composición de la relación hermana y padre. En general, para determinar si el par
(x, z ) está en la relación R  S , se necesita siempre un intermediario (hermana),
como en el caso de la relación tía: tal que sea válida xRy e ySz .
La composición de dos relaciones se puede representar mediante un gráfico. Sean
las R : X → Y y S :Y → Z . Se dibujan todos los nodos X a la izquierda, todos los
nodos de Z a la derecha, y todos los nodos del conjunto intermedio Y en el medio.
Se asume que los elementos de X van desde x1 hasta x4 , los elementos de Y van
desde y1 hasta y 4 , y los elementos de Z van desde z1 hasta z5 .
Gráficamente se muestra en la siguiente figura
Figura 4.7
De acuerdo con lo que ha visto, el par ( xi , z k ) está en R  S si y sólo si existe un
intermediario y j tal que existe un arco que va desde xi a y j , y de y j hasta z k . Por
ejemplo ( x1 , z 4 ) está en R  S , porque existe un arco desde x1 a y 2 y de y 2 a z 4 . Por
otra parte ( x1 , z3 ) no está en la relación R  S por que no existe y j a través del cual x1
pueda acceder a z3 .
Por lo tanto la relación resultante es: R o S = {( x1 , z1 ) , ( x1 , z2 ) , ( x1 , z4 ) , ( x4 , z3 )}
La composición es una operación asociativa, esto es, si R, S y P son tres
relaciones, entonces se cumple que: ( R o S ) o P = R o ( S o P ) . Cuando se trate de la
composición de varias relaciones, los paréntesis pueden suprimirse.
Si S1 , S 2 y S 3 son tres relaciones, entonces x ( S1 o S 2 o S 3 ) y es verdadera si y sólo
si existen exactamente dos intermediarios, a través de los cuales x tiene acceso a y
Elaboró: afmorales
58
Relaciones y grafos
Por tanto, la composición de tres relaciones es el conjunto de todos los pares (x, y )
tales que x puede alcanzar al objeto y en exactamente tres pasos. En general, la
composición de n relaciones S1 ; S 2 ;  ; S n contiene el conjunto de todos los pares
(x, y ) tales que
x puede alcanzar a y en, exactamente n pasos.
Si R : A → A es una relación, entonces R  R es el par (x, y ) tal que x puede
alcanzar a y en exactamente dos pasos. Normalmente, se abrevia R  R en la forma
R 2 , RoRoR por R3 , y así sucesivamente. Obviamente R n es el conjunto de todos
los pares (x, y ) tales que x puede alcanzar a y en exactamente n pasos.
Ejemplos.
1. Se tienen cinco personas A; B; C ; D y E ; C es el dueño del camión llamado
aventurero y E es el dueño del camión llamado imperioso. A es amigo de
B y D . B es amigo de C y C es amigo de E . Sea R la relación “ x es amigo
de y ” y sea S la relación “ y es dueño del camión z ”.
Calcular la relación R  S .
Solución
R = {( A, B ); ( A, D ); (B, C ); (C , E )}
S = {(C , aventurero); (E , imperioso )}
R  S = {(B, aventurero ); (C , imperioso )}
2. Sean: R = {(1, 2); (3, 4 ); (2, 2 )}
R = {(4, 2); (2, 5); (3, 1); (1, 3)}
Calcular: R  S ; S  R ; R  (S  R ) ; (R  S )  R ; R  R ; S  S ; R  R  R .
4.6
Propiedades de las relaciones
En diversas aplicaciones de las ciencias de la computación se utilizan conocimientos
de las propiedades que existen entre relaciones determinadas por conjuntos, se hace
necesario analizar un grupo de propiedades asociadas con las relaciones. En el
conjunto de los números enteros, existen tres relaciones importantes, las cuales son:
“ = ”; “ < ” y “ ≤ ”.
Una propiedad importante de la relación de igualdad es su reflexividad, esto quiere
decir que para cada entero x tiene que ser x = x . Esta propiedad no es admisible
con la relación “ < ”, pero es valida para “ ≤ ”; es decir, esta relación también es
Elaboró: afmorales
59
Relaciones y grafos
reflexiva. La segunda propiedad de la igualdad es su simetría; es decir, si x = y
implica que y = x , esta propiedad no es aplicable a la relación “ < ” ni a la relación “
≤ ”. La tercera propiedad de la igualdad es la transitividad, esto significa que si
=
x y=
y y z implica que
=
x z . Esta propiedad también es válida para “ < ” y “ ≤ ”; es
decir, si x < y y y < z implica que x < z y si x ≤ y y y ≤ z implica que x ≤ z .
Relaciones reflexivas
Una relación R de un conjunto A es reflexiva si el par
( x, y ) ∈ R
para todos los
valores de x ∈ A , es decir xRx para toda x ∈ A . Una relación R de un conjunto A es
/ para toda x ∈ A .
no reflexiva sí xRx
Definición: Una relación binaria R sobre A es reflexiva, si para x ∈ A , el par ( x, x )
está en la relación. Simbólicamente se puede expresar como:
R es reflexiva sí y sólo sí ∀x ( xRx )
En algunos casos R no contiene ningún elemento del tipo ( x, x ) . En este caso R se
le denomina no reflexiva.
NOTA: Reflexiva significa que xRx es verdadera para toda x y no reflexiva que xRx
no es verdadera para ninguna x . Si xRx es cierta para alguna “ x ”, y es falsa para
otras, entonces la relación no es reflexiva. En algunos casos R no contiene ningún
elemento del tipo ( x, x ) , en este caso R se le denomina no reflexiva o antireflexiva.
Ejemplos
1. Sea A
=
2, 3} y R {(1, 2), (1,1), (2, 2), (3, 2), (3,3)}
{1,=
determinar si la relación
cumple la propiedad reflexiva.
Solución
La relación es reflexiva porque: (1,1) ∈ R, (2, 2) ∈ R y (3,3) ∈ R .
2. Dado el =
conjunto A {1,
=
2, 3} y R {(1, 2), (1,1), (2,1), (2, 2), (3, 2)} determinar si la
relación cumple la propiedad reflexiva.
Solución
La relación no es reflexiva porque: (3,3) ∉ R .
=
a, b, c, d , e} y R {(a, a), (a, c), (b, b), (c, c), (c, e), (d , d ), (e, e)} determinar
3. Sea A {=
si la relación cumple la propiedad reflexiva.
T {( x, y ) ∈ R × R : x ≤ y} determinar si la relación es reflexiva
4. Sea=
R
5. Sea=
{( x, y ) ∈ N × N : x < y}
determinar si la relación es reflexiva o antireflexiva.
Elaboró: afmorales
60
Relaciones y grafos
Relaciones simétricas
Una relación R en un conjunto A es simétrica, si xRy , entonces yRx . De esto se
desprende que R no es simétrica si tiene algunas “ x ” y “ y ” en A , de modo que xRy
, pero yR/ x . Una relación R en el conjunto A es asimétrica, si en todos los casos xRy
, se tiene que yR/ x . Por lo tanto, R no es asimétrica si se tienen algunas “ x ” y “ y ” en
A , con ambas xRy y yRx .
Una relación R en un conjunto A es antisimétrica, si en todos los casos en ( x, y ) ∈ R
implica que ( y, x) ∉ R a menos que x = y . Es decir; si tanto ( x, y ) como ( y, x) están
en R , entonces se tiene que x = y . La contrapositiva de esta afirmación es que R
es antisimétrica, sí x ≠ y entonces xR/ y ó yR/ x. De esto se desprende que: R no es
antisimétrica, si se tiene “ x ” y “ y ” en A, x ≠ y y ambas xRy y yRx .
Definición: Una relación R sobre un conjunto A es simétrica, si para toda “ x ” y “ y ”
pertenecientes al conjunto A , es decir, si xRy implica que yRx . Simbólicamente se
expresa como:
R es simétrica sí y sólo sí ∀x∀y ( xRy → yRx)
Definición: Una relación R sobre un conjunto A es asimétrica, si para todo ( x, y ) ∈ R
se tiene que el par ( y, x) ∉ R . Simbólicamente se expresa como:
R es asimétrica sí y solo sí ∀x∀y ( xRy → yR/ x)
Definición: Una relación R sobre un conjunto A es antisimétrica, si para toda y ≠ x ,
xRy excluye a yRx ; es decir, si se alcanzan xRy e yRx , entonces x = y .
Simbólicamente se expresa como:
R es antisimétrica sí y solo sí ∀x∀y ( xRy ∧ yRx → x = y)
Ejemplos: Determinar, si las siguientes relaciones son simétricas.
=
1 Sean A
Solución
2, 3, 4} y R {(1, 2), (2,1), (2, 2), (2,3), (3, 2), (3, 4), (4,3), (4, 4)}
{1,=
1, 2 ∈ A,
si (1, 2) ∈ R → (2,1) ∈ R
2,3 ∈ A,
si (2,3) ∈ R → (3, 2) ∈ R
3, 4 ∈ A,
si (3, 4) ∈ R → (4,3) ∈ R
2 ∈ A, si (2, 2) ∈ R → (2, 2) ∈ R(2 =
2)
4 ∈ A, si (4, 4) ∈ R → (4, 4) ∈ R(4 =
4)
Por tanto, la relación es simétrica
Elaboró: afmorales
61
Relaciones y grafos
=
2 Sean A
2, 3, 4} y R {(1,1), (2, 2), (2,3), (3, 2), (3,3), (3, 4), (4, 4)}
{1,=
Solución
La relación no es simétrica porque:
para 3, 4 ∈ A, el (3, 4) ∈ R, pero (4,3) ∉ R
3 Sea A = conjunto de estudiantes de un salón de clase ,
4
S = {( x, y ) : xSy sí y sólo sí x es sobrino de y}
+
=
y T
5 A Z=
+
y R
=
6 A Z=
{( x, y) : xTy sí
{( x, y) : xRy sí
y sólo sí x ≥ y}
y sólo sí x divide a y}
Relaciones transitivas
Una relación R sobre el conjunto A es transitiva, siempre que xRy “y” yRz ,
entonces xRz . Una relación R en A es no transitiva si existen “ x ”, “ y ” y “ z ” en A
de manera que xRy “y” yRz y, pero x R/ z . Si no existen “ x ”, “ y ” y “ z ”, entonces R es
transitiva).
Definición: Una relación R sobre A es transitiva, si para todo “ x ”, “ y ” y “ z ” en A
siempre que xRy “y” yRz , entonces xRz . Esto es:
R es transitiva sí y sólo sí ∀x∀y∀z ( xRy ∧ yRz → xRz ).
La transitividad está relacionada con la composición, esto quiere decir que la
definición anterior se puede expresar como: ∀x∀z (∃y )( xRy ∧ yRz ) → xRz
Ejemplos: determina, si las siguientes relaciones son transitivas.
=
a, b, c} y
R {(a, a ), (a, b), (a, c)} .
1. A {=
Solución
( a, a ) ∧ ( a, b) ∈ R → ( a, b) ∈ R
Como: (a, a ) ∧ (a, c) ∈ R → (a, c) ∈ R
( a, a ) ∧ ( a, a ) ∈ R → ( a, a ) ∈ R
Por tanto, la relación es transitiva.
=
a, b, c} y
T { (a, b), (a, c)} .
2. A {=
Solución
Como: (a, b) ∧ (b, c) ∈ T ; pero (a, c) ∉ T
Por tanto, la relación no es transitiva.
=
=
2, 3, 4} y T { (1, 2), (1,3), (4, 2)} .
3. A {1,
Elaboró: afmorales
62
Relaciones y grafos
=
4. A
=
5. A
=
6. A
=
7. A
a, b, c, d , e} y R {(a, a), (b, b), (c, c), ( d , d ), (e, e), (b, c), (b, a)}
{=
a, b, c, d , e} y R {(a, a ), (a, b), (b, a), (b, b), (b, c), (b, e), (c, e) (b, d ), (d , a), (e, e)}
{=
Z=
y R { ( x, y ) : x < y}
+
Z=
y R {( x, y ) : xRy sí y sólo sí x divide a y}
Relaciones de equivalencia
La relación de equivalencia más importante es la relación de igualdad. Esta relación
es reflexiva porque x = x para todo x . Es simétrica porque si x = y implica que y = x
. Finalmente, es transitiva porque si x = y “y” a su vez y = z , implica que x = z . En
general, dos objetos “ x ” y “ y ” están en una relación de equivalencia si son iguales
en un cierto aspecto.
Definición: Una relación R , es una relación de equivalencia si y sólo si, es reflexiva,
simétrica y transitiva.
Ejemplos: Determinar si las siguientes relaciones son relaciones de equivalencia.
=
A
1. .
a, b, c, d , e} y R {(a, a ), (b, b), (c, c), (d , d ), (e, e), ( a, e), (b, c) (c, b), (e, a)}
{=
Solución
Como: (a, a ) ∈ R, (b, b) ∈ R, (c, c) ∈ R, (d , d ) ∈ R, (e, e) ∈ R , entonces R es reflexiva.
a, e ∈ R,
si (a, e) ∈ R → (e, a ) ∈ R
b, c ∈ R,
si (b, c) ∈ R → (c, b) ∈ R
a ∈ R, si (a, a ) ∈ R → (a, a ) ∈ R
b ∈ R, si (b, b) ∈ R → (b, b) ∈ R
c ∈ R, si (c, c) ∈ R → (c, c) ∈ R
d ∈ R, si (d , d ) ∈ R → (d , d ) ∈ R
e ∈ R, si (e, e) ∈ R → (e, e) ∈ R
Por tanto la relación es simétrica
Elaboró: afmorales
63
Relaciones y grafos
( a , a ) ∧ ( a , e) ∈ R → ( a , e) ∈ R
(b, b) ∧ (b, c) ∈ R → (b, c) ∈ R
(c, c ) ∧ (c, b ) ∈ R → (c, b ) ∈ R
(e, e) ∧ (e, a ) ∈ R → (e, a ) ∈ R
( a, a ) ∧ ( a, a ) ∈ R → ( a, a ) ∈ R
(b, b) ∧ (b, b) ∈ R → (b, b) ∈ R
( c, c ) ∧ ( c, c ) ∈ R → ( c, c ) ∈ R
(d , d ) ∧ (d , d ) ∈ R → (d , d ) ∈ R
(e, e) ∧ (e, e) ∈ R → (e, e) ∈ R
Por tanto la relación es transitiva
Como se cumplen las tres propiedades, entonces la relación es transitiva.
=
2 A
=
3 A
=
4 A
2,3, 4} y R {(1,1), (1, 2), (1,3), (2,1), (2, 2), (2,3), (3,1), (3, 2), (3,3), (4, 4)}
{1,=
Z=
y R { ( x, y ) : xRy sí y sólo sí x ≤ y}
Z =
y R { (a, b) : aRb sí=
a − b 2k }
4.7 Cerradura de relaciones
Si R es una relación sobre un conjunto A , puede ocurrir que R carezca de algunas
de las propiedades relacionales importantes, especialmente la reflexividad, simetría y
transitividad. Si R no posee una propiedad en particular, se pueden agregar a R
pares relacionados hasta obtener una relación que si cumpla la propiedad requerida.
Naturalmente, se desea agregar el menor número de pares posible, por lo cual se
necesita obtener una relación más pequeña R1 en A que contenga a R y posea la
propiedad que se desea. En ocasiones R1 no existe. Si existe una relación tal como
R1 , se llama cerradura de R con respecto a la propiedad en cuestión.
Cerradura reflexiva
Supóngase R una relación sobre un conjunto A , y que R no es reflexiva. Sea
A = {1, 2, 3, 4} y R = {(1,3), (1, 4), (2, 2), (3,3), (4,1)} , la cual no es reflexiva. Para
obtener la relación reflexiva R1 se necesita agregar los pares (1,1) y (4, 4) . Así
R1= R ∪ ∆ es la relación reflexiva más pequeña en A que contiene a R , es decir, la
cerradura reflexiva de R es R ∪ ∆ .
Cerradura simétrica
Supóngase R una relación sobre un conjunto A , y que R no es simétrica. Sea
A = {1, 2, 3, 4} y R = {(1,3), (1, 4), (2, 2), (3,3), (4,1)} , la cual no es simétrica. Para
Elaboró: afmorales
64
Relaciones y grafos
obtener la relación simétrica R1 se necesita agregar el par (3,1) . Así R1= R ∪ R −1 es la
relación simétrica más pequeña en A que contiene a R , es decir, la cerradura
simétrica de R es R ∪ R −1 .
Cerradura transitiva
Supóngase R una relación sobre un conjunto A , y que R no es transitiva. Sea
A = {1, 2, 3, 4} y R = {(1, 2), (2,3), (3, 4), (2,1)} , la cual no es transitiva. Para obtener la
relación transitiva R1 se necesitan agregar los pares (1,1), (1,3) , (2, 2) y (2, 4) . En
general, si existe una cadena de x a y , es decir, si hay puntos x1 , x2 , ..., xm−1 , tales
que
xRx1 , x1Rx2 ,..., xm−1Ry , entonces ( x, y ) debe estar en R1 . Si una cadena de x a y y
otra de y a z entonces hay una cadena de x a z . Por tanto, el conjunto de pares
( x, y ) conectados por cadenas es una relación transitiva y es la mínima relación
transitiva que contiene a R .
Elaboró: afmorales
65
Relaciones y grafos
Problemas propuestos
A Determina el dominio y rango de relación.
1. Sean A = {a, b, c, d }; B = {1, 2, 3} y R = {(a, 1); (a, 2); (b, 1); (c, 2 ); (d , 1)} .
{
2. Sean A = {1, 2, 3, 4}; B = {1, 4, 6, 8, 9} y R = (a, b ) : a
}
sR y sí b só b =í al 2 o.
3.
A = {1, 2, 3, 4, 8}; B = {1, 4, 6, 9} y R = {(x, y ) : x
s Ry s í ys óx d í l aio yv} .
4.
A = {1, 2, 3, 4, 5} = B y R = {(x, y ) : x
sR y sí y só x ≤í yl } .
5.
A = {1, 2, 3, 4, 8} = B y R = {(x, y ) : x
sR y sí y só x + íy l≤ 9o}.
B Determinar si la relación es reflexiva, simétrica, asimétrica, antisimétrica y
transitiva.
1.
R = {(1, 1); (1, 2); (2, 1); (2, 2 ); (3, 3); (3, 4 ); (4, 3); (4, 4 )}
2.
R = {(1, 3); (1, 1); (3, 1); (1, 2 ); (3, 3); (4, 4 )}
3.
R = {(1, 2); (1, 3); (3, 1); (1, 1); (3, 3); (3, 2 ); (1, 4 ); (4, 2 ); (3, 4 )}
4.
R = {(1, 1); (1, 2); (1, 3); (1, 5); (2, 3); (4, 3); (4, 2 ); (4, 5); (4, 4 ); (5, 3)}
5. Sean A = {1, 2, 3, 4} y R = {(a, b ) : a
sR y sí bsó a ≤í bl + 1o}
6. Sean A = {1, 2, 3, 4} y R = {(a, b ) : a
s Ry sí bs ó a −íb l = o
2}
7. Sean A = {1, 2, 3, 4} y R = {(a, b ) : a
s Ry s í sb óM í (al, b )o=C1}
Elaboró: afmorales
66
Bibliografía
BIBLIOGRAFÍA
1. INTRODUCCIÓN A LA LÓGICA MATEMÁTICA
P. SUPPES – SHIRLEY HILL
REVERTÉ
2. INTRODUCCIÓN A LA LÓGICA
IRVING M. COPI - CARL COHEN
LIMUSA
3. LOGICA SMMBOLICA
IRVING M. COPI
CECSA
4. FUNDAMENTOS DE LÓGICA COMPUTACIONAL
JUAN FRAUSTO SOLÍS – GILDARDO SÁNCHEZ ANTE
TRILLAS
5. LÓGICA SIMBÓLICA PARA INFORMÁTICOS
PASCUAL JULIÁN IRANZO
ALFAOMEGA
6. ESTUDIOS PREVIOS SOBRE LAS DIFICULTADES EN LA FORMALIZACIÓN
DE ENUNCIADOS
TRABAJO ELABORADO POR: JOSE LUIS RAMÍREZ ALCÁNTARA
JUNIO 2002
7. TRABAJO DE INVESTIGACIÓN PARA TESIS DOCTORAL
M. EN C. JOSÉ LUIS RAMÍREZ ALCÁNTARA
2002 – 2004
8. ESTRUCTURAS DE MATEMÁTICAS DISCRETAS PARA LA COMPUTACIÓN
BERNARD KOLMAN, ROBERT C. BUSBY, SHARON ROSS
PRENTICE HALL
9. MATEMÁTICAS DISCRETA Y COMBINATORIA (Una introducción con
aplicaciones).
RALPH P. GRIMALDI
ADDISON WESLEY LONGMAN.
Elaboró: afmorales