Introducción de Conjuntos Numericos.

Conjuntos de números

¿Qué tiene esto que ver con matemáticas? Cuando definimos un conjunto, todo lo que hace falta es una propiedad común. ¿Quién dice que no se puede hacer lo mismo con números?

Conjunto de números pares: {..., -4, -2, 0, 2, 4, ...}
Conjunto de números impares: {..., -3, -1, 1, 3, ...}
Conjunto de números primos: {2, 3, 5, 7, 11, 13, 17, ...}
Múltiplos positivos de 3 que son menores que 10: {3, 6, 9}

Y la lista sigue. Podemos inventar muchos conjuntos distintos.
También hay conjuntos de números que no cumplen una propiedad común, simplemente se definen así. Por ejemplo:

{2, 3, 6, 828, 3839, 8827}
{4, 5, 6, 10, 21}
{2, 949, 48282, 42882959, 119484203}

Todos estos conjuntos los he escrito aporreando mi teclado sin mirar.

¿Por qué son importantes los conjuntos?

Los conjuntos son los ladrillos fundamentales de las matemáticas. Es verdad que los conjuntos, por sí solos, no parecen nada del otro mundo. Pero cuando los aplicas en distintas situaciones es cuando se convierten en los bloques con los que las matemáticas se construyen.

Las matemáticas se pueden complicar mucho rápidamente. Teoría de grafos, álgebra astracta, análises real, análisis complejo, álgebra lineal, teoría de números, y la lista sigue y sigue. Pero hay una cosa que todas estas partes de las matemáticas tienen en común: los conjuntos.

Las matemáticas se pueden complicar mucho rápidamente. Teoría de grafos, álgebra astracta, análises real, análisis complejo, álgebra lineal, teoría de números, y la lista sigue y sigue. Pero hay una cosa que todas estas partes de las matemáticas tienen en común: los conjuntos.

 

Conjunto universal

 

Igualdad

Dos conjuntos son iguales si tienen exactamente los mismos miembros. Quizás no parezcan iguales a primera vista, ¡tienes que mirarlos bien!

Ejemplos: Son A y B iguales si:

• A es el conjunto de los cuatro primeros enteros positivos
• B = {4, 2, 1, 3}

Vamos a verlo. Los dos contienen 1. Y 2. Y 3, y 4. Y ya hemos comprobado los elementos de los dos conjuntos, así que: ¡Sí, son iguales!

Y el signo igual (=) se usa precisamente para indicar igualdades, así que escribimos:

A = B

Subconjuntos

Cuando definimos un conjunto, si tomamos partes de él tenemos algo que se llama un subconjunto.
Así que por ejemplo tenemos el conjunto {1, 2, 3, 4, 5}. Un subconjunto suyo es {1, 2, 3}. Otro subconjunto es {3, 4} y otro es {1}. Sin embargo, {1, 6} no es un subconjunto, porque contiene un elemento (el 6) que no está en el conjunto grande. En general:

A es subconjunto de B si y sólo si cada elemento de A está en B.

Así que vamos a usar esta definición en algunos ejemplos.

¿Es A subconjunto de B, si A = {1, 3, 4} y B = {1, 4, 3, 2}?

1 está A, pero 1 también está en B. Por ahora bien. 2 está en B, pero no en A. Pero recuerda que eso no importa, sólo hay que mirar los elementos de A. 3 está en A y también en B. Falta uno más. 4 está A, y en B. Esos son todos los elementos de A, y están todos en B, así que ya está.

Vamos a intentar un ejemplo más difícil.

Sean A todos los múltiplos de 4 y B todos los múltiplos de 2. ¿Es A un subconjunto de B? ¿Es B un subconjunto de A?

