Logo-apuntesuned

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterHoy824
mod_vvisit_counterAyer697

Fecha: 17 Dic de 2017

Lógica y Estructuras Discretas

Esta asignatura proporciona estructuras matemáticas sobre las que modelizar problemas (preguntas, restricciones, sobre un determinado conjunto de datos). Además facilita los mecanismos deductivos necesarios para construir la solución de tales problemas o para comprobar que una solución dada es correcta.

Contenidos de la asignatura

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

  • Proposicional: sintaxis y semántica, tablas de verdad, formas normales; satisfacibilidad, validez, equivalencia y consecuencia.
  • Predicados: sintaxis y semántica.

2. Técnicas básicas de prueba

  • Deducción natural: pruebas directas. Tableaux.
  • Inducción. Definiciones recursivas.

3. Conjuntos, relaciones y funciones

  • Subconjunto, complemento, diagramas de Venn, producto cartesiano, conjunto potencia
  • Relaciones: concepto y propiedades (reflexividad, simetría, antisimetría, transitividad). Relaciones de equivalencia y de orden.
  • Funciones: inyectivas, sobreyectivas, inversa, composición.

4. Combinatoria

  • Principios básicos de la combinatoria.
  • Formas de agrupamiento: Variaciones, combinaciones y permutaciones.

5. Árboles y grafos

  • Grafo: definición. Grafos dirigidos y no dirigidos. Grafos acíclicos. Árboles.
  • Estrategias de recorrido. Árboles de expansión.