MAD Resumen Final (Matematica Discreta) PDF

Preview

Summary

Resumen Matematica discreta UTN - FRC contiene todo el material teórico del cursado basado en el libro vendido en la editorial EDUCO, los temas tratados son: Teoría de Números, Lógica Matemática, Razonamientos, Conjuntos, Funciones y relaciones, Estructuras algebraicas, Grafos y Arboles...

Description

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

RESUMEN PARA FINAL TEORICO DE MATEMATICA DISCRETA

Unidad 1: Teoría de Números - División entera o Euclídea o teorema del resto. Dados dos enteros a y b con b ≠ 0, existen dos enteros únicos q (cociente) y r (resto), tales que 0 ≤ r < |b| y se cumple que a = (b * q) + r

Entonces… a) (b * q) ≤ a Siempre! b) El resto r siempre es positivo y menor que b

- Operaciones div y mod La operación div proporciona el cociente (q) entre a y b, y la operación mod proporciona el resto (r) de dividir a y b a div b = q

;

a mod b = r

- Divisibilidad Sean a y b dos números enteros, se dice que a divide a b y se escribe como a | b si existe un numero entero c tal que b = a x c. También decimos que a es divisor de b, queb es múltiplo de a o que a es un factor de b.

Entonces…  Es decir que se trata de división exacta donde el resto es 0  no confundir el símbolo de división “ / ” con el de divisibilidad “ | ”

Teoremas: 1) 1 | a y a|0 2) Si a | b y b | c => a | c 3) Todo entero que es divisor de otros es divisor de la suma de ellos 1|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información Si d | A y d | B y d | C entonces d | A + B + C 4) Todo entero que es divisor de otro es también divisor de los múltiplos de ese otro. 5) Todo entero que es divisor de otros dos es también divisor de su diferencia 6) Todo entero que es divisor de otros dos es también divisor del resto de la división de estos

- Numero primos

Un entero positivo p ≠ 1 se dice que es primo absoluto o directamente primo si sus únicos divisores son p y 1

Todo número mayor que 1 que no es primo se denomina numero compuesto

- Primos relativos

Si dos enteros positivos a y b verifican que mcd(a, b) = 1 se dicen que son primos relativos

- Mínimo común Múltiplo

El MCM de los enteros positivos a y b, es el menor entero positivo que es múltiplo tanto de a como dé b. Y se denota como mcm (a, b)

- Máximo común divisor

Dados dos números entero a y b donde a ≠ 0 o b ≠ 0, se define como máximo común divisor de a y b, al mayor de los divisores comunes de a y b. Se lo escribe como mcd (a, b)

- Algoritmo de Euclides para el cálculo del mcd Si a = b x q + r siendo 0 ≤ r < b Si r1 = 0 => b | a y el mcd (a, b) = b Si r1 ≠ 0 => se calcula b = r1 x q2 + r2 con 0 ≤ r2 < r1 Si r2 = 0 => el proceso termina cuando nr = 0 2|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información - Teorema fundamental de la aritmética Todo entero positivo puede ser escrito como producto de primos, y la factorización es la única, salvo en el orden de los factores.

Donde los an son numero naturales y los pn son números primos distintos

-Algoritmo para probar si un entero N > 1 es un numero primo 1) 2) 3) 4)

Verificar si N = 2 Verificar si 2 | N Calcular el valor del entero K solo la parte entera de √𝑵 Comprobar si D | K con D tal que 1 < D ≤ K. si es afirmativo para algún D divisor de K, entonces no es un numero primo.

3|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

Unidad 2: Lógica Matemática La lógica matemática, también llamada lógica simbólica, informalmente puede definirse como la disciplina que formaliza el estudio de los métodos de razonamiento. Objetivos:  

Eliminar la ambigüedad del lenguaje natural u ordinario. Establecer reglas que determinen la validez de un razonamiento

-Proposición lógica Es toda oración declarativa de la cual pueda decirse que es o verdadera o falsa

- Proposición compuesta Es toda composición de proposiciones simples, mediante conectivos lógicos

