Formalización
Formalizar quiere decir escribir una expresión de una manera estándar que
todos entiendan.
Al trabajar con algoritmos lógicos, podemos estar pensando todo el rato en
frases como “Si llueve y no tengo paraguas, entonces me mojo”. Se puede, pero
es muy largo. Es mejor representar cada acción con una letra, y escribir la frase
usando esas letras y palabras sencillas como y, o, no, o entonces.
Ejemplo. Tenemos este vocabulario:
P: llover
Q: tener paraguas
R: mojarse
La frase “Si llueve y no tengo paraguas, entonces me mojo” queda mejor
como “si P y no Q, entonces R”.
En la deducción natural se usaría solo la versión de las letras, con estas
condiciones:
Las letras (que se llaman letras proposicionales) van en may´usculas.
Se suelen usar las letras P, Q, R, S, ... aunque se puede usar cualquiera.
Se usan unos símbolos especiales para los operadores y, o, no e implicación.
Símbolos usados
Para expresar las relaciones entre una acción y otra, hay varios dibujitos
internacionales. Los operadores b´asicos que tienes que conocer son ∨, ∧, Å , ⇒.
Los otros son más complicados, pero los he mostrado todos para cuando haya
que consultarlos.
Símbolo Se lee... Descripción
∨ o A ∨ B se cumple cuando uno de los dos, o los dos, es cierto.
∧ y Para que A∧B se cumpla, tanto A como B tienen que ser ciertos.
Å no ¬A se cumple sólo cuando A es falso.
⇒ implica Indica una consecuencia. La expresión A ⇒ B dice que cuando
A se cumple, B también. Adem´as, A ⇒ B es cierto excepto para
el caso A cierto y B falso. Para entenderlo, piensa en un A que
implique B y pregúntate: ¿es posible que A sea cierto y B no?
Tampoco te preocupes mucho por esto, no es importante ahora.
⇐⇒ si y sólo si A ⇐⇒ B equivale a (A ⇒ B) ∧ (B ⇒ A). Quiere decir que de
A se puede deducir B y viceversa, o sea, que son equivalentes.
0 falso El 0 binario representa falso. Más técnicamente, representa a {}.
1 cierto El 1 binario representa cierto. Más técnicamente,representa a {<>}.
Deducción natural
¿Para que sirve?
La deducción natural sirve para intentar demostrar que un razonamiento es
correcto (“para comprobar la validez de un secuente”, dice la teoría). Ejemplo:
Yo te digo: “En verano hace calor, y ahora estamos en verano, por eso hace
calor”. Tú te pones a hacer cálculos, y respondes “Vale, puedo demostrar que el
razonamiento que has hecho es correcto”. Para eso sirve la deducción natural.
No siempre es tan fácil: “si suspendes una asignatura, la tienes que repetir. Si
no estudias, la suspendes. Supongamos que no la repites. Entonces, o la estudias,
o la suspendes, o las dos cosas a la vez”. Este razonamiento es válido y se puede
demostrar con la deducción natural.
Notación
P, P ⇒ Q ⊢ P ∧ Q
La soluci´on a P, P ⇒ Q ⊢ P ∧ Q es:
1 P
2 P ⇒ Q
3 Q E⇒ 2,1
4 P ∧ Q I∧ 1,3
Aquí no hay que pensar mucho, simplemente hay que usar bien las reglas y
justificaciones.
Lo primero, entender lo que nos han dicho: nos dicen que ahora pasan dos
cosas, la primera es que P y la segunda es que P ⇒ Q (son las dos fórmulas que
hay a la izquierda del ⊢). Estas dos cosas nos las tenemos que apuntar, una en
cada línea, porque en esta demostración serían siempre ciertas (nos guste o no).
El objetivo de esta demostración es saber que P ∧Q también es cierto, porque
nos han contado que cuando P y P ⇒ Q son ciertos, entonces P ∧Q también, y
queremos comprobar si es verdad. Al final se ha conseguido, porque en la ´ultima
línea sale el P ∧ Q escrito.
¿Cómo seguimos ahora? Hay que fijarse en a dónde queremos llegar. Si P ∧Q
tiene que ser cierto, entonces tanto P como Q tendrían que ser ciertos; vamos a
preocuparnos por demostrar que lo son.
P es cierto, porque nos lo han dicho, y lo tenemos apuntado en la línea 1.