3.1.8 Demostración formal (Directa, Por contradicción)

Un sistema matemático consta de axiomas, definiciones y términos no definidos. Se suponen verdaderos los axiomas. Las definiciones se utilizan para crear conceptos nuevos en términos de los existentes. Algunos términos no se definen en forma explicita, sino que se definen en forma implícita mediante los axiomas. Dentro de un sistema matemático es posible deducir teoremas. Un Teorema es una proposición cuya verdad se ha demostrado.

Un argumento que establece la verdad de un teorema es una demostración. La lógica es una herramienta para el análisis de las demostraciones. En esta sección describiremos dos métodos generales de demostración: Directa y por contradicción.

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.

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 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.

http://www.mitecnologico.com/Main/DemostracionesFormales

http://docencia.udea.edu.co/cen/logica/cap3.htm

 

3.2 Lógica de predicados

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.

Por ejemplo una compuerta lógica puede estar en un estado indeterminado antes de basarse en un nivel estable de voltaje. Esto puede ser formalizado en tres valores lógicos con un valor {$ X $} en la suma de de verdadero y falso. La definición de los operadores se extiende a los nuevos valores, por ejemplo, {$ X $} y verdadero = {$ X $}.

Veamos un 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’.

http://elcentro.uniandes.edu.co/cr/mate/estructural/libro/enero/node5.html

 

http://www.monografias.com/trabajos/iartificial/pagina4_2.htm

http://www.paginasobrefilosofia.com/html/predtrad.html

3.2.1 Cuantificadores

1. 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. 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 . . . «

Las declaraciones cuantificadas se escriben en la forma que se leen «para todo x, es verdad que p» y «existe por lo menos un y tal que q es verdad».

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.

 

http://huitoto.udea.edu.co/SistemasDiscretos/contenido/cuantificadores.html

http://www.victorbravo.info/media/archivos/MD2Logica.pdf

3.2.2 Representación y evaluación de predicados

La lógica de predicados es un lenguaje mas de la matemáticas  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. Tales cualidades,relaciones o atributos, se denominan predicados.

Al construir los predicados se asume que su veracidad está basada en su relación con el mundo real. Naturalmente, siendo prácticos, trataremos que los predicados que definimos estén de acuerdo con el mundo que conocemos, pero no es absolutamente necesario que así lo hagamos. En lógica de predicados el establecer como verdadero un predicado es suficiente para que así sea considerado.

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.

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)].

Desde el punto vista de representación, los cuantificadores son difíciles de usar. Por lo que es deseable reemplazarlos con alguna representación equivalente, más fácil de manipular. El caso del cuantificador universal es más simple ya que se asume a todas las variables como universalmente cuantificadas.

 

 

http://www.wikilearning.com/curso_gratis/logica_matematica-lpred_cuantificadores/24609-8

 

http://www.smartcomputing.com.ar/logica-de-primer-orden.aspx

3.3 Álgebra 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.

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 → ↔.

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:

Involución

¬ (¬ p) ↔ p (se lee «no, no p, equivale a p»)

Idempotencia

(p ^ ¬ p) ↔ p

(p v ¬ p) ↔ p

Conmutatividad

a) de la disyunción: p v q ↔ q v p

b) de la conjunción: p ^ q ↔ q ^ p

Asociatividad

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)

Distributividad:

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)

Leyes de De Morgan

~ ( 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»

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 → ↔.

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:

Involución

¬ (¬ p) ↔ p (se lee «no, no p, equivale a p»)

Idempotencia

(p ^ ¬ p) ↔ p

(p v ¬ p) ↔ p

Conmutatividad

a) de la disyunción: p v q ↔ q v p

b) de la conjunción: p ^ q ↔ q ^ p

Asociatividad

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)

Distributividad:

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)

Leyes de De Morgan

~ ( 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»

Negación de una Implicación

Las proposiciones p Þ q y ~ (p Ù ~ q) son equivalentes, como vemos realizando la tabla de valores correspondientes:

p	q	p Þ q	(p Ù ~ q)	~(p Ù ~ q)	p Þ q  ~(p Ù ~ q)
V V F F	V F V F	V F V V	F V F F	V F V V	V V V V

Con esto, comprobamos que la negación de la primera equivale a la negación de la segunda, es decir

~ (p Þ q) Û ~{ ~(p Ù ~ q)}, y podemos concluir entonces que:  ~ ( p Þ q ) Û ( p Ù ~ q)

Es decir, la negación de una implicación no es una implicación sino la conjunción del antecedente con la negación del consecuente.

Ejemplo: Sea la implicación p: hoy es viernes entonces mañana es domingo

Su negación es ~ p: hoy es viernes y mañana no es domingo.

A continuación un video…

http://www.mitecnologico.com/Main/AlgebraDeclarativa

http://www.slideshare.net/rezzaca/u15-lgebra-declarativa

3.4 Inducción matemática

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.

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.

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.

Recuerda:

A continuación un video de apoyo…

 

http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica

http://induccionmatematica.galeon.com/

3.5 Aplicación 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.

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.

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.