Lógica y Estructuras Discretas: Oihane Barcenilla Martín

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 66

Lógica y estructuras

discretas

Oihane Barcenilla Martín


Tema 1 Lógica de proposiciones y de predicados de primer orden.
Lógica de proposiciones
Sintaxis

El alfabeto de la Lógica de Proposiciones debe proporcionar los símbolos necesarios para representar
proposiciones sobre el mundo. Como el número de proposiciones que pueden manejarse en un mismo
razonamiento no está limitado, debe proveer un número infinito de letras proposicionales.
Consta de los siguientes elementos:
1. Infinitas letras proposicionales: p0, p1, p2, p3 . . .
2. Símbolos lógicos: constantes (^,), conectiva monaria () y conectivas binarias (⋀,⋁,→,↔)
3. Dos símbolos auxiliares de puntuación: paréntesis izquierdo’(’ y derecho ’)’.
En las exposiciones teóricas, el número de letras proposicionales que se consideran simultáneamente es
pequeño (por ejemplo, de p0 a p8). En estos caso se suelen notar informalmente con las últimas letras del
alfabeto latino: {p,q, r, s, t, . . .}.
En la siguiente tabla se adjunta el nombre usual de cada conectiva y su lectura:
^, Enunciado Falso, Verdadero
Negación  No p p
Conjunción  pyq  p  q
Disyunción  poq  p  q
Condicional  Si p entonces q  p  q    p  q 
Bicondicional  p si y sólo si q  p  q    p  q    q  p 

Semántica de las conectivas

p q p pq pq pq p«q


1 1 0 1 1 1 1
1 0 0 0 1 0 0
0 1 1 0 1 1 0
0 0 1 0 0 1 1

Tablas de verdad

Si interesa conocer cómo se comporta globalmente la fórmula habrá que estudiarla frente a toda
asignación posible. La tabla de verdad es una enumeración completa del valor de la fórmula para cada
asignación distinta. A este tipo de tablas se le denomina tabla de verdad de la fórmula.
A una fórmula verdadera para toda interpretación se le denomina tautología.
A una fórmula falsa para toda interpretación se le denomina contradicción.
A las fórmulas que no son ni tautología ni contradicción se las suele denominar contingentes.

1
Satisfacibilidad

Una interpretación satisface una o varias fórmulas cuando éstas se evalúan como verdaderas en esa
interpretación o línea.
Sobre la tabla de verdad, cualquier "línea" (interpretación) donde una fórmula se evalúa como 1 satisface
esa fórmula.
Una interpretación satisface a un conjunto de fórmulas si todas ellas presentan valor 1 en esa misma línea.
La satisfacibilidad es la posibilidad de ser satisfecho por alguna interpretación.
Basta que al menos exista una línea donde se satisfaga simultáneamente ese conjunto de fórmulas para
afirmar que es satisfacible.
Si un conjunto o una fórmula no es satisfacible se denominará insatisfacible.
Las fórmulas insatisfacibles también se denominan contradicciones.
En la tabla de verdad 1, la primera fórmula por la izquierda es insatisfacible, una contradicción. Las dos
restantes son satisfacibles. De estas dos fórmulas satisfacibles, una resulta ser verdadera en toda
interpretación y la otra no.

p q r (p  q)  ¬ (q  r) (p  q) → (q  r) (p  q) → (q  r)
1 1 1 0 1 1
1 1 0 0 0 1
1 0 1 0 1 1
1 0 0 0 1 1
0 1 1 0 1 1
0 1 0 0 1 1
0 0 1 0 1 1
0 0 0 0 1 1
Tabla 1: Una fórmula insatisfacible y dos satisfacibles

En la tabla de verdad 2, ese conjunto de tres fórmulas es satisfacible. Existe al menos una línea donde
todas las fórmulas tienen el valor 1.
El conjunto de fórmulas de la tabla 1.8 se satisface simultáneamente en 5 líneas.
 Si se eliminase una de las fórmulas, el conjunto resultante se satisfaría en un número igual o
mayor de líneas.
 Si se añadiese una fórmula cualquiera, el conjunto resultante se satisfaría en un número igual o
menor de líneas.

p q r p → (q  r) (p  q)  r r → (r  p)
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 1 1
1 0 0 0 0 1
0 1 1 1 1 1
0 1 0 1 0 1
0 0 1 1 1 1
0 0 0 1 0 1

Tabla 2: El conjunto Г = {p → (q  r), (p  q)  r, r → (r  p)} es satisfacible

2
La tabla 3 corresponde a un conjunto de fórmulas insatisfacible.

p q r p → (q  r) (p  q) ¬ (r  p)
1 1 1 1 1 0
1 1 0 1 1 0
1 0 1 1 0 0
1 0 0 0 0 0
0 1 1 1 0 0
0 1 0 1 0 1
0 0 1 1 0 0
0 0 0 1 0 0

Tabla 3: El conjunto Ω = {p → (q  r), (p  q), ¬ (r  p)} es insatisfacible

El método más directo para decidir la satisfacibilidad de una fórmula o de un conjunto consiste en
recorrer todas las interpretaciones de la tabla de verdad, hasta producir:
 Un resultado afirmativo es satisfacible, basta encontrar la primera interpretación satisfactoria.
 Un resultado negativo no es satisfacible hay que recorrer todas las interpretaciones posibles.
Si en un conjunto de fórmulas aparecen n letras proposicionales, el número de interpretaciones distintas
es 2n.

Validez

Una fórmula válida es aquélla que es verdadera frente a cualquier interpretación.


Las tautologías son fórmulas válidas.
La satisfacibilidad divide en dos al conjunto de fórmulas: en insatisfacibles y satisfacibles.
Este último conjunto también se divide en dos: fórmulas tautológicas y fórmulas contingentes.
Observe que:
 Si niega una fórmula insatisfacible, la fórmula resultante es una tautología.
 Si niega una tautología, la fórmula resultante es insatisfacible.
 Si niega una fórmula contingente, la fórmula resultante es contingente.
 Si niega una fórmula satisfacible, la fórmula resultante puede ser satisfacible o no serlo, tan sólo
se puede afirmar que no será tautología.
Notación: Para expresar que una fórmula φ es válida se utilizará la notación  φ.
Para decidir la validez de una fórmula, el procedimiento semántico extensivo requiere recorrer toda la
tabla de verdad.
Los resultados negativos se pueden obtener más rápidamente: basta encontrar la primera interpretación
que no satisface la fórmula.

3
Consecuencia

Una descripción informal de "ser consecuencia lógica de" es:


Todas las líneas donde las fórmulas denominadas premisas son verdaderas necesariamente la última,
denominada conclusión, también lo es.

En este ejemplo, (q ⋁ r) es consecuencia lógica del conjunto de fórmulas {(p ⋁ q), (p ⋁ r)}, a las que
denominaremos premisas o hipótesis.

p q r ¬p  q p  r qr
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 0 1 1
1 0 0 0 1 0
0 1 1 1 1 1
0 1 0 1 0 1
0 0 1 1 1 1
0 0 0 1 0 0

Tabla 4: Consecuencia {(¬p  q), (p  r)}  (q  r)

Para representar que Ψ es consecuencia lógica de Φ = {φ1, . . . , φn} se suele emplear la notación Φ  Ψ, ó
Φ = {φ1, . . . , φn}  Ψ. Es también usual omitir las llaves del conjunto: φ1, . . . , φn  Ψ.

Cuando no se cumple la relación de consecuencia se denota tachando el símbolo: Φ  Ψ.

En Lógica de Proposiciones donde el número de interpretaciones distintas es finito, la relación de


consecuencia lógica se puede decidir mediante el siguiente procedimiento:
 Se forma la tabla de verdad de las premisas y la conclusión y se comprueba que siempre que las
premisas toman el valor de verdad “1” también la conclusión toma el valor “1”.
 Para mostrar que no es consecuencia lógica basta encontrar un caso en el que las premisas sean
verdaderas y la conclusión falsa.

Absolutamente cualquier fórmula verifica que es consecuencia lógica de un conjunto de fórmulas,


premisas, insatisfacible.

4
Equivalencias

Dos fórmulas, φ y Ψ, son equivalentes si φ  Ψ y Ψ  φ.


Sobre la tabla de verdad, dos fórmulas equivalentes tienen exactamente los mismos valores de verdad
sobre cada línea.

Escribiremos φ ≡ Ψ cuando ambas fórmulas sean equivalentes y φ ≢ Ψ cuando no lo sean.


Cualquier relación binaria que es reflexiva, simétrica y transitiva se le denomina relación de
equivalencia. Tiene las siguientes propiedades:
 Reflexividad: φ ≡ Ψ
 Simetría: si φ ≡ Ψ entonces Ψ ≡ φ
 Transitividad: si φ ≡ Ψ y Ψ ≡ χ entonces φ ≡ χ

Dadas dos fórmulas, φ y Ψ, son equivalentes si y sólo si la fórmula φ « Ψ es una tautología.

Equivalencias Nombre
p  p   Ley del medio excluido
p  p ^ Ley de contradicción
p  ^ p
p  p
p  
Leyes de identidad

p ^^
p p  p
p p  p Leyes de idempotencia
p  p Ley de doble negación
pq  q p
pq  q p Leyes conmutativas

 p  q  r  p  q  r 
Leyes asociativas
 p  q  r  p  q  r
 p  q   p  r   p  q  r 
Leyes distributivas
 p  q   p  r   p  q  r 
p   p  q  p
Leyes de absorción
p   p  q  p
  p  q    p  q
Leyes de De Morgan
  p  q    p  q
p  q  p  q
p  q  q  p
p  q   q  p 
Leyes de transposición
 p  q    p  q    q  p 
 p  q     p  q    p  q  
 p   q  q    p Reducción al absurdo

5
Formas normales

Una forma normal disyuntiva es aquella que está escrita como una disyunción de conjunción de literales.

(p ⋀ q) ⋁ (q ⋀ r)
Una forma normal disyuntiva es una contradicción si y sólo si cada una de sus conjunciones incluye una
letra negada y no negada.
Una forma normal conjuntiva es aquella que está escrita como una conjunción de disyunciones de
literales.

(p ⋁ q) ⋀ (q ⋁ r)
Una forma normal conjuntiva es una tautología si y sólo si cada una de sus disyunciones incluye una letra
negada y no negada.

Forma clausulada

Un literal es una fórmula atómica o la negación de una fórmula atómica.


Son literales cada una de las siguientes seis expresiones: p, q, ¬r, ¬p, ^,¬.

No son literales las expresiones: ¬¬p, r ⋁ q, ¬(p⋀q).


A cada literal l le corresponde un literal complementario lc.

Una fórmula como la siguiente está en forma normal conjuntiva:

(p ⋁ ¬q) ⋀ (¬r ⋁ ¬q ⋁ r ⋁ p) ⋀ (r ⋁ q)

A toda fórmula proposicional se le puede hacer corresponder una fórmula normal conjuntiva equivalente.
1. Eliminar los bicondicionales, si los hubiera: p«q ≡ (pq) ⋀ (qp)

2. Eliminar los condicionales, si los hubiera, mediante el reemplazo: pq ≡ ¬p ⋁ q


3. Introducir todas las negaciones hasta que afecten a fórmulas atómicas:

¬ (p ⋀ q) ≡ (¬p ⋁¬q) ¬ (p ⋁ q) ≡ (¬p ⋀ ¬q)


4. Eliminar las dobles negaciones:
¬¬p ≡ p
5. Reubicar correctamente las conjunciones y disyunciones:

p ⋀ (q ⋁ r) ≡ (p ⋀ q) ⋁ (p ⋀ r)

p ⋁ (q ⋀ r) ≡ (p ⋁ q) ⋀ (p ⋁ r)

6
Lógica de Predicados Monádicos
Sintaxis

El alfabeto de un lenguaje de Primer Orden incluye:


 Símbolos comunes:
o variables: Var = {x, y, z . . .}
o conectivas: {^, , , , , , }

o cuantificadores: {, }
o símbolos de puntuación: paréntesis y comas
o símbolo de igualdad: {»}

 Símbolos propios:
o un conjunto de constantes:  = {a, b, . . .}

o un conjunto de funciones:  = { f, g, . . .}

o un conjunto de relaciones:  = {R, S, . . .}

Se utilizan como constantes las letras iniciales del alfabeto latino {a,b,c,d,...}, las letras finales como
variables {...,u,v,w,x,y,z} y letras intermedias {f,g,h,...} como funciones. Para las relaciones se usarán
letras mayúsculas {R, S,. . .}.
Si queremos expresar los enunciados con una estructura interna necesitamos añadir una colección de
posibles propiedades P, Q, R, S,…, son predicados monádicos, son cosas que se dicen sobre un
determinado elemento sobre los que diremos algo {a,b,c,d,...}.
P sola sin ningún elemento a, b,… no es una fórmula, no podemos evaluarla como verdadera o falsa.
Pa, Qb, ya es una fórmula atómica con una estructura.

Semántica

Una interpretación de una frase debe contener información suficiente para determinar si la frase es
verdadera o falsa.
Formalmente, una interpretación de una expresión lógica contiene los siguientes componentes:
1. seleccionar un conjunto U no vacío, cualquiera.
2. Por cada predicado monádico, como P(x), debe escoger un subconjunto de U.
3. Cada interpretación de este lenguaje debe fijar qué subconjuntos del universo son PI y QI y
qué elementos del universo son aI, bI y cI.
4. Buscar que elementos tienen la propiedad P, Q,…
5. Debemos valorar si la fórmula completa es verdadera o falsa.

7
Ejemplos de Lógica de Predicados Monádicos

U = {1,2,3,4,5}; PI = {2,4,5}; QI = {1,4}; aI = 1; bI = 4

U
PI QI
Pa  Qb FV F  
Pa  Qb FF F 2               1
  3
Pa  Qb FV V 5 4
Pa  Qb FV F

U = {1,2,3,4,5}; PI = {2,4,5}; QI = {2,4,5}; aI = 1; bI = 4

U
PI QI
Pa  Qb FV F             3
Pa  Qb FF F 2 
Pa  Qb FV V   4 
1
Pa  Qb FV F    5

U = {1,2,3,4,5}; PI = {2,4,5}; QI = {1,4}; aI = 4; bI = 4

U
PI QI
Pa  Qb VV V  
Pa  Qb VF V 2               1
  3
Pa  Qb VV V 5 4
Pa  Qb VV V

8
Sintaxis de los cuantificadores

Al cuantificador  “para todo” se le denomina universal.


Al cuantificador  “existe”, existencial.
Además vamos a trabajar con el conjunto de las variables: {x, y, z...}, que nos van a servir para completar
el cuantificador y rellenar los términos de un predicado monádico, diádico, etc.
Las constantes no pueden completar un cuantificador.

Variables libres y ligadas

Si una fórmula es de la forma (∀xφ) o (∃xφ) se dice que φ es el ámbito de ese cuantificador.

Todas las apariciones de una variable x, en el ámbito de un cuantificador para esa variable, (∀xφ) o (∃xφ),
se denominan ligadas.
En una fórmula sin cuantificadores ninguna variable está ligada.
Todo cuantificador liga, a lo sumo, las apariciones de una variable en su ámbito.

Semántica de los cuantificadores

U = {1,2,3,4,5}; PI = {2,3,5};
œxPx representa la frase “todos los elementos tienen la propiedad P”. Px tenemos que evaluarlo para
todas las opciones posibles del universo. Para cualquier interpretación que tenga que hacer verdadera esta
fórmula necesariamente todos los elementos del universo tienen la propiedad P. Es una fórmula falsa para
este universo e interpretación.
œxPx representa la frase “ningún elemento tiene la propiedad P”.
œxPx esta fórmula es verdadera donde œxPx es falsa. Podría representar las frases “no todos tienen la
propiedad P”.