Bueno, no se pueden comprobar todos los elementos de estos conjuntos, porque hay infinitos elementos. Así que tenemos que hacernos una idea de cómo son los elementos en cada uno, y comparar.
Para representar un múltiplo de 2, usamos 2n, donde n es un entero. Y hacemos lo mismo con los múltiplos de 4: son 4m, donde m es entero. Así que si tenemos un número 4m, ¿lo podemos escribir como un múltiplo de 2, con la forma 2n? ¡Claro que podemos!
Sabemos que 4 = 2*2, así que 4m = 2*2m, o mejor 2(2m). También sabemos que 2m es un entero. Así que vamos a llamar a = 2m, donde a es un entero. Entonces podemos decir que 4m = 2*2m = 2(2m) = 2(a). Como a es un entero, 2a es prácticamente lo mismo que 2n. Quiero decir, lo único que pasa es que usamos otra letra, pero no importa qué letra usemos. Así que A es un subconjunto de B.
¿Pero es B un subconjunto de A? Bueno, podemos probar a hacer lo mismo. Tenemos 2n y queremos que sea como 4m. Una manera de hacer eso sería multiplicarlo por 2 para que tengamos 2*2n o lo que es lo mismo 4n. Pero recuerda lo de arriba, sólo podemos usar el signo igual. Si multiplicas un número por 2, ya no es igual a lo que era. Así que nos hemos topado con un muro. No parece que 2n se pueda hacer parecido a 4m. ¿A lo mejor lo que queremos es falso? Vamos a probar lo contrario, a ver si es verdad que B no es subconjunto de A. ¿Cómo lo haríamos? Bueno, nos basta encontrar un elemento de B que no esté en A. Todo lo que hay que hacer es buscar un elemento así. Queremos un múltiplo de 2 que no sea múltiplo de 4. Pero de hecho, 2 es múltiplo de 2, pero no es múltiplo de 4. Así que 2 está en B pero no en A, y entonces B no es subconjunto de A.

Subconjuntos propios

Si nos fijamos en la definición de subconjunto y dejamos que nuestra mente trabaje un poco, llegamos a una conclusión rara. Digamos que A es un conjunto. ¿Es verdad que todo elemento a de A también es un elemento de A? Bueno, está claro que sí, ¿no? ¿Y eso no significa que A es un subconjunto de A? Esto no parece muy correcto, ¿no? Queremos que nuestros subconjuntos sean propios. Así que introducimos la definición de subconjuntos propios.
A es un subconjunto propio de B si y sólo si cada elemento de A está en B, y existe por lo menos un elemento de B que no está en A.
Esta pequeña parte del final es la que hace que A no sea un subconjunto propio de sí mismo. Por lo demás, un subconjunto propio es lo mismo que un subconjunto normal.

Así que por ejemplo, {1, 2, 3} es un subconjunto de {1, 2, 3}, pero no es un subconjunto propio de {1, 2, 3}.
Por otra parte, {1, 2, 3} es un subconjunto propio de {1, 2, 3, 4} porque el elemento 4 no está en el primer conjunto.

Fíjate en que si A es un subconjunto propio de B, entonces también es un subconjunto de B.

El conjunto vacío y subconjuntos

Volvamos a la definición de subconjunto. Tenemos un conjunto A. No decimos más de él, podría ser cualquier conjunto. ¿El conjunto vacío es subconjunto de A?
Volviendo a la definición de subconjunto, si todo elemento del conjunto vacío también está en A, entonces el conjunto vacío es subconjunto de A. ¿Pero y si no hay elementos?
Hay falta aprender algo de lógica para entender esto, pero esa frase es verdadera de manera "vacía" o "trivial". Piénsalo de esta manera: no podemos encontrar elementos en el conjunto vacío que no estén en A, así que todos los elementos del conjunto vacío están en A.
Así que la respuesta a la pregunta que hicimos es un sonoro sí.
El conjunto vacío es subconjunto de todos los conjuntos, incluido él mismo.

Cardinal

Todo conjunto tiene una propiedad asociada llamada cardinal. Es simplemente el tamaño del conjunto.
De la misma manera que hay conjuntos finitos e infinitos, estos tienen cardinal finito e infinito. Para conjuntos finitos, lo representamos con un número, el número de elementos. Por ejemplo, {1, 2, 3, 4} tiene cardinal 4. Sobre conjuntos infinitos, sólo podemos decir que tienen cardinal infinito. Aunque parezca raro, hay infinitos más grandes que otros, pero este es un tema avanzado en teoría de conjuntos.

Aristas y Vertices de un Grafo ,Grafos Eulerianos,Grafos Conexos.

