Month: enero 2011

Hablamos siempre de grafos dirigidos. Un vértice v_i alcanza a otro v_j si existe un camino que vaya desde v_i ahasta v_j, entonces v_j es accesible desde v_i.
Matriz de accesibilidad

En la matriz cuadrada R, r_ij vale 0 si v_i no alcanza a v_j y vale 1 si v_j es accesible desde v_i. La diagonal principal siempre es de unos, ya que todo vértice es accesible desde sí mismo.
El conjunto R(v_i) esta formado por los vértices accesibles desde v_i. Estará formado por él mismo, sus vértices adyacentes, Γ(v_i), y los adyacentes a estos Γ²(v_i)… hasta Γ^p(v_i), donde ya no se aporten vértices nuevos a la siguiente iteración.

Matriz de acceso

Q es la transpuesta de la matriz de accesibilidad (R), por lo que el elemento q_ij vale 0 si v_i no es alcanzado desde v_j y vale 1 si v_i es accesible desde v_j.
El conjunto Q(v_i) lo forman los vértices que alcanzan a v_i. Estará formado por él mismo, los vertices que son extremo inicial de los aros incidentes con él, Γ^-1(v_i), y los respectivos a estos Γ^-2(v_i)… hasta Γ^-p(v_i).

Matriz de Adyacencia: Matriz cuadrada A, donde a_ij, es el número de aristas que unen el vértice v_i con el v_j, o el número de arcos que van desde v_i hasta v_j.

• En grafos no dirigidos es una matriz simétrica, y los bucles cuentan por 2. Además la suma de los elementos de cada columna i o de cada fila i son el grado del vértice v_i.
• En grafos dirigidos la suma de las elementos de la fila i es el grado de salida del vértice v_i, mientras que la suma de los elementos de una columna j es el grado de entrada del vértice v_j.

Al elevar la matriz A a r, se obtiene A^r, otra matriz cuadrada cuyos elementos a_ij son el número de cadenas de longitud r que van desde v_i hasta v_j.

Matriz de Incidencia: Cada fila corresponde a un vértice y cada columna a un arco o arista.

• En grafos no dirigidos, el elemento m_ij puede ser: 0 si v_i no es incidene con e_j; 1 si v_i es incidene con e_j; y 2 si en v_i, e_j forma un bucle.
• En grafos dirigidos, el elemento m_ij puede ser: 0 si v_i no es incidene con e_j; 1 si v_i es vértice inicial de e_j; -1 si v_i es vértice final de e_j; y 2 si en v_i, e_j forma un bucle.

Cadena: Sucesión de vértices y de las aristas que los unen

• Camino: Cadena con todos sus vértices distintos.
• Cadena Simple: Cadena con todas sus aristas distintas.
• Cadena Cerrada: Cadena con el vértice inicial igual al final.
  • Ciclo: Cadena simple y cerrada con sus vértices internos distintos.
  • Circuito: Ciclo en un grafo dirigido.

Longitud: Número de aristas que contiene una cadena. Un ciclo de longitud k se llama k-ciclo.

Conexión: Dos vértices u y v están conectados si existe una cadena desde u hasta v y viceversa.

Grafo conexo: Si para todo par de vértices están conectados.

TEOREMA: Un grafo es bipartido si no existe un ciclo de longitud impar en él.

Subgrafos: Un grafo H es subgrafo de G si todos los vértices y todas las aristas de H están también presentes en G. Si además, el subgrafo H tiene el mismo número de vértices que G, decimos que es un subgrafo generador.

Cualquier grafo tiene un subgrafo generador simple. Si este subgrafo tiene el mayor número de aristas se llama grafo simple subyacente.

Grado de un vértice: Siendo G=(V,A) un grafo no dirigido, y v pertenece a V, el grado de v, dG(v), es el número de aristas incidentes con él. El conjunto de vértices adyacentes con v se denomina Γ(v).

En un grafo dirigido se diferencian el grado dalida ds(v) y el grado de entrada de(v). El grado total del vñertice es la suma de ambos, d(v)=de(v)+ds(v). En este caso, Γ(v) contiene los vértices que son extremo final de los arcos que salen de v, y Γ^-1(v) a los vértices que son extremo inicial de los arcos que entran en v.

TEOREMA: El número de vértices de grado impar en un grafo, es par.

GRAFO: Conjunto de vértices (V) unidos entre si mediante enlaces, aristas o arcos (A), G=(V,A).

