11 Formulas proposicionales

Las expresiones empleadas para representar las proposiciones, tanto simples

como compuestas, se denominan formulas. Este apartado es una aproxi-

macion al concepto de formula proposicional, primero de manera intuitiva y

luego mediante una definicion matematica.

Como un ejemplo informal, se considera el siguiente razonamiento matema-

tico sencillo.

El punto x esta en la frontera del abierto A. Si x pertenece a A

entonces esta en el interior de A. Si el punto x esta en la frontera

del abierto A, entonces no esta en el exterior de A y no esta en

el interior de A. Si x no pertenece a A, entonces es adherente al

abierto A o esta en el exterior de A. Por lo tanto, el punto x es

adherente al abierto A.

En un primer intento de simbolizacion, las frases mas sencillas se representan

con letras como sigue.

p = el punto x esta en la frontera del abierto A

q = el punto x pertenece al abierto A

r = el punto x esta en el interior del abierto A

s = el punto x esta en el exterior del abierto A

t = el punto x es adherente al abierto A

Al sustituir estas igualdades, el razonamiento toma el siguiente aspecto. Aqu

se hace necesario emplear parentesis adecuados para mantener el sentido que

2el lenguaje coloquial le da a las expresiones compuestas.

p

si q entonces r

si p entonces ((no s) y (no r))

si (no q) entonces (t o s)

Por lo tanto, t

Para el segundo paso de la simbolizacion se emplean los siguientes signos.

no . . .

. . . y . . .

. . . o . . .

si . . . entonces . . .

. . . si y solo si . . .

Ahora el razonamiento queda simbolizado de manera completa.

p

q r

p ((s) (r))

(q) (t s)

t

Los signos empleados en la simbolizacion dan lugar a la siguiente convencion.

Definicion 1.1. Un alfabeto proposicional es la union (disyunta) de los tres

conjuntos siguientes.

1. Un conjunto no vaco L de letras proposicionales

2. El conjunto {,,,,} de los conectivos

33. El conjunto {(, )} de los parentesis

El conjunto L se puede escoger con libertad, segun el problema que se estudia.

Sus elementos, es decir, las letras se denotan a, b, c, . . . , o p, q, r, . . . o bien

p1, p2, p3, . . . El alfabeto proposicional se denota A(L).

Las formulas son ciertas sucesiones finitas de integrantes del alfabeto. El

conjunto de las sucesiones finitas tiene bastante interes matematico.

Construccion 1.2. Dado un conjunto no vaco X, se construye el monoide

X de las palabras en el alfabeto X como sigue. Los elementos de X son

cadenas o sucesiones finitas de elementos de X.

X ={x1x2x3 xk : k N, xi X

}

La sucesion sin elementos o vaca se denota . Dados x = x1x2x3 xk, y =

y1y2y3 yn X se define su yuxtaposicion xy como xy = x1 xky1 yn.

Evidentemente esta es una operacion asociativa, cancelativa a ambos lados

y es su elemento neutro (vease el ejercicio 1.1). El unico caso en el que es

conmutativa es cuando el conjunto X es unitario (ejercicios 1.3 y 1.4). En

resumen: X es un monoide cancelativo y, en general, no conmutativo.

Ahora se definen las formulas de manera constructiva, no descriptiva.

Definicion 1.3. En el conjunto A(L) de las cadenas del alfabeto A(L) se

especifica el subconjunto F(L) de las formulas proposicionales en L mediante

las clausulas siguientes.

1. Las letras proposicionales son formulas, L F(L)

2. Si es una formula entonces () tambien es una formula, llamada la

negacion de

3. Si , son formulas entonces las siguientes tambien son formulas:

4 () (), llamada la conjuncion de y

() (), llamada la disyuncion de y

() (), llamada la implicacion con antecedente y conse-

cuente

() (), llamada la equivalencia de y

4. Eso es todo: Toda formula se obtiene por la aplicacion (iterada) de las

clausulas anteriores

Ejemplo 1.4. Las siguientes son algunas formulas de F(p).

p (p) ((p)) (p) ((p) ((p) (p))) (p)

Las siguientes son algunas formulas de F(p, q).

p (q) (p) ((p) (q)) (((p) (q)) (p)) ((q))

Una pregunta que podra surgir de manera natural es: Cuantas formulas

hay?

Afirmacion 1.5. Para cualquier conjunto no vaco L de letras, el conjunto

de formulas F(L) es infinito. Si ademas L es finito o enumerable, F(L) es

enumerable.

Demostracion. Dado p L 6= sea 1 = (p) y, para cada n 1, sea

n+1 = (n). Ahora (n)n es una sucesion infinita de formulas distintas

luego F(L) es infinito.

El caracter enumerable de F(L) se debe a la enumerabilidad del monoide de

las palabras (vease el ejercicio 1.5).

Ejercicios.

1.1. Demuestre las propiedades siguientes de la operacion de yuxtaposicion

en el monoide X de las palabras de un conjunto cualquiera X.

5a) Asociativa: x(yz) = (xy)z

b) Cancelativa: xy = xz implica y = z y, ademas, xz = yz implica x = y.

c) Elemento neutro: x = x y x = x.

1.2. Establezca una funcion inyectiva X X que permita ver el conjunto

original X como un subconjunto del monoide de palabras X.

1.3. Demuestre que si existen elementos distintos x1, x2 en el conjunto X

entonces el monoide X no es conmutativo.

1.4. Muestre que si el conjunto X es unitario entonces el monoide X es

isomorfo al conjunto de los numeros naturales (desde el cero) con la adicion.

1.5. Sea X un conjunto no vaco.

a)Muestre que el conjunto de las palabras de X con longitud k es isomorfo

a la potencia Xk.

b) Concluya que X = k0Xk.

c) Demuestre que si X es un conjunto finito o enumerable entonces el

conjunto X de las palabras es infinito enumerable.