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.