Herramientas de usuario

Herramientas del sitio


intrologica:main

Introducción a la Lógica y la Computación

* Cursado: Segundo cuatrimestre de 2017

* Profesores: Mariana Badano, Raúl Fervari, Héctor Gramaglia, Miguel Pagano

* Ayudantes: Guillermo Incatasciato, Marianela Morales, Francisco Trucco

Programa de la materia correspondiente al año 2017

Generalidades

  • La materia se divide en tres partes, que corresponden con los tres grandes ejes temáticos.
  • Parte 1: Estructuras Ordenadas. A cargo de Héctor Gramaglia, se desarrolla en el período 16/8 al 8/9.
  • Parte 2: Lógica. A cargo de Miguel Pagano, se desarrolla en el período 13/9 al 18/10.
  • Parte 3: Lenguajes y Autómatas. A cargo de Raul Fervari, se desarrolla en el período 20/10 al 17/11.
  • Primer Parcial: 15/9/2017.
  • Segundo Parcial: 25/10/2017.
  • Recuperatorio: 22/11/2017.
  • Coloquio: 22/11/2017.
  • Promoción: obteniendo al menos 6 en cada uno de los parciales, con promedio al menos 7 y aprobando el coloquio de la parte 3.
  • Regularidad: aprobando 2 parciales con al menos 4.

Reprogramación del parcial para quienes no rindieron el viernes pasado: Martes 19/09 a las 9h

AULA 11

Apuntes

Clases 2017

Parte I: Estructuras Ordenadas

  • Clase del 16/8 Concepto de Relación. Relaciones de equivalencia y de orden. Caracterización de las relaciones de equivalencia.
  • Clase del 18/8 Conjunto parcialmente ordendo (CPO o POSET). Máximos, mínimos, elementos maximales y minimales, supremos e ínfimos. Noción de isomorfismo. Propiedades de los isomorfismo.
  • Clase del 23/8 Poset reticulado. Reticulado como estructura algebraica. Reticulado de divisores. Reticulado de subconjuntos. Isomorfismo de reticulados.
  • Clase del 25/8 Reticulados acotados y complementados. Problema de la existencia de más de un complemento: reticulados M3 y N5. Desigualdades distributivas. Reticulados distributivos.
  • Clase del 30/8 Caracterización de los reticulados distributivos. Álgebras de Boole. Leyes de De Morgan. Problema: ¿todas las álgebras de Boole son álgebras de un conjunto?
  • Clase del 1/9 Teorema de Representación para las Álgebras de Boole.
  • Clase del 6/9 Reticulado de subconjuntos decrecientes de un poset. Teorema de Birkhoff. Caso Álgebras de Boole.
  • Clase del 8/9 Construcción de un Álgebra de Boole infinita que no es Álgebra de conjuntos. Propiedades de los reticulados Dn.

Parte II: Lógica Proposicional

Parte III: Lenguajes y Autómatas

Prácticos 2017

Parte I: Estructuras Ordenadas

  • Práctico A.1 Ejercicios seleccionados del Capítulo 1: Relaciones.
  • Práctico A.2 Ejercicios seleccionados del Capítulo 2: Conjuntos parcialmente ordenados (posets).
  • Práctico A.3 Ejercicios seleccionados de los Capítulos 2 y 3: Isomorfismos de posets. Posets reticulados.
  • Práctico A.4 Ejercicios seleccionados del Capítulo 3: Reticulados. Es un práctico corto, ideal para ponerse al día!
  • Práctico A.5 Ejercicios seleccionados del Capítulo 3: Reticulados con complementos y reticulados distributivos. En esta clase le preguntamos al Estado: ¿Dónde está Santiago Maldonado?

  • Práctico A.6 Ejercicios seleccionados del Capítulo 3: Álgebras de Boole.
  • Práctico A.7 Ejercicios seleccionados del Capítulo 4: Álgebras de Boole, átomos y representación.
  • Práctico A.8 Ejercicios seleccionados del Capítulo 4: Teorema de Birkhoff para reticulados distributivos.
  • Práctico A 9 Práctico de repaso.

Parte II: Lógica Proposicional

Parte III: Lenguajes y Autómatas

Cursado de años anteriores

Cursado 2016