-Principios fundamentales de la lógica clásica Principio de Identidad: toda proposición es idéntica a sí misma, y solo a si misma (A es A) Principios de NO contradicción: dadas dos proposiciones contradictorias entre sí, no pueden ser ambas verdaderas. Principio de Tercero Excluido: dadas dos proposiciones contradictorias entre sí, no pueden ser ambas falsas

-Conectivos lógicos Vínculos que, actuando entre proposiciones simples, generan proposiciones compuestas. Conectivo No Y O Si… entonces Si y solo si

Símbolo ~ ۸ ۷ → ↔

Operación Negación Conjunción Disyunción Implicación simple Doble implicación

Significado No p, no es el caso deq p yq p oq Si p entonces q p si y solo si q

Negación: Verdadera si p es falsa y falsa si p es verdadera Conjunción: verdadera si ambas proposiciones lo son y falsa para los demás casos Disyunción: verdadera si alguna de las proposiciones lo es y falsa para ambas falsas Disyunción exclusiva: no admite ambos casos verdaderos 4|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información Implicación simple: solo falsa si es precedente es verdadero y el consecuente es falso Implicación doble: deben estar en el mismo estado para ser verdadero

Tautología: Llamaremos tautología, a las proposiciones compuestas que son verdaderas para toda posible combinación de valores de verdad de las variables proposicionales que la componen (V 0) Contradicción: Llamaremos contradicción, a las proposiciones compuestas que son falsas para toda posible combinación de valores de verdad de las variables proposicionales que la componen (F 0) Contingencia: a todas las proposiciones compuestas que pueden ser verdaderas o falsas, según el valor de sus proposiciones, se las suele llamar contingentes.

Si P: p -> q daremos un nombre a las siguientes proposiciones compuestas   

q -> p es las reciproca de P ~p -> ~q es la contraria de P ~q -> ~p es la contrareciproca de P P V V F F

q V F V F

p -> q V F V V

q -> p V V F V

~p -> ~q V V F V

~q -> ~p V F V V

-Implicación Lógica Dadas dos proposiciones compuestas P (p, q, …, z) y Q (p, q, …, z) se dice que P implica lógicamente a Q (o que Q es consecuencia lógica de P), y se denota como P => Q, si para cualquier combinación de valores de verdad de p, q, …z que haga que P verdadera, resulta que Q también es verdadera

-Equivalencia Lógica Dadas dos proposiciones compuestas P (p, q, …, z) y Q (p, q, …, z) se dice que P es lógicamente equivalente a Q, y se denota como P ↔ Q, si para cualquier combinación de valores de verdad de p, q, …z, resultan P y Q con igual valor de verdad (es más fácil de identificar por tabla)

5|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

-leyes lógicas para ۸۷         

Involución: ~(~p) = p Impotencia: p ۸ p = p Conmutatividad Asociatividad Distributiva Leyes de Morgan: ~(p ۸ q) = ~p ۸ ~q Leyes de neutro Leyes de dominación Leyes de complemento

-Principio de dualidad Si T es un teorema de la lógica matemática, entonces el dual deT , denotado como T* construido reemplazando los símbolos {v, f, ٨, ٧} de T por los símbolos {v, f, ٧, ٨}, respectivamente, es también un teorema

6|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

Unidad 3: Razonamientos -Razonamiento deductivo Dadas dos o más proposiciones p 1, p2, …, p n llamadas hipótesis o premisas, y proposición Q, llamada Conclusión, llamaremos razonamiento a la relación entre ellas. Se denota como: 𝐩𝟏, 𝐩𝟐, … , 𝐩𝐧 ∴ 𝐐 Y diremos que la misma es válida si Q resulta verdadera cada vez que las hipótesis sean simultáneamente verdaderas De un razonamiento que no es válido, se dice que es una falacia

 Un razonamiento es una relación entre proposiciones, la cual no puede decirse que sea verdadera o falsa, sino que es válida o no.  Un razonamiento será válido, si y solo si, la verdad de las hipótesis o premisas es evidencia de la verdad de la conclusión, o sea, no es posible que las premisas sean verdaderas y la conclusión falsa. Entonces el razonamiento será válido si 𝒑 ۸ 𝒑 ۸ … ۸ 𝒑 → 𝑸 𝒆𝒔 𝒖𝒏𝒂 𝒕𝒂𝒖𝒕𝒐𝒍𝒐𝒈𝒊𝒂  Si un razonamiento es válido, la relación entre las premisas mismas y entre ellas y la conclusión, conforman un esquema válido independiente de los valores de verdad de las proposiciones intervinientes A esta forma de razonar se le denomina regla de inferencia -Reglas de inferencia Ley de separación (modus ponens) : si p y p → q son ambos verdaderos, se infiere queq también lo es. En símbolos: p, p → q ⁖ q En su forma clásica: 𝒑 𝒑 →𝒒 ∴𝒒 Ley del modus tolens: si p → q es verdadero y q es falsa, se infiere quep es falsa. En símbolos: 𝐩 → 𝐪,~𝐪 ∴ ~𝐩 En su forma clásica: 𝐩 → 𝐪 ~𝒒 ∴ ~𝒑