• No dirigidos: Las uniones son aristas, sin sentido definido (equivalente a un segmento). Funcionan para ambas direcciones.
• Dirigidos: Las uniones son arcos, con sentido definido, representado con una flecha (equivalente a un vector). Si en un grafo dirigido ignoramos la dirección de los arcos obtenemos en grafo no dirigido asociado.
• Mixto: Contiene tanto aristas como arcos.

• Simple: Sin bucles (union de un vértice consigo mismo), y sin más de una arista (o más de un arco en el mismo sentido) que unan el mismo par de vértices.
• Multigrafo: Grafo que no es simple.

• Completo: Con al menos una arista (o un arco para cada uno de los sentidos) uniendo cada par de vértices.
• Incompleto: Un grafo que no es completo. Si no hay ninguna unión el grafo se llama vacío.

• Bipartido: Los vértices pueden dividirse en dos conjuntos (por ejemplo X e Y) y los enlaces siempre unen un vértice de X con uno de Y. Un grafo dirigido es bipartido si lo es su grafo no dirigido asociado.

• Regular: De cada vértice parte el mismo número de aristas. Si son dirigidos se cuentan las aristas que entran y salen.

ESPECIFICACIONES:

Un grafo completo, no dirigido y simple se denomina Kn, siendo n el número de vértices

Los extremos (vértices) de un enlace (arista o arco) son incidentes a ese enlace

Dos vértices incidentes al mismo enlace son adyacentes entre sí.

En un grafo simple, un enlace queda definido por los vértices a los que une

Un grafo regular se representa como n-regular, siendo n el numero de enlaces con los que cada vértice es incidente.

1. Lógica Formal de Primer Orden:

1.1. Razonar: Resolver problemas conectando unas ideas con otras.

• Lógica: Ciencia formal que estudia la validez de los razonamientos.
• Lógica Formal: Ejerce la lógica sirviéndose de lenguajes formales abstractos que desprecian el contenido del razonamiento y se centran en la estructura.

1.2. Componentes de los razonamientos:

• Proposición: Sentencia declarativa bivalente, que puede ser verdadera o falsa.
  • Atómica: Carece de conexiones con otras proposiciones, V o F.
  • Literal: Proposición atómica afirmada o negada.
  • Molecular: Conjunto de proposiciones atómicas unidas por una conectiva:

–  Conjuntiva: Equivale al “Y”, es conmutativa, expresa adicción.

–  Disyuntiva: Equivale al “O”, es conmutativa, expresa alternativas.

–  Condicional: Equivale al “SI… ENTONCES…”, no es conmutativa.

°       Antecedente: Después del “SI” condición suficiente del consecuente.

°       Consecuente: Después del “ENTONCES” condición necesaria del antecedente.

–  Bi-condicional: Equivale al “SI Y SOLO SI… ENTONCES…” es conmutativa.

• Premisas: Proposiciones de las que se parte para llevar a cabo un razonamiento.
• Inferencia: Operación lógica que obtiene nuevas proposiciones aplicando reglas.
• Conclusión: Resultado que se quiere demostrar. Se obtiene a partir de las premisas.

1.3. Razonamientos correctos y falacias

• Razonamiento correcto: Si no es posible que sus premisas sean verdaderas y su conclusión falsa. Si se aceptan las premisas se acepta la conclusión.
• Falacia: Razonamiento aparentemente lógico pero que incorrecto.
  • Falacia formal: Afecta a la estructura del razonamiento.

–  Afirmar el consecuente: En un condicional, si se afirma el consecuente, no tiene porque afirmarse el antecedente.

–  Negar el antecedente: En las condicionales, al negar el antecedente no se debe negar el consecuente.

• Falacia informal: Afecta al contenido del razonamiento.

1.4. Sistemas Formales Lógicos: Herramienta de la lógica formal compuesta por:

• Lenguaje formal ^{Tema 2}: Símbolos (alfabeto) y reglas (gramática), formalmente especificados, que combinados dan  lugar a una fbf (formula bien formada).
• Semántica ^{Temas 3 y 4}: Estudia la interpretación de las fórmulas en el mundo real.
• Proceso Deductivo: Demostración de que desde las premisas se extrae la conclusión, mediante la aplicación de reglas
• Lógica Proposicional: Supone que existen hechos simples que pueden ser verdaderos o falsos (proposiciones), y los relaciona mediante conectivas lógicas.
• Lógica de predicados: Describe, además de los hechos y sus relaciones, a los sujetos, sus propiedades y sus  semejanzas con otros sujetos.

2. Lenguaje de la Lógica de Primer Orden. Teoría de Conjuntos.

2.1. El Lenguaje de la Lógica de Primer Orden:

