• Author / Uploaded
• Sergio Derzü

• Categories
• Prueba matemática
• Ciencias de la Computación
• Álgebra de Boole
• Proposición
• Lógica de primer orden

Citation preview

Universidad Cat´ olica San Pablo Escuela Profesional de Ciencia de la Computaci´ on SILABO CS1D1. Estructuras Discretas I (Obligatorio) 2019-I 1. DATOS GENERALES 1.1 CARRERA PROFESIONAL 1.2 ASIGNATURA ´ 1.3 SEMESTRE ACADEMICO 1.4 PREREQUISITO(S) ´ 1.5 CARACTER 1.6 HORAS ´ 1.7 CREDITOS

: : : : : : :

Ciencia de la Computaci´on CS1D1. Estructuras Discretas I 1er Semestre. Obligatorio 2 HT; 4 HP; 4

2. DOCENTE Dr. Graciela Lecireth Meza Lov´ on Dr. Ciencia de la Computaci´ on, Universidad Nacional San Agust´ın, Per´ u, 2016. Mag. Ciencia de la Computaci´ on, UFMS-MS, Brasil, 2007. Prof. Bachiller en Ingenier´ıa Inform´ atica, Universidad Cat´olica San Pablo, Per´ u, 2004. Mg. Jenny Linet Copara Zea Mag. Ciencia de la Computaci´ on, Universidad Cat´olica San Pablo, Per´ u, 2017.

´ DEL CURSO 3. FUNDAMENTACION Las estructuras discretas proporcionan los fundamentos te´oricos necesarios para la computaci´on. Dichos fundamentos no son s´olo u ´tiles para desarrollar la computaci´ on desde un punto de vista te´orico como sucede en el curso de teor´ıa de la computaci´on, sino que tambi´en son u ´tiles para la pr´actica de la computaci´on; en particular se aplica en ´areas como verificaci´on, criptograf´ıa, m´etodos formales, etc. 4. SUMILLA 1. L´ogica b´asica2. T´ecnicas de demostraci´ on3. Funciones, relaciones y conjuntos4. Fundamentos de L´ogica Digital 5. OBJETIVO GENERAL Aplicar adecuadamente conceptos de la matem´atica finita (conjuntos, relaciones, funciones) para representar datos de problemas reales. Modelar situaciones reales descritas en lenguaje natural, usando l´ogica proposicional y l´ogica de predicados. Aplicar el m´etodo de demostraci´ on m´ as adecuado para determinar la veracidad de un enunciado. Construir argumentos matem´ aticos correctos. Interpretar las soluciones matem´ aticas para un problema y determinar su fiabilidad, ventajas y desventajas. ´ Expresar el funcionamiento de un circuito electr´onico simple usando conceptos del Algebra de Boole.

1

´ A LA FORMACION ´ PROFESIONAL Y FORMACION ´ GENERAL 6. CONTRIBUCION Esta disciplina contribuye al logro de los siguientes resultados de la carrera: a) Aplicar conocimientos de computaci´ on y de matem´aticas apropiadas para la disciplina. (Usar) i) Utilizar t´ecnicas y herramientas actuales necesarias para la pr´actica de la computaci´on. (Evaluar) j) Aplicar la base matem´ atica, principios de algoritmos y la teor´ıa de la Ciencia de la Computaci´on en el modelamiento y dise˜ no de sistemas computacionales de tal manera que demuestre comprensi´on de los puntos de equilibrio involucrados en la opci´ on escogida. (Usar)

´ 7. COMPETENCIAS ESPEC´ IFICAS DE COMPUTACION Esta disciplina contribuye a la formaci´ on de las siguientes competencias del ´area de computaci´on (IEEE): C1. La comprensi´ on intelectual y la capacidad de aplicar las bases matem´aticas y la teor´ıa de la inform´atica (computer science).⇒ Outcome a C20. Posibilidad de conectar la teor´ıa y las habilidades aprendidas en la academia a los acontecimientos del mundo real que explican su pertinencia y utilidad.⇒ Outcome i,j

8. CONTENIDOS UNIDAD 1: L´ ogica b´ asica(14) Competencias: C1,C20 CONTENIDO

OBJETIVO GENERAL

L´ogica proposicional.

Convertir declaraciones l´ogicas desde el lenguaje informal a expresiones de l´ogica proposicional y de predicados[Usar]

Conectores l´ogicos. Tablas de verdad.

Aplicar m´etodos formales de simbolismo proposicional y l´ogica de predicados, como el c´alculo de la validez de formulas y c´alculo de formas normales[Usar]

Forma normal (conjuntiva y disyuntiva) Validaci´on de f´ ormula bien formada.

Usar reglas de inferencia para construir demostraciones en l´ogica proposicional y de predicados[Usar]

Reglas de inferencia proposicional (conceptos de modus ponens y modus tollens)

Describir como la l´ogica simb´olica puede ser usada para modelar situaciones o aplicaciones de la vida real, incluidos aquellos planteados en el contexto computacional como an´alisis de software (ejm. programas correctores ), consulta de base de datos y algoritmos[Familiarizarse]

Logica de predicados: • Cuantificaci´ on universal y existencial Limitaciones de la l´ ogica proposicional y de predicados (ej. problemas de expresividad)

Aplicar demostraciones de l´ogica formal y/o informal, pero rigurosa, razonamiento l´ogico para problemas reales, como la predicci´on del comportamiento de software o soluci´on de problemas tales como rompecabezas[Usar] Describir las fortalezas y limitaciones de la l´ogica proposicional y de predicados[Usar] Lecturas: [Rosen, 2007], [Grimaldi, 2003]