7|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

Ley de silogismo hipotético: sip → q y q → r son ambos verdaderos, se infiere la veracidad de p → r. En símbolos:𝒑 → 𝒒,𝒒 → 𝒓 ∴ 𝒑 → 𝒓 En su forma clásica: 𝒑 →𝒒 𝒒→𝒓 ∴ 𝒑 →𝒓

Estas son solo 3 de algunas de las infinitas tautologías que pueden darse. Pero la idea general de este tema es que, para efectuar la demostración de un teorema , es necesario aplicar una sucesión finita de transformaciones, sobre las premisas, hasta llegar a la conclusión buscada.

-Lógica de predicados Función proposicional: o predicado es una variableX, denotado como F(x) es toda oración declarativa que asigne una determinada propiedad “F” al objeto indeterminado “X” y que se convierta en proposición lógica al instanciarlo.

-clase La serie de objetos que comparten alguna característica común, “ser hombres”, conforman una abstracción que se ha dado en llamar clase o categoría Generalmente se denotan con mayúscula las clases, y con minúscula los objetos que a ellas pertenecen. Además si un objeto posee una propiedad o característica que defina la clase C se dice que el miembro de ella o que pertenece a ella (𝑿 ∈ 𝑪 𝒐 𝑿 ∉ 𝑪) La clase además puede ser vacía (⊘ )

-Cuantificadores Universal y Existencia *Todo X posee la propiedad F, se escribe como:∀𝒙 :𝑭(𝒙) *Existe un X, que posee la propiedad F, se escribe como:∃𝒙/𝑭(𝒙) En la primera la función esta cuantificada universalmente y en la segunda está cuantificada existencialmente. Y así una función proposicional adquiere el rango de proposición lógic

8|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

-proposiciones categóricas: Dadas dos clases A y B, llamaremos proposición categórica a toda proposición lógica que tenga una de las siguientes cuatro formas.  1) 2)  3) 4)

universales Para todo X perteneciente a A, también pertenece a B Para todo X perteneciente a A, no pertenece a B Particulares Existe al menos un X de A, que también pertenece a B Existe al menos un X de A, que no pertenece a B

-Principio de inducción matemática. Sucesiones y series: Sucesión: una sucesión es una estructura discreta utilizada para representar una lista ordenada de elementos Una sucesión numérica es una secuencia ordenada de números, llamados “términos”, entre cada uno de los cuales hay una relación que se debe cumplir para determinar el próximo número. -Inducción matemática Es el proceso por el cual vislumbramos nuevas verdades generales a partir de verdades particulares conocidas, haciéndolo de lo particular a lo general Axioma: son verdades evidentes, que no requieren o no pueden ser demostradas -Propiedades de los números naturales 1. 0 es un numero natural (axioma de Peano) 2. Si a es un numero natural, entonces a+1 también es un numero natural (axioma de Peano) 3. Cualquier subconjunto no vacío de números naturales tiene un elemento mínimo (principio del buen orden)

-Principio de inducción Matemática Una función proposicional F(n) referida a los números naturales es verdadera para cualquier número natural n > n0 si se satisfacen las dos siguientes condiciones  

