estructuras discretas

CONJUNTOS

Un conjunto es una colección bien definida de objetos, entendiendo que dichos objetos pueden ser cualquier cosa: números, personas, letras, otros conjuntos, etc. Algunos ejemplos son:
A es el conjunto de los números naturales menores que 5. es el conjunto de los colores verde, blanco y rojo. es el conjunto de las vocales a, e, i, o y u. es el conjunto de los palos de la baraja francesa.Los conjuntos se denotan habitualmente por letras mayúsculas. Los objetos que componen el conjunto se llaman elementos o miembros. Se dice que «pertenecen» al conjunto y se denota mediante el símbolo ∈:[n 1] la expresión a ∈A se lee entonces como «a está en A», «a pertenece a A», «A contiene a a», etc. Para la noción contraria se usa el símbolo ∉. Por ejemplo:
3 ∈ A , ♠ ∈ Damarillo ∉ B, z ∉ CEn matemáticas, un conjunto es una colección de elementos considerada en sí misma como un objeto. Los elementos de un conjunto, pueden ser las siguientes:personas, números, colores, letras,figuras, etc. Se dice que un elemento (o miembro) pertenece al conjunto si está definido como incluido de algún modo dentro de él.
Ejemplo: el conjunto de los colores delarcoíris es:
AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta}Un conjunto suele definirse mediante una propiedad que todos sus elementos poseen. Por ejemplo, para los números naturales, si se considera la propiedad de ser un número primo, el conjunto de los números primos es:
P = {2, 3, 5, 7, 11, 13, ...}Un conjunto queda definido únicamente por sus miembros y por nada más. En particular, un conjunto puede escribirse como una lista de elementos, pero cambiar el orden de dicha lista o añadir elementos repetidos no define un conjunto nuevo. Por ejemplo:
S = {Lunes, Martes, Miércoles, Jueves, Viernes} = {Martes, Viernes, Jueves, Lunes, Miércoles}AI = {Rojo, Naranja, Amarillo, Verde, Azul, Añil, Violeta} = {Amarillo, Naranja, Rojo, Verde, Violeta, Añil, Azul}Los conjuntos pueden ser finitos oinfinitos. El conjunto de los números naturales es infinito, pero el conjunto de los planetas en el Sistema Solar es finito (tiene ocho elementos). Además, los conjuntos pueden combinarse medianteoperaciones, de manera similar a lasoperaciones con números.
Los conjuntos son un concepto primitivo, en el sentido de que no es posible definirlos en términos de nociones más elementales, por lo que su estudio puede realizarse de manera informal, apelando a la intuición y a la lógica. Por otro lado, son el concepto fundamental de la matemática: mediante ellos puede formularse el resto de objetos matemáticos, como los números y lasfunciones, entre otros. Su estudio detallado requiere pues la introducción de axiomas y conduce a la teoría de conjuntos.
Notación

El conjunto Aes un conjunto de polígonos. En la imagen, algunas de las figuras pertenecen a dicho conjunto, pero otras no.

Existen varias maneras de referirse a un conjunto. En el ejemplo anterior, para los conjuntos A y D se usa una definición intensiva o por comprensión, donde se especifica una propiedad que todos sus elementos poseen. Sin embargo, para los conjuntos B y C se usa una definición extensiva, listando todos sus elementos explícitamente.
Es habitual usar llaves para escribir los elementos de un conjunto, de modo que:
B = {verde, blanco, rojo}C = {a, e, i, o, u}Esta notación mediante llaves también se utiliza cuando los conjuntos se especifican de forma intensiva mediante una propiedad:
A = {Números naturales menores que 5}D = {Palos de la baraja francesa}Otra notación habitual para denotar por comprensión es:
A = {m : m es un número natural, y 1 ≤ m ≤ 5}D = {p : p es un palo de la baraja francesa}F = {n2 : n es un entero y 1 ≤ n ≤ 10},En estas expresiones los dos puntos («:») significan «tal que». Así, el conjunto F es el conjunto de «los números de la forman2 tal que n es un número natural entre 1 y 10 (ambos inclusive)», o sea, el conjunto de los diez primeros cuadradosde números naturales. En lugar de los dos puntos se utiliza también la barra vertical («|») u oblicua «/» .
Igualdad de conjuntos

El conjunto de «personas» mostrado en la imagen, A, tiene 8 miembros. Este conjunto puede representarse mediante llaves o mediante un diagrama de Venn. El orden de las personas en A es irrelevante.

