3.LÓGICA MATEMÁTICA

3.LÓGICA MATEMÁTICA

1. 3.1 LÓGICA PROPOSICIONAL

   • 3.1.1 PROPOSICIONES SIMPLES Y COMPUESTAS
     • 3.1.2 TABLAS DE VERDAD
       • 3.1.3 TAUTOLOGÍAS, CONTRADICCIÓN Y CONTIGENCIA
         • 3.1.4 EQUIVALENCIAS LÓGICAS
           • 3.1.5 REGLAS DE INFERENCIA
             • 3.1.6 ARGUMENTOS VALIDOS Y NO VALIDOS
               • 3.1.7 DEMOSTRACIÓN FORMAL
                 • Un argumento es una secuencia de afirmaciones, todas las afirmaciones excepto la última se llamarán premisas, suposiciones o hipótesis, la declaración final se llamará conclusión. Argumentar consiste en deducir una conclusión a partir de una premisa que se tienen por verdaderas. Un argumento, por lo tanto, estará compuesto de unas premisas y de una conclusión Lo que hace que podamos hablar de razonamiento es la relación que existe entre los enunciados que llamamos premisas y la conclusión. Diremos que un argumento es argumento válidos y para cualquier valor de las variables proposicionales involucradas en las fórmulas que hacen verdaderas las premisas la conclusión es verdadera. Argumento: Conjunto de formulas para el razonamiento lógico. Argumento Valido: Un argumento es valido si se cumple:
               • Un argumento es una secuencia de afirmaciones, todas las afirmaciones excepto la última se llamarán premisas, suposiciones o hipótesis, la declaración final se llamará conclusión. Argumentar consiste en deducir una conclusión a partir de una premisa que se tienen por verdaderas. Un argumento, por lo tanto, estará compuesto de unas premisas y de una conclusión Lo que hace que podamos hablar de razonamiento es la relación que existe entre los enunciados que llamamos premisas y la conclusión. Diremos que un argumento es argumento válidosi para cualquier valor de las variables proposicionales involucradas en las fórmulas que hacen verdaderas las premisas la conclusión es verdadera. Argumento: Conjunto de formulas para el razonamiento logico. Argumento Valido: Un argumento es valido si se cumple.
             • 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. Las reglas de inferencia logica, entre otras, son: el Modus Ponendo Ponens (MPP), el Modus Tollendo Tollens (MTT) y el Modus Tollendo ponens (MTP), expresiones latinas que traducen: Metodo que afirmando afirma, Metodo que negando niega y Metodo que negando afirma respectivamente.
           • Decimos que dos proposiciones p , q son equivalentes cuando cada una de ella implica a la otra.Todas las conectivas, por definición, son equivalentes entre sí. Esto permite sustituir a una conectiva por otra en un sistema axiomático formalizado de acuerdo a ciertas reglas previamente establecidas. También es posible reducir cualquier fórmula a una fórmula elemental en la que las conectivas sean únicamente la conjunción, la disyunción y la negación. Esto permite simplificar mucho la estructura de un lenguaje formalizado porque con ello se puede reducir la cantidad de conectivas utilizadas. A fin de indicar la equivalencia de dos proposiciones p, q se emplea cualquiera de los giros siguientes: (E1) P es equivalente a Q (E2) P = Q (E3) P implica a Q, y viceversa (E4) P es condición necesaria y suficiente para Q
         • TAUTOLOGÍA Las tautologías son identidades lógicas que siempre serán verdaderas, no son solo un útil objeto en la lógica son usadas primordialmente para pruebas sentenciales, desempeñan un papel fundamental en los procesos de la deducción dentro de esta lógica (sentencial). Ejemplo: La expresión ‘(p ^ q) → (p v r)’ es una tautología.
           • CONTRADICCIÓN Si una proposición compuesta es falsa para todas las asignaciones entonces es una contradicción. Son formulas sentencialmente contra-validas o de tercer grado. Ejemplo: P ∧ ¬P (se lee: P y no P). Su tabla de verdad es la siguiente.
             • CONTIGENCIA Se utilizan para hacer circuitos de control y automatismo, surgen cuando en dos proposiciones, su equivalencia es verdadera y falsa a la vez. Ejemplo: A^(BVC)
       • Estas tablas pueden construirse haciendo una interpretación de los signos lógicos como: no, o, y, si…entonces, sí y sólo si, respectivamente. La interpretación corresponde al sentido que estas operaciones tienen dentro del razonamiento. Puede establecerse una correspondencia entre los resultados de estas tablas y la deducción lógico matemática. En consecuencia, las tablas de verdad constituyen un método de decisión para chequear si una proposición es o no un teorema. Para la construcción de la tabla se asignará el valor 1(uno) a una proposición cierta y 0 (cero) a una proposición falsa.
       • Negación: Si p es una proposición fundamental, de ésta se puede formar otra proposición, que se le llama Negación de p, escribiendo: “Es falso que” antes de p, ó, cuando es posible, se inserta en p la palabra “No”, (¬p) Su símbolo es: ¬, ~
         • Disyunción: Se representan dos enunciados separadas por la expresión o basta con que una sea verdadera para que se cumpla la proposición (pvq). Su símbolo es: V
           • Conjunción: Es cuando dos proposiciones simples se combinan mediante la expresión y , la proposición compuesta resultante se le llama conjunción (pΛq). Su símbolo es: Λ, &, ·
             • Condicional: El condicional material es un operador que opera sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad falso sólo cuando la primera proposición es verdadera y la segunda falsa, y verdadero en cualquier otro caso. La condicional de dos proposiciones p, q da lugar a la proposición; si p entonces q, se representa por p → q
               • Bicondicional: O doble implicación es un operador que funciona sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad verdadero cuando ambas proposiciones tienen el mismo valor de verdad, y falso cuando sus valores de verdad difieren.
                 • p: ”10 es un número impar” q: “6 es un número primo” p↔q: “10 es un número impar si y solo si 6 es un número primo” p: ”3 + 2 = 7″ q: “4 + 4 = 8″ p↔q: “3 + 2 = 7 si y solo si 4 + 4 = 8″
               • EJEMPLO Si está dormido entonces está soñando. Si quiere comer entonces tiene hambre. Si Londres está en Inglaterra entonces París está en Francia. Si hay gasolina en mi tanque entonces mi automóvil funciona.
             • EJEMPLO La puerta está vieja y oxidada. Hace frío y está nevando. Está lloviendo y es de noche. Tiene gasolina y tiene corriente.
           • EJEMPLO Está lloviendo o es de noche. Está feliz o está enojado. Está caminando o está lloviendo. Hay derivadas o hay integrales.
         • EJEMPLO No está lloviendo. La señora no ceno. Es falso que 5×2=12. Es falso que Alemania se encuentra en Europa.
     • PROPOSICIONES SIMPLES Son aquellas que no tienen oraciones componentes afectadas por negaciones (“no”) o términos de enlace como conjunciones (“y”), disyunciones (“o”) o implicaciones (“si . . . entonces”). Pueden aparecer términos de enlace en el sujeto o en el predicado, pero no entre oraciones.
       • EJEMPLO •La ballena es roja. •La raíz cuadrada de 16 es 4, •Gustavo es alto. •Teresa va a la escuela.
     • PROPOSICIONES COMPUESTAS Una proposición compuesta es una frase que consta de uno o varios sujetos y de un predicado que afirma algo en torno a dichos sujetos.Los sujetos de una proposición simple deben ser todos términos singulares. El predicado debe contener un verbo que exprese la acción sobre los sujetos. Enmatemáticas se usan ciertos símbolos para representar predicados de uso frecuente como: el símbolo “_”, como representante del predicado “es igual a “, y el símbolo “<” como sustituto de “es menor que”.
       • EJEMPLO •La ballena no es roja. •Gustavo no es alto. •Teresa va a la escuela o María es inteligente. •4 es menor que 8 o 6 es mayor que 10. •El 1 es el primer número primo y es mayor que cero.
   • La lógica proposicional trata sobre la verdad o la falsedad de las proposiciones y de cómo la verdad se transmite de unas proposiciones (premisas) a otras (conclusión). Una proposición es la unidad mínima de significado susceptible de ser verdadera o falsa.
     • EJEMPLO: Todos los hombres son mortales es una proposición atómica porque ninguno de sus elementos componentes es una proposición. Como podemos observar, una proposición atómica es verdadera o falsa, y su verdad o falsedad no depende de otras proposiciones, sino de cómo es la realidad. Si hubiera algún hombre inmortal, la proposición del ejemplo sería falsa.