›xPx representa la frase “hay algún elemento del universo que tiene la propiedad P”. Es sólo verdadera
en las estructuras en que P sea distinto del vacío. Si al menos una asignación de la variable x hace
verdadera Px entonces ›xPx es verdadero. Es una fórmula verdadera para este universo e interpretación.
›x¬Px representa la frase “no todos tienen la propiedad P”. Para que esta fórmula sea verdadera basta
que exista un elemento que tenga la propiedad ¬P, que esté “fuera del conjunto P”.
¬›xPx representa la frase “ningún elemento tiene la propiedad P”.

œx(PxQx) representa la frase “todos los x tienen la propiedad P y la propiedad Q”.


U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Falso.
U = {1,2,3,4}; PI = {1,2,3,4}; QI = {1,2,3,4}; Resulta ser Verdadero.

œx(PxQx) representa la frase “todos los x tienen la propiedad P o bien la propiedad Q o ambas”.
U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Falso.
U = {1,2,3,4}; PI = {1,2,4}; QI = {1,2,3}; Resulta ser Verdadero.

9
œx(Px→Qx) representa la frase “todos los P son Q”, en tres de las cuatro regiones marcadas puede haber
elementos sin que esta fórmula sea falsa, basta que haya un elemento en PQ , que haga verdadero el
antecedente y falso el consecuente, para que se evalúe como falso todo el bucle.
Observe que una estructura en que P no tenga elementos también satisface esta fórmula. No se requiere
que P tenga elementos, pero, si los tiene, deben estar en la región PQ. Es decir, la fórmula se hace
verdadera donde PdQ es verdadero. Esta fórmula puede leerse “todos los P son Q”.

U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Verdadero.


U = {1,2,3,4}; PI = {1,2,4}; QI = {1,2,3}; Resulta ser Falso. Hay un elemento en PQ .

U œx(Px→Qx)
U
PI QI
1 V→V V  
2 V→V V   4 1              3
 
3 F→V V 2
4 F→F V

›x(PxQx) esta fórmula es verdadera en las estructuras donde al menos un elemento pertenece a P y ese
mismo elemento pertenece también a Q. Es decir, cuando la intersección de ambos conjuntos no sea
vacía.
U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Verdadero.
U = {1,2,3,4}; PI = {2}; QI = {3}; Resulta ser Falso. No hay ningún elemento en PQ.

›x(Px¬Qx) esta fórmula es verdadera en las estructuras donde al menos un elemento pertenece a P y
ese mismo elemento NO pertenece a Q.
U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Falso.
U = {1,2,3,4}; PI = {2}; QI = {1,3}; Resulta ser Verdadero.

›x¬(PxQx) esta fórmula es verdadera en las estructuras donde al menos un elemento NO pertenece a P
y ese mismo elemento NO pertenece a Q.
U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Verdadero.
U = {1,2,3,4}; PI = {1,2,3,4}; QI = {1,2,3,4}; Resulta ser Falso.

›x(PxQx) esta fórmula es verdadera en las estructuras donde al menos un elemento pertenece a P o ese
mismo elemento pertenece también a Q. Podrían estar situados en cualquiera de las 3 regiones que
comprende la unión PcQ, que no debe ser vacía.
U = {1,2,3,4}; PI = {1,2}; QI = {1,2,3}; Resulta ser Verdadero.
U = {1,2,3,4}; PI = {2}; QI = {3}; Resulta ser Verdadero. Hay al menos un elemento en PcQ.

10
Lógica de Predicados Diádicos
Sintaxis

Rab, es una relación de a a b donde tenemos que decidir si existe tal relación.

U = {1,2,3,4,5,6}; RI = {(3,6),(5,4),(6,2)}; aI = 6; bI = 2; Se cumple.


U = {1,2,3,4,5,6}; RI = {(3,6),(5,4),(6,2)}; aI = 2; bI = 6; No se cumple.
U = {1,2,3,4,5,6}; RI = {(3,6),(5,4),(6,2)}; aI = 1; bI = 6; No se cumple.
U = {1,2,3,4,5,6}; RI = {(3,6),(5,4),(6,2)}; aI = 3; bI = 3; No se cumple.

U
    3    2
1 6
4 5

Ejemplos de Lógica de Predicados Diádicos

U = {1,2,3,4,5,6,7};
Raa; aI = 6 Resulta ser Falso.
Raa; aI = 4 Resulta ser Verdadero. U
Rab  Rab; aI = 4; bI = 2 Resulta ser Falso.               1 5
I I
Rab  Rba; a = 4; b = 2 Resulta ser Falso.
7 3
Rab  Rba; aI = 1; bI = 5 Resulta ser Verdadero.
Rab  Rba; aI = 6; bI = 6 Resulta ser Verdadero. 4
Rab  Rba; aI = 3; bI = 5 Resulta ser Verdadero. 6 2
I I
Rac  Rca; a = 4; c = 2 Resulta ser Verdadero.
Rac  Rca; aI = 1; cI = 5 Resulta ser Falso.
Rac  Rca; aI = 6; cI = 6 Resulta ser Falso.
Rac  Rca; aI = 3; cI = 5 Resulta ser Verdadero.
(Rab  Rbc)  Rac; aI = 7; bI = 4; cI = 2 Resulta ser Verdadero.

11
œxRax, para que esta interpretación sea verdadera, la interpretación tiene que ser tal que a tiene que estar
relacionado con todos los elementos x del universo.
U = {1,2,3,4,5}; RI = {(1,3) (2,1),(2,2),(2,3),(2,4),(2,5),(3,5)}; aI = 2; Se cumple.
U = {1,2,3,4,5}; RI = {(1,3) (2,1),(2,2),(2,3),(2,4),(2,5),(3,5)}; aI = 3; No se cumple.

œxRxa, para que esta interpretación sea verdadera, la interpretación tiene que ser tal que todos los
elementos x del universo tienen que estar relacionados con a.

›xRax, para que esta interpretación sea verdadera, la interpretación tiene que ser tal que a tiene que estar
relacionado con al menos uno de los elementos x del universo.

›xRxa, para que esta interpretación sea verdadera, la interpretación tiene que ser tal que al menos uno de
los elementos x del universo tienen que estar relacionado con a.

›yœxRyx para que esta interpretación sea verdadera, al menos un elemento y del universo debe de estar
relacionado con todos los elementos x del universo.
U = {1,2,3,4}; RI = {(1,5),(2,1),(2,4),(3,1),(3,2),(3,3),(3,4)}; Se cumple.

›xœyRxy, tenemos que determinar si existe al menos un elemento x que esté relacionado con todos los
valores de y.
Informalmente se puede leer como “existe al menos una fila x para toda columna y tal que la casilla
(x,y) pertenece a la relación”.
U = {1,2,3,4}; RI = {(1,1),(1,2),(1,3),(1,4),(2,3),(3,2),(4,2)}; Se cumple.
1 2 3 4
1 ● ● ● ●
2 ●
3 ●
4 ●

›x›yRxy, al menos un elemento x del universo debe de estar relacionado con un elemento y del universo.
U = {1,2,3}; RI = {(2,3)}; Se cumple.

œx›yRxy, para todos los valores de x debe de existir al menos un valor de y.


Informalmente se puede leer como “para toda fila x existe una columna y tal que la casilla (x,y)
pertenece a la relación”.
U = {1,2,3}; RI = {(1,2),(2,2),(3,1)}; Se cumple.

œxœyRxy, todos los elementos x del universo tienen que estar relacionados con todos los elementos y del
universo.
U = {1,2,3}; RI = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}; Se cumple.

12
›yœxRxy "existe una columna y tal que, para toda fila x sobre esa columna", la casilla pertenece a la
relación. Observe que esta fórmula es la que se obtiene de œx›yRxy permutando los cuantificadores: no
son equivalentes, no es lo mismo decir “todo el mundo quiere a alguien” que “alguien es querido por
todo el mundo”.
Ejemplos permutando los cuantificadores

U = {1,2,3};

œy›xRxy SI
SI R = {(3,1),(3,2),(3,3)}
NO
NO ● ● ●

›xœyRxy SI ● ●
NO R = {(1,1),(1,3),(3,2)}
NO
NO ●

NO
›xœyRyx ● ●
NO
NO R = {(1,1),(1,3),(3,1)}
SI


● R = {(1,2),(2,2),(3,2)}

œx(Px  ›yRxy)
U = {1,2,3}; PI = {1,2}; RI = {(1,3),(3,2)}; Resulta ser Falso.

U
U œx(Px  ›yRxy) F PI
         
1 VV V

2 VF F    
3
3 FV F    1

U = {1,2,3}; PI = {1,2,3}; RI = {(1,3),(2,1),(3,2)}; Resulta ser Verdadero.

U
U œx(Px  ›yRxy) V PI
         
1 VV V

2 VV V
       3 
3 VV V
   1

13
œx(Px  ›yRxy)
U = {1,2,3}; PI = {1,2,3}; RI = {(1,3),(2,1),(3,2)}; Resulta ser Verdadero.

U
U œx(Px  ›yRxy) V PI
         
1 VV V

2 VV V
       3 
3 VV V
   1

U = {1,2,3}; PI = {1,2}; RI = {(1,3)}; Resulta ser Falso.

U
U œx(Px  ›yRxy) F PI
         
1 VV V

2 VF F    
3
3 FF V    1

Esta fórmula no obliga a que haya elementos en P, pero en el caso que los haya debe de cumplirse el
consecuente.

U = {1,2,3}; PI = {∅}; RI = {(1,3)}; Resulta ser Verdadero.

U
U œx(Px  ›yRxy) V PI
         1 
1 FV V  
2 FF V          2
3 FF V     3

14
Funciones

œx(PxQ f(x))
U = {1,2,3}; PI = {1,2}; QI = {1,2}; f(1) = 3, f(2) = 2, f(3) = 2, que se podía haber escrito como
f={(1,3),(2,2),(3,2)}. Resulta ser Verdadero.

›xRx f(c) Esta fórmula podría representar la sentencia "todo el mundo quiere a la madre de Juan".

›xR f(x)x Esta fórmula podría ser una versión simbólica de la expresión "mi mamá me mima": para toda
persona, su madre quiere a esa persona.

Identidad

Tratamos con predicados diádicos cuyos elementos se relacionan exclusivamente consigo mismo.

Iab ●

U = {1,2,3}; I = {(1,1),(2,2),(3,3)}; Resulta ser Verdadero. ●


Una forma para hacer la negación es: Iab; (a = b); a ≠ b;

Satisfacibilidad

Una fórmula es satisfacible si existe algún universo, interpretación y asignación donde sea verdadera.
Un conjunto de fórmulas es satisfacible si existe algún universo, interpretación y asignación donde
coincidan todas en ser verdaderas.
También podemos decir que un conjunto de fórmulas es satisfacible si, y sólo si, la fórmula conjunción de
todas ellas es satisfacible.
Otra forma de definir la satisfacibilidad es:
Un conjunto de predicados es satisfacible si existe algún modelo para el que todos los predicados sean
verdaderos.
Un conjunto de predicados es insatisfacible si no existe ningún modelo para el que todos los predicados
sean verdaderos, es decir, si cualquier modelo hace que alguno de los predicados sea falso.

Consecuencia

En todas las líneas en que las fórmulas denominadas premisas coinciden en ser verdaderas la
consecuencia también lo es.
Diremos que C es consecuencia lógica de X,Y y Z. {X, Y, Z}  C;

Otra forma de hacerlo es así, las premisas implican lógicamente a la conclusión: X Y Z  C
A partir de una relación de consecuencia se construye un conjunto que necesariamente es insatisfacible.

15
Validez

Una fórmula es válida si se satisface para todo universo, toda interpretación y asignación.
Una fórmula es válida si y sólo si su negación es insatisfacible. Un conjunto de fórmulas es satisfacible si
y sólo si la fórmula conjunción de todas ellas es satisfacible.

Una fórmula φ es consecuencia lógica de un conjunto de fórmulas Φ si en toda estructura 〈U,I〉 y


asignación en que todas las fórmulas de Φ sean verdaderas también lo es φ. Se expresará entonces como
Φ  φ.

Equivalencias

Dos fórmulas φ y Ψ son equivalentes si φ  Ψ y Ψ  φ.


Sobre la tabla de verdad, dos fórmulas equivalentes tienen exactamente los mismos valores de verdad
sobre cada línea.

Escribiremos φ ≡ Ψ cuando ambas fórmulas sean equivalentes y φ ≢ Ψ cuando no lo sean.

xPx  yPy
xPx  xPx
xPx  xPx

Forma prenexa

La forma normal prenexa es una expresión que tiene todos los cuantificadores desplazados a la parte
delantera de la expresión.
Una expresión está en forma normal prenexa si no hay cuantificadores en el ámbito de las conectivas
lógicas , , , ,  .
Toda expresión puede transformarse en forma normal prenexa siguiendo estos pasos:
 Eliminar todas las apariciones de  y  de la expresión.
 Desplazar todas las negaciones hacia el interior de modo que al final las negaciones sólo
aparezcan como partes de literales.
 Normalizar todas las variables.
 La forma normal prenexa se puede obtener desplazando todos los cuantificadores a la parte
delantera de la expresión.

Encontrar la forma normal prenexa de 


x yR  x, y   yS  x, y     yR  x, y   P  

Primero eliminamos  
x   yR  x, y   yS  x, y      yR  x, y   P  
Desplazamos las negaciones x  yR  x, y   yS  x, y   yR  x, y   P 

Se normalizan los cuantificadores x  y1R  x, y1   y2 S  x, y2   y3R  x, y3   P 

Se desplazan los cuantificadores xy1y2y3  R  x, y1   S  x, y2   R  x, y3   P 

16
La confirmación de insatisfacibilidad: Tableaux

Si desea comprobar que una fórmula es consecuencia de otras, niéguela e incorpórela a esas otras.
Si este nuevo conjunto resulta insatisfacible, efectivamente existía aquella relación de consecuencia.

1. Se utilizan para decidir la satisfacibilidad de un conjunto de fórmulas; indirectamente, para decidir la


relación de consecuencia entre una fórmula y un conjunto: niegue aquélla e incorpórela al conjunto
inicial analizado
2. Se construye un primer árbol, con una sola rama, que consta de tantos nodos como fórmulas haya en
el conjunto inicial
3. Las ramas se pueden bifurcar si es de tipo β (disyuntiva) o ampliar linealmente si es de tipo α
(conjuntiva), los nodos añadidos son subfórmulas adecuadas negadas o no de una fórmula en esa
rama
4. Una rama es satisfacible si lo es el conjunto de todas sus fórmulas.
5. Si entre ellas se encuentran tanto una fórmula como su negación, la rama es insatisfacible.
6. Un árbol es satisfacible si lo es alguna de sus ramas
7. El árbol inicial es tan satisfacible como los sucesivos árboles ampliados; así, si se detecta que alguno
de ellos es insatisfacible, también lo era el conjunto inicial de fórmulas

Notación uniforme

Conjuntiva Disyuntiva
 1 2  1 2
XY X Y  (XY)  X Y
 (XY)  X Y XY X Y
 (XY) X Y XY X Y
 (XY) X Y XY  X Y
 (X Y) X Y X Y  X Y
X Y  X Y  (X Y) X Y
X↛Y  X Y  (X ↛Y) X Y
X↚Y X Y  (X ↚Y) X Y

17
Reglas de expansión γ y δ

Universales Existenciales
  (t)   (t)
∀xX X (t) ∃xX X (a)
∃xX X (t) ∀xX X (a)

Todas ellas producen una expansión del árbol en un sólo nodo. No producen bifurcación del árbol.
Se obtiene una fórmula omitiendo el cuantificador principal.
Es lo que se conoce como instancia por sustitución de esta subfórmula.
El párrafo siguiente expone cuáles pueden ser las cadenas sustituyentes.

Parámetros. Cada lenguaje de primer orden fija sus propias constantes y funciones. Si se pretende que el
lenguaje sirva, por ejemplo, para razonar sobre números naturales, debe incluir una constante (que se
asignará al 0) y una función (la función sucesor).

