ESTRUCTURAS DISCRETAS 

ESTUDIANTE:               ISMAEL CAMACHO VALLEJOS

DOCENTE:                     GUSTAVO TANTANI MAMANI

 

2022

LOGICA MATEMATICA

La lógica es la disciplina que trata de los métodos modos y formas de razonamiento humano ofrece reglas y técnicas para determinar si un argumento es valido o no. 

Una de las metas fundamentales de la lógica es eliminar la ambigüedad del lenguaje ordinario introduciendo símbolos y conectivos lógicos en la construcción de proposiciones.

PROPOSICIONES 

Una proposición es su enunciado que puede ser verdadero o falso. La verdad y la falsedad se llaman valores de verdad de una proposición.

EJEMPLO: Determinar cual de las oraciones llega a ser proposicion. 

1.- El dia esta frio.                                          F no es proposición 

2.- El símbolo del agua es H2O                     V si es proposición 

3.- 5 es menor que -5                                     V se es proposición 

4.- Bolívar es campeón                                  F no es proposición

NOTA: a las preposiciones se les otorga un valor de verdad 

                                                                              Valores de verdad 

1.- El símbolo del agua es H2O                              V

2.- 5 ES MENOR QUE -5                                       F

3.- 7=8                                                                     F

NOTACIÓN Y CONECTIVOS LOGICOS.-

 A las proposiciones simples o genéricas (llamadas atómicas) se acostumbran denotar con las letras minúsculas: p,q,r,s,t.

 

q: El símbolo del agua es H2O                              q=V

p: 5 ES MENOR QUE -5                                       p=F

r: 7=8                                                                      r=F

s: 5<3                                                                      s=f

A partir de proposiciones simples se puede construir proposiciones compuestas (moleculares) introduciendo símbolos y conectivos lógicos tales como  

  

 

 OPERACIONES PROPOSICIONALES:

Las condiciones en las que las negaciones, conjunciones, disyunciones, implicaciones y complicaciones son varaderas o falsas se analizan mediante tablas de verdad.

NEGACION.-

Cuando decimos "no P" (~p), afirmamos que la proposición p es falsa, por tanto:

REGLA: La negación de una proposición es falsa, si la proposición negada es verdadera; y es verdadera, si la proposición negada es falsa. 

 

CONJUNCION.-

Cuando decimos "p y q" (p ^ q), afirmamos que tanto p como q son verdaderas por tanto: 

 REGLA: La conjunción es verdadera solo cuando ambas proposiciones son verdaderas; si alguna es falsa, la conjunción es también falsa.

DISYUNCION.-

Cuando decimos "p o q" (p ∨ q), en el sentido de p y/o q, afirmamos que al menos una de las dos proposiciones es verdaderas; por tanto:

 

REGLA: La disyunción es verdadera cuando al menos una de las dos proposiciones es verdadera; si ambas son falsas, la disyunción es también falsa.

IMPLICACION.- 

 Cuando decimos "Si p entonces q" (p→q),afirmamos que en caso de que p sea verdadera, q también lo es, por tanto:

 COIMPLICACION.-

 Cuando decimos "p si y solo si q"(p↔q), afirmamos que ninguna de esas proposiciones es verdadera sin que tambien sea verdadera la otra por tanto:

 

REGLA: La coimplicación es verdadera solo cuando ambas proposiciones son falsas. En los otros casos, es falsa 

DISYUNCION EXCLUSIVA.-   "⊻" "p ⊻ q"

REGLA: Es verdadero si las preposiciones tienen valores de verdad contrarios, caso contrario es falso.

FORMULAS PROPOSICIONALES:

Una formula proposicional es una combinacion de proposiciones y conectivos logicos 

TABLAS DE VALORES DE VERDAD.-

El valor de verdad de una formula proposicional depende de los valores de verdad de las proposiciones simples que la componen 

 La cantiad de combinaciones (Registro o filas) depende del numero de proposiciones y se coloca con la formula 2n,donde n es el número de proposiciones.

CLASIFICACION DE FORMULAS PROPOSICIONALES 

Las fórmulas proposicionales (las proposiciones compuestas) se clasifican, según sus

valores de verdad, en Tautología, Contradicción y Contingencia.

TAUTOLOGIA 

Es una fórmula proposicional que es verdadera para cualquier valor de verdad de las proposiciones que la componen. 

CONTRADICCIÓN.-

Es una fórmula proposicional que es falsa para cualquier valor de verdad de las proposiciones que la componen.