• Lenguaje Natural: Ambiguo, polisemántico, muy expresivo. Ejemplo: el español.
• Lenguaje Formal: Conciso, preciso, universal, estático, basado en la estructura y no en el contenido. Ejemplo: Lenguaje Formal de la Lógica de Primer Orden:
  • Lógica Proposicional: Busca hechos y conexiones entre ellos
  • Lógica de Predicados: Además destaca sujetos y sus propiedades y relaciones.

2.2. El Lenguaje Proposicional: Propio de la lógica proposicional.

• Alfabeto: Conjunto de símbolos que se utilizan en el lenguaje.
  • Variables Proposicionales: Letras que representan proposiciones atómicas.
  • Conectivas Lógicas: Representan conexiones entre proposiciones atómicas.

– Negación: Se expresa mediante ¬ y, ¬A es cierta cuando A es falsa.

– Conjunción: Se expresa como ∧, y A∧B es cierto cuando ambas son ciertas.

– Disyunción: Se expresa como ∨, y A∨B es cierto si alguna de las dos lo es.

– Condicional: Se expresa como →, A→B se cumple si para A cierto, lo es B.

– Bicondicional: Se expresa como ↔, A↔B se cumple si v(A)=v(B).

• Símbolos auxiliares: Paréntesis que se utilizan para estructurar las fórmulas.
• Gramática: Equivale al “Y”, es conmutativa, expresa adicción.
  • Formación de una fbf: Una variable proposicional A siempre es una fbf, además también lo serán ¬A, A∧B, A∨B, A→B y A↔B.
  • Jerarquía: Negación (¬), conjunción (∧) y disyunción (∨), y condicionales (→,↔)
  • Asociatividad: Todas las conectivas lógica binarias son asociativas por la izquierda menos los condicionales y bicondicionales que lo son por la derecha.

2.3. El Lenguaje de Predicados: Formaliza las proposiciones con  sus conexiones y los sujetos que las realizan con sus propiedades y relaciones dentro de un marco conceptual.

• Alfabeto: Conjunto de símbolos formado por:
• Símbolos del lenguaje proposicional: Las variables proposicionales, conectivas lógicas y los símbolos auxiliares también se usan en este lenguaje.
• Términos: Expresión que se refiere a un objeto, no es ni verdadera ni falsa.

– Variables: Se refieren a objetos indeterminados Ej: x.

– Constantes: Hacen referencia a algún objeto concreto Ej: maría.

– Funciones: Denotan objetos en función de sus argumentos Ej: padre (luís).

• Predicados: Denotan una propiedad de su argumento o describen una relación entre sus argumentos, pueden ser verdaderos o falsos Ej: Padre(pepe, luís).
• Cuantificadores: Establecen el alcance de las variables de una fórmula lógica

– Universal: Se escribe como “, y engloba a todos los elementos del dominio. Ej. “x(Ho(x) → Mor(x)), todo hombre es mortal.

– Existencial: Se escribe como $, y declara que algún elemento del dominio cumple la condición. Ej. $x(Ho(x) ∧ Feo(x)), existe algún hombre feo.

• Gramática: Similar a la del lenguaje proposicional
• Dominio: Conjunto de cosas de las cuales se habla, universo del discurso.

2.4. Construcción de Formulas:

• Formalizar en lenguaje proposicional: Ver si la formula es atómica  o molecular.
  • Atómica: En este caso nombrarla con una variable proposicional.
  • Molecular: En este caso detectar los elementos que la forman y unirlos con las conectivas correspondientes. Realizar el smismo análisis con los elementos.
  • Formalizar en lenguaje de predicados: Analizar la estructura de la fórmula lógica:
    • Atómica: Elegir nombre para predicados y constantes.
    • Molecular: Conectar los componentes con las conectivas correspondientes.
    • No constantes: Elegir cuantificador y el nombre de predicados.

– Un cuantificador universal se formaliza con el Implicador.

– Un cuantificador existencial se formaliza con la conjunción.

• Equivalencias:
  • Implicador-Disyuntor: A→B » ¬A∨B
  • Implicador-Conjuntor: A→B » ¬(A ∧ ¬B)
  • Leyes de Morgan: ¬A ∧ ¬B » ¬(A ∨ B) ; ¬A ∨ ¬B » ¬(A ∧ B)
  • Ley del Bicondicional: A↔B » (A→B) ∧ (B→A)
  • Cuantificadores: ¬ [“/$] x P(x) » [$/”]x ¬P(x) ; ¬[“/$] ¬P(x) » [$/”]x P(x).

2.5. Formalización de Razonamientos: Para formalizar un razonamiento deductivo en el lenguaje lógico hay que identificar las premisas y la conclusión, y formalizarlas tras definir un marco conceptual sobre el que trabajarán.