Parte I: Estructuras Ordenadas

  • Clase del 17/8 Concepto de Relación. Relaciones de equivalencia y de orden. Caracterización de las relaciones de equivalencia.
  • Clase del 19/8 Conjunto parcialmente ordendo (CPO o POSET). Máximos, mínimos, elementos maximales y minimales, supremos e ínfimos. Noción de isomorfismo. Propiedades de los isomorfismo.
  • Clase del 26/8 Poset reticulado. Reticulado como estructura algebraica. Reticulado de divisores. Reticulado de subconjuntos. Isomorfismo de reticulados.
  • Clase del 31/8 Reticulados acotados y complementados. Problema de la existencia de más de un complemento: reticulados M3 y N5. Desigualdades distributivas. Reticulados distributivos.
  • Clase del 2/9 Caracterización de los reticulados distributivos. Álgebras de Boole. Leyes de De Morgan. Problema: ¿todas las álgebras de Boole son álgebras de un conjunto?
  • Clase del 7/9 Teorema de Representación para las Álgebras de Boole. Reticulado de subconjuntos decrecientes de un poset. Teorema de Birkhoff.
  • Clase del 9/9 Reticulado de subconjuntos decrecientes de un poset. Teorema de Birkhoff. Caso Álgebras de Boole.
  • Clase del 14/9 (Ver pdf: Clase del 9/9) Construcción de un Álgebra de Boole infinita que no es Álgebra de conjuntos. Propiedades de los reticulados Dn.

Parte II: Lógica Proposicional

Parte III: Lenguajes y Autómatas

Prácticos 2016

Estructuras Ordenadas

  • Práctico A.1 Ejercicios seleccionados del Capítulo 1: Relaciones.
  • Práctico A.2 Ejercicios seleccionados del Capítulo 2: Conjuntos parcialmente ordenados (posets).
  • Práctico A.3 Ejercicios seleccionados de los Capítulos 2 y 3: Isomorfismos de posets. Posets reticulados.
  • Práctico A.4 Ejercicios seleccionados del Capítulo 3: Reticulados. Es un práctico corto, ideal para ponerse al día!
  • Práctico A.5 Ejercicios seleccionados del Capítulo 3: Reticulados con complementos y reticulados distributivos.
  • Práctico A.6 Ejercicios seleccionados del Capítulo 3: Álgebras de Boole.
  • Práctico A.7 ½ Ejercicios seleccionados del Capítulo 4: Álgebras de Boole, átomos y representación. Teorema de Birkhoff para reticulados distributivos.
  • Práctico A.9 Práctico de repaso

Lógica Proposicional

  • Práctico.B.1 Proposiciones. Definición de PROP. Definiciones por recursión.
  • Práctico.B.2 Asignaciones. Valor de verdad de una proposición: función semántica.
  • Práctico.B.3 Consecuencia lógica. Derivaciones: el sistema de deducción natural.
  • Práctico.B.4 Práctico.B.4.bis Derivaciones. Regla RAA.
  • Práctico.B.5. Conjuntos consistentes (maximales). Corrección y Completitud. (Es el práctico 4 del año pasado, está bien así).

Lenguajes y Autómatas

Notas de Parciales

Notas de Final 16/2/2017

Legajo: 347476229 (nueve)
Legajo: 372250567 (siete)
Legajo: 37517946No Aprobado
Legajo: 3213748110 (diez)
Legajo: 342949395 (cinco)
Legajo: 381790944 (cuatro)

Notas de Final 20/12/2016

396225818
377320444
365901537
394469033
383327946
291628187
399356543
943400396
383300855
402488992
381790943
385033985
384094716
364332725

Notas de Final 6/12/2016

35817100 7
40502555 5
37732044 NA
36925612 4
29162818 NA
40685211 4
29609883 6
34689323 7
34689323 NA

Notas de Recuperatorio 1

37189870 3
35817100 9
40502555 5

Notas de Recuperatorio 2

39421350 4
33894712 6
37732044 7
36985795 6

Clases 2015

Parte I: Estructuras Ordenadas

Parte II: Lógica Proposicional

  • Clase del 9/9 Sintaxis de la lógica proposicional: recursión e inducción en fórmulas.
  • Clase del 16/9 Semántica de la lógica proposicional.
  • Clase del 18/9 Sistema deductivo para la lógica proposicional: reglas de conjunción, implicación y ⊥.
  • Clase del 23/9 Regla de deducción para la reducción al absurdo. El conjunto de derivaciones y manipulación de derivación.
  • Clase del 2/10 Regla de deducción para la disyunción, la negación y la doble-implicación. Adelanto de corrección y completitud.
  • Clase del 7/10 Teorema de Corrección.
  • Clases del 9/10 y 14/10 Conjuntos consistentes, consistentes maximales; existencia de valuación para ellos. Teorema de completitud.

Parte III: Lenguajes y Autómatas

Prácticos 2015