INTRODUCCION

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
En este trabajo se tratará brevemente de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así como en la memoria.
En este trabajo, traté de ser lo más breve posible explicando de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado para su mayor entendimiento.
Dada esta pequeña introducción empezará el desarrollo del tema.

 

GRAFOS

CONCEPTO:

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.
Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.
La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.
Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.
Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
• Cruce: Son dos aristas que cruzan en un punto.

Vértices

Son los puntos o nodos con los que esta conformado un grafo.
Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
• Vértice Aislado: Es un vértice de grado cero.
• Vértice Terminal: Es un vértice de grado 1.

Caminos
Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

• x e y se llaman los extremos del camino
• El número de aristas del camino se llama la longitud del camino.
• Si los vértices no se repiten el camino se dice propio o simple.
• Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
• Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
• Llamaremos ciclo a un circuito simple
• Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

CLASIFICACION DE GRAFOS

Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Ejemplos
G1 = (V1, A1)
V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
G2 = (V2, A2)
V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}
G3 = (V3, A3)
V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

Algunos de los principales tipos de grafos son los que se muestran a continuación:

Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

A continuación pueden verse los dibujos de K3, K4, K5 y K6

Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

GRAFOS EULERIANOS.

Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes:

El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.

GRAFOS CONEXOS.

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.

ÁRBOLES.

Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).

BOSQUES DE ÁRBOLES.
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.

RECORRIDO DE UN GRAFO.
Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida.    Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.

• Recorrido en anchura:    El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
• Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.

REPRESENTACIÓN DE GRAFOS EN PROGRAMAS.
Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.

• Representación mediante matrices:   La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
• Representación mediante listas:    En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
• Representación mediante matrices dispersas:    Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.

DÍGRAFO (GRAFO DIRIGIDO).

A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.

APLICACIONES DE LOS DIGRAFOS
 
Una de las aplicaciones mas importantes es de hallar el camino mas corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de árboles, sirve para la representación de algoritmos, etc.
Un ejemplo de esto es la tarea de freír un huevo:

RESUMEN

Grafo
Conjunto ordenado de V y A, Vértices y Aristas, los cuales son sus principales componentes.
Vértice
Cada uno de los puntos de un grafo, también llamados nodos. Los diferentes tipos de vértices son:

• Vértice adyacente.
• Vértice Aislado.
• Vértice Inicial.

Arista.

Cada una de las líneas que unen a los vértices del grafo. Los diferentes tipos de aristas son:

• Aristas Adyacentes.
• Aristas Paralelas.
• Aristas Cíclicas.
• Cruces.

Camino.
Es un conjunto de vértices y aristas que llevan a un punto del grafo.
Clasificación de grafos.
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos.

Grafo regular: Aquel con el mismo grado en todos los vértices

Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto.

Grafo completo: Aquel con una arista entre cada par de vértices.

Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.

GRAFOS EULERIANOS.
Aquellos que contienen un camino euleriano.
GRAFOS CONEXOS
Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro.
ÁRBOLES
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo.
BOSQUES DE ÁRBOLES.
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.
RECORRIDO DE UN GRAFO.
Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida.  Las dos principales técnicas para recorrerlo son: recorrido en anchura y recorrido en profundidad.
DÍGRAFO (GRAFO DIRIGIDO).
A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas.

Isomorfismo de Grafos.

Isomorfismo de grafos

Dados G=(V,E) y G´=(V´,E´), se denomina isomorfismo de G a G´ a la aplicación biyectiva f  tal que para a,bÎV, {a,b}ÎE Û se cumple {f(a),f(b)}ÎE´. Es decir, la aplicación que relaciona biyectivamente pares de vértices de E con pares de vértices de E´, de modo que los vértices conectados por aristas siguen estándolo.

G y G´ se denominan isomorfos, y son matemáticamente iguales, solo varia la apariencia, o sea, que se mantienen las adyacencias, estructura, caminos y ciclos.

Los grafos G y G ‘ son isomorfos pues existe la biyección f: V ® V ‘ definida por f(a) = 2, f(b) = 1, f(c) = 3, f(d) = 4 que conserva la adyacencia.

Complejidad

Los problemas matemáticos se pueden dividir en primera instancia en dos grupos:

Ø      Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo.

Ø      Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo.

