Clase 25/09/2013 Tomado y editado de los apuntes de Pedro S´anchez Terraf

A pesar de haber ejercitado la realizaci´on de demostraciones en varias materias, es frecuente que el alumno consulte sobre la validez de una prueba, sobre la correctitud de un razonamiento. En este segmento estudiaremos formalmente el concepto de demostraci´on, proporcionando elementos para que el alumno pueda decidir por s´ı mismo si una argumentaci´on matem´atica es l´ogicamente correcta. Haremos esto para un fragmento relativamente simple de la l´ogica matem´atica llamado L´ ogica Proposicional.

Proposiciones Las proposiciones representan afirmaciones. Estas afirmaciones se escriben con una notaci´on muy particular: usamos conectivas l´ogicas como ∧, ∨, →, . . .. Tambi´en se utilizan par´entesis como ‘(’ y ‘)’ para resolver ambig¨ uedades, y variables proposicionales. Es decir que las proposiciones ser´an ciertas secuencias, listas o cadenas (usamos estas tres palabras como sin´onimos) de s´ımbolos. Utilizaremos los siguientes s´ımbolos. Al conjunto de s´ımbolos permitidos se le llama alfabeto.

Alfabeto de la L´ ogica Proposicional La l´ogica proposicional se escribir´a con el siguiente alfabeto: 1. S´ımbolos proposicionales (en cantidad numerable): p0 , p1 , . . . , pn , . . . ; 2. Conectivos. B´asicos: ⊥, ∧, →. Derivados: ¬, ∨, ↔, >, |, . . . ; 3. S´ımbolos auxiliares: ‘(’ y ‘)’. Llamamos Σ al conjunto de estos s´ımbolos, y Σ∗ al conjunto de todas las cadenas de s´ımbolos de Σ. Ejemplos de tales cadenas: p0 p3 )⊥ ∧ p0 p0 ∧ p 5

(()) ∧ ∨ → (p0 ∧ p5 )

p0 → p1 ) ((p0 ∧ p5 ))

)p0 ∧ p5 ( p3

(()p3 ) (p3 )

Ejemplos de cadenas que no pertenecen a Σ∗ : llueve F →V

x≤y ϕ∧ψ

p→q (ϕ ∧ ψ)

1

p 0 ⇒ p3 2 es par

p0 → p j p0  p1

Lenguaje de la L´ ogica Proposicional No cualquier cadena de Σ∗ denota una proposici´on.1 A los s´ımbolos proposicionales se los llama tambi´en variables proposicionales, y se define V = {p0 , p1 , . . . , pn , . . . }. Si agregamos el s´ımbolo ⊥, tenemos los ´atomos o proposiciones at´omicas, y los designaremos con el nombre At = V ∪ {⊥}. El conectivo ¬ es unario, ⊥ es nulario (corresponde a una constante) y el resto son binarios. Para designar un operador binario arbitrario, utilizaremos el meta-s´ımbolo  .2 Definici´ on 1. El conjunto de las proposiciones, PROP , es el menor conjunto que cumple con las siguientes propiedades: ϕ ∈ At Para todo ϕ ∈ At, ϕ ∈ PROP . (¬ϕ) Para toda ϕ en PROP , (¬ϕ) est´a en PROP . (ϕ  ψ) Para todas ϕ, ψ en PROP , (ϕ  ψ) est´a en PROP . Usaremos letras griegas ϕ, ψ, χ, . . . para nombrar proposiciones arbitrarias. La u ´ltima cl´ausula se vale del meta-s´ımbolo  que representa un operador binario gen´erico y evita ser repetitivos. Si no deber´ıamos escribir una cl´ausula como esa para cada uno de los operadores binarios: (ϕ ∧ ψ) Para todas ϕ, ψ en PROP , (ϕ ∧ ψ) est´a en PROP . (ϕ → ψ) Para todas ϕ, ψ en PROP , (ϕ → ψ) est´a en PROP . etc´etera

Proposiciones por extensi´ on La definici´on dada establece que las siguientes cadenas son proposiciones: 1. Los a´tomos ⊥, p0 , p1 , . . . , pn , . . . son las proposiciones at´omicas. 2. Para cada proposici´on ϕ y ψ ya listada, y para cada conectivo binario  , (¬ϕ) y (ϕ  ψ) son proposiciones un poco m´as complejas. Ejemplos: (¬⊥), (¬p0 ), etc. Otros: (⊥ ∧ ⊥), (⊥ ∧ p0 ), etc. 3. Para cada proposici´on ϕ y ψ ya listada, y para cada conectivo binario  , (¬ϕ) y (ϕ  ψ) son proposiciones un poco m´as complejas. Ejemplos: (¬(¬⊥)), (¬(⊥ ∧ p0 )), etc. Otros: ((¬⊥) ∧ (p0 ∧ p1 )), (⊥ ∧ (p0 ∧ p1 )), etc. 4. etc´etera Esta enumeraci´on de las proposiciones por extensi´ on contin´ ua indefinidamente, presentando en cada l´ınea proposiciones m´as y m´as complejas porque en cada l´ınea se puede concebir nuevas proposiciones de la forma (¬ϕ) y (ϕ  ψ) para cada proposici´on ϕ y ψ listada con anterioridad, y para cada operador binario  . En efecto, todas las proposiciones de la primera l´ınea son cadenas de un solo s´ımbolo, en la segunda hay cadenas de cuatro s´ımbolos y otras de cinco s´ımbolos. En la tercera l´ınea ya hay m´as variantes, pero en particular tenemos proposiciones de la forma (ϕ  ψ) donde ϕ y ψ denotan cadenas de cinco s´ımbolos, por lo tanto (ϕ  ψ) denota otra cadena de trece s´ımbolos. En la cuarta l´ınea habr´a nuevas cadenas de 29 s´ımbolos, en la quinta de 61, en la sexta de 125, etc. 1 2

¿Cu´ ales de los ejemplos de cadenas de Σ∗ enumeradas arriba lo hace? Le llamamos meta para indicar que no pertenece al alfabeto Σ.

2

Inducci´ on y recursi´ on La definici´on del conjunto PROP dice que es el menor conjunto que satisface las tres cl´ausulas ya explicadas. Ser el menor conjunto significa que PROP no contiene ning´ un otro elemento que no sea producto de esas cl´ausulas. Nos permite deducir, por ejemplo, que p0 p1 no pertenece a PROP porque no es un ´atomo (y por ello no puede ser producto de la primera cl´ausula) ni comienza con un par´entesis que abre (y por ello, no puede ser producto de ninguna de las otras dos cl´ausulas). Tambi´en nos permite deducir que las siguientes cadenas no pertenecen a PROP : p0 ∧ p1 (p0  p1 )

((p0 ∧ p1 )) (¬ϕ)

¬⊥ (¬pi )

(p0 ) ()

p0 ∧ (p0 → p1 ) (⊥)

M´as interesante a´ un, que PROP sea el menor conjunto que satisface las tres cl´ausulas implica que se puede demostrar propiedades sobre las proposiciones por inducci´on de la siguiente manera. Teorema 2 (inducci´on en subf´ormulas). Sea A un predicado sobre PROP . Luego A(ϕ) es verdadero para toda ϕ ∈ PROP si y s´olo si: ϕ ∈ At Si ϕ es at´omica, A(ϕ) vale. (¬ϕ) Si A(ϕ) entonces A((¬ϕ)). (ϕ  ψ) Si A(ϕ) y A(ψ) entonces A((ϕ  ψ)). Demostraci´on. Sea X = {ϕ ∈ PROP : A(ϕ)}. X satisface las tres propiedades de la Definici´on 1, as´ı que PROP ⊆ X (pues PROP es el menor conjunto con tales propiedades). Como X ⊆ PROP , tenemos X = PROP y entonces A(ϕ) vale para toda ϕ ∈ PROP . Por la misma raz´on, tambi´en es posible definir funciones f de PROP en cualquier otro conjunto por recursi´on de la siguiente manera: ϕ ∈ At Si ϕ es at´omica, se define f (ϕ) de manera directa, sin llamadas recursivas. (¬ϕ) Para definir f ((¬ϕ)) est´a permitido llamar recursivamente a f (ϕ). (ϕ  ψ) Para definir f ((ϕ  ψ)) est´a permitido llamar recursivamente a f (ϕ) y a f (ψ). Dicho de otra manera, es posible definir una funci´on f de PROP en otro conjunto siguiendo el esquema: f (pi ) f (⊥) f ((¬ϕ)) f ((ϕ  ψ))

= = = =

... ... . . . f (ϕ) . . . . . . f (ϕ) . . . f (ψ) . . .

caso base, sin llamadas a f caso base, sin llamadas a f llamada recursiva permitida llamadas recursivas permitidas

Daremos algunos ejemplos de definiciones recursivas y luego de prueba por inducci´on.

3

Definiciones recursivas A continuaci´on definimos una funci´on que calcula el n´ umero de s´ımbolos de cada proposici´on, # : PROP −→ N: #(pi ) #(⊥) #((¬ϕ)) #((ϕ  ψ))

= = = =

1 1 #(ϕ) + 3 #(ϕ) + #(ψ) + 3

Por ejemplo, #((¬(p2 → (¬p3 )))) = = = = =

#((p2 → (¬p3 ))) + 3 #(p2 ) + #((¬p3 )) + 3 + 3 1 + #(p3 ) + 3 + 3 + 3 1+1+9 11

El n´ umero de pares de conectivas l´ogicas de una proposici´on (c : PROP −→ N): c(pi ) c(⊥) c((¬ϕ)) c((ϕ  ψ))

= = = =

0 1 c(ϕ) + 1 c(ϕ) + c(ψ) + 1

Por ejemplo c(((¬p1 ) ∧ (p2 → (p1 ∨ p3 )))) = 4. El conjunto de variables o s´ımbolos proposicionales que ocurren en una proposici´on (vars : PROP −→ P(V)): vars(pi ) vars(⊥) vars((¬ϕ)) vars((ϕ  ψ))

{pi } {} vars(ϕ) vars(ϕ) ∪ vars(ψ)

= = = =

Por ejemplo vars(((¬p1 ) ∧ (p2 → (p1 ∨ p3 )))) = {p1 , p2 , p3 }. El conjunto de subf´ormulas o subproposiciones de una proposici´on (sub : PROP −→ P(PROP )): sub(pi ) = {pi } sub(⊥) = {⊥} sub((¬ϕ)) = sub(ϕ) ∪ {(¬ϕ)} sub((ϕ  ψ)) = sub(ϕ) ∪ sub(ψ) ∪ {(ϕ  ψ)} Por ejemplo sub(((¬p1 ) → (p1 ∨ p3 ))) = {p1 , p3 , (¬p1 ), (p1 ∨ p3 ), ((¬p1 ) → (p1 ∨ p3 ))}. La sustituci´on del s´ımbolo proposicional pi por ψ en ϕ, que se denota por ϕ[ψ/pi ]  ψ si i = j pj [ψ/pi ] = pj si i 6= j ⊥[ψ/pi ] = ⊥ (¬ϕ)[ψ/pi ] = (¬ϕ[ψ/pi ]) (ϕ  ξ)[ψ/pi ] = (ϕ[ψ/pi ]  ξ[ψ/pi ]) Por ejemplo, (p1 → (¬p2 ))[(¬p3 )/p1 ] = = = =

(p1 [(¬p3 )/p1 ] → (¬p2 )[(¬p3 )/p1 ]) ((¬p3 ) → (¬p2 [(¬p3 )/p1 ])) ((¬p3 ) → (¬p2 [(¬p3 )/p1 ])) ((¬p3 ) → (¬p2 )) 4

Prueba por inducci´ on Veamos un ejemplo de prueba por inducci´on: Definici´ on 3. Una sucesi´on de proposiciones ϕ1 , . . . , ϕn es una serie de formaci´on de ϕ ∈ PROP si ϕn = ϕ y para todo i ≤ n, ϕi es: at´omica, o bien igual a (¬ϕj ) con j < i, ´o igual a (ϕj  ϕk ) con j, k < i. Por ejemplo p1 , p2 , p3 , (¬p1 ), ((¬p1 ) ∧ p2 ), (p1 ∨ p3 ), ((¬p1 ) → (p1 ∨ p3 ))} es una serie de formaci´on de ((¬p1 ) → (p1 ∨ p3 )), aunque no es la m´as corta posible. En cambio, si se elimina la segunda proposici´on, p2 , de la sucesi´on deja de ser una serie de formaci´on. Si adem´as se suprime la quinta proposici´on, obtenemos una nueva serie de formaci´on de ((¬p1 ) → (p1 ∨ p3 )), esta vez de longitud m´ınima. ¿Es la u ´nica de longitud m´ınima? Teorema 4. Toda ϕ ∈ PROP tiene serie de formaci´on. Demostraci´on. Analizamos cada caso: ϕ ∈ At ϕ es una serie de formaci´on de ϕ. (¬ϕ) Por hip´otesis inductiva, ϕ tiene una serie de formaci´on; sea ϕ1 , . . . , ϕn−1 , ϕ una tal serie. Pero ϕ1 , . . . , ϕn−1 , ϕ, (¬ϕ) es una serie de formaci´on de (¬ϕ). (ϕ  ψ) Por hip´otesis inductiva, ϕ y ψ tienen sus series de formaci´on; llam´emoslas ϕ1 , . . . , ϕn−1 , ϕ y ψ1 , . . . , ψm−1 , ψ. Luego ϕ1 , . . . , ϕn−1 , ϕ, ψ1 , . . . , ψm−1 , ψ, (ϕ  ψ) es serie de formaci´on de (ϕ  ψ). Con esto se concluye la prueba.

5