2.6. Conjunto: Colección de objetos definidos y diferenciados llamados elementos. Se denotan con letras mayúsculas, Ej. El conjunto de vocales: V= {a,e,i,o,u}.

• Pertenencia: Si “a” es un elemento del conjunto “A” se dice que aÎA, y si no aÏA.
• Declaración: Encerrando entre llaves todos sus elementos, o enunciando una característica que lo defina. Æ es el conjunto vacio, y U el universo del discurso.
• Subconjuntos: A es un subconjunto de B si todo elemento de A pertenece también a B: AÍB. Para que el subconjunto sea propio A no debe ser igual que B.

2.7. Operaciones entre Conjuntos:

• Intersección: Se representa por AÇB, y lo forman los elementos que pertenecen a A y a B al mismo tiempo.
• Unión: Escrito AÈB,  lo forman todos los elementos de A y todos los de B.
• Diferencia: A-B, es el conjunto formado por todos los elementos de A menos los que también pertenecen a B.
• Complementario: A’ lo forman los elementos que no pertenecen a A.
• Propiedades: Conmutativa, asociativa, distributiva y leyes de Morgan.

2.8. Relación entre Tª de Conjuntos y L. de 1er Orden

• El subconjunto equivale al Implicador: AÍB » A→B.
• La unión equivale a la disyunción: AÈB » A∨B .
• La intersección equivale a la conjunción: AÇB » A∨B.
• El complementario equivale al negado: A’ » ¬A.

3. Semántica de la Lógica de Primer Orden. Demostración.

3.1. Fundamentos teóricos:

• Preparación del problema: Con Tablas de Verdad, el Contraejemplo, o Resolución.
• Concepto de verdad: Se define como satisfacción de una condición. Según el principio de bivalencia, una proposición atómica solo puede ser verdadera o falsa.
• Interpretación: Función que asigna un valor de verdad a una función a partir de los significados de sus componentes básicas.
  • Fórmulas atómicas: Tienen dos interpretaciones, verdadero y falso.
  • Fórmulas moleculares: Según sus variables n, tiene 2ⁿ interpretaciones.

– Conectivas: Mirar el apartado 2.2. (“Conectivas Lógicas”).

– Términos: Es necesario definir un dominio de referencia.

– Predicados: También se define según el dominio, con Dⁿ interpretaciones.

– Cuantificadores: Se definen según el dominio de referencia:

°   Universales: Son V si todos los elementos del dominio de la variable son V.

°   Existenciales: Son V si algún elemento del dominio de la variable es V.

• Tipos de interpretaciones: Según los valores de la interpretación:

– Interpretación Modelo: Bajo la cual, la fbf se interpreta como verdadera.

– Interpretación Contraejemplo: Cuando la fbf se interpreta como falsa.

• Clasificación Semántica: De fórm. atómicas hay 2: V y F. De las moleculares:

– Tautología: Cuando para toda interpretación la fbf es verdadera.

– Contradicción: Cuando para cualquier interpretación la fbf es falsa.

– Contingencia: Existe algunas interpretaciones que la hagan V y otras F.

• Tipos de fórmulas: Según sus interpretaciones posibles:

– Satisfacible: Si alguna interpretación la hace verdadera.

– Insatisfacible: Si ninguna interpretación la hace verdadera.

• Consecuencia Lógica: Q es consecuencia lógica de P si siempre que se cumple P se cumple Q también, sin excepción
• Razonamiento correcto: Un razonamiento P_i Þ Q es correcto solo si la conclusión Q es consecuencia lógica de las premisas.

3.2. Métodos de las tablas de verdad y del contraejemplo

• Tablas de Verdad: Muestran el valor semántico de una fbf molecular para cada combinación de valores de verdad que se pueden asignar a sus componentes.

–  Filas: Una por cada interpretación de la fórmula. 2ⁿ siendo n las variables.

–  Columnas: Una por cada variable que aparezca en la fbf.

• Resultado: Con el desglose de valores de verdad podemos comprobar que siempre que se cumplen las premisas se cumple la conclusión.
• Método del Contraejemplo: Prueba la falsedad de un enunciado, suponiendo que lo es. Si con esta suposición se llega a contradicción el enunciado es correcto.
  • Procedimientos: Dar valores verdaderos a todas las premisas y valor falso a la conclusión, y desarrollar hasta encontrar una contradicción. Si no encontramos contradicción es que existe una interpretación con esos valores, que hacen al razonamiento contingente o contradictorio.

3.3. Regla de Resolución: Comprueba que el conjunto C = {P1, P2,…Pi, ¬Q} es insatisfacible.

