Lógica

Pronto se darán cuenta que la mayoría del contenido en esta parte del curso tendrá que ver con poder demostrar que algún concepto matemático o computacional es cierto o falso. Para eso, necesitamos la lógica.

Enunciados, enunciados compuestos

Capítulos

• Goodaire: 1.1

• Rosen: 1.1

Definiciones

• enunciado: Un enunciado es una oración completa a la cual podemos adjudicarlo un valor de "cierto" o "falso".

• enunciado compuesto: Un enunciado compuesto es un enunciado creado con dos otros enunciados conectados con "y" o "o" (literalmente las palabras "y" o "o").

• implicaciones: Una implicación es un enunciado de la forma "p implica a q" donde p se llama la hipótesis y q se llama la conclusión. Solo es falso cuando la hipótesis es cierta y la conclusión es falsa.

• converso: El converso de una implicación como "p implica a q" es un enunciado de la forma "q implica a p". Esto NO es lo mismo que el enunciado original, en general.

• doble implicación: Una doble implicación es un enunciado de la forma "p implica a q y q implica a p".

• negación: La negación de un enunciado como "p" es un enunciado que dice "p no es cierto".

• contrapositivo: El contrapositivo de una implicación como "p implica a q" es el enunciado "q no es cierto implica a p no es cierto". Esto SI es lo mismo que el enunciado original, siempre.

Se utilizan los siguientes simbolos para conectivos logicos:

Ejercicios

• Cual de los siguientes es un enunciado?

  • El perro es un gato.

  • A Daddy Yankee y Bad Bunny les gusta Vico-C.

  • El sol es una bola de fuego.

• Crea un enunciado compuesto con los enunciados anteriores.

• Crea una implicación utilizando el enunciado que creaste.

• Con esa implicación:

  • escribe su negación

  • escribe su converso

  • escribe su contrapositivo

Algo que quisiera resaltar en esta parte es que hay muchas maneras de escribir una implicación utilizando lenguaje. El enunciado "p implica a q" también puede ser igualmente escrito como:

• q si p.

• p solo si q.

• Si p, entonces q.

• Si p, q.

• Por p, tenemos q.

Para mas informacion, pueden leer:

Predicados y cuantificadores

Capítulos

• Goodaire: 1.1

• Rosen: 1.3, 1.4

Definiciones

• predicado: Un predicado es un enunciado cuyo valor de verdad depende de una variable. Cuando esa variable toman un valor concreto, podemos decir si el enunciado es cierto o falso. También es llamado un enunciado abierto.

• cuantificador universal: Un cuantificador universal es un enunciado que quiere decir que es cierto para todo valor que pueda tomar su argumento.

• cuantificador existencial: Un cuantificador existencial es un enunciado que quiere decir que es cierto para por lo menos 1 valor que pueda tomar su argumento.

Ejercicios:

• Escribe un predicado.

• Determina cuales de los siguientes tienen cuantificadores universales, existenciales, ambos o ninguno:

  • Todos los enteros son positivos.

  • El perro es un gato.

  • Cualquier numero par es un múltiplo de 2.

  • Para todo entero a, existe un entero r tal que a = 1 + r.

Ivelisse ha puesto varias tareas con ejercicios que tratan sobre como manipular cuantificadores o simplificarlos, también hay videos con explicaciones muy buenas sobre estos.

Equivalencias

Capítulos:

• Goodaire: 1.3, 1.4

• Rosen: 1.2

Definiciones:

• equivalencia: Un enunciado p es equivalente a un enunciado q si toman el mismo valor de verdad en todo caso.

Las equivalencias se escriben con el símbolo especial:

• tabla de la verdad: Una tabla de la verdad es una tabla que se utiliza para enumerar todos los posibles valores que puede tomar un enunciado.

• ley De Morgan: La ley De Morgan dice las siguientes equivalencias:

• forma normal: La forma normal de un enunciado es un enunciado de la forma "(p1 y p2 y ... p) o (q1 y q2 y ... q) o ... (r1 y r2 y ... r)" que es equivalente al enunciado original. Para crear este enunciado, se hace la tabla de la verdad, y cada paréntesis representa una fila que tiene como resultado un valor de verdad cierto.

Ejercicios:

• Haz la tabla de la verdad para el siguiente enunciado:

• Haz la tabla de la verdad para el siguiente enunciado:

• Verifica si el enunciado anterior es equivalente al enunciado:

• Escribe la forma normal del enunciado anterior y después utiliza las propiedades de lógica para simplificarlo.

Reglas de inferencia

Capítulos:

• Goodaire: 1.5

• Rosen: 1.5

Definiciones:

• regla de inferencia:

Ejercicios:

• a

Demostraciones

Las demostraciones son y lo seguirán siendo el pan de cada dia hasta que se acabe el curso. Repasen esto bien!

Pruebas directas

Capítulos:

• Goodaire: 1.2

• Rosen: 1.6

Definiciones:

• proposición:

• lemma:

• teorema:

• corolario:

• axioma:

Ejercicios:

• a

Pruebas por casos y contrapositivo

Capítulos:

• Goodaire: 1.2

• Rosen: 1.6

Definiciones:

• enunciado falso:

• caso:

Ejercicios:

• a

Contradiccion y construccion

Capítulos:

• Goodaire: 1.2

• Rosen: 1.6

Definiciones:

• prueba por contradiccion:

• prueba por construccion:

Ejercicios:

• a

Inducción

Esto técnicamente es una estrategia de demostración y por eso debería estar en la sección anterior. Pero, es un tema que le da mucho trabajo a muchos estudiantes. Asi que aquí lo resalto para ustedes.

Capítulos:

• Goodaire: 5.1

• Rosen: 4.1, 4.2

Definiciones:

• Principio del buen orden:

• caso base:

• hipótesis inductiva:

• conclusion inductiva:

• inducción:

Ejercicios:

• a

Divisibilidad

La divisibilidad esta atada a muchas partes de la ciencia de cómputos como los números binarios y las estructuras de datos. Sera importante estudiar esto y sus propiedades.

Divisibilidad

Capítulos:

• Goodaire: 4.2

• Rosen: 3.4, 3.5

Definiciones:

• divisibilidad:

• divisor común mayor:

• múltiplo común menor:

• algoritmo de Euclides:

Ejercicios:

• a

Algoritmo de la division

Capítulos:

• Goodaire: 4.1

• Rosen: 3.4

Definiciones:

• algoritmo de la division:

Ejercicios:

• a