2

UNIDAD 2: T´ ecnicas de demostraci´ on(14) Competencias: C1,C20 CONTENIDO

OBJETIVO GENERAL

Nociones de implicancia, equivalencia, conversi´on, inversa, contrapositivo, negaci´ on, y contradicci´on

Identificar la t´ecnica de demostraci´on utilizada en una demostraci´on dada[Evaluar]

Estructura de pruebas matem´ aticas.

Describir la estructura b´asica de cada t´ecnica de demostraci´on (demostraci´on directa, demostraci´on por contradicci´on e inducci´on) descritas en esta unidad[Usar]

Demostraci´on directa. Refutar por contraejemplo.

Aplicar las t´ecnicas de demostraci´on (demostraci´on directa, demostraci´on por contradicci´on e inducci´on) correctamente en la construcci´on de un argumento solido[Usar]

Demostracci´ on por contradicci´ on. Inducci´on sobre n´ umeros naturales. Inducci´on estructural.

Determine que tipo de demostraci´on es la mejor para un problema dado[Evaluar]

Inducci´on leve y fuerte (Ej. Primer y Segundo principio de la inducci´ on)

Explicar el paralelismo entre ideas matem´aticas y/o inducci´on estructural para la recursi´on y definir estructuras recursivamente[Familiarizarse]

Definiciones matem´ aticas recursivas. Conjuntos bien ordenados.

Explicar la relaci´on entre inducci´on fuerte y d´ebil y dar ejemplos del apropiado uso de cada uno[Evaluar] Enunciar el principio del buen-orden y su relaci´on con la inducci´on matem´atica[Familiarizarse] Lecturas: [Rosen, 2007], [Epp, 2010], [Scheinerman, 2012] UNIDAD 3: Funciones, relaciones y conjuntos(13) Competencias: C1,C20 CONTENIDO

OBJETIVO GENERAL

Conjuntos:

Explicar con ejemplos la terminolog´ıa b´ asica de funciones, relaciones y conjuntos[Evaluar]

• Diagramas de Venn

Realizar las operaciones asociadas con conjuntos, funciones y relaciones[Evaluar]

• Uni´on, intersecci´ on, complemento • Producto Cartesiano

Relacionar ejemplos pr´acticos para conjuntos funciones o modelos de relaci´on apropiados e interpretar la asociaci´on de operaciones y terminolog´ıa en contexto[Evaluar]

• Potencia de conjuntos • Cardinalidad de Conjuntos finitos Relaciones: • Reflexividad, simetria, transitividad • Relaciones equivalentes, ordenes parciales Funciones: • Suryecciones, inyecciones, biyecciones • Inversas • Composici´ on Lecturas: [Grimaldi, 2003], [Rosen, 2007]

3

UNIDAD 4: Fundamentos de L´ ogica Digital (19) Competencias: C1,C20 CONTENIDO

OBJETIVO GENERAL

´ Ordenes Parciales y Conjuntos Parcialmente Ordenados.

´ Explicar la importancia del Algebra de Boole como unificaci´on de la Teor´ıa de Conjuntos y la L´ogica Proposicional [Familiarizarse].

Elementos extremos de un Conjunto Parcialmente Ordenado.

Demostrar enunciados usando el concepto de ret´ıcula y sus propiedades[Evaluar].

Ret´ıculas: Tipos y propiedades.

Explicar la relaci´on entre ret´ıcula y conjunto parcialmente ordenado [Familiarizarse].

´ Algebras Booleanas Funciones y expresiones Boolenas

Demostrar para una terna formada por un conjunto y dos operaciones internas, si cumple las propiedades ´ de una Algebra de Boole [Evaluar].

Representaci´ on de Funciones Booleanas: Forma Normal Disyuntiva y Conjuntiva

Representar una funci´on booleana en sus formas can´onicas[Usar].

Puertas L´ogicas Minimizaci´on de funciones booleanas.

Representar una funci´on booleana como un circuito booleano usando puertas l´ogicas [Usar]. Minimizar una funci´on booleana [Usar].

Lecturas: [Rosen, 2007], [Grimaldi, 2003] 9. METODOLOG´IA El profesor del curso presentar´ a clases te´ oricas de los temas se˜ nalados en el programa propiciando la intervenci´on de los alumnos. El profesor del curso presentar´ a demostraciones para fundamentar clases te´oricas. El profesor y los alumnos realizar´ an pr´ acticas. Los alumnos deber´ an asistir a clase habiendo le´ıdo lo que el profesor va a presentar. De esta manera se facilitar´a la comprensi´on y los estudiantes estar´ an en mejores condiciones de hacer consultas en clase.

10. EVALUACIONES Evaluaci´ on Permanente 1 : 20 % Examen Parcial : 30 % Evaluaci´ on Permanente 2 : 20 % Examen Final : 30 %

Referencias [Epp, 2010] Epp, S. S. (2010). Discrete Mathematics with Applications. 4 ed. edition. [Grimaldi, 2003] Grimaldi, R. (2003). Discrete and Combinatorial Mathematics: An Applied Introduction. Pearson, 5 ed. edition. [Rosen, 2007] Rosen, K. H. (2007). Discrete Mathematics and Its Applications. 7 ed. edition.

4

[Scheinerman, 2012] Scheinerman, E. R. (2012). Mathematics: A Discrete Introduction. 3 ed. edition.

5