logica y algoritmia: LOGICA Y ALGORITMIA...

PRIMERA TUTORIA...

DATOS VARIABLES Y CONSTANTES...

Métodos de demostración.

Demostración por el método directo.

Supóngase que p®q es una tautología, en donde p y q pueden ser proposiciones compuestas, en las que intervengan cualquier número de variables propositvas, se dice que q se desprende lógicamente de p. Supóngase una implicación de la forma.

(p1 Ù p2 Ù.......Ù pn) Þ q

Es una tautología. 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

Realmente el camino que se debe seguir para llevar a cabo una demostración formal usando el método directo. Significa que sí se sabe que p1 es verdadera, p2 es verdadera,...... y pn también es verdadera, entonces se sabe que q es verdadera.

Prácticamente todos los teoremas matemáticos están compuestos por implicaciones de este tipo.

(p1 Ù p2 Ù.......Ù pn) Þ q

Donde la pi 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 pi son verdaderas.

Toda demostración debe comenzar con las hipótesis, seguidas de las tautologías y reglas de inferencia necesarias, hasta llegar a la conclusión.

A continuación se prueba un enunciado en donde se puede apreciar el uso tanto de las tautologías como de las reglas de inferencia.

Sean

p: Trabajo.
q: Ahorro.
r: Compraré una casa.
s: Podré guardar el coche en mi casa.

Analizar el siguiente argumento:
"Si trabajo o ahorro, entonces compraré una casa. Si compro una casa, entonces podré guardar el coche en mi casa. Por consiguiente, si no puedo guardar el coche en mi casa, entonces no ahorro".

El enunciado anterior se puede representar como:

p Ú q ® r; y r ® s; entonces s' ® q'

Equivale también a probar el siguiente teorema:

[(p Ú q) ® r] Ù [r ® s] Þ [s' ® q']

Como se trata de probar un teorema de la forma general:

p1 Ù p2 Ù......Ù pn Þ q

Se aplica el procedimiento general para demostración de enunciados válidos. A continuación se demuestra el teorema respaldando cada uno de sus pasos en tautologías o reglas de inferencia ya conocidas.

1.- (p Ù q) ® r Hipótesis
2.- r ® s Hipótesis
3.- q ® (q Ù p) Adición tautología 10
4.- q ® (p Ú q) 3; ley conmutativa, regla 2
5.- q ® r 4,1; silogismo hipotético, regla 22
6.- q ® s 5,2; regla 22
7.- s' ® q' 6; contrapositiva, regla 7.

El enunciado es válido aunque la conclusión puede ser falsa o verdadera.

Es recomendable numerar cada uno de los pasos. Se puede notar que las primeras líneas son hipótesis, la línea 3 es una tautología conocida y de la línea 4 a 7 se obtuvieron aplicando reglas de inferencia. Se indica la regla de inferencia aplicada por medio del número de la derecha, y las líneas a las cuales se les aplicó dicha regla de inferencia por medio de los números de la izquierda.
El ejemplo anterior es una demostración sencilla, pero puede ser tan complicada como sea necesario y el método debe funcionar.
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 ® (p Ù r) ] Ù [(q Ú s) ® t ]Ù (p Ú s) Þ t

Demostración

1.- p ® (p Ù r) Hipótesis
2.- (q Ú s) ® t Hipótesis
3.- p Ú s Hipótesis
4.- t’ Negación de la conclusión
5.- (qÚ s)’ 2,4; Modus tollens, regla 25
6.- q’ Ù s’ 5; Ley de Morgan, 6ª
7.- q’ 6; Simplificación, regla 20
8.- s’ Ù q’ 6; Ley conmutativa, 2b
9.- s’ 8; Simplificación, regla 20
10.- sÚ p 3; Ley conmutativa, 2ª
11.- p 10,9; Silogismo disyuntivo, regla 21
12.- q Ù r 11,1; Modus ponens, regla 24
13.- q 12; Simplificación, regla 29
14.- q Ù q’ 13,7; Conjunción, regla 23
15.- Contradicción.

Note que juntamente con las premisas se debe incluir la negación de la conclusión. 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 mencionadosLa 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.

Conclusiones.

La idea principal de este trabajo es que el alumno aprenda el concepto de proposición, la forma en que se pueden formar proposiciones compuestas usando los conectores lógicos, representar enunciados por medio de simbología lógica, conocer los conceptos de tautología, equivalencia lógica, regla de inferencia. Realizar demostraciones de teoremas por medio del método directo y contradicción. Pero con problemas que le sean familiares e interesantes. Se trata de que en cada uno de los subtemas participe proponiendo sus propios ejemplo y que sobre todo al final de la unidad él tenga la habilidad, confianza e iniciativa para inferir posibles soluciones.