Regla de expansión γ.
Los nodos “universales”, pueden reutilizarse, expandirse en todas las ramas a las que pertenezcan
cuantas veces se desee. Se puede escoger en su expansión cualquier constante, utilizada anteriormente
o no, estratégicamente, conviene utilizar constantes ya empleadas, para cerrar ramas.
Las fórmulas γ son del tipo x ó ∃x. Su expansión es un único nodo de la forma  (x/p) o  (x/p)
respectivamente, donde todas las apariciones libres de la variable del cuantificador se han sustituido por
el mismo término t. Este término debe ser cerrado: no debe incluir variables, sólo constantes y funciones
de L o constantes auxiliares.

Regla de expansión δ.
Deben utilizarse constantes no empleadas anteriormente, al menos no empleadas en esa rama.
Las fórmulas δ son del tipo ∃x ó x. Su expansión es un único nodo de la forma  (x/p) o  (x/p)
respectivamente, donde todas las apariciones libres en  de la variable del cuantificador se han sustituido
por el mismo parámetro p. Este parámetro, esta constante auxiliar, debe ser nueva en el árbol: no puede
figurar en ninguna fórmula previa (realmente, basta que sea nueva en la rama).
Cada instanciación debe hacerse sobre una constante nueva. De lo contrario, esta constante tendría unas
propiedades (fijadas en otras fórmulas, donde aparece) que pueden modificar (innecesariamente) la
decisión final sobre la satisfabilidad del conjunto.
Estratégicamente, siempre es preferible expandir primero las fórmulas proposicionales α y β, luego las
existenciales (δ) y finalmente las universales (γ) para intentar cerrar.

18
Considere el siguiente conjunto de fórmulas.

X1: p  q
X2: p → r
X3: q → r
X4: r

Se pueden plantear, entre otras, las siguientes tres preguntas:


1. ¿Es consecuencia: X1, X2, X3  X4?
2. ¿Es insatisfacible { X1, X2, X3, ¬ X4}?
3. ¿Es tautología X1  X2  X3 → X4?

Observe que, en general, la insatisfacibilidad de {X1,X2,X3,¬X4} implica que es efectivamente


consecuencia X1,X2,X3  X4. Se puede afirmar que también son consecuencias X1,X2,¬X4  ¬X3 ó
¬X4,X2,X3  ¬ X1. Se Comprueba, sobre su tabla de verdad:

X1 X2 X3 X4 ¬X4
pqr pq p→r q→r r
000 0 1 1 0 1
001 0 1 1 1 0
010 1 1 0 0 1
011 1 1 1 1 0
100 1 0 1 0 1
101 1 1 1 1 0
110 1 0 0 0 1
111 1 1 1 1 0

Figura 1: ejemplo insatisfacible {(p  q), (p → r),( q → r), ¬ r}

Comprobación de consecuencia: si se desea comprobar una relación de consecuencia, como X1,X2,X3 


X4, hay que negar la supuesta consecuencia, X4, antes de introducirla en el conjunto de nodos iniciales.
De hecho, lo que el tableau comprueba es que un determinado conjunto, {X1,X2,X3,¬X4} en este caso, es
insatisfacible.

Comprobación de insatisfacibilidad: suponga que en un examen la pregunta que se plantea es “¿es


insatisfacible el conjunto de fórmulas Ω?”, entonces hay que situar todas las fórmulas de Ω como nodos
iniciales, sin manipular (negar) ninguna.

19
Contenido
Tema 1 Lógica de proposiciones y de predicados de primer orden. ............................................................. 1 
Lógica de proposiciones ................................................................................................................................ 1 
Sintaxis ...................................................................................................................................................... 1 
Semántica de las conectivas ...................................................................................................................... 1 
Tablas de verdad........................................................................................................................................ 1 
Satisfacibilidad .......................................................................................................................................... 2 
Validez....................................................................................................................................................... 3 
Consecuencia ............................................................................................................................................. 4 
Equivalencias............................................................................................................................................. 5 
Formas normales ....................................................................................................................................... 6 
Forma clausulada ....................................................................................................................................... 6 
Lógica de Predicados Monádicos .................................................................................................................. 7 
Sintaxis ...................................................................................................................................................... 7 
Semántica .................................................................................................................................................. 7 
Ejemplos de Lógica de Predicados Monádicos ......................................................................................... 8 
Sintaxis de los cuantificadores .................................................................................................................. 9 
Variables libres y ligadas .......................................................................................................................... 9 
Semántica de los cuantificadores .............................................................................................................. 9 
Lógica de Predicados Diádicos ................................................................................................................... 11 
Sintaxis .................................................................................................................................................... 11 
Ejemplos de Lógica de Predicados Diádicos .......................................................................................... 11 
Ejemplos permutando los cuantificadores ............................................................................................... 13 
Funciones................................................................................................................................................. 15 
Identidad .................................................................................................................................................. 15 
Satisfacibilidad ........................................................................................................................................ 15 
Consecuencia ........................................................................................................................................... 15 
Validez..................................................................................................................................................... 16 
Equivalencias........................................................................................................................................... 16 
Forma prenexa ......................................................................................................................................... 16 
La confirmación de insatisfacibilidad: Tableaux .................................................................................... 17 

20
Deducción natural
La derivación natural hace uso de varias reglas de inferencia.

Introduce conectiva Elimina conectiva


Nombre Regla Nombre Regla
¬I Teorema de la deducción ¬E ¬¬A ⊢ A
⇒I Teorema de la deducción ⇒ E A,A ⇒ B ⊢ B
∧I A,B ⊢ A ∧ B ∧E A∧ B⊢A
A∧ B⊢B
∨I A ⊢ B∨ A ∨ E Teorema de la deducción
⇔I A ⇒ B, ⇔ E A ⇔ B⊢A⇒ B
B⇒A⊢A⇒B A ⇔ B⊢B⇒ A

Existen dos reglas para cada conectiva lógica, una para introducir la conectiva y otra para eliminarla.

Probar que P ∧ Q ⊢ ( P ∨ Q ) ∧ ( Q ∨ R )

1 ( P ∧ Q)
2 P ∧ E ,1
3 Q ∧ E ,1
4 P∨ R ∨I , 2
Q∨R
5 ∨ I ,3
6 ( P ∨ Q ) ∧ (Q ∨ R) ∧ I , 4,5

Implementación del teorema de la deducción.

Tres reglas de la tabla hacen uso del teorema de deducción. ¬I , ⇒ I , ∨ E .


En todos los casos hay que crear una derivación subordinada y en el caso de ∨ E dos derivaciones
subordinadas.
Las subderivaciones pueden ser anidadas.
La derivación que crea la subderivación es la derivación de llamada.
Todas las subderivaciones presentan un supuesto adicional que se desecha una vez que la subderivación está
terminada.
El siguiente ejemplo prueba el silogismo hipotético.

1 P⇒Q
2 Q⇒R

3 P
4 P⇒Q R,1
5 Q ⇒ E , 3, 4
6 Q⇒R R,2
7 ⇒ E , 5, 6
R
8 ⇒ I,3− 7
P⇒R

1
Derivación del Modus Tollens en deducción natural.

1 P⇒Q
2 ¬Q

3 P
4 P⇒Q R,1
5 Q ⇒ E , 3, 4
6 ¬Q R,2
7
Q ∧ ¬Q ∧ I ,5, 6
8 ¬I , 3 − 7
¬P

Derivación por el silogismo disyuntivo.

1 P∨Q
2 ¬Q

3 P
4 P R,3

5 Q

6 ¬P
7 Q ∧ ¬Q ∧ I , 2,5
8 ¬¬P ¬I , 6 − 7
9 P ¬E ,8
10
P ∨ E ,1, 3 − 4,5 − 9

Resolución.

La prueba del teorema de resolución es un método para hacer derivaciones que tiene las siguientes
propiedades:
Las únicas expresiones que se permiten en la prueba del teorema de la resolución son disyunción de
literales. Una disyunción de literales se llama cláusula. Todas las expresiones deben ser cláusulas.
La resolución se ajusta al principio de refutación, que demuestra que la negación de la conclusión es
inconsistente con las premisas.
Hay esencialmente una sola regla de inferencia, la resolución.

Ejemplo del Modus Ponens:

Se puede expresar como: P, P ⇒ Q ⊨ Q ,


La negación de la conclusión se añade a las premisas: P, P ⇒ Q, ¬Q ,
Se debe demostrar que es imposible encontrar asignación alguna que pueda satisfacer todas esas
proposiciones, es decir que las proposiciones son inconsistentes. Hay que convertir todas las expresiones en
disyunciones: P, ¬P ∨ Q, ¬Q .
Dos cláusulas se pueden resolver si y solo si contienen dos literales complementarios.
Dando origen a una nueva cláusula llamada resolverte.
2
Si los literales complementarios son P y ¬P se dice que la resolución radica en P.
Las cláusulas que dan origen al resolvente se llaman cláusulas padre.
El resolverte sobre P es la disyunción de todos los literales de las cláusulas padre, excepto P y ¬P se
omiten en el resolverte.

Hallar el resolverte de: P ∨ ¬Q ∨ R y ¬S ∨ Q .

Las dos cláusulas se pueden resolver sobre Q porque Q es negativa en la primera cláusula y positiva en
la segunda.

El resolverte es la disyunción de P ∨ R con ¬S , por lo tanto,

P ∨ R ∨ ¬S

Se pueden tratar las cláusulas como conjuntos: C = A ∪ B − { P, ¬P}

Para probar el Modus Ponens se usan las siguientes derivaciones:

1. P Premisa

2. ¬P ∨ Q Premisa

3. ¬Q Negación de la conclusión

4. Q Resolvente de 1, 2

5. F Resolvente de 3, 4

Para el silogismo hipotético se tiene:

1. ¬P ∨ Q Premisa

2. ¬Q ∨ R Premisa

3. P Derivada de la negación de la conclusión

4. ¬R Derivada de la negación de la conclusión

5. Q Resolvente de 1, 3

6. ¬Q Resolvente de 2, 4

7. F Resolvente de 5, 6

3
Se suele utilizar la resolución unitaria que consiste en que todas las resoluciones implican al menos una
cláusula unitaria.
Otra estrategia es la del conjunto de apoyo:

Se dividen todas las cláusulas en dos conjuntos, el conjunto de apoyo y el auxiliar.


El conjunto auxiliar está formado de manera que las expresiones que contiene no son contradictorias.
Las premisas se usan como conjunto auxiliar inicial.
Y la negación de la conclusión como el conjunto de apoyo inicial.
Cada resolución toma al menos una cláusula del conjunto de apoyo.
Entonces el resolvente se añade al conjunto de apoyo.

La estrategia del conjunto de apoyo es completa, pero la resolución unitaria no.


Si no hay cláusula unitaria se hace imposible la resolución unitaria.
La resolución de las cláusulas unitarias se puede modificar de forma que no se permita que haya cláusulas
unitarias para resolver a partir de otras cláusulas.
Esto da lugar a una estrategia de preferencia unitaria.
A veces se aplica una regla adicional en la prueba del teorema de la resolución, es la factorización.
La factorización permite eliminar ciertas resoluciones no eficientes a la vez que se mantiene la condición de
completo.

4
Tablas semánticas, Tableaux
Introducción
Si desea comprobar que una fórmula es consecuencia de otras, niéguela e incorpórela a esas otras. Si resulta
insatisfacible este nuevo conjunto, efectivamente existía aquella relación de consecuencia.

La satisfacibilidad de las cláusulas se define como:

• Una cláusula C = {l1, . . . , ln} es satisfacible si y sólo si la fórmula (l1 . . . ln) es satisfacible.

• La cláusula vacía {} es insatisfacible.

• Un conjunto de cláusulas {C1, . . . ,Ck} es satisfacible si y sólo si existe una misma interpretación que
satisface a cada cláusula del conjunto.

Recuerde que una cláusula es una disyunción implícita. Es, por lo tanto satisfacible si existe un literal que se
hace verdadero bajo cierta asignación. En la cláusula vacía no existe ningún literal que pueda hacerla
verdadera, luego es insatisfacible. Denotaremos a la cláusula vacía como {} o como .

Para satisfacer un conjunto de cláusulas basta encontrar una interpretación que satisface al menos un literal
en cada cláusula.

Tableaux
Las tablas semánticas también se denominan tablas analíticas y más comúnmente tableaux.

Es una estrategia deductiva por refutación, las tablas semánticas proporcionan un medio sintáctico de
investigar la satisfacibilidad de un conjunto.

Si desea comprobar que una fórmula es consecuencia de otras, niéguela e incorpórela a esas otras. Si resulta
insatisfacible este nuevo conjunto, efectivamente existía aquella relación de consecuencia.

Constatación sintáctica de la insatisfacibilidad. De nuevo, si el conjunto de partida Φ ∪ {¬Ψ} era


insatisfacible, en algún momento del cálculo se evidencia claramente.

Intuitivamente, las fórmulas del conjunto inicial se estructuran como árbol. En particular como un árbol
muy lineal, con una sola rama. Existen dos tipos de reglas de inferencia y ambas añaden nodos al árbol: una,
linealmente, y otra produciendo una bifurcación binaria. La satisfacibilidad de un árbol se puede comprobar
en cualquier momento, considerando la satisfacibilidad de cada rama. Existen indicadores sintácticos que lo
explicitan.

La clave de estas operaciones consiste en la preservación de la satisfacibilidad. Cada aplicación de una regla
amplía el árbol sin modificar la satisfacibilidad. Si el árbol original, las fórmulas de partida, eran
satisfacibles así resultará el árbol ampliado en todo momento. Y si eran insatisfacibles, se llegará a constatar
sintácticamente en algún momento.

Notación uniforme
Considere la fórmula ( p ∧ ¬q ) . Una interpretación la satisface si y sólo si satisface a sus componentes
conjuntivos. Es decir,

( p ∧ ¬q ) es satisfacible si y sólo si {p,¬q} es satisfacible.

5
La fórmula propuesta era evidentemente conjuntiva. Otra fórmula como ¬(¬p ∨ q ) se puede fácilmente
reescribir de forma equivalente como una fórmula conjuntiva. En particular como (¬¬p ∧ ¬q ) . Y se
satisfaría, de nuevo, si y sólo si se satisfacen simultáneamente sus componentes.

Dualmente, una fórmula disyuntiva como ( p ∨ ¬q ) se satisface si y sólo si se satisface alguna de sus dos
fórmulas inmediatas. Otras fórmulas, no explícitamente disyuntivas como ( p → ¬q ) también se puede
reescribir equivalentemente como (¬p ∨ ¬q ) .

Vamos a fijar el desarrollo que se persigue con esta introducción. Observe la tabla en figura. 1.21.

Cada fórmula α de la izquierda es equivalente a la conjunción de sus componentes α1 y α2. Y cada fórmula
β, a la disyunción de sus componentes β1, β2.

Tanto en un caso como en otro, las componentes son subfórmulas de la fórmula principal. Y a partir sólo de
ellas y de sus negaciones se construye una conjunción o una disyunción equivalente a la fórmula dada.

Conjuntiva Disyuntiva
α α1 α2 β β1 β2
X ∧Y X Y ¬( X ∧ Y ) ¬X ¬ Y
¬( X ∨ Y ) ¬X ¬Y X ∨Y X Y
¬( X → Y ) X ¬Y X →Y ¬X Y
¬( X ← Y ) X ←Y
¬X Y X ¬Y
¬( X ↑ Y ) X Y X ↑Y ¬X ¬Y
X ↓Y ¬X ¬Y ¬( X ↓ Y ) X Y
X→ / Y X ¬Y ¬( X →
/ Y) ¬X Y
X← / Y ¬X Y ¬( X ←
/ Y) X ¬Y

En las tres primeras líneas se utilizan las conectivas básicas que se fijaron en el alfabeto. Las cinco líneas
restantes utilizan otras conectivas binarias que se podían haber incorporado igualmente al alfabeto. Si se
asume esta notación, incluso utilizando todas estas conectivas, cada fórmulas es simplemente de tipo α o de
tipo β. Y, recursivamente, cada una de sus subfórmulas es de uno de estos dos tipos.

Ni el bicondicional ni su negación, la disyunción exclusiva, se pueden escribir como una conjunción o