2. 3.2 LÓGICA DE PREDICADOS

   • 3.2.1 CUANTIFICADORES
     • 3.2.2 REPRESENTACIÓN Y EVALUACIÓN DE PREDICADOS
       • 3.2.3 ALGEBRA DECLARATIVA
         • 3.2..4 INDUCCIÓN MATEMÁTICA
           • 3.2.5 APLICACIONES DE LA LÓGICA MATEMÁTICA EN LA COMPUTACIÓN
             • La lógica computacional Es la misma lógica matemática aplicada al contexto de las ciencias de la computación. Su uso es fundamental a varios niveles: en los circuitos computacionales, en la programación lógica y en el análisis y optimización (de recursos temporales y espaciales) de algoritmos.
               • ALGORITMOS
                 • Conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiéndolos pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia. El pseudocódigo es una herramienta algorítmica que permite escribir pseudoprogramas(una imitación de un programa real) utilizando un lenguaje de pseudoprogramación que es una imitación de los lenguajes de programación de alto nivel. Así, un pseudocódigo es una combinación de símbolos (+, -, *, /, %, >, >=, <, <=, !=, ==, y, o, no), términos(Leer, Imprimir, Abrir, Cerrar, Hacer…Mientras, Mientras…Hacer, Para…Mientras, etc.) y otras características comúnmente utilizadas en uno o más lenguajes de alto nivel.
               • CIRCUITOS COMPUTACIONALES
                 • El nivel menos abstracto dentro de una computadora está constituido por circuitos electrónicos que responden a diferentes señales eléctricas, siguiendo los patrones de la lógica booleana; esto es, compuertas lógicas que devuelven un valor dependiendo de las entradas que se le dan al sistema. Existen ocho compuertas lógicas básicas con las cuales se pueden formar sistemas muy complejos: AND, OR, Inverter, Buffer, NAND, NOR, XOR y XNOR. Todas ellas son representadas mediante un símbolo y una tabla de valores de verdad, que es simplemente un cuadro donde se ubican todas las posibles entradas y los valores que devolvería la compuerta dados dichos valores. Todo sistema computacional, por muy complejo que sea, no está compuesto por más que circuitos electrónicos que únicamente entienden un lenguaje binario. La lógica computacional se encarga de modelar y optimizar tales sistemas a este nivel.
               • PROGRAMACIÓN LÓGICA
                 • La programación lógica consiste en la aplicación del corpus de conocimiento sobre lógica para el diseño de lenguajes de programación; La programación lógica es un tipo de paradigmas de programación dentro del paradigma de programación declarativa. El resto de los subparadigmas de programación dentro de la programación declarativa son: programación funcional, programación basada en restricciones, programas DSL (de dominio específico) e híbridos. La programación lógica gira en torno al concepto de predicado, o relación entre elementos. La programación funcional se basa en el concepto de función (que no es más que una evolución de los predicados), de corte más matemático.
           • En las matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro n que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento: Premisa mayor: El número entero a tiene la propiedad P. Premisa menor: El hecho de que cualquier número entero n tenga la propiedad P implica que n + 1 también la tiene. Conclusión: Todos los números enteros a partir de a tienen la propiedad P.
             • Conclusión: Todos los números enteros a partir de a tienen la propiedad P. 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ón k e S se llama Hipótesis de Inducción Y como ya se mencionó todo junto se llama Principio de Inducción Matemática.
         • Lo que algunos llaman álgebra declarativa no es otra cosa que el álgebra proposicional, o sea, la estructura algebraica que se forma con expresiones utilizando los conectivos lógicos. Empezaremos por definir formalmente cómo se construye una fórmula en lógica. Una expresión sintácticamente correcta se le llama fórmula bien formada (fbf) o simplemente fórmula y su definición es: Una fórmula en lógica de proposiciones se obtiene al aplicar una ó más veces las siguientes reglas: (B) si p es una proposición lógica, es una fbf. (R) si F es una fórmula bien formada (fbf) también lo es (¬F). (R) si p,q son fbf entonces también lo es (p*q) donde * es uno de los operadores binarios, ^ v → ↔.
           • Negación de una Implicación Las proposiciones p Þ q y ~ (p Ù ~ q) son equivalentes, como vemos realizando la tabla de valores correspondientes: Lo que algunos llaman álgebra declarativa no es otra cosa que el álgebra proposicional, o sea, la estructura algebraica que se forma con expresiones utilizando los conectivos lógicos. Empezaremos por definir formalmente cómo se construye una fórmula en lógica. Una expresión sintácticamente correcta se le llama fórmula bien formada (fbf) o simplemente fórmula y su definición es: Una fórmula en lógica de proposiciones se obtiene al aplicar una ó más veces las siguientes reglas: (B) si p es una proposición lógica, es una fbf. (R) si F es una fórmula bien formada (fbf) también lo es (¬F). (R) si p,q son fbf entonces también lo es (p*q) donde * es uno de los operadores binarios, ^ v → ↔.
       • La principal debilidad de la lógica proposicional es su limitada habilidad para expresar conocimiento. Existen varias sentencias complejas que pierden mucho de su significado cuando se las representa en lógica proposicional. Por esto se desarrolló una forma lógica más general, capaz de representar todos los detalles expresados en las sentencias, esta es la lógica de predicados. Al igual que las proposiciones, los predicados tienen un valor de veracidad, pero a diferencia de las preposiciones, su valor de veracidad, depende de sus términos. Es decir, un predicado puede ser verdadero para un conjunto de términos, pero falso para otro. La lógica de predicados, se ocupa únicamente de métodos de argumentación sólidos. Tales argumentaciones se denominan Reglas de Inferencia. Si se da un conjunto de axiomas que son aceptados como verdaderos, las reglas de inferencia garantizan que sólo serán derivadas consecuencias verdaderas. El cuantificador universal; “ indica que la fórmula bien formad
         • Establece que “para todo X, es verdad que . . . “ El cuantificador existencial;$ , indica que la fórmula bien formada, dentro de su alcance, es verdadera para algún valor o valores dentro del dominio. Por ejemplo: $ X . . . . Establece que “existe un X, tal que . . . “ Ejemplos de predicados cuantificados: “ X, [niño (X) => le_gusta (X, helados)]. “ Y, [mamífero (Y) => nace (Y, vivo)]. $ Z, [cartero(Z) ^ mordió (boby, Z)].
     • Un cuantificador se utiliza para indicar cuántos elementos de un conjunto dado cumplen con cierta propiedad. Existen dos tipos de cuantificadores, cuyas características resumimos en la siguiente tabla: Nombre Notación Se lee cuantificador universal Para todo x… cuantificador existencial Existe por lo menos un x… Los cuantificadores: · Cuantificador universal (para todo). El cuantificador universal permite referirse a todos los individuos del universo del discurso. · Cuantificador existencial (existe). El cuantificador existencial permite referirse a algunos de los individuos del universo del discurso. Las variables, también pueden ser cuantificadas. Los cuantificadores que típicamente se utilizan en lógica de predicados son: El cuantificador universal; ” indica que la fórmula bien formada, dentro de su alcance, es verdadera para todos los valores posibles de la variable que es cuantificada
       • EJEMPLO De la proposición: Todos lo números son pares Se convierten Existe x tal que x es un número y x es par.
   • La lógica de predicados es un lenguaje mas de la matemáticas. Sin menospreciar otros sistemas de lógica que se han estudiado, algunos por razones filosóficas y otros por la importancia de sus aplicaciones, incluyendo las ciencias de la computación.La lógica de predicados, se ocupa únicamente de métodos de argumentación sólidos. Tales argumentaciones se denominan Reglas de Inferencia,tema mencionado anteriormente. Si se da un conjunto de axiomas que son aceptados como verdaderos, las reglas de inferencia garantizan que sólo serán derivadas consecuencias verdaderas. En las ciencias de la computación, sabemos que muchas cosas pueden ser codificadas en bits y esto justifica la restricción de la lógica boleana (dos valores).En ocasiones es conveniente hacer referencia directamente a tres ó mas valores discretos.
     • EJEMPLO Consideremos las 2 sentencias, “1 < 2″ y “Esta lloviendo”. la primera sentencia siempre es verdadera mientras que la segunda es verdadera solo en algunas ocasiones. esto puede ser expresado en el cálculo de predicados como: ‘Para todas ocasiones de t, el valor “1 < 2″ en la ocasión t, es verdadero’ y ‘Para algunas ocasiones de t, el valor de “Esta lloviendo”, en la ocasión t es verdadero’.

3. La lógica matemática estudia los sistemas formales en relación con el modo en el que codifican o definen nociones intuitivas de objetos matemáticos como conjuntos, números, demostraciones, y algoritmos, utilizando un lenguaje formal . 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 recursion. La investigación en lógica matemática ha jugado un papel fundamental en el estudio de los fundamentos de las matemáticas. Actualmente se usan indiferentemente como sinónimos las expresiones: lógica simbólica (o logística), lógica matemática, lógica teorética y lógica formal. 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.

Imágenes y archivos del mapa