Todo enunciado puede ser planteado en términos de teoremas. Un teorema por lo general es resultado de un planteamiento de un problema, este planteamiento debe tener el siguiente formato.

(p1 Ù p2 Ù.......Ù pn) Þ q

Como se establece p1, p2 ,......,pn son hipótesis (o premisas) derivadas del mismo problema y que se consideran válidas. Pero además deberán conectarse con el operador And (Ù), lo cual implica que p1 es cierta y (Ù) p2 es verdad y (Ù)...... y pn también es cierta entonces (Þ) la conclusión (q) es cierta. Para realizar la demostración formal del teorema se deberá partir de las hipótesis, y después obtener una serie de pasos que también deben ser válidos, ya que son producto de reglas de inferencia. Sin embargo no solamente las hipótesis y reglas de inferencia pueden aparecer en una demostración formal, sino también tautologías conocidas. En el teorema anterior cada uno de los pasos p1, p2,...pn son escalones que deberán alcanzarse hasta llegar a la solución.

Lo mismo ocurre con todo tipo de problemas que se nos presentan en la vida, antes de llegar a la solución debemos alcanzar ciertas metas (p1,p2,....pn) hasta llegar al objetivo o conclusión (q). Pero una vez que logramos el objetivo debemos plantearnos nuevos objetivos que nos permitirán superarnos.

Dependiendo del área de interés al estudiante puede transportad dichos conocimientos, de tal manera que le auxilien para entender y resolver otro tipo de problemas. En el caso de computación cada línea de un programa se obtiene inconcientemente aplicando una regla de inferencia y por lo tanto cada instrucción tiene su orden en que debe de ir colocada, si se cambia esa línea seguramente el resultado ya no será igual. Pero hay tantas formas de resolver un problema por medio de un programa como alumnos distintos tenga un maestro.

Una demostración formal equivale a relacionar esquemas para formar estructuras cognitivas. Sí el alumno sabe inferir soluciones lógicas, estará en condiciones de resolver todo tipo de problemas.
Uno de los objetivos principales del constructivismo, es la construcción del conocimiento. El tema de “lógica matemática”, se presta para que el alumno pueda realizar los relacionamientos entre las distintas proposiciones, esto permite crear nuevas formas de resolver problemas en distintas ramas: matemáticas, física, química pero también en las ciencias sociales y por su puesto cualquier problema de la vida real. Porque cada vez que nos enfrentamos a un problema, manipulamos la información por medio de reglas de inferencia que aunque no estén escritas debemos respetar. Cada vez que realizamos una actividad empleamos la lógica para realizarla, quizá algunos realicen dicha actividad por caminos más corto, otros realizan recorridos más largos, pero al fin de cuentas lo que importa es llegar al resultado. Si se le da la confianza al alumno para que cree e innove, su estructura cognitiva seguramente va a crecer.

¿Qué es y qué no es permisible como argumento en un debate?
Un argumento es una serie de afirmaciones conectadas entre sí con el objetivo de establecer una determinada proposición. De los muchos tipos de argumentos que existen, trataré aquí los argumentos lógicos deductivos realizados en lógica booleana. La lógica booleana (de Boole) es aquélla con la cual estamos más familiarizados, en la cual existen dos posibilidades al considerar la veracidad de una proposición: verdadero o falso. También se la conoce, por esto, como lógica binaria. Un argumento lógico se construye con proposiciones, o sea, frases que afirman una determinada cosa. Un argumento deductivo contiene una o más proposiciones llamadas premisas que son los pre-supuestos del argumento, o sea, lo que se asume como verdadero para poder deducir el resto. La proposición que se deduce de las premisas se denomina conclusión.

Inferencia Logica Licenciatura

