#+title: Resumen 2 - Mates Discreta

* Algebra booleana
Es un sistema en el cual solo se pueden tomar dos valores 1 o 0 y 
basa su funcionamiento en el uso de compuertas logicas las cuales pueden ser:

- AND,  
  Necesita que ambos terminos son 1 para dar un 1. Se describe con un (*) o un $\land$
  
- OR,  
  Cuando una de sus entradas es 1 da 1. E representado con un (+) o un $\lor$
  
- NOT,  
  Invierte el valor del termino. puede ser representado con un $\overline{x}$ o un $\lnot$

- Xor,  
  Si bien la profe dijo que no lo va a tomar lo explico ahora. Solo da 1 cuando una entrada es positiva. Representado con un $\oplus$

* Ordenes 
Una funcion booleana es de orden n dependiendo de la cantidad de entradas que posea, es decir, si tiene 4 entradas es de cuarto orden.

* Variable bool
Este es un dato que puede variar entre los valores del siguiente conjunto, { 0, 1 }. Y un vector de n variables se representaria de esta forma (x_1, x_2, x_3, ..., x_n). 

* Funcion bool
Una funcion le asigna un valor a cada entrada. ej, f(x_1, x_2, ..., x_n).

* Tablas 
Tambien conocidas como tablas de la verdad son representaciones de todos los valores posibles con las variables dadas y todos los resultados posibles de la funcion booleana.

Ejemplo de una tabla

|------|--------|-----|
| #    | x*y    | rta |
|------|--------|-----|
| 0,0  | 0 * 0  | 0   |
| 0,1  | 0 * 1  | 0   |
| 1,0  | 1 * 0  | 0   |
| 1,1  | 1 * 1  | 1   | 
|------|--------|-----|

* Formas Normales
** FND
*Forma Normal Disyuntiva*, consiste de disyuncio (OR) de operaciones AND. un ejemplo:  

\begin{center}
$f(a, b, c) = (a \land b \land \lnot c) \lor (\lnot a \land b\land \lnot c) \lor (\lnot a \land \lnot b \land \lnot c)$
\end{center}

** FNC
Conocida como *Forma Natural Conjuntiva* Consiste de operaciones AND unidas por operaciones OR.  

\begin{center}
$f(a, b, c) = (a \land b \land c ) \lor (\lnot a \land b \land c ) \lor (a \land \lnot b \land \lnot c)$
\end{center}

* Congruencia
Por definicion la congruencia son varios terminos que son consistentes entre sí, para matematicas discretas serian los terminos que al calcular un mismo modulo (resto de divicion) tienen el mismo resto.  

Por ejemplo:  
(1, 7, 13) modulo 6 tienen el mismo resto, por lo que son congruentes entre sí.  

*NOTA:* Es fácil notar que los numeros que son congruentes entre si pueden ser representados como un offset constante (C) de un multiplo del valor modulo. Para el caso anterior calculé los numeros congruentes como: $f(x, C) = x*6 + C$ donde C es 1.

Veamos un ejercicio ejemplo:

#+begin_quote
La idea es encontrar valores de x que, cuando los multiplicás por 5, el resultado tenga un resto de 3 cuando lo dividís por 9. Es decir, querés ver qué múltiplos de 5, al sumarle o restarle algo, te dan un número que cae en la clase de resto 3, si lo mirás módulo 9.
#+end_quote

Lo que hay que encontrar es un numero que al ser multiplicado por 5 nos dé un numero que restado 3 sea multiplo de 9. Es decir, el numero más el 3 tiene que ser multiplo de 5 pero sin el 3 de 9.
9 + 3 = 12 [no multiplo 5].   
18 + 3 = 21   
27 + 3 = 30  [YESSS mul 5 al fin]   

y como 30 / 5 = 6 entonces 6 es el primer resultado.

encontremos el segundo

36 + 3 = 39  
45 + 3 = 48  
54 + 3 = 57  
 3 + 3 = 66  

Además todos los numeros que son menores que el numero del modulo pertenecen a un grupo de resto.

* Teorema del resto chino
haganse un favor y miren este video:  

[[https://www.youtube.com/watch?v=v8XsnE1_u70]]