Sin embargo, que un problema sea decidible no implica que se pueda encontrar su solución, pues muchos problemas que disponen de algoritmos para su resolución son inabordables para un computador por el elevado número de operaciones que hay que realizar para resolverlos. Esto permite separar los problemas decidibles en dos:

Ø      intratables: aquellos para los que no es factible obtener su solución.

Ø      tratables: aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo razonable.

Los problemas pueden clasificarse también atendiendo a su complejidad. Aquellos problemas para los que se conoce un algoritmo polinómico que los resuelve se denominan clase P. Los algoritmos que los resuelven son deterministas. Para otros problemas, sus mejores algoritmos conocidos son no deterministas. Esta clase de problemas se denomina clase NP. Por tanto, los problemas de la clase P son un subconjunto de los de la clase NP, pues sólo cuentan con una alternativa en cada paso.

Tablas de Verdad.

Analizaremos las tablas de verdad asociadas a cada conectivo, para desarrollar ejemplos usando sus propiedades.
Objetivos

• Conocer y entender los conectivos lógicos
• Conocer y entender las tablas de verdad
• Aplicar las propiedades y resultados de los conectivos lógicos para resolver problemas

Proposiciones simples y compuestas

Recordamos que una proposición es una oración declarativa a la cual se le puede asociar un valor de verdad.

Para representar proposiciones usaremos las letras p, q, r,...
Por ejemplo
p = el sol brilla todo el día
q = hace frío son proposiciones simples.
Así como en álgebra las variables que representan cantidades pueden formar expresiones más complejas mediante el uso de las operaciones básicas de aritmética y algunas funciones, en lógica podemos relacionar proposiciones mediante los conectivos lógicos.
Los conectivos lógicos son símbolos usados para combinar proposiciones simples dadas, produciendo así otras llamadas proposiciones compuestas.
Los conectivos lógicos que usaremos son

• ~ negación
• disyunción
• conjunción
• condicionante
• bicondicionante

Tablas de Verdad.

Definimos una tabla de verdad como un arreglo que nos permite tener los posibles valores de verdad de una proposición compuesta a partir de los valores de verdad de las proposiciones simples.
Las tablas de verdad para los conectivos lógicos listados arriba son las siguientes:
Negación
La negación de una proposición es una nueva proposición que tiene un valor de verdad opuesto a la proposición original. Es decir, si el valor de verdad de una proposición p es verdadero, entonces el valor de verdad de ~p es falso.
La tabla de verdad para el conectivo ~ está dada por

p	~p
V	F
F	V

Disyunción
La disyunción es la proposición compuesta que resulta de conectar dos proposiciones, p y q, mediante el conectivo .
Esta proposición compuesta de denota por y se lee p o q.
La tabla de verdad para el conectivo está dada por

p	q
V	V	V
V	F	V
F	V	V
F	F	F

Se puede ver que para que una proposición compuesta tenga valor de verdad verdadero, basta con una de las proposiciones simples tenga valor de verdad verdadero.
Conjunción
La conjunción es la proposición compuesta que resulta de conectar dos proposiciones, p y q, mediante el conectivo .
Esta proposición compuesta de denota por y se lee p y q.
La tabla de verdad para el conectivo está dada por

p	q
V	V	V
V	F	F
F	V	F
F	F	F

Se puede ver que para que una proposición compuesta tenga valor de verdad verdadero, ambas proposiciones simples deben tener valor de verdad verdadero.
Condicionante
La condicional es la proposición compuesta que resulta de conectar dos proposiciones, p y q, mediante el conectivo .
Esta proposición compuesta de denota por y se lee p implica q.
En esta proposición compuesta, la proposición simple p se llama antecedente, mientras que la proposición simple q se llama consecuente.
La tabla de verdad para el conectivo está dada por

p	q
V	V	V
V	F	F
F	V	V
F	F	V

Se puede ver que una proposición compuesta tiene valor de verdad falso solamente cuando el antecedente es verdadero y el consecuente es falso. En cualquier otro caso, el valor de verdad de la proposición compuesta es verdadero.
Bicondicionante
La bicondicional es la proposición compuesta que resulta de conectar dos proposiciones, p y q, mediante el conectivo .
Esta proposición compuesta se denota por y se lee p si y solo si q.
La tabla de verdad para el conectivo está dada por