Un conjunto está totalmente determinado por sus elementos. Por ello, la igualdad de conjuntos se establece como:
Propiedad de laintencionalidad
Dos conjuntosA y B que tengan los mismos elementos son el mismo conjunto, A =B.Esta propiedad tiene varias consecuencias. Un mismo conjunto puede especificarse de muchas maneras distintas, en particular extensivas o intensivas. Por ejemplo, el conjunto A de los números naturales menores que 5 es el mismo conjunto que A′, el conjunto de los números 1, 2, 3 y 4. También:
B = {verde, blanco, rojo} = {colores de la bandera de México}C = {a, e, i, o, u} = {vocales delespañol}D = {Palos de la baraja francesa} = {♠, ♣, ♥, ♦}El orden en el que se precisan los elementos tampoco se tiene en cuenta para comparar dos conjuntos:
B = {verde, blanco, rojo} = {rojo, verde, blanco}C = {a, e, i, o, u} = {e, i, u, a, o}Además, un conjunto no puede tener elementos «repetidos», ya que un objeto solo puede o bien ser un elemento de dicho conjunto o no serlo. Se da entonces que, por ejemplo:
{1, 2} = {1, 2, 1}En ausencia de alguna característica adicional que distinga los «1» repetidos, lo único que puede decirse del conjunto de la derecha es que «1» es uno de sus elementos.
Conjunto vacío

Artículo principal: Conjunto vacío

El conjunto que no contiene ningún elemento se llama el conjunto vacío y se denota por ∅ o simplemente {}. Algunasteorías axiomáticas de conjuntosaseguran que el conjunto vacío existe incluyendo un axioma del conjunto vacío. En otras teorías, su existencia puede deducirse. Muchas posibles propiedades de conjuntos son trivialmente válidas para el conjunto vacío.
Propiedades[editar]
En la teoría de conjuntos axiomáticaestándar, por el Axioma de estacionalidad, dos conjuntos son iguales si tienen los mismos elementos; por lo tanto sólo puede haber un conjunto sin ningún elemento. Por consiguiente, sólo hay un único conjunto vacío, y hablamos de "el conjunto vacío" en lugar de "un conjunto vacío".
Para cualquier conjunto :
(Ver operaciones con conjuntos)
El conjunto vacío es unsubconjunto de :
La unión de con el conjunto vacío es :
La intersección de con el conjunto vacío es el conjunto vacío:
El producto cartesiano de A y el conjunto vacío es el conjunto vacío:
El conjunto vacío tiene las siguientes propiedades:
Su único subconjunto es el propio conjunto vacío:
El "conjunto de poder" del conjunto vacío es el conjunto que contiene únicamente el conjunto vacío:
Su número de elementos (cardinalidad) es cero:
(La lista de símbolos matemáticos empleados se encuentra aquí).Subconjuntos

Artículo principal: Subconjunto

B es un subconjunto de A(en particular un subconjunto propio).

Un subconjunto A de un conjunto B, es un conjunto que contiene algunos de los elementos de B (o quizá todos):
Un conjuntoA es undel conjuntoB si cada elemento deA es a su vez un elemento de B.Cuando A es un subconjunto de B, se denota como A ⊆ B y se dice que «A está contenido en B». También puede escribirse B ⊇ A, y decirse que B es un de A y también «Bcontiene a A» o «B incluye a A».
Todo conjunto A es un subconjunto de sí mismo, ya que siempre se cumple que «cada elemento de A es a su vez un elemento de A». Es habitual establecer una distinción más fina mediante el concepto de : A es un subconjunto propio de B si es un subconjunto de B pero no es igual a B. Se denota como A ⊊ B, es decir: A ⊆ B peroA ≠ B (y equivalentemente, para un súper conjunto propio, B ⊋ A).[n 2]
Ejemplos.
El «conjunto de todos los hombres» es un subconjunto propio del «conjunto de todas las personas».{1, 3} ⊊ {1, 2, 3, 4}{1, 2, 3, 4} ⊆ {1, 2, 3, 4}Conjuntos disjuntos

Artículo principal: Conjuntos disjuntos

Dos conjuntos A y B son disjuntos si no tienen ningún elemento en común. Por ejemplo, los conjuntos de los números racionales y los números irracionales son disjuntos: no hay ningún número que sea a la vez racional e irracional. Laintersección de dos conjuntos disjuntos es el conjunto vacío.
Cardinalidad

Artículo principal: Número cardinal

Los conjuntos pueden ser finitos oinfinitos. En el caso de un conjunto finito se pueden contar los elementos del conjunto:
El número de elementos de un conjunto finito es su.El cardinal se denota por |A|, card(A) o #A. Así, en los ejemplos anteriores, se tiene que |A| = 4 (cuatro números), |B| = 3 (tres colores) y |F| = 10 (diez cuadrados). El único conjunto cuyo cardinal es 0 es elconjunto vacío ∅.
Existen, a su vez, determinadas. Si tomamos como ejemplo dos conjuntos,  y :
Y en el caso de tres conjuntos, ,  y :
En un conjunto infinito no hay un número finito de elementos. Es el caso por ejemplo de los números naturales:  = {1, 2, 3, ...}. Sin embargo, existe una manera de comparar conjuntos infinitos entre sí, y se obtiene que existen conjuntos infinitos «más grandes» que otros. El «número de elementos» de un conjunto infinito es unnúmero transfinito.
Cardinalidad de los reales

