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.
Induccion matematicas
G. Peano (1858–1932) propuso cinco propiedades fundamentales que caracterizan a los números naturales, Axiomas de Peano. Una de ellas conocida como el Principo de Inducción Matemática es actualmente una herramienta de uso práctico y teórico principalmente para matemáticos y personas que trabajan en Ciencias Computacionales.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
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ónk e S se llama Hipótesis de InducciónY 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.
1. Demostrar por Inducción Matematica que:
F(n): entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H → M] Sumamos (k+1) de los dos lados de la igualdad Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
En el ejemplo anterior para llegar a n=k+1 partiendo de n=k al lado izquierdo sólo le faltaba k+1 por lo que la estrategia fue sumar k+1 en ambos lados de la igualdad.
Esta estrategia la podemos utilizar para el siguiente algoritmo
Da click aqui para descargar la explicación en vídeo
ALGORITMO . Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
→ [Hipótesis de Inducción] Escribir la fórmula para n=k.
→ [Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración,sino más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la preparación de los estudiantes a los que va dirigido.
2. Demostrar por Inducción Matematica que: ∑ Es la letra griega sigma mayuscula y en matematicas significa suma
*[B] Si n=1; tenemos: entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H→M] Sumando (6(k+1)−2) a ambos lados Por lo tanto, podemos concluir que la formula (2) es valida para cualquiera que sea el valor de n
El Principio de Inducción Matemática es mucho más que el algoritmo aquí presentado, ya que hay muchos casos en los que no aparecen igualdades algebraicas y como se mencionó en el principio inicialmente (B), (I) son tan generales que puede aplicarse a cualquier cosa que cumpla las condiciones. Sin embargo el poder aprender y resolver problemas con este algoritmo le da al alumno la madurez necesaria para entenderlo en general y le sirve también para formalizar y entender posteriormente la recursividad, concepto tan importente en Ciencias Computacionales.
Para practicar hacer los ejercicios del 85 al 94 de Ejercicios MC 1
Definiciones por inducción: Utilizando el método de Inducción Matemáticas podemos definir conceptos en forma recursiva, la ventaja es que se formalizan los conceptos además de que son más fáciles de manejar.
Factorial:[B] 0! = 1[R] (n+1)! = n! (n+1)
Notación Sumatoria:
Suma:[B] m + 0 = m[R] m + n’ = (m+n)’
La definición anterior se basa en los números naturales, n’ significa el sucesor de n que equivale a n+1, por la misma definición anterior.
Producto:[B] m * 0 = 0[R] m * (n+1) = (m * n) + m.
El principio lo enunciaremos para los enteros positivos N+, pero bien se puede ampliar a los números naturales o a cualquier subconjunto de los enteros mayores o iguales a un entero fijo.
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ónk e S se llama Hipótesis de InducciónY 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.
1. Demostrar por Inducción Matematica que:
F(n): entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H → M] Sumamos (k+1) de los dos lados de la igualdad Por lo tanto, podemos concluir que la formula (1) es valida para todos los enteros positivos
Para realizar el Paso de Inducción se debe de partir del caso n=k y llegar mediante pasos válidos al caso n=k+1.
En el ejemplo anterior para llegar a n=k+1 partiendo de n=k al lado izquierdo sólo le faltaba k+1 por lo que la estrategia fue sumar k+1 en ambos lados de la igualdad.
Esta estrategia la podemos utilizar para el siguiente algoritmo
Da click aqui para descargar la explicación en vídeo
ALGORITMO . Para demostrar una igualdad F(n) algebraica válida que involucra enteros donde la parte izquierda es una suma cuyo término n-ésimo es una fórmula de n.
[Fórmula] Escribir la fórmula en función de n, sea F(n).
[Caso Base] Probar la fórmula para n=1, F(1).
[Meta] Escribir la fórmula para n=k+1, F(k+1).
[Paso de Inducción]
→ [Hipótesis de Inducción] Escribir la fórmula para n=k.
→ [Llegar a la Meta] Sumar a ambos lados el último término de la parte izquierda de la [Meta], o sea la igualdad para n=k+1.
Aplicar propiedades algebraicas al lado derecho hasta llegar al lado derecho de la [Meta], o sea la igualdad para n=k+1.
Nota: Cabe aclarar que la única dificultad se puede presentar en el manejo algebraico de las expresiones en la segunda parte del Paso de Inducción y que depende muchas veces de la complejidad de la expresión y de la habilidad algebraica de quien realiza la prueba.
Nota: La meta la marcamos con rojo para indicar que no es un paso válido en la demostración,sino más bien una guía de a dónde queremos llegar y para tener una mejor idea de lo que estamos demostrando.
En los ejemplos que se vean se debe considerar expresiones que se puedan resolver con la preparación de los estudiantes a los que va dirigido.
2. Demostrar por Inducción Matematica que: ∑ Es la letra griega sigma mayuscula y en matematicas significa suma
*[B] Si n=1; tenemos: entonces 1 está en S o sea que se cumple el caso base.
*[I] Inducción
**[H] Suponemos que cumple para n=k;
**[H→M] Sumando (6(k+1)−2) a ambos lados Por lo tanto, podemos concluir que la formula (2) es valida para cualquiera que sea el valor de n
El Principio de Inducción Matemática es mucho más que el algoritmo aquí presentado, ya que hay muchos casos en los que no aparecen igualdades algebraicas y como se mencionó en el principio inicialmente (B), (I) son tan generales que puede aplicarse a cualquier cosa que cumpla las condiciones. Sin embargo el poder aprender y resolver problemas con este algoritmo le da al alumno la madurez necesaria para entenderlo en general y le sirve también para formalizar y entender posteriormente la recursividad, concepto tan importente en Ciencias Computacionales.
Para practicar hacer los ejercicios del 85 al 94 de Ejercicios MC 1
Definiciones por inducción: Utilizando el método de Inducción Matemáticas podemos definir conceptos en forma recursiva, la ventaja es que se formalizan los conceptos además de que son más fáciles de manejar.
Factorial:[B] 0! = 1[R] (n+1)! = n! (n+1)
Notación Sumatoria:
Suma:[B] m + 0 = m[R] m + n’ = (m+n)’
La definición anterior se basa en los números naturales, n’ significa el sucesor de n que equivale a n+1, por la misma definición anterior.
Producto:[B] m * 0 = 0[R] m * (n+1) = (m * n) + m.
Algebra declarativa
los operadores lógicos con proposiciones, si esos operadores los combinamos podemos formar fórmulas lógicas.
La primera pregunta que nos hacemos es: Cómo sabemos si una fórmula está bien formada.
Pendiente: Dar la definición formal de fórmula bien formada, en forma recursiva.
¿Cómo simplificar en lógica?
Hay que utilizar equivalencias lógicas.
Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.
Para esto utilizamos las siguientes equivalencias lógicas:
( A ^ B ) ^ C <=> A^(B ^C)
A ^ ¬ A <=> F
A ^ F <=> F
( p ^ q ) ^ ¬q <=> F
Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.
Ejemplo
Demostrar que una vez que p ^ q esta establecida, se puede concluir q.
Esta demostración se puede hacer de dos formas:
A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.
Demostración
¬p V ¬q V q <=> V
B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica
La primera pregunta que nos hacemos es: Cómo sabemos si una fórmula está bien formada.
Pendiente: Dar la definición formal de fórmula bien formada, en forma recursiva.
¿Cómo simplificar en lógica?
Hay que utilizar equivalencias lógicas.
Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.
Para esto utilizamos las siguientes equivalencias lógicas:
( A ^ B ) ^ C <=> A^(B ^C)
A ^ ¬ A <=> F
A ^ F <=> F
( p ^ q ) ^ ¬q <=> F
Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.
Ejemplo
Demostrar que una vez que p ^ q esta establecida, se puede concluir q.
Esta demostración se puede hacer de dos formas:
A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.
Demostración
¬p V ¬q V q <=> V
B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica
Cuantificadores Y Restricciones
Dos casos centrales en el cálculo de predicados se presentan cuando se analiza si el predicado se cumple para la población completa y cuando se analiza para ver si cumple para un caso en particular al menos. Estos dos casos se llaman Universal y Particular o Existencial vienen a ser la interpretación o la semántica de los símbolos de cuantificadores que se vieron en la sección 1.4 Calculo de Predicados Definicion y se definen de la siguiente forma:
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la espresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio.
Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una expresión de cálculo de predicados F se representa por la espresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio.
Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.
Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una varible conectados mediante una condicional y tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
(∀ x) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todos las personas que viven en Tijuana.
Aquí podemos ver claramente que el dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede represntar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.
Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde.
A una expresión como las anteriores se le llama Universal Afirmativa y se representa con la letra A.
Los griegos utilizaban enunciados como los anteriores en los Silogismos, que son formas de razonamiento que contienen dos premisas tipo A, E , I, O y una conclusión también de uno de los cuatro tipos, las premisas están conectadas con un predicado común y la conclusión debe estar formado por las no comunes que se le llaman técnicamente premisa menor y premisa mayor.
Una expresión tipo E es llamada Universal Negativa y se representa por
(∀ x) (P(x) → ¬Q(x)) y en español se lee ningún P cumple Q o sea que los que cumplen el predicado P(x) no cumples el predicado Q(x).
Ningún alumno llegó tarde se puede representar por (∀ x) (A(x) → ¬T(x)) donde A es alumno y T es llegó tarde.
Las dos expresiones restantes corresponden a casos particulares y para formarlas utilizamos el cuantificador existencial, y en lugar del operador condicional se usa la conjunción, así
I es (∃ x) (P(x) ∧ Q(x)) llamado Particular Afirmativa y
O es (∃ x) (P(x) ∧ ¬ Q(x)) que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el segundo aseguramos que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación, pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
Primeramente estableceremos dos reglas generales con un predicado simple:
Propiedad:
¬(∀ x) P(x) es equivalente a (∃ x) (¬ P(x))
¬(∃ x) P(x) es equivalente a (∀ x) (¬P(x))
Ahora sí, podemos combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la Universal Negativa.
O sea que la negación de la forma A es la forma O y la negación de la forma I es la forma E.
¬ (∀ x) (P(x) → Q(x)) es equivalente a (∃ x) (P(x) ^ ¬ Q(x))
¬ (∃ x) (P(x) ^ Q(x)) es equivalente a (∀ x) (P(x) → ¬Q(x))
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la negación de Alguno es Ninguno.
Esto es muy útil en matemáticas y en computación, por ejemplo si queremos demostrar que no es cierto que todas las funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la espresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula son verdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio.
Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT.
Cuantificador Existencial. El cuantificador existencial al menos uno o existe uno asociado a una expresión de cálculo de predicados F se representa por la espresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio.
Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.
Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una varible conectados mediante una condicional y tomando el cuantificador universal.
Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante
(∀ x) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todos las personas que viven en Tijuana.
Aquí podemos ver claramente que el dominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad.
Todos los hombres son mortales se puede represntar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.
Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde.
A una expresión como las anteriores se le llama Universal Afirmativa y se representa con la letra A.
Los griegos utilizaban enunciados como los anteriores en los Silogismos, que son formas de razonamiento que contienen dos premisas tipo A, E , I, O y una conclusión también de uno de los cuatro tipos, las premisas están conectadas con un predicado común y la conclusión debe estar formado por las no comunes que se le llaman técnicamente premisa menor y premisa mayor.
Una expresión tipo E es llamada Universal Negativa y se representa por
(∀ x) (P(x) → ¬Q(x)) y en español se lee ningún P cumple Q o sea que los que cumplen el predicado P(x) no cumples el predicado Q(x).
Ningún alumno llegó tarde se puede representar por (∀ x) (A(x) → ¬T(x)) donde A es alumno y T es llegó tarde.
Las dos expresiones restantes corresponden a casos particulares y para formarlas utilizamos el cuantificador existencial, y en lugar del operador condicional se usa la conjunción, así
I es (∃ x) (P(x) ∧ Q(x)) llamado Particular Afirmativa y
O es (∃ x) (P(x) ∧ ¬ Q(x)) que es la Particular Negativa.
En el primer caso se indica un elemento que cumple las dos condiciones dadas por los predicados y en el segundo aseguramos que hay un elemento que cumple la primera condición pero no la segunda.
Una manera muy simple de combinar estas expresiones mediante una propiedad es utilizando la negación, pues dos de ellas son las negaciones de las otras dos, de ahí sus nombres de afirmativas y negativas.
Primeramente estableceremos dos reglas generales con un predicado simple:
Propiedad:
¬(∀ x) P(x) es equivalente a (∃ x) (¬ P(x))
¬(∃ x) P(x) es equivalente a (∀ x) (¬P(x))
Ahora sí, podemos combinar estos dos resultados con las Universales y Particulares Afirmativas y Negativas y tenemos lo siguiente.
Teorema:
La negación de la Universal Afirmativa es la Particular Negativa y La negación de la Particular Afirmativa es la Universal Negativa.
O sea que la negación de la forma A es la forma O y la negación de la forma I es la forma E.
¬ (∀ x) (P(x) → Q(x)) es equivalente a (∃ x) (P(x) ^ ¬ Q(x))
¬ (∃ x) (P(x) ^ Q(x)) es equivalente a (∀ x) (P(x) → ¬Q(x))
De una manera más simple lo que dice la primera fórmula es que la negación de Todos es Alguno No y que la negación de Alguno es Ninguno.
Esto es muy útil en matemáticas y en computación, por ejemplo si queremos demostrar que no es cierto que todas las funciones integrables son continuas, basta encontrar una que sea integrable y que no sea continua.
Variables Y Particularizaciones
En cálculo de predicados tenemos expresiones con variables, las variables pertenecen a un conjunto o dominio previamente determinado. Por lo que es muy importante definir el dominio cuado interpretamos una fórmula mediante un predicado específico.
Ejemplo:
x es alumno del ITT, que se podría representar por T(x), aquí el predicado T es “alumno del ITT” y el dominio podría ser el conjunto de los estudiantes de Tijuana. Otro caso es: x es azul, se representa A(x), el predicado “es de color azul” y podemos poner el dominio como el conjunto de los libros.
Una variable, en estos casos x, represente un valor cualquiera del dominio dado, y cuando le asignamos un valor específico a la variable se llama instancia o lo que programa menciona como particularición.
Así por ejemplo: Juan Pérez es alumno del ITT es una instancia del primer ejemplo y Mi libro de matemáticas es azul es una instancia del segundo ejemplo.
En el primer caso prodríamos considerar como dominio el conjunto de todos los alumnos de Tijuana, también podría ser sólo los alumnos de nivel profesional o también podríamos tener a todos los alumnos de México. Por eso es muy importante que se especifique con toda claridad el dominio.
Ejemplo:
x es alumno del ITT, que se podría representar por T(x), aquí el predicado T es “alumno del ITT” y el dominio podría ser el conjunto de los estudiantes de Tijuana. Otro caso es: x es azul, se representa A(x), el predicado “es de color azul” y podemos poner el dominio como el conjunto de los libros.
Una variable, en estos casos x, represente un valor cualquiera del dominio dado, y cuando le asignamos un valor específico a la variable se llama instancia o lo que programa menciona como particularición.
Así por ejemplo: Juan Pérez es alumno del ITT es una instancia del primer ejemplo y Mi libro de matemáticas es azul es una instancia del segundo ejemplo.
En el primer caso prodríamos considerar como dominio el conjunto de todos los alumnos de Tijuana, también podría ser sólo los alumnos de nivel profesional o también podríamos tener a todos los alumnos de México. Por eso es muy importante que se especifique con toda claridad el dominio.
Definición
Una fórmula en lógica de predicados es una expresión que se puede obtener mediante alguna de las formas siguientes: i) p(x1, x2, … ,xn) donde p es un símbolo que representa un predicado y x1, x2, … ,xn son símbolos de variable.ii) (¬ F) donde F es una fórmula de lógica de predicados.iii) (F G) donde F y G son fórmulas de lógica de predicados y es cualquiera de los operadores ^, v, →, ↔iv) (∀ x) F, donde F es un fórmula en lógica de predicados.v) (∃ x) F, donde F es un fórmula en lógica de predicados.
Nota: El paréntesis encerrando las expresiones en (ii) y (iii) es con el fin de evitar ambigüedades en las interpretaciones igual que en lógica de proposiciones,
Nota: El paréntesis encerrando las expresiones en (ii) y (iii) es con el fin de evitar ambigüedades en las interpretaciones igual que en lógica de proposiciones,
Suscribirse a:
Entradas (Atom)