disyunción de sus subfórmulas negadas o no. Por tanto, no se considerarán conectivas primarias del lenguaje
sino abreviaturas.

Tableaux: definición

Ejemplo 1.68. Observe la figura 1.22 considerando que inicialmente sólo consta del nodo 1.

Esto es así porque el conjunto de fórmulas iniciales analizado consta de una única fórmula: ¬( p → (q ∧ r )) .
Luego se construye un árbol A que consta de ese único nodo.

Puede comprobarse que la fórmula analizada es de tipo α, en concreto ¬( X → Y ) . Expandamos el árbol A


con dos nodos más: α1 (nodo 2) y α2 (nodo 3). El resultado es otro árbol A′ : una rama compuesta por tres
fórmulas que son satisfacibles por las mismas interpretaciones.

La fórmula del nodo 3 puede aún expandirse. Es una fórmula de tipo β (disyuntiva), y por tanto para su
satisfación basta que una de las dos componentes se satisfaga. Representemos ese hecho bifurcando el árbol
en ese punto terminal. El resultado es el árbol A′′ final que se observa en la figura (fig. 1.22).

Con las consideraciones anteriores, la fórmula inicial se satisface si y sólo si se satisfacen todas las de la
rama 1-4 o las de la rama 1-5. Cuando se recorren, tanto una como otra, no hay señales evidentes de que
tales fórmulas no puedan ser satisfechas a la vez. De hecho, para que la rama 1-4 se satisfaga basta
considerar q falsa y p verdadero. Y en la rama 1-5, r falso y p verdadero.

6
Ejemplo 1.69 La figura 1.23 inicialmente constaba sólo de los nodos 1 y 2. Se pretende analizar la
satisfacibilidad del conjunto formado por esas dos fórmulas.
Nos situaremos en el nodo 2, por ser el extremo actual de ese árbol. Y aplicaremos allí la expansión de una
de esas dos fórmulas. En concreto, escogemos expandir la fórmula 2, podía haber sido la 1. La fórmula 2 es
de tipo α y produce los nodos 3 y 4.
Nos situamos en el nodo 4 y expandimos la fórmula 1, que es de tipo β. Como la satisfacción de esta
fórmula puede venir por un lado o por otro, se produce la bifurcación de los nodos 5 y 6. En este punto, las
fórmulas iniciales son simultáneamente satisfacibles si y sólo si lo son todas las fórmulas de la rama 1-5 o
todas las fórmulas de la rama 1-6.
Recorriendo las fórmulas de la rama 1-5 se observa que una de las fórmulas es p mientras otra es ¬p. Luego
la satisfacibilidad simultánea de todas las fórmulas de esa rama queda descartada, se marca su extremo.
Comprobamos la otra rama, el conjunto inicial es satisfacible si y sólo si lo es esta rama.
Como aún se pueden expandir más fórmulas, nos situamos en 6 y lo hacemos. En concreto se expande la
propia fórmula 6, que produce los nodos 7 y 8 por ser de tipo conjuntivo. De nuevo, recorriendo esta rama
se encuentra uno con r y ¬r y la rama queda cerrada.
El conjunto formado por las dos fórmulas iniciales no es satisfacible.

7
Definición 1.70. Tableau de un conjunto de fórmulas. Sea {φ1, . . . ,φn} un conjunto de fórmulas. Entonces
el árbol formado por la única rama φ1 . . .φn es un tableau A para este conjunto.

Si A es un tableau para ese conjunto y A′ resulta de aplicar a A alguna de las reglas de expansión de
tableaux, entonces A′ es un tableau para ese conjunto.

Falta precisar cuáles son las reglas de expansión, dónde y cómo se puede expandir un árbol y si existe un
final determinado para este proceso.

Las reglas de expansión son las que se muestran en la tabla 2.5. Dado un árbol, se escoge una rama
cualquiera del mismo y una fórmula de esa rama que pueda expandirse, que no sea un literal. La expansión
se produce en el terminal de esa rama: una bifurcación si la fórmula escogida era disyuntiva o la secuencia
de dos nodos si era conjuntiva.

Definición 1.71. Tableau cerrado Una rama se dice cerrada si ocurren en ella tanto una fórmula X como una
fórmula ¬X, o si ocurre la fórmula z . Está atómicamente cerrado si la fórmula X es atómica o si ocurre z .

Un árbol se ha cerrado si se han cerrado todas sus ramas. Cuando todos los cierres son atómicos se dice que
el árbol se ha cerrado de forma atómica.

Tabla 2.5 Reglas de expansión de un Tableau.

Conectivas monarias ¬¬X ¬y ¬z


X z y
Conectivas binarias α β
α1 β1 β 2
Cuantificador universal γ
(para cualquier término t cerrado de Lpar )
γ (t )
Cuantificador existencial δ
(para cualquier parámetro p nuevo)
δ ( p)

Observe que las reglas de expansión son no deterministas. Se puede escoger la rama y la fórmula siguientes
que se van a expandir. Esta opción obliga a plantearse si existen estrategias de elección, heurísticas, más
eficientes que otras. En efecto, por regla general, trate de expandir todas las fórmulas α primero.

Previa a esta preocupación por la complejidad, conviene fijar si el proceso para en algún momento.

No hay nada en las definiciones que impida expandir la misma fórmula α una y otra vez sobre una rama,
puesto que no se elimina. Afortunadamente, para la lógica proposicional abordada, basta utilizar una única
vez cada fórmula para garantizar el cierre del tableau (si es que debe cerrarse). No ocurría así en la
Resolución. El sistema descrito es consistente y completo en los mismo términos con que se enunció para
Resolución: un conjunto es insatisfacible si y sólo si existe un tableau cerrado del mismo.

8
Tablas semánticas

Fórmulas proposicionales
Recordemos las propiedades básicas de los tableaux para fórmulas proposicionales:

1. se utilizan para decidir la satisfacibilidad de un conjunto de fórmulas; indirectamente, para decidir la


relación de consecuencia entre una fórmula y un conjunto: niegue aquélla e incorpórela al conjunto
inicial analizado

2. se construye un primer árbol, con una sola rama, que consta de tantos nodos como fórmulas haya en
el conjunto inicial

3. las ramas se pueden bifurcar o ampliar linealmente; los nodos añadidos son subfórmulas adecuadas
negadas o no de una fórmula en esa rama

4. una rama es satisfacible si lo es el conjunto de todas sus fórmulas; obviamente, si entre ellas se
encuentran tanto una fórmula como su negación, la rama es insatisfacible

5. un árbol es satisfacible si lo es alguna de sus ramas

6. el árbol inicial es tan satisfacible como los sucesivos árboles ampliados; así, si se detecta que alguno
de ellos es insatisfacible, también lo era el conjunto inicial de fórmulas

Ejemplo 2.71 Observe el árbol de la figura 2.7. Muestra que, de la hipótesis p → (q ∧ r ) , es consecuencia
lógica ¬r → ¬p . Más apropiadamente, que esto segundo se deduce de aquello primero.

Pero en este sistema consistente todo lo que se deduce es consecuencia.

[Nodos 1-2] El árbol inicial lo constituyen el nodo 1 (única hipótesis) y el nodo 2 (negación de la supuesta
conclusión). Situados en el nodo más bajo de esta rama (el 2), tratamos de ampliarla descomponiendo
adecuadamente alguna de las fórmulas de esa rama. Estratégicamente, se recomienda descomponer primero
las fórmulas α (conjuntivas) y después las β (disyuntivas).

[Nodos 3-5] Optamos por utilizar la fórmula 2 (α, conjuntiva): da lugar a una expansión lineal de esa rama
(nodos 3 y 4). Y seguimos expandiendo: estamos en el nodo 4 y podemos expandir esa rama utilizando
cualquiera de las fórmulas de la misma. Entre las diversas opciones, se opta por utilizar la propia fórmula 4:
la ’doble negación’ se puede expandir como ’sin negación’ (nodo 5).

[Nodos 6-7] En el nodo 5 se decide expandir la fórmula 1 (β, disyuntiva), que bifurca la rama (nodos 6 y 7).
La rama del nodo 6 se puede cerrar inmediatamente: entre las fórmulas de esa rama (1-6) hay tanto una
fórmula (la 6) como su negación (en 5).

[Nodos 8-9] En la rama del nodo 7 no se observa aún este tipo de contradicción. Pero todavía se pueden
expandir fórmulas de esa rama; en concreto, la propia fórmula 7 (de tipo α). Se obtienen los nodos 8 y 9. Y
el nodo 9 es la negación de la fórmula del nodo 3, en esa misma rama desde la raíz.

El árbol se ha cerrado. Luego el conjunto de partida ( ϕ en nodo 1, ¬ψ en nodo 2) era insatisfacible.

Así que se ha demostrado que ϕ ⊢ ψ , es decir, que ϕ ⊨ ψ .

9
10
Ejemplo 2.72 El árbol de la figura 2.8 es igual al del ejemplo previo figura 2.7. Compare las fórmulas de
uno y otro: todas las fórmulas del segundo ejemplo se obtienen, por sustitución uniforme, de las del primero.
Observe cómo se produce el cierre del segundo ejemplo: donde antes se cerraban en fórmulas atómicas,
ahora se pueden cerrar en sus fórmulas sustituyentes.

11
El árbol de la figura 2.9 es ya una primera incursión en lógica de predicados. Sin embargo, no se van a
necesitar aquí reglas adicionales: también es una instancia por sustitución del primer árbol considerado.
Compruebe qué fórmula ha sustituido a qué proposición.

Notación uniforme
En lógica de predicados, no todas las relaciones de consecuencia entre fórmulas tienen raíz puramente
conectiva proposicional. Por eso se requieren nuevas reglas de inferencia. En concreto, en este sistema, se
añadirán dos nuevas reglas:

1. una, para manipular fórmulas universalmente cuantificadas (tipo γ)

2. otra, para manipular fórmulas existencialmente cuantificadas (tipo δ)

Así, toda fórmula en este sistema es intrínsecamente conjuntiva (α), disyuntiva (β), universal (γ), existencial
(δ) o una doble negación (ó z ó y ).

La tabla 2.4 resume las fórmulas que se consideran intrínsecamente universales (γ) y existenciales (δ), junto
a su expansión. Todas ellas producen una expansión del árbol en un sólo nodo. No producen, por tanto,
bifurcación del árbol.

12
Tabla 2.4 Notificación uniforme, fórmulas cuantificadotas.

Universales Existenciales
γ γ (t ) δ δ (a)
∀xX X (t ) ∃xX X (a)
¬∃xX X (t ) ¬∀xX X (a)

Ejemplo 2.73 Considere la fórmula:

¬∀x(∀z¬( Pz → Qx) → ∃wRwa )

es de tipo existencial (δ). Su subfórmula inmediata:

(∀z¬( Pz → Qx) → ∃wRwa )

es de tipo (β). Sus subfórmulas inmediatas:

∀z¬( Pz → Qx), ∃wRwa

son, respectivamente, (γ) y (δ). Y la subfórmula:

¬( Pz → Qx)

es de tipo (α).

Reglas de expansión γ y δ
En ambos tipos de fórmulas la expansión aporta un sólo nodo. En concreto, la subfórmula inmediata:

La fórmula que resta cuando se omite el cuantificador principal. Más precisamente, una instancia por
sustitución de esta subfórmula. El párrafo siguiente expone cuáles pueden ser las cadenas sustituyentes.

Más adelante se determinará qué se debe sustituir y con qué restricciones.

Parámetros. Cada lenguaje de primer orden fija sus propias constantes y funciones. Si se pretende que el
lenguaje sirva, por ejemplo, para razonar sobre números naturales, debe incluir una constante (que se
asignará al 0) y una función (la función sucesor).

Las demostraciones sobre fórmulas de un lenguaje suelen requerir, como herramienta, el uso de constantes
auxiliares. A estas constantes adicionales se les denomina ’parámetros’. Así, las demostraciones sobre
fórmulas de un cierto lenguaje L se describen usando fórmulas del lenguaje Lpar, extensión del L por adición
de estas constantes.

Las cadenas sustituyentes en la expansión serán, según los casos, parámetros o términos cerrados, términos
de Lpar que no incluyen variables.

Regla de expansión δ. Las fórmulas δ son del tipo ∃xφ ó ¬∀xφ . Su expansión es un único nodo de la
forma φ ( x / p ) o ¬φ ( x / p ) respectivamente, donde todas las apariciones libres en φ de la variable del
cuantificador se han sustituido por el mismo parámetro p. Este parámetro, esta constante auxiliar, debe ser
nueva en el árbol: no puede figurar en ninguna fórmula previa (realmente, basta que sea nueva en la rama).

13
De una fórmula como ∃xPx no tiene por qué ser consecuencia Pa. Sin embargo, si ∃xPx es satisfacible,
también lo será Pa. Y estamos trabajando en un sistema que trata de decidir la satisfacibilidad de un
conjunto de fórmulas.

Cada instanciación debe hacerse sobre una constante nueva. De lo contrario, esta constante tendría unas
propiedades (fijadas en otras fórmulas, donde aparece) que pueden modificar (innecesariamente) la decisión
final sobre la satisfabilidad del conjunto.

Este cuidado se mantiene en toda manipulación de fórmulas de primer orden. Si no se considera, se puede
llegar a afirmar (erróneamente) que ’siempre que hay alguien que tiene la propiedad P y hay alguien que
tiene la propiedad Q, entonces alguien tiene ambas propiedades’. Un razonamiento erróneo en deducción
natural sería: “puesto que alguien tiene la propiedad P, llamémosle a, luego Pa. Puesto que alguien tienen la
propiedad Q, llamémosle a, luego Qa. Entonces, Pa ∧ Qa . Luego alguien tiene (a la vez) la propiedad P y la
Q”.

Regla de expansión γ. Las fórmulas γ son del tipo ∀xφ ó ¬∃xφ . Su expansión es un único nodo de la
forma φ ( x / p ) o ¬φ ( x / p ) respectivamente, donde todas las apariciones libres de la variable del
cuantificador se han sustituido por el mismo término t. Este término debe ser cerrado: no debe incluir
variables, sólo constantes y funciones de L o constantes auxiliares.

La particularización de una fórmula universal no requiere de ningún cuidado especial: lo que es verdadero
para todo elemento del universo lo será para el que represente al término t.

Todas las reglas de expansión se recogen en la tabla 2.5.

Tabla 2.5 Reglas de expansión de un Tableau.

Conectivas monarias ¬¬X ¬y ¬z


X z y
Conectivas binarias α β
α1 β1 β 2
Cuantificador universal γ
(para cualquier término t cerrado de Lpar )
γ (t )
Cuantificador existencial δ
(para cualquier parámetro p nuevo)
δ ( p)

2.4.4 Ejemplos

Ejemplo 2.74. El árbol de la figura 2.10 muestra que:

∀xPx ∨ ∃yQy ⊢ ∃y∀x( Px ∨ Qy )

[Nodos 1-2]Respectivamente, hipótesis y negación de la supuesta conclusión.

[Nodos 3-4] Expansión (β) de la fórmula 1. Estratégicamente, siempre es preferible expandir primero las
fórmulas proposicionales (α y β), luego las existenciales (δ) y finalmente las universales (γ) para intentar
cerrar.

[Nodo 5] Expansión de la fórmula 2 (universal, γ), porque no existía ninguna fórmula existencial en la rama
1-3. Se puede instanciar y por cualquier parámetro.

[Nodo 6] Expansión de la fórmula 5 (existencial, δ). El parámetro de la instanciación debe ser nuevo: b.
14
[Nodos 7-8]Expansión de la fórmula 6 (α)

[Nodo 9]Aprovechando que ya existe ¬Pb en el nodo 8, expandiremos la fórmula 3 (universal).

Como se puede escoger cualquier término, elegiremos instanciarla para b, cerrando esta rama.

[Nodos 10-14] Se procede de manera análoga (indicada en el árbol). Tan sólo merece reseñar la elección de
parámetros. El de la línea 10 debía ser un parámetro nuevo en la rama. Se ha escogido incluso nuevo en el
árbol (c).

