Upload
heriberto-suarez-fajardo
View
10
Download
0
Embed Size (px)
Citation preview
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.