UP | HOME

Matemáticas Discretas
Apuntes

Índice

1 Lenguaje formal

El lenguaje formal es un lenguaje artificial, convencional, elegido de manera consciente y cuidadosa para expresarse precisa, sistemática, rigurosa y unívocamente, por lo común dentro de un cierto campo del saber y con determinados fines.

2 Lenguaje natural

El lenguaje natural es aquel que utilizamos cotidianamente. Surge históricamente dentro de la sociedad y es aprendido sin que exista necesariamente en el individuo un acto reflexivo.

3 Variables proposiciones

conjunto de enunciados declarativos que formalizan la expresión, usualmente se les denota con las letras (p, q, r, s…).

Enunciado declarativo
es aquella proposición de lenguaje objeto de la caal podemos predicar su verdad o su falsedad.

"Hay un automóvil blanco en el aparcamento".

Enunciado NO declarativo
es un enunciado que no puede ser convertido a lenguaje formal.

"¿Dónde esta mi automóvil?".
"¡Guarda silencio!".

Enunciado atómico
es aquél enunciado único, que en su expresión no incluye ningún conectivo lógico, es decir, no une dos o más enunciados.

"Hoy es miércoles."
"Vivo en el distrito Federeal."
"Pablo es matematico"

Extraido

4 Conectivas proposicionales

4.1 resumen

son los simbolos que formalizan los elementos del lenguaje que sirven para su funcion argumentativa.

Relacion Notación Lectura
Negacion \(\lnot\) no
Conjunción \(\lor\) o
Disyunción \(\land\) y
Implicación \(\rightarrow\) entonces
Equivalencia \(\equiv \) equivalente a
Por lo tanto \(\vdash\) deduce que, conclusion
Doble implicación \(\leftrightarrow\) Sí y solo sí
Tautología \(\top ~ T\) Verdadero
Contradicción \(\bot ~ F\) Falso
pertenece \(\in\) sí x pertenece a un conjunto
Cuantificador universal \(\forall\) para todo x hay y
Cuantificador existencial \(\exists\) existe;hay por lo menos un

conjuncion diyuncion negacion

Lista de simbolos | Lista de Simbolos completa

4.2 Conjucion

Solo una de las variables preposicionales tiene que ser verdadera para que el predicado sea verdadero

4.3 Disyunción

Lo opuesto a la conjunción, ambas tienen que ser verdaderas para que la expresión sea verdadera.

4.4 Implicación

Sí un enunciado es verdadero el otro tambien es verdadero

P ≡ "Hace frio" q ≡ "Usare sueter"

\[ p \rightarrow q \]

4.5 Por lo tanto

Se usa para denotar la conclusion de un argumento, si es verdadero entonces el argumento es valido; sí es falso entonces no es valido.

"Juan es francés si nació el 23 de febrero. Si es bretón, entonces es más bien bajo. Ahora bien, nació el 23 de febrero o es bretón. Por consiguiente, es francés o es más bien bajo."

Convenciones simbólicas:

  • p ≡ Juan es francés
  • q ≡ Juan nació el 23 de febrero
  • r ≡ Juan es bretón
  • s ≡ Juan es más bien bajo

Formalización: \[q \rightarrow p, r \rightarrow s, q \lor r \vdash p \lor s\]

4.6 Doble implicación

Se lee como "sí y solo sí", eso significa que para que sea verdadera ambos valores tienen que ser iguales (ambos verdaderos o ambos falsos).

4.7 Tautología

es un forma de enunciado que siempre es verdadera, independientemente de los valores de verdad de los enunciados individuales sustituidos por sus enunciados variables. Un enunciado cuya forma es una tautología es un enunciado tautológico.

4.8 Contradicción

es una forma de enunciado que siempre es falso, independientemente de los valors de verdad de los enunciados individuales de los enunciados sustituidos. Un enunciado cuya forma es una contradicción es un enunciado contradictorio.

4.9 Cuantificador universal

para todos los elementos de un dominio siempre se cumple una funcion proposicional.

4.10 Cuantificador existencial

De todos los elementos del dominio existe por lo menos un elemento que cumple la funcion propocional.

4.11 Ejemplo de cuantificador universal y existencial

"Todos los artistas son ricos. Algunos políticos son corruptos. En conclusión no todos los artistas y no todos los políticos son ricos y corruptos"