Estructuras Ordenadas

  • Práctico A.1 Ejercicios seleccionados del Capítulo 1: Relaciones.
  • Práctico A.2 Ejercicios seleccionados del Capítulo 2: Conjuntos parcialmente ordenados (posets).
  • Práctico A.3 Ejercicios seleccionados de los Capítulos 2 y 3: Isomorfismos de posets. Posets reticulados.
  • Práctico A.4 Ejercicios seleccionados del Capítulo 3: Reticulados. Es un práctico corto, ideal para ponerse al día!
  • Práctico A.5 Ejercicios seleccionados del Capítulo 3: Reticulados con complementos y reticulados distributivos.
  • Práctico A.6 Ejercicios seleccionados del Capítulo 3: Álgebras de Boole.
  • Práctico A.7 Ejercicios seleccionados del Capítulo 4: Álgebras de Boole, átomos y representación.
  • Práctico A.8 Ejercicios seleccionados del Capítulo 4, y otros: Teorema de Birkhoff.
  • Práctico A.9 Práctico de repaso

Lógica Proposicional

Lenguajes y Autómatas

Temas por clase 2013

  • Parte A: Relaciones de orden
    • Clase 14/08/2013 El concepto de relación. Propiedades de las relaciones. Relaciones de orden y de equivalencia. Relaciones de equivalencia y particiones.
    • Clase 16/08/2013 Conjuntos Parcialmente Ordenados (posets). Diagramas de Hasse. Elementos maximales, minimales, máximos y mínimos. Supremos e ínfimos. Isomorfismos de posets.
    • Clase 21/08/2013 Demostración de propiedades del isomorfismo (Lema 3.1). Definición de poset reticulado. Ejemplos de reticulados. Propiedades ecuacionales de las operaciones supremo e ínfimo.
    • Clase 23/08/2013 Reticulado como como poset y como estructura algebraica (modelo del TAD Reticulado). Isomorfismo de reticulados (como poset y como estructuras algebraicas).
    • Clase 28/08/2013 Reticulados acotados. Complemento y reticulados complementados. Distributividad y unicidad del complemento. Criterios para analizar distributividad.
    • Clase 30/08/2013 Álgebras de Boole (AB). ¿Cuándo Dn es un AB? Isomorfismo de AB. Iso de posets implica iso de AB. Leyes de De Morgan. Teorema de representación: toda AB finita es un álgebra de conjuntos.
    • Clase 04/09/2013 Teorema de representación: toda AB finita es un álgebra de conjuntos. Isomorfismo entre 2^n y un álgebra de conjuntos. Isomorfismo entre D_n y un álgebra de conjuntos. Reticulado de subconjuntos decrecientes de un poset.
    • Clase 06/09/2013 Teorema de Birkhoff. Análisis de la distributividad usando el Teorema de Birkhoff.
  • Parte B: Lógica Proposicional
    • Clase 25/09/2013 Lógica Proposicional. Sintaxis: símbolos, alfabeto, cadenas de símbolos, ejemplos. Definición inductiva del conjunto de proposiciones como conjunto de cadenas. Ejemplos. Principio de inducción sobre proposiciones. Esquema de recursión. Ejemplos. Variables de una proposición. Subfórmulas de una proposición. Substitución de una variable proposicional por una proposición. Serie de formación de una proposición. Ejemplo de prueba por inducción sobre proposiciones.
    • Clase 27/09/2013 Semántica. Tablas de verdad, asignación y valuación. Lemas de coincidencia y de sustitución. Validez lógica y consecuencia lógica. Ejemplos. Completitud funcional.
    • Clase 02/10/2013 Motivación: definición formal de demostración. Convenciones sintácticas: precedencia de operadores. Reglas de inferencia. Reglas de introducción y de eliminación. Reglas de la conjunción. Ejemplos. Reglas del implica. Ejemplos. Regla de bottom. Regla de reduction ad absurdum. Ejemplos.
    • Clase 04/10/2013 Repaso de las reglas de inferencia. Ejemplos. Definición formal de derivación. Principio de inducción sobre las derivaciones. Esquema de recusión sobre las derivaciones. Ejemplo: definición del conjunto de hipótesis de una derivación. Definición de derivación de una proposición a partir de un conjunto de hipótesis. Definición de teorema.
    • Clase 09/10/2013 Otros conectivos: reglas de inferencia, derivaciones, recursión, ejemplos. Poset asociado.
    • Clase 11/10/2013 Recursión e inducción sobre las derivaciones. Definición de la función Hip. Teorema de Corrección para la lógica proposicional.
    • Clase 16/10/2013 Teorema de completitud. Conjunto consistente e inconsistente, consistente maximal. Propiedades. Prueba de Completitud.
    • Clase 18/10/2013 PROP como poset. Antisimetría, clases de equivalencia. Buena definición. Distributividad. Complementos. PROP como álgebra de Boole.
    • Prop.hs Clase 23/10/2013 Repaso: proposiciones, asignaciones, valuaciones, tautologias, consecuencia lógica, derivaciones en Haskell.

Parciales

Otros

intrologica/main.txt · Última modificación: 2017/09/19 13:20 por mpagano