INFERENCIA DEDUCTIVA CON UNA CONDICIONAL
Notamos que tanto el primero, como el último son argumentos válidos; mientras que en los otros dos no hay concluisón.
El primero se llama MPP: Modus Ponendo Ponens y el último MTT: Modus Tollen Tollens, están en latín y en español MPP podría ser Ley de Afirmar Afirmando o de Poner Poniendo y MTT quedaría Ley de Negar Negando o Quitar Quitando. Sin embargo es costumbre nombrarlos en latín.
Todo esto se puede ilustrar con una pequeña máquina de inferencia. Fig 17 A.
En general podemos decir que estas dos reglas de inferencia son las escenciales, y cualquier demostración de podría realizar con el uso de MPP y de MTT, pero es muy conveniente tener algunas otras reglas de inferencia, sobretodo porque en muchos resulta complicado cambiarlo a la forma MPP o MTT, por lo que tener una lista de raglas de inferencia resulta ser muy útil para realizar demostraciones.
A → C A → C A ¬A --------- --------- C (MPP) No hay A → C A → C C ¬C --------- --------- No hay ¬A (MTT)
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 una 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 vaores verdaderos.
Para una mayor comprensión mediante algunos otros ejercicios referirse a la sección del curso de licenciatura que se encuentra en el siguiente enlace: Ejercicios MCI 2.
Integrantes del equipoVillarreal Perez Miguel A.Garay Manrriques Marco A.Martinez Villegas Daniel29 Mayo 2007
‘’‘
Inferencia Lógica
‘’‘ En la lógica tradicional se llamaba inferencia a la figura lógica que permite obtener una conclusión directamente, a partir de una única premisa. Teniendo en cuenta que el esquema fundamental de esa lógica era el silogismo, la inferencia aparecía como un caso especial. Así del conocimiento de que “Está lloviendo”, se infiere “el suelo está mojado”. Tambien podemos decir que, inferir es interpretar el contenido de un texto con solo leer el titulo o palabra clave del mismo. Para entender mejor el tema, primeramente considerar que inferencia es una forma de hacer deducciones; esto es, obtener alguna conclusión en base a hechos conocidos. La forma de inferencia mas antigua es Modus Ponens(MP) y se puede expresar:
Regla de inferencia: Modus Ponens (MP)
p→q p ----- qPrimero se nota que para cualquier tipo de inferencia se debe tener algo conocido, en este caso, lo que esta antes
de la raya, las proposiciones se llaman premisas. Y lo que esta debajo de la raya se llama conclusion. Esta inferencia es valida por que siempre que p→q y p son verdaderas tambien lo es q. En general para saber si una inferencia es valida se analiza la condicional de la conjuncion de las premisas y la conclusion. Esto es:A1.. Inferencia o Argumento.An------C
La inferencia es valida si (A1,^….An)→C es tautologia. Como sabemos, por la seccion anterior que ((p→q)^p)→q es una tautologia:
p→qp-----qes una inferencia valida. Las inferencias mas importantes que se usan para comprobar otras inferencias se llaman reglas de inferencia
DemostraciónPara comprobar que una inferencia es válida se debe demostrar. Una demostracion es un conjunto de pasos donde el ultimo paso de la conclusion, cualquiera de los siguientes pasos es valido:
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 conclusion 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 valida.
Ejemplo 1: Comprobar que r se infiere de:
r → ¬t, q → t, ¬q → ¬s, r
Una forma de representar esto es:
r → ¬t, q → t, ¬q → ¬s, r = ¬s
(Imagen Ejemplo 1)
Demostración:
1. r → ¬t Premisa2. q → t Premisa3. ¬q → ¬s Premisa4. r Premisa5. ¬t MPP (1.4)6. ¬q MTT (2,5)7. ¬s MPP (3,6)Por lo tanto, Argumento Vàlido.
Los primeros cuatro pasos de la demostracion son las premisas y los pasos 5, 6 y 7 son la aplicacion de la regla MP con las premisas que se encuentran en el parentesis.
Una demostracion como la anterior se llama prueba directa. Para poder hacer una comprobacion como la anterior es conveniente tener algunas identidades y reglas de inferencia validas.
!! Reglas de Inferencia:
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
Modus ponendo ponens (Latín: modo que afirmando afirma) es una regla de inferencia simple:
MPP Si el que esta solo es igual al primero (Antecesor) se concluye l segundo (consecuente)
Si P entonces Q.
P.
Entonces, Q.
Expresado en la notación de operadores lógicos:
p → q, p = q
donde = representa la aserción lógica.
También se puede expresar de la siguiente forma:
[(p → q) ^ p ] = q
Modus tollendo tollens (del latín, modo que negando niega), también llamado razonamiento indirecto. En lógica, es el nombre formal para la prueba indirecta o inferencia contrapositiva. Usualmente se lo abrevia como “MTT”.
MTT Si el que esta solo es el opuesto del segundo, se concluye el opuesto del primero.
La tautología Modus Tollens toma las siguientes formas de ley lógica:
Si P, entonces Q.
Q es falso.
Entonces P es falso.
En una notación diferente, utilizando operadores lógicos:
[(p → q) ^ ¬q ] → ¬p
O también:
p → q
¬= q,
∴¬= p
donde \vdash representa la aserción logica.
Un posible ejemplo es:
Si llueve voy al cine
No fui al cine
Por lo tanto, no llovió
Mquina de Razonamiento Basico
(IMAGEN MRB)
Silogismo Disyuntivo Llamado también Modus Tollendo Ponens, que significa literalmente “modo que quitando (negando), pone (afirma)”. El silogismo disyuntivo es una implicación tautológica que afirma que si disponemos de una disyunción y además la negación de uno de sus miembros, entonces podemos inferir como conclusión el otro miembro de la disyunción de marras.
(IMAGEN SD)
El silogismo disyuntivo tiene la siguiente forma lógica:
[(pvq)^(¬p)]→q
y también
[(pvq)^(¬q)]→p
Y sus argumentos correspondientes:
AvB
¬A
-----
B

