* 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

• 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

• Apunte de la primera parte: Estructuras de orden Autores: Alejandro Tiraboschi, Héctor Gramaglia
• Lema 3.1 Corrección en la demostración del Lema 3.1 del capítulo 2 del apunte de la primera parte.
• Apunte de la segunda parte: Lógica Proposicional Autor: Pedro Sánchez Terraf
• Apunte de la tercera parte: Lenguajes y Automatas (2015) Autor: Raúl Fervari y Ezequiel Orbe
• Apunte de la tercera parte: Lenguajes y Automatas (2012) Autor: Alejandro Tiraboschi, Pedro Sánchez Terraf

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

• Clase del 13/9 Introducción a lógica proposicional. Sintaxis.
• Clase del 27/9 Semántica de lógica proposicional. Completitud funcional. Noción de modelo.
• Clase del 29/9 Derivaciones con conjunción, implicación y ⊥.
• Clase del 4/10 Derivaciones con Reducción al absurdo. Repaso.
• Clase del 6/10 Derivaciones con negación, doble-implicación y disyunción. Conjunto de derivaciones.
• Clase del 11/10 (Meta-)Teorema de corrección.
• Clases del 13/10 y 18/10 (Meta-)Teorema de completitud: consistentes y consistentes maximales.

Parte III: Lenguajes y Autómatas

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

• Práctico B 1 Ejercicios correspondientes a la Sección 1.2 del apunte. Sintaxis.
• Práctico B 2 Ejercicios correspondientes a la Sección 1.3 del apunte. Semántica
• Práctico B 3 Ejercicios correspondientes a la Sección 1.4 y 2.1 del apunte. Deducción y derivación.
• Práctico B 4 Ejercicios correspondientes a la Sección 2.1 del apunte. Más derivación.
• Práctico B 5 Ejercicios correspondientes a la Sección 2.2-4 del apunte.

Parte III: Lenguajes y Autómatas

• 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.

• 23 de Septiembre: sintaxis de la lógica proposicional. Recursión e inducción en proposiciones.
• 28 de Septiembre: semántica de las proposiciones. Asignaciones, validez y consecuencia lógica.
• 5 de Octubre: Deducción natural. Reglas para conjunción, implicación y bottom.
• 7 de Octubre: Deducción natural. Reducción al absurdo. Definición del conjunto de derivaciones.
• 12 de Octubre: Deducción natural. Reglas para disyunción, negación y doble implicación. Esquema de prueba del meta-teorema de corrección.
• 14 de Octubre: Paro Docente. En contra del recorte presupuestario. En defensa del salario docente.
• 19 de Octubre: Teorema de corrección.
• 21 de Octubre: Teorema de completitud. Consistentes, consistentes maximales. Criterio de consistencia y su vuelta.

• Clase del 26/10 Autómatas Finitos Determinísticos.
• Clases del 28/10 y 02/11 Autómatas Finitos No Determinísticos.
• Clase del 9/11 Expresiones Regulares.
• Clase del 11/11 Gramáticas Regulares.
• Clase del 16/11 Pumping Lemma - Gramáticas Libres de Contexto.
• Clase del 18/11 Autómatas con Pila.

• 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

• 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í).

• Práctico C.1 Autómatas Finitos Determinísticos
• Práctico C.2 Autómatas Finitos No Determinísticos
• Práctico C.3 Expresiones Regulares
• Práctico C.4 Gramáticas Regulares
• Práctico C.5 Pumping Lemma - Gramáticas Libres de Contexto
• Práctico C.6 Autómatas con Pila

• Notas del Parcial 1
• Notas del Parcial 2

• Filminas de la clase del 12/8
• Filminas de la clase del 14/8
• Filminas de la clase del 19/8
• Filminas de la clase del 21/8
• Filminas de la clase del 26/8
• Filminas de la clase del 28/8
• Filminas de las clases 2/9 y 4/9

• 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.

• Clase del 16/10 Autómatas Finitos Determinísticos.
• Clases del 21/10 y 23/10 Autómatas Finitos No Determinísticos.
• Clase del 28/10 Expresiones Regulares.
• Clase del 04/11 Gramáticas Regulares.
• Clase del 06/11 Pumping Lemma y Gramáticas Libre de Contexto.
• Clase del 11/11 Autómatas con Pila.

• 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

• Práctico B.1 Sintaxis y semántica
• Práctico B.2 Semántica, deducción y derivación
• Práctico B.3 Deducción Natural (Parte II)
• Práctico B.4 Conjuntos consistentes

• Práctico C.1 Autómatas Finitos Determinísticos
• Práctico C.2 Autómatas Finitos No Determinísticos
• Práctico C.3 Expresiones Regulares y Gramáticas Regulares
• Práctico C.4 Pumping Lemma - Gramáticas Libres de Contexto

• 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.

Ejemplo de examen