CONTINGENCIA.-

Es una formula proposicional que no es tautología ni contradicción.

 EQUIVALENCIA LOGICA

Dos fórmulas proposicionales se dice que son lógicamente equivalentes si las tablas de

verdad son idénticas, o sus valores de verdad son los mismos en cada renglón.

Usaremos el símbolo " = " para expresar la equivalencia entre dos fórmulas

proporcionales. 

EJEMPLOS ADICIONALES 

ALGEBRA DE PROPOSICIONES

Son operaciones lógicas que se realizan en una fórmula proposicional, aplicando adecuadamente ciertas reglas básicas llamadas leyes lógicas. Es decir, al igual que en álgebra básica donde la simplificación de expresiones algebraicas es muy importante, en lógica también existe la necesidad de sinrplificar fórmulas proposicionales complejas, a través de ciertas equivalencias llamadas leyes lógicas. que a continuación se listan.

LEYES LOGICAS 

SIMPLIFICACION DE FORMULAS PROPOSICIONALES 

Se trata de trasformar una fórmula proposicional en otra equivalente a ella pero lo más

reducida posible. Para lo cual se debe usar oportuna y correctamente las leyes lógicas.

Así mismo, deben especificarse en cada paso la ley o leyes que fueron utilizados.

CIRCUITOS LOGICOS 

Un circuito, con un interruptor, puede estar"abierto" o "cerrado". Cuando el interruptor

está abierto no permite el paso de corriente. mientras c¡ue cuando está cerrado sí lo

permite. Si asociamos una proposición a cada interruptor, intuitivamente, vemos que en

el álgebra de circuitos la V de tal proposición indica el interruptor cerrado y F el

interruptor abierto. Así, el circuito lógico que representa a una proposición p es: 

CIRCUITOS EN PARALELO 

La disyunción de dos proposiciones (p v q) está representada por un circuito lógico en paralelo. Esto es:

Este circuito no permite el paso de corriente únicamente si p y q son F (o están abiertos). Por lo cual, la tabla de verdad de la disyunción de dos proposiciones, p y q, es: 

INFERENCIA LÓGICA

Se debe entender por inferencia lógica a un razonamiento en el que a partir de un conjunto de proposiciones llamadas premisas se obtiene un resultado llamado conclusión. 

REGLAS DE INFERENCIA

Se le llaman reglas de inferencia a todo argumento universalmente correcto (o tormas, correctas de razonamiento) que representan métodos generales de razonamiento válido. Las siguientes son formas correctas de razonamiento: 

EJEMPLOS

FUNCIONES PROPOSICIONALES Y SU CUANTIFICACIÓN

FUNCIONES PROPOSICIONALES

Una función proposicional en una variable X es toda expresión en la que X representa al

sujeto u objeto perteneciente a cierto conjunto. La cual se convierte en proposición para

cada especificación de X. Es decir, si P(X) es una expresión que se convierte en

proposición al sustituir la variable X por un objeto matemático, se dice que P es una

función proposicional. Asimismo hay funciones proposicionales con más de una

variable.

CUANTIFICADORES

A partir de funciones proposicionales se puede obtener proposiciones generales mediante un proceso llamado de cuantificación. Para ello, introducimos los símbolos V y 3, llamados cuantificador universal y existencial, respectivamente. Los cuales asociados a la variable x expresan lo siguiente:

V x, para expresar "para todo x", o "cualquiera que sea x"

3 x, para expresar "existe algún x, tal que", o "existe al menos un x, tal que"

CONJUNTOS 

Si bien, el concepto de conjunto se podría atribuir con objetos reales como una agrupación de animales, personas, países, capitales del mundo, tipos de palomas, en fin cualquier cosa que tenga algo en común en la vida real para agruparlos, no fue hasta el siglo XIX comenzó a aplicarse el concepto de conjunto como un objeto abstracto donde sus elementos se conformaban por ejemplo con números, otros conjuntos, agrupaciones de signos matemáticos, etc.

Por ejemplo, el conjunto de aves:

$$A=\left\{\text{pelicano, gallina, tucan}\right\}$$

El conjunto de marcas de smartphone:

$$C=\left\{\text{Sony, Samsung, Apple, Lg, Huawei}\right\}$$

O el conjunto de los números primos:

$$P=\{2,3,5,7,11,\cdots \}$$

DETERMINACION DE UN CONJUNTO

Un conjunto puede ser determinado de dos maneras: por extensión y por comprensión