Base inductiva: la proposición F(0) es verdadera para algún número natural 0n Paso Inductivo: la veracidad de F(k) para cualquier número natural K > 0nimplica que la veracidad de F(k+1) para el numero natural siguiente k+1

9|Página Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

10 | P á g i n a Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información Método para la demostración por inducción matemática 1) Base Inductiva: demuestre que P(a) es verdadera para algún número natural 0n 2) Paso Inductivo: demuestre que para todo entero K ≥ a, que si P(k) se cumple entonces P(k+1) es verdadera Para demostrarlo: 3) Hipótesis Inductiva: suponga que P(k) es verdadera 4) Denueste que P(k+1) es verdadera

11 | P á g i n a Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

Unidad 4: Conjuntos Diremos que un con conjun jun junto to eess cualq cualqui ui uier er ccolecc olecc olección ión bie bien n ddef ef efinida inida ddee oobj bj bjeto eto etoss, los cuales reciben el nombre de miembros o elem elemento ento entoss del conjunto. Un conjunto puede tener un número finito de elemento (letras vocales), o un número infinito de elementos (números naturales). -No -Notació tació tación n: Con mayúscula al conjunto (A A ) y con minúscula al elemento (a)   

Pertenencia: 𝒂 ∈ 𝑨 No pertenencia: 𝒂 ∉ 𝑨 Determinación de un conjunto: 1. por ejemplo las vocales 𝑉 = {𝑎, 𝑒, 𝑖, 𝑜, 𝑢} definido por extensión o enumeración 2. definido por comprensión 𝑉 = {𝒙 / 𝒙 𝑒𝑠 𝑢𝑛𝑎 𝑣𝑜𝑐𝑎𝑙 𝑑𝑒𝑙 𝑎𝑙𝑓𝑎𝑏𝑒𝑡𝑜 𝑒𝑠𝑝𝑎ñ𝑜𝑙}

-Co -Conjun njun njuntos tos esp especi eci eciales ales ales:: Con Conjunt junt junto o vacío vacío: simbolizado por 𝜙 o por extensión {} Con Conjunt junt junto o unita unitario: rio: aquel que posee un solo elemento Univ Universo erso ddee dis discu cu curso: rso: al cual pertenecen naturalmente todos los objetos a los que se hace referencia en el estudio. Con Conjunt junt junto o univ universal: ersal: del cual son miembros todos los elementos de los conjuntos bajo estudio y se lo denota como “U ”

-Igu -Igualda alda aldad d de C Conju onju onjunto nto ntoss

Dados dos conjuntos A y B diremos que son iguales, (A = B), si están formados por exactamente los mismo elementos. 𝑨 = 𝑩 ↔ ∀𝒙: 𝒙 ∈ 𝑨 → 𝒙 ∈ 𝑩 ⋀ ∀𝒚: 𝒚 ∈ 𝑩 → 𝒚 ∈ 𝑨

-Su -Subco bco bconjun njun njuntos tos Dados dos conjuntos A y B, diremos que A esta incluido en B 𝐴 ( ⊆ 𝐵), si todo elemento de A es elemento de B. 𝑨 ⊆ 𝑩 ↔ ∀𝒙: 𝒙 ∈ 𝑨 → 𝒙 ∈ 𝑩 Esta inclusión se conoce como inclusión amplia o simplemente inclusión

12 | P á g i n a Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

Diagrama de Venn de la inclusión 𝑨 ⊆ 𝑩

Dados dos conjuntos A y B, diremos que A esta estrictamente incluido en B𝐴( ⊂ 𝐵), si todo elemento de A es elemento de B, pero existe al menos un elemento de B que no es elemento de A. 𝑨 ⊆ 𝑩 ↔ ∀𝒙: 𝒙 ∈ 𝑨 → 𝒙 ∈ 𝑩 ∧ ∃𝒚 / 𝒚 ∈ 𝑩 ∧ 𝒚 ∉ 𝑨 Esta inclusión se conoce como inclusión estricta

-Cardinalidad de un conjunto Dado un conjunto finito A , llamaremos cardinalidad de A (y lo denotaremos como |A|), al número de n elementos que pertenecen a él. |A|=n