p	q
V	V	V
V	F	F
F	V	F
F	F	V

Se puede ver que la proposición compuesta tiene valor de verdad verdadero siempre que las proposiciones simples tienen el mismo valor de verdad. Es cualquier otro caso, la proposición compuesta tiene valor de verdad falso.


Las proposiciones compuestas pueden combinarse o conectarse para formar proposiciones aún más complejas. Es claro que el valor de verdad de una proposición, por compleja que sea, depende de los valores de verdad de las proposiciones que las componen en sus formas más simples.
Para hacer la tabla de verdad de una proposición le asignamos una columna a cada proposición que interviene, sea ésta simple o compuesta, normalmente comenzando con las más simples y progresando en el orden de complejidad de las proposiciones componentes.
El número de filas de la tabla viene dado por la potencia , donde es el número de proposiciones en la forma más simple que forman la proposición compuesta dada.

Tipos de Grafos.

Tipos de grafos

• Grafo simple. o simplemente grafo es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.

• Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

• Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha

• Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.

• Grafo aleatorio. Grafo cuyas aristas están asociadas a una Probabilidad.

• Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

• Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Se dice que el grafo G = (V, E) es

a)      un grafo regular de grado n si todos sus vértices tienen grado n.

Grafos regulares de grado 2.

Grafos regulares de grado 3.

b)      un grafo completo si cada par de vértices está unido por una arista. Se denota por K_n al grafo completo de n vértices

c)      un ciclo si V = {v₁, v₂, . . . v_n},  n³> 3, y  E = {(v₁, v₂), (v₂, v₃), . . . , (v_n, v₁)}. Se denota por C_n al ciclo de n vértices

d)      una rueda si V = {v₀, v1, v₂, . . . v_n}, n n> 3, y E = {(v₁, v₂), (v₂, v₃), . . . , (v_n, v₁), {(v₁, v₀), (v₂, v₀), . . . , (v_n, v₀) }. Se denota por W_n a la rueda de n+1 vértices

e)      un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Q_n al cubo asociado al cubo n-dimensional.

f)        un grafo bipartido si V=V₁UV₂ y cada arista de E une un vértice de V₁ y otro de V₂

 

g)      un grafo bipartido completo si V=V₁UV₂ y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V₁ y el otro en V₂. Se denota por K_r,s al grafo bipartido completo donde V₁ tiene r vértices y V₂ tiene s vértices

 

Ejemplo 1.3.2. Una red de n ordenadores conectados a una unidad central estarían dispuestos formando un grafo del tipo W_n. Por otra parte, en un ordenador que tenga múltiples procesadores para efectuar procesamiento en paralelo, en el caso de que tenga n² procesadores, estos se pueden conectar formando una red en forma de cuadrilátero, aunque una de las formas de conexión más importantes es la de 2ⁿ ordenadores según el grafo Q_n.

 

Definición 1.3.3. Un digrafo o grafo dirigido es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados de vértices a cuyos elementos llamaremos aristas o arcos.

Al par (u, v)eE lo denotaremos por uv y diremos que u es el extremo inicial y que v es el extremo final.

 

V={u, v, w, x, y, z}

E={ uu, vu, vw, vy, xv, xw, yz, zy }

 

Un digrafo simple es un par D = (V, E) consistente en un conjunto finito no vacío V cuyos miembros se llaman vértices y una familia finita E de pares ordenados distintos de vértices distintos a cuyos elementos llamaremos aristas o arcos.

 

Definición 1.3.4. Dado un digrafo D = (V, E), se llama grado de entrada de un vértice al número de arcos que lo tienen por extremo final y se llama grado de salida de un vértice al numero de arcos que lo tienen por extremo inicial.

Tipos de Bucles.

Tipos de Bucles

Existen 4 tipos de bucles para PHP, estos son:

1. While
2. Do...While
3. For
4. Foreach

Cada uno de ellos tiene su sintaxis y su uso específico. Cada uno estará explicado detalladamente luego.
While

Su funcionamiento es sencillo, ya que primero se evalúa que la condición sea verdadera y luego se ejecuta, hasta que la condición pase a ser falsa; una sentencia while (Español: Mientras) puede que no se ejecute ni siquiera una vez, si su condición es inicialmente falsa.
Veamos un ejemplo de su uso:

<?php
  $i = 1;
  while($i <= 3)  $i += 1;
  echo 'La variable $i vale: ' . $i ;
?>

Salida:

La variable $i vale: 4

Esta sintaxis de la instrucción while solo permite el uso de una sentencia dentro del bucle, en el ejemplo anterior la sentencia $i += 1  es la única que se repite.

Un bucle while puede contener varias sentencia, encerrándolas entre llaves ({}) o usando ésta sintaxis alternativa:

 while (condición): 
   sentencia; 
   sentencia;
   .
   .
   .
   sentencia; 
 endwhile;

Do...While

Su uso es similar a while, pero aquí, las sentencias que siguen al do (Español: Hacer) se ejecutan por lo menos una vez y se comprueba la condición luego de la primera iteración; así, si es verdadera la condición se repite por segunda vez, si es falsa se continúa con las sentencias inmediatamente después de la instrucción while. Tiene sólo una sintáxis.

Sintáxis:


do {
  sentencia;
  sentencia;
  .
  .
  .
  sentencia;
} while (condición);


Todo lo explicado referente al bucle while se aplica también al do...while, sin embargo la principal diferencia con este es que el do...while siempre ejecuta al menos la primera iteración, mientras que en el while pudiera no ejecutar ninguna iteración, esto ocurre si la condición es falsa desde antes del inicio del bucle.

Un ejemplo con do...while:


 <?php
  $i = 5;
  $n = 1;
  do {
    $n = $n * $i;
    $i -= 1;
  }while($i > 1);
  echo "5! es igual a: " . $n
 ?>



Salida



5! es igual a: 120

Claro que, si cambiamos la primera instrucción por $i = 0 el bucle se ejecutará al menos una vez, pues la condición se evalúa al final, y dará la salida (errónea):

0! es igual a : 0
 
 
 
For
 
Los bucles for (Español: Para) son los más complejos en PHP (y en otros lenguajes de programación). Su sintaxis es la siguiente:

Sintáxis:




 for (inicialización; condición; actualización) sentencia;



Inicialización: Es una expresión que ejecuta una sola vez al inicio y predetermina el primer valor inicial, mas comúnmente asignado a una variable ejemplo:


:$i = 1;



Condición: Es una expresión que se evalúa como falsa o verdadera, si es falsa el bucle finaliza, en caso contrario el bucle ejecuta la sentencia ejemplo:


:$i <= 5;



Actualización: Es una expresión que modifica la expresión de inicialización comúnmente en incremento o decremento Ejemplo:


:$i += 1



Nota: Observe que en esta ultima expresión no lleva (;).
 
 
Foreach




Introducido en PHP 4 es una solución fácil para trabajar con arreglos, muy semejante a Perl y otros lenguajes, funciona solo en arreglos y presentara un error al utilizar una variable con diferente tipo o no inicializada. Existen dos sintaxis la segunda opción en menor pero tiene mejor uso que la primera.

Sintáxis:




<p>foreach</p>
 foreac<html>
<body>h (expresión_arreglo as $valor)
     sentencia



 foreach (expresión_arreglo as $llave => $valor)
     sentencia
</body>
</html>



En la primera forma los ciclos sobre el arreglo están dados por expresión_arreglo. En cada ciclo, el valor del elemento actual se asigna internamente a $valor y el puntero interno del arreglo avanza en uno de tal forma que en el siguiente ciclo vera el siguiente elemento.

La segunda forma es la misma cosa, salvo que la clave del elemento actual se asigna a la variable $llave en cada bucle.

A partir de PHP 5, también es posible iterar objetos.

Nota: Cuando foreach inicia por primera vez su ejecución, el puntero interno del arreglo reinicia automáticamente en el primer elemento del arreglo. Esto significa que este necesita llamar a reset() antes de un blucle foreach.

Nota: A menos que el arreglo sea referenciado, foreach opera en una copia de el arreglo especifico y no en el propio arreglo. foreach tiene algunos efectos laterales en el puntero del arreglo. No se cuenta con un puntero del arreglo durante o después del foreach sin reiniciarlo.