• Forma Clausal: Expresión de una formula como disyunción de literales.
  • Obtención: Usando las equivalencias que resultan en disyunciones (2.4.) y las propiedades (2.7.), renombrando variables, usando el criterio de Skolem y situando los universales al principio de la fórmula.

– Criterio de Skolem: Si un cuantificador existencial esta dentro del ámbito de un universal, la variable del primero depende de la del segundo según una función: Ej. “y$x P(x, y) » ” P(f(y), y).

• Resolución Proposicional: A partir de un conjunto de clausulas C = {P1, P2,…Pi, ¬Q} se desarrollan clausulas resolubles y se obtienen resolventes (a partir de literales complementarios) Ej. desde Cl1: P∨Q , Cl2: ¬P∨R, se obtiene Cl3: Q∨R. Hasta encontrar una contradicción que demuestre que el conjunto C es insatisfacible.
• Resolución Predicativa: Es necesaria la sustitución de las variables por términos, con el fin de conseguir los literales complementarios (si tenemos Q(x) y ¬Q(a) deberemos sustituir x por a), la sustitución se debe hacer en todas las sub-fórmulas: Ej. Cl1: P(x, y) ∨ Q(x), Cl2: ¬Q(a) ∨ R(z), Cl3: P(a, y) ∨ R(z).

4. Demostración por Deducción Natural

4.1. Fundamentos Teóricos: El objetivo es, a partir de las premisas y con el único apoyo de unas reglas básicas obtener la conclusión pedida, tras pequeños pasos justificados.

• Subdeducciones: Deducciones tras un supuesto provisional. Este supuesto debe cancelarse antes de finalizar la demostración y las formulas interiores de la subdeducción son inaccesibles. Podemos suponer cualquier cosa.
• Componentes: Un número finito de fórmulas que pueden diferenciarse en:
  • Premisas: Hipotéticamente dadas desde el principio de la deducción.
  • Supuestos provisionales: Subdeducciones.
  • Líneas deducidas: Consecuencias lógicas inmediatas de líneas anteriores.
  • Líneas de deducción:
    • Número de líneas: Se numeran las líneas en la parte izquierda, desde el 1.
    • Señalas premisas: Se señalan con una raya antes de la numeración.
    • Comentarios de consecuencias inmediatas: Se señala, en cada deducción inmediata la regla utilizada para llevarla a cabo, y las líneas afectadas.
    • Subdeducciones: En la línea que empieza marcamos con el inicio de una escuadra (ì), y en las sucesivas prolongamos la escuadra (ï). Para cancelas la subdeducción cerramos la escuadra (î), siempre antes de la numeración.

4.2. Reglas de Inferencia Básicas: Dos para cada conectiva (introducción y eliminación):

• Reglas básicas de Implicación
  • Introducción: Si de una hipótesis A se sigue B, se puede añadir que A→B.
  • Eliminación: Supuesta una implicación y la fórmula que hace en ella de  antecedente, se puede afirmar  consecuente.
  • Reglas básicas de Conjunción
    • Introducción: Si se afirma una proposición y luego se afirma otra también, se puede afirmar la conjunción de ambas
    • Eliminación: De la conjunción de varias proposiciones se afirman todas ellas.
  • Reglas básicas de Disyunción
    • Introducción: Si una fórmula es verdadera, también es verdadera su disyunción con otra fórmula cualquiera.
    • Eliminación: Si de cada uno de los componentes se deduce la misma fórmula se puede afirmar esa fórmula.
  • Reglas básicas de Negación
    • Introducción: Toda proposición que deduce una contradicción debe negarse.
    • Eliminación: Negar doblemente una fórmula es tanto como afirmarla.
  • Reglas básicas del Cuantificador Universal
    • Introducción: Si un individuo cualquiera (no uno en particular) verifica una propiedad, todos los individuos del universo la verifican.
    • Eliminación: De la verdad de todos los individuos se puede afirmar la verdad de un individuo en particular.
  • Reglas básicas del Cuantificador Existencial
    • Introducción: Si un individuo verifica una propiedad P, existe algún individuo que la verifica.

4.3. Demostración por el Método Directo: Si se quiere deducir una formula condicional hay que suponer el consecuente (subdeducción) y se realiza la argumentación hasta llegar a inferir el consecuente.

4.4. Demostración por el Método de Reducción al Absurdo: Para demostrar una formula por este método debemos de suponer su complementaria, y desarrollarla en una subdeducción hasta llegar a una contradicción. Si aparece la contradicción es que la negada, la complementaria, no existe, con lo que la formula queda demostrada.