[Nodos 11-14]El parámetro de la línea 11 proviene de una sustitución universal: podía ser cualquiera.

Como ya existía Qc previamente, se escoge asimismo Qc. El parámetro de la línea 12 debía ser nuevo: d. La
elección correcta de la instancia universal en la línea 11 acaba favoreciendo el cierre de esta última rama en
14.

15
Ejemplo 2.75 La figura 2.11 confirma que

∀x∃y ( Rxy → Qy ), ∀x∀yRxy ⊢ ∃zQz

16
Tema 3 Conjuntos, Relaciones y Funciones.
Conjuntos
Los conjuntos se representan con letras mayúsculas, A, B,C ,…
Los elementos se representas con minúsculas, a, b, c, x, y, z.

Relación de pertenencia:
 El elemento a pertenece al conjunto X, a  X
 El elemento a no pertenece al conjunto Z, a  Z

Formas de definir un conjunto:


 Extensión: enumeramos todos y cada uno de los elementos.
 Comprensión: definimos alguna característica común a todos los elementos.

Conjunto definidos por extensión:

S = {lunes, martes, miércoles, jueves, viernes, sábado, domingo}


V = {a, e, i, o, u}

Conjunto definidos por compresión:

S = {días de la semana}
V = {vocales del español}

Por comprensión podemos definir de la siguiente manera los conjuntos:

V   x  A x es vocal
V es el conjunto de los elementos x que pertenecen al conjunto de las letras del alfabeto español A,
tales que x es una vocal.

Relación de inclusión:
Dados dos conjuntos A y B, se dice que A está incluido en B y se escribe A ⊂ B o A ⊆ B cuando todos los
elementos de A pertenecen a B.
Si A está contenido en B se dice que A es un subconjunto de B o que A es una parte de B.
Si A no es subconjunto de B se denota como A ⊈ B.

Propiedades de la inclusión de conjuntos.

 Reflexiva: todo conjunto A está contenido en sí mismo. A  A .

 Transitiva: Si un conjunto A está contenido en otro B, y B está contenido en otro conjunto C,


entonces A está contenido en C.
Si A  B y B  C , entonces A  C .

Si A y B son dos conjuntos tales que A  B y B  A entonces son iguales A  B .

Se dice que un conjunto A es un subconjunto propio de un conjunto B, denotado A ⊊ B, si A ⊂B y A ≠ B.

Si un conjunto A es subconjunto de un conjunto B entonces se dice que B es un superconjunto de A.


Se denota como B ⊃ A, ó B ⊇ A. Si B no es superconjunto de A entonces lo denotamos como B ⊉ A.

1
Conjunto universal, es el conjunto que contiene a todos los conjuntos que se analizan en un determinado
contexto y se representa por U.

Conjunto vacío es un conjunto que no tiene elementos, se representa por  .

Cualquiera que sea el conjunto A se cumple   A .

Operaciones con conjuntos.


La intersección de dos conjuntos A y B es el conjunto que tiene como elementos los comunes a ambos
conjuntos, se representa por A  B .

Dos conjuntos son disjuntos si no tienen elementos comunes, A  B   .

La unión de los conjuntos A y B es el conjunto que tiene como elementos los que pertenecen a alguno de
los conjuntos, se representa por A  B .

El conjunto complementario de A está formado por los elementos del conjunto universal que no
pertenecen a A, se representa por ∼A.

La diferencia de dos conjuntos A y B es el conjunto formado por los elementos de A que no pertenecen a B,
se representa por A \ B.

La diferencia de dos conjuntos A y B es igual a la intersección de A con el complementario de B, se


representa por A \ B = A ⋂∼B.

Sea un conjunto S. Se denomina partición de S a una colección de conjuntos S1,S2,…,Sn tales que todos son
distintos de ∅, la unión da como resultado S, y cada par de conjuntos Si y Sj, con i≠j, son disjuntos.

Diagramas de Venn
Los conjuntos suelen representarse por medio de unos dibujos denominados diagramas de Venn. El
conjunto universal lo representamos por un rectángulo y los conjuntos por círculos dentro del conjunto
universal.

2
Resumen de las propiedades de los conjuntos

Propiedad Nombre
 A  B  C  A   B  C 
Asociativa
 A  B  C  A   B  C 
A B  B  A Conmutativa
A B  B  A
A   B  C    A  B   A  C 
Distributiva
A   B  C    A  B   A  C 
A A  A Idempotencia
A A  A
A   A  B  A
Absorción
A   A  B  A
  A  B   A  B
De De Morgan
  A  B   A  B
   A  A Doble negación
A U  A
Identidad
A  A
A  A  U Complemento
A  A   Exclusión
A U  U
Leyes de dominación
A  
U  Complementación
  U Complementación

3
Producto cartesiano

Una relación es un conjunto de parejas ordenadas.


Si A y B son dos conjuntos cualesquiera, R es una relación de A en B sí y sólo sí R es un subconjunto de
AxB.
El producto cartesiano de dos conjuntos es una operación que resulta en otro conjunto cuyos elementos
son todos los pares ordenados que pueden formarse tomando el primer elemento del par del primer
conjunto, y el segundo elemento del segundo conjunto.

Por ejemplo, dados los conjuntos A = {1, 2, 3, 4} y B = {a, b}, su producto cartesiano es:

A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b), (4, a), (4, b)}

Conjuntos potencia
Sea A un cierto conjunto, el conjunto potencia de A, escrito como P( A) , es el conjunto cuyos elementos
son todos los subconjuntos de A.

Si el conjunto A tiene n elementos, el conjunto de las partes de A tiene 2n elementos.

Construir el conjunto potencia de A  a, b, c .

P ( A)  , a , b , c , a, b , b, c , a, c , a, b, c

4
Relaciones
Una relación de A en B es cualquier conjunto de pares  x, y  , x  A e y  B . Si  x, y   R , diremos que x es
R-relacionado con y. Para expresar que R es una relación de A en B, escribiremos R : A  B .
Forma de expresar las relaciones, notación lista: enumera todos los elementos de la relación, en forma de
tabla, en forma de matriz, gráficamente formada por nodos y arcos.
Si  x, y  es un par, uno puede definir un predicado PR para cada relación R que es verdadera si  x, y   R y
falsa en caso contrario, se expresa como Rxy . Rxy   x, y   R

Relación reflexiva

Una relación binaria R sobre X es reflexiva si, para cada x  X , el par  x, x  está en la relación, por
consiguiente R es reflexiva x  Rxx 
El ejemplo más sencillo de una relación reflexiva es la relación identidad I X , cuyos únicos elementos son
 x, x  , x X .
En algunos casos R no contiene ningún elemento del tipo  x, x  , en este caso R se denomina no reflexiva
(irreflexible).
La relación hermano es no reflexiva.
Si todos los nodos tienen un bucle entonces la relación es reflexiva.
La reflexividad es visible cuando una relación está dada en forma matricial.
Sea M R   mij  la matriz de la relación R, entonces la diagonal principal de la matriz es el conjunto de
todos los mii . Si todos los mii  1 entonces la relación es reflexiva.
Si todos los mii  0 entonces la relación es NO reflexiva.

1 0 1  0 0 1  1 0 1 
0 1 0 0 0 0 0 0 0
     
1 0 1  1 1 0   0 1 1 
Es reflexiva Es irreflexiva Ninguna

Relación irreflexiva
Una relación binaria: R, entre los elementos de un conjunto: A, es una relación irreflexiva, también
llamada: antirreflexiva o antirrefleja, si ningún elemento del conjunto está relacionado consigo mismo:

œx ∈ A: (x,x) ∉ R

Para todo x que pertenezca a A, (x, x) no pertenece R.

Que también puede expresarse: ¬›x ∈ A: (x,x) ∉ R

No existe ningún elemento x en el conjunto A que cumpla que: (x, x) pertenezca a R.

5
Relaciones simétricas

Una relación R sobre un conjunto X es simétrica si para todos x e y perteneciente a X, Rxy implica Ryx, por
consiguiente:
 R es simétrica xy  Rxy  Ryx 

La relación hermano es simétrica.

Una relación R sobre X es antisimétrica si para todo y  x , Rxy excluye a Ryx, o sea si se alcanzan Rxy e
Ryx, entonces x = y, por consiguiente:
 R es antisimétrica xy  Rxy  Ryx  x  y 

La relación “madre de” es antisimétrica.

En el dígrafo de una relación simétrica todos los arcos son bidireccionales.


Si la relación es antisimétrica ningún arco tiene un compañero que vaya en la dirección opuesta.

Sea M R   mij  la matriz de la relación R, entonces la matriz es simétrica si y solo si mij  m ji .


Una matriz es antisimétrica si y solo si mij  1 obliga a que m ji  0 . En las relaciones antisimétricas tanto
mij como m ji pueden ser 0.

1 0 1  0 0 1  1 0 1 
0 1 0 1 0 0  0 0 0
     
1 0 0   0 1 0  1 1 1 
Simétrica Antisimétrica Ninguna

Transitividad
Una relación R sobre un conjunto X es transitiva si para todo x, y, z en X siempre que Rxy e Ryz, entonces
xRz, por consiguiente:
R es transitiva xyz  Rxy  Ryz  Rxz 
Una relación es transitiva si y sólo si todos los pares de objetos que pueden ser alcanzados a través de un
intermediario pueden también ser alcanzados directamente.

La transitividad se divide en dos grupos:


 Relaciones simétricas.
 Relaciones antisimétricas.

La relación de igualdad es la más importante de las relaciones simétricas transitivas.

6
Cierres
 El cierre reflexivo R  r  de una relación R es la relación reflexiva más pequeña que contiene a R
como subconjunto.
 El cierre simétrico R  s  de una relación R es la relación simétrica más pequeña que contiene a R
como subconjunto.
 R  de una relación R es la relación transitiva más pequeña que contiene a R como subconjunto.
 El cierre transitivo R* de una relación R es la relación transitiva reflexiva más pequeña que contiene
a R como subconjunto.
 En resumen para obtener un cierre se añaden tan pocos elementos como sea posible para hacer a la
relación en cuestión.

Consiste en hacer que una relación que no cumple una propiedad sí la cumpla.

Por ejemplo, el cierre reflexivo de {(a,b),(c,d),(a,a)}, definida en {a,b,c,d}, sería:

{(a,b),(c,d),(a,a),(b,b),(c,c),(d,d)}, pues la segunda relación sí es reflexiva.

Para la misma relación, el cierre simétrico es {(a,b),(c,d),(a,a),(b,a),(d,c)}.

Cierre Reflexivo Cierre Simétrico


a b a b

c d c d

1 1 0 0 1 1 0 0
0 1 0 0  1 0 0 0 
 
0 0 1 1 0 0 0 1
   
0 0 0 1 0 0 1 0

Sean

A = {1, 2, 3, 4}
R = {(1,2), (2,3), (3,4)}

Cierre transitivo: señale todos los pares que faltan para que esta relación sea transitiva

(1,3),(2,4),(1,4)

1 2

3 4

7
Relaciones de equivalencia
Una relación es una relación de equivalencia si y solo si es:
 Reflexiva.
 Simétrica.
 Transitiva.

La relación de equivalencia más importante es la de igualdad. Es Reflexiva, Simétrica y Transitiva.

Órdenes parciales
Las relaciones transitivas antisimétricas conducen a los órdenes parciales.
Existen dos tipos de órdenes parciales.
Una relación R : S  S se denomina un orden parcial débil si es reflexiva, antisimétrica y transitiva.
R se denomina orden parcial estricto si es irreflexiva, es antisimétrica y es transitiva.
Todos los órdenes parciales son no cíclicos.
Un conjunto A junto con un orden parcial R se denomina conjunto parcialmente ordenado o un cpo. El cpo
 A, R  es el conjunto A junto con el orden parcial R.
Un orden parcial R es un orden total o un orden lineal si y solo si para todos los x e y, Rxy  Ryx es
siempre verdadera. En este caso se llama al cpo  A, R  un conjunto totalmente ordenado o una cadena.
Un orden total implica que sea reflexiva, antisimétrica y transitiva.
Los órdenes parciales describen algún orden aún cuando no todos los elementos sean comparables.
Los órdenes parciales estrictos no pueden tener bucles.

8
Funciones
Las funciones son relaciones.
Toda función de A en B es una relación de A en B.
Una función entre dos conjuntos A y B es una transformación que convierte cada elemento del conjunto A
en un único elemento del conjunto B.
El conjunto A se llama conjunto inicial o dominio de la aplicación.
El conjunto B se llama conjunto final o rango de la aplicación.

La notación más común para indicar que el par  x, y  pertenece a alguna función f es y  f  x  .
Por lo tanto  x, y   f , y  f  x  e f : x  y es lo mismo.

Ejemplo 6.1 ¿Cuáles de las siguiente relaciones de A  a, b, c con B  1, 2,3, 4 son funciones?
1. f1   a,3 ,  b,1 ,  c, 2 
2. f 2   a,3 ,  b,3 ,  c, 2 
3. f3   a,3 ,  a, 4  ,  b,1 ,  c, 2 
4. f 4   a,3 ,  b,1

f1 es función ya que cada x está relacionada con una y.


f2 es función, aunque la imagen 3 está asociada con a y b no viola los requisitos de una función.
f3 NO es función porque a se relaciona con 3 y 4.
f4 NO es función porque no hay elemento relacionado con c.

Tipos de Funciones
Una función f : A  B es inyectiva si a cada valor del conjunto inicial "A" le corresponde un valor distinto
en el conjunto final B de f. Es decir, a cada elemento del conjunto inicial A le corresponde un solo valor del
conjunto final B tal que, en el conjunto A no puede haber dos o más elementos que tengan la misma imagen.

Una función f : A  B es, sobreyectiva cuando cada elemento de "B" es la imagen de como mínimo un
elemento de "A".

Una función f : A  B es, biyectiva si es al mismo tiempo inyectiva y sobreyectiva; es decir, si todos los
elementos del conjunto de salida tienen una imagen distinta en el conjunto de llegada, y a cada elemento del
conjunto de llegada le corresponde un elemento del conjunto de salida.

A B A B A B

1 a 1 a 1 a
2 b 2 b 2 b
3 c 3 c 3 c
d 4 4 d

Inyectiva Sobreyectiva Biyectiva

9
Una relación f es una función parcial de X a Y si para todo x  X existe como máximo una y  Y .
Algunos elementos del espacio del dominio X pueden no tener su correspondiente y  f  x  .
En este caso el dominio puede ser un subconjunto propio del espacio del dominio.
Toda función es una función parcial.
NO toda función parcial es una función.

Ejemplo:

En el dominio de los números enteros, f  x   x es una función parcial, porque cuando x es impar no
2
podemos asociar ninguna imagen, por lo tanto no es función sino una función parcial.

1 1/2 1
2 1 2 1
3 3/2 3
4 2 4 2

En el gráfico se ve que 1 y 3 no tienen imagen en el dominio de los enteros, ya que ½ y 3/2 no pertenecen a
los enteros.
La función identidad transforma cada valor en sí mismo, esto es f  x   x .
La función constante tiene una sola imagen, por ejemplo c y todos los argumentos se refieren a la misma
imagen, si f denota a la función constante se tiene: f  x   y . La imagen de cada x es y.

10
Composición
Si tenemos dos funciones: f(x) y g(x), de modo que el dominio de la 2ª esté incluido en el recorrido de la 1ª,
se puede definir una nueva función que asocie a cada elemento del dominio de f(x) el valor de g[f(x)].

f g f g
a 2 z
a 1 1 u
f g
b 2 2 v b 4 x
c 3 3 x f g
d 4 4 z c 1 v
A B B C d
f
3
g
u

g  f es la composición de las funciones f y g.

Se lee f compuesta con g.

La composición de funciones es una operación asociativa, pero no es conmutativa, se cumple que:

h  g   f  hg  f 

Ejemplo: Encontrar g  f si f  x   x  4 y g  x   x 2