Convenciones simbólicas:

  • A = { a | a es un politico }
  • B = { b | b es un artista }
  • p(a): Los políticos que son ricos
  • p(b): Los artistas que son ricos
  • q(a): Los políticos que son corruptos
  • q(b): Los artisas que son corruptos

Formalización:

\[ [(\forall b \in B) p(b), (\exists a \in A) q(a)] \vdash (\exists a \in A) p(a) \land (\exists a \in A) q(a) \land (\exists b \in B) p(b) \land (\exists b \in B) q(b) \]

5 Tablas de verdad

Son tablas que nos sirven para conocer los valores de verdad de las proposiciones compuestas.

"No salió electo Presidente de la República o el crecimiento anual no fue del 7%"

Convenciones simbólicas:

  • p ≡ "salió electo Presidente de la República"
  • q ≡ "el crecimiento anual fue del 7%"

Tabla de verdad:

p q ¬p ¬q p∧q ¬p∧q p∧¬q ¬p∧¬q
F F V V F V V V

Generador de tablas de verdad

6 Equivalencia lógica

Dos formas de enunciado se llaman lógicamente equivalents si y sólo si, tienen los mismos valores de verdad para cada posible sustitución de enunciados por sus enunciados de variables. La equivalencia lógica de las formas de enunciado P y Q se denota escribiendo P ≡ Q.

7 Leyes commutativas

Establecen que el orden en el cual sume o multiplique dos números reales no afecta el resultado.

\[ \begin{aligned} p \land q &\equiv q \land p & p \lor q &\equiv q \lor p \end{aligned} \]

8 Leyes asociativas

Establecen que cuando suma o multiplica cualesquiera tres números reales, el grupo (o asociación) de los números no afecta el resultado.

\[ \begin{aligned} (p \land q) \land r &\equiv p \land (q \land r) \\ (p \lor q) \lor r &\equiv p \lor (q \lor r) \end{aligned} \]

9 Leyes distributivas

Expresa que se obtiene la misma respuesta cuando multiplicas un conjunto de números por otro número que cuando se hace cada multiplicación por separado

\[ \begin{aligned} p \land (q \lor r) &\equiv (p \land q) \lor (p \land r) \\ p \lor (q \land r) &\equiv (p \lor q) \land (p \lor r) \end{aligned} \]

10 Leyes de la identidad

Es la constatación de que dos objetos que matemáticamente se escriben diferente, son de hecho el mismo objeto.

\[ \begin{aligned} p \land t &\equiv p & p \lor c &\equiv p \end{aligned} \]

11 Leyes de negacion

Dada una proposición p su contraria no p es verdadera.

\[ \begin{aligned} p \land \lnot p &\equiv t & p \lor \lnot p &\equiv c \end{aligned} \]

12 Ley de la doble negacion

se produce cuando se combina el adverbio no con la presencia de otros elementos que tienen también sentido negativo.

\[ \begin{aligned} \lnot(\lnot p) \equiv p \end{aligned} \]

13 Leyes de idempotencia

es la propiedad para realizar una acción determinada varias veces y aun así conseguir el mismo resultado que se obtendría si se realizase una sola vez.

\[ \begin{aligned} p \land p &\equiv p & p \lor p &\equiv p \end{aligned} \]

14 Leyes universales acortadas

\[ \begin{aligned} p \lor t &\equiv t & p \land c &\equiv c \end{aligned} \]

15 Leyes de morgan

son un par de reglas de transformación que son ambas reglas de inferencia válidas. Las normas permiten la expresión de las conjunciones y disyunciones puramente en términos de vía negación.

\[ \begin{aligned} \lnot ( p \land q ) &\equiv \lnot p \lor \lnot q & \lnot ( p \lor q ) &\equiv \lnot p \land \lnot q \end{aligned} \]

16 Leyes de absorción

\[ \begin{aligned} p \lor (p \land q) &\equiv p & p \land (p \lor q) &\equiv p \end{aligned} \]

17 Negaciones de t y c

El negativo de una tautología es una contradicción y el opuesto de una contradicción es una tautología.

\[ \begin{aligned} \lnot t &\equiv c & \lnot c &\equiv t \end{aligned} \]

18 Implicación

La implicación logica se emplea para representar una afirmacion no hipotetica, es decir: A es verdadero por lo tanto B es verdadero.

"Sí llueve, el suelo esta mojado"
"llueve. por tanto, el suelo esta mojado"

19 Validación de argumentos (Demostración)

Un argumento es valido (lógico) sí la conclusion es verdadera siempre y cuando todas las premisas sean verdaderas

