1) INTRODUCCION A LA LOGICA MATEMATICA
2) TEORIA DE LA DEMOSTRACION
3) INDUCCION MATEMATICO
4) SISTEMAS NUMERICOS
domingo, 4 de octubre de 2009
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.
Suscribirse a:
Entradas (Atom)