g  f  x   g  x  4   x  4
2

Ejemplo: Encontrar g  f y f  g si f  x   x  3 y g  x   2 x

g  f  x    g  x  3  2  x  3
g  f  x   2  x  3

f  g  x   f  2x   2x  3
f  g  x  2x  3

11
Cardinalidad

El cardinal de un conjunto X es su número de elementos y se representa por |X|.

A B  A  B  A B

Si dos conjuntos A y B son disjuntos, el cardinal de la unión es igual a la suma de los cardinales.

Si A  B   , entonces A  B  A  B  A  B

Si A y B son dos conjuntos, siempre se cumple que el cardinal de su unión  A  B  es igual al cardinal de A
más el cardinal de B menos el cardinal de la intersección  A  B  .

A B  A  B  A B

Podemos razonar la fórmula de otra manera:

A B  A B  B  A  A B

Tenemos que A   A  B    A  B  , siendo  A  B  y  A  B  disjuntos, por lo tanto:

 A  A B  A B
 B  B  A  A B

12
Homomorfismos, automorfismos e isomorfismos

Sean dos funciones f:X→X y g:Y→Y . Si existe una función h:X→Y tal que g(h(x))=h(f(x)) entonces se dice
que f y g son homomorfas, y que h es un homomorfismo.

Sean dos funciones f:X→X y g:Y→Y que son homomorfas, y sea h su homomorfismo. Si h es biyectiva
entonces se dice que f y g son isomorfas, y que h es un isomorfismo.

Sean dos funciones f:X→X y g:Y→Y que son homomorfosmas, y sea h su homomorfismo. Si X=Y entonces
se dice que f y g son endomorfas, y que h es un endomorfismo.

Sean dos funciones f:X→X y g:Y→Y que son isomorfosmas, y sea h su isomorfismo. Si X=Y entonces se
dice que f y g son automorfas, y que h es un automorfismo.

G y G´ se denominan isomorfos, y son matemáticamente iguales, solo varia la apariencia, o sea, que se
mantienen las adyacencias, estructura, caminos y ciclos.

A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:

f(a) = 1;
f(b) = 6;
f(c) = 8;
f(d) = 3;
f(g) = 5;
f(h) = 2;
f(i) = 4;
f(j) = 7;

13
Sean los siguientes grafos G1 y G2

Un isomorfismo para los grafos anteriores G1 y G2 está definido por:


f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g(Xi) = Yi, i = 1, ... , 5
Los grafos G1 y G2 son isomorfos si y solo si para alguna ordenación de vértices y lados sus matrices de
incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:

14
Tema 4 Combinatoria
Principios Básicos de la combinatoria

La combinatoria es una disciplina que se ocupa de estudiar técnicas de conteo y enumeración de


conjuntos, en especial cuando la cantidad de elementos que poseen es muy grande. Aplicada a la teoría de
probabilidades permite en muchos casos determinar la cantidad de elementos de un espacio de muestra
finito y la cantidad de elementos de algún evento de interés.

Principio de la adición:

Si una tarea se puede realizar de dos formas posibles, dando la primera m resultados posibles y la
segunda n resultados posibles, entonces la tarea completa se puede arrojar m+n formas posibles.

Principio de la multiplicación:
Si una experiencia está compuesta de varias etapas y cada una de ellas admite diferentes posibilidades,
el número total de situaciones posibles se obtendrá multiplicando.

Variaciones
Sea A un conjunto con n elementos y r ≤ n, llamaremos variación de orden r a toda lista ordenada
formada por r elementos distintos de entre los n elementos de A.

Dos listas serán distintas si difieren en algún elemento o en el orden.

El número total de listas se indica: V (n, r ) .

n!
V (n, r ) 
(n  r )!

Variaciones con repetición


Si en la definición anterior podemos repetir elementos obtendremos las variaciones con repetición que
se representan por:

VR ( n , r )  n r

Permutaciones
Sea A un conjunto finito formado por n elementos, una permutación de A es una lista ordenada
formada por los n elementos de A. Dos permutaciones de A difieren en la colocación de al menos uno de los
elementos. Las permutaciones son manera de distribuir objetos.

P (n)  n !

1
Permutaciones con repetición
Sea A un conjunto finito con k elementos (k > 0), una permutación con repetición de m elementos de
A, es una lista en la que el elemento a1 se repite mk veces. Dos listas son distintas si difieren en el orden de
sus elementos.

r!
PRnr 
n1 ! n2 !...nk !

Combinaciones
Sea A un conjunto finito formado por n elementos (n > 0) y r un número natural r ≤ n, una
combinación de orden r de A es una lista de elementos de A distintos dos a dos. Diremos que dos
combinaciones son diferentes si algún elemento de una lista no se encuentra en la otra. Las combinaciones
son maneras de seleccionar objetos.

n n!
C (n, r )    
 r  r ! (n  r )!

Combinaciones con repetición


Sea A un conjunto finito formado por n elementos (n > 0) y r un número natural r ≤ n, una
combinación con repetición de orden r de A es una lista de elementos de A en donde los elementos pueden
repetirse. Diremos que dos combinaciones con repetición son diferentes si algún elemento de una de las dos
listas no se encuentra en la otra.

 n  r  1
CR(n, r )   
 r 

Números combinatorios

n V n!
Cnr     nr 
 r  Pr r ! (n  r )!

Binomio de newton

( x  y ) 2  x 2  2 xy  y 2
 2  2  2
( x  y ) 2    x 2    xy    y 2  x 2  2 xy  y 2
0 1  2

( x  y ) 3  x 3  3 x 2 y  3 xy 2  y 3
 3  3  3  3
( x  y )3    x3    x 2 y    xy 2    y 3  x3  3 x 2 y  3 xy 2  y 3
0 1  2  3

2
( x  y ) 4  x 4  4 x 3 y  6 x 2 y 2  4 xy 3  y 4
 4  4  4  4  4
( x  y ) 4    x 4    x3 y    x 2 y 2    xy 3    y 4  x 4  4 x3 y  6 x 2 y 2  4 xy 3  y 4
0 1  2  3  4

RESUMEN
Tenemos n elementos y formamos grupos de r.

Importa el Puede En cada


Agrupación FÓRMULA
Orden Repetirse Agrupación
n!
Variaciones SI NO r<n V (n, r ) 
(n  r ) !
Variaciones VR ( n , r )  n r
SI SI r<n
Repetición
Permutaciones SI NO r=n P (n)  n !
Permutaciones n!
SI SI r=n PRnr 
Repetición r1 ! r2 ! r3 !...
n n!
Combinaciones NO NO r≤n C (n, r )    
 r  r ! (n  r )!
Combinaciones  n  r  1
NO SI r≤n CR(n, r )   
Repetición  r 

3
Tema 5 Árboles y Grafos.
Definiciones básicas de teoría de grafos.
Un grafo consta de un conjunto de nodos, un conjunto de aristas y una correspondencia f del conjunto de
aristas al conjunto de nodos.
Si una arista se corresponde con un par ordenado, entonces se dice que es una arista dirigida, en caso
contrario es una arista no dirigida.
Los pares de nodos que estén conectados por una arista dentro de un grafo se denominan nodos
adyacentes.
Un grafo en el que toda arista es dirigida se denomina digrafo o grafo dirigido.
Un grafo en el que todas las aristas son no dirigidas se denomina grafo no dirigido.
Si en un grafo hay aristas dirigidas y aristas no dirigidas se denomina mixta.
Sea G  ( N , A) y sea e  A una arista dirigida asociada al par ordenado de nodos (u,v). Se dice que la
arista e sale del nodo u o comienza en el nodo u y llega al nodo v o termina en el nodo v.
También se dice que los nodos u y v son los nodos inicial y Terminal de la arista e.
Una arista e  A que conecte los nodos u y v tanto si es dirigida como si no se dice que es incidente en los
nodos u y v.
Una arista que conecte un nodo consigo misma se denomina bucle o lazo.
En algunos grafos pueden existir ciertos pares de nodos que estén unidos por más de una arista, se
denominan aristas paralelas.
Todo grafo que contenga aristas paralelas se denomina multigrafo.
Si no hay más de una arista entre pares de nodos se denomina grafo sencillo.
Existen grafos en los que los números de las aristas muestran los pesos de éstas, se denominan grafos
ponderados.
En un grafo un nodo que no sea adyacente a ningún otro nodo se denominará nodo aislado.
Un grafo que contenga solamente nodos aislados se denomina grafo nulo.
En un grafo dirigido, para todo nodo v el número de aristas que tienen a v como nodo inicial se denomina
grado de salida del nodo v.
El número de aristas que tienen a v como nodo terminal es lo que se denomina grado de entrada.
La suma del índice de entrada y el índice de salida es lo que se denomina grado total del nodo v.
La suma de los grados de todos los nodos de un grafo debe de ser un número par que será igual al doble
del número de aristas que haya en el grafo.

Sea N ( H ) el conjunto de nodos de un grafo H y sea N (G ) el conjunto de nodos un grafo G tales que
N ( H )  N (G ) . Si además toda arista de H es también una arista de G, entonces se dice que el grafo H es
un subgrafo del grafo G y esto se expresa en la forma H  G .
Un grafo G  ( N , A) es completo si todos sus nodos son adyacentes a todos los nodos del grafo, se
denotan de la forma K n
Un grafo sencillo G  ( N , A) se denomina grafo bipartito si N se puede descomponer en dos subconjuntos
V1 y V2 tales que no haya dos nodos de V1 que sean adyacentes ni tampoco dos nodos de V2 .
Sea G  ( N , A) un digrafo sencillo, toda arista de A se puede expresar por medio de un par ordenado de
elementos de N, esto es A  N  N .
Cualquier subconjunto de N  N define una relación sobre N.

1
Caminos, accesibilidad y conexiones.

Sea G  ( N , A) un digrafo sencillo, se dice que una sucesión de aristas es un camino de G si y solo si el
nodo terminal de cada arista del camino es el nodo inicial de la próxima arista del camino, si lo hubiere.

Un camino recorre los nodos que aparecen en la sucesión, comenzando en el nodo inicial de la primera
arista y finalizando en el nodo terminal de la última arista de la sucesión.

El número de aristas que aparecen en la sucesión de un camino se denomina longitud del camino.

Un camino de un digrafo en el cual todas las aristas sean distintas se denomina camino sencillo.
Un camino en el que todos los nodos sean diferentes se denomina camino elemental.

Un camino que comienza y acaba en el mismo nodo se denomina ciclo.


Ciclo sencillo, si ninguna arista del ciclo aparece más de una vez en el camino.
Ciclo elemental, si no pasa por ningún nodo más de una vez.

Un digrafo sencillo que no tenga ningún ciclo se denomina aclíclico.

Sea G  ( N , A) un digrafo sencillo, entonces se define la relación de camino, C de G en la forma


C   u , v  existe un camino del nodo u al nodo v.
Si un nodo v resulta alcanzable desde el nodo u, entonces un camino de longitud mínima que vaya de u a v
se denomina camino de longitud mínima.
La longitud de un camino de longitud mínima del nodo u al nodo v se denomina distancia y se denota
como d(u,v). Se supone que d(u,u)=0 para todo nodo u.
La longitud de un camino de un grafo es el número de aristas que aparecen en la sucesión del camino.
La alcanzabilidad es una relación binaria sobre el conjunto de los nodos de un digrafo sencillo.
La alcanzabilidad es reflexiva y transitiva, pero no necesariamente simétrica o antisimétrica.

La distancia d(u,v) desde un nodo u hasta un nodo v satisface las propiedades siguientes:

d (u , v)  0
d (u , u )  0
d (u , v)  d (v, w)  d (u , w)

La última igualdad se llama desigualdad triangular. Si no puede alcanzarse v desde u se escribe d (u, u )   .
Si se puede alcanzar v desde u y u desde v entonces d (u, v) no es necesariamente igual a d (v, u ) .

En un digrafo sencillo la longitud de cualquier camino elemental es menor o igual que n-1, en donde n es
el número de nodos que haya en el grafo, similarmente la longitud de cualquier ciclo elemental no
sobrepasará n.
El número de nodos diferentes de cualquier camino elemental de longitud k es k+1.

En un grafo sencillo no dirigido, una sucesión v1 , v2 ,..., vd forma un camino si para i  1, 2,3..., d existe una
arista no dirigida vi 1 , vi  . Se dice que la arista vi 1 , vi  se encuentra en el camino.
La longitud del camino está dada por el número de aristas que haya en el camino y es d-1.
Si v1  vd entonces el camino forma un ciclo.
Un ciclo sencillo en un grafo no dirigido es un ciclo sencillo que tiene que tener al menos tres aristas
distintas y en donde solo se repite el nodo inicial y el nodo final de la sucesión.

Se dice que un grafo no dirigido es conexo si para cualquier pareja de nodos del grafo se puede llegar
hasta el otro nodo partiendo de cualquiera de ellos.
2
Un digrafo es conexo o débilmente conexo si es conexo como grafo codirigido, despreciando los sentidos
de las aristas, es decir si se transforman las aristas dirigidas en aristas no dirigidas.

Un digrafo sencillo se dice unilateralmente conexo si para toda pareja de nodos del grafo al menos uno de
los nodos de esa pareja se puede alcanzar desde el otro.

Si para toda pareja de nodos del grafo los dos nodos de la pareja se pueden alcanzar uno desde el otro,
entonces se dice que el grafo es fuertemente conexo.

Si un grafo es fuertemente conexo entonces es unilateralmente conexo.


Si un grafo es unilateralmente conexo entonces es débilmente conexo.
Un grafo no dirigido es débilmente conexo si y sólo si es unilateralmente conexo, y si y sólo si es
fuertemente conexo.

Fuertemente conexo Débilmente conexo Unilateralmente conexo


No Unilateralmente conexo No Fuertemente conexo

Sea G  ( N , A) un digrafo sencillo, y sea X  N , se dice que el subgrafo cuyos nodos están dados por el
conjunto X y cuyas aristas son todas aquellas aristas de G que tengan sus nodos iniciales y finales en X es
el subgrafo inducido por X.

Un subgrafo G1 se denomina maximal con respecto a alguna propiedad si no hay ningún otro subgrafo que
también posea esa propiedad y que incluya a G1.
Para un digrafo sencillo los subgrafos maximales fuertemente conexos se denominan componentes fuertes.
Un subgrafo maximal unilateralmente conexo o un subgrafo maximal débilmente conexo se denominan
componente unilateral o componente débil.
En un digrafo sencillo G  ( N , A) , todo nodo del digrafo se encuentra exactamente en un componente
fuerte.

3
Tipos especiales de caminos
Un camino hamiltoniano en un grafo es una sucesión de aristas adyacentes que visita todos los vértices
del grafo una sola vez.
Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo tan solo una única vez, siendo
condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden
vértice inicial o de salida y vértice final o meta).
Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo
solamente una vez".
Se debe tener en cuenta que no importa la repetición de vértices mientras no se repitan aristas.

Un camino euleriano es un camino que pasa por cada arista una y solo una vez.
Un ciclo euleriano es un camino cerrado que recorre cada arista exactamente una vez.
El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en el famoso
problema de los puentes de Königsberg.

Se denomina grafo euleriano a un grafo que contiene un ciclo euleriano.


Un grafo conexo es un grafo euleriano si y sólo si todos los vértices tienen grado total par.

4
Árboles de expansión.

Árboles libres.
Un árbol libre es un grafo sencillo no dirigido que es a la vez conexo y acíclico.
Todo árbol libre que contenga n nodos debe de tener n-1 aristas.

Árboles de expansión.

Un árbol de expansión de un grafo conexo no dirigido G  ( N , A) es un árbol libre con el conjunto de


nodos N que es un subgrafo de G, es decir un árbol de expansión conexo, acíclico y tiene a todo N como
nodos y a parte de A como conjunto de aristas.
Todo árbol de expansión para un grafo de n nodos contiene siempre n-1 aristas.
Para la generación de un árbol de expansión se selecciona una sucesión de n-1 aristas, una a una tal que en
cada paso el subgrafo actual sea acíclico.
Tanto la búsqueda en amplitud como la búsqueda en profundidad utilizan este enfoque.