POR EXTENSIÓN 

Se dice que un conjunto está determinado por extensión sí y

solo sí se nombran todos los elementos que lo constituyen. En este caso se escriben sus

elementos entre dos llaves. 

POR COMPRENSIÓN 

Se dice que un conjunto está determinado por comprensión sí y solo si se da la propiedad o propiedades que caracterizan a todos los elementos del conjunto. 

CONJUNTOS ESPECIALES

Llamaremos conjuntos especiales a aquellos conjuntos que se caracterizan por el

número de elementos, entre ellos tenemos: conjunto unitario, conjunto vacío. conjunto

universal,

CONJUNTO UNITARIO

Es aquel conjunto que tiene un sólo elemento. 

CONJUNTO VACIO

El conjunto nulo o vacío es aquél conjunto que carece de elementos, y se denota por 0. Es decir, 0 :{ }

CONJUNTO UNIVERSAL 

El conjunto universal, llamado también universo o referencial, es un conjunto de cuyos elementos se escogen algunos de ellos para formar otros conjuntos. Se denota por U. 

RELACIONES

Una relación propiamente dicha es un vinculo entre dos objetos, este concepto también es usado en matemáticas para buscar una relación entre los elementos de dos conjuntos distintos o sobre el mismo conjunto.

La sección de relaciones cataloga dos tipos según las propiedades que cada una las diferencia, en este caso, las propiedades de relación de un conjunto sobre si mismo, es decir, de la relación entre los elementos del conjunto consigo mismo se estudia en la sección de relaciones binarias y para el estudio de las propiedades dos conjuntos distintos se estudia en la sección de correspondencia.

¿Que es un par ordenado?

Un par ordenado es esta expresión que ves aquí:

$$(a,b)$$

Definimos un par ordenado como un conjunto ordenado tal $a$ es la primera componente y $b$ es la segunda componente y cumple la siguiente restricción:

$$(a,b)$$

Si y sólo si $a\ne b$. Esta restricción obliga que para dos pares ordenados $(a,b)$ y $(c,d)$ se cumpla:

$$(a,b)=(c,d)$$

Siempre y cuando $a=c$ y $b=d$.

Para que estos pares ordenados existan, cada componente debe estar definido sobre un conjunto, puede que cada componente tenga su propio conjunto definido completamente diferentes o las dos componentes estén definidos sobre un mismo conjunto. Esto significa que también podemos crear parejas de pares ordenados con el resto de los elementos de estos conjuntos y tiene un nombre especial, y lo veremos en breve:

¿Producto cartesiano?

También llamado conjunto producto, y comprende todo el conjunto de pares ordenados formado por los vínculos aleatorios (es decir, todas las combinaciones posibles) de dos conjuntos distintos o de un mismo conjunto.

Si tenemos el conjunto $A=\{a,b,c\}$ y el conjunto $B=\{2,4,6\}$, simbolizamos el producto cartesiano por $A\times B$ tal que forma el siguiente conjunto por extensión de pares ordenados:

$$A\times B=\left\{\begin{array}{ccc}(a,2)& (a,4)& (a,6)\\ (b,2)& (b,4)& (b,6)\\ (c,2)& (c,4)& (c,6)\end{array}\right\}$$

De aquí, podemos extraer muchos subconjuntos de $A\times B$, como por ejemplo:

• $R_1=\left\{\right(a,2),(b,4),(c,6\left)\right\}$
• $R_2=\left\{\right(a,4),(b,6),(c,4),(b,2\left)\right\}$
• $R_3=\left\{\right(a,6),(b,4),(c,2\left)\right\}$

Donde estos conjuntos de pares ordenados son subconjuntos de $A\times B$, estos subconjuntos tiene un nombre.

¿Que es el producto cartesiano?

También llamado no muy usualmente como conjunto producto y es el conjunto de todas combinaciones de pares ordenados de dos conjuntos dados tal que la primera componente pertenece a uno de los conjuntos y la segunda componente al siguiente conjunto. 

Se que es obvio pero igual vale mencionarlo (por si acaso), el producto cartesiano de dos conjuntos no tiene nada que ver con el producto de números naturales, excepto con su cardinal (numero de elementos) que indica cuantos pares ordenados hay en un producto cartesiano, pero esto ya lo veremos mas adelante.

Definición

Dados dos conjuntos $A$ y $B$, llamamos producto cartesiano $A\times B$ al conjunto de pares ordenados $(a,b)$ tal que $a\in A$ y $b\in B$, esto es:

$$A\times B=\left\{\right(a,b)|a\in A\wedge B\}$$

o en la forma proposicional:

$$(a,b)\in A\times B$$

Una consecuencia de esta definición es:

$$(a,b)\notin A\times B\leftrightarrow a\notin A\vee b\notin B$$

En efecto, si un par ordenado $(a,b)$ no pertenece al conjunto producto $A\times B$ es porque al menos existe un elemento que no pertenece al conjunto $A$ o al conjunto $B$.

También lo podemos definir como un conjunto potencia si usamos como definición conjuntista de par ordenado $(a,b)=\{\left\{a\right\},\{a,b\}\}$  que planteamos en la sección anterior, pero esta definición lo realizaremos al final de la sección actual para no traer confusiones al desarrollo del titulo.

Ejemplos

1. Sea los conjuntos $A=\{1,2\}$ y $B=\{a,b,c\}$, su  producto cartesiano es:
   $$A\times B=\left\{\right(1,a),(1,b),(1,c),(2,a),(2,b),(2,c\left)\right\}$$
   Lo podemos representar en un tablero de la siguiente manera:
   $$\begin{array}{ccc}c& (1,c)& (2,c)\\ b& (1,b)& (2,b)\\ a& (1,a)& (2,a)\\ A\times B& 1& 2\end{array}$$
   Una forma un poco elemental para determinar los elementos de un conjunto.
2. El producto cartesiano de $A=\{1,2,3\}$ y $B=\{4,5,6\}$ lo determinaremos con el siguiente tablero:
   $$\begin{array}{cccc}6& (1,6)& (2,6)& (3,6)\\ 5& (1,5)& (2,5)& (3,5)\\ 4& (1,4)& (2,4)& (3,4)\\ A\times B& 1& 2& 3\end{array}$$
   Del tablero, todos los pares ordenados del producto cartesiano es:
   $$A\times B=\left\{\right(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6\left)\right\}$$
   Por lo menos el tablero nos ayuda a completar todos los pares ordenados sin olvidar alguno, aunque generalmente trabajaremos con variables que con números.

                                    

 FUNCIONES

¿Qué es una función matemática?

Una función matemática (también llamada simplemente función) es la relación que hay entre una magnitud y otra, cuando el valor de la primera depende de la segunda.

Por ejemplo, si decimos que el valor de la temperatura del día depende de la hora a la que la consultemos, estaremos sin saberlo estableciendo entre ambas cosas una función. Ambas magnitudes son variables, pero se distinguen entre:

• Variable dependiente. Es la que depende del valor de la otra magnitud. En el caso del ejemplo, es la temperatura.
• Variable independiente. Es la que define la variable dependiente. En el caso del ejemplo es la hora.

De esta manera, toda función matemática consiste en la relación entre un elemento de un grupo A y otro elemento de un grupo B, siempre que se vinculen de manera única y exclusiva. Por lo tanto, dicha función puede expresarse en términos algebraicos, empleando signos de la siguiente manera:

f: A → B

a → f(a)

En donde A representa el dominio de la función (f), el conjunto de elementos de partida, mientras que B es el codominio de la función, o sea, el conjunto de llegada. Por f(a) se denota la relación entre un objeto arbitrario a perteneciente al dominio A, y el único objeto de B que le corresponde (su imagen).

Estas funciones matemáticas también pueden representarse como ecuaciones, acudiendo a variables y signos aritméticos para expresar la relación existente entre las magnitudes. Dichas ecuaciones, a su vez, podrán resolverse, despejando sus incógnitas, o bien ser graficadas geométricamente.

Tipos de funciones matemáticas

Las funciones matemáticas pueden clasificarse de acuerdo al tipo de correspondencia que se da entre los elementos del dominio A y los de B, teniendo así lo siguiente:

• Función inyectiva. Cualquier función será inyectiva si elementos distintos del dominio A se corresponden con elementos distintos del B, es decir, que ningún elemento del dominio se corresponde con la misma imagen de otro.
• Función sobreyectiva. Similarmente, hablaremos de una función sobreyectiva (o subyectiva) cuando a cada elemento del dominio A le corresponde una imagen en el B, incluso si ello implica compartir imágenes.
• Función biyectiva. Ocurre cuando una función es inyectiva y sobreyectiva a la vez, es decir, cuando a cada elemento de A le corresponde un único elemento de B, y no quedan en el codominio imágenes sin asociar, o sea, no hay elementos en B que no correspondan a uno en A.