Un argumento valido seria algo como:

\[ ((\lnot p \implies q) \land (p \implies (\lnot r \lor s))) \implies ( \lnot s \land \lnot q \land \lnot r ) \implies p\]

20 Ejercicios

21 Conjuntos

Un conjunto es una Colección bien definida de objetos, que se denominan elementos o miembros del conjunto. Usualmente las letras mayúsculas denotan a los conjuntos y las letras minúsculas denotan a los elementos del conjunto.

  • \(a \in S\) denota que el elemento a pertenece al conjunto S.
  • \(a \not \in S \) denota que el elemento NO pertenece al conjunto S.

22 Subconjunto

Se dice que A es un subconjunto de B si A está contenido en B o en otras palabras que B contiene a A. \( A \subseteq B \) o \( B \supseteq A \). Dos conjuntos son iguales si ambos tienen los mismos elementos o, equivalentemente, si cada uno está contenido en el otro.

A = B si y solo si \( A \subseteq B \) y \( B \subseteq A \)

23 Simbolos especiales

Los conjuntos numéricos usuales en matemáticas son:

  • el conjunto de los números naturales \(\mathbb{N}\).
  • números racionales \(\mathbb{Q}\).
  • números enteros \(\mathbb{Z}\).
  • números reales \(\mathbb{R}\).
  • números complejos \(\mathbb{C}\).

La relacion entre estos grupos es la siguiente:

\[ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C} \]

24 Operacion es de conjuntos

Existen unas operaciones básicas que permiten manipular los conjuntos y sus elementos, similares a las operaciones aritméticas, constituyendo el álgebra de conjuntos:

24.1 Union

La unión de dos conjuntos A y B, es el conjunto de todos los elementos que pertenecen a A o a B, es decir:

12.png

Figura 1: \(A \cup B = \{x|x \in A~o~x \in B \}\)

24.2 Intersección

La intesección de dos conjuntos A y B, es el conjunto de todos los elementos que pertenecen tanto a A como a B, es decir:

13.png

Figura 2: \( A \cap B \{x|x \in A~y~x \in B \} \)

24.3 Complemento (Complemento Absoluto)

El complemento absoluto o simplemente complemento de un conjunto A es el conjunto de elementos que pertenecen a U pero no pertenencen a A:

Dado un conjunto A, su complementario es el conjunto formado por los elementos que no pertenecen a A.

14.png

Figura 3: \(A^C = \{ x | x \in U, x \not \in A \} \)

24.4 Diferencia de conjuntos (Complemento relativo)

La diferencia entre A y B también se denomina complemento relativo de B en A, y se denota \(C_AB\), cuando el segundo es un subconjunto del primero.

El complemento relativo de un conjunto B respecto de un un conjunto B o la diferencia de A y B, es el conjunto de elementos que pertenecen a A pero no pertenecen a B:

15.png

Figura 4: \(A \backslash B = \{ x | x \in A, x \not\in B \} \)

24.5 Diferencias simétrica

Dados dos conjuntos A y B, su diferencia simétrica, A Δ B, es un conjunto que contiene los elementos de A y los de B, excepto los que son comunes a ambos.

La diferencia simétrica de los conjuntos A y B consta de los elementos que pertenecen a A o a B pero no a ambos:

16.png

\(A \bigoplus B = (A \cup B) \backslash (A \cap B) \)
o
\(A \bigoplus B = (A \backslash B) \cup (B \backslash A) \)

Mas informacion

25 Productos fundamentales

\[ \begin{matrix} P_1 = A \cap B \cap C & ~ & P_2 = A \cap B \cap C^C \\ P_3 = A \cap B^C \cap C & ~ & P_4 = A \cap B^C \cap C^C \\ P_5 = A^C \cap B \cap C & ~ & P_6 = A^C \cap B \cap C^C \\ P_7 = A^C \cap B^C \cap C^C & ~ & P_8 = A^C \cap B^C \cap C^C \\ \end{matrix} \]

17.png

26 Representación grafica de las relaciones

26.1 Grafo dirigido

Para representar una relación R sobre un solo conjunto A.

A={1,2,3,4},
R={(1,2),(2,2),(2,4),(3,2),(3,4),(4,1),(4,3)}

18.png

26.2 Diagrama sagital

A={1,2,3}, B={x,y,z}
R={(1,y),(1,z),(3,y)}

19.png

26.3 Matriz de relación

20.png