Árboles de expansión mínima.


Un árbol de expansión de un grafo ponderado conexo y no dirigido en el cual la suma de los costes de sus
aristas sea mínima se denomina árbol de expansión mínima.

Grafos

Fundamentos y terminología básica


Un grafo, G, es un par, compuesto por dos conjuntos V y A. Al conjunto V se le llama conjunto de vértices o
nodos del grafo. A es un conjunto de pares de vértices, estos pares se conocen habitualmente con el nombre de
arcos o ejes del grafo. Se suele utilizar la notacion G = (V, A) para identificar un grafo.

Los grafos representan un conjunto de objetos donde no hay restricción a la relación entre ellos. Son
estructuras más generales y menos restrictivas. Podemos clasificar los grafos en dos grupos: dirigidos y no
dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los
pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un
par ordenado de vértices , de forma que y representan dos arcos diferentes.

Los grafos permiten representar conjuntos de objetos arbitrariamente relacionados. Se puede asociar el
conjunto de vértices con el conjunto de objetos y el conjunto de arcos con las relaciones que se establecen
entre ellos.

Los grafos son modelos matemáticos de numerosas situaciones reales: un mapa de carreteras, la red de
ferrocarriles, el plano de un circuito eléctrico, el esquema de la red telefónica de una compañia, etc.

El número de distintos pares de vértices (v(i), v(j)), con v(i) <> v(j), en un grafo con n vértices es n*(n-1)/2.
Este es el número máximo de arcos en un grafo no dirigido de n vértices. Un grafo no dirigido que tenga
exactamente n*(n-1)/2 arcos se dice que es un grafo completo. En el caso de un grafo dirigido de n vértices el
número máximo de arcos es n*(n-1).

Algunas definiciones básicas en grafos:

 Orden de un grafo: es el número de nodos (vértices) del grafo.


 Grado de un nodo: es el número de ejes (arcos) que inciden sobre el nodo
 Grafo simétrico: es un grafo dirigido tal que si existe la relación entonces existe , con u, v
pertenecientes a V.
 Grafo no simétrico: es un grafo que no cumple la propiedad anterior.
5
 Grafo reflexivo: es el grafo que cumple que para todo nodo u de V existe la relación (u, u) de A.
 Grafo transitivo: es aquél que cumple que si existen las relaciones (u, v) y (v, z) de A entonces existe
(u, z) de A.
 Grafo completo: es el grafo que contiene todos los posibles pares de relaciones, es decir, para cualquier
par de nodos u, v de V, (u <> v), existe (u, v) de A.
 Camino: un camino en el grafo G es una sucesión de vértices y arcos: v(0), a(1), v(1), a(2), v(2), ... ,
a(k), v(k); tal que los extremos del arco a(i) son los vértices v(i-1) y v(i).
 Longitud de un camino: es el número de arcos que componen el camino.
 Camino cerrado (circuito): camino en el que coinciden los vértices extremos (v(0) = v(k)).
 Camino simple: camino donde sus vértices son distintos dos a dos, salvo a lo sumo los extremos.
 Camino elemental: camino donde sus arcos son distintos dos a dos.
 Camino euleriano: camino simple que contiene todos los arcos del grafo.
 Grafo euleriano: es un grafo que tiene un camino euleriano cerrado.
 Grafo conexo: es un grafo no dirigido tal que para cualquier par de nodos existe al menos un camino
que los une.
 Grafo fuertemente conexo: es un grafo dirigido tal que para cualquier par de nodos existe un camino
que los une.
 Punto de articulación: es un nodo que si desaparece provoca que se cree un grafo no conexo.
 Componente conexa: subgrafo conexo maximal de un grafo no dirigido (parte más grande de un grafo
que sea conexa).

6
El lenguaje de la lógica proposicional LOGICA PROPOSICIONAL

Tablas de verdad
Negación Conjunción Disyunción Condicional Bicondicional
p q 𝑝˄𝑞 p q 𝑝˅𝑞 p q 𝑝→𝑞 p q 𝑝↔𝑞
𝑝 ¬𝑝 0 0 0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 0 1 1 0 1 1 0 1 0
1 0 1 0 0 1 0 1 1 0 0 1 0 0
1 1 1 1 1 1 1 1 1 1 1 1

Equivalencia
Generación de equivalencias por reemplazo:

Doble negación Conjunción Disyunción Conmutativa Asociativa


¬¬ 𝐴 ≡ 𝐴 𝐴˄𝐴 ≡ 𝐴 𝐴˅𝐴 ≡ 𝐴 𝐴˄𝐵 ≡ 𝐵˄𝐴 (𝐴˄𝐵)˄𝐶 ≡ 𝐴˄(𝐵˄𝐶)
𝐴˄¬𝐴 ≡⊥ 𝐴˅¬𝐴 ≡ ⟙ 𝐴˅𝐵 ≡ 𝐵˅𝐴 (𝐴˅𝐵)˅𝐶 ≡ 𝐴˅(𝐵˅𝐶)
𝐴˄⟙ ≡ 𝐴 𝐴˅⟙ ≡ ⟙ 𝐴↔𝐵≡𝐵↔𝐴 (𝐴 ↔ 𝐵) ↔ 𝐶 ≡ 𝐴 ↔ (𝐵 ↔ 𝐶)
𝐴˄ ⊥ ≡⊥ 𝐴˅ ⊥ ≡ 𝑝

Absorción De Morgan Condicional Bicondicional


Distributiva
𝐴 → 𝐵 ≡ ¬𝐴˅𝐵 𝐴 ↔ 𝐵 ≡ (𝐴 → 𝐵)˄(𝐵 → 𝐴)
𝐴˄(𝐵˅𝐶) ≡ (𝐴˄𝐵)˅(𝐴˄𝐶) 𝐴˄(𝐴˅𝐵) ≡ 𝐴 ¬(𝐴˄𝐵) ≡ ¬𝐴˅¬𝐵
𝐴 → 𝐵 ≡ ¬𝐵 → ¬𝐴 𝐴 ↔ 𝐵 ≡ (𝐴˄𝐵)˅(¬𝐴˄¬𝐵)
𝐴˅(𝐵˄𝐶) ≡ (𝐴˅𝐵)˄(𝐴˅𝐶) 𝐴˅(𝐴˄𝐵) ≡ 𝐴 ¬(𝐴˅𝐵) ≡ ¬𝐴˄¬𝐵
Forma normal conjuntiva: Conjunción de disyunciones (A ˅ B) ˄ (A ˅ B)
Forma normal disyuntiva: Disyunción de conjunciones (A ˄ B) ˅ (A ˄ B)

Tautología y Contradicciones
Una Tautología es una formula verdadera en todas las interpretaciones y lo anotamos como “⊨A”.
Una Contradicción es una formula falsa en todas las interpretaciones.
Propiedades
Todas las tautologías son equivalentes entre sí y con⟙ . Todas las contradicciones son equivalentes entre sí y con ⊥
Si A ≡ B, entonces ⊨A↔B, por tanto, toda equivalencia se puede transformar en un bicondicional tautológico.
Pasa saber si una fórmula es una tautología se hace el tableau de la negativa del conjunto y debe dar un tableau cerrado.

Tableau proposicional
LINEAL BIFURCACION

Doble negación Conjunción Negación Condicional Disyunción Condicional Bicondicional Negación Bicondicional
¬¬𝐴 (A ˄ B) ¬(𝐴 → 𝐵) (A ˅ B) 𝐴→𝐵 𝐴↔𝐵 ¬(𝐴 ↔ 𝐵)
| | | | | | | | | | |
𝐴 A A A B ¬𝐴 B A ¬𝐴 A ¬𝐴
| | | | | |
B ¬𝐵 B ¬𝐵 ¬𝐵 B

Si se encuentra un término y su negación la rama se cierra con el símbolo , si todas las ramas se cierran es un tableau cerrado y por tanto
insatisfacible. Si queda alguna rama totalmente desarrollada y abierta es un tableau abierto y por tanto satisfacible en al menos una de sus
interpretaciones (el cual se logra según los literales de la rama).

Consecuencia lógica
Es cuando, en un conjunto de fórmulas, todas las interpretaciones que satisface ese conjunto también lo satisface la consecuente.
Propiedades
1. Reflexiva: Cualquier fórmula es consecuencia de sí misma o de un conjunto de fórmulas que la contenga.A ⊨A o A,B ⊨A
2. Monotonía: Si un conjunto de fórmulas es consecuencia de una, al añadir formulas al conjunto sigue siendo consecuencia. A ⊨A → A,B ⊨A
2.1. Si la nueva fórmula acorta las interpretaciones satisfacibles, la formula seguirá siendo consecuencia de las restantes.
2.2. Si la nueva fórmula hace insatisfacible el conjunto, toda formula es consecuencia de un conjunto insatisfacible.
3. Transitiva: A ⊨ B, B ⊨C ⇒ A ⊨ C

Si tenemos {A, B, C} ⊨D, es tautología que A˄𝐵˄𝐶 → D y a la inversa.


Si {A, B, C} ⊨D, entonces el conjunto {A, B, C, ¬D} no es satisfacible.
Para saber si una fórmula es consecuencia lógica se hace el tableau con la consecuencia negada, si sale cerrado es consecuencia. Por tanto:
{A, B, C} ⊨D ⇒ {A, B, C, ¬D} Tableau cerrado
El lenguaje de la lógica de predicados LOGICA DE PREDICADOS
El lenguaje de la lógica de predicados consta de los siguientes símbolos:
1. Constantes: a, b, c…
2. Conjunto no vacío de variables: x, y, z…
3. Funciones: f, g, h…
A cada función se le asocia un número natural llamado “aridad”, que indica el número de sus argumentos.
4. Conjunto no vacío de predicados: P, Q, R…
A cada predicado se le asocia una aridad.
4.1. Propiedades: predicados de aridad 1 (monádicos)
4.2. Relaciones: predicados de aridad 2 (diádicos) o mayor
5. La relación diádica de identidad la denotamos mediante =.
6. Constantes lógicas:
6.1. Cuantificador universal: ∀ (todos); ¬∃ (nadie)
6.2. Cuantificador existencial: ∃ (alguien); ¬∀ (no todos)
6.3. Restantes: ¬ , ˄ , ˅ , → , ↔.

Términos: conjunto más pequeño que se pueda lograr, indican un individuo. Pueden serlo constantes, variables y funciones.
Modelo: es la estructura que compone el lenguaje. La forma:
1.Dominio o universo de discurso: Conjunto de términos que componen el universo en el que se estudia. U= {1, 2, 3, 4}
2.Función de interpretación: 𝐼
2.1. Cada constante tiene una interpretación: a=1
2.2. Cada predicado tiene un subconjunto de términos del universo: P {1,4} R {2,3}

La fórmula tipo ∀𝑥𝛼 en un universo finito equivale a una conjunción. Para que una fórmula de este tipo sea verdadera todos los casos deben ser
verdaderos.
La fórmula tipo ∃𝑥𝛼 en un universo finito equivale a una disyunción. Para que una fórmula de este tipo sea verdadera al menos uno de los sacos debe
ser verdadero.

Equivalencias y Forma Prenexa

Podemos emplear todas las equivalencias de la lógica proposicional, además de las siguientes:

Quitar negación Factor común cuantificador Cambiar nombre variable Sacar cuantificador universal Sacar cuantificador existencial
¬∀𝑥 𝑄 ≡ ∃𝑥 ¬𝑄 ∀𝑥𝑄 ⋀ ∀𝑥𝑅 ≡ ∀𝑥(𝑄⋀𝑅) ∀𝑦𝑄 ≡ ∀𝑥𝑄(𝑦/𝑥) ∀𝑥𝑄 ⋀ 𝑅 ≡ ∀𝑥(𝑄⋀𝑅) ∃𝑥𝑄 ⋀ 𝑅 ≡ ∃𝑥(𝑄⋀𝑅)
¬∃𝑥 𝑄 ≡ ∀𝑥 ¬𝑄 ∃𝑥𝑄 ⋁ ∃𝑥𝑅 ≡ ∃𝑥(𝑄⋁𝑅) ∃𝑦𝑄 ≡ ∃𝑥𝑄(𝑦/𝑥) ∀𝑥𝑄 ⋁ 𝑅 ≡ ∀𝑥 (𝑄⋁𝑅) ∃𝑥𝑄 ⋁ 𝑅 ≡ ∃𝑥(𝑄⋁𝑅)

∀𝑥𝑄 → 𝑅 ≡ ∃𝑥(𝑄 → 𝑅) 𝑄 → ∀𝑥𝑅 ≡ ∀𝑥(𝑄 → 𝑅)


∃𝑥𝑄 → 𝑅 ≡ ∀𝑥(𝑄 → 𝑅) 𝑄 → ∃𝑥𝑅 ≡ ∃𝑥(𝑄 → 𝑅)

Forma Prenexa: Cuando en una formula todos los cuantificadores están al comienzo de la misma y por tanto no están afectados por ningún operador.

Tableau predicado
En él se aplican las mismas reglas que en el proposicional y se usa para lo mismo (satisfacibilidad, consecuencia, etc.), añadiendo dos reglas más:
- Regla 𝛾: Se usa en las fórmulas con constantes universales (∀𝑥𝑄, ¬∃𝑥𝑄). Se quitan los cuantificadores y se cambian las variables por cualquier término,
las veces que se necesite.
- Regla 𝛿: Se usa en las fórmulas con constantes existenciales (∃𝑥𝑄, ¬∀𝑥𝑄). Se quitan los cuantificadores y se cambian las variables por términos
nuevos, que no fueran anteriormente usados en la formula.
Se suele sustituir primero los existenciales y después los universales, para así poner los mismos términos y poder cerrar más fácilmente las ramas.
Teoría de Conjuntos ESTRUCTURAS DISCRETAS
Conceptos básicos
Conjunto: Colección de objetos distintos en el cual el orden no tiene importancia. Cada objeto que lo forma se llama elemento: Ej. S = {1, 2, 3, b, r, a, j, k}
Para expresar que un elemento pertenece a un conjunto se pone “∈”: Ej. 𝑎 ∈ 𝑆 , si el elemento no pertenece al conjunto se pone “∉ ": Ej. 𝑐 ∉ 𝑆

Podemos determinar un conjunto de dos formas: por extensión y por comprensión o intensión:
Extensión: Cuando se muestran concretamente todos los elementos del conjunto.
Comprensión o intensión: Cuando el conjunto aparece definiendo características de los elementos.

Conjunto finito: Conjunto que contiene un número limitado de elementos. Si no es finito el conjunto se denomina “conjunto infinito”.
Cardinalidad: Es el número de elementos que forman un conjunto finito. Se expresa poniendo “||”. Ej. A= {1, 2, 3} B = {1, 2, c, f, t}⇒ |A|=3; |B|=5
Conjunto vacío: No contiene ningún elemento. Se representa con el “∅”. Ej. A=∅ . Y por tanto su cardinal será 0. Ej. A=∅ ⇒ |A|=0
CUIDADO: ∅ ≠ {∅} El primer término es el vacío, pero el segundo se toma como un elemento mas de un conjunto

Subconjunto: Un conjunto es subconjunto de otro si todo elemento que pertenece al primero pertenece al segundo en el segundo. Se expresa con el
símbolo “⊏” o “⊑”. El conjunto vacío es subconjunto de cualquier conjunto: Ej. A = {1, 2, 3} B = {1, 2, 3, 4, 5}⇒ A ⊏ B; ∅ ⊏ B
Subconjunto propio: Es cuando un conjunto es subconjunto de otro, pero son distintos entre sí. Ej. A⊏ B y A≠B
Superconjunto: Se le denomina así al conjunto que contiene uno o varios subconjuntos. Se expresa con el símbolo “⊐” o “⊒”:
Ej. A= {1, 2, 3} B= {1, 2, 3, 4, 5} ⇒ B ⊐ A
Proposición: Un conjunto es un subconjunto de otro solo si ese otro es un superconjunto del primero: Ej. A⊏ B ⇒ B ⊐ A
Conjuntos iguales: Dos conjuntos son iguales si A ⊏ B y B ⊏ A, se escribe con el símbolo “=”. Ej. A=B. Si fuesen distintos se escribiría con el símbolo “≠”
Conjunto universal: (Se expresa como U o E) Es el conjunto que está formado por todos los posibles elementos que pueden pertenecer a cualquier otro
conjunto determinado en un contexto. E A= {1, 2, 3} B= {1, 2, 3, 4, 5}⇒ U = {1, 2, 3, 4, 5} o U = {x ∣ x es un número natural mayor que 0 y menor que 6}

