Federico Valentin Andrade | Legajo 2033665
Operadores Proposicionales
Leyes Lógicas
Nombre Formula Nombre Formula
Involución Identidad
Conmutatividad Dominación
Asociatividad Bicondicional
Distributividad Condicional
Idempotencia Tercero excluido
De Morgan Simplificación
Absorción Adición
Reglas de inferencia
Regla Nombre Regla Nombre
Modus Ponens Adición
Modus Tollens Simplificación
Silogismo Hipotético Conjunción
Silogismo Disyuntivo Resolución
Bicondicionales
Particularización Universal Particularización Existencial
Si a es genérico Generalización Universal Generalización Existencial
Federico Valentin Andrade | Legajo 2033665
Relaciones de conjuntos
Propiedades
Operaciones entre conjuntos
Propiedades
Propiedad Definición Propiedad Definición
Involución Neutro
Conmutatividad Absorbente
Asociatividad Absorción
Distributividad Equivalencia de la diferencia
Idempotencia Complementación
Leyes de De Morgan
Particiones
Producto Cartesiano
Propiedades
Inducción
ó
1. Paso base:
2. Paso inductivo:
(↑ Hipótesis inductiva) (↑ Tesis Inductiva)
Federico Valentin Andrade | Legajo 2033665
Formalización de la ecuación de cociente y resto
Relación de divisibilidad
Algoritmo de Euclides Matricial
Primero se coloca la matriz identidad de orden 2, y en una tercer columna los dos números enteros, siendo el mayor el de la primera fila. De
ahí se van obteniendo nuevas filas restando el mayor múltiplo posible del que sea menor al ante-ultimo hasta llegar a un valor nulo, tal que
el ultimo valor antes del nulo es el valor del máximo común divisor. Y también se puede ver que, dados los dos primeros elementos de la
ultima fila de la matriz, , y los números que se querían calcular originalmente, (siendo mayor que ), se da que:
Teorema de Bezaut
1.
2.
3.
4.
siendo el resto de la división de por .
Si se da el teorema de Bezaut, entonces y son co-primos entre ellos.
Si entonces también.
Federico Valentin Andrade | Legajo 2033665
Relaciones
Reglas y clasificaciones de funciones
Matrices
Propiedades
Matrices de relaciones
Propiedades de relaciones en un conjunto
Relación de equivalencia
Toda relación es una relación de equivalencia si cumple con tres propiedades: La reflexiva, la simétrica, y la transitiva.
Una clase de equivalencia es un subconjunto del dominio tal que todos los elementos del conjunto se relacionan con este elemento:
Un conjunto cociente es el conjunto de indices de una relación de equivalencia:
Congruencia
y
| (Regla de existencia)
(Regla de unicidad)
| Si cumple ambas es biyectiva.
y
Idempotencia: y
Conmutatividad: y
Asociatividad: , y
Distributividad: y
| | |
" es congruente con módulo "
Federico Valentin Andrade | Legajo 2033665
Orden
Las relaciones de orden son un tipo de relación especial que se da únicamente cuando la relación es reflexiva, anti-simétrica, y transitiva.
Las relaciones de orden también se denominan de orden amplio. Y también hay una sub-categoría denominada orden estricto. Las relaciones de orden amplio buscan se representan
por el símbolo , por ejemplo .
Dadas dos relaciones de orden y , se puede generar la relación del conjunto tal que dados
Dado , esta bien ordenado todo subconjunto de tiene primer elemento. Si un conjunto esta bien ordenado entonces también es de orden total.
Sea un conjunto ordenado y , se denomina a una cota superior de , y a una cota inferior de
.
También se denominan al conjunto de cotas superiores e inferiores como conjunto mayorante y minorante respectivamente, con la menor de las cotas superiores llamada supremo y
la mayor de las cotas inferiores llamada ínfimo. Si este supremo o ínfimo pertenecen a , entonces se nombran máximo de y mínimo de respectivamente.
Divisibilidad
Redes
Se reduce e .
Dada una red y sus maximales y minimales y respectivamente, se denomina al complemento de un elemento como tal que y , donde
por ejemplo es complemento de y viceversa. Una red es complementada si todo elemento tiene al menos un complemento.
Dada una red , se dice que la red es distributiva y .
Algebras de Boole
Dada una álgebra de Boole , ambas operaciones tienen que cumplir: Ser operaciones binarias cerradas en | Ser conmutativas | Ser distributivas entre sí | Tener elementos
neutros y respectivamente
Propiedades
Dada la AdB. (A, , )
Dada una álgebra de Boole, un subconjunto de dicha álgebra es una sub-álgebra si y solo si esta es una álgebra de Boole que mantiene los mismos supremos, ínfimos y elementos
neutros.
Dadas dos álgebras de Boole, un homomorfismo se genera en forma de una función tal que:
Las funciones booleanas son funciones de tipo siendo ( ) un álgebra de Boole (usualmente se utilizar ( )).
con siendo el minimal.á
Dado un numero natural , se define a como el conjunto de divisores del número tal que es un conjunto ordenado.
Superior Semirretículo: es superior semirretículo , osea, existe un supremo para todo par de elementos de .
Inferior Semirretículo: es inferior semirretículo .í
í
Si y .
Si y y .
Operación Cerrada: Una operación es cerrada en el conjunto .
Operación Conmutativa: Una operación es conmutativa en el conjunto .
Operación Idempotente: Una operación es idempotente en el conjunto .
Elemento Neutro: es un elemento neutro de .
Elemento absorbente: es un elemento absorbente de .
Los elementos y son únicos. | Todo elemento tiene un único complemento. | Todo elemento es idempotente. | Los elementos neutros se complementan mutuamente.
Todo elemento es involutivo. | El elemento neutro para es y es absorbente para . | El elemento neutro para es y es absorbente para .
Se cumple la absorción. | Se cumple la asociatividad en ambas funciones.
| |
|
Esta función es biyectiva, también llamado isomorfismo, si ambos conjuntos tienen cardinales iguales.
una AdB finita es isomorfa al conjunto de partes de sus átomos.
Minitérmino: se define a un término en el que se hallan todas las variables o sus complementos multiplicados entre si. (P.e.: es un minitérmino).
Maxitérmino: un factor de todas las variables o sus complementos sumados entre sí.
Forma normal disyuntiva: Una función booleana esta expresada en forma normal disyuntiva cuando se expresa como la suma de minitérminos.
Forma normal conjuntiva: Una función booleana esta expresada en forma normal conjuntiva cuando se expresa como el producto de maxitérminos.
Una función booleana se puede transformar a esta forma mediante las propiedades de las expresiones booleanas, o directamente sumando cada minitérmino cuya
imagen en la función de 1.
Similarmente esta forma es alcanzable tnato por propiedades o por tomar los términos cuya función de 0.
Federico Valentin Andrade | Legajo 2033665
Orden: Cuantos valores iniciales se deben conocer a priori.
Grado: El mayor exponente de cualquiera de los valores de la sucesión ( ).
Ecuación Homogénea: Si
Ecuación con coeficientes constantes: Si para toda variable, ninguno es multiplicado por .
Solución de lineal homogénea orden 1 :
Solución de lineal homogénea orden 2 :
Solución de recurrencias lineales no homogéneas de orden 1:
Soluciones particulares
Solución particular probable
Polinomio completo de grado
Si ninguna funciona elevar por .
Si no se recibe una función del tipo intentar acomodar todos los valores para esta cuestión.
Fibonacci:
Solución:
pasar a
resolver las raices de
resolver considerando los datos iniciales
Federico Valentin Andrade | Legajo 2033665
Un sistema completo de enteros incongruentes módulo es un conjunto formado por un elemento de cada clase de
equivalencia de la congruencia módulo . Un sistema reducido de restos módulo es un conjunto de números menores o
iguales a , co-primos con .
La función de Euler devuelve el cardinal del sistema reducido de restos módulo dado dicho valor.
Teoremas de Fermat y Euler
Ecuaciones lineales de congruencia
Si es primo entonces .
Dados un número primo y uno no primo,
Si
Si .
Si .
Dado , si entonces la solución es: .
Si entonces la solución existe y tiene soluciones
Si .
Federico Valentin Andrade | Legajo 2033665
Grupos
Monóide:
Dados y ambos grupos con neutros y , se define a la operación en el conjunto tal que: . Y a
(Si y son conmutativas va a ser conmutativa también.)
Dado un monoide con neutro , y sea una relación de equivalencia:
es asociativa
es conmutativa
tiene elemento neutro o identidad
tiene elementos simétricos si, dado un elemento , su simétrico va a ser tal que: .
tiene elementos idempotentes si dado .
tiene elementos absorbentes si dado .
(Distributividad a izquierda)
(Distributividad a derecha)
Grupoide si es operación cerrada. | - Semi-grupo si además es asociativa. | - Monoide si además tiene neutro.
Grupo si además de todo lo anterior tiene simétrico. | - Si es conmutativa, entonces se le añade "Abeliano"
es regular a izquierda | - y es regular a derecha | -
( es un grupo)
es el subgrupo trivial de | - es el subgrupo impropio de | - Todo otro subgrupo es subgrupo propio. | - Un grupo es cíclico
(es abeliano).
subgrupo cíclico de generado por al conjunto: con , y . .
Todos los grupos son cíclicos. | - Sus generadores son .
La cantidad de subgrupos de es . | - Cada subgrupo tiene por cardinal a uno de los elementos . | - La red de subgrupos es isomorfa a .
es compatible a izquierda con .
es compatible a derecha con .
el conjunto cociente es un monoide, siendo
Dado un subgrupo de , , definimos la siguiente relación: , osea, es congruente a derecha con módulo . a izquierda:
( .) | -
La clase equivalencia de cualquier elemento es: | + para derecha | + para izquierda
| - esta relación produce una partición en el conjunto.
el índice de en (escrito como ) es la cantidad de clases de equivalencia módulo .
| - | - Si y son finitos:
Dado un grupo de orden finito y un subgrupo de , entonces el orden de divide al orden de .
es un subgrupo normal las clases a derecha coinciden con las clases a izquierda. | - Si es abeliano entonces todos los subgrupos son normales.
Los subgrupos impropio y trivial son normales. | - Si entonces es normal.
como el grupo cociente de módulo tal que: y el cardinal de es .
ó
| -
Si es inyectiva (osea y ), se llama monomorfismo.
Si es sobreyectiva (osea si ), se llama epimorfismo. | - Si es biyectiva, se llama isomorfismo.
Si , se llama endomorfismo. | - Si , y es biyectiva, se llama automorfismo.
. | - es subgrupo de . | - es inyectiva.
. | - es subgrupo de .
, se define a la imagen reciproca a: .
existe al menos un isomorfismo entre ellos.
El grupo es isomorfo a
Federico Valentin Andrade | Legajo 2033665
Grafos
Dígrafos
Arboles
| - es adyacente a
es aislado no es adyacente a
es incidente a (y es el extremo de )
es adyacente a | - es paralela a
es un bucle o lazo | - Un grafo es simple si no tiene aristas paraleles o bucles.
Matriz de Adyacencia tal que cada casilla es si es adyacente con y 0 de ser lo contrario.
Matriz de incidencia , tal que cada casilla es si es extremo de y sino.
, donde es la cantidad de aristas incidentes en y los bucles cuentan por dos.
camino es una sucesión de aristas adyacentes. | - camino cerrado si su vértice inicial es igual a su vértice final.
camino es simple si todos sus vértices son distintos. | - grafo es conexo si existe un camino que pasa por todos los vértices.
camino de Euler es un camino que pasa por todas las aristas sólo una vez. Un grafo tiene un camino euleriano si es conexo, y si todos los
vértices tienen grado par, o como mucho, dos de los vértices tienen grado impar.
ciclo de Euler es tal que pasa por todas las aristas del grafo. Un grafo tiene un ciclo de Euler si es conexo y todos los vértices tienen grado par.
camino es de Hamilton si es un camino simple que pasa por todos los vértices.
grafo es .
tal que: , también son , con siendo
.
es bipartito .
Un grafo bipartito es completo si tiene vértices con estas representando y y que este grafo tenga todas las
aristas únicas posibles. Esta cantidad de aristas es .
Si para crear un sub-grafo se remueve una arista o vértice, se especifica con la forma (siendo la vértice o arista a suprimir).
Dado un grafo , se define a la relación de conexión en el conjunto como: camino de a . Siendo esta una
relación de equivalencia y sus clases de equivalencia denominadas componentes conexas.
Un istmo es todo vértice tal que el sub-grafo no es conexo. | - Un puente es una arista tal que el sub-grafo no es conexo.
El subconjunto es desconectante si no es conexo.
El subconjunto es de corte es desconectante (osea, si se suprime todo el conjunto , el sub-grafo no seria conexo), y además
, no es desconectante.
La conectividad de un grafo es cuantos vértices se debe suprimir mínimamente para desconectar al grafo.
Un grafo es plano si existe un grafo isomorfo (con los mismos dos conjuntos y función de incidencia) tal que se grafique sin que ninguna arista
toque con otra.
Todo grafo es plano si no contiene ningún sub-grafo isomorfo al grafo bipartito completo o al grafo 5-regular.
Dos grafos y son isomorfos si existen dos funciones biyectivas y tales que .
Si no hay aristas paralelas se tiene suficiente evidencia si: .
Dos aristas son anti-paralelas entre sí si: dada , obligatoriamente es .
Un camino es simple si todos los vértices son distintos. | - Un camino es elemental si todas sus aristas son distintas.
| - | -
Un vértice es un pozo si | - Un vértice es una fuente si
para que exista un ciclo de Euler en un dígrafo es: .
En todo árbol se cumple que .
Un bosque es un grafo no conexo en el que cada una de las componentes es un árbol, este cumple la propiedad de que, si tiene
componentes: .
Un árbol dirigido con raíz es tal que todo excepto uno, denominado raíz, que tiene grado positivo 0.
Un vértice de un árbol se denomina hoja cuando
El nivel de un vértice depende de cuan lejos esta de la raíz, teniendo la raíz nivel 0 ( ), y cada vértice subsiguiente tiene un nivel mas
que su padre ( ). La altura de un árbol es el nivel máximo.
Si todas las hojas están en un nivel , o a lo sumo un nivel debajo es un árbol balanceado.
Un árbol con raíz es -ario . | - es regular si todos sus vértices tienen la misma cantidad de hijos | - es pleno o
completo si todas las hojas se hallan en el mismo nivel.
se llama sub-árbol con raíz y se indica , al árbol que consta de , y todos sus descendientes y aristas entre ellos.
Orden Previo/Notación Polaca: Raíz-Izquierda-Derecha. | - Orden Simétrico/Notación Usual: Izquierda-Raíz-Derecha
Orden Posterior/Notación Polaca Inversa: Izquierda-Derecha-Raíz | - NPI leída al revés (de principio a fin): Raíz-Derecha-Izquierda
Federico Valentin Andrade | Legajo 2033665
Lenguajes
Gramáticas
Tipo Nombre Producciones Máquina que lo reconoce
0 Irrestricta Con cualquier producción posible Máquina de Turing
1 Sensible al contexto donde y Autómata linealmente acotado
2 Independiente al contexto donde Autómata de Pila (Push Down)
3 Regular donde y puede ser Autómata Finito
Autómatas
Un autómata finito es una 5-upla: tal que:
p = a · q t = a · s + b · ro = a · o / p = a* v = a · v + b · wx = lambda
a
b
a
a ba
q
p
s
t
r
o v
w
x-final
Dados y , podemos pasar de uno a otro sabiendo que:
Obtener AF de una GR:
| - | - | -
Dada una palabra en el lenguaje, esta es palíndromo si es igual a su inversa.
Una propiedad de la concatenación es que . Además, la estructura es un monoide con neutro
| -
Existe el lenguaje nulo, , que contiene la palabra vacía.
También existe el lenguaje vacío, que no tiene palabras .
es un monoide abeliano con neutro
es un monoide abeliano con neutro
| - es un monoide con neutro siendo
| - es elemento absorbente.
Si y entonces
Una gramática es una cuaterna :
el vocabulario, o alfabeto de no terminales. | - el vocabulario de terminales.
las producciones. | - el símbolo o variable inicial.
el conjunto finito de estados.
el vocabulario de entrada.
la función de transición.
el estado inicial.
el conjunto de estados finales tal que
Autómata finito determinístico: Que es un A.F. que no tiene transiciones por y que su función de transición cumple con la unicidad (osea que
en cada estado se va a tener únicamente una transición por carácter).
| - | -
Las producciones son tales que y si es un estado final.
| - | - | -
si y si
Machete de Discreta.pdf
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.
Descargar
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.