Lógica matemática
se divide en cuatro áreas: teoría de modelos, teoría de la demostración, teoría de conjuntos y teoría de la computabilidad.
La teoría de conjuntos se originó en el estudio del infinito por Georg Cantor y ha sido la fuente de muchos de los temas más desafiantes e importantes de la lógica matemática
La teoría de la demostración y la teoría de modelos fueron el fundamento de la lógica matemática.
Inducción matemática
La inducción matemática es un método de demostración que se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones. El método es bastante natural para usarse en una variedad de situaciones en la ciencia de la computación. En términos simples, la inducción matemática consiste en el siguiente razonamiento
Caso base distinto de 0 o 1
Inducción en más de un contador
Descenso infinito
Inducción fuerte
Lógica proposicional.
Una lógica proposicional, o a veces lógica de orden cero, es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas lógicas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.
se divide en:
Equivalencias lógicas
Proposiciones simples y compuestas.
Tablas de verdad
Reglas de inferencia
Tautologías, contradicción y contingencia.
Demostración formal
Argumentos válidos y no válidos
Una tautología es una expresión lógica que es verdadera para todos los posibles valores de verdad de sus componentes atómicos. Las proposiciones dan el resultado positivo.
Las proposiciones simples son aquellas que no tienen otras oraciones dentro de sí mismas. Las proposiciones compuestas son aquellas que contienen dentro de sí más de una proposición simple.
En lógica, las declaraciones p y q son lógicamente equivalentes si tienen el mismo contenido lógico. Este es un concepto semántico, dos afirmaciones son equivalentes si tienen el mismo valor de verdad en todos los modelos.
Una tabla de verdad, o tabla de valores de verdades, es una tabla que muestra el valor de verdad de una proposición compuesta, para cada combinación de verdad que se pueda asignar.
En lógica, una regla de inferencia, o regla de transformación es una forma lógica que consiste en una función que toma premisas, analiza su sintaxis, y devuelve una conclusión (o conclusiones).
es un argumento deductivo para asegurar la verdad de una proposición matemática. En la argumentación se pueden usar otras afirmaciones previamente establecidas, tales como teoremas o bien las afirmaciones iniciales o axiomas
Algebra declarativa
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.
En el cálculo proposicional existen algunas tautologías especialmente útiles cuya demostración se reduce a la confección de su correspondiente tabla de verdad, a saber:
Asociatividad:
Distributividad:
Conmutatividad:
Leyes de De Morgan:
Idempotencia:
Negación de una Implicación:
Involución:
¬ (¬ p) ↔ p (se lee “no, no p, equivale a p”)
(p ^ ¬ p) ↔ p (p v ¬ p) ↔ p
a) de la disyunción: p v q ↔ q v p
b) de la conjunción: p ^ q ↔ q ^ p
a) de la disyunción: (p v q) v r ↔ p v (q v r)
b) de la conjunción: (p ^ q) ^ r ↔ p ^ (q ^ r)
De la conjunción respecto de la disyunción: (p Ú q) Ù r ↔ (p Ù r) Ú (q Ù r)
De la disyunción respecto de la conjunción: (p Ù q) Ú r ↔ (p Ú r) Ú (q Ú r)
Las proposiciones p Þ q y ~ (p Ù ~ q) son equivalentes, como vemos realizando la tabla de valores correspondientes:
~ ( p Ú q ) ↔ ~ p Ù ~ q
“La negación de una disyunción equivale a la conjunción de las negaciones”
~ ( p Ù q ) ↔ ~ p Ú ~ q
“La negación de una conjunción equivale a la disyunción de las negaciones”
Lógica de predicados
La lógica de predicados está basada en la idea de las sentencias realmente expresan relaciones entre objetos, así como también cualidades y atributos de tales objetos. Los objetos pueden ser personas, objetos físicos, o conceptos. Talescualidades, relaciones o atributos, se denominan predicados.Los objetos se conocen como argumentos o términos delpredicado.
Cuantificadores.
En lógica, teoría de conjuntos y matemáticas en general, los cuantificadores son símbolos utilizados para indicar cuántos elementos de un conjunto dado cumplen con cierta propiedad. Existen muchos tipos de cuantificadores, pero quizás los más estudiados y utilizados sean:
Cuantificador universal Para todo x, y… Cuantificador existencial Existe al menos un x, y… Cuantificador existencial único Existe exactamente un x, y… Negación del cuantificador existencial No existe ningún x, y… Declaraciones cuantificadas Las declaraciones cuantificadas se escriben en la forma: Para todo x que pertenece a R, se cumple que 2x pertenece a R. Para todo a que pertenece a R, existe x que pertenece a R, que está comprendido entre a y a+1 Para todo a que pertenece a R diferente de cero, existe un único x que pertenece a R, que cumple que a por x es igual a 1.
Representación y evaluación de predicados.
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. Por ejemplo: ” X . . . . 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 . . . “
A continuación se dan algunos 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)].
Aplicaciones de la lógica matemática en 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.
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.
Un argumento es válido si el hecho de que todas las premisas sean verdaderas obligan a que la conclusión sea verdadera. Un argumento no válido es una falacia. Varias técnicas para saber si un argumento es válido.