Operaciones sobre conjuntos


Intersección: Es el conjunto de los elementos comunes en varios conjuntos, se representa con el “∩”.Ej. A= {1, 2, 3} B = {1, 2, c, f, t} ⇒ A∩B= {1,2}
Unión: Es el conjunto que contiene los elementos de varios conjuntos, se representa con el “∪”. Ej. A= {1, 2, 3} B = {1, 2, c, f, t} ⇒ A∪B= {1,2,3,c,f,t}
Si en una unión de dos conjuntos uno es un conjunto vacío, el resultado es el otro conjunto.
Diferencia: Es el conjunto formado por los elementos no comunes de varios conjuntos, se representa con la “\”.
Ej. A= {1, 2, 3} B = {1, 2, 6, 7}⇒A\B= {3}
Complemento de un conjunto: Dado un conjunto universal y un subconjunto del universal, se denomina el complemento del subconjunto al conjunto
formado por aquellos elementos del universal que no pertenecen al subconjunto. Se representa con el “~”. Ej. U= {1,2,3} A={2} ⇒ ~A={1,3}
El orden de precedencia es: ~, ∩, ∪, \

Partición de un conjunto
Conjuntos disjuntos: Son disjuntos si la intersección entre conjuntos da un conjunto vacío.Ej. A= {1, 2, 3} B = {c, f, t} ⇒ A∩B=∅
Partición de conjuntos: Es una colección de conjuntos los cuales ninguno es vacío, cada par de conjuntos es disjunto entre ellos y la unión de ellos forma
el conjunto inicial. Ej. A= {1, 2, 3, 4, 5} ⇒ A1= {1,5}; A2= {4}; A3= {2,3}
Conjunto Potencia: Es la unión de los subconjuntos que forman el conjunto inicial. En la unión también se cuenta el vacío y el propio conjunto; Ej.
A= {1, 2} ⇒ P(A)={ {1}, {2}, ∅, {1,2} } ⇒ {∅} ∪ { {1}, {2} } ∪ {A} CARDINAL del conjunto potencia |P(A)| = 2 n

Cardinalidad de unión
Cardinalidad de la unión de dos conjuntos: pasa saber la cardinalidad de dos conjuntos hay que sumar ambos conjuntos y restarle los que son comunes.
Ej. |𝐴 ∪ 𝐵|= |A|+|B|-|A∩B|
Cardinalidad de la unión de tres conjuntos: pasa saber la cardinalidad de tres conjuntos hay que sumar los conjuntos, restamos las intersecciones de
parejas y sumamos la intersección de las tres. Ej. |𝐴 ∪ 𝐵|= |A|+|B|+|c|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C |

Representación gráfica de conjuntos

Diagrama de Venn: Es una representación que sirve para visualizar varios conjuntos y sus interacciones. Cada conjunto se representa con un círculo y
dentro de ellos se ponen los elementos que tienen. Los conjuntos universales se representan con un cuadrado.
Ej. S∩T= {2,4}

Propiedades básicas

Asociativa Conmutativa Distributiva Idempotencia Absorción De Morgan


(𝐴 ∪ 𝐵) ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶) 𝐴∪𝐵=𝐵∪𝐴 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶) 𝐴 ∪ 𝐴 = 𝐴 𝐴 ∪ (𝐴 ∩ 𝐵) = 𝐴 ∼ (𝐴 ∪ 𝐵) =∼ 𝐴 ∩∼ 𝐵
(𝐴 ∩ 𝐵) ∩ 𝐶 = 𝐴 ∩ (𝐵 ∩ 𝐶) 𝐴∩𝐵=𝐵∩𝐴 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶) 𝐴 ∩ 𝐴 = 𝐴 𝐴 ∩ (𝐴 ∪ 𝐵) = 𝐴 ∼ (𝐴 ∩ 𝐵) =∼ 𝐴 ∪∼ 𝐵

Doble Complementación Identidad Complemento Exclusión Dominación Universal y vacío


∼ (∼ 𝐴) = 𝐴 𝐴∪∅=𝐴 𝐴 ∪ ~𝐴 = 𝑈 𝐴 ∩ ~𝐴 = ∅ 𝐴∪𝑈=𝑈 ~𝑈 = ∅
𝐴∩𝑈=𝐴 𝐴∩∅=∅ ~∅ = 𝑈
Relaciones ESTRUCTURAS DISCRETAS
Una relación de A en B es cualquier conjunto de pares (x,y), tal que x pertenece a A, y pertenece a B. (x,y) pertenece a R ⇒ R: A↔B
Producto cartesiano: Unión de elementos de dos conjuntos, en los que importa el orden. Se expresa con el símbolo “x”. No es conmutativo (a,2)≠(2,a).
Ej. A={1,2} B={a,b} ⇒ AxB= {(1,a), (1,b), (2,a), (2,b)}
Ej. R = {(1,b), (2,b)}
Dominio: Es todo elemento que este en la primera parte de la secuencia. Es el que inicia la relación. (1, a) Ej. dom R = {1, 2}
Rango: Es todo elemento que este en la segunda parte de la secuencia. Es el que recibe la relación. (1, a) Ej. ran R={b}
Aridad: cuenta el número de conjuntos que forman la relación, independientemente del número de relaciones que contenga. Ej. AxBxF tiene aridad 3.
Cardinalidad: m·n siendo m=|A| y n=|B|

FORMAS DE EXPRESAR RELACIONES


Matriz: Se colocan los términos del primer conjunto de la relación en las filas y los del segundo termino en las columnas.
Se pone 1 donde hay relación y 0 donde no. 𝑎 𝑏

( )
Ej. A={1,2} B={a,b} ⇒ R = { (1,b), (2,b)} ⇒ 1 0 1
2 0 1
Dígrafo: diagrama de flechas, donde se ponen los elementos de cada conjunto en círculos y se muestran las relaciones mediante flechas.
1 a
Ej. A={1,2} B={a,b} ⇒ R = { (1,b), (2,b)} ⇒
2 b

OPERACIONES SOBRE RELACIONES


Unión: R1 ∪ R2. Unión de todas la tuplas de R1 y R2.
Conjunción o Intersección: R1 ∩ R2. Tuplas comunes a R1 y R2.
Diferencia: R1 \ R2. Tuplas de R1 que no pertenecen a R2.
Complemento: ~R. Conjunto de las tuplas de A × B que no pertenecen a R. Ej. ~R={(1,a), (2,a)}
Relación inversa: R− 1. Es el intercambio del orden de los elementos que forman la secuencia. Ej. R− 1={(b,1), (b,2)}
Relación identidad: IA. Relación en A formada por todos los pares (x, x). Ej. IA={(1,1), (2,2)}
Composición de relaciones: Cuando hay una relación de dos conjuntos y a una relación de otro dos, de los cuales el primer conjunto coincide con el
segundo de la anterior relación. Se puede crear una tercera relación con el primer conjunto de la primera relación y el segundo conjunto de la segunda,
solo en los que compartan el termino elemento del conjunto en común. Ej.
X={1,2,3} | Relaciones: | (1,b) (b,t) ⇒ (1,t) | Relación obtenida:
Y={a,b,c} | XxY={ (1,a), (1,b), (2,c), (2,a) } | (1,b) (b,w) ⇒ (1,w) | XxZ={ (1,t), (1,w), (2,v) }
Z={t,u,v,w} | YxZ={ (b,t), (b,w), (c,v), (d,u) } | (2,c) (c,v) ⇒ (2,v) |

PROPIEDADES DE UNA RELACIÓN


En una relación binaria es:
Reflexiva: Es si TODO elemento tiene relación consigo mismo, (x,x), también llamado “𝐼 x”(relación identidad). Ej. en dígrafo: x
Irreflexiva: Es si NINGÚN elemento tienen relación consigo mismo.
Simétrica: Si TODA relación entre dos elementos diferentes es reciproca, R={(x,y), (y,x) }. Ej. En dígrafo: x y
Antisimétrica: Si NINGUNA relación entre dos elementos diferentes es reciproca.
Transitiva: En toda relación de tres elementos consecutivos debe haber una relación entre el primero y el ultimo. Ej. En dígrafo:

g f m g f

Cierres: Es añadir relaciones hasta que el conjunto cumpla la propiedad o propiedades que se busquen.
Relación de equivalencia: cuando es: Reflexiva, Simétrica y Transitiva.

RELACIONES DE ORDEN
Orden parcial o débil: Es Reflexiva, Antisimétrica y Transitiva. Ej. “ser menor o igual que”.
Orden estricto: Es Irreflexiva, Antisimétrica Y Transitiva. Ej. “ser menor que”.
Orden estricto inducido por un orden parcial: Es Irreflexiva, Antisimétrica Y Transitiva. Rʹ = R \ IX.
Orden total o lineal: Es cuando todos los elementos tienen que tener relación con los demás elementos, incluso consigo mismos.
RELACIÓN DE EQUIVALENCIA: es reflexiva, simétrica y transitiva
Funciones ESTRUCTURAS DISCRETAS
Naturales N={0,1,2…}; Enteros Z={…,-2,-1,0,1,2,…}; Racionales Q={...-1/3,-1,0,2,9/2,…} (NO raiz2 NO pi); Reales R=Q+Irraciona
Función total: Cuando en una relación cada elemento del primer conjunto esta relacionado con solo un elemento del segundo conjunto
(puede ser repetido). Ej. a 1 a 1 Las funciones creadas por las relaciones de conjuntos se denomina f(A)
b 2 b 2 g(A), etc…
c 3 c 3
Función parcial: Cuando en una relación de dos conjuntos se crea una función de un subconjunto del primer conjunto con el segundo conjunto.
Ej. A={1,2,3}; B={a,b,c,d} ⇒ A’={2,3} | A’ ⊏ A ⇒ A’xB={(2,b), (3,a)} Toda función total, es parcial
Función fija: Todo elemento del primer conjunto esta relacionado con el mismo elemento del segundo conjunto en la función.
Función Inyectiva: Si en la función no hay dos elementos del primer conjunto que lleguen al mismo elemento del segundo conjunto.
Función Sobreyectiva: A todo elemento del segundo conjunto de la función le debe llegar, al menos, una relación.
Función Biyectiva: Cuando es inyectiva y sobreyectiva. En el segundo conjunto de la función reciben todos los elementos una relación y solo una.
• Dos conjuntos tienen la misma cardinalidad si existe entre ellos una biyección. (Tienen que tener el mismo número de elementos).
• Cuando una función es biyectiva tiene inversa y se denomina con la letra de la función y un “-1”. En una composición de funciones si es con
X e Y ⇒ f-1 𝜊 f= Ix (Identidad de X); f 𝜊 f-1= Iy (Identidad de Y).
• Puede ser conjuntos vacíos, los cuales cumplen las propiedades necesarias.
Dominio: El conjunto primero en sí, puesto que todos deben estar relacionados con un elemento. En el parcial no tienen que estar relacionados todos.
Imagen: Los elementos del segundo conjunto que reciban la relación del primer conjunto (no tienen por qué ser todos).
Composición de funciones: *Igual que en la composición de 3 componentes de las relaciones. Se relaciona el primer conjunto de una función con el
segundo conjunto de una segunda función, siempre que tengan un mismo conjunto relacionándolos y coincidan elementos de ese conjunto. Cuando se
ve una composición de funciones se expresa con el símbolo “𝜊” la relación de funciones y cambiando el orden. Ej. f ( X→ Y); g(Y→ 𝑍) ⇒g 𝜊 f(Z→ 𝑍)

Combinaciones
(Recordad que 0!=1)
Grafos ESTRUCTURAS DISCRETAS
Grafos: Conjunto de nodos, “E”, (vértices) y un conjunto de aristas, “A”, (arcos)⇒(x,y) .
• Nodos son los componentes que tiene y aristas el par el cual está unido con cierto orden.
• Puede ser dirigido, dígrafo, (que tiene flecha) o no dirigido (no se pone flechas, solo una línea, porque esta en los dos sentidos.
• Sencillo: no hay aristas repetidas, si sale repetida se denomina multígrafo.
• Bucle: arista que comienza y acaba en el mismo nodo.
Número máximo de aristas o arcos de un grafo de n Vértices, sin contar las aristas que unen un vértice consigo mismo (no bucles):
• Grafo no dirigido: n (n-1) / 2
• Grafo dirigido: n (n-1)

GRADOS
Grado de entrada: número de aristas que terminan en un nodo.
Grado de salida: numero de aristas que comienzan en un nodo.
Grado total: suma de los grados de entrada y salida de un nodo.
• Si una arista es de identidad, reflexiva, (x,x) es tanto un grado de entrada como de salida.
• Grado total de un nodo de un grafo dirigido sencillo sin bucles de n nodos = 2n-2 . Y con bucles = 2n

CAMINOS
Camino: Sucesión de aristas, donde el nodo final es el inicial de la siguiente arista. Se puede expresar como⇒ camino= (a,b,c)
• Ciclo: cuando un camino comienza y acaba en el mismo nodo. Cuando un dígrafo no tiene ciclos se llama acíclico.
Camino sencillo: No pasa dos veces por la misma arista.
Camino elemental: No pasa dos veces por el mismo nodo. Cuando es un ciclo se permite que se repita el ultimo nodo para su cierre.

DISTANCIA ENTRE NODOS


La longitud de un camino es las aristas que forman ese camino.
20
Grafo ponderado: Grafo en el que sus aristas tienen valor. Ej. x y
• La longitud de un grado ponderado es la suma de sus aristas.

Distancia: Longitud mínima que hay entre dos nodos.


• Si no hay camino que los conecte si valor es infinito.
• La distancia entre un nodo y el mismo es 0.

CONECTIVIDAD
Un grafo no dirigido: (con líneas en vez de flechas por el doble sentido), es conexo si para cualquier pareja de nodos hay un camino.
• Todos los tipos de conectividad coinciden
Un dígrafo o grafo dirigido: (con flechas) es unilateralmente conexo si para cualquier pareja de nodos hay al menos un camino.
• Es fuertemente conexo si para cualquier pareja de nodos existen caminos para ir desde un nodo a otro.
• Es débilmente conexo o conexo si eliminando el sentido de las flechas es conexo

RECORRIDO DE GRAFOS
Anchura: (Amplitud) Se miran los nodos por niveles, no avanzando en el desarrollo hasta completar el nivel.
Profundidad: Se sigue un camino y hasta que no se termina no se puede empezar otro. No se resuelve el primer nodo
que dejaste pendiente de seguir, sino el ultimo. Al nodo desde el que se pueden visitar todos los nodos se denomina
raíz.

Ordenación topológica: En un dígrafo es una ordenación de sus nodos de forma que todas las aristas del grafo van
siempre desde un nodo anterior a uno posterior en la ordenación, para ello no puede ser un ciclo. Ej.
(a,c), (a,d), (a,b), (c,d) ⇒ (a,b,c,d)

ARBOLES DE EXPANSION

Árbol libre (árbol): Grafo sencillo, no dirigido, conexo y acíclico. (Como en anterior puesto)

Árbol de expansión: Trozo de grafo, no dirigido, conexo y acíclico. Es un subgrafo, es decir, sus aristas son un subconjunto del grafo.

Árbol de expansión mínimo: Grafo ponderado, conexo y no dirigido, tal que la suma de los valores de sus aristas es el mínimo posible.

También podría gustarte