Los sistemas numéricos son muy importantes en computación, aquí veremos los sistemas en base 2, 8 y 16 que son las que más se utilizan en computación; por supuesto con la relación entre la base 10 que es la que utilizamos los seres humanos.
SISTEMAS DE NUMERACIÓN
Un sistema de numeración es un conjunto de símbolos y reglas que se utilizan para representar y operar con cantidades. Sistemas Aditivos:
Los sistemas aditivos son aquellos que acumulan los simbolos de todas las unidades, decenas… como sean necesarios hasta completar el número. Una de sus características es por tanto que se pueden poner los símbolos en cualquier orden, aunque en general se ha preferido una determinada disposición. Han sido de este tipo las numeraciones egipcia, sumeria (de base 60), hitita, cretense, azteca (de base 20), romana y las alfabéticas de los griegos, armenios, judios y árabes.
Sistema Egipcio
Desde el tercer milenio A.C. los egipcios usaron un sistema deescribir los números en base diez utilizando los geroglíficos de la figura para representar los distintos ordenes de unidades.
Sistema Griego:
El primer sistema de numeración griego se desarrolló hacia el 600 A.C. Era un sistema de base decimal que usaba los símbolos de la figura siguiente para representar esas cantidades.
Para representar la unidad y los números hasta el 4 se usaban trazos verticales. Para el 5, 10 y 100 las letras correspondientes a la inicial de la palabra cinco (pente), diez (deka) y mil (khiloi). Por este motivo se llama a este sistema acrofónicos.
Sistemas Híbridos
En estos sistemas se combina el principio aditivo con el multiplicativo.
Sistema Chino:
La forma clásica de escritura de los números en China se empezó a usar desde el 1500 A.C. aproximadamente. Es un sistema decimal estricto que usa las unidades y las distintas potencias de 10. Utiliza los ideogramas de la figura:
y usa la combinación de los números hasta el diez con la decena, centena, millar y decena de millar para según el principio multiplicativo representar 50, 700 ó 3000. El orden de escritura se hace fundamental, ya que 5 10 7 igual podría representar 57 que 75.
Sistema Babilónico:
Entre la muchas civilizaciones que florecieron en la antigua Mesopotámica se desarrollaron distintos sistemas de numeración. En el ssss A.C. se inventó un sistema de base 10, aditivo hasta el 60 y posicional para números superiores
Sistema Maya
Los mayas idearon un sistema de base 20 con el 5 cómo base auxiliar. La unidad se representaba por un punto. Dos, tres, y cuatro puntos servían para 2, 3 y 4. El 5 era una raya horizontal, a la que se añadían los puntos necesarios para representar 6, 7, 8 y 9. Para el 10 se usaban dos rayas, y de la misma forma se continúa hasta el 20, con cuatro rayas.
Un sistema de numeración es un conjunto de reglas y símbolos que permiten representar de forma única los números. Esta representación posibilita la realización de sencillos algoritmos para la ejecución de operaciones aritméticas.
Los sistemas de numeración usados en la actualidad son posiciónales. El valor de una cifra depende tanto de qué dígito es como de la posición que ocupa en el número. Base: Es el número de símbolos distintos que se utiliza para representar un número en un sistema de numeración. Entonces decimos que el sistema de numeración es de esa base. Los símbolos de una determinada base van desde el 0 hasta la base b-1.
Coeficiente: El coeficiente determina el valor de cada símbolo dependiendo de la posición que ocupe con respecto al punto decimal. Por lo tanto a estos sistemas de numeración los llamaremos sistemas de numeración posiciónales, porque el valor de cada cifra dependerá del valor absoluto del símbolo y de la posición relativa que ocupa con respecto al punto decimal.
Los sistemas de numeración actuales son sistemas posiciónales, en los que el valor que representa cada símbolo o cifra, depende de su valor absoluto y de la posición relativa que ocupa la cifra con respecto al resto.
En los sistemas de numeración existe un elemento característico que define el sistema y se denomina base, siendo ésta el número de símbolos que se utilizan para la representación.
Se entiende por base (b) de un sistema de numeración al número de símbolos que se utilizan para la representación. Todos los sistemas usados actualmente usan una base n. En un sistema de numeración de base n existen n símbolos. Al escribir un número en base n, el dígito d en la posición i, de derecha a izquierda, tiene un valor.
En general, un número escrito en base n como dmdm − 1…d2d1 tiene un valor
El sistema decimal:
El sistema de numeración decimal es un sistema posicional. La base del sistema de numeración decimal es 10 y está formado por los dígitos del 0 al 1. Un número en el sistema de numeración decimal lo podemos definir según el teorema fundamental de la numeración de la siguiente forma. Numerob= x0b0+ x1b1 + x2b2 + …. + xn-1bn-1 xi = cifras b = datos n = número de cifras
El sistema binario:
El sistema binario o sistema de numeración en base 2 es también un sistema de numeración posicional igual que el decimal, pero sólo utiliza dos símbolos, el “0” y el “1”. Por lo tanto para poder representar mayor número de información al tener menos símbolos tendremos que utilizar más cifras
§ Cuarteto: Número formado por 4 cifras en base 2 § Bit: Bynary digit § Byte: 8 bits § Kilobyte: 1024 bytes § Megabyte: 1024 kilobytes § Gigabyte: 1025 megabytes
Binario puro
El método de representación de enteros del binario puro consiste en pasar el número entero sin signo a binario, con la particularidad de respetar siempre el tamaño de la representación.
El paso de decimal a binario consiste en dividir por 2 sucesivamente hasta que el cociente sea menor que la base: Con lo que queda 1110 = 10112
Sistema Octal:
Es un sistema de base 8, es decir, con tan solo ocho dígitos posibles, ‘0’ a ‘7’. El paso de octal a decimal se realiza multiplicando cada dígito por su peso: 278 = 2 •81 + 7 • 80 = 2310 El paso inverso consiste en dividir por la base (8): Con lo que queda 678 = 10310
Sistema Hexadecimal:
Sin embargo el sistema de numeración más utilizado es el hexadecimal, el cual consta de 16 dígitos diferentes {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}.
El paso de hexadecimal a decimal es análogo a los anteriores: 12316 = 1 • 162 + 2 • 161 + 3 • 160 = 29110 Al igual que el paso de decimal a hexadecimal: Con lo que queda 2910 = 12316
lunes, 7 de diciembre de 2009
Arboles Generadores
Un árbol T, subgrafo de un grafo G que contenga todos los vértices de G se denómina Arbol Generador de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es asi como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.
ARBOLES GENERADORES
Debido a que los arboles son estructuras mas simples de manejar que los grafos, es conveniente cuando tenemos un grafo conexo, construir un árbol que contenga todos los nodos: de esta forma es posible visitar todos los nodos con una estructura mas eficiente y donde es posible visitar todos los nodos con una estructura mas eficiente y donde es posible implementar de una forma mas directa los algoritmo para el manejo de la información.
Definición: un árbol generador T de un grafo conexo G un árbol que es subgrafo de G y que contiene todos los nodos.
un árbol generador es: T1=( ( a,b), (a,d),(b,c),(c,f),(d,e) ) El cual lo podríamos dibujar
También el árbol T2 es otro árbol generador T2= ( (b,a),(b,c),(b,c),(b,e),(c,f) )
El cual se puede representar como
Hay varias formas de crear los arboles generadores, dos de las mas comunes e importantes son las de los algoritmos.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es asi como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.
ARBOLES GENERADORES
Debido a que los arboles son estructuras mas simples de manejar que los grafos, es conveniente cuando tenemos un grafo conexo, construir un árbol que contenga todos los nodos: de esta forma es posible visitar todos los nodos con una estructura mas eficiente y donde es posible visitar todos los nodos con una estructura mas eficiente y donde es posible implementar de una forma mas directa los algoritmo para el manejo de la información.
Definición: un árbol generador T de un grafo conexo G un árbol que es subgrafo de G y que contiene todos los nodos.
un árbol generador es: T1=( ( a,b), (a,d),(b,c),(c,f),(d,e) ) El cual lo podríamos dibujar
También el árbol T2 es otro árbol generador T2= ( (b,a),(b,c),(b,c),(b,e),(c,f) )
El cual se puede representar como
Hay varias formas de crear los arboles generadores, dos de las mas comunes e importantes son las de los algoritmos.
Propiedades De Los Arboles
Arboles
Son un tipo especial de grafo.
G es un grafo, no digrafo sin bucles. G es un arbol si es conexo y no tiene ciclos.
Arboles degenerados: Arbol con un solo vertice y sin lados.
Arbol maximal: T es un arbol maximal de un grafo G conexo, si es un arbol y contiene todos los vertices de G.
Teorema 1: Si a y b son dos vertices distintos de un arbol, entonces existe un unico camino elemental que conecta dichos vertices.
Teorema 2: T es un arbol cualquiera, entonces
v=E+1.
Teorema 3: T es un arbol con
v”2, se verifica que tiene almenos dos vertices terminales.
Son un tipo especial de grafo.
G es un grafo, no digrafo sin bucles. G es un arbol si es conexo y no tiene ciclos.
Arboles degenerados: Arbol con un solo vertice y sin lados.
Arbol maximal: T es un arbol maximal de un grafo G conexo, si es un arbol y contiene todos los vertices de G.
Teorema 1: Si a y b son dos vertices distintos de un arbol, entonces existe un unico camino elemental que conecta dichos vertices.
Teorema 2: T es un arbol cualquiera, entonces
v=E+1.
Teorema 3: T es un arbol con
v”2, se verifica que tiene almenos dos vertices terminales.
Arboles
Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc… Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles.
Una forma particular de árbol puede ser la estructura vacía. Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo. Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R. En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A),
V= A+ 1.
Teorema:
Para cualquier árbol R = (V,A), si
A
›= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, …, vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, …, v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si
V › 1, sean R1, R2, R3, …., Rk los subarboles de R según se va de izquierda a derecha.
El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.
El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,…., Rk en orden simétrico.
El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,…., Rk en orden posterior y a continuación por la raíz.
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.
Teorema:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.
Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
Una forma particular de árbol puede ser la estructura vacía. Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo. Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R. En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A),
V= A+ 1.
Teorema:
Para cualquier árbol R = (V,A), si
A
›= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, …, vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, …, v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si
V › 1, sean R1, R2, R3, …., Rk los subarboles de R según se va de izquierda a derecha.
El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.
El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,…., Rk en orden simétrico.
El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,…., Rk en orden posterior y a continuación por la raíz.
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.
Teorema:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.
Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
Representacion De Estructura Mediante Grafos
Uno de los aspectos más importantes en computación es la programación. Para elaborar un programa es conveniente tener una forma de representar las ideas antes de elaborar el código. Aquí presentamos una aplicación de los grafos en la representación de los conceptos básicos de diagramas de flujo. Por supuesto que los diagramas de flujo son mucho más generales que su uso en programación y pueden ser utilizados para muchas otras aplicaciones.
Clasificacion De Grafos
Los grafos se pueden clasificar 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> }
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. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior o 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. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior
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.
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> }
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. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior o 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. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior
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.
Conceptos Basicos De Grafos
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
→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
Introduccion a La Teoria De Grafos
Problema de los Puentes de Könisberg
Definición: Un grafo G = (N,A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos. Una arista en general se representa por {a,b}.
Una forma de represtar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.
Ejemplo: G = { n1, n2, n3,n4,n5, n6, n7,n8 } , A = { {n1, n2}}, {n1, n5},{n2, n3},{n3, n4} , {n4, n7}, {n2, n6},{n6, n2} } Outline del contenido
Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo a1(n2, n6) , a2(n2, n6) son dos aritas para unir los nodos n2 y n6. También puede ser que en un arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n1, n2). Valencias
Definición: Un grafo G = (N,A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos. Una arista en general se representa por {a,b}.
Una forma de represtar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.
Ejemplo: G = { n1, n2, n3,n4,n5, n6, n7,n8 } , A = { {n1, n2}}, {n1, n5},{n2, n3},{n3, n4} , {n4, n7}, {n2, n6},{n6, n2} } Outline del contenido
Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo a1(n2, n6) , a2(n2, n6) son dos aritas para unir los nodos n2 y n6. También puede ser que en un arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n1, n2). Valencias
Teoria De Grafos
En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados nodos (o vértices) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada).
domingo, 4 de octubre de 2009
TEMARIO
1) INTRODUCCION A LA LOGICA MATEMATICA
2) TEORIA DE LA DEMOSTRACION
3) INDUCCION MATEMATICO
4) SISTEMAS NUMERICOS
2) TEORIA DE LA DEMOSTRACION
3) INDUCCION MATEMATICO
4) SISTEMAS NUMERICOS
viernes, 2 de octubre de 2009
Demostracion Condicional Y Directa
Si una fórmula tiene la forma A → B y es una tautología, en donde A y B pueden ser proposiciones compuestas, entonces decimos que B se desprende lógicamente de A y se representa por A = B.
También podemos considerar tautologías de la forma (p1 p2 ^ … ^ pn) → q
Entonces está implicación es verdadera sin importar los valores de verdad de cualquiera de sus componentes. En este caso, se dice que q se desprende lógicamente de p1,p2,…,pn. Se escribe.
p1 , p2 , … , pn = q
o también
p1 p2 ...pn = q
Significa que si se sabe que p1 es verdadera, p2 es verdadera ,…, y pn también es verdadera, entonces estamos seguros que q es verdadera.
Prácticamente todos los teoremas matemáticos están compuestos por implicaciones de este tipo. Donde p1, p2, … son llamadas hipótesis o premisas, y q es llamada conclusión. Demostrar el teorema, es demostrar que la implicación es una tautología. Note que no estamos tratando de demostrar que q (la conclusión) es verdadera, sino solamente que q es verdadera si todas las p1, p2, … son verdaderas.
Una demostración directa comienza con las hipótesis, seguidas de las tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión. Ver Tema anterior 1.9.2 Deduccion Preposicional.
A continuación veremos lo que es una prueba condicional. En este caso la conclusión es un enunciado de la forma A → B ; en este caso demostrar que la condicional sedesprende de un conjunto de premisas P1, P2, … Pn es equivalente a probar que B de desprende de las premisas junto con A, la cual se llama premisa adicional.
Esto lo podemos expresar en el siguiente teorema.
P1, P2, … , Pn = (A → B) es equivalente a
P1, P2, … , Pn, A = B.
Ejemplo 1.
Demustre el argumento
p → ¬q, q ∨ ¬r, s → r = p → ¬s
Demostración
1. p → ¬q Premisa
2. q ∨ ¬r Premisa
3. s → r Premisa
4. p Premisa Adicional
5. ¬q MPP(1,4)
6. ¬r SD(2,5)
7. ¬s MTT(3,6)
Demostración por contradicción.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
La demostración del siguiente teorema por el método de contradicción es como se indica
p → (q ^ r), (q ∨ s) → t, (p ∨ s) = t
Demostración
1. p → (q ^ r) Premisa
2. (q ∨ s) → t Premisa
3. p ∨ s Premisa
4. ¬t Premisa Adicional
5. ¬(q ∨ s) MPP(2,4)
6. ¬q ^ ¬s Ley de De Morgan(5)
7. ¬q LS(6)
8. ¬s LS(6)
9. p SD(3,8)
10. q ^ r MPP(1,9)
11. q LS(10)
12. q ^ ¬q Conjunción(7,11)
Pero esto último es una comtradicción, por lo que queda demostrado el argumento.
Note que juntamente con las premisas se debe incluir la negación de la conclusión como premisa adicional, paso 4. En este momento el alumno ya tiene los elementos para llevar a cabo demostraciones con el apoyo del maestro. Es conveniente plantear varios enunciados, para que el alumno los represente con simbología lógica en forma de teorema. Que ese mismo teorema lo represente con su tabla de verdad y haga la correspondiente demostración por los dos métodos antes mencionados.
La forma en que el aprende a aplicar reglas de inferencia es semejante a la manera en que deberá realizar una factorización o una aplicación de una fórmula en cálculo diferencial o integral o la formula que debe aplicar para resolver un problema en física. Lo que debe aprender es a relacionar los distintos conocimientos para poder llegar a la solución. Es importante mencionar que el camino que debe seguir el alumno no es el mismo que el maestro siguió sino uno distinto pero que ambos llegan al resultado.
También podemos considerar tautologías de la forma (p1 p2 ^ … ^ pn) → q
Entonces está implicación es verdadera sin importar los valores de verdad de cualquiera de sus componentes. En este caso, se dice que q se desprende lógicamente de p1,p2,…,pn. Se escribe.
p1 , p2 , … , pn = q
o también
p1 p2 ...pn = q
Significa que si se sabe que p1 es verdadera, p2 es verdadera ,…, y pn también es verdadera, entonces estamos seguros que q es verdadera.
Prácticamente todos los teoremas matemáticos están compuestos por implicaciones de este tipo. Donde p1, p2, … son llamadas hipótesis o premisas, y q es llamada conclusión. Demostrar el teorema, es demostrar que la implicación es una tautología. Note que no estamos tratando de demostrar que q (la conclusión) es verdadera, sino solamente que q es verdadera si todas las p1, p2, … son verdaderas.
Una demostración directa comienza con las hipótesis, seguidas de las tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión. Ver Tema anterior 1.9.2 Deduccion Preposicional.
A continuación veremos lo que es una prueba condicional. En este caso la conclusión es un enunciado de la forma A → B ; en este caso demostrar que la condicional sedesprende de un conjunto de premisas P1, P2, … Pn es equivalente a probar que B de desprende de las premisas junto con A, la cual se llama premisa adicional.
Esto lo podemos expresar en el siguiente teorema.
P1, P2, … , Pn = (A → B) es equivalente a
P1, P2, … , Pn, A = B.
Ejemplo 1.
Demustre el argumento
p → ¬q, q ∨ ¬r, s → r = p → ¬s
Demostración
1. p → ¬q Premisa
2. q ∨ ¬r Premisa
3. s → r Premisa
4. p Premisa Adicional
5. ¬q MPP(1,4)
6. ¬r SD(2,5)
7. ¬s MTT(3,6)
Demostración por contradicción.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
La demostración del siguiente teorema por el método de contradicción es como se indica
p → (q ^ r), (q ∨ s) → t, (p ∨ s) = t
Demostración
1. p → (q ^ r) Premisa
2. (q ∨ s) → t Premisa
3. p ∨ s Premisa
4. ¬t Premisa Adicional
5. ¬(q ∨ s) MPP(2,4)
6. ¬q ^ ¬s Ley de De Morgan(5)
7. ¬q LS(6)
8. ¬s LS(6)
9. p SD(3,8)
10. q ^ r MPP(1,9)
11. q LS(10)
12. q ^ ¬q Conjunción(7,11)
Pero esto último es una comtradicción, por lo que queda demostrado el argumento.
Note que juntamente con las premisas se debe incluir la negación de la conclusión como premisa adicional, paso 4. En este momento el alumno ya tiene los elementos para llevar a cabo demostraciones con el apoyo del maestro. Es conveniente plantear varios enunciados, para que el alumno los represente con simbología lógica en forma de teorema. Que ese mismo teorema lo represente con su tabla de verdad y haga la correspondiente demostración por los dos métodos antes mencionados.
La forma en que el aprende a aplicar reglas de inferencia es semejante a la manera en que deberá realizar una factorización o una aplicación de una fórmula en cálculo diferencial o integral o la formula que debe aplicar para resolver un problema en física. Lo que debe aprender es a relacionar los distintos conocimientos para poder llegar a la solución. Es importante mencionar que el camino que debe seguir el alumno no es el mismo que el maestro siguió sino uno distinto pero que ambos llegan al resultado.
Deduccion preposicional
En lugar de deducción preposicioal es deducción proposicional, aunque un nombre más general podría ser inferencia. o
La inferencia es un procediendo para obtener conclusiones, hay tres tipos de inferencia: Por inducción, por deducción y por abducción.
Por inducción es de lo particular a lo general, esto es de muchas observaciones concluir una regla general. Por deducción es de lo general a lo particular, esto es de un regla general se concluye un caso particular. Por abducción de particular a partuclar o de general a general. Para una explicación más amplia ver el Tema 1.7 Reglas de Inferencia.
En lógica proposicional solo se admite la deducción como procedimiento válido para obtener conclusiones, los otros mátodos se pueden utilizar en probalididad, estadística, lógica difusa, ciencias, etc.
Primeramente consideraremos algunas reglas de inferencia deductiva; esto es, obtener alguna conclusión en base a hechos conocidos.
Reglas de Inferencia Deductiva
MPP Modus ponendo ponens A → B A - - - - - B
MTTModus tollendo tollens A → B ¬B - - - - - ¬A
SD Silogismo Disyuntivo A ∨ B ¬A - - - - - ¬B
SH Silogismo hipotético A → B B → C - - - - - A → C
LS Ley de simplificación A ∧ B - - - - - A
LA Ley de adición A - - - - - A ∨ B
CONTRAPOSITIVA A → B - - - - - ¬B → ¬A
En la notación anterior los elementos conocidos, premisas están antes de la raya, y lo que está debajo de la raya se llama conclusión.
En general una inferencia es válida si cuando las premisas son verdaderas la conclusión también lo es, o sea
La inferencia es válida si (A1 ^ A2 ^ … ^ An)→ C es tautología.
¿Qué es una demostración?.
Para comprobar que una inferencia es válida se debe demostrar. Una demostración es un conjunto de pasos donde el último paso es la conclusión, cualquiera de los siguientes pasos es válido:
Pasos válidos en una demostración
Premisa; en cualquier paso se puede usar una premisa, esto es, lo que suponemos válido.
Equivalencias; cualquier paso puede ser un equivalente de un paso anterior.
Regla de Inferencia; en cualquier paso se puede escribir la conclusión de una regla de inferencia si sus premisas son pasos anteriores.
Propiedades previas; cualquier teorema o propiedad conocida puede ser usado en un paso, en particular cualquier inferencia válida puede ser utilizada.
Ejemplo 1. Comprobar que r se infiere de las premisas:
p, ¬p ∨ q, ¬r &rarr: ¬q
Una forma de represetar esto es:
p, ¬p ∨ q, ¬r &rarr: ¬ = r
Demostración Utilizando únicamente MPP
1. p Premisa
2. ¬p ∨ q Premisa
3. ¬r → ¬ q Premisa
4. p → q Equivalencia (2)
5. q MPP(1,4)
6. q → r Equivalencia (3)
7. r MPP(5,6)
Los primeros tres pasos de la demostración son las premisas, los pasos 4 y 6 son equivalencias y los pasos 5 y 7 son la aplicación de la regla MPP con las premisas que se encuentran en el paréntesis.
La demostración anterior la podemos hacer sin utilizar equivalencias utilizando otras leyes de inferencia además de MPP.
Ejemplo 2.
Comprobar p, ¬p ∨ q, ¬r &rarr: ¬ = r
Demostración
1. p Premisa
2. ¬p ∨ q Premisa
3. ¬r → ¬ q Premisa
4. q SD(1,2)
5. r MTT(3,4)
Generalmente si se utilizan más reglas de inferencia la demostración es más corta.
Ejemplo 3.
t → s, ¬q → ¬s, t = q
Demostración 1
1. t → s Premisa
2. ¬q → ¬s Premisa
3. t Premisa
4. s MPP(1,3)
5. q MTT(2,4)
Demostración 2
1. t → s Premisa
2. ¬q → ¬s Premisa
3. t Premisa
4. s MPP(1,3)
5. s → q Equivalencia (2)
6. q MTT(4,5)
Como se puede ver la regla de inferencia Modus Tollendo Tollens (MTT), no es necesaria si usamos la eauivalencia en el paso 5, sin embargo, muchos personas prefieren usarla porque es un paso menos.
La inferencia es un procediendo para obtener conclusiones, hay tres tipos de inferencia: Por inducción, por deducción y por abducción.
Por inducción es de lo particular a lo general, esto es de muchas observaciones concluir una regla general. Por deducción es de lo general a lo particular, esto es de un regla general se concluye un caso particular. Por abducción de particular a partuclar o de general a general. Para una explicación más amplia ver el Tema 1.7 Reglas de Inferencia.
En lógica proposicional solo se admite la deducción como procedimiento válido para obtener conclusiones, los otros mátodos se pueden utilizar en probalididad, estadística, lógica difusa, ciencias, etc.
Primeramente consideraremos algunas reglas de inferencia deductiva; esto es, obtener alguna conclusión en base a hechos conocidos.
Reglas de Inferencia Deductiva
MPP Modus ponendo ponens A → B A - - - - - B
MTTModus tollendo tollens A → B ¬B - - - - - ¬A
SD Silogismo Disyuntivo A ∨ B ¬A - - - - - ¬B
SH Silogismo hipotético A → B B → C - - - - - A → C
LS Ley de simplificación A ∧ B - - - - - A
LA Ley de adición A - - - - - A ∨ B
CONTRAPOSITIVA A → B - - - - - ¬B → ¬A
En la notación anterior los elementos conocidos, premisas están antes de la raya, y lo que está debajo de la raya se llama conclusión.
En general una inferencia es válida si cuando las premisas son verdaderas la conclusión también lo es, o sea
La inferencia es válida si (A1 ^ A2 ^ … ^ An)→ C es tautología.
¿Qué es una demostración?.
Para comprobar que una inferencia es válida se debe demostrar. Una demostración es un conjunto de pasos donde el último paso es la conclusión, cualquiera de los siguientes pasos es válido:
Pasos válidos en una demostración
Premisa; en cualquier paso se puede usar una premisa, esto es, lo que suponemos válido.
Equivalencias; cualquier paso puede ser un equivalente de un paso anterior.
Regla de Inferencia; en cualquier paso se puede escribir la conclusión de una regla de inferencia si sus premisas son pasos anteriores.
Propiedades previas; cualquier teorema o propiedad conocida puede ser usado en un paso, en particular cualquier inferencia válida puede ser utilizada.
Ejemplo 1. Comprobar que r se infiere de las premisas:
p, ¬p ∨ q, ¬r &rarr: ¬q
Una forma de represetar esto es:
p, ¬p ∨ q, ¬r &rarr: ¬ = r
Demostración Utilizando únicamente MPP
1. p Premisa
2. ¬p ∨ q Premisa
3. ¬r → ¬ q Premisa
4. p → q Equivalencia (2)
5. q MPP(1,4)
6. q → r Equivalencia (3)
7. r MPP(5,6)
Los primeros tres pasos de la demostración son las premisas, los pasos 4 y 6 son equivalencias y los pasos 5 y 7 son la aplicación de la regla MPP con las premisas que se encuentran en el paréntesis.
La demostración anterior la podemos hacer sin utilizar equivalencias utilizando otras leyes de inferencia además de MPP.
Ejemplo 2.
Comprobar p, ¬p ∨ q, ¬r &rarr: ¬ = r
Demostración
1. p Premisa
2. ¬p ∨ q Premisa
3. ¬r → ¬ q Premisa
4. q SD(1,2)
5. r MTT(3,4)
Generalmente si se utilizan más reglas de inferencia la demostración es más corta.
Ejemplo 3.
t → s, ¬q → ¬s, t = q
Demostración 1
1. t → s Premisa
2. ¬q → ¬s Premisa
3. t Premisa
4. s MPP(1,3)
5. q MTT(2,4)
Demostración 2
1. t → s Premisa
2. ¬q → ¬s Premisa
3. t Premisa
4. s MPP(1,3)
5. s → q Equivalencia (2)
6. q MTT(4,5)
Como se puede ver la regla de inferencia Modus Tollendo Tollens (MTT), no es necesaria si usamos la eauivalencia en el paso 5, sin embargo, muchos personas prefieren usarla porque es un paso menos.
Equivalencias Logicas Y Utilizaciones
Junto con las tautologías un concepto muy utilizado es el de equivalencia.
Definición: Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos los posibles valores de verdad de sus componentes atómicos.
Ejemplo 2: Las dos fórmulas siguientes son equivalentes:
(p → ¬q) ∨ (¬p ∨ r) ¬p ∨ ¬q ∨ r
de manera similar a lo establecido en las secciones anteriores, elaboramos el árbol sintáctico y la tabla
p q r ¬q ¬p p → ¬q ¬p ∨ r (p → ¬q) ∨ (¬p ∨ r) ¬ p ∨ ¬q ¬p ∨ ¬q ∨ r
VVV F F F V F V
VVF F F F F F F F
VFV V F V V V V V
VFF V F V F V V V
FVV F V V V V V V
FVF F V V V V V V
FFV V V V V V V V
FFF V V V V V V V
Dnde se puede observar que la última yla antepenúltima columnas son iguales.
Las equivalencias se relacionan con las tautologías de la siguiente forma.
Teorema: Si dos fórmulas lógicas son eqivalentes entonces la fórmula que se obtiene al operarlas con la bicondiconal es una tautología.
Si F ≡ G entonces F ⇔ G
La propiedad inversa también se cumple pues si una bicondicional es una tautología, las fórmulas que la componen son equivalentes. El teorema y su inverso se comprueban directamente de la tabla de verdad de la bicondicional.
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
La comprobación de cualquiera de las tautologías anteriores es directa, es suficiente hacer la tabla de verdad y se obtendrá la columna correspondiente a la fórmula con valores verdaderos únicamente.
Equivalencias
¬(¬p) ≡ p Doble Negación
¬(p ∨ q) ≡ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ∨ q) ≡ ¬p ^ ¬q Ley 2 de De Morgan
(p → q) ≡ (¬ p ∨ q) Condicional como cláusula
((p → q) ≡ (¬ q → ¬ p) Contrapositiva
¬(p → q) ≡ p ^ ¬q Negación de la Implicación
Ejemplo 2: p → q ≡ ¬p ∨ q
El árbol sintáctico es:
y en la tabla las columnas 3 y 5 son iguales
p q p → q ¬p ¬p ∨ q
VV V F V
VF F F F
FV V V V
FF V V V
Definición: Dos fórmulas lógicas son equivalentes si tienen los mismos valores de verdad para todos los posibles valores de verdad de sus componentes atómicos.
Ejemplo 2: Las dos fórmulas siguientes son equivalentes:
(p → ¬q) ∨ (¬p ∨ r) ¬p ∨ ¬q ∨ r
de manera similar a lo establecido en las secciones anteriores, elaboramos el árbol sintáctico y la tabla
p q r ¬q ¬p p → ¬q ¬p ∨ r (p → ¬q) ∨ (¬p ∨ r) ¬ p ∨ ¬q ¬p ∨ ¬q ∨ r
VVV F F F V F V
VVF F F F F F F F
VFV V F V V V V V
VFF V F V F V V V
FVV F V V V V V V
FVF F V V V V V V
FFV V V V V V V V
FFF V V V V V V V
Dnde se puede observar que la última yla antepenúltima columnas son iguales.
Las equivalencias se relacionan con las tautologías de la siguiente forma.
Teorema: Si dos fórmulas lógicas son eqivalentes entonces la fórmula que se obtiene al operarlas con la bicondiconal es una tautología.
Si F ≡ G entonces F ⇔ G
La propiedad inversa también se cumple pues si una bicondicional es una tautología, las fórmulas que la componen son equivalentes. El teorema y su inverso se comprueban directamente de la tabla de verdad de la bicondicional.
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
La comprobación de cualquiera de las tautologías anteriores es directa, es suficiente hacer la tabla de verdad y se obtendrá la columna correspondiente a la fórmula con valores verdaderos únicamente.
Equivalencias
¬(¬p) ≡ p Doble Negación
¬(p ∨ q) ≡ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ∨ q) ≡ ¬p ^ ¬q Ley 2 de De Morgan
(p → q) ≡ (¬ p ∨ q) Condicional como cláusula
((p → q) ≡ (¬ q → ¬ p) Contrapositiva
¬(p → q) ≡ p ^ ¬q Negación de la Implicación
Ejemplo 2: p → q ≡ ¬p ∨ q
El árbol sintáctico es:
y en la tabla las columnas 3 y 5 son iguales
p q p → q ¬p ¬p ∨ q
VV V F V
VF F F F
FV V V V
FF V V V
Tautologias Y Contradicciones
Una tautología es una expresión lógica que es verdadera para todos los posibles valores de verdad de sus componentes atómicos.
En lógica se entiende por tautología aquella proposición cuya tabla de verdad da siempre el valor de verdad V en todos los casos posibles de los valores de verdad (V, F) de cada una de las proposiciones que la integran, o de un modo más sencillo: la supuesta explicación de algo mediante una perogrullada, la “explicación” o definición de algo mediante una ligera variación de palabras que tienen en conjunto el mismo significado ya conocido de lo supuestamente explicado (Ej.: “Existe el calor porque lo provoca el calórico”).
Tautología: en todos los casos la forma del argumento ofrece un resultado verdadero, por lo que el argumento es válido.
Una contradiccion es uan expresion logica que es falsa para todos sus valores.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
Ejemplo 1:
La expresión ‘(p ^ q) → (p ∨ r)’ es una tautología
Primeramente se construye el árbol de acuerdo a los pasos 1 y 2 del algortimo.
Recordemos que si no se tiene práctica haciendo el árbol sintáctico, una buena idea es numerar los operadores en orden
jerárquico.
Una vez numerado se forma el árbol empezando por el número más grande en orden descendiente.
(p ∧ q) → (p ∨ ¬ r)
p ∧ q p ∨ ¬ r
p ∧ q p ∨ ¬ r
¬ r
Utilizamos el árbol para construir la tabla, para ver con detalle los pasos ver el Tema 1.8 Evaluacion de Expresiones.
p q r ¬ r p ∧ q p ∨ ¬ r (p ∧ q) → (p ∨ ¬ r)
V V V F V V V
V V F V V V V
V F V F F V V
V F F V F V V
F V V F F F V
F V F V F V V
F F V F F F V
F F F V F V V
Vemos que la última columna tiene unicamente V por que se comprueba que es una tautología.
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
¬(¬p) ↔ p Doble Negación
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 2 de De Morgan
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
(p → q) ↔ (¬ p ∨ q) Condicional como cláusula
((p → q) ↔ (¬ q → ¬ p) Contrapositiva
‘Ejemplo 2.’ Veamos la comprobación de Modus Tollendo Tollens
((p → q) ∧ ¬q) → ¬p
→
(p → q) ∧ ¬q ¬p
∧
(p → q) ¬q ¬p
→
p q ¬q
El árbol sintáctico es:
Y la tabla comprueba que es una tautología.
p q p → q ¬ q (p → q) ∧ ¬ q ¬ p ((p → q) ∧ ¬ q) → ¬ p
V V V F F F V
V F F V F F V
F V V F F V V
F F V V V V V
En lógica se entiende por tautología aquella proposición cuya tabla de verdad da siempre el valor de verdad V en todos los casos posibles de los valores de verdad (V, F) de cada una de las proposiciones que la integran, o de un modo más sencillo: la supuesta explicación de algo mediante una perogrullada, la “explicación” o definición de algo mediante una ligera variación de palabras que tienen en conjunto el mismo significado ya conocido de lo supuestamente explicado (Ej.: “Existe el calor porque lo provoca el calórico”).
Tautología: en todos los casos la forma del argumento ofrece un resultado verdadero, por lo que el argumento es válido.
Una contradiccion es uan expresion logica que es falsa para todos sus valores.
El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.
Ejemplo 1:
La expresión ‘(p ^ q) → (p ∨ r)’ es una tautología
Primeramente se construye el árbol de acuerdo a los pasos 1 y 2 del algortimo.
Recordemos que si no se tiene práctica haciendo el árbol sintáctico, una buena idea es numerar los operadores en orden
jerárquico.
Una vez numerado se forma el árbol empezando por el número más grande en orden descendiente.
(p ∧ q) → (p ∨ ¬ r)
p ∧ q p ∨ ¬ r
p ∧ q p ∨ ¬ r
¬ r
Utilizamos el árbol para construir la tabla, para ver con detalle los pasos ver el Tema 1.8 Evaluacion de Expresiones.
p q r ¬ r p ∧ q p ∨ ¬ r (p ∧ q) → (p ∨ ¬ r)
V V V F V V V
V V F V V V V
V F V F F V V
V F F V F V V
F V V F F F V
F V F V F V V
F F V F F F V
F F F V F V V
Vemos que la última columna tiene unicamente V por que se comprueba que es una tautología.
Tautologías Fundamentales
p ∨ ¬p Ley del medio excluido
¬ (p ^ ¬p) Ley de no contradicción
¬(¬p) ↔ p Doble Negación
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 1 de De Morgan
¬(p ∨ q) ↔ ¬p ^ ¬q Ley 2 de De Morgan
((p → q)^p) → q Modus ponendo ponens
((p → q)^ ¬ q) → ¬ p Modus tollendo tollens
((p ∨ q) ∧ ¬ p) → q Silogismo Disyuntivo
((p → q) ∧ (q → r)) → (p → r) Silogismo Hipotético
(p → q) ↔ (¬ p ∨ q) Condicional como cláusula
((p → q) ↔ (¬ q → ¬ p) Contrapositiva
‘Ejemplo 2.’ Veamos la comprobación de Modus Tollendo Tollens
((p → q) ∧ ¬q) → ¬p
→
(p → q) ∧ ¬q ¬p
∧
(p → q) ¬q ¬p
→
p q ¬q
El árbol sintáctico es:
Y la tabla comprueba que es una tautología.
p q p → q ¬ q (p → q) ∧ ¬ q ¬ p ((p → q) ∧ ¬ q) → ¬ p
V V V F F F V
V F F V F F V
F V V F F V V
F F V V V V V
Evaluacion De Expresiones
Como ya sabemos la sintaxis en lógica es la forma correcta de escribir una fórmula y la semántica es lo que significa. Como en lógica solamente tenemos dos valores una fórmula solamente puede ser verdadera o falsa. Para determinar su valor seguimos las reglas simples que dimos en las definiciones básicas de acuerdo a su tabla de verdad. Esto lo hacemos mediante interpretaciones. Una interpretación de una fórmula es un conjunto de valores que se les asignan a sus proposiciones atómicas.
Al interpretar una fórmula lo que finalmente vamos a obtener es un valor de verdad, bien sea verdadero o falso. Pero para poder encontrarlo muchas veces el proceso en laborioso porque puede estar formada por varias proposiciones atómicas. Primeramente se le asignan valores de verdad a los átomos y se puede encontrar el valor de la expresión.
Si deseamos hacerlo en general, debemos analizar todas las posibilidades, esto se puede hacer construyendo una tabla de verdad. Para fines prácticos cuando se tienen varios átomos las tablas de verdad no resultan prácticas por lo que analizaremos solamente expresiones con tres átomos como máximo.
Por supuesto que se puede construir una tabla para un número mayor de átomos, pero notemos que por cada átomo que se aumente el número de renglones se duplica. Esto es, para un átomos son dos renglones, para dos átomos son cuatro, para tres átomos son ocho, para cuatro dieciséis, etc.
Algoritmo para construir una tabla de verdad de una fórmula en lógica de proposiciones.
1. Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan la misma jerarquía, se le asigna el número menor al de la izquierda.
2. Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor jerarquía. O sea, del número mayor al menor. Ver Tema 1.5 Algebra Declarativa.
3. Numerar las ramas del árbol en forma secuencial empezando por las hojas hacia la raíz, con la única condición de que una rama se puede numerar hasta que estén numerados los hijos. Para empezar con la numeración de las hojas es buena idea hacerlo en orden alfabético, así todos obtienen los renglones de la tabla en el mismo orden para poder comparar resultados.
4. Escribir los encabezados de la tabla las fórmulas siguiendo la numeración que se le dió a las ramas en el árbol sintáctico.
5. Asignarle a los átomos, las hojas del árbol, todos los posibles valores de verdad de acuerdo al orden establecido. Por supuesto que el orden es arbitrario, pero como el número de permutaciones es n!, conviene establecer un orden para poder comparar resultados fácilmente.
6. Asignar valor de verdad a cada una de las columnas restantes de acuerdo al operador indicado en el árbol sintáctico utilizando las tablas de verdad correspondiente del Conexiones Logicas y Jerarquias. Conviene aprenderse de memoria las tablas de los operadores, al principio pueden tener un resumen con todas las tablas mientras se memorizan.
7. La última columna, correspondiente a la fórmula original, es la que indica los valores de verdad posibles de la fórmula para cada caso.
Ejemplo. Construya la tabla de verdad de las siguientes expresiones lógicas:
i) (p → ¬q) v (¬p v r) ii) p → (q ^ r)iii) (p → ¬ r) ↔ (q v p)iv) ¬(p ¬ q) → ¬ r v) (¬p ^ q) → ¬(q v ¬r)
Solución: (Faltan las gráficas de los árboles, los quitaron)
i) Seguimos los pasos del algoritmo con la fórmula (p → ¬q) v (¬p v r)
Al interpretar una fórmula lo que finalmente vamos a obtener es un valor de verdad, bien sea verdadero o falso. Pero para poder encontrarlo muchas veces el proceso en laborioso porque puede estar formada por varias proposiciones atómicas. Primeramente se le asignan valores de verdad a los átomos y se puede encontrar el valor de la expresión.
Si deseamos hacerlo en general, debemos analizar todas las posibilidades, esto se puede hacer construyendo una tabla de verdad. Para fines prácticos cuando se tienen varios átomos las tablas de verdad no resultan prácticas por lo que analizaremos solamente expresiones con tres átomos como máximo.
Por supuesto que se puede construir una tabla para un número mayor de átomos, pero notemos que por cada átomo que se aumente el número de renglones se duplica. Esto es, para un átomos son dos renglones, para dos átomos son cuatro, para tres átomos son ocho, para cuatro dieciséis, etc.
Algoritmo para construir una tabla de verdad de una fórmula en lógica de proposiciones.
1. Escribir la fórmula con un número arriba de cada operador que indique su jerarquía. Se escriben los enteros positivos en orden, donde el número 1 corresponde al operador de mayor jerarquía. Cuando dos operadores tengan la misma jerarquía, se le asigna el número menor al de la izquierda.
2. Construir el árbol sintáctico empezando con la fórmula en la raíz y utilizando en cada caso el operador de menor jerarquía. O sea, del número mayor al menor. Ver Tema 1.5 Algebra Declarativa.
3. Numerar las ramas del árbol en forma secuencial empezando por las hojas hacia la raíz, con la única condición de que una rama se puede numerar hasta que estén numerados los hijos. Para empezar con la numeración de las hojas es buena idea hacerlo en orden alfabético, así todos obtienen los renglones de la tabla en el mismo orden para poder comparar resultados.
4. Escribir los encabezados de la tabla las fórmulas siguiendo la numeración que se le dió a las ramas en el árbol sintáctico.
5. Asignarle a los átomos, las hojas del árbol, todos los posibles valores de verdad de acuerdo al orden establecido. Por supuesto que el orden es arbitrario, pero como el número de permutaciones es n!, conviene establecer un orden para poder comparar resultados fácilmente.
6. Asignar valor de verdad a cada una de las columnas restantes de acuerdo al operador indicado en el árbol sintáctico utilizando las tablas de verdad correspondiente del Conexiones Logicas y Jerarquias. Conviene aprenderse de memoria las tablas de los operadores, al principio pueden tener un resumen con todas las tablas mientras se memorizan.
7. La última columna, correspondiente a la fórmula original, es la que indica los valores de verdad posibles de la fórmula para cada caso.
Ejemplo. Construya la tabla de verdad de las siguientes expresiones lógicas:
i) (p → ¬q) v (¬p v r) ii) p → (q ^ r)iii) (p → ¬ r) ↔ (q v p)iv) ¬(p ¬ q) → ¬ r v) (¬p ^ q) → ¬(q v ¬r)
Solución: (Faltan las gráficas de los árboles, los quitaron)
i) Seguimos los pasos del algoritmo con la fórmula (p → ¬q) v (¬p v r)
Reglas De Inferencia
En un cálculo lógico, las reglas de inferencia o reglas de transformación son aquellos esquemas formales que nos permiten derivar unas fórmulas bien formadas (conclusiones) a partir de otras (premisas). Por ejemplo, la Regla de Eliminación del Condicional:
A → B
A
______
B
nos permite derivar la fórmula “p v q” de las fórmulas “p → (p v q)” y “p”.
Las reglas de inferencia no deben confundirse con las leyes lógicas o tautologías, puesto que éstas no pertenecen al metalenguaje del cálculo.
Primero presentamos los tipos de inferencia, la inferencia válida en computación y matemáticas y al final una serie de reglas que se utilizan para la inferencia deductiva.
La inferencia es la forma en la que obtenemos conclusiones en base a datos y declaraciones establecidas.
Un argumento, por ejemplo es una inferencia, donde las premisas son los datos o expresiones conocidas y de ellas se desprende una conclusión.
Los argumentos basados en tautologías representan métodos de razonamiento universalmente correctos. Su validez depende solamente de la forma de las proposiciones que intervienen y no de los valores de verdad de las variables que contienen. A esos argumentos se les llama reglas de inferencia. Las reglas de inferencia permiten relacionar dos o más tautologías o hipótesis en una demostración.
Una inferencia puede ser: Inductiva, deductiva, transductiva y abductiva. Ver Inferencia.
De los cuatro tipos de inferencia señalados anteriormente, en matemáticas y computaión solamente se acepta el deductivo para demostraciones formales; Ver Deducción. Por esta rezón se denominan Reglas de Inferencia Deductiva.
Reglas de Inferencia Deductiva
MPP Modus ponendo ponens A → B A - - - - - B
MTTModus tollendo tollens A → B ¬B - - - - - ¬A
SD Silogismo Disyuntivo A ∨ B ¬A - - - - - ¬B
SH Silogismo hipotético A → B B → C - - - - - A → C
LS Ley de simplificación A ∧ B - - - - - A
LA Ley de adición A - - - - - A ∨ B
CONTRAPOSITIVA A → B - - - - - ¬B → ¬A
La comprobación de las reglas anteriores es directa y basta hacer fórmula con la conjunción de las premisas condicional la conclusión y probar que es una tautología, por ejemplo haciendo una tabla y obtener todos los valores verdaderos.
A → B
A
______
B
nos permite derivar la fórmula “p v q” de las fórmulas “p → (p v q)” y “p”.
Las reglas de inferencia no deben confundirse con las leyes lógicas o tautologías, puesto que éstas no pertenecen al metalenguaje del cálculo.
Primero presentamos los tipos de inferencia, la inferencia válida en computación y matemáticas y al final una serie de reglas que se utilizan para la inferencia deductiva.
La inferencia es la forma en la que obtenemos conclusiones en base a datos y declaraciones establecidas.
Un argumento, por ejemplo es una inferencia, donde las premisas son los datos o expresiones conocidas y de ellas se desprende una conclusión.
Los argumentos basados en tautologías representan métodos de razonamiento universalmente correctos. Su validez depende solamente de la forma de las proposiciones que intervienen y no de los valores de verdad de las variables que contienen. A esos argumentos se les llama reglas de inferencia. Las reglas de inferencia permiten relacionar dos o más tautologías o hipótesis en una demostración.
Una inferencia puede ser: Inductiva, deductiva, transductiva y abductiva. Ver Inferencia.
De los cuatro tipos de inferencia señalados anteriormente, en matemáticas y computaión solamente se acepta el deductivo para demostraciones formales; Ver Deducción. Por esta rezón se denominan Reglas de Inferencia Deductiva.
Reglas de Inferencia Deductiva
MPP Modus ponendo ponens A → B A - - - - - B
MTTModus tollendo tollens A → B ¬B - - - - - ¬A
SD Silogismo Disyuntivo A ∨ B ¬A - - - - - ¬B
SH Silogismo hipotético A → B B → C - - - - - A → C
LS Ley de simplificación A ∧ B - - - - - A
LA Ley de adición A - - - - - A ∨ B
CONTRAPOSITIVA A → B - - - - - ¬B → ¬A
La comprobación de las reglas anteriores es directa y basta hacer fórmula con la conjunción de las premisas condicional la conclusión y probar que es una tautología, por ejemplo haciendo una tabla y obtener todos los valores verdaderos.
Induccion matematicas
G. Peano (1858–1932) propuso cinco propiedades fundamentales que caracterizan a los números naturales, Axiomas de Peano. Una de ellas conocida como el Principo de Inducción Matemática es actualmente una herramienta de uso práctico y teórico principalmente para matemáticos y personas que trabajan en Ciencias Computacionales.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
Principio de Inducción Matemática.
Si S en un conjunto de enteros positivos tal que
(B) 1 e S
(I) k e S Þ (k+1) e S
entonces S contiene todos los enteros positivos.
En en principio de Inducción Matemática son muy importantes los nombres asociados y en la literatura técnica, como es costumbre, no se presenta con detalle los pasos, por lo que resulta indispensable conocer la nomenclatura.
Nomenclatura de Inducción Matemática.
(B) se llama Caso Base o caso inicial(I) se llama Paso de Inducciónk e S se llama Hipótesis de InducciónY como ya se mencionó todo junto se llama Principio de Inducción Matemática.
Es importante que el alumno comprenda y memorice cada uno de estos conceptos y su participación directa en la propiedad.
Escencialmente lo que enuncia el principio de inducción matemática es, si logramos establecer que el primer entero positivo cumple, una propiedad, y si partiendo de que un entero arbitrario también la cumple, se puede comprobar que el entero siguiente también tiene la propiedad entonces concluimos que todos los enteros positivos tienen la propiedad indicada.
Por lo que otra forma de enunciar el Principio de Inducción Matemática es:
Si F(n) es una proposición abierta que involucra enteros y se tiene (B) F(1) es verdadera; o sea, se que cumple para n=1 (I) F(K) Þ F(k+1); Si se cumple para n = k entonces también se cumple para n=k+1.
Concluimos que la proposición es verdadera para todos los enteros positivos.
El Principio de Inducción Matemática se utiliza para demostrar propiedades, formulas, validarlas y probar que son verdaderas, usualmente en el conjunto de los números enteros positivos. Muchas propiedades que incluyen la definición de de factorial se pueden probar por Inducción Matemática, como el Teorema del Binomio de Newton, el Triángulo de Pascal y algunas propiedades de combinatoria que involucran combinaciones y permutaciones. Otra forma de utilizarla es para proporcionar definiciones y formalizar conceptos.
1. Demostrar por Inducción Matematica que:
F(n): entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H → M] Sumamos (k+1) de los dos lados de la igualdad Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
En el ejemplo anterior para llegar a n=k+1 partiendo de n=k al lado izquierdo sólo le faltaba k+1 por lo que la estrategia fue sumar k+1 en ambos lados de la igualdad.
Esta estrategia la podemos utilizar para el siguiente algoritmo
Da click aqui para descargar la explicación en vídeo
ALGORITMO . Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
→ [Hipótesis de Inducción] Escribir la fórmula para n=k.
→ [Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración,sino más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la preparación de los estudiantes a los que va dirigido.
2. Demostrar por Inducción Matematica que: ∑ Es la letra griega sigma mayuscula y en matematicas significa suma
*[B] Si n=1; tenemos: entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H→M] Sumando (6(k+1)−2) a ambos lados Por lo tanto, podemos concluir que la formula (2) es valida para cualquiera que sea el valor de n
El Principio de Inducción Matemática es mucho más que el algoritmo aquí presentado, ya que hay muchos casos en los que no aparecen igualdades algebraicas y como se mencionó en el principio inicialmente (B), (I) son tan generales que puede aplicarse a cualquier cosa que cumpla las condiciones. Sin embargo el poder aprender y resolver problemas con este algoritmo le da al alumno la madurez necesaria para entenderlo en general y le sirve también para formalizar y entender posteriormente la recursividad, concepto tan importente en Ciencias Computacionales.
Para practicar hacer los ejercicios del 85 al 94 de Ejercicios MC 1
Definiciones por inducción: Utilizando el método de Inducción Matemáticas podemos definir conceptos en forma recursiva, la ventaja es que se formalizan los conceptos además de que son más fáciles de manejar.
Factorial:[B] 0! = 1[R] (n+1)! = n! (n+1)
Notación Sumatoria:
Suma:[B] m + 0 = m[R] m + n’ = (m+n)’
La definición anterior se basa en los números naturales, n’ significa el sucesor de n que equivale a n+1, por la misma definición anterior.
Producto:[B] m * 0 = 0[R] m * (n+1) = (m * n) + m.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
Principio de Inducción Matemática.
Si S en un conjunto de enteros positivos tal que
(B) 1 e S
(I) k e S Þ (k+1) e S
entonces S contiene todos los enteros positivos.
En en principio de Inducción Matemática son muy importantes los nombres asociados y en la literatura técnica, como es costumbre, no se presenta con detalle los pasos, por lo que resulta indispensable conocer la nomenclatura.
Nomenclatura de Inducción Matemática.
(B) se llama Caso Base o caso inicial(I) se llama Paso de Inducciónk e S se llama Hipótesis de InducciónY como ya se mencionó todo junto se llama Principio de Inducción Matemática.
Es importante que el alumno comprenda y memorice cada uno de estos conceptos y su participación directa en la propiedad.
Escencialmente lo que enuncia el principio de inducción matemática es, si logramos establecer que el primer entero positivo cumple, una propiedad, y si partiendo de que un entero arbitrario también la cumple, se puede comprobar que el entero siguiente también tiene la propiedad entonces concluimos que todos los enteros positivos tienen la propiedad indicada.
Por lo que otra forma de enunciar el Principio de Inducción Matemática es:
Si F(n) es una proposición abierta que involucra enteros y se tiene (B) F(1) es verdadera; o sea, se que cumple para n=1 (I) F(K) Þ F(k+1); Si se cumple para n = k entonces también se cumple para n=k+1.
Concluimos que la proposición es verdadera para todos los enteros positivos.
El Principio de Inducción Matemática se utiliza para demostrar propiedades, formulas, validarlas y probar que son verdaderas, usualmente en el conjunto de los números enteros positivos. Muchas propiedades que incluyen la definición de de factorial se pueden probar por Inducción Matemática, como el Teorema del Binomio de Newton, el Triángulo de Pascal y algunas propiedades de combinatoria que involucran combinaciones y permutaciones. Otra forma de utilizarla es para proporcionar definiciones y formalizar conceptos.
1. Demostrar por Inducción Matematica que:
F(n): entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H → M] Sumamos (k+1) de los dos lados de la igualdad Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
En el ejemplo anterior para llegar a n=k+1 partiendo de n=k al lado izquierdo sólo le faltaba k+1 por lo que la estrategia fue sumar k+1 en ambos lados de la igualdad.
Esta estrategia la podemos utilizar para el siguiente algoritmo
Da click aqui para descargar la explicación en vídeo
ALGORITMO . Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
→ [Hipótesis de Inducción] Escribir la fórmula para n=k.
→ [Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración,sino más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la preparación de los estudiantes a los que va dirigido.
2. Demostrar por Inducción Matematica que: ∑ Es la letra griega sigma mayuscula y en matematicas significa suma
*[B] Si n=1; tenemos: entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H→M] Sumando (6(k+1)−2) a ambos lados Por lo tanto, podemos concluir que la formula (2) es valida para cualquiera que sea el valor de n
El Principio de Inducción Matemática es mucho más que el algoritmo aquí presentado, ya que hay muchos casos en los que no aparecen igualdades algebraicas y como se mencionó en el principio inicialmente (B), (I) son tan generales que puede aplicarse a cualquier cosa que cumpla las condiciones. Sin embargo el poder aprender y resolver problemas con este algoritmo le da al alumno la madurez necesaria para entenderlo en general y le sirve también para formalizar y entender posteriormente la recursividad, concepto tan importente en Ciencias Computacionales.
Para practicar hacer los ejercicios del 85 al 94 de Ejercicios MC 1
Definiciones por inducción: Utilizando el método de Inducción Matemáticas podemos definir conceptos en forma recursiva, la ventaja es que se formalizan los conceptos además de que son más fáciles de manejar.
Factorial:[B] 0! = 1[R] (n+1)! = n! (n+1)
Notación Sumatoria:
Suma:[B] m + 0 = m[R] m + n’ = (m+n)’
La definición anterior se basa en los números naturales, n’ significa el sucesor de n que equivale a n+1, por la misma definición anterior.
Producto:[B] m * 0 = 0[R] m * (n+1) = (m * n) + m.
Algebra declarativa
los operadores lógicos con proposiciones, si esos operadores los combinamos podemos formar fórmulas lógicas.
La primera pregunta que nos hacemos es: Cómo sabemos si una fórmula está bien formada.
Pendiente: Dar la definición formal de fórmula bien formada, en forma recursiva.
¿Cómo simplificar en lógica?
Hay que utilizar equivalencias lógicas.
Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.
Para esto utilizamos las siguientes equivalencias lógicas:
( A ^ B ) ^ C <=> A^(B ^C)
A ^ ¬ A <=> F
A ^ F <=> F
( p ^ q ) ^ ¬q <=> F
Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.
Ejemplo
Demostrar que una vez que p ^ q esta establecida, se puede concluir q.
Esta demostración se puede hacer de dos formas:
A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.
Demostración
¬p V ¬q V q <=> V
B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica
La primera pregunta que nos hacemos es: Cómo sabemos si una fórmula está bien formada.
Pendiente: Dar la definición formal de fórmula bien formada, en forma recursiva.
¿Cómo simplificar en lógica?
Hay que utilizar equivalencias lógicas.
Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.
Para esto utilizamos las siguientes equivalencias lógicas:
( A ^ B ) ^ C <=> A^(B ^C)
A ^ ¬ A <=> F
A ^ F <=> F
( p ^ q ) ^ ¬q <=> F
Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.
Ejemplo
Demostrar que una vez que p ^ q esta establecida, se puede concluir q.
Esta demostración se puede hacer de dos formas:
A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.
Demostración
¬p V ¬q V q <=> V
B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica
Cuantificadores Y Restricciones
Dos casos centrales en el cálculo de predicados se presentan cuando se analiza si el predicado se cumple para la población completa y cuando se analiza para ver si cumple para un caso en particular al menos. Estos dos casos se llaman Universal y Particular o Existencial vienen a ser la interpretación o la semántica de los símbolos de cuantificadores que se vieron en la sección 1.4 Calculo de Predicados Definicion y se definen de la siguiente forma:
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la espresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio.
Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una expresión de cálculo de predicados F se representa por la espresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio.
Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.
Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una varible conectados mediante una condicional y tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
(∀ x) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todos las personas que viven en Tijuana.
Aquí podemos ver claramente que el dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede represntar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.
Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde.
A una expresión como las anteriores se le llama Universal Afirmativa y se representa con la letra A.
Los griegos utilizaban enunciados como los anteriores en los Silogismos, que son formas de razonamiento que contienen dos premisas tipo A, E , I, O y una conclusión también de uno de los cuatro tipos, las premisas están conectadas con un predicado común y la conclusión debe estar formado por las no comunes que se le llaman técnicamente premisa menor y premisa mayor.
Una expresión tipo E es llamada Universal Negativa y se representa por
(∀ x) (P(x) → ¬Q(x)) y en español se lee ningún P cumple Q o sea que los que cumplen el predicado P(x) no cumples el predicado Q(x).
Ningún alumno llegó tarde se puede representar por (∀ x) (A(x) → ¬T(x)) donde A es alumno y T es llegó tarde.
Las dos expresiones restantes corresponden a casos particulares y para formarlas utilizamos el cuantificador existencial, y en lugar del operador condicional se usa la conjunción, así
I es (∃ x) (P(x) ∧ Q(x)) llamado Particular Afirmativa y
O es (∃ x) (P(x) ∧ ¬ Q(x)) que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el segundo aseguramos que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación, pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
Primeramente estableceremos dos reglas generales con un predicado simple:
Propiedad:
¬(∀ x) P(x) es equivalente a (∃ x) (¬ P(x))
¬(∃ x) P(x) es equivalente a (∀ x) (¬P(x))
Ahora sí, podemos combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la Universal Negativa.
O sea que la negación de la forma A es la forma O y la negación de la forma I es la forma E.
¬ (∀ x) (P(x) → Q(x)) es equivalente a (∃ x) (P(x) ^ ¬ Q(x))
¬ (∃ x) (P(x) ^ Q(x)) es equivalente a (∀ x) (P(x) → ¬Q(x))
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la negación de Alguno es Ninguno.
Esto es muy útil en matemáticas y en computación, por ejemplo si queremos demostrar que no es cierto que todas las funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la espresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio.
Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una expresión de cálculo de predicados F se representa por la espresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio.
Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.
Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una varible conectados mediante una condicional y tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
(∀ x) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todos las personas que viven en Tijuana.
Aquí podemos ver claramente que el dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede represntar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.
Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde.
A una expresión como las anteriores se le llama Universal Afirmativa y se representa con la letra A.
Los griegos utilizaban enunciados como los anteriores en los Silogismos, que son formas de razonamiento que contienen dos premisas tipo A, E , I, O y una conclusión también de uno de los cuatro tipos, las premisas están conectadas con un predicado común y la conclusión debe estar formado por las no comunes que se le llaman técnicamente premisa menor y premisa mayor.
Una expresión tipo E es llamada Universal Negativa y se representa por
(∀ x) (P(x) → ¬Q(x)) y en español se lee ningún P cumple Q o sea que los que cumplen el predicado P(x) no cumples el predicado Q(x).
Ningún alumno llegó tarde se puede representar por (∀ x) (A(x) → ¬T(x)) donde A es alumno y T es llegó tarde.
Las dos expresiones restantes corresponden a casos particulares y para formarlas utilizamos el cuantificador existencial, y en lugar del operador condicional se usa la conjunción, así
I es (∃ x) (P(x) ∧ Q(x)) llamado Particular Afirmativa y
O es (∃ x) (P(x) ∧ ¬ Q(x)) que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el segundo aseguramos que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación, pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
Primeramente estableceremos dos reglas generales con un predicado simple:
Propiedad:
¬(∀ x) P(x) es equivalente a (∃ x) (¬ P(x))
¬(∃ x) P(x) es equivalente a (∀ x) (¬P(x))
Ahora sí, podemos combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la Universal Negativa.
O sea que la negación de la forma A es la forma O y la negación de la forma I es la forma E.
¬ (∀ x) (P(x) → Q(x)) es equivalente a (∃ x) (P(x) ^ ¬ Q(x))
¬ (∃ x) (P(x) ^ Q(x)) es equivalente a (∀ x) (P(x) → ¬Q(x))
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la negación de Alguno es Ninguno.
Esto es muy útil en matemáticas y en computación, por ejemplo si queremos demostrar que no es cierto que todas las funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
Variables Y Particularizaciones
En cálculo de predicados tenemos expresiones con variables, las variables pertenecen a un conjunto o dominio previamente determinado. Por lo que es muy importante definir el dominio cuado interpretamos una fórmula mediante un predicado específico.
Ejemplo:
x es alumno del ITT, que se podría representar por T(x), aquí el predicado T es “alumno del ITT” y el dominio podría ser el conjunto de los estudiantes de Tijuana. Otro caso es: x es azul, se representa A(x), el predicado “es de color azul” y podemos poner el dominio como el conjunto de los libros.
Una variable, en estos casos x, represente un valor cualquiera del dominio dado, y cuando le asignamos un valor específico a la variable se llama instancia o lo que programa menciona como particularición.
Así por ejemplo: Juan Pérez es alumno del ITT es una instancia del primer ejemplo y Mi libro de matemáticas es azul es una instancia del segundo ejemplo.
En el primer caso prodríamos considerar como dominio el conjunto de todos los alumnos de Tijuana, también podría ser sólo los alumnos de nivel profesional o también podríamos tener a todos los alumnos de México. Por eso es muy importante que se especifique con toda claridad el dominio.
Ejemplo:
x es alumno del ITT, que se podría representar por T(x), aquí el predicado T es “alumno del ITT” y el dominio podría ser el conjunto de los estudiantes de Tijuana. Otro caso es: x es azul, se representa A(x), el predicado “es de color azul” y podemos poner el dominio como el conjunto de los libros.
Una variable, en estos casos x, represente un valor cualquiera del dominio dado, y cuando le asignamos un valor específico a la variable se llama instancia o lo que programa menciona como particularición.
Así por ejemplo: Juan Pérez es alumno del ITT es una instancia del primer ejemplo y Mi libro de matemáticas es azul es una instancia del segundo ejemplo.
En el primer caso prodríamos considerar como dominio el conjunto de todos los alumnos de Tijuana, también podría ser sólo los alumnos de nivel profesional o también podríamos tener a todos los alumnos de México. Por eso es muy importante que se especifique con toda claridad el dominio.
Definición
Una fórmula en lógica de predicados es una expresión que se puede obtener mediante alguna de las formas siguientes: i) p(x1, x2, … ,xn) donde p es un símbolo que representa un predicado y x1, x2, … ,xn son símbolos de variable.ii) (¬ F) donde F es una fórmula de lógica de predicados.iii) (F G) donde F y G son fórmulas de lógica de predicados y es cualquiera de los operadores ^, v, →, ↔iv) (∀ x) F, donde F es un fórmula en lógica de predicados.v) (∃ x) F, donde F es un fórmula en lógica de predicados.
Nota: El paréntesis encerrando las expresiones en (ii) y (iii) es con el fin de evitar ambigüedades en las interpretaciones igual que en lógica de proposiciones,
Nota: El paréntesis encerrando las expresiones en (ii) y (iii) es con el fin de evitar ambigüedades en las interpretaciones igual que en lógica de proposiciones,
lunes, 28 de septiembre de 2009
Calculo de predicados
En cálculo de predicados tenemos elementos más simples para formar las expresiones atómicas, a diferencia de una proposición simple donde su valor es verdadero o falso de acuerdo a una interpretación, en cálculo de predicados el valor de verdad depende de los componentes que forman el predicado. Por ejemplo: Juan es padre de Pedro es una expresión en cálculo de predicados, que en general podría ser: x es padre de y, o simplemente p(x,y).
En otras palabras tenemos aquí una proposición abierta que depende de dos variables, y que por supuesto el valor de verdad depende de los valores que le demos a las varibles, porque por ejemplo: Luis es padre de Agustín puede tener un valor de verdad diferente al anterior.
En general podemos decir que un predicado puede tener una o más variables y que las variables pueden tomar valores de un conjunto específico llamado DOMINIO.
Así por ejemplo las dos expresiones mencionadas anteriormente son de la forma p(x,y) donde el predicado p representa “es padre de” y el domino es el conjunto de las personas.
Analiza cuáles son los predicados y las variables en los siguientes ejemplos:
El libro es azul
Armando y Eduardo son hermanos
Jesús es alumno del tecnológico
El concierto de Aranjuez es una composición de Joaquín Rodrigo
Elías tiene más años que René en el trabajo
Esteban compra mercancía los lunes en Almacenes A.
Solución:
AZ(x), AZ es el predicado: es de color azul, en el dominio de objetos.
H(x,y), H es el predicado: es hermano de, el dominio el conjunto de las personas.
T(x), T es el predicado: es alumno del Tecnológico, el dominio el conjunto de los estudiantes.
R(x), r es el predicado: es composición de Joaquín Rodrigo, el dominio de las obras musicales.
T(x,y), T es el predicado: tiene menos tiempo trabajando que, el dominio de las personas
A(x,y), A es el predicado: comprar en los almacenes cierto día, el dominio para el primer argumento es el de las personas, el dominio del segundo son los días de la semana.
Podemos observar que la definición del predicado es arbitraria y que para un mismo ejemplo podría variar la estrustura, por ejemplo en el predicado: El libro es azul, podríamos considerar como fórmula propuesta M(x,y), donde M es el predicado: es de color, y el dominio para la primera variable es el conjunto de los objetos y para la segunda el de los colores.
También observamos que el dominio puede ajustarse según las necesidades, por ejemplo, en el tercer ejemplo en T(x), x podría ser el conjunto de todos los alumnos de un país,o de una ciudad o de una disciplina.
Bicondicional
La bicondicional de dos proposiciones p, q da lugar a la proposición; p si y sólo si q, se representa por p ↔ q su tabla de verdad está dada por:
p q p ↔ q
V V V
V F F
F V F
F F V
Jerarquia de Operadores.
Combinando los operadores anteriores podemos formar nuevas expresiones.
En términos formales la negación de p, deberá ser ( ¬ p), así como la conjunción de p y q sería (p ^ q). Con el uso de paréntesis evitamos la ambiguedad, por ejemplo ¬p ^ q podría significar dos cosas distintas
Por un lado podría significar: (( ¬ p) ^ q) O también: ( ¬ (p ^ q)).
En la práctica para no usar tantos paréntesis se considera que el operador ¬ tiene jerarquia sobre ^, v, →, ↔. Así ¬ p ^ q significa (( ¬ p)^ q).
En algunos casos se considera ^, v tienen mayor jerarquía que ↔ por lo que p ↔ q v r sería (p ↔ (q v r)) y también que ^ tiene prioridad sobre v, por lo que p ^ q v r sería (p ^ q) v r.
Así por ejemplo, en electrónica, para representar circuitos lógicos se utiliza + en lugar de v y · en lugar de ^.
Por lo que p·q+r es ((p ^ q) v r).
En estos apuntes no se considerará jerarquía en ninguno de los operadores binarios ^, v, →, ↔ por lo que utilizaremos paréntesis. Sólo ¬ tiene prioridad sobre los demás operadores. Esto nos ahorrá algunos paréntesis, por ejemplo: ((( ¬ p) ^ q) v r) se representa por ( ¬ p ^ q) v r.
p q p ↔ q
V V V
V F F
F V F
F F V
Jerarquia de Operadores.
Combinando los operadores anteriores podemos formar nuevas expresiones.
En términos formales la negación de p, deberá ser ( ¬ p), así como la conjunción de p y q sería (p ^ q). Con el uso de paréntesis evitamos la ambiguedad, por ejemplo ¬p ^ q podría significar dos cosas distintas
Por un lado podría significar: (( ¬ p) ^ q) O también: ( ¬ (p ^ q)).
En la práctica para no usar tantos paréntesis se considera que el operador ¬ tiene jerarquia sobre ^, v, →, ↔. Así ¬ p ^ q significa (( ¬ p)^ q).
En algunos casos se considera ^, v tienen mayor jerarquía que ↔ por lo que p ↔ q v r sería (p ↔ (q v r)) y también que ^ tiene prioridad sobre v, por lo que p ^ q v r sería (p ^ q) v r.
Así por ejemplo, en electrónica, para representar circuitos lógicos se utiliza + en lugar de v y · en lugar de ^.
Por lo que p·q+r es ((p ^ q) v r).
En estos apuntes no se considerará jerarquía en ninguno de los operadores binarios ^, v, →, ↔ por lo que utilizaremos paréntesis. Sólo ¬ tiene prioridad sobre los demás operadores. Esto nos ahorrá algunos paréntesis, por ejemplo: ((( ¬ p) ^ q) v r) se representa por ( ¬ p ^ q) v r.
Condicional
La condicional de dos proposiciones p, q da lugar a la proposición; si p entonces q, se representa por p → q, y su tabla de verdad está dada por:
p q p→q
V V V
V F F
F V V
F F V
Con respecto a este operador binario, lo primero que hay que destacar es que no es conmutativo, a diferencia de los dos anteriores la conjunción y la disyunción. El único caso que resulta falso es cuando el primero es verdadero y el segundo falso.
Por ejemplo, si p es llueve y q es hay nubes entonces:
p → q es si llueve entonces hay nubes.
También cabe señalar que este viene a ser el operador más importante en el proceso deductivo y que la mayoría de las leyes de inferencia y las propiedades en matemáticas se pueden enunciar utilizando este operador.
Dada su importancia se le dedica una sección completa al final de la primera parte, sección
p q p→q
V V V
V F F
F V V
F F V
Con respecto a este operador binario, lo primero que hay que destacar es que no es conmutativo, a diferencia de los dos anteriores la conjunción y la disyunción. El único caso que resulta falso es cuando el primero es verdadero y el segundo falso.
Por ejemplo, si p es llueve y q es hay nubes entonces:
p → q es si llueve entonces hay nubes.
También cabe señalar que este viene a ser el operador más importante en el proceso deductivo y que la mayoría de las leyes de inferencia y las propiedades en matemáticas se pueden enunciar utilizando este operador.
Dada su importancia se le dedica una sección completa al final de la primera parte, sección
Disyuncion
La disyunción de dos proposiciones p, q es la operación binaria que da por resultado p ó q, notación p v q, y tiene la siguiente tabla:
p q p v q
V V V
V F V
F V V
F F F
Con la disyunción a diferencia de la conjunción, representamos dos expresiones y que afirman que una de las dos es verdadera, por lo que basta con que una de ellas sea verdaera para que la expresión p ∨ q sea verdadera.
Así por ejemplo la expresión: el libro se le entregará a Juan o el libro se le entregará a Luis significa que si va uno de los dos, el libro se le entrega, si van los dos también se entrega y solamente en caso de que no vaya ninguno de los dos no se debe entregar.
Aquí debemos tener cuidado, porque en español muchas veces utilizamos la disyunción para representar otros operadores que aparentemente son lo mismo, pero que tienen diferente significado.
En español tenemos tres casos de disyunción:
La llamada y/o bancaria, lógica o matemática, que es la misma y se utliza en computación como el operador OR, este operador corresponde al mencionado anteriormente p v q y ya se mostró su tabla de verdad.
La o excluyente, que algunos también le llaman o exclusiva, y que indica que una de las dos proposiciones se cumple, pero no las dos. Este caso corresponde por ejemplo a: Hoy compraré un libro o iré al cine; se sobrentiende que una de las dos debe ser verdadera, pero no la dos. Se representa por p XOR q y su tabla de verdad es:
p q p XOR q
V V F
V F V
F V V
F F F
Por último, también es muy común utilizar una disyunción como la siguiente: El menú incluye café o té. En este caso se esta dando una disyuntiva diferente pues no se pueden las dos simultáneamente como en el caso anterior, pero aquí si es válido el caso donde las dos son falsas. Es el caso “no ámbas”, se puede representar por p § q y su tablas es
p q p § q
V V F
V F V
F V V
F F V
Nota: El último símbolo no es estándar y puede haber varias formas de representarlo.
Un buen ejercicio consiste en enunciar varias expresiones del español que utilizando los conectivos y o para analizar cuál de los operadores es.
Hay que tener mucho cuidado cuando se traduce del lenguaje usual por las costumbres, muchas veces depende del contexto o de la situación específica en la que se usan los conectivos, por ejemplo si decimos: Se pueden estacionar alumnos y maestros, en realidad se está queriendo decir un operador disyuntivo, en este caso la o matemática, o sea el primer operador que corresponde a la primera tabla de esta sección.
p q p v q
V V V
V F V
F V V
F F F
Con la disyunción a diferencia de la conjunción, representamos dos expresiones y que afirman que una de las dos es verdadera, por lo que basta con que una de ellas sea verdaera para que la expresión p ∨ q sea verdadera.
Así por ejemplo la expresión: el libro se le entregará a Juan o el libro se le entregará a Luis significa que si va uno de los dos, el libro se le entrega, si van los dos también se entrega y solamente en caso de que no vaya ninguno de los dos no se debe entregar.
Aquí debemos tener cuidado, porque en español muchas veces utilizamos la disyunción para representar otros operadores que aparentemente son lo mismo, pero que tienen diferente significado.
En español tenemos tres casos de disyunción:
La llamada y/o bancaria, lógica o matemática, que es la misma y se utliza en computación como el operador OR, este operador corresponde al mencionado anteriormente p v q y ya se mostró su tabla de verdad.
La o excluyente, que algunos también le llaman o exclusiva, y que indica que una de las dos proposiciones se cumple, pero no las dos. Este caso corresponde por ejemplo a: Hoy compraré un libro o iré al cine; se sobrentiende que una de las dos debe ser verdadera, pero no la dos. Se representa por p XOR q y su tabla de verdad es:
p q p XOR q
V V F
V F V
F V V
F F F
Por último, también es muy común utilizar una disyunción como la siguiente: El menú incluye café o té. En este caso se esta dando una disyuntiva diferente pues no se pueden las dos simultáneamente como en el caso anterior, pero aquí si es válido el caso donde las dos son falsas. Es el caso “no ámbas”, se puede representar por p § q y su tablas es
p q p § q
V V F
V F V
F V V
F F V
Nota: El último símbolo no es estándar y puede haber varias formas de representarlo.
Un buen ejercicio consiste en enunciar varias expresiones del español que utilizando los conectivos y o para analizar cuál de los operadores es.
Hay que tener mucho cuidado cuando se traduce del lenguaje usual por las costumbres, muchas veces depende del contexto o de la situación específica en la que se usan los conectivos, por ejemplo si decimos: Se pueden estacionar alumnos y maestros, en realidad se está queriendo decir un operador disyuntivo, en este caso la o matemática, o sea el primer operador que corresponde a la primera tabla de esta sección.
Conexiones logicas y jerarquias
Conjucion
La conjunción de las proposiciones p, q es la operación binaria que tiene por resultado p y q, se representa por p^q, y su tabla de verdad es:
p q p^q
V V V
V F F
F V F
F F F
La conjunción nos sirve para indicar que se cumplen dos condiciones simultáneamente, así por ejemplo si tenemos:
La función es creciente y está definida para los números positivos, utilizamos
p ^ q, donde
p: la función es crecienteq: la función esta definida para los números positivos Así también: p ^ q, donde
p: el número es divisible por 3q: el número está representado en base 2
se lee: El número es divisible entre 3 y está representado en base 2.
Nota: Observamos que para la conjunción p ^ q sea verdadera las dos expresiones que intervienen deben ser verdaderas y sólo en ese caso como se indica por su tabla de verdad.
La conjunción de las proposiciones p, q es la operación binaria que tiene por resultado p y q, se representa por p^q, y su tabla de verdad es:
p q p^q
V V V
V F F
F V F
F F F
La conjunción nos sirve para indicar que se cumplen dos condiciones simultáneamente, así por ejemplo si tenemos:
La función es creciente y está definida para los números positivos, utilizamos
p ^ q, donde
p: la función es crecienteq: la función esta definida para los números positivos Así también: p ^ q, donde
p: el número es divisible por 3q: el número está representado en base 2
se lee: El número es divisible entre 3 y está representado en base 2.
Nota: Observamos que para la conjunción p ^ q sea verdadera las dos expresiones que intervienen deben ser verdaderas y sólo en ese caso como se indica por su tabla de verdad.
consepto de argumento y tipos de oposiciones lògicas
Los argumentos son una de las formas más comunes en matemáticas, en lógica y en computación de establecer razonamientos para llegar a la verdad.
Podemos tener también situaciones como:
Todos los hombres son mortales.Sócrates es hombre.Por lo tanto: Sócrates es mortal.
Si lo comparamos con:
Todos lo árboles son verdes.Todos lo pericos son verdes.Por lo tanto: Todos los árboles son pericos.
La pregunta importante es, ¿cómo saber si un razonamiento es válido? En general, la lógica proporciona los métodos para saber si un argumento es correcto y poder obtener conclusiones.
Un argumento es un conjunto de premisas, condiciones dadas, junto con una conclusión. Y decimos que un argumento es válido si la conclusión es verdadera siempre que las premisas lo son.
Uno de los principales propósitos de la lógica es por lo tanto encontrar la forma de poder saber si un argumento es válido o no. A esto le llamamos inferencia y está en la sección 1.7 Reglas de Inferencia.
Antes de poder decidir un argumento es válido o no, debemos de empezar por estudiar sus componentes, los elementos más simples que componen un argumento se llaman elementos atómicos.
Empezaremos por decir que en lógica proposicional utilizaremos dos valores asociados llamados valores de verdad, que son verdadero (V) y falso (F), y en computación a las expresiones que se les asocia uno de estos dos valores se les llama expresiones booleanas.
Los enunciados o expresiones del lenguaje se pueden clasificar en: Proposiciones lógicas, Proposiciones abiertas y Frases o expresiones indeterminadas.
Proposición lógica. Expresiones que pueden ser verdaderos o falsos pero no ambas.
Proposición abierta. Una expresión que contiene una o más variables y al sustituir las variables por valores específicos se obtiene una proposición lógica.
Frases. Todas las expresiones que no cumplen alguna de las dos definiciones anteriores.
Expresiones Booleanas. Proposiciones lógicas y proposiciones abiertas.
Ejemplo
i) México está en América Proposición Lógica
ii) 1 < 2 Proposición Lógica
iii) Hoy es lunes Proposición Abierta
iv) x+3=5 Proposición Abierta
v) Ecosistemas Frase
vi) Buenos días Frase
vii) El 3 de abril de 1970 fue domingo Proposición Lógica
viii) Los cocodrilos pueden volar Proposición Lógica
ix) Las matemáticas son agradables Proposición Abierta
x) Esta expresión es falsa Frase
Podemos tener también situaciones como:
Todos los hombres son mortales.Sócrates es hombre.Por lo tanto: Sócrates es mortal.
Si lo comparamos con:
Todos lo árboles son verdes.Todos lo pericos son verdes.Por lo tanto: Todos los árboles son pericos.
La pregunta importante es, ¿cómo saber si un razonamiento es válido? En general, la lógica proporciona los métodos para saber si un argumento es correcto y poder obtener conclusiones.
Un argumento es un conjunto de premisas, condiciones dadas, junto con una conclusión. Y decimos que un argumento es válido si la conclusión es verdadera siempre que las premisas lo son.
Uno de los principales propósitos de la lógica es por lo tanto encontrar la forma de poder saber si un argumento es válido o no. A esto le llamamos inferencia y está en la sección 1.7 Reglas de Inferencia.
Antes de poder decidir un argumento es válido o no, debemos de empezar por estudiar sus componentes, los elementos más simples que componen un argumento se llaman elementos atómicos.
Empezaremos por decir que en lógica proposicional utilizaremos dos valores asociados llamados valores de verdad, que son verdadero (V) y falso (F), y en computación a las expresiones que se les asocia uno de estos dos valores se les llama expresiones booleanas.
Los enunciados o expresiones del lenguaje se pueden clasificar en: Proposiciones lógicas, Proposiciones abiertas y Frases o expresiones indeterminadas.
Proposición lógica. Expresiones que pueden ser verdaderos o falsos pero no ambas.
Proposición abierta. Una expresión que contiene una o más variables y al sustituir las variables por valores específicos se obtiene una proposición lógica.
Frases. Todas las expresiones que no cumplen alguna de las dos definiciones anteriores.
Expresiones Booleanas. Proposiciones lógicas y proposiciones abiertas.
Ejemplo
i) México está en América Proposición Lógica
ii) 1 < 2 Proposición Lógica
iii) Hoy es lunes Proposición Abierta
iv) x+3=5 Proposición Abierta
v) Ecosistemas Frase
vi) Buenos días Frase
vii) El 3 de abril de 1970 fue domingo Proposición Lógica
viii) Los cocodrilos pueden volar Proposición Lógica
ix) Las matemáticas son agradables Proposición Abierta
x) Esta expresión es falsa Frase
lunes, 21 de septiembre de 2009
LOGICA-MATEMATICA
la longica-matematicas
La lógica matemática es un subcampo de la lógica y las matemáticas. Consiste en el estudio matemático de la lógica y en la aplicación de este estudio a otras áreas de las matemáticas. La lógica matemática guarda estrechas conexiones con la ciencias de la computación y la lógica filosófica.
La lógica matemática estudia los sistemas formales en relación con el modo en el que codifican conceptos intuitivos de objetos matemáticos como conjuntos, números, demostraciones y computación.
La lógica matemática suele dividirse en cuatro subcampos: teoría de modelos, teoría de la demostración, teoría de conjuntos y teoría de la recursión. La investigación en lógica matemática ha jugado un papel fundamental en el estudio de los fundamentos de las matemáticas.
La lógica matemática fue también llamada lógica simbólica. El primer término todavía se utiliza como sinónimo suyo, pero el segundo se refiere ahora a ciertos aspectos de la teoría de la demostración.
La lógica matemática no es la "lógica de las matemáticas" sino la "matemática de la lógica". Incluye aquellas partes de la lógica que pueden ser modeladas y estudiadas matemáticamente. Lógica Matemática fue el nombre dado por Giuseppe Peano para esta disciplina. En esencia, es la lógica de Aristóteles, pero desde el punto de vista de una nueva notación, más abstracta, tomada del álgebra.
La lógica matemática es un subcampo de la lógica y las matemáticas. Consiste en el estudio matemático de la lógica y en la aplicación de este estudio a otras áreas de las matemáticas. La lógica matemática guarda estrechas conexiones con la ciencias de la computación y la lógica filosófica.
La lógica matemática estudia los sistemas formales en relación con el modo en el que codifican conceptos intuitivos de objetos matemáticos como conjuntos, números, demostraciones y computación.
La lógica matemática suele dividirse en cuatro subcampos: teoría de modelos, teoría de la demostración, teoría de conjuntos y teoría de la recursión. La investigación en lógica matemática ha jugado un papel fundamental en el estudio de los fundamentos de las matemáticas.
La lógica matemática fue también llamada lógica simbólica. El primer término todavía se utiliza como sinónimo suyo, pero el segundo se refiere ahora a ciertos aspectos de la teoría de la demostración.
La lógica matemática no es la "lógica de las matemáticas" sino la "matemática de la lógica". Incluye aquellas partes de la lógica que pueden ser modeladas y estudiadas matemáticamente. Lógica Matemática fue el nombre dado por Giuseppe Peano para esta disciplina. En esencia, es la lógica de Aristóteles, pero desde el punto de vista de una nueva notación, más abstracta, tomada del álgebra.
Suscribirse a:
Entradas (Atom)