Artículo principal: Número real

Uno de los resultados más importantes de Georg Cantor fue que la cardinalidad de los reales () es más grande que la de los números naturales (). Esto es, que hay más números reales que números enteros . Concretamente, Cantor mostró que
La hipótesis del continuo afirma que no existen conjuntos con cardinalidades intermedias entre los naturales y losreales:
No existe ningún conjunto Atal que su cardinal |A| cumpla:Si se asume el axioma de elección, la estructura de los cardinales infinitos es más clara: todos los cardinales infinitos son álefs y están bien ordenados, por lo que existe sólo un cardinal inmediatamente superior a ℵ0, denotado por ℵ1
El cardinal del conjunto de los números reales es el inmediatamente superior al cardinal de los números naturales:Operaciones con conjuntos

Operaciones con conjuntos

Unión

Intersección

Diferencia

Complemento

Diferencia simétrica

Artículo principal: Álgebra de conjuntos

Existen varias operaciones básicas que pueden realizarse para, partiendo de ciertos conjuntos dados, obtener nuevos conjuntos:
: (símbolo ∪) La uniónde dos conjuntos A y B, que se representa como A ∪ B, es el conjunto de todos los elementos que pertenecen al menos a uno de los conjuntosA y B.: (símbolo ∩) Laintersección de dos conjuntosA y B es el conjunto A ∩ B de los elementos comunes a A yB.: (símbolo \) Ladiferencia del conjunto A con Bes el conjunto A \ B que resulta de eliminar de Acualquier elemento que esté en B.: Elcomplemento de un conjuntoA es el conjunto A∁ que contiene todos los elementos que no pertenecen a A, respecto a un conjunto U que lo contiene.: (símbolo Δ) La diferencia simétrica de dos conjuntos A y B es el conjunto A Δ B con todos los elementos que pertenecen, o bien a A, o bien a B, pero no a ambos a la vez.: (símbolo ×) El producto cartesiano de dos conjuntos A y B es el conjunto A × B de todos lospares ordenados (a, b)formados con un primer elemento a perteneciente a A,

Funciones proposicionales

Supongamos los enunciados abiertos:

" x es la capital de Buenos Aires"

" y + 4 = 11"

Estos no tienen un valor veritativo. Pero si en el primero de ellos hacemos x = La Plata, tenemos:

"La Plata es la capital de Buenos Aires" (V)

Asimismo, si en el segundo hacemos x = 9, resulta: 9 + 4 = 11 (F)

Podemos, entonces, dar la siguiente definición: "Una función proposicional es un enunciado abierto de la forma P(x) que se convierte en una proposición cuando se le asigna un valor específico a la variable".

Ejemplos:

p(x) : 2x + 5 > 11 , si x = 4 \ 13 > 11 (Verdadero)

q(x) : 3x + 7 = 11 , si x = 5 \ 22 = 16 (Falso)

r(x) : 2x + 1 = 5 , si x = 2 \ 5 = 5 (Verdadero)

s(x) : x es un animal, si x = mesa se tendrá : mesa es un animal (Falso)

t(x) : x es un ave, si x = flamenco se tiene: el flamenco es un ave (Verdadero)

CUANTIFICADORES

A partir de funciones proposicionales es posible obtener proposiciones generales mediante un proceso llamado de cuantificación. Asociados a la indeterminada x, introducimos los símbolos " x y $ x, llamados cuantificador universal y cuantificador existencial respectivamente. Las expresiones

Para todo x, se verifica p(x) se denota por " x : p(x)

Existe x, tal que se verifica p(x) se denota por $ x / p(x)

Corresponden a una función proposicional p(x) cuantificada universalmente en el primer caso, y existencialmente en el segundo.

Ejemplo: Una función proposicional cuantificada universalmente es V si y sólo si son V todas las proposiciones particulares asociadas a aquella. Para asegurar la verdad de una proposición cuantificada universalmente es suficiente que sea verdadera alguna de las proposiciones asociadas a la función proposicional.

Un problema de interés es la negación de funciones proposicionales cuantificadas. Por ejemplo, La negación de "Todos los enteros son impares" es "Existen enteros que no son impares" y en símbolos: $ x / ~ p(x)

Entonces, para negar una función proposicional cuantificada universalmente se cambia el cuantificador en existencial, y se niega la función proposicional.

Ejemplo: Supongamos la proposición: Todos los alumnos de mi colegio son aplicados

La vamos a escribir en lenguaje simbólico, negarla y retraducir la negación al lenguaje ordinario.

Nos damos cuenta pronto que se trata de la implicación de dos funciones proposicionales:

p(x) : es alumno de mi colegio

q(x) : es aplicado

Tenemos: " x : p(x) Þ q(x)

Teniendo en cuenta la forma de negar una función proposicional cuantificada universalmente y una implicación resulta:

$ x / p(x) Ù ~ q(x)