AvB
¬B
-----
A
Aguinaga Barreal Diana Veronica
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.
Una inferencia puede ser: Inductiva, deductiva, transductiva y abductiva.
Inductiva (de lo particular a lo general)
Aquí por ejemplo si durante la primera semana el maestro llega 10 minutos tarde, podemos concluir que todo el semestre va a llegar tarde. Esta conclusión no necesariamente es válida porque puede ser que el maestro algún día llegue temprano. En general una inferencia inductiva es la que se desprende de una o varias observaciones y en general no podemos estar seguros de que será verdadero lo que concluímos.
En este caso podemos mencionar el ejemplo el mentiroso: Un joven le dice a un amigo, tu todos los días dices mentiras, y el contesta, no es cierto, ayer en todo el día no dije una sóla mentira.
Resumiendo, la inferencia inductiva es la ley general que se obtiene de la observación de uno o más casos y no se puede asegurar que la conclusión sea verdadera en general.
Deductiva (de lo general a lo particular)
Cuando se conoce una ley general y se aplica a un caso particular, por ejemplo se sabe que siempre que llueve hay nubes, concluímos que el día de hoy que está lloviendo hay nubes. También se conoce como inferencia deductiva cuando tenemos un caso que analiza todos los posibles resultados y de acuerdo a las premisas sólo hay una posible situación, en este caso decimos que la situación única es la conclusión. Es este caso estamos seguros de que si las premisas son verdaderas entonces la conclusión también lo es.
En este caso se encuentran MPP: Modus Ponendo Ponens y MTT: Modus Tollendo Tollens que de acuerdo a la tabla de verdad de la condicional son dos formas de establecer una inferencia válida. La inferencia deductiva es la única aceptada como válida en matemáticas y computación para hacer comprobaciones y sacar conclusiones. El tema se discute en forma detallada más delante en INFERENCIA DEDUCTIVA CON UNA CONDICIONAL.
Transductiva (de particular a particular o de general a general) con el mismo caso del maestro que llega tarde drante los primeros días y concluímos que el lunes siguiente también llegará tarde. O del amigo que varias veces nos ha mentido y concluímos que lo que nos dice es ese momento es mentira.
El anterior sería de particular a particular, un caso de general a general es por ejemplo de un compañero maestro que la primera vez que impartió matemáticas discretas observó que todos los alumnos estudiaban, concluyó que para el siguiente semestre todos los alumnos iban a estudiar.
Este es un caso donde como en el caso inductivo, no podemos estar seguros de que la conclusión es verdadera.
Abductiva es semejante a la deductuva, también utiliza la estrategia de analizar todas las posibilidades, pero en este caso hay varios casos que se pueden presentar, como por ejemplo si se sabe que siempre que llueve hay nubes y se sabe que hay nubes se puede concluir que llueve, pero no se tiene la certeza, al igual que el caso inductivo y transductivo no es una forma válida de obtener conclusiones en matemáticas o en lógica y es necesario conocer más información para poder verificar la validez.
Ejemplo: Dadas las condiciones escritas antes de la raya, qué podemos concluir?
Si llueve hay nubes. Hay nubes.- - - - - - - - - - - - - Si haces la tarea te llevo al cine. Lo vimos en el cine.- - - - - - - - - - - - - - - - - - - - -
Si se hace el experimento en un salón de clases o con un grupo de personas, en el primer caso todos contestan que no se sabe pues puede o no llover. Sin embargo en el segundo caso casi todos coinciden en que sí hay conclusión y que se está seguro que hizo la tarea.
Analicemos los casos simbólicamente, en el primero:
p: llueve q: hay nubes con símbolos queda:
p → q q - - - - - -
En el segundo caso
p: hacer la tarea q: llevarlo al cine - - - - - - - - - -
con símbolos:
p → q q - - - - - -
Observamos que en ambos casos es la misma estructura del argumento, por lo que en los dos casos se puede sacar conclusión válida o en ninguno. Pero no es posible que en uno sí y en el otro no.
La respuesta correcta es que en ningún caso se puede obtener conclusión válida. A continuación se presentan los cuatro casos posibles de argumento con una condicional simple, de los cuales dos tienen conclusión válida y dos no.

logica y algoritmia

29 de abril de 2008

LOGICA Y ALGORITMIA...

No hay comentarios:

Métodos de demostración.

Archivo del blog

Datos personales