Pro Propied pied piedade ade adess d de e la inclu inclusi si sión ón 1) Pro ropieda pieda piedad dR Refl efl eflexiva exiva exiva:: todo conjunto es parte de sí mismo 2) Pro ropieda pieda piedad d Trans Transitiv itiv itiva: a: si un conjunto es subconjunto de otro y este es subconjunto de un tercero, entonces el primero es subconjunto del tercero 3) Pro ropieda pieda piedad dA Antis ntis ntisim im imetri etri etrica: ca: si un conjunto es subconjunto de otro y este es subconjunto del primero, entonces los conjuntos son iguales. 4) Vacío siem siempr pr pre ep pres res resen en ente: te: el conjunto vacío está incluido en cualquier conjunto 5) Unicid nicidad ad d del el vvacío: acío: el conjunto vacío es único. 6) Cardina ardinalidad: lidad: si un conjunto finito, está incluido en otro, también finito, entonces la cardinalidad de este el menor o igual a la del segundo. Fam Familia ilia d de e co conjunto njunto njuntos. s. Conjunto de conjuntos, clase de conjuntos o familia de conjuntos, son conjuntos que tienen como elementos a otros conjuntos A = {{a}, b} entonces {𝒂} ∈ 𝑨

𝒃 ∈𝑨

{𝒃} ⊆ 𝑨

{𝒂} ⊆ 𝑨 13 | P á g i n a

Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información Sin embargo el elemento a no pertenece al conjunto A y el conjunto {a} no está incluido en A si no que es un elemento de mismo Co Conjun njun njunto to p poten oten otencia. cia. Una familia de conjuntos cuya aplicación es importante, es el denominadoconjunto potencia de un conjunto A, denotado por P(A), la cual se define como aquella que tiene por elementos a todos los posibles subconjuntos de A. 𝑷(𝑨) = {𝑿 / 𝑿 ⊆ 𝑨

-Operaciones con conjuntos  Co Comple mple mplementa menta mentació ció ción: n: Dado un conjunto A, y el conjunto universalU, llamaremos complemento de A al conjunto ∼𝐴, formado por rodos los elementos del conjunto universal, que no pertenecen al conjunto A ∼ 𝑨 = {𝒙 / 𝒙 ∈ 𝑼 ∧ 𝒙 ∉ 𝑨

Dados dos conjuntos A y B , llamaremos complemento de A con respecto de B, al conjunto B-A formado por todos los elementos de B que no pertenecen a B - A = {𝒙 / 𝒙 ∈ 𝑩 ∧ 𝒙 ∉ 𝑨

14 | P á g i n a Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información  Inte Intersec rsec rsección: ción: Dados dos conjuntos A y B, llamaremos intersección de A y B, al conjunto𝐴 ∩ 𝐵 formado por todos los elementos comunes de A y de B 𝑨 ∩ 𝑩 = {𝒙 / 𝒙 ∈ 𝑨 ∧ 𝒙 ∈ 𝑩

 Unió Unión: n: Dados dos conjuntos A y B, llamaremos unión de A y B, al conjunto𝐴 ∪ 𝐵 formado por todos los elementos de A y todos los elementos de B 𝑨 ∪ 𝑩 = {𝒙 / 𝒙 ∈ 𝑨 ∨ 𝒙 ∈ 𝑩

 Partic Partición ión del cconjunt onjunt onjunto o Dados los conjuntos no vacíosA 1, A2, A3 , …, An y el conjunto B, llamaremos partición de B a la familia L = { A1, A2, A3, …, An } si se verifica que los conjuntos A, son distintos de a pares y si para cada elemento x de B, x pertenece a algún conjunto A i con i = 1, 2, …, n. a) 𝐀𝐢 ∩ 𝐀𝐣 = ⊘, con i ≠ 𝑗 𝑒 𝑖, 𝑗 = 1, 2, … , 𝑛 b) 𝑩 = 𝐀 𝟏 ∪ 𝐀𝟐 ∪… ∪ 𝐀𝐧

15 | P á g i n a Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba Ingeniería en Sistemas de Información

16 | P á g i n a Alumno: Gigena Mauro Curso: 1K7

instagram: chico.utn

Universidad Tecnológica Nacional – Facultad Regional de Córdoba I...