* Cursado: Segundo cuatrimestre de 2019

* Profesores: Mariana Badano, Héctor Gramaglia, Miguel Pagano

* Ayudantes: María Clara Gorín, Andrés Saravia y Matías Steinberg.

Programa de la materia correspondiente al año 2019

Anuncio Exámen final del 3 de agosto de 2020

* Coloquio

* Notas del Primer parcial

* Notas del Primer Parcial - Profesorado

* Notas del Segundo parcial

* Notas del Segundo Parcial - Profesorado

* Notas Examen Final 4 de diciembre de 2019

* Notas Examen Final 4 de diciembre de 2019

• 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.
• Parte 2: Lógica. A cargo de Mariana Badano.
• Parte 3: Lenguajes y Autómatas. A cargo de Miguel Pagano.
• Primer Parcial: 18 de setiembre
• Segundo Parcial: 18 de octubre
• Recuperatorio: 19 de noviembre
• Coloquio: 19 de noviembre
• 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.

• 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 Clases completas

Parte II: Lógica Proposicional Clases completas

Parte III: Lenguajes Regulares y Autómatas

• Autómatas Finitos Deterministas
• Autómatas Finitos No Deterministas Determinización y eliminación de transiciones ε.
• Expresiones Regulares Junto con Pumping Lemma.
• Expresiones Regulares Equivalencia entre AFD y ER.
• Gramáticas Libres de Contexto

Parte I: Estructuras Ordenadas

• Práctico A.1 Relaciones de equivalencia
• Práctico A.2 Relaciones de orden. Minimales, maximales, ínfimos y supremos.
• Práctico A.3 Isomorfismo de poset y posets reticulados.
• Práctico A.4 Reticulados, subreticulados, complementos.
• Práctico A.5 Reticulados complementados y distributivos.
• Práctico A.6 Subreticulados. Álgebras de Boole.
• Práctico A.7 Teorema de Birkhoff. Reticulado producto.
• Práctico complementario

Parte II: Lógica Proposicional

• Práctico B.1 Sintaxis y semántica
• Práctico B.2 Semántica
• Práctico B.3 Semántica, deducción y derivaciones.
• Práctico B.4 Derivaciones y teorema de corrección.
• Práctico B.5 Completitud: conjuntos consistentes maximales, cerrados por derivaciones.

Parte III: Lenguajes Regulares y Lenguajes Libres de Contexto

• Gramáticas Libres de Contexto

Parte I: Estructuras Ordenadas Clases completas

• Miércoles 12. Concepto de Relación. Relaciones de equivalencia y de orden. Caracterización de las relaciones de equivalencia. Diagramas de Hasse para representar relaciones de orden. Conjuntos parcialmente ordenados.
• Viernes 14. 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. Poset reticulado. Reticulado como estructura algebraica. Reticulado de divisores. Reticulado de subconjuntos.
• Miércoles 12/09. Isomorfismo de reticulados. Reticulados acotados y complementados. Problema de la existencia de más de un complemento: reticulados M3 y N5. Desigualdades distributivas. Reticulados distributivos.
• Viernes 19/09. Isomorfismo de reticulados. Reticulados acotados y complementados. Problema de la existencia de más de un complemento: reticulados M3 y N5. Desigualdades distributivas. Reticulados distributivos. Caracterización de los reticulados distributivos.
• Miércoles 26. Álgebras de Boole. Leyes de De Morgan. Problema: ¿todas las álgebras de Boole son álgebras de un conjunto? Teorema de Representación para las Álgebras de Boole.
• Viernes 28. Reticulado de subconjuntos decrecientes de un poset. Teorema de Birkhoff. Caso Álgebras de Boole.

Parte III: Autómatas y Lenguajes

• Miércoles 31/10. Autómatas Finitos Determinísticos (DFA) Slides
• Viernes 2/11. Repaso de DFA y Autómatas Finitos No-Determinísticos (AFN).Filminas
• Viernes 9/11. Autómatas Finitos No-determinísticos y NFA con transiciones-ε Filminas
• Miércoles 14/11. Autómatas Finitos No-determinísticos con transiciones-ε, Pumping Lemma y Expresiones Regulares. Filminas
• Viernes 16/11. Paro.
• Miércoles 21/11. Equivalencia entre Autómatas Finitos y Expresiones Regulares. Filminas
• Viernes 23/11. Filminas Gramáticas libres de contexto.

Parte I: Estructuras Ordenadas

• Miércoles 12/09. Práctico A.1 Relaciones de equivalencia.
• Viernes 14/09. Práctico A.2 Posets.
• Viernes 14/09. Práctico A.3 Isomorfismos de posets. Posets reticulados.
• Miércoles 19/09. Práctico A.4 Reticulados.
• Viernes 21/09. Práctico A.5 Reticulados complementados y distributivos.
• Miércoles 26/09. Práctico A.6 Álgebras de Boole.
• Viernes 28/09. Práctico A.7 Teorema de Birkhoff para reticulados distributivos.

Parte II: Lógica Proposicional

• Miércoles 10/10. Práctico B.1 Sintaxis y Semántica.
• Viernes 12/10. Práctico B.2 Sintaxis y Semántica.
• Miércoles 17/10. Práctico B.3 Semántica, deducción y derivación.
• Práctico B.4 Deducción y derivaciones.
• Práctico B.5 Conjuntos Consistentes; completitud y corrección.

Parte III: Autómatas y Lenguajes

• Miércoles 31/10. Práctico C.1 Autómatas Finitos Determinísticos (DFA).
• Práctico C.2 NFA y Determinización.
• Práctico C.3 Expresiones Regulares.
• Práctico C.4 Decidir si ciertos lenguajes son regulares o no.

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

• Clase del 20/10 Autómatas Finitos Determinísticos.
• Clase del 25/10 y 1/11 Autómatas Finitos No Determinísticos.
• Clase del 01/11 y 03/11 Expresiones Regulares.
• Clase del 08/11 Gramáticas Regulares.
• Clase del 10/11 Pumping Lemma - Gramáticas Libres de Contexto.
• Clase del 15/11 Autómatas con Pila.

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

• Práctico C.1 Ejercicios seleccionados de la sección 2 del apunte: Autómatas Finitos Determinísticos.
• Práctico C.2 Ejercicios seleccionados de la sección 3 del apunte: Autómatas Finitos No Determinísticos.
• Práctico C.3 Ejercicios seleccionados de la sección 3.4 del apunte: Expresiones Regulares.
• Práctico C.4 Ejercicios seleccionados de la sección 4 del apunte: Gramáticas Regulares.
• Práctico C.5 Ejercicios seleccionados de las secciones 5.1 y 5.2 del apunte: Pumping Lemma - Gramáticas Libres de Contexto.
• Práctico C.6 Ejercicios seleccionados de la sección 5.5 del apunte: Autómatas con Pila.

• 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

Otro

Otro

Otro