Al
Al
Al
Notas de Clase
Camilo Rocha
cbna
Esta obra est bajo una licencia de Creative Commons
Reconocimiento-NoComercial-CompartirIgual 4.0 Internacional.
Este trabajo puede ser copiado y distribudo libremente, como copia electrnica o en
papel. No puede ser vendido por un valor mayor a su costo actual de reproduccin,
almacenamiento o transmisin.
ndice general
Captulo 1.
Prembulo
1.1.
Preludio
1.2.
Induccin
1.3.
Sistemas formales
Lenguaje y especificacin
15
2.1.
Proposiciones
16
2.2.
Lenguaje formal
19
2.3.
rboles de sintaxis
24
2.4.
26
Captulo 3.
Semntica
31
3.1.
Funciones Booleanas
31
3.2.
Valuaciones
39
3.3.
Clasificacin de proposiciones
44
3.4.
48
3.5.
53
Captulo 4.
59
4.1.
El sistema formal DS
59
4.2.
66
4.3.
La negacin y la discrepancia
70
4.4.
La disyuncin
75
80
4.6.
83
La conjuncin
ndice general
vi
4.7.
La implicacin y la consecuencia
Captulo 5.
86
95
5.1.
Eliminacin de parntesis
96
5.2.
Tcnicas bsicas
98
5.3.
Derivaciones relajadas
101
5.4.
Propiedades importantes de DS
104
5.5.
Tcnicas complementarias
109
Lenguaje y especificacin
125
6.1.
Trminos y frmulas
126
6.2.
136
6.3.
Sustitucin de trminos
140
6.4.
146
Captulo 7.
157
7.1.
157
7.2.
La cuantificacin universal
163
7.3.
La cuantificacin existencial
166
7.4.
Algunos metateoremas
169
7.5.
La igualdad
174
Captulo 1
Prembulo
Este captulo contiene material necesario para el resto del texto y debe ser
abordado a medida que se necesite. El material en esta seccin incluye convenciones y definiciones bsicas, y adems hace un recuento sucinto sobre la induccin
matemtica y los sistemas formales.
1.1.
Preludio
1. Prembulo
Primero que todo note que las definiciones vienen identificadas con un cdigo.
As, no es necesario referirse a ellas como en la definicin anterior (puede haber
ms de una definicin antes del texto y entonces esta afirmacin sera ambigua), sino
ms bien referencindola directamente como en la Definicin 1.1. En este ltimo
caso, la palabra definicin es un nombre propio y por eso la letra mayscula.
Los tipos de letra son claves para entender una definicin. En la Definicin 1.1
hay dos tipos de letra. Los sustantivos conjunto de nmeros naturales y nmero
natural estn en letra cursiva, lo cual no es un capricho: estos dos son los nombres
de los objetos que estn siendo definidos. Esto quiere decir, por ejemplo, que en este
texto los nmeros naturales son esos y no otros. Como convencin se adopta que
la expresin N representa el conjunto de nmeros naturales. En la segunda parte
de la Definicin 1.1, la expresin n es una variable matemtica y por eso tambin
aparece en letra cursiva.
En algunas ocasiones se hacen suposiciones de notacin y convencin. Por ejemplo, en la Definicin 1.1 el autor supone que el lector sabe qu es un nmero, que
prefiere la notacin arbica sobre la romana para escribirlos y que entiende qu
significa el smbolo . Es posible tratar de definir todo esto formalmente; sin,
embargo sera imprctico y no es el objetivo del texto.
Una vez un objeto est (unvocamente) definido, es posible entonces proceder
a estudiarlo. Es en este momento cuando se postulan y se demuestran propiedades
sobre el objeto de estudio.
Teorema 1.2
Sea n un nmero. Si n N, entonces (n + 1) N.
El Teorema 1.2 (si!, tambin tiene nombre) establece una propiedad inductiva
de los nmeros naturales que por lo pronto sirve nicamente de ejemplo. Esta
propiedad indica que el sucesor de todo nmero natural es un nmero natural.
Claramente, esto debe estar acompaado de una demostracin de la forma (en
donde el cuadro vaco al final de una lnea indica el fin de la demostracin):
Demostracin. ...
A diferencia de otros cursos de matemticas como clculo, algebra, etc., el estudio de la lgica se ocupa simultneamente de dos roles de la lgica: como objeto de
estudio y como herramienta de estudio. En este texto, se estudian diferentes lgicas
y cada una de ellas se define como un sistema formal (Seccin 1.3). Entonces, el tipo
de propiedades que se pueden establecer son dos: (i) propiedades del sistema formal
o (ii) propiedades dentro del sistema formal. En el caso (i) la lgica, como sistema
formal, es un objeto de estudio y las propiedades demostradas son meta-teoremas
(i.e., propiedades de la lgica como tal). En el caso (ii) la lgica, como herramienta,
est siendo usada para obtener resultados y las propiedades demostradas son teoremas (i.e., propiedades particulares de las expresiones de la lgica). La convencin
que sigue el texto es clasificar con el nombre de Metateorema a cada meta-teorema
y con el nombre de Teorema a cada teorema. El texto tambin usa los nombres
1.2. Induccin
1.2.
Induccin
Hay una pequea ancdota acerca del matemtico alemn Gauss quien, a los
8 aos de edad, no prestaba mucha atencin en clase. A modo de castigo, una vez
su profesor le pidi sumar los nmeros naturales de 0 a 100. La leyenda dice que
Gauss respondi correctamente 5050 despus de un par de segundos de formulada la
pregunta; esto enfureci al profesor. Cmo pudo Gauss hacer el clculo con tanta
rapidz? Posiblemente Gauss saba que
n (n + 1)
2
para todo nmero natural n. Entonces, al tomar n = 100, Gauss pudo calcular
fcilmente
100 101
0 + 1 + 2 + 3 + 4 + + 100 =
= 5050.
2
(1.1)
0 + 1 + 2 + 3 + 4 + + n =
1. Prembulo
Definicin 1.5
El principio de induccin matemtica dice que, bajo la suposicin de las propiedades
(1) y (2) mencionadas anteriormente, todo n N tiene la propiedad M (n). La
suposicin que aparece en el caso inductivo se llama hiptesis inductiva.
n(n+1)
2
para n N.
(n + 1) ((n + 1) + 1)
.
2
1.2. Induccin
Dado que los casos (1) y (2) son ciertos para G, por el principio de induccin
matemtica (Definicin 1.5), se sigue que todo n N tiene la propiedad G(n).
En la prctica, el principio de induccin matemtica tiene muchas variantes.
Por ejemplo, es posible contar con una versin en la que el caso base es n = 1,
lo cual excluira el 0. Tambin, como se ver en algunas secciones, el principio de
induccin matemtica se puede adaptar para hacer demostraciones sobre estructuras diferentes a los nmeros naturales como por ejemplo expresiones o rboles de
sintaxis. En cada variante, lo ms importante es identificar los casos base (puede
haber ms de uno) y los casos inductivos (de los cuales tambin puede haber ms
de uno).
Ejercicios
1. Use el principio de induccin matemtica, indicando cada uno de los casos y el
uso de la hiptesis inductiva, para demostrar
(2 1 1) + (2 2 1) + (2 3 1) + + (2 n 1) = n2
para todo n N con n 1.
2. Use el principio de induccin matemtica, indicando cada uno de los casos y el
uso de la hiptesis inductiva, para demostrar
n (n + 1) (2 n + 1)
02 + 12 + 22 + 32 + + n2 =
6
para todo n N.
3. Demuestre que 2n n+12 para todo nmero natural n 4. En este problema, el
caso base es n = 4. Es cierta es propiedad para n < 4? Justifique su respuesta.
4. Sea h(n) =
1
1
1
2
1
3
1. Prembulo
1.3.
Sistemas formales
El lenguaje debe tener la propiedad de que exista un algoritmo para decidir (i.e.,
que responda si o no en un nmero finito de pasos) si una expresin arbitraria es una
frmula o no. Todos los lenguajes estudiados en este texto tienen esta propiedad.
Nota 1.9
A lo largo de este texto, las letras griegas minsculas , , , , , , . . . (incluyendo
sus versiones primadas o con subndices) se usan para denotar frmulas de un
sistema formal, mientras que las letras griegas maysculas , , , , . . . se usan
para denotar conjuntos de frmulas.
Los axiomas de un sistema formal F son algunas frmulas especialmente seleccionadas. En muchos casos, el lenguaje formal se escoge con cierta interpretacin
inicial en mente y los axiomas entonces son algunas frmulas obviamente ciertas.
Un sistema formal debe contar con un algoritmo que decida si una frmula es un
axioma o no.
Una regla de inferencia es una regla que afirma que una frmula (llamada
conclusin) se sigue de un conjunto finito de frmulas (llamadas premisas). Suponga
que 0 , 1 , . . . , k , son frmulas (en la mayora de los casos k = 0, k = 1 o
k = 2). Una regla de inferencia con premisas 0 , 1 , . . . , k y conclusin se escribe
esquemticamente como
0
x+y =z
R2
y+x=z
1. Prembulo
semnticos. La interaccin entre los conceptos sintcticos y semnticos es fundamental en el estudio de la lgica matemtica. Por ejemplo, en la lgica proposicional
existe el concepto sintctico de teorema y el semntico de tautologa. Un objetivo
frecuente en el estudio de la lgica proposicional es demostrar que una frmula es
un teorema si y solo si es una tautologa.
Al contar con el concepto de sistema formal, ahora es posible dar definiciones
precisas de lo que son una demostracin y un teorema.
Definicin 1.10
Sea F un sistema formal. Una demostracin en F es una secuencia finita de frmulas
0 , 1 , . . . , n de F tal que para 0 k n una de las siguientes condiciones es
cierta:
1. k es un axioma de F o
2. k > 0 y k es la conclusin de una regla de inferencia de F cuyas premisas
aparecen en la secuencia 0 , . . . k1 .
Si 0 , 1 , . . . , n es una demostracin en F, entonces se dice que n es un teorema
de F, lo cual se escribe como
` F n .
(explicacin0 )
1.
(explicacin1 )
(explicacinn )
n.
Ejemplo 1.2
La frmula || + ||| = ||||| es un teorema del sistema formal ADD. Para demostrarlo,
basta con exhibir una demostracin formal:
0. | + | = ||
(axioma de F)
1. || + | = |||
2. ||| + | = ||||
3. | + ||| = ||||
4. || + ||| = |||||
(...)
1.
(...)
n1
(...)
n 1.
10
1. Prembulo
Nota 1.12
Fjese que la frmula , aparte de ser un teorema, es cualquier frmula. Ninguna
otra suposicin se ha hecho sobre la forma o estructura interna de . Lo mismo
sucede con los i . Entonces, al lograr el objetivo de demostrar que tiene la propiedad Q, necesariamente se logra demostrar que cualquier teorema de F tiene la
propiedad Q. Este tipo de comportamiento se conoce comnmente como el principio
de universalidad.
11
Ejercicios
1. Complete el Ejemplo 1.3 con el caso para la regla R2 de ADD.
2. Liste todos los teoremas del siguiente sistema formal:
Lenguaje: hay tres smbolos a, b y c; toda expresin es una frmula
Axiomas: cabcba
Reglas de inferencia: hay tres reglas de inferencia:
12
1. Prembulo
()
Add
Double
Omit
()
a) Demuestre que cada una de las siguientes frmulas son teoremas de PR:
1) ((())())
2) (())()()()
3) ()(()())()
b) Demuestre que todo teorema de PR tiene la propiedad de que la cantidad
de parntesis izquierdos es igual a la cantidad de parntesis derechos.
Parte 1
Lgica proposicional
Captulo 2
Lenguaje y especificacin
Ejemplo 2.1
Si el tren llega tarde y no hay taxis en la estacin, entonces Juan llegar tarde a su
reunin. Juan no llega tarde a su reunin. El tren lleg tarde. Consecuentemente,
haba taxis en la estacin.
15
16
2. Lenguaje y especificacin
Ejemplo 2.2
Si est lloviendo y Juana no tiene una sombrilla a su alcance, entonces ella se
empapar. Juana no se empap. Est lloviendo. Consecuentemente, Juana tiene
una sombrilla a su alcance.
Ejemplo 2.2
est lloviendo
Juana tiene una sombrilla a su alcance
Juana se empapa
En realidad, la argumentacin en cada uno de los ejemplos puede ser formulada sin referirse a protagonistas especficos, trenes, taxis, sombrillas o lluvia, de la
siguiente forma:
Si p y no q, entonces r. No r. p. Consecuentemente, q.
Como moraleja, es importante entender que al desarrollar una lgica la principal preocupacin no es saber el significado particular de cada frase sino ms bien
aprender sobre su estructura. Obviamente, al aplicar un razonamiento, como en
caso anterior, el significado de cada frases es de vital importancia.
Este captulo se ocupa de desarrollar el lenguaje de la lgica proposicional como
lenguaje para especificar. El siguiente captulo explica cundo una especificacin es
cierta y cundo una argumentacin es vlida.
2.1.
Proposiciones
Para razonar rigurosamente es indispensable desarrollar un lenguaje para expresar afirmaciones de forma tal que su estructura interna sea evidente y pueda ser
analizada. Este es el lenguaje de la lgica proposicional: est basado en proposiciones o sentencias declarativas, i.e., frases con un valor de verdad asociado.
Ejemplo 2.3
Las siguientes frases son ejemplos de proposiciones:
1. La suma de los nmeros 3 y 5 es 8.
2. Juana reaccion agresivamente ante las acusaciones de Juan.
2.1. Proposiciones
17
3. Todo nmero natural n > 2 par puede expresarse como la suma de dos nmeros
primos.
4. A todo marciano le gusta el calentado con frjoles.
5. Such a good actress, hiding all her pain, trading in memories for fortune and
fame.
6. Albert Camus tait un crivain franais.
7. Die Wrde des Menschen ist unantastbar.
8. jIyajbe.
Todas estas frases son declarativas porque en principio cada una de ellas es verdadera o falsa. La frase (1) puede ser verificada usando aspectos bsicos de la
aritmtica (y suponiendo tcitamente una representacin arbica en base diez de
los nmeros naturales). La frase (2) es un poco problemtica. Para determinar su
valor de verdad es necesario saber quines son Juana y Juan, y posiblemente tener
un recuento fehaciente sobre la situacin. En principio, si alguien estuvo en la escena, entonces pudo haber detectado la reaccin agresiva de Juana. La frase (3) es
conocida como la conjetura de Goldbach y a simple vista parece trivial. Claramente
una afirmacin acerca de todos los nmeros naturales pares mayores que 2 es verdadera o falsa. Al da de hoy, nadie sabe si la conjetura de Goldbach es verdadera
o falsa, por simple que parezca. La frase (4) parece un poco tonta: afirma que si los
marcianos existen y gustan comer calentado, entonces o lo prefieren con frjoles o
sin frjoles. Esta frase tiene asociado un valor de verdad independientemente de si
existan o no los marcianos; en este sentido es una proposicin. Et alors, quest-ce
quon pense des phrases (5), (6), (7) et (8)? Las frases (5), (6), (7) y (8) son tambin
proposiciones; esto lo puede corroborar si puede leer un poco de, respectivamente,
ingls, francs, alemn o klingon.
Nota 2.1
En este texto se consideran como proposiciones aquellas frases que tengan un valor
de verdad asociado, independientemente de si este valor corresponde o no a la
realidad. Adems, una proposicin puede estar escrita en cualquier lenguaje, natural
o artifical.
Ejemplo 2.4
Ejemplos de frases que no son proposiciones:
18
2. Lenguaje y especificacin
Las lgicas que se desarrollan en este texto son simblicas por naturaleza y su
desarrollo sigue una metodologa. Inicialmente se traduce un conjunto suficientemente grande de proposiciones del castellano a cadenas de smbolos. Estas cadenas
son cortas pero codifican las proposiciones y permiten concentrarse en la mecnica
del razonamiento. Adems, esta metodologa abre las puertas a la mecanizacin de
la manipulacin simblica, algo que los computadores hacen muy bien (y rpido).
Ejercicios
1. Los siguientes prrafos han sido tomados de Wikipedia. De estos prrafos, liste
tres proposiciones y tres frases que no sean proposiciones.
La lgica matemtica estudia los sistemas formales en relacin con el modo en el que codifican conceptos intuitivos de objetos matemticos como
conjuntos, nmeros, demostraciones y computacin. La lgica estudia las
reglas de deduccin formales, las capacidades expresivas de los diferentes
lenguajes formales y las propiedades metalgicas de los mismos.
En un nivel elemental, la lgica proporciona reglas y tcnicas para determinar si es o no vlido un argumento dado dentro de un determinado sistema
formal. En un nivel avanzado, la lgica matemtica se ocupa de la posibilidad de axiomatizar las teoras matemticas, de clasificar su capacidad
expresiva, y desarrollar mtodos computacionales tiles en sistemas formales. La teora de la demostracin y la matemtica inversa son dos de los
razonamientos ms recientes de la lgica matemtica abstracta. Debe sealarse que la lgica matemtica se ocupa de sistemas formales que pueden
no ser equivalentes en todos sus aspectos, por lo que la lgica matemtica no es mtodo de descubrir verdades del mundo fsico real, sino slo
una fuente posible de modelos lgicos aplicables a teoras cientficas, muy
especialmente a la matemtica convencional.
La lgica matemtica no se encarga por otra parte del concepto de razonamiento humano general o del proceso creativo de construccin de demostraciones matemticas mediante argumentos rigurosos pero hechas usando
lenguaje informal con algunos signos o diagramas, sino slo de demostraciones y razonamientos que pueden ser completamente formalizados en todos
sus aspectos.
2. Los siguientes prrafos han sido tomados de Wikipedia. De estos prrafos, liste
tres proposiciones y tres frases que no sean proposiciones.
19
Una especificacin formal usa notacin matemtica para describir de manera precisa las propiedades que un sistema de informacin debe tener, sin
preocuparse por la forma de obtener dichas propiedades. Describe lo que el
sistema debe hacer sin decir cmo se va a hacer.
Esta abstraccin hace que las especificaciones formales sean tiles en el
proceso de desarrollar un sistema, porque permiten responder preguntas
acerca de lo que el sistema hace con confianza, sin la necesidad de tratar
con una gran cantidad de informacin no relevante que se encuentra en el
cdigo de programa del sistema en un lenguaje de programacin cualquiera,
o especular sobre el significado de frases en un impreciso Pseudocdigo.
Una especificacin formal puede servir como un punto de referencia fiable
tanto para quienes se dedican a investigar sobre los requerimientos del cliente que solicita el sistema, como para aquellos que desarrollan los programas
para satisfacer esos requerimientos, y tambin para los que redactan manuales de instrucciones para el sistema. Debido a que es independiente del
cdigo del programa, las especificaciones formales de un sistema pueden
ser elaboradas a principios de su desarrollo; y puede ser un medio valioso
para promover un entendimiento comn entre todos los interesados en el
sistema.
2.2.
Lenguaje formal
20
2. Lenguaje y especificacin
Nombre
negacin
equivalencia
disyuncin
conjuncin
implicacin
consecuencia
Interpretacin
no
si y solo si
o
y
si , entonces
si
21
22
2. Lenguaje y especificacin
::= p | () | ( ) | ( ) | ( ) | ( ) | ( )
Ejemplo 2.7
Usando las convenciones en la Nota 2.5, el argumento en el Ejemplo 2.1, puede
especificarse con la siguiente secuencia de cuatro proposiciones
((p (q)) r), (r), p, q
en donde las variables proposicionales simbolizan:
p: el tren est tarde
q: hay taxis en la estacin
r: Juan llega tarde a su reunin
Ejercicios
1. Justifique por qu cada una de las siguientes expresiones es una proposicin:
a) p
b) (q (q))
c) (p (p (q)))
d ) ((((p r))))
23
24
2. Lenguaje y especificacin
r q
p q r
Figura 1. rbol de sintaxis de (((p q) (r)) (r q)).
2.3.
rboles de sintaxis
Para los humanos, utilizar parntesis es tedioso. La razn por la cual son necesarios en las proposiciones, es porque las proposiciones en realidad tienen forma
de rbol!, a pesar de que comnmente sean escritas como lneas de texto. Los
parntesis son los signos de puntuacin que permiten escribir proposiciones linealmente. La Figura 1 presenta el rbol de sintaxis correspondiente a la proposicin
(((p q) (r)) (r q)). En un rbol de sintaxis los parntesis son innecesarios.
Sus caminos y estructura arborescente eliminan cualquier posible ambigueadad al
leer una proposicin. Al escribir una proposicin linealmente, su estructura arborescente se conserva insertando parntesis tal y como se describe en la definicin de
proposicin (Definicin 2.4).
Note que un rbol de sintaxis tiene como raz (i.e., primer smbolo de arriba
a abajo) una variable proposicional o un conectivo lgico. En el primer caso, la
variable proposicional es el nico smbolo que aparece en el rbol. En el caso en que
la raz sea el conectivo lgico , entonces la raz tiene exactamente un subrbol.
En cualquier otro caso, la raz tiene exactamente dos subrboles. En todas estas
situaciones, los subrboles se comportan tal y como se acaba de describir; este es
un nuevo ejemplo de una definicin inductiva.
Pensar acerca de proposiciones usando su representacin en rbol de sintaxis
puede ser til para entender nociones como, por ejemplo, el de subproposicin (o,
igualmente, subfrmula).
Definicin 2.6
Sea una proposicin. Una subproposicin de es una proposicin que corresponde
a uno de los subrboles del rbol de sintaxis de .
25
Ejemplo 2.8
Las subproposiciones de (((p q)(r)) (rq)), de acuerdo con la Definicin 2.6,
se obtienen a partir del rbol de sintaxis en la Figura 1. Esta proposicin tiene 8
subproposiciones, que se listan a continuacin:
p
(r)
((p q) (r))
(r q)
(p q)
p q
Primero que todo note que no se ha afirmado que este rbol corresponda a un
rbol de sintaxis. De hecho, este rbol no corresponde a un rbol de sintaxis. Por
ejemplo, la hoja , de acuerdo con la definicin de proposicin, se debe aplicar
a dos subproposiciones pero en este caso no se aplica a proposicin alguna (porque
este nodo no tiene subrboles). Un argumento similar aplica para el subrbol con
raz , en dnde hace falta un subrbol.
Ejercicios
1. Dibuje el rbol de sintaxis para cada una de las siguientes proposiciones:
a) p
b) (p r)
c) ((p (q)) r)
d ) ((p q) ((p) (q)))
26
2. Lenguaje y especificacin
e) (p (q p))
f ) ((p r) (p q))
g) (((r (r (p s))) (((p q) (r (r))))))
2. Liste todas las subproposiciones de cada una de las siguientes proposiciones:
a) p
b) (p r)
c) ((p (q)) r)
d ) ((p q) ((p) (q)))
e) (p (q p))
f ) ((p r) (p q))
g) (((r (r (p s))) (((p q) (r (r))))))
3. Dibuje rbol de sintaxis para cada una de los siguientes casos:
a) Una proposicin que es una negacin de una equivalencia.
b) Una proposicin que es una disyuncin cuyos disyuntos ambos son conjunciones.
c) Una proposicin que es una conjuncin de conjunciones.
d ) Una proposicin que es una implicacin cuyo antecedente es una negacin
y consecuente es una equivalencia.
e) Una proposicin que es una consecuencia cuyo antecedente es una disyuncin y consecuente una implicacin.
4. Escriba la proposicin correspondiente al siguiente rbol de sintaxis:
q r p
p
q q
5. En cada uno de los siguientes casos, dibuje un rbol de smbolos que no represente una proposicin y que satisfaga las condiciones dadas:
a) Al extenderlo con al menos un subrbol el rbol obtenido represente una
proposicin.
b) Sea patolgicamente mal formado, i.e., no hay forma de extenderlo con
subrboles de tal modo que el rbol obtenido represente una proposicin.
2.4.
Para demostrar que toda proposicin (o una gran cantidad de ellas) tiene una
propiedad dada se emplea el principio de induccin sobre proposiciones. Este principio de induccin se presenta en el Metateorema 2.7; su demostracin se obtiene
27
En el Metateorema 2.7, el numeral (1) corresponde al caso base de una demostracin por induccin, mientras que los numerales (2) y (3) corresponden al caso
inductivo; la suposicin de que y tienen la propiedad Q es la hiptesis inductiva.
28
2. Lenguaje y especificacin
Ejemplo 2.10
Se desea demostrar que toda proposicin tiene la misma cantidad de parntesis
izquierdos y derechos. Para una proposicin , se definen las funciones L y R de la
siguiente manera:
L() : nmero de parntesis izquierdos en ,
R() : nmero de parntesis derechos en .
Para cualquier proposicin , el objetivo es demostrar la propiedad P :
P () : L() = R().
La demostracin procede por induccin sobre .
Caso base: Si es una variable proposicional, entonces no tiene parntesis
alguno y se tiene que L() = 0 = R().
Caso inductivo: Hay 6 casos: que sea de la forma (), ( ), ( ),
( ), ( ) o ( ). Suponga que es de la forma ( ). Por la
hiptesis inductiva, se sabe que L() = R() y L( ) = R( ). Note que:
L() = L(( ))
= 1 + L() + L( )
= 1 + R() + R( )
= R(( )) = R().
En cualquiera de los dos casos L() = R(), como se desea. Los casos en que es
de la forma (), ( ), ( ), ( ) o ( ) son similares y se proponen
como ejercicios para el lector.
Ejercicios
1. Complete la demostracin del Metateorema 2.7 con los casos en que sea de
las forma (), ( ), ( ), ( ) o ( ).
2. Complete el Ejemplo 2.10 con los casos en que sea de la forma (), ( ),
( ), ( ) o ( ).
3. Demuestre que cualquier proposicin que no sea una variable proposicional
inicia con un parntesis izquierdo y termina con un parntesis derecho.
4. Demuestre que cualquier proposicin tiene al menos una variable proposicional.
5. Demuestre que cualquier frmula con al menos una mencin de menciona al
menos dos variables proposicionales (no necesariamente distintas).
6. Sea Prop(, ) el conjunto de proposiciones que tienen a y como nicos
conectivos lgicos. Demuestre que si Prop(, ), entonces es de la forma
p, (p), (()), ( ) o (( )), en donde y son proposiciones en
Prop(, ).
29
Captulo 3
Semntica
3.1.
Funciones Booleanas
Una proposicin expresa un hecho acerca del mundo, real o imaginario, de alguno abstracto como lo es un modelo de computador o simplemente se refiere a
una idea o un sentimiento. En cualquier escenario, una proposicin tiene un nico
31
32
3. Semntica
33
Ejemplo 3.1
Sea H : B2 B la funcin Booleana definida por
H(F, F) = H(F, T) = F
H(T, F) = H(T, T) = T.
F F
F T
T F
T T
Las primeras dos columnas de la tabla sistemticamente listan todos los elementos
del conjunto B2 (i.e., los valores de entrada); la tercera columna muestra el valor
de H para cada una de las parejas de las primeras dos columnas (i.e., los valores
de salida).
(p)
T
F
H (F) = T
H (T) = F
34
3. Semntica
propsito de enfatizar o resaltar el efecto que tiene una funcin Booleana sobre una
variable proposicional.
Definicin 3.7
La funcin H define la interpretacin de la equivalencia:
p q
F F
F T
T F
T T
(p q)
T
F
F
T
H (F, F) = H (T, T) = T
H (F, T) = H (T, F) = F
(p q)
F
T
T
T
H (F, F) = F
H (F, T) = H (T, F) = H (T, T) = T
(p q)
F
F
F
T
35
Definicin 3.10
La funcin H define la interpretacin de la implicacin:
p
F
F
T
T
q
F
T
F
T
(p q)
T
T
F
T
Definicin 3.12
La funcin H define la interpretacin de la consecuencia:
p
F
F
T
T
q
F
T
F
T
(p q)
T
F
T
T
36
3. Semntica
q
F
T
F
T
(p q)
T
T
F
T
37
imposible. Por ejemplo, para diez variables proposicionales (i.e., n = 10), la tabla
de verdad tiene 1024 renglones. Por estas limitaciones, las tablas de verdad son
tiles para valores de n relativamente pequeos.
Ejercicios
1. Liste todas las funciones Booleanas unarias.
2. Determine el nmero de funciones Booleanas binarias y describa dos que sean
diferentes a H , H , H , H y H .
3. Escriba una tabla de verdad para el operador o exclusivo que permite expresar
la proposicin p o q pero no ambas. Tambin presente una definicin de este
operador en donde nicamente se usen los conectivos lgicos de negacin y
equivalencia.
4. Dibuje la tabla de verdad para cada una de las siguientes proposiciones:
a) (p (q))
b) (p (q))
c) (p (q))
d ) ((p q) (q p))
e) ((q (p)))
f ) ((p q) (q p))
g) ((p q) p)
h) (p (p q))
i ) ((p (p q)) (p q))
j ) ((p (q r)) ((p q) r))
k ) ((p (q r)) ((p q) r))
l ) ((p (q r)) ((p q) r))
5. Tienen las proposiciones (p q) y ((p q) (p q)) el mismo significado?
Justifique su respuesta.
6. Justifique que la equivalencia no es asociativa, es decir, que las proposiciones
(p (q r)) y ((p q) r) no tienen el mismo significado.
7. Dibuje la tabla de verdad de la proposicin que se encuentra en la Figura 1
(Seccin 2.3).
8. Una proposicin se llama tautologa si y solo si todos los renglones de su tabla
de verdad resultan en T y se llama contradiccin si y solo si todos los renglones
resultan en F. Encuentre una proposicin que no sea tautologa ni contradiccin
y dibuje su tabla de verdad.
9. Considere un conectivo lgico binario ? cuya interpretacin est dada por la
funcin Booleana H? : B2 B definida de la siguiente manera:
H? (F, F) = T
38
3. Semntica
c) Encuentre una proposicin que nicamente mencione las variables proposicionales p, q y el conectivo ?, y con la misma tabla de verdad de (p q).
10. Considere un conectivo lgico binario cuya interpretacin est dada por la
funcin Booleana H : B2 B definida de la siguiente manera:
H (F, F) = H (F, T) = H (T, F) = T
H (T, T) = F.
H (F, T) = T.
3.2. Valuaciones
39
3.2.
Valuaciones
40
3. Semntica
Nota 3.14
Es conveniente seguir algunas convenciones para escribir valuaciones. Se usarn letras minsculas en negrilla para denotar valuaciones. Adems, dada una proposicin
con variables en la lista p1 , p2 , . . . , pn , se usar la expresin
{p1 7 val1 , p2 7 val2 , . . . , pn 7 valn }
para denotar una valuacin de que asigna los valores Booleanos val1 a p1 , val2 a
p2 , . . . y valn a pn . Por ejemplo, si se identifica con v la valuacin en el Ejemplo 3.3,
esta puede escribirse como
v = {p 7 T, q 7 F}.
Definicin 3.15
Sea una proposicin y v una valuacin de . La extensin de v a , denotada
como v, se define inductivamente para toda subproposicin de de la siguiente
forma:
1. v(p) = v(p)
2. v(()) = H (v())
3. v(( )) = H (v(), v( ))
4. v(( )) = H (v(), v( ))
5. v(( )) = H (v(), v( ))
6. v(( )) = H (v(), v( ))
7. v(( )) = H (v(), v( ))
Note en la Definicin 3.15, que una valuacin y su extensin coinciden en las variables proposicionales (caso (1)). Los dems casos en la Definicin 3.15 corresponden
a definiciones inductivas que dependen de los conectivos lgicos.
3.2. Valuaciones
41
Ejemplo 3.4
Considere la valuacin v = {p 7 T, q 7 F} de ((p) q) en el Ejemplo 3.3. De
acuerdo con la Definicin 3.15, se tiene que:
v(((p) q)) = H (v((p)), v(q))
= H (v((p)), F)
(v(q) = v(q) = F)
= H (H (v(p)), F)
= H (H (T), F)
(v(p) = v(p) = T)
= H (F, F)
=T
42
3. Semntica
w coinciden en todas las variables proposicionales que aparecen en . La demostracin de que tiene la propiedad M se sigue del principio de induccin sobre
proposiciones (Metateorema 2.7):
Caso base: Si es una variable proposicional, por ejemplo p, entonces
v(p) = v(p) = w(p) = w(p)
dado que v y w coinciden en cualquier variable proposicional en .
Caso inductivo: Hay 6 casos: que sea de la forma (), ( ), ( ),
( ), ( ) o ( ). Si es de la forma () y tiene la propiedad
M , entonces:
v(()) = H (v())
= H (w())
(hiptesis inductiva)
= w(())
Si es de la forma ( ) y, tanto como tienen la propiedad M , entonces:
v(( )) = H (v(), v( ))
= H (w(), w( ))
= w(( ))
En cualquiera de los tres casos v() = w(), como se desea. Los casos en que es
de la forma ( ), ( ), ( ) o ( ) son similares y se proponen como
ejercicios para el lector.
Nota 3.17
Para simplificar la escritura de la extensin v de una valuacin v, se adopta la
convencin de referirse a dicha extensin como una valuacin y denotarla como v.
Es decir, intencionalmente se evita distinguir entre una valuacin y su extensin.
Hay una forma alternativa, pero algo informal, de caracterizar esta extensin al
usar directamente el significado intuitivo de los conectivos lgicos y evitando mencionar explcitamente las funciones Booleanas. Esta formulacin alternativa puede
simplificar an ms razonamientos y clculos.
Metateorema 3.18
Sean y proposiciones, y v una valuacin de y . Entonces:
1. v(()) = F si y solo si v() = T; v(()) = T si y solo si v() = F.
2. v(( )) = T si y solo si v() = v(); de lo contrario v(( )) = F.
3. v(( )) = F si y solo si v() = v() = F; de lo contrario v(( )) = T.
3.2. Valuaciones
43
Nota 3.19
La expresin si y solo si que aparece en el Metateorema 3.18 es una metaequivalencia: tiene dos operandos y es verdad nicamente cuando los dos operandos
coinciden en sus valores de verdad. Note que su interpreacin es similar a la de la
equivalencia lgica. Sin embargo, no es el mismo operador: el si y solo si tiene
como operandos expresiones que no hacen parte del lenguaje de la lgica proposicional, y como tal hace parte del lenguaje cotidiano y no del lenguaje del sistema
formal de la lgica proposicional. El operador si y solo si en algunas ocasiones se
abrevia como sii.
44
3. Semntica
tiene:
v((p q)) = F sii v(p) = T y v(q) = F
(caso )
(caso )
(caso ).
De estos clculos se concluye que v((p q)) = v(((p) q)) y, por el mismo
Metateorema 3.18, se obtiene v(((p q) ((p) q))) = T (caso ).
Ejercicios
1. Considere la proposicin representada por el siguiente rbol de sintaxis:
q r p
p
q q
w = {p 7 T, q 7 F, r 7 T}.
3.3.
45
Clasificacin de proposiciones
Esta seccin presenta terminologa que permite clasificar proposiciones de acuerdo con su valor de verdad.
La proposicin el agua moja es verdadera por virtud de un hecho de la naturaleza; pueda que esta proposicin sea falsa en otro mundo o realidad. A su vez, la
proposicin el agua moja o no moja es cierta por virtud de su estructura interna
y, en particular, por el significado de la disyuncin y la negacin; esta proposicin
es cierta en cualquier mundo o realidad. Este segundo ejemplo motiva la siguiente
definicin.
Definicin 3.20
Una proposicin es una tautologa, escrito |= , si y solo si v() = T para cualquier
valuacin v de .
46
3. Semntica
Metateorema 3.21
Hay un algoritmo que, dada cualquier proposicin de la lgica proposicional, decide
si esta es una tautologa o no.
Intuitivamente, dos proposiciones son lgicamente equivalentes si sus tablas de verdad coinciden en todos los renglones. Una proposicin implica lgicamente a otra
siempre y cuando si la primera es verdadera en un rengln de verdad, entonces la
segunda necesariamente es cierta en ese mismo rengln. Note que la implicacin
lgica no es una relacin simtrica: puede que implique lgicamente a , pero no
necesariamente implica . En este sentido, la equivalencia lgica es un concepto
ms verstil que la implicacin lgica porque, a diferencia de la implicacin lgica,
la equivalencia lgica si es simtrica.
Ejemplo 3.7
Las proposiciones (p q) y (q p) son lgicamente equivalentes, al igual que las
proposiciones (p (q r)) y ((p q) r). La proposicin (p q) implica lgicamente a p. Sin embargo, las proposiciones p y q no son lgicamente equivalentes ni
p implica lgicamente a (p q).
Claramente no toda proposicin es una tautologa. La siguiente definicin completa la clasificacin de proposiciones.
47
Definicin 3.24
Sea una proposicin. Se dice que:
1. es satisfacible si y solo si hay una valuacin v de tal que v() = T.
2. es insatisfacible (o una contradiccin), escrito 6|= , si y solo si cualquier
valuacin v de es tal que v() = F.
Note que si una proposicin es una tautologa, entonces es satisfacible. Adems, una
proposicin es una tautologa siempre y cuando su negacin sea una contradiccin
(y viceversa). Algunas de estas relaciones se proponen como ejercicios para el lector.
Ejemplo 3.8
Para demostrar que (p (q)) es satisfacible, basta con encontrar una valuacin v
tal que v((p (q))) = T. Note que
v = {p 7 T, q 7 F}
es tal que v((p (q))) = T. Dado que esta proposicin es satisfacible, es imposible
que sea una contradiccin.
Ejercicios
1. Demuestre que las siguientes proposiciones son tautologas:
a) (( ) ( )).
b) (( ( )) (( ) )).
c) (( ) ( )).
d ) (( ( )) (( ) )).
e) (( ) ( )).
f ) (( ( )) (( ) )).
g) (( ())).
h) ( ( )).
i ) (( ( )) (( ) ( ))).
j ) (( ) (() ())).
2. Demuestre que las siguientes proposiciones son satisfacibles pero no tautologas:
a) (p q).
b) ((p) q).
c) ((p) (p q)).
d ) ((p (q))).
e) (((p q)) p).
3. Proponga 3 proposiciones que sean contradicciones.
48
3. Semntica
3.4.
49
Definicin 3.26
Sea una proposicin y un conjunto de proposiciones. Se dice que es una
consecuencia tautolgica de , escrito |= , si y solo si cualquier valuacin que
satisface a tambin satisface a .
Ejemplo 3.9
Sea = {(p q), p}. Note que |= q porque si v es tal que v((p q)) = T
y v(p) = T, por la funcin H se sigue v(q) = T. Otra forma de proceder para
llegar a la misma conclusin es tratar de falsificar la conscuencia lgica: encontrar
una valuacin v tal que v(q) = F y que v((p q)) = v(p) = T. Pero note que si
v(p) = T, entonces es imposible tener v((p q)) = T y v(q) = F. En esta caso
tambin se tiene |= q.
50
3. Semntica
Ejemplo 3.10
Sea = {(p q), p}. Note que q no es una consecuencia tautolgica de . Tome,
por ejemplo,
v = {p 7 T, q 7 F}
y note que v satsiface pero v(q) = F. Entonces q no es una consecuencia tautolgica de .
51
Vale la pena resaltar un par de detalles claves en la Definicin 3.31 sobre la validez e
invalidez de una argumentacin. Primero, note que 1 , . . . , n , es vlida siempre y
cuando toda valuacin v es tal que si v(i ) = T para 1 i n, entonces v() = T.
De forma similar, 1 , . . . , n , es invlida siempre y cuando haya una valuacin w
es tal que si w(i ) = T para 1 i n, entonces w() = F.
Ejemplo 3.11
Se demuestra que la siguiente argumentacin, correspondiente al Ejemplo 2.1, es
vlida:
((p (q)) r), (r), p, q.
Por la Definicin 3.31, se debe demostrar
{((p (q)) r), (r), p} |= q.
Sea v una valuacin tal que:
(1) v(((p (q)) r)) = T,
(2) v((r)) = T,
(3) v(p) = T.
52
3. Semntica
El objetivo es demostrar v(q) = T. De (2) se tiene que v(r) = F. Esto, junto con
(1), indica que v((p (q))) = F. Por (3), se tiene necesariamente que v((q)) = F,
es decir, v(q) = T.
Una demostracin alternativa, usando el Metateorema 3.29, se propone como
ejercicio para el lector.
Ejemplo 3.12
Considere la siguiente argumentacin:
((p q)), (p), q.
Para demostrar que es invlida, basta con encontrar una valuacin que satisfaga a
{((p q)), (p)} y que falsifique a q. Tome v = {p 7 F, q 7 F} y note que:
v(((p q))) = v((p)) = T
pero
v(q) = F.
Ejercicios
1. Demuestre para cualesquiera proposiciones , , :
a) {} |= .
b) {(( ))} |= .
c) {} |= ( ).
d ) {( ), (() )} |= ( ).
2. Demuestre el Metateorema 3.29.
3. Proponga una demostracin del Ejemplo 3.11 que use directamente el Metateorema 3.29.
4. Sean y conjuntos de proposiciones, y , proposiciones. Demuestre:
a) Si |= y , entonces |= .
b) {} |= si y solo si |= ( ).
c) Si {} |= y {()} |= , entonces |= .
5. Sean y conjuntos de proposiciones, y una proposicin. Demuestre que si
|= y |= (), entonces es insatisfacible.
6. Demuestre que cada una de las siguientes argumentaciones son vlidas:
a) ( ), (), ().
b) ( ), (), ().
c) ( ), (), .
d ) ( ), ( ()), ().
7. Demuestre que cada una de las siguientes argumentaciones es invlida:
53
a) (p q), q, p.
b) (p q), (p), (q).
8. Considere el Ejercicio 5 en la Seccin 2.2. Especifique cada una de las argumentaciones y determine cules de las argumentaciones son vlidas o invlidas.
Justifique su respuesta.
9. Si una argumentacin 1 , . . . , n , es invlida, entonces la argumentacin
1 , . . . , n , () es vlida? Justifique su respuesta.
3.5.
Hay una amplia variedad de acertijos lgicos (i.e., adivinanzas) relativas a una
isla en la cual ciertos habitantes llamados caballeros dicen siempre la verdad y otros
llamados escuderos siempre mienten. En esta isla cada habitante es caballero o
escudero; de ah su nombre: la isla de caballeros y escuderos. Esta seccin presenta
ejemplos sobre cmo especificar y analizar acertijos lgicos relativos a la isla de
caballeros y escuderos usando la lgica proposicional. Los metodos presentados en
esta seccin pueder ser utilizados para analizar otros tipos de acertijos.
Nota 3.32
Las isla de caballeros y escuderos (en ingls, the island of knights and knaves) fue
presentada inicialmente por Raymond Smullyan en su libro Cmo se llama este
libro? (en ingls, What is the name of this book?) en 1978. Smullyan es un prolfico
matemtico y lgico Estadounidense.
54
3. Semntica
55
El anlisis en el Ejemplo 3.16 se hace por casos sobre la naturaleza de A. Inicialmente se explora la posibilidad de que A sea caballero, concluyendo que entonces
B es escudero. Posteriormente, se explora la posibilidad de que A sea escudero,
concluyendo que es imposible. Solo hay una posibilidad, luego las naturalezas de A
y B se pueden determinar unvocamente: A es caballero y B es escudero.
Hay una forma alternativa de analizar este tipo de acertijos. En particular, note
que en el anlsis por casos del Ejemplo 3.16 explora todas las posibles valuaciones
de la proposicin que especifica el acertijo. Otra forma de analizar el acertijo es por
medio de tablas de verdad.
Ejemplo 3.17
El anlisis por tabla de verdad del acertijo del Ejemplo 3.13 se hace sobre la proposicin encontada en el Ejemplo 3.15:
(a ((a) (b))).
56
3. Semntica
b ((a) (b))
F
T
T
T
F
T
T
F
(a ((a) (b)))
F
F
T
F
1 , . . . , n , ,
en donde 1 , . . . , n son proposiciones que especifican informacin suministrada en
el enunciado del acertijo y es una proposicin incgnita. Con este enfoque, el
objetivo es despejar buscando proposiciones que suministren informacin sobre
la naturaleza de los habitantes de la isla involucrados en el acertijo. Por ejemplo, si
1 , . . . , n son las hiptesis de la argumentacin y se quiere averigar si el habitante
P puede ser caballero, basta con encontrar una valuacin v tal que v(p) = T y v
satisfaga {1 , . . . , n }. Coversamente, si se quiere averigar si el habitante P puede
ser escudero, basta con encontrar una valuacin w tal que w(p) = F y w satisfaga
{1 , . . . , n }. En el primer escenario, de ser factible, se establece que la situacin
descrita por el acertijo es posible cuando P es caballero. En el segundo escenario, de
ser factible, se establece que la situacin descrita por el acertijo es posible cuando
P es escudero. Luego, si exactamente uno de los dos escenarios es factible para P ,
entonces se ha determinado unvocamente la naturaleza de P .
Ejemplo 3.18
En esta ocasin, tres habitantes de la isla, llamados A, B y C, estn siendo entrevistados. Se emiten las siguientes afirmaciones:
A dice: B es caballero.
B dice: Si A es caballero, entonces tambin lo es C.
El objetivo es determinar la naturaleza de A, B y C.
57
Ejercicios
1. Explique por qu en el Ejemplo 3.16 es suficiente hacer anlisis por casos sobre
a, y no es necesario hacer anlisis por casos sobre a y b.
2. Suponga que un habitante de la isla llamado A dice: soy un escudero o B es
un caballero. Determine la naturaleza de A y B.
3. Suponga que un habitante de la isla llamado A dice: soy un escudero y B no
lo es. Determine la naturaleza de A y B.
4. Suponga que un turista est en presencia de dos habitantes de la isla llamados
A y B. A dice : nosotros tenemos la misma naturaleza. Pueden determinarse
las naturalezas de A y B? Justifique su respuesta.
5. Suponga que un turista est en presencia de dos habitantes de la isla llamados
A y B. A dice : al menos uno de nosotros es caballero. Pueden determinarse
las naturalezas de A y B? Justifique su respuesta.
6. Proponga una frase que nunca puede ser hecha por un habitante de la isla.
Explique su respuesta.
7. Suponga que las variables proposicionales a y b representan la naturaleza de
dos habitantes de la isla llamados A y B. Invente un acertijo que corresponda
58
3. Semntica
59
Captulo 4
El sistema de Dijkstra y
Scholten
4.1.
El sistema formal DS
El lenguaje formal del sistema DS generaliza el lenguaje de la lgica proposicional propuesto inicialmente en la Definicin 2.2 (Seccin 2.2).
Definicin 4.1
Los smbolos de DS son:
Una coleccin infinita de variables proposicionales
p0 , p1 , p2 , . . .
Parntesis izquierdo ( y parntesis derecho )
61
62
En el lenguaje de la lgica proposicional hay una cantidad infinita de variables proposicionales p0 , p1 , . . . que se emplean para representar proposiciones atmicas. Los
parntesis izquiero y derecho se utilizan para puntuar frmulas del sistema formal.
El lenguaje de DS incluye los conectivos lgicos previamente estudiados como la
negacin (), la equivalencia (), la disyuncin (), la conjuncin (), la implicacin () y la consecuencia () (Definicin 2.2, Seccin 2.2). Estos conectivos son
completados con tres nuevos smbolos lgicos: true, false y 6. A continuacin se
presenta una tabla con los nombres y las interpretaciones intuitivas que reciben los
smbolos lgicos del sistema DS:
Smbolo
true
false
Nombre
verdadero
falso
negacin
equivalencia
discrepancia
disyuncin
conjuncin
implicacin
consecuencia
Interpretacin
verdad
falsedad
no
si y solo si
o exclusivo
o
y
si , entonces
si
63
Definicin 4.3
Las frmulas del sistema DS (o proposiciones) son aquellas cadenas obtenidas usando
una cantidad finita de veces las siguientes reglas:
1. Cada variable proposicional es una proposicin.
2. Las constantes true y false son proposiciones.
3. Si es una proposicin, entonces () es una proposicin.
4. Si y son proposiciones, y {, 6, , , , }, entonces ( ) es una
proposicin.
La expresin VPROP denota el conjunto de variables proposicionales de DS y la
expresin PROP el conjunto de proposiciones de DS. Note que VPROP ( PROP.
Hfalse () = F.
H6 (F, T) = H6 (T, F) = T.
64
Una sustitucin F es una funcin que asocia una proposicin F (p) a cualquier
variable p. Sin embargo, cualquier sustitucin F es tal que F (p) 6= p para una
cantidad finita de variables p. Por ello, una sustitucin siempre puede ser escrita
como un conjunto finito de la forma
{q0 7 0 , q1 7 1 , . . . , qn 7 n }
indicando que la proposicin i est asociada a la variable proposicional qi (0
i n) y cualquier otra variable est asociada a s misma cuando esta no aparece
en la lista q0 , . . . , qn .
Un sustitucin F puede ser aplicada a una proposicin con el propsito de
obtener una nueva proposicin F (). En la proposicin F (), algunas variables p
de son sustitudas por F (p). La aplicacin de una sustitucin a una proposicin
recibe el nombre de sustitucin textual.
Definicin 4.7
Sea una proposicin y F = {q0 7 0 , . . . , qn 7 n } una sustitucin. La sustitucin
textual de F en , denotada como F (), se define inductivamente para toda subproposicin
de de la siguiente forma:
1. F (p) = F (p), si p {q0 , . . . , qn }
2. F (p) = p, si p
/ {q0 , . . . , qn }
3. F (true) = true
4. F (false) = false
5. F (()) = (F ())
6. F (( )) = (F () F ( )), si {, 6, , , , }
65
(caso 6)
(caso )
(caso q
/ {p, r, s})
(caso )
66
(Ax2): (( ) ( ))
(Ax3): (( true) )
(Ax4): (( ( )) (( ) ))
(Ax5): (( ) ( ))
(Ax6): (( false) )
(Ax7): (( ) )
(Ax8): (( ( )) (( ) ( )))
( )
Ecuanimidad
( )
Leibniz
([p := ] [p := ])
67
El sistema DS cuenta con dos reglas de inferencia. La regla Ecuanimidad representa el hecho de que si hay un teorema en DS, digamos , y se puede demostrar en
DS que es equivalente a , entonces necesariamente es un teorema de DS. La
regla Leibniz determina que al hacer cambio de iguales por iguales en una proposicin, las proposiciones resultantes son equivalentes. En el caso de la regla Leibniz,
fjese en que la variable proposicional p puede no ser parte de : en ese caso cada
una de las sustituciones textuales [p := ] y [p := ] en la conclusin de la regla
trivialmente son .
Habiendo completado la definicin del sistema DS, la definicin de demostracin
en DS y de la relacin `DS de demostrabiliad en DS son heredadas automticamente
de la Definicin 1.10 (Seccin 1.3).
Teorema 4.12
Para cualquier proposicin :
1. `DS true
2. `DS (( ) true)
3. `DS ( )
(Ax3)
(Ax3)
3. (true true)
(Ecuanimidad 2 y 1)
4. true
(Ecuanimidad 3 y 2).
(Ax3)
(Ax2)
3. ( ( true))
(Ecuanimidad 1 y 2)
4. (( ( true)) (( ) true))
(Ax1)
5. (( ) true)
(Ecuanimidad 3 y 4).
68
Ejercicios
1. Demuestre que H6 = H H , en donde denota la composicin funcional:
(H H )(x, y) = H (H (x, y)) para x, y B.
2. Considere la sustitucin F = {p 7 (p q), q 7 (r s), r 7 false}. Determine
la proposicin correspondiente a la sustitucin textual de F en cada una de las
siguientes proposiciones:
a) p
b) (p r)
c) ((p (q)) r)
d ) ((p q) ((p) (q)))
e) (p (q p))
f ) ((p r) (p q))
g) (((r (r (p s))) (((p q) (r (r))))))
3. Para cada una de las siguientes proposiciones encuentre una sustitucin F tal
que la proposicin resultante de la sustitucin textual bajo F sea una tautologa:
a) p
b) (p r)
c) ((p (q)) r)
d ) ((p q) ((p) (q)))
e) (p (q p))
f ) ((p r) (p q))
g) (((r (r (p s))) (((p q) (r (r))))))
4. Para cada uno de los siguientes casos encuentre proposiciones concretas , ,
tales que:
a) ([q := ])[p := ] 6= ([p := ])[q := ].
b) [p, q := , ] 6= ([p := ])[q := ].
5. Demuestre que cada uno de los axiomas de DS es una tautologa.
6. Demuestre que si |= y |= ( ), entonces |= .
7. Demuestre que si |= ( ), entonces |= ([p := ] [p := ]).
8. Encuentre proposiciones concretas , , para las cuales |= ([p := ] [p := ])
pero no |= ( ).
9. Demuestre el Teorema 4.12.3 (ayuda: use las demostraciones de los teoremas 4.12.1 y 4.12.2).
4.2.
69
( )
.. ..
. .
..
.
n.
( )
n + 1.
( )
.. ..
. .
..
.
n + m. ( )
( )
n + m + 1. (( ) ( ))
(Ax2)
n + m + 2. ( )
(Ecuanimidad n + m y n + m + 1)
n + m + 3.
(Ecuanimidad n y n + m + 2).
Nota 4.14
El Metateorema 4.13 justifica la correccin de las siguientes reglas de inferencia:
( )
Ecuanimidad*
( )
Leibniz*
([p := ] [p := ])
70
Nota 4.16
El Metateorema 1 justifica la correccin de las siguientes reglas de inferencia:
( )
( )
Transitividad
( )
( true)
Identidad
Identidad
( true)
71
( )
n. ( ( ))
( )
n + 1. (( ( )) (( ) ))
(Ax1)
n + 2. (( ) )
(Ecuanimidad n y n + 1).
( )
n. (( ) )
( )
n + 1. (( ( )) (( ) ))
(Ax2)
n + 2. ( ( ))
(Ecuanimidad* n y n + 1).
Nota 4.18
El Metateorema 4.17 justifica la correccin de las siguientes reglas de inferencia:
( ( ))
Asociatividad
(( ) )
(( ) )
Asociatividad
( ( ))
( )
Conmutatividad
( )
Las reglas de inferencia introducidas en esta seccin ahora son parte de DS.
Recuerde que estas reglas no le otorgan ms poder deductivo a DS, simplemente
facilitan la obtencin de teoremas en el sistema formal.
Ejercicios
1. Demuestre el Metateorema 4.13.2.
2. Demuestre:
a) El Metateorema 4.15.1.
b) El Metateorema 4.15.2.
3. Demuestre el Metateorema 4.17.2.
4. Utilice las reglas de inferencia introducidas en esta seccin para simplificar las
demostraciones presentadas en la Seccin 4.1.
72
4.3.
La negacin y la discrepancia
La negacin es por naturaleza el operador de complemento de la lgica. La discrepancia es el operador opuesto de la equivalencia. En DS se modela el complemento
lgico de una proposicin haciendo esta equivalente a false (Ax9). La discrepancia,
al ser el inverso de la equivalencia, se puede definir al negar uno de sus operandos
(Ax10). Como se ver ms adelante en esta seccin por medio de un teorema, no
importa cul de los dos operandos se niegue en la definicin de 6 pues las dos
proposiciones resultantes son equivalentes.
A continuacin se presentan algunas propiedades de la negacin.
Teorema 4.20
Para cualesquiera proposiciones y de DS:
1. `DS (false (true))
2. `DS ((false) true)
3. `DS (false)
4. `DS ((( )) (() ))
5. `DS ((() ) ( ()))
73
6. `DS ((()) )
7. `DS (( ()) false)
Las constantes true y false son opuestos el uno del otro (teoremas 4.20.1 y 4.20.2), y
entonces, naturalmente, la negacin de false es un teorema de DS (Teorema 4.20.3).
La negacin distribuye sobre la equivalencia (Teorema 4.20.4) y alterna entre los
operandos de una equivalencia (Teorema 4.20.5). Este ltimo teorema justifica la
afirmacin hecha previamente acerca de la definicin de 6: desde el punto de vista
deductivo resulta indiferente cul de los operandos de la equivalencia sea negado. El Teorema 4.20.6 establece la propiedad de la doble negacin: la negacin se
cancela con ella misma. Finalmente, el Teorema 4.20.7 caracteriza la contradiccin
lgica en trminos de la equivalencia y la negacin. A continuacin se presentan
demostraciones de algunos de estos teoremas.
Demostracin. Para (1):
1. ((true) (true false))
(Ax9)
(Asociatividad 1)
(Conmutatividad 2)
(Ax3)
5. (false (true))
(Transitividad 3,4).
Para (2):
1. ((false) (false false))
(Ax9)
3. ((false) true)
(Transitividad 1,2).
Para (4):
1. ((( )) (( ) false))
(Ax9)
2. (( ) ( ))
(Ax2)
(Leibniz 2)
(Ax1)
5. (() ( false))
(Ax9)
6. (( ( false)) ( ()))
(Leibniz* 5)
7. (( ()) (() ))
(Ax2)
8. ((( )) (() ))
(Transitividad 1,3,4,6,7).
74
(Ax9)
(Teorema 4.20.5)
3. ((false) true)
(Teorema 4.20.2)
4. (( (false)) ( true))
(Leibniz 3)
5. ((()) ( true))
(Transitividad 1,2,4)
6. (((()) ) true)
(Asociatividad 5)
7. ((()) )
(Identidad 6).
Demostraciones para los dems teoremas se proponen como ejercicios para el lector.
Las demostraciones presentadas anteriormente sirven para ilustrar el primer uso de
algunas reglas de inferencia de DS y para introducir algunas convenciones:
En la demostracin del Teorema 4.20.1 se usan las reglas estructurales de asociatividad y conmutatividad de la equivalencia presentadas en la Seccin 4.2.
La demostracin presentada del Teorema 4.20.2 no es precisamente una demostracin en el sentido estricto de la definicin de DS. En particular, el rengln
2 viola la definicin de demostracin porque la proposicin que all aparece
no es una axioma ni tampoco se obtiene usando una regla de inferencia con
premisas que previamente aparecen en dicha demostracin. Sin embargo, usar
teoremas en los renglones de una demostracin es una libertad que se permite
para simplicar el trabajo deductivo. Estas simplificaciones son aceptadas bajo
el siguiente acuerdo: dicho teorema debe ser anterior y estar demostrado; adems se debe indicar cmo reemplazar las proposiciones del teorema usado en
la proposicin que aparece en la demostracin actual. El efecto formal de esta
convencin es el de copiar y pegar una demostracin del teorema usado en la
demostracin actual con las proposiciones reemplazadas adecuadamente. Por
ejemplo, en el rengln 2 de la demostracin del Teorema 4.20.2, se usa el Teorema 4.12.2 (i.e, (( ) true)) en donde se reemplaza con false. Recuerde
que toda instancia de un axioma es un axioma. Tambin, toda instancia de un
teorema es a su vez un teorema (Ejercicio 9, Seccin 4.1).
La regla Leibniz se utiliza en el rengln 3 de la demostracin del Teorema 4.20.4. Note que esta deduccin corresponde a la siguiente inferencia:
(( ) ( ))
Leibniz
((p false)[p := ( )] (p false)[p := ( )])
Finalmente, observe que la regla Transitividad es usada en varias de las
demostraciones. En particular, se usa en el rengln 8 de la demostracin del
Teorema 4.20.4 con la explicacin Transitividad 1,3,4,6,7. Esta es una convenicin para usar la transitividad de la equivalencia en cadena o cascada (i.e.,
transitivamente). Por ejemplo, la secuencia 1,3,4,6,7 en dicha leyenda indica
75
que se aplica Transitividad con premisas en los renglones 1 y 3, la proposicin resultante se usa como premisa junto con la proposicin en el rengln 4
para otra vez aplicar la regla, y as sucesivamente.
La discrepancia es un operador muy conocido y usado en informtica, pero bajo
otro nombre: xor. Su interpretacin es la de o exclusivo. En el lenguaje cotidiano,
la discrepancia elimina la ambiguedad de la disyuncin cuando se desea enunciar una
situacin en la cual exactamente uno de sus operandos es cierto (pero no ambos).
En informtica, ms precisamente en criptografa, la discrepancia es utilizada para
obtener un simple pero efectivo mtodo de ciframiento y desciframiento conocido
como ciframiento xor (en ingls, xor cypher). Este mtodo est basado en el
hecho de que la discrepancia puede interpretarse como la suma de bits modulo
2 en donde true corresponde a 1 y false corresponde a 0: 0 + 0 = 0 = 1 + 1 y
0 + 1 = 1 = 1 + 0. El uso de la discrepancia en criptografa se ilustra con un ejemplo
al final de esta seccin.
A continuacin se presentan algunas propiedades de la discrepancia.
Teorema 4.21
Para cualesquiera proposiciones , y de DS:
1. `DS (( 6 ( 6 )) (( 6 ) 6 ))
2. `DS (( 6 ) ( 6 ))
3. `DS (( 6 false) )
4. `DS (( 6 ) false)
5. `DS ((( 6 ) 6 ) )
La discrepancia es asociativa, conmutativa y tiene elemento identidad false (teoremas 4.21.1-3). La discrepancia es irreflexiva (Teorema 4.21.4) y acepta una ley
de cancelacin (Teorema 4.21.5). A continuacin se presentan demostraciones de
algunos de estos teoremas.
Demostracin. Para (4):
1. (( 6 ) (() ))
(Ax10)
2. ((() ) ( ()))
(Ax2)
3. (( ()) false)
(Teorema 4.20.7)
4. (( 6 ) false)
(Transitividad 1,2,3).
Demostraciones para los dems teoremas se proponen como ejercicios para el lector.
4.3.1. Ciframiento de texto con xor. Como se explic al inicio de esta seccin, en informtica hay (y se usa) un mtodo de ciframiento basado en la discrepancia. En particular, este mtodo est basado en las propiedades de la discrepancia
enunciadas en los teoremas 4.21.1-5. La idea es que dada una cadena texto t y una
76
01101001
01101011
01101001
10011010
10011000
10011010.
Para revertir el proceso se repite la misma operacin bit a bit usando como operandos el texto cifrado y la llave de ciframiento originalmente usada:
10100100
10011010
10011000
10011010
Nota 4.22
El ciframiento basado en xor es muy usado gracias a su simplicidad y facilidad de
implementacin. La siguiente funcin xor_cypher en el lenguaje de programacin
Python 3, cifra una cadena de texto con una llave (tambin representada como
cadena) usando xor con el mtodo descrito anteriormente:
1
2
3
4
4.4. La disyuncin
77
Ejercicios
1. Demuestre que el axioma (Ax9) es una tautologa.
2. Demuestre que el axioma (Ax10) es una tautologa.
3. Ilustre con una inferencia el uso de la regla Leibniz* en el rengln 6 de la
demostracin del Teorema 4.20.4.
4. Demuestre el Teorema 4.20.3.
5. Demuestre el Teorema 4.20.5.
6. Demuestre el Teorema 4.20.7.
7. Demuestre el Teorema 4.21.1 (solo si tiene mucho tiempo disponible).
8. Demuestre el Teorema 4.21.2.
9. Demuestre el Teorema 4.21.3.
10. Demuestre el Teorema 4.21.5.
11. Investigue acerca de los siguientes operadores de Python 3, explique su uso e
ilstrelo con ejemplos:
^
zip
ord
chr
join
4.4.
La disyuncin
La disyuncin es uno de los operadores bsicos del sistema formal DS, junto
con las constantes true y false, y la equivalencia . Su interpretacin es la del o
inclusivo, es decir, es verdadera cuando al menos uno de sus operandos es verdadero.
78
A continuacin se recuerdan los axiomas de DS que estn relacionados directamente con la disyuncin.
Definicin 4.23
Sean , , proposiciones de DS. El conjunto de axiomas de DS incluye los siguientes
axiomas relacionados directamente con la disyuncin:
(Ax4): (( ( )) (( ) ))
(Ax5): (( ) ( ))
(Ax6): (( false) )
(Ax7): (( ) )
(Ax8): (( ( )) (( ) ( )))
Teorema 4.24
Para cualesquiera proposiciones y de DS:
1. `DS ( ())
2. `DS (( true) true)
3. `DS ( true)
4. `DS (( ) (( ()) ))
La disyuncin satisface la ley del tercero excludo, es decir, bajo cualquier valuacin una proposicin o su negacin son verdaderas (Teorema 4.24.1). La disyuncin
tiene elemento anulador true (teoremas 4.24.2-3). El Teorema 4.24.4 es una propiedad de caracterizacin extraa que es til a la hora de simplificar algunas demostraciones que involucran a la disyuncin. A continuacin se presentan demostraciones
de algunos de estos teoremas.
4.4. La disyuncin
79
(Ax9)
2. (( ()) ( ( false)))
(Leibniz 1)
(Ax7)
(Leibniz 4)
6. (( false) )
(Ax6)
7. (( ( false)) ( ))
(Leibniz 6)
8. (( ) true)
(Teorema 4.12.2)
9. (( ()) true)
(Transitividad 2,3,5,7,8)
10. ( ())
(Identidad).
Demostraciones para los dems teoremas se proponen como ejercicios para el lector.
Histricamente, la disyuncin ha desempeando un papel protagnico en la
lgica y en su estudio, pues este conectivo lgico sirve para explicar la diferencia
entre dos tipos de lgicas: la lgica clsica y la lgica intuicionista (o constructivista). Desde el punto de vista filosfico, la lgica clsica puede verse como una
versin Platnica de la lgica en donde la verdad de una proposicin siempre existe
y un observador nicamente puede encontrar una demostracin directa o indirecta de ella. La lgica intuicionista es diferente en este sentido dado que la verdad
de una proposicin nicamente es aceptada cuando se construye una demostracin
directa de ella; en el contexto de la lgica intuicionista, la verdad no existe sin
una demostracin directa. Una ejemplo de una demostracin directa es cualquier
demostracin de un teorema de DS que se haya hecho hasta ahora. Un ejemplo de
una demostracin indirecta de una proposicin es una demostracin por contradiccin: si se supone que () es cierto, entonces se llega a un absurdo. Y es as
como surge la siguiente pregunta: para demostrar una propiedad basta con (i)
exhibir una demostracin para o (ii) justificar la imposibilidad de la ausencia de
una demostracin para ? Los intuicionistas solo aceptan como razonable la situacin (i), mientras que los dems aceptan tanto (i) como (ii). El sistema DS es un
sistema lgico clsico. En este sentido, en DS se puede demostrar como teorema
una proposicin ya bien sea dando una demostracin directa o una indirecta de
ella. Como sistema lgico clsico que es, DS est caracterizado por el teorema del
tercero excludo (Teorema 4.24.1).
A continuacin se presenta
una demostracin no constructiva de un hecho muy
conocido en matemticas: 2 es irracional. Un nmero real x es irracional sii x no
puede expresarse como una fraccin ab con a, b Z y b 6= 0.
80
Ejemplo 4.3
2 es irracional.
con b 6= 0 tales que x = ab . Como 2 > 0, se puede suponer que a > 0 y b > 0.
Adems, siempre se puede suponer que la fraccin ab es irreducible (i.e., a y b no
tiene factores en comn aparte de 1). Observe entonces lo siguiente:
a
a2
2=
sii 2 = 2 sii 2b2 = a2 .
b
b
Esto indica que a es par (Ejercicio 7), es decir, a = 2c para algn c N (Ejercicio 6).
Entonces se tiene:
2b2 = a2
sii b2 = 2c2 .
p: 2 es irracional.
La demostracin del Ejemplo 4.3 se justifica en DS de la siguiente forma:
1. (p (p))
2. ((p))
(Teorema 4.24.1)
( 2 no es racional)
(Ax9)
4. ((p) false)
(Ecuanimidad 2,3)
(Leibniz 4)
6. (p false)
(Ecuanimidad 1,5)
7. ((p false) p)
(Ax6)
8.
(Ecuanimidad 6,7).
4.4. La disyuncin
81
Ejercicios
1. Demuestre el Teorema 4.24.2.
2. Demuestre el Teorema 4.24.3.
3. Demuestre el Teorema 4.24.4.
4. Apelando a la interpretacin formal de los conectivos lgicos, es decir, basndose en las funciones Htrue , Hfalse , . . . de la Seccin 4.1, identifique cul de los
operadores lgicos de DS determina que false la proposicin mnima entre todas
las proposiciones de DS. Justifique su respuesta.
5. Apelando a la interpretacin formal de los conectivos lgicos, es decir, basndose en las funciones Htrue , Hfalse , . . . de la Seccin 4.1, identifique cul de los
conectivos lgicos de DS es un rden parcial. Un conectivo lgico binario es
un orden parcial sii es reflexivo (i.e., v( ) = T para cualquier valuacin
v de ), transitivo (i.e., si v( ) = T y v( ) = T, entonces v( ) = T
para cualquier valuacin v de , , ) y antisimtrico (i.e., si v( ) = T y
v( ) = T, entonces v( ) = T para cualquier valuacin v de , ).
6. Demuestre que si a N y a es par, entonces hay un c N tal que a = 2c.
7. Demuestre que si a N y a2 es par, entonces a es par.
()
Silogismo disyuntivo
82
(() )
Corte
( )
Debilitamiento
( )
Explique brevemente el significado de la regla Debilitamiento, de un ejemplo
de su uso y demuestre que es correcta.
13. Considere la siguiente regla de inferencia:
( )
Debilitamiento?
4.5.
Intermezzo: derivaciones
Note que una derivacin es una secuencia finita (y no vaca) de proposiciones en DS.
En particular, se acepta como derivacin una secuencia con una nica proposicin.
La Definicin 4.25 no asocia a una derivacin relacin alguna con una demostracin.
La relacin que existe entre estos dos objetos de DS es establecida en el Metateorema 4.26.
83
Metateorema 4.26
Sea 0 , 1 , . . . , n una derivacin en DS. Entonces se tiene `DS (0 n ).
..
.
h ... i
n1
84
Ejemplo 4.5
A continuacin se presenta un ejemplo de una derivacin. Se sugiere al lector comparar esta derivacin con la demostracin inicialmente presentada del Teorema 4.20.1.
(true)
h Ax9 i
(true false)
h conmutatividad de i
(false true)
h Ax3 i
false
Por el Metateorema 4.26 se obtiene `DS ((true) false). Por la regla Conmutatividad se concluye `DS (false (true)).
Ejercicios
1. Investigue el significado y el orgen de la palabra intermezzo. Ilustre el uso de
esta palabra con un par de ejemplos.
2. Considere una proposicin y la siguiente argumentacin:
La secuencia unitaria es una derivacin. Entonces, por el Metateorema 4.26 se tiene `DS .
Por qu esta argumentacin es incorrecta? Justifique su respuesta.
3. Demuestre que si una secuencia 0 , . . . , n de proposiciones en DS es una demostracin, entonces es una derivacin.
4. Formule un ejemplo en donde una secuencia de proposiciones sea una derivacin
pero no una demostracin.
5. Considere una secuencia 0 , . . . , n de proposiciones en DS. Demuestre que las
siguientes dos afirmaciones son equivalentes:
0 , . . . , n es una derivacin
n , . . . , 0 es una derivacin
6. Considere una secuencia 0 , . . . , n de proposiciones en DS y las siguientes
afirmaciones:
0 , . . . , n es una derivacin
`DS (0 n )
Justifique por qu estas dos afirmaciones no son equivalentes.
7. Siguiendo la demostracin del Metateorema 4.26, obtenga la demostracin en
DS correspondiente a la derivacin en el Ejemplo 4.5. En otras palabras, compile
dicha derivacin en una demostracin de DS.
4.6. La conjuncin
4.6.
85
La conjuncin
Definicin 4.28
Sean y proposiciones de DS. El siguiente axioma de DS define la conjuncin:
(Ax11): (( ) ( ( ( ))))
Teorema 4.29
Para cualesquiera proposiciones , , de DS:
1. `DS (( ( )) (( ) ))
2. `DS (( ) ( ))
3. `DS (( true) )
4. `DS (( false) false)
5. `DS (( ) )
86
h Ax11 i
( ( ( )))
h conmutatividad de i
( ( ( )))
h asociatividad de i
(( ) ( ))
h conmutatividad de i
(( ) ( ))
h asociatividad de i
( ( ( )))
h Ax11 i
( )
Demostraciones para los dems teoremas se proponen como ejercicios para el lector.
Fjese que en la derivacin del Teorema 4.29.2 no se hace referencia alguna a las
reglas de inferencia de DS en ninguna de las explicaciones. Esta ser una prctica
ms comn a medida que se avance en este texto con el obejtivo de aprovechar el
nivel de abstraccin que brindan las derivaciones y tambin simplificar su escritura.
Sin embargo, se alerta al lector para que siempre tenga en cuenta qu regla de
inferencia se usa en cada paso de una derivacin.
A continuacin se enuncian algunas propiedades que relacionan la conjuncin
con otros conectivos lgicos.
Teorema 4.30
Para cualesquiera proposiciones , , de DS:
1. `DS (( ()) false)
2. `DS ((( )) (() ()))
3. `DS ((( )) (() ()))
4. `DS (( ( )) ((( ) ( )) ))
5. `DS (( ( 6 )) (( ) 6 ( )))
6. `DS (( ( )) (( ) ( )))
7. `DS (( ( )) (( ) ( )))
4.6. La conjuncin
87
establecen cmo la negacin distribuye sobre la conjuncin y la disyuncin, respectivamente. La conjuncin pseudo-distribuye sobre la equivalencia (Teorema 4.30.4)
y distribuye sobre la discrepancia (Teorema 4.30.5). La conjuncin y la disyuncin
distribuyen mtuamente una sobre la otra (teoremas 4.30.6-7). Demostraciones de
estos teoremas se proponen como ejercicios para el lector.
Desde el punto de vista computacional, cuando la conjuncin es interpretada
como un operador binario sobre bits (es decir, sobre los valores 0 y 1 en donde 0
corresponde a false y 1 a true), la conjuncin no es otra cosa ms que el operador
de mnimo: el bit 0 es el mnimo entre 0 y 1. Traduciendo esta interpretacin al
sistema formal DS, se puede decir que la conjuncin completa el order estricto para
las constantes Booleanas introducido al final de la Seccin 4.4: true es el mximo
entre false y true, y false es el mnimo entre false y true. En el mismo sentido en
que la disyuncin establece a true como el mximo entre todas las proposiciones de
DS, la conjuncin establece a false como el mnimo entre todas las proposiciones
de DS (Teorema 4.29.4).
Ejercicios
1. Demuestre que el axioma (Ax11) es una tautologa.
2. Demuestre el Teorema 4.29.1.
3. Demuestre el Teorema 4.29.3.
4. Demuestre el Teorema 4.29.4.
5. Demuestre el Teorema 4.29.5.
6. Demuestre la siguiente versin de la regla dorada para la disyuncin y la
discrepancia:
`DS (( ) ( 6 ( 6 ( )))).
7. Demuestre el Teorema 4.30.1.
8. Demuestre el Teorema 4.30.2.
9. Demuestre el Teorema 4.30.3.
10. Demuestre el Teorema 4.30.4.
11. Demuestre el Teorema 4.30.5.
12. Demuestre el Teorema 4.30.6.
13. Demuestre el Teorema 4.30.7.
14. Investigue cules son los operadores de conjuncin lgica y conjuncin entre
bits de Python. De ejemplos del uso de cada uno de ellos.
15. Considere la siguiente regla de inferencia:
( )
Debilitamiento
88
Unin
( )
Explique brevemente el significado de la regla Unin, de un ejemplo de su uso
y demuestre que es correcta.
4.7.
La implicacin y la consecuencia
89
y el bit del consecuente es el bit del consecuente. Esto es compatible con la semntica
de la implicacin: es falsa nicamnete cuando el antecedente es verdadero y el
consecuenta falso, es decir, cuando el mximo entre el antecedente y el consecuente
no es el consecuente.
La primera cuestin a observar es que la implicacin puede ser definida de varias formas. En este sentido, los primeros teoremas acerca de la implicacin son
propiedades que permiten reescribir la implicacin de manera alternativa y complementaria a aquella indicada por el axioma (Ax12).
Teorema 4.33
Para cualesquiera proposiciones y de DS:
1. `DS (( ) (() ))
2. `DS (( ) (( ) ))
h definicin de i
(( false) )
h conmutatividad de i
( ( false))
h distribucin de sobre i
(( ) ( false))
h identidad de i
(( ) )
h conmutatividad de i
(( ) )
h definicin de i
( )
La demostracin para (2) se propone como ejercicio para el lector.
90
Teorema 4.34
Para cualquier proposicin de DS:
1. `DS ( true)
2. `DS (false )
3. `DS ((true ) )
4. `DS (( false) ())
91
h conmutatividad de i
(() )
92
Teorema 4.40
Para cualesquiera proposiciones y de DS:
1. `DS ( ( ))
2. `DS (( ) )
3. `DS (( ) ( ))
93
4. `DS ((( ) ( )) ( ))
5. `DS ((( ) ) (( ) ( )))
6. `DS (( ( )) (( ) ( )))
Los teoremas 4.40.1-4 son caracterizaciones tpicas de fortalecimientos y debilitamientos. Los teoremas 4.40.5-6 son propiedades de anlisis de casos. Por ejemplo, el
Teorema 4.40.5 indica que si en el antecedente de una implicacin hay una disyuncin, entonces dicha implicacin es equivalente a la conjuncin de dos implicaciones
ms sencillas, una por cada operando de la disyuncin y con el mismo consecuente de la implicacin inicial. Demostraciones de estos teoremas se proponen como
ejercicios para el lector.
Finalmente, se presentan algunos teoremas acerca de la transitividad de la equivalencia y la implicacin. En particular, se establece que la equivalencia es transitiva
(hecho que en este punto se conoce pero que no ha sido caracterizado dentro de
DS). Tambin se identifica cmo la transitividad de la implicacin conmuta con la
transitividad de la equivalencia y viceversa.
Teorema 4.41
Para cualesquiera proposiciones , , de DS:
1. `DS ((( ) ( )) ( ))
2. `DS ((( ) ( )) ( ))
3. `DS ((( ) ( )) ( ))
Ejercicios
1. Demuestre que el axioma (Ax12) es una tautologa.
2. Demuestre que el axioma (Ax13) es una tautologa.
3. Demuestre el Teorema 4.33.2.
4. Demuestre el Teorema 4.34.1.
5. Demuestre el Teorema 4.34.2.
6. Demuestre el Teorema 4.34.3.
7. Demuestre el Teorema 4.34.4.
8. Demuestre el Teorema 4.35.1.
94
c)
d)
e)
f)
95
(( ) (( ) ( )))
(( ) (( ) ( )))
(( ) (( ) ( )))
(( ) (( ) ( )))
( )
Modus Ponens
96
Una particularidad de Principia Mathematica es que su contenido est agrupado en prrafos enumerados. Investigue y transcriba al castellano el prrafo (1)
del Volmen 1 acerca de proposiciones elementales.
48. El sistema formal L, propuesto por Gottlob Frege, usa los conectivos {, }.
Para , , proposiciones de L, los axiomas de L estn dados por el siguiente
esquema axiomtico:
L1: ( ( ))
L2: (( ( )) (( ) ( )))
L3: ((() ()) ( ))
El sistema L tiene como nica regla de inferencia Modus Ponens. Lleve a cabo
los numerales (a)(d) del Ejercicio 46 para L en lugar de PM.
49. El sistema formal R, propuesto por Barkley Rosser, usa los conectivos {, , }.
Para , , proposiciones de R, los axiomas de R estn dados por el siguiente
esquema axiomtico:
R1: ( ( ))
R2: (( ) )
R3: (( ) ((( )) (( ))))
El sistema R tiene como nica regla de inferencia Modus Ponens. Lleve a
cabo los numerales (a)(d) del Ejercicio 46 para R en lugar de PM.
50. El sistema formal LUK, propuesto por Jan ukasiewicz (pronunciado vu-cache-vich), usa los conectivos {, }. Para , , proposiciones de LUK, los
axiomas de LUK estn dados por el siguiente esquema axiomtico:
LU K1: (( ) (( ) ( )))
LU K2: ((() ) )
LU K3: ( (() ))
El sistema LUK tiene como nica regla de inferencia Modus Ponens. Lleve a
cabo los numerales (a)(d) del Ejercicio 46 para LUK en lugar de PM.
51. El sistema formal KA, propuesto por Stig Kanger, usa los conectivos {, }.
Para , , proposiciones de KA, los axiomas de KA estn dados por el siguiente
esquema axiomtico:
KA1: ( ( ))
KA2: (( ) (( ) ( )))
KA3: (( ()) ( ()))
KA4: ((()) (() ))
El sistema KA tiene como nica regla de inferencia Modus Ponens y es un
sistema proposicional de la lgica intuicionista. Lleve a cabo los numerales (a)
(c) del Ejercicio 46 para KA en lugar de PM.
Captulo 5
Tcnicas de razonamiento y
demostracin
97
98
5.1.
Eliminacin de parntesis
El lector posiblemente ha notado que algunas frmulas de DS tienen una cantidad abrumadora de parntesis; sin ellos, muchas expresiones son ambigas en el
sentido que una expresin puede tener ms de un significado. Esta corta seccin
establece algunas convenciones para simplificar la escritura de proposiciones al permitir obviar parntesis en muchos casos.
Los parntesis son escenciales cuando una mquina es programada para reconocer una frmula o, en general, una expresin como un programa en un lenguaje
de programacin. En el caso del lenguaje de programacin LISP (cuyo nombre proviene del ingls LISt Processing), famoso por el uso extensivo de parntesis en sus
expresiones, algunos creen que el nombre del lenguaje realmente abrevia lots of
unnecessary stupid parenthesis. En contraste, si se tiene suficiente cuidado, para
un humano no es necesario el uso extensivo de parntesis, an para leer cdigo
LISP. En el caso de una proposicin, por ejemplo, algunos parntesis pueden ser
eliminados cuando dicha omisin no genera ambigedad, es decir, cuando exista
una nica forma de interpretar la proposicin resultante de eliminar los parntesis.
Una forma de evitar algunos parntesis es por medio de convenciones sintcticas
sobre los conectivos lgicos. Al asignar una precedencia a cada uno de los conectivos
lgicos de DS es posibe evitar la escritura de algunos parntesis en las proposiciones.
Nota 5.1
Se adoptan las siguientes convenciones sobre la precedencia de los conectivos lgicos
de DS:
Las constantes true y false tienen ms precedencia que .
El conectivo tiene ms precedencia que and .
Los conectivos y tienen ms precedencia que y .
Los conectivos y tienen ms precedencia que y 6.
99
Ejemplo 5.1
Dado que la disyuncin tiene ms precedencia que la implicacin, la proposicin
((p q) r) se escribe de forma simplificada como p q r. De manera similar,
la expresin ((p q) r) se escribe como (p q) r. Sin embargo, esta combinacin
de conjuncin y disyuncin no se puede escribir como p q r porque esta ltima
expresin es ambiga: (p q) r y p (q r) tienen interpretaciones distintas.
Ejercicios
1. Elimine tantos parntesis como sea posible de la siguientes proposiciones sin
introducir ambigedad:
a) (( ( )) (( ) ))
b) (( ) ( ))
c) (( false) )
d ) (( ) )
e) (( ( )) (( ) ( )))
f ) (() ( false))
g) (false (true))
h) ((false) true)
i ) (false)
100
j)
k)
l)
m)
n)
)
o)
p)
q)
r)
s)
t)
u)
v)
w)
x)
y)
z)
((( )) (() ))
((() ) ( ()))
((()) )
(( ()) false)
(( ) (( ()) ))
(( ) ( ( ( ))))
(( ) )
(( ()) false)
((( )) (() ()))
(( ( )) (( ) ( )))
(( ( )) (( ) ( )))
(( ) (( ) ))
(( ) ( ))
(( false) ())
(( ( )) (( ) ( )))
(( ( )) (( ) ( )))
(( ( )) ( ))
((( ) ( )) ( ))
5.2.
Tcnicas bsicas
101
5.2.1. Reduccin a true. Considere la situacin en la cual se quiere demostrar que una proposicin es teorema. La tcnica de reduccin a true consiste en
construir una derivacin de la forma
, . . . , true.
Esta derivacin establece `DS true por el Metateorema 4.26. Dado que todo
teorema de DS es equivalente a true (Metateorema 4.15.2), se concluye `DS .
Ejemplo 5.3
Considere el Teorema 4.38.1 de la reflexividad de la implicacin; el objetivo es
demostrar `DS . Se propone la siguiente derivacin:
h tercero excludo i
true
Dado que es equivalente a true, se establece `DS .
La tcnica de reduccin a true tiene ventajas y desventajas. Una ventaja es la claridad en su mtodo: reducir a true por medio de simplificaciones que provienen de
axiomas o teoremas previamente demostrados. Otra ventaja es que la informacin
de la proposicin a ser demostrada est disponible en cualquier paso de derivacin,
lo cual potencia las posibilidades de simplificacin. En contraste, una desventaja de
la tcnica de reduccin a true es que la derivacin resultante puede ser verbosa dado
que en cada paso de la derivacin se puede repetir una y otra vez una misma subproposicin. En este sentido, es preferible contar con una estrategia de demostracin,
an cuando esto demande ms tiempo antes de iniciar la demostracin.
5.2.2. Trnsito. Dado que la equivalencia es un conectivo lgico importante
en DS, en muchas ocasiones el objetivo de una demostracin es una equivalencia
lgica. En realidad, cualquier demostracin de una proposicin en DS puede
plantearse como una demostracin de true porque true es la identidad de la
equivalencia.
Para demostrar que una equivalencia de la forma es teorema de DS, tal
y como su nombre lo indica, la tcnica de trnsito tiene como objetivo construr
una derivacin de la forma
, . . . , .
El Metateorema 4.26 establece entonces que `DS . Cuando una de las proposiciones o es la constante true, entonces las tcnicas de reduccin a true y
trnsito coinciden. Ejemplos de derivaciones que usan la tcnica de trnsito incluyen
las demostraciones del Teorema 4.20.1 y del Teorema 4.29.2, entre otros.
102
103
Ejercicios
1. Demuestre que si 0 , . . . , n , true es una derivacin por reduccin a true, entonces 0 , . . . , n es una demostracin de DS.
2. Demuestre el Teorema 4.29.1 por reduccin a true.
3. Demuestre el Teorema 4.29.1 por trnsito.
4. Demuestre el Teorema 4.29.1 usando lemas.
5.3.
Derivaciones relajadas
Hasta ahora, la tcnica de reduccin a true (Seccin 5.2.1) es la nica alternativa para demostrar que una implicacin lgica es teorema. Esta seccin presenta el
concepto de derivacin relajada, una extensin del concepto de derivacin. La utilidad de una derivacin relajada es que permite demostraciones de implicaciones y
consecuencias lgicas por trnsito desde el antecedente al consecuente (y viceversa).
Es importante entender por qu una derivacin no es til, en general, para derivar por trnsito una implicacin lgica. Por definicin, en una derivacin cualquier
par de proposiciones consecutivas son equivalentes; de esta forma, apelando a la
transitividad de la equivalencia, la primera y ltima proposiciones en una derivacin son equivalentes. Por tanto, cuando dos proposiciones no son equivalentes, es
imposible que haya una derivacin por trnsito de una a la otra. Por ejemplo, es
imposible que exista una derivacin por trnsito de p q a p q, a pesar de que
estas proposiciones estn relacionadas por la implicacin lgica, porque estas no
son equivalentes.
En una derivacin relajada se relajan los requisitos deductivos de una derivacin para permitir pasos deductivos en donde es suficiente preservar la implicacin
lgica. De esta forma, y apelando a la transitividad de la implicacin, con una
derivacin relajada se puede demostrar por trnsito que p q implica p q (o,
alternativamente, que p q es consecuencia lgica de p q).
Definicin 5.4
Una secuencia de proposiciones 0 , . . . , n de DS es:
1. Una derivacin (relajada) de debilitamiento si y solo si `DS k1 k para
cualquier 0 < k n.
2. Una derivacin (relajada) de fortalecimiento si y solo si `DS k1 k para
cualquier 0 < k n.
104
Metateorema 5.5
Sean 0 , . . . , n proposiciones de DS.
1. Si 0 , . . . , n es una derivacin de debilitamiento, entonces `DS 0 n .
2. Si 0 , . . . , n es una derivacin de fortalecimiento, entonces `DS 0 n .
Demostracin. A continuacin se presenta una demostracin para (1); una demostracin para (2) se obtiene de forma similar y se propone como ejercicio para el
lector. Sea 0 , . . . , n una derivacin de debilitamiento. Se procede por induccin
sobre n N.
Caso base: si n = 0, entonces el objetivo es demostrar `DS 0 0 lo cual es
cierto porque la implicacin es reflexiva (Teorema 4.38.1).
Caso inductivo: se tiene que 0 , . . . , n , n+1 es una derivacin de debilitamiento; el objetivo es demostrar que `DS 0 n+1 usando como hiptesis inductiva `DS 0 n . Por la Definicin 5.4.1 se tiene `DS n n+1 . Como la
implicacin es transitiva (Teorema 4.38.2), se concluye `DS 0 n+1 .
Es importante notar que cualquier derivacin es simultneamente una derivacin de debilitamiento y una de fortalecimiento. La observacin clave es que si
es teorema, tambin lo son y por el Teorema 4.36.4. Como
consecuencia prctica, en una derivacin de debilitamiento (respectivamente, de
fortalecimiento) se pueden usar pasos de equivalencia y de implicacin (respectivamente, de consecuencia) conjuntamente. Otra forma de justificar esta observacin
es con base en los teoremas 4.41.2-3.
Nota 5.6
Un paso de derivacin de debilitamiento de a se puede diagramar esquemticamente de la siguiente forma:
105
Ejemplo 5.6
Considere la siguiente derivacin del axioma (KA4) del sistema formal KA (Ejercicio 4.7.51):
h definicin alternativa de i
Ejercicios
1. Demuestre el Metateorema 5.5.2.
2. Considere dos proposiciones y de DS. Es posible que exista una derivacin
de debilitamiento y otra de fortalecimiento de a ? Justifique su respuesta.
3. Considere el siguiente esquema:
h ... i
h ... i
106
5.4.
Propiedades importantes de DS
Esta seccin presenta dos resultados importantes del sistema DS, cada uno de
ellos en la forma de un metateorema. El primero de ellos es el Metateorema de la
Deduccin el cual facilita la demostracin de implicaciones lgicas en DS por medio
del mecansmo de suposicin del antecedente. El segundo es el Metateorema de
Solvencia y Completitud el cual establece que el concepto semntico de tautologa
y el concepto deductivo de teorema coinciden en DS. Estas dos propiedades de DS
se presentan para el caso general de demostraciones con suposiciones, una extensin
del concepto de demostracin en un sistema formal.
A continuacin se presenta el concepto de demostracin son suposiciones.
Definicin 5.7
Sea un conjunto de proposiciones de DS. Una demostracin con suposiciones en
es una secuencia de proposiciones 0 , . . . , n de DS tal que para 0 k n una
de las siguientes condiciones es cierta:
107
1. k es un axioma de DS,
2. k > 0 y k es la conclusin de una regla de inferencia de DS cuyas premisas
aparecen en la secuencia 0 , . . . , k1 , o
3. k .
Si 0 , . . . , n es una demostracin con suposiciones en , entonces se dice que n
es un teorema de en DS, lo cual se escribe como
`DS n .
El Metateorema de la Deduccin formaliza y justifica una tcnica de demostracin muy comn en la prctica de la informtica y de las matemticas conocida
como la tcnica de demostracin por suposicin del antecedente. El Metateorema
de la Deduccin establece que para demostar una implicacin lgica basta con construr una demostracin del consecuente a partir de la informacin del antecedente.
Metateorema 5.9
Sean , proposiciones de DS y un conjunto de proposiciones de DS:
si {} `DS ,
entonces
`DS .
El Metateorema de la Deduccin establece que si una proposicin se puede demostrar a partir de un conjunto de suposiciones {}, entonces la implicacin
se puede demostrar a partir de . En el caso especial cuando = , el
108
h distribucin de sobre i
Entonces, `DS .
Leibniz: se obtiene con premisa k = 0 1 , para algn 0 k n. Entonces
es de la forma [p := 0 ] [p := 1 ]. Por la hiptesis inductiva se tiene `DS
(0 1 ). El objetivo es demostrar
`DS ([p := 0 ] [p := 1 ]).
Esta demostracin se puede obtener por induccin estructural sobre y se propone como ejercicio para el lector (Ejercicio 5.4.3).
En cualquiera de los casos se tiene que si {} `DS , entonces `DS .
109
o, in extremis, demostrar
{, } `DS .
Considere la siguiente derivacin con suposiciones en {, }:
h suposicin i
true
Por el Metateorema de la Deduccin se concluye `DS ( ).
Ejemplo 5.8
Considere el Teorema 4.41.2:
`DS ( ) ( ) ( ).
Por el Teorema 4.36.5, basta con demostrar:
`DS ( ) (( ) ( )).
Considere la siguiente derivacin con suposiciones en { , }:
h suposicin: i
h debilitamiento: i
entonces
{} `DS .
110
|= .
Ejercicios
1. Basndose en la Definicin 5.7, proponga definiciones para:
a) Derivacin con suposiciones.
b) Derivacin de debilitamiento con suposiciones.
c) Derivacin de fortalecimiento con suposiciones.
2. Sea un conjunto de proposiciones de DS, y , proposiciones de DS. Demuestre:
a) Si es un teorema de DS, entonces `DS .
b) Si {}, entonces `DS .
3. Sea un conjunto de proposiciones de DS, y , , , 0 , 1 proposiciones de DS.
El objetivo es demostrar que si `DS (0 1 ), entonces:
`DS ([p := 0 ] [p := 1 ])
Una demostracin se puede obtener por induccin sobre la estructura de ;
lleve a cabo los siguientes pasos:
Demuestre que la propiedad es cierta cuando es una constante.
111
Demuestre que la propiedad es cierta cuando es una variable proposicional (considere dos casos, cuando es p y cuando no es p).
Demuestre que la propiedad es cierta cuando es de la forma 0 1
suponiendo que la propiedad es cierta para 0 y 1 .
Demuestre que la propiedad es cierta cuando es de la forma 0 1
suponiendo que la propiedad es cierta para 0 y 1 .
Dado que en DS los conectivos lgicos true, false, , bastan para axiomatizar cualquier otro conectivo lgico, los casos anteriores son suficientes para
establecer la veracidad de la afirmacin inicial.
4. Sean y conjuntos de proposiciones de DS, y , proposiciones de DS.
Demuestre:
a) Si y `DS , entonces `DS .
b) Si {} `DS y `DS , entonces `DS .
5. Sea un conjunto de proposiciones de DS y una proposicin de DS. Demuestre
que si `DS y cada una de las proposiciones en es teorema de DS, entonces
`DS .
6. Demuestre el Metateorema 5.10.
7. Sean 0 , . . . , n tautologas. Demuestre que si {0 , . . . , n } |= , entonces es
teorema de DS.
8. Demuestre: `DS si y solo si {} es insatisfacible.
9. Sea un conjunto de proposiciones satisfacible. Demuestre o refute:
a) Si `DS , entonces {} o {} es satisfacible.
b) Si `DS ( ), entonces {, } es satisfacible.
5.5.
Tcnicas complementarias
Esta seccin presenta tcnicas complementarias para razonar sobre proposiciones. A diferencia de las tcnicas inicialmente presentadas en la Seccin 5.2, las
tcnicas en esta seccin son ms generales y no estn reservadas nicamente para
razonar sobre la equivalencia lgica. De hecho, la mayora de las tcnicas presentadas en esta seccin son especialmente tiles para razonar sobre implicaciones lgicas
o, en su defecto, estn basadas en la implicacin lgica. Como ejemplos, esta seccin hace uso extensivo de teoras como la artimtica y los conjuntos, apelando a
definiciones bsicas e intuitivas.
Es importante resaltar que las tcnicas presentadas en esta seccin son de caracter general en un sentido complementario: pueden ser usadas en cualquier otro
sistema formal de la lgica proposicional y no son exclusivas de DS. En particular, el
material de esta seccin sirve para sustentar algunas tcnicas de demostracin que
comnmente se encuentran en textos y que, por falta de estas bases, son ilegibles
parar el lector.
5.5.1. Demostracin por suposicin del antecedente. Una prctica comn
para demostrar una implicacin lgica es usar la tcnica de suposicin del antecedente. Esta tcnica consiste en demostrar bajo la suposicin de , para conclur
112
sii
{} `DS .
Ejemplo 5.9
Si a y b son nmeros enteros consecutivos, entonces a + b es impar.
Demostracin. A continuacin se especifica el objetivo de la demostracin en el
lenguaje del sistema DS :
`DS (a = b + 1) impar(a + b)
Esta especificacin establece un rden entre a y b, lo cual no importa porque la
suma de nmeros enteros es conmutativa. En favor de la brevedad, se abusa la
notacin dado que los smbolos +, =, impar no hacen parte de DS. Al suponer el
antecedente, basta con demostrar (paso 1):
{a = b + 1} `DS impar(a + b).
113
h suposicin: a = b + 1 i
impar((b + 1) + b)
h aritmtica i
impar(2b + 1)
true.
Por el Meateorema 5.12 se concluye `DS (a = b + 1) impar(a + b).
sii
`DS y `DS .
114
h suposicin: B = A B i
x (A B)
true.
115
Metateorema 5.14
Sean un conjunto de proposiciones y , proposiciones:
1. `DS
sii
2. `DS
`DS false.
sii
`DS false.
116
contradiccin:
true
h suposicin: impar(a + b) i
impar(a + b)
h aritmtica i
impar(2(ca + cb + 1))
false.
sii
`DS .
117
Metateorema 5.17
Sean un conjunto de proposiciones y , 0 , 1 , , 0 , 1 proposiciones:
1. `DS 0 1 sii `DS 1 0 .
2. `DS 0 1 sii `DS 0 1 .
3. `DS 0 1 0 1 sii `DS 0 1 0 1 .
118
sii
`DS [p := true]
y `DS [p := false] .
El Metateorema 5.18 est basado en una propiedad de la lgica proposicional conocida como la Regla de Shannon.
Teorema 5.19
Sean p una variable proposicional y una proposicin:
`DS (p [p := true]) (p [p := false]).
119
120
Ejemplo 5.14
Si a Z, entonces a2 6= 5.
Demostracin. Considere los siguientes tres casos:
0 : a < 2,
1 : 2 a 2,
2 : 2 < a.
Los casos 0 , 1 , 2 son exhaustivos sobre a (por qu?). Por el Metateorema 5.21
basta con demostrar que las implicaciones i , para i = 0, 1, 2, son teoremas.
Estas tres demostraciones se proponen como ejercicios para el lector.
a = 3c + 1
a = 3c + 2.
121
Ejercicios
1. Demuestre el Metateorema 5.12.
2. Explique, paso a paso, por qu en la demostracin de la propiedad (1) en el
Ejemplo 5.10 basta con demostrar para cualquier x:
{A B = B, x A} `DS x B.
3. Complete el Ejemplo 5.10 con la demostracin de la propiedad (2).
4. Sean A, B y C conjuntos. Demuestre:
a) A B A.
b) A A B.
c) (C A) (C B) C (A B).
5. Sean A y B conjuntos. En cada uno de los siguientes casos establezca si la
condicin dada es suficiente para establecer la igualdad de A y B (i.e, A = B):
a) A B y B A.
b) A B = B y A B = B.
c) A B = B y A B = A.
Justifique su respuesta: en el caso afirmativo presente una demostracin; en el
caso negativo presente un contraejemplo.
6. Demuestre el Metateorema 5.13.
122
n
^
iff
`DS i ,
para cada 0 i n.
i=0
n
_
iff
`DS i ,
para algn 0 i n.
i=0
sii
`DS .
123
25. Demuestre que si a, b Z son tales que par(a+b), entonces a y b tienen la misma
paridad. Dos nmeros tienen la misma paridad cuando ambos son impares o
ambos son pares.
26. Demuestre que si a, b Z son tales que par(ab), entonces al menos uno de a y
b es par.
27. Demuestre que si a, b Z son tales que impar(ab), entonces a y b es son impares.
28. Demuestre que si a es un nmero entero positivo de la forma a = 3c + 2, para
algn c Z, entonces a no es un cuadrado perfecto. Ayuda: note que todo
nmero entero a puede escribirse como a = 3c, a = 3c + 1 o a = 3c + 2 para
algn c Z.
29. Demuestre que si a es un nmero entero de la forma a = 4c + 2 o a = 4c + 3
para algn c Z, entonces a no es un cuadrado perfecto. Ayuda: note que
todo nmero entero a puede escribirse como a = 4c, a = 4c + 1, a = 4c + 2 o
a = 4c + 3, para algn c Z.
30. Demuestre que si a, b R son tales que ab es irracional, entonces al menos uno
de a y b es irracional.
31. Demuestre el Teorema 5.19.
32. Demuestre el Metateorema 5.18.
33. Complete las demostraciones en el Ejemplo 5.13.
34. Demuestre el Metateorema 5.21 por induccin sobre n N.
35. Complete las demostraciones en el Ejemplo 5.14.
36. Demuestre que si a Z, entonces alguno de a3 , a3 + 1 o a3 1 es mltiplo de 9.
37. Demuestre que si a N, entonces a7 a es mltiplo de 7. Ayuda: use anlsis
de casos sobre a con respecto a mltiplos de 7.
38. Demuestre el Metateorema 5.22.1.
39. Demuestre el Metateorema 5.22.2.
40. Complete el Ejemplo 5.15 con las demostraciones de las condiciones (1) y (2).
41. Investigue y explique brevemente en qu consiste el teorema de los 4 colores
(en ingls, four color theorem). En particular, describa cmo fue til un computador para demostrarlo y explique qu tcnica de demostracin (abordada en
esta seccin) fue extensivamente usada en dicha demostracin mecnica.
42. Investigue sobre la conjetura de Kepler (en ingls, Kepler conjecture). Explique en qu consiste la conjetura y el estado actual de su demostracin. Qu
tcnica fue usada extensivamente en su demostracin? Explique brevemente.
43. En internet circulan listas de tcnicas de demostracin como, por ejemplo,
demostracin por intimidacon, por omisin o por ofuscacin. A la luz de la lgica este tipo de razonamientos carecen de cualquier justificacin. Sin embargo,
puede ser interesante conocer algunos de estos argumentos para evitarlos a toda
costa, al menos en un curso de lgica. Investigue y explique en qu consisten
las siguientes tcnicas de demostracin:
a) Demostracin por intimidacon.
b) Demostracin por omisin.
c) Demostracin por ofuscacin.
124
d)
e)
f)
g)
h)
i)
j)
k)
l)
m)
n)
)
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
Demostracin
por
por
por
por
por
por
por
por
por
por
por
por
intuicin.
acumulacin de evidencia.
referencia a una fuente inaccesible.
autoridad eminente.
creencia religiosa.
asombro.
repeticin.
reduccin al problema equivocado.
importancia.
eliminacin del contraejemplo.
cambio de definicin.
notacin ilegible.
Parte 2
Lgica de predicados
Captulo 6
Lenguaje y especificacin
Desde el punto de vista de la lgica proposicional, la argumentacin en el Ejemplo 6.1 tiene la forma
p, q, r,
la cual, de acuerdo con los mtodos estudiados en los captulos 3 y 4, no es vlida.
Sin embargo, intuitivamente este argumento es vlido: de lo contrario habra un informtico intelectualmente no destacado, contradiciendo la primera proposicin en
la argumentacin. Esto evidencia que la lgica proposicional no es lo suficientemente
fuerte para verificar la validez de algunas argumentaciones.
En este captulo se estudiarn los lenguajes de primer orden. Estos lenguajes
tienen la caracterstica de ser ms generales que el lenguaje de la lgica proposicional y, gracias a su poder expresivo, permitirn traducir y analizar argumentaciones
como la del Ejemplo 6.1. Anticipando el desarrollo de este captulo, la argumentacin del Ejemplo 6.1 en lgica de predicados tendra la siguiente forma:
(x (I(x) D(x))), I(t), D(t),
127
128
6. Lenguaje y especificacin
6.1.
Trminos y frmulas
El otro tipo de ente denota valores de verdad sobre los objetos, como por
ejemplo, I(x), (I(x) D(x)) y D(Turing).
Nota 6.2
Una frmula es una expresin que denota valores de verdad sobre los trminos.
129
130
6. Lenguaje y especificacin
Ejemplo 6.2
Sea F = {n, f, g} con ar(n) = 0, ar(f ) = 1 y ar(g) = 2. Entonces n,
g(f (n), n) y f (g(f (n), n)) son trminos. Sin embargo, las expresiones n(f ), g(f (n))
y g(f (n), n, n) no lo son. Por qu?
Ejemplo 6.3
Sea F = {0, 1, 2, . . . , s, +, , } con ar(n) = 0 si n N, ar(s) = 1 y ar(+) = ar() =
ar() = 2. Entonces ((2, +(s(x1 ), x0 )), x1 ) es un trmino. Usualmente los smbolos
de funcin binarios se escriben con notacin infija en favor de la notacin prefija;
consecuentemente, este trmino se escribe como
(2 (s(x1 ) + x0 )) x1 .
131
De acuerdo con la Definicin 6.5, observe cmo en una frmula de la lgica de predicados los argumentos de un smbolo de predicado son trminos. La Definicin 6.5
puede escribirse usando la notacin Backus-Naur de la siguiente manera:
(6.2)
Nombre
Interpretacin
cuantificador universal todo es tal que
cuantificador existencia hay un tal que
Nota 6.6
Por conveniencia, en la lgica de predicados se preserva la convencin sobre la precedencia de los conectivos lgicos de la lgica proposicional (Nota 5.1). Se establece
que los cuantificadores , tienen la misma precedencia que . En consecuencia, se
adoptan las siguientes convenciones sobre la precedencia de los conectivos lgicos
de la lgica de predicados:
Las constantes true y false tienen ms precedencia que , , .
Los conectivos , , tienen ms precedencia que , .
Los conectivos , tienen ms precedencia que , .
Los conectivos , tienen ms precedencia que , 6.
Las frmulas de la lgica de predicados, al igual que los trminos, pueden ser
representadas por medio de rboles sintcticos. En un rbol de sintaxis, los cuantificadores y tienen exactamente un subrbol, como la negacin , que corresponde
al rbol de la frmula que cuantifican. Las frmulas que se construyen a partir de
un smbolo de predicado P y una lista de trminos t1 , . . . , tn (i.e., una frmula
P (t1 , . . . , tn )), en un rbol de sintaxis tienen raz con etiqueta P y n subrboles,
uno por cada ti . La situacin es similar para un trmino que se construye a partir
de un smbolo de funcin f y una lista de trminos t1 , . . . , tn (i.e., una trmino
f (t1 , . . . , tn )). Este caso, la raz en un rbol de sintaxis tiene etiqueta f y n subrboles, uno por cada ti . La Figura 2 presenta el rbol de sintaxis correspondiente a
la frmula x0 ((P (x0 ) Q(x0 )) S(x0 , x1 )).
Como se ilustr en la introduccin de este captulo, la lgica de predicados
generaliza la lgica proposicional y cuenta con un lenguaje que permite modelar en
ms detalle situaciones de inters. Considere el problema de simbolizar y especificar
la siguiente proposicin en un lenguaje de la lgica de predicados:
132
6. Lenguaje y especificacin
x0
S
Q x0 x1
x0 x0
Figura 2. rbol de sintaxis de x0 ((P (x0 ) Q(x0 )) S(x0 , x1 )).
Ejemplo 6.5
En este ejemplo se usa padre como funcin. Los smbolos yo, H, I se definen como
en el Ejemplo 6.4. En adicin, el smbolo de funcin p es tal que p(x) representa el
padre de x. Note que dada una persona, su padre est unvocamente definido y por
ende la expresin p(x) est bien definida. Con esta simbolizacin, la especificacin
133
Ejercicios
1. Dibuje el rbol de sintaxis de los trminos n, g(f (n), n) y f (g(f (n), n)) del
Ejemplo 6.2.
2. Explique por qu las expresiones n(f ), g(f (n)) y g(f (n), n, n) del Ejemplo 6.2
no son trminos.
3. Sea F = {a, b, c} con a, b, c constantes (i.e., ar(a) = ar(b) = ar(c) = 0). Cules
son los trminos sobre F?
4. Sea F = {a, f } con a constante y f un smbolo unario (i.e., ar(a) = 0 y ar(f ) =
1). Cules son los trminos sobre F libres de variables (i.e., sin apariciones de
variable alguna)?
134
6. Lenguaje y especificacin
135
136
6. Lenguaje y especificacin
137
138
6. Lenguaje y especificacin
6.2.
139
x0
P
x0
f
x1
x2
x2
P
x2 x0
140
6. Lenguaje y especificacin
Ejemplo 6.6
Considere la frmula representada por el rbol de sintaxis en la Figura 3. La variable
x0 ocurre libre y acotada en esta frmula. A su vez, la variable x1 nicamente ocurre
libre, mientras que x2 , al igual que x0 , ocurre libre y acotada en la frmula.
Nota 6.9
Considere una variable x y una frmula . Intuitivamente, una aparicin acotada
de x por un cuantificador universal en representa cualquier valor posible para
esa aparicin de x. Una aparicin acotada de x por un cuantificador existencial en
representa algn valor posible para esa aparicin de x. Una aparicin libre de x
en representa un valor externo (o desconocido) que debe ser suministrado (por
ejemplo, por el contenido de una direccin de memoria en un computador).
141
Ejemplo 6.8
Considere la frmula
x0 (P (x0 , x1 ) x0 Q(x0 )).
En este caso, el alcance de x0 es P (x0 , x1 ) y el alcance de x0 es Q(x0 ).
Ejercicios
1. Considere el rbol de sintaxis en la Figura 3. Explique por qu una aparicin
de x2 es libre y la otra es acotada.
2. Considere la frmula en el Ejemplo 6.8. Dibuje el rbol de sintaxis, y explique
por qu el alcance de x0 es P (x0 , x1 ) y el alcance de x0 es Q(x0 ).
3. Sean m un smbolo de funcin constante, f un smbolo de funcin con un
argumento y S, B smbolos de predicado con dos argumentos. Suponga que
x, y, z son variables en X . Para cada una de las siguientes frmulas, indique (i)
cules apariciones de x, y, z son libres y (ii) cules son acotadas.
a) S(m, x)
b) B(m, f (m))
c) B(x, y) z S(z, y)
d ) y B(x, y) z S(z, y)
e) S(x, y) S(y, f (f (x)))
4. Sean c, d smbolos de funcin constantes, f un smbolo de funcin con un argumento y h un smbolo de funcin con dos argumentos. Adems, sean P, Q
smbolos de predicado con tres argumentos. Suponga que x, y, z son variables
en X . Para cada una de las siguientes frmulas, indique (i) cules apariciones
de x, y, z son libres, (ii) cules son acotadas y (iii) el alcance de cada uno de
los cuantificadores.
a) P (c, c, d) x P (f (d), h(h(c, x), d), y)
b) y (P (x, y, x) z Q(z, y, f (z)))
c) y P (x, y, x) 6 y Q(z, y, f (z))
d ) y (P (x, y, x) 6 y Q(z, y, f (z)))
e) x y P (x, y, x) z Q(z, y, f (x))
f ) z y P (x, y, x) z Q(z, y, f (x))
g) x (y P (x, y, x) z Q(z, y, f (x)))
h) z (y P (x, y, x) z Q(z, y, f (x)))
5. Sea la frmula
x(P (y, z) y (Q(y, x) P (y, z))),
en donde x, y, z son variables y P, Q smbolos de predicado con dos argumentos.
142
6. Lenguaje y especificacin
6.3.
Sustitucin de trminos
Las variables son comodines en una frmula, luego es natural contar con mecanismos para reemplazarlas por informacin ms concreta. Esta seccin presenta la
sustitucin textual de trminos como mecanismo para hacer estas instanciaciones
en una frmula de la lgica de predicados. Adicionalmente, esta seccin presenta la
nocin de cundo un trmino t puede reemplazar una variable x en una frmula
de manera tal que la frmula resultante diga sobre t lo mismo que dice sobre x.
As se finaliza la discusin iniciada en la Seccin 6.2 acerca de esta problemtica.
De acuerdo con las definiciones de trminos y frmulas (definiciones 6.4 y 6.5)
nicamente es correcto sustitur una variable por un trmino. De lo contrario, se
tendran trminos cuyos subtrminos pueden ser frmulas.
A continuacin se presenta el concepto de sustitucin de trminos.
Definicin 6.11
Una sustitucin de trminos es una funcin F : X T (X , F) distinta a la identidad
en una cantidad finita de elementos del dominio.
Una sustitucin de trminos F es una funcin que asocia un trmino F (x) a cualquier variable x X . Recuerde que T (X , F) denota la coleccin de trminos sobre
F (Definicin 6.4). Al igual que una sustitucin de la lgica proposicional (Definicin 4.6), cualquier sustitucin de trminos F es tal que F (x) 6= x para una
cantidad finita de variables x. Entonces, una sustitucin de trminos tambin puede ser escrita como un conjunto finito de la forma
{y0 7 u0 , y1 7 u1 , . . . , yn 7 un }
indicando que el trmino ui est asociado a la variable yi (0 i n) y cualquier
otra variable est asociada a s misma cuando esta no aparece en la lista de variables
y0 , y1 , . . . , yn .
143
144
6. Lenguaje y especificacin
La Definicin 6.14 indica cmo aplicar una sustitucin F a una frmula resulta
en una frmula F (). La sustitucin no tiene efecto alguno sobre las constantes
true y false, ni tampoco sobre predicados sin argumentos (casos (1)-(3)). Una sustitucin aplicada a una frmula que corresponde a un predicado con al menos un
argumento, resulta en la sustitucin aplicada a cada uno de sus subtrminos (caso
(3)). Note que en este caso la sustitucin se aplica sobre trminos como lo establece la Definicin 6.12. La definicin inductiva para combinaciones Booleanas de
frmulas es considera en los casos (4) y (5). La situacin con las cuantificaciones
es ms interesante (caso (6)). Una sustitucin no afecta la variable cuantificada en
x o x. Adems, ninguna aparicin de x en se sustituye cuando se aplica una
sustitucin a una frmula x o x . En el caso especfico de las cuantificaciones, las restricciones son el instrumento que permite controlar qu variables son
reemplazadas.
145
Desafortunadamente, an bajo los cuidados de la Definicin 6.14, las sustituciones textuales pueden dar lugar a efectos inesperados. En una sustitucin textual
[x := t], puede suceder que una variable y aparezca en t mientras una aparicin
libre de x en est en el alcance de una cuantificacin y o y. En este caso, la
variable y que en denota un valor externo, da lugar en [x := t] a una variable que
146
6. Lenguaje y especificacin
Ejemplo 6.14
Sea la frmula en la Figura 3:
((x0 P (x0 , f (x1 ))) Q(x2 ) x2 P (x2 , x0 )).
f (x2 ) no es libre para x0 en porque hay una aparicin libre de x0 en que
est bajo el alcance de un cuantificador x2 y x2 es una variable en f (x2 ).
x1 es libre para x1 en .
f (x2 ) es libre para x1 en .
h(x0 , x3 ) no es libre para x1 en porque hay una aparicin libre de x1 en que
est bajo el alcance de un cuantificador x0 , y x0 es una variable en h(x0 , x3 ).
147
Ejercicios
1. Considere la sustitucin textual F y el trmino t en el Ejemplo 6.9. Escriba en
detalle el clculo de F (t).
2. Considere la sustitucin textual F y la frmula en el Ejemplo 6.11.
a) Dibuje el rbol de sintaxis de .
b) Asocie a cada uno de los nodos del rbol de sintaxis de la sustitucin
correspondiente.
c) Dibuje el rbol de sintaxis de F ().
3. Considere la sustitucin textual F y la frmula en el Ejemplo 6.12.
a) Dibuje el rbol de sintaxis de .
b) Asocie a cada uno de los nodos del rbol de sintaxis de la sustitucin
correspondiente.
c) Dibuje el rbol de sintaxis de F ().
4. Determine la frmula [x2 := f (x1 , x2 )] en donde es cada una de las siguientes
frmulas:
a) x2 (P (x1 , x2 ) P (x2 , c))
b) x2 P (x1 , x2 ) P (x2 , c)
c) Q(x3 ) x1 x2 R(x1 , x2 , c)
d ) x1 Q(x1 ) x2 P (x1 , x2 )
e) x2 (P (f (x1 , x2 ), x1 ) x1 S(x3 , g(x1 , x2 )))
5. Sea t el trmino f (x1 , x2 ). Explique si t es libre para x2 en cada una de las
siguientes frmulas:
a) x2 (P (x1 , x2 ) P (x2 , c))
b) x2 P (x1 , x2 ) P (x2 , c)
c) Q(x3 ) x1 x2 R(x1 , x2 , c)
d ) x1 Q(x1 ) x2 P (x1 , x2 )
e) x2 (P (f (x1 , x2 ), x1 ) x1 S(x3 , g(x1 , x2 )))
6. En cada uno de los siguientes casos, sea la frmula dada. Sea t el trmino
f (x1 , x3 ). Calcule [x1 := t] y luego explique si t es libre para x1 en .
a) x2 (P (x2 , f (x1 , x2 )) Q(x1 ))
b) x2 P (x2 , f (x1 , x2 )) Q(x1 )
c) x1 x3 (Q(x3 ) 6 Q(x1 ))
d ) x1 x3 Q(x3 ) 6 Q(x1 )
e) x2 R(x1 , g(x1 ), x2 ) x3 Q(f (x1 , x3 ))
7. Repita el Ejercicio 6 para cada uno de los siguientes trminos t:
a) x2
b) x3
c) f (x4 , x1 )
d ) h(x1 , x2 , x3 )
148
6. Lenguaje y especificacin
6.4.
149
El lenguaje LA considera tres tipos de objetos: los ndices, los valores y los
arreglos. Como se ver en los siguientes prrafos, estas distinciones se pueden inclur
en LA usando la nocin de tipo.
Nota 6.17
Un tipo es una convecin sintctica asociada a los smbolos de un lenguaje de primer
orden, de funcin y predicado, para clasificar trminos.
Los tipos de LA son I para ndices, V para valores y A para nombres de arreglos.
Definicin 6.18
Los smbolos de funcin FA son los siguientes:
Una coleccin infinita de smbolos constantes 0, 1, 2, . . . de tipo I.
Una coleccin infinita de smbolos constantes . . . , 2, 1, 0, 1, 2, . . . de tipo V .
Una coleccin infinita de smbolos constantes a0 , a1 , a2 , . . . de tipo A.
Un smbolo unario len de tipo V con argumento de tipo A.
Un smbolo binario read de tipo V con primer argumento de tipo A y segundo
argumento de tipo I.
Los smbolos binarios +, , de tipo V con argumentos de tipo V .
150
6. Lenguaje y especificacin
Definicin 6.20
La expresin XI denota una coleccin infinita de variables de tipo I y XV una
coleccin infinita de variables de tipo V .
len(a)
len(b)
read (a, i)
read (b, i)
n+m
nm
Los trminos i, j tienen tipo I, el trmino a tiene tipo A, los trminos len(a), len(b)
tienen tipo V , mientras que read (a, i), read (b, i), n + m, n m tienen tipo V .
151
A continuacin se presentan ejemplos de cmo especificar en LA las frases (1)(3) en la introduccin de la seccin. En estas especificaciones se opta por usar
arreglos cuyo primer ndice es 0. Esto quiere decir que si un arreglo almacena n
elementos, entonces el ltimo ndice de dicho arreglo es n 1.
Ejemplo 6.16
Para la frase el arreglo a no es vaco se propone la frmula
len(a) > 0.
152
6. Lenguaje y especificacin
153
Ejemplo 6.20
Sea a una constante de tipo A. Considere la siguiente frmula de LA :
(i:I | 0 i < len(a) : (j:I | 0 j < len(a) : a[i] + a[j] = 0)).
Cmo se interpreta esta frmula? En castellano, esta frmula podra ser traducida as:
si se toma cualquier elemento v en a (v = a[i]), hay un elemento u en a (u = a[j])
tal que u es el inverso aditivo de v.
Ejemplo 6.21
Sea a una constante de tipo a. Considere la siguiente frmula de LA :
(i:I | 0 i < len(a) : a[i] = i).
En castellano, esta frmula indica que el arreglo a tiene al menos un punto fijo.
def empty(a):
assert type(a)==list
return len(a)==0
En el Ejemplo 6.22, se define el smbolo empty con la funcin empty. Esta funcin
retorna de forma afirmativa nicamente cuando el arreglo dado tiene longitud 0 y
de forma negativa de lo contrario; esta es la definicin lgica del smbolo empty en
LA . La instruccin assert se usa para validar la precondicin de la funcin empty:
el argumento de la funcin debe ser de tipo arreglo (i.e., type(a) debe ser list).
La instruccin assert permite evaluar aserciones: si la condicin dada se cumple,
entonces el cdigo de la funcin sigue su ejecucin; de lo contrario, la ejecucin
de la funcin termina abruptamente con un error de violacin de la asercin. A
pesar de ser muy sencillo, el Ejemplo 6.22 sirve el propsito de resaltar por qu es
importante identificar qu smbolos son parmetros en una frmula y qu debe ser
cierto sobre ellos. En la frmula empty(a), el nombre de arreglo a es un parmetro
y, consecuentemente, la funcin Python empty tiene un argumento que corresponde
154
6. Lenguaje y especificacin
al nombre del arreglo sobre el cual se hace la verificacin. Note que el smbolo de
funcin len de LA coincide con el nombre de la funcin len de Python3, pero son
smbolos en dos mundos distintos.
Ejemplo 6.23
Considere la siguiente funcin asc en Python3:
1
2
3
4
5
6
7
8
9
10
11
12
def asc(a,x,y):
assert type(a)==list
r = 0<=x<=len(a) and 0<=y<=len(a)
i = x
while r and i<y:
j = x
while r and j<y:
if i<j:
r = a[i]<=a[j]
j += 1
i += 1
return r
155
def equal(a,b):
assert type(a)==type(b)==list
r,i = len(a)==len(b),0
while r and i<len(a):
r,i = a[i]==b[i],i+1
return r
Ejercicios
1. Dibuje el rbol de sintaxis de los trminos en el Ejemplo 6.15.
2. Sean x una variable en XV , i una variable en XI y a un nombre de arreglo.
Determine cules de las siguientes expresiones son trminos de LA . En el caso de
que la expresin sea un trmino, dibuje el rbol de sintaxis; en el caso contrario
explique por qu no es un trmino.
a) len(a, 0)
b) read (a, 0)
c) a[0]
d ) read (x, i)
e) x[i]
3. Dibuje el rbol de sintaxis de la frmula en el Ejemplo 6.16.
4. Dibuje el rbol de sintaxis de la frmula en el Ejemplo 6.17.
5. Dibuje el rbol de sintaxis de la frmula en el Ejemplo 6.18.
6. Dibuje el rbol de sintaxis de las frmulas en el Ejemplo 6.19.
7. Dibuje el rbol de sintaxis de la frmula en el Ejemplo 6.20.
8. Dibuje el rbol de sintaxis de la frmula en el Ejemplo 6.21.
9. Sean x una variable en XV y a un nombre de arreglo. Determine cules de las
siguientes expresiones son frmulas de LA . En el caso de que la expresin sea
una frmula, dibuje el rbol de sintaxis; en el caso contrario explique por qu
no es una frmula.
a) i:I (a[i] = x)
b) i:I (0 i < len(a) a[i] = x)
c) b:A (b[i] = x)
d ) len(a) > 1 j:I (a[0] a[j] = a[0])
e) (i:I | 0 < i < len(a) : a[i 1] a[i])
10. Exhiba tres arreglos concretos para a que satisfagan la frmula del Ejemplo 6.17;
exhiba tres que no la satisfagan.
156
6. Lenguaje y especificacin
157
Captulo 7
El sistema de Dijkstra y
Scholten para primer orden
7.1.
159
160
Una sustitucin de frmulas F es una funcin que asocia una frmula F (x) a cualquier smbolo constante de predicado p P. Recuerde que T (X , F, P) denota la
coleccin de frmulas sobre (F, P) (Definicin 6.5). Al igual que una sustitucin
de la lgica proposicional y de trminos, cualquier sustitucin de frmulas F es tal
que F (p) 6= p para una cantidad finita de smbolos p de aridad 0. Entonces, una
sustitucin de frmulas tambin puede ser escrita como un conjunto finito de la
forma {q0 7 0 , q1 7 1 , . . . , qn 7 n } indicando que la frmula i est asociada
al smbolo constante qi (0 i n) y cualquier otro smbolo constante est asociado
a s mismo cuando este no aparece en la lista de smbolos q0 , q1 , . . . , qn .
Una sustitucin de frmulas nicamente se aplica a una frmula. Note que no
tiene sentido aplicar una sustitucin de frmulas a un trmino. Primero, porque
un trmino no menciona smbolos de predicado. Segundo, porque en general un
trmino no puede tener una frmula como subtrmino.
161
Definicin 7.3
Sea una frmula y F = {q0 7 0 , q1 7 1 , . . . , qn 7 n } una sustitucin
de frmulas. La sustitucin textual de F en , denotada como F (), se define
inductivamente para toda subfrmula de de la siguiente manera:
1. F (true) = true y F (false) = false,
2. F (p) = F (p), si p {q0 , . . . , qn },
3. F (p) = p, si ar(p) = 0 y p
/ {q0 , . . . , qn },
4. F (Q(t1 , . . . , tk )) = Q(t1 , . . . , tk ), si Q P es tal que ar(Q) = k > 0 y t1 , . . . , tk
son trminos sobre F,
5. F () = F (),
6. F ( ) = F () F ( ), si {, 6, , , , } y
7. F (x ) = x F () y F (x ) = x F ().
162
Definicin 7.5
Sean x una variable, t un trmino y , , frmulas. El conjunto de axiomas de
DS(L) est dado por el siguiente esquema axiomtico:
(Ax): Cualquier axioma de DS.
(Bx1): (x ) , si x no aparece libre en .
(Bx2): (x ) x ( ), si x no aparece libre en .
(Bx3): (x ) (x ) x ( ).
(Bx4): (x ) [x := t] , si t es libre para x en .
Cualquier axioma de DS es un axioma de DS(L) y para su identificacin se conservan los nombres de DS. La cuantificacin de una variable no tiene efecto sobre una
frmula en la cual dicha variable no aparece libre (Bx1). La disyuncin distribuye
sobre la cuantificacin universal siempre y cuando la frmula siendo distribuda no
sea capturada por el cuantificador (Bx2). La cuantificacin universal y la conjuncin
conmutan (Bx3). Una frmula cuantificada universalmente puede ser particularizada por cualquier trmino, siempre y cuando dicho trmino sea libre para la variable
cuantificada en dicha frmula (Bx4). Finalmente, note que algunos parntesis en
la Definicin 7.5 se incluyen nicamente por claridad en la lectura y pueden ser
eliminados de acuerdo con las convenciones de precedencia en la Nota 6.6.
A continuacin se define el conjunto de reglas de inferencia de DS(L).
Definicin 7.6
Sean x una variable, p un smbolo de predicado con aridad 0 y , , frmulas. Las
reglas de inferencia de DS(L) son:
Ecuanimidad
Leibniz
[p := ] [p := ]
Generalizacin
x
El sistema DS(L) cuenta con tres reglas de inferencia. Las reglas Ecuanimidad y
Leibniz son similares a las reglas de inferencia de DS. La tercera regla de inferencia
es Generalizacin e indica que si una frmula es teorema, entonces tambin lo
es cualquiera de sus versiones cuantificadas universalmente (i.e., para cualquier
variable en X ).
163
Nota 7.7
Note que los conceptos de derivacin (Definicin 4.25) y derivacin relajada (Definicin 5.4) definidos para DS pueden ser definidos de manera similar para DS.
Algo similar sucede con las reglas de inferencia derivadas en el Captulo 4 para DS,
las cuales deben ser correctas para DS(L), al igual que con las tcnicas de razonamiento y demostracin del Captulo 5. Sin embargo, se debe tener cuidado con el
Metateorema de la Deduccin para DS(L) que es distinto a su contraparte en DS
(ver Seccin 7.4).
(suposicin 1)
2.
(suposicin 2)
I(Turing)
I(Turing) D(Turing)
5.
D(Turing)
Ejercicios
1. Sean x, y variables, f un smbolo de funcin con ar(f ) = 2 y H un smbolo de
predicado con ar(H) = 1. Sea F la sustitucin de frmulas
{p0 7 p1 , p2 7 true, p3 7 H(x), p4 7 p4 }.
Determine la sustitucin textual de F para cada una de las siguientes frmulas:
a) p0
b) H(y) x H(x) false
c) x y (H(f (x, y)) p3 )
2. Sean x, y, f, H como en el Ejercicio 1. Para cada una de las siguientes frmulas
, determine si F (pi ) es libre para pi en (i = 0, 1, 2, 3, 4):
a) p0
b) H(y) x H(x) false
c) x y (H(f (x, y)) p3 )
164
Modus Ponens
sii
`DS(L) y `DS(L) .
7.2.
165
La cuantificacin universal
Los teoremas 7.8.1 y 7.8.2 establecen que la cuantificacin universal no tiene efecto
alguno sobre las constantes Booleanas y el Teorema 7.8.3 establece que la cuantificacin universal es idempotente.
Demostracin. A continuacin se presenta una demostracin de (1); demostraciones de (2) y (3) se proponen como ejercicio para el lector.
x true
Los teoremas de trueque indican cmo mover frmulas entre el rango y el trmino
de una cuantificacin. El Teorema 7.9.1 establece que una frmula en el rango puede
ser negada y pasada al trmino bajo una disyuncin y viceversa. Los teoremas 7.9.2
166
y teoremas 7.9.3 indican cmo hacer trueque de frmulas que corresponden a una
conjuncin.
Demostracin. Se presenta una demostracin de (1); demostraciones de (2) y (3)
se proponen como ejercicio para el lector.
(x | : )
h azcar sintctico i
x ( )
h definicin alternativa de i
x ( )
h identidad de i
x (true )
h azcar sintctico i
(x | true : )
h azcar sintctico i
(x |: ).
Los teoremas 7.10.1 y 7.10.3 son versiones de la monotona de la implicacin bajo la cuantificacin universal, mientras que los teoremas 7.10.2 y 7.10.4 son versiones de la monotona de la equivalencia bajo la cuantificacin universal. Recuerde que la expresin x ( ) (x x ) corresponde a la frmula
x ( ) ((x ) (x )). Las demostraciones de estos teoremas se proponen como ejercicios para el lector.
A continuacin se presentan algunos teoremas de distribucin de conectivos
lgicos sobre la cuantificacin universal.
167
Teorema 7.11
Sean x una variable y , frmulas. Si x no aparece libre en :
1. `DS(L) x x ( )
2. `DS(L) x x ( )
h axioma (Bx3) i
x ( ).
El Teorema 7.12.1 se llama regla del rango vaco pues indica cmo operar una
cuantificacin universal cuando ningn elemento del dominio del discurso satisface
su rango. El Teorema 7.12.2 se llama regla de ruptura de rango pues indica cmo
operar una cuantificacin universal cuando su rango corresponde a una disyuncin.
El Teorema 7.12.3 permite el renombramiento de variables y el Teorema 7.12.4
permite el intercambio de variables cuantificadas universalmente.
168
Ejercicios
1. Demuestre el Teorema 7.8.2.
2. Demuestre el Teorema 7.8.3.
3. Demuestre el Teorema 7.9.2.
4. Demuestre el Teorema 7.9.3.
5. Sean , , frmulas; demuestre los siguientes teoremas de trueque:
a) `DS(L) (x | : ) (x |: )
b) `DS(L) (x |: ) (x | : ( ))
6. Demuestre el Teorema 7.10.1.
7. Demuestre el Teorema 7.10.2.
8. Demuestre el Teorema 7.10.3.
9. Demuestre el Teorema 7.10.4.
10. Demuestre o refute: `DS(L) x x ( ).
11. Demuestre el Teorema 7.11.1.
12. Demuestre el Teorema 7.11.2.
13. Demuestre el Teorema 7.12.1.
14. Demuestre el Teorema 7.12.2.
15. Demuestre el Teorema 7.12.3.
16. Demuestre el Teorema 7.12.4.
7.3.
La cuantificacin existencial
169
Teorema 7.14
Para cualquier variable x y frmula :
1. `DS(L) x true true
2. `DS(L) x false false
3. `DS(L) x x x
El teorema 7.15 indica que x es cierto siempre y cuando haya un testigo t para x
que haga [x := t] cierta. Este teorema es importante en la prctica porque establece
una condicin suficiente para que una frmula cuantificada existencialmente sea
cierta: basta encontrar un testigo que haga dicha fmrula cierta.
A continuacin se presentan teoremas de monotonas para la cuantificacin
existencial.
Teorema 7.16
Para cualesquiera variable x y frmulas , , :
1. `DS(L) x ( ) (x x )
2. `DS(L) x ( ) (x x )
3. `DS(L) (x | : ) ((x | : ) (x | : ))
4. `DS(L) (x | : ) ((x | : ) (x | : ))
170
Finalmente, se presentan algunos teoremas que relacionan la cuantificacin universal y la cuantificacin existencial.
Teorema 7.19
Sean x una variable y , frmulas. Si x no aparece libre en :
1. `DS(L) x x ( )
2. `DS(L) x x ( )
Ejercicios
1. Demuestre el Teorema 7.14.1.
2. Demuestre el Teorema 7.14.2.
3. Demuestre el Teorema 7.14.3.
4. Demuestre el Teorema 7.15.
5. Demuestre el Teorema 7.16.1.
6. Demuestre el Teorema 7.16.2.
171
7.4.
Algunos metateoremas
sii
`DS(L) .
El Metateorema de Generalizacin ( 7.20) indica que para demostrar que una frmula cuantificada universalmente es teorema, basta con ignorar el cuantificador
universal. Es importante advertir que este metateorema indica que una frmula y
su versin cuantificada universalmente son equidemostrables, mas no equivalentes.
Confundir estos dos conceptos es un error comn en quienes inician el estudio de
la lgica.
Demostracin. Se procede por doble implicacin; basta con demostrar:
1. Si `DS(L) x , entonces `DS(L) .
2. Si `DS(L) , entonces `DS(L) x .
172
(suposicin)
2. x [x := x]
3.
[x := x]
2. x
(suposicin)
(Generalizacin 1).
Al igual que DS, el sistema DS(L) cuenta una versin del Metateorema de la
Deduccin en la cual hay diferencias sutiles. Estas diferencias se introducen para
evitar cometer errores a causa de las variables libres.
Metateorema 7.21
Sean , frmulas y un conjunto de frmulas. Si
1. {} `DS(L) y
2. la demostracin en (1) no usa la regla Generalizacin sobre una variable
libre de ,
entonces `DS(L) .
173
Para cierto tipo de frmulas se puede formular una versin del Metateorema 7.21 ms sencilla. En particular, para aquellas frmulas que no tienen variables
libres.
Definicin 7.22
Una frmula se llama sentencia si y slo s no tiene variables libres.
La versin del Metateorema de la Deduccin para suposiciones que son sentencias es ms sencilla que su versin general.
Metateorema 7.23
Sean , frmulas y un conjunto de frmulas. Si
1. {} `DS(L) y
2. es una sentencia
entonces `DS(L) .
Demostracin. Es suficiente con demostrar las condiciones (1) y (2) del Metateorema 7.21. Note que la condicin (1) del Metateorema 7.21 coincide con la suposicin (1) (del metateorema que est siendo demostrado). Por la suposicin (2)
se tiene que es una sentencia; consecuentemente no tiene variables libres. De
esta forma la condicin (2) del Metateorema 7.21 se cumple trivialmente. Entonces,
`DS(L) .
El converso del Metateorema de la Deduccin es cierto sin las condiciones sobre
el uso de la regla Generalizacin para las variables libres de la suposicin. A
continuacin se formula este metateorema.
Metateorema 7.24
Sean , frmulas y un conjunto de frmulas:
si `DS(L) entonces
{} `DS(L) .
174
Nota 7.25
Una sucesin de nmeros reales (o sucesin) es una funcin f : N R.
Se distinguen tres tipos para modelar sucesiones en DS(L): uno para nmeros
naturales, uno para nmeros reales y uno para sucesiones. El tipo de nmeros
naturales se denota con la letra N y el de los nmeros reales con la letra R.
El inters principal es el estudio de algunas propiedades del lmite de una sucesin, cuando este existe. En particular, el inters es establecer propiedades del
predicado binario limit definido para cualquer sucesin f y nmero real x de la
siguiente manera:
limit(f, x) : el lmite de f es x.
Claramente esta no es una definicin formal de lo que significa que un valor x sea
el lmite de una sucesin f . De acuerdo con Wikipedia, una definicin (adaptada)
es la siguiente:
una sucesin f tiene lmite x cuando n tiende a infinito, si para todo valor
> 0 por pequeo que sea, existe un valor m a partir del cual si n > m se
tiene que la distancia de x a f (n) es menor que .
Esta definicin, an informal, se especifica el DS(L) en el siguiente ejemplo.
Ejemplo 7.3
A continuacin se presenta una definicin de limit:
limit(f, x) (:R | > 0 : (m:R | m 0 : (n:N | n > m : abs(f (n) x) < ))).
Note que en la definicin de limit (Ejemplo 7.3) se hace explcito el tipo de las variables que se emplean. Adems, es claro el alcance de cada uno de los cuantificadores.
La expresin abs es un smbolo de funcin unario de tipo R cuyo argumento es de
tipo R que denota el valor absoluto. Los smbolos <, >, , son los predicados de
comparacin usuales para nmeros.
En el siguiente ejemplo se usan propiedades bsicas de los nmeros naturales y
reales.
Ejemplo 7.4
Sea f la funcin definida por f (n) = 1 para todo n N. A continuacin se demuestra
que 1 es el lmite de f . El objetivo es demostrar:
`DS(L) (:R | > 0 : (m:R | m 0 : (n:N | n > m : abs(f (n) 1) < ))).
175
h azcar sintctico i
m:R (m 0 (n:N | n > m : abs(f (n) 1) < ))
h definicin de f i
abs(1 1) <
h suposicin i
true.
Ejercicios
1. Sea una coleccin de frmulas. Defina cada uno de los siguientes conceptos
para DS(L):
a) Demostracin con suposiciones en .
b) Derivacin con suposiciones en .
c) Derivacin de debilitamiento con suposiciones en .
d ) Derivacin de fortalecimiento con suposiciones en .
2. Sea x una variable y una frmula. Refute: x .
3. (Difcil) Demuestre el Metateorema de la Deduccin (7.21).
4. Demuestre el Metateorema 7.24.
5. Repita la demostracin en el Ejemplo 7.4 con testigo m = 10.
176
1
n
1
n+1
1
n2
7.5.
La igualdad
La igualdad es reflexiva para variables (Bx6) y permite la sustitucin de una variable libre por un trmino en una frmula siempre y cuando las variables de dicho
trmino no sean capturadas en el proceso (Bx7).
En algunas ocasiones, cuando el rango de una cuantificacin corresponde a una
igualdad, es posible simplificar dicha frmula.
Teorema 7.27
Sea x una varible, t un trmino y una frmula. Si t es libre para x en y x no
aparece en t:
1. `DS(L) (x | x = t : ) [x := t]
7.5. La igualdad
177
2. `DS(L) (x | x = t : ) [x := t]
Cada uno de los teoremas en 7.27 se llama regla de un punto porque indican cmo
operar una cuantificacin, universal o existencial, cuando exactamente un elemento
del dominio del discurso satisface su rango.
Demostracin. A continuacin se presenta una demostracin de (1); una demostracin de (2) se propone como ejercicio para el lector. Se procede por doble implicacin.
(x | x = t : )
h azcar sintctico i
x ((x = t) )
h (Bx6); identidad de i
[x := t] .
En el otro sentido suponga `DS(L) [x := t], y note que por el axioma (Bx7) las
frmulas ((x = t) ) y ((x = t) [x := t]) son equivalentes. Entonces se
tiene que `DS(L) (x = t) . Por la regla Generalizacin se obtiene que la
frmula x ((x = t) ) es teorema. Finalmente, esta frmula puede ser escrita
como (x | x = t : ). Entonces:
`DS(L) [x := t] (x | x = t : ).
Para ilustrar el uso de la igualdad, se retoma el concepto de divisibilidad en Z.
Recuerde el predicado de divisibilidad | entre nmeros enteros introducido en la
Seccin 5.5:
a | b : hay un cab Z tal que b = acab .
Para especificar divisibilidad en L, se supone un nico tipo (i.e., nmeros enteros)
y por lo tanto no es necesario asociarle un nombre para identificarlo.
178
Ejemplo 7.5
Se presenta una definicin del predicado de divisibilidad para cualquier par de
nmeros enteros a y b:
a | b x (ax = b)
La relacin de divisibilidad tiene muchas propiedades. Entre ellas que es reflexiva y transitiva. A continuacin se presenta como ejemplo la demostracin de que
la relacin de divisibilidad es reflexiva y se propone para el lector la demostracin
de la transitividad.
Ejemplo 7.6
Se presenta una demostracin de la reflexividad de la relacin de divisibilidad. Es
decir, el objetivo es demostrar:
`DS(L) a (a | a).
Por el Metateorema 7.20 basta con demostrar:
`DS(L) a | a.
Considere la siguiente derivacin:
a | a
h definicin i
c (ac = a)
h (Bx6) i
true.
7.5. La igualdad
179
h definicin i
x (ax = b) a | bc
h Teorema 7.19.2 i
x ((ax = b) a | bc).
Por los metateoremas 7.20 y 7.21, basta con demostrar:
{ax = b} `DS(L) a | bc.
Considere la siguiente derivacin:
a | bc
h definicin i
y (ay = bc)
h suposicin i
y (ay = axc)
h (Bx6) i
true.
Note que deliberadamente, en la ltima derivacin del Ejemplo 7.7, se escoge una
variable y distanta a x en el primer paso de la derivacin. Esto se debe a que esta
variable es distinta a la variable x en la suposicin.
Ejercicios
1. Demuestre que = es reflexivo, i.e., `DS(L) t = t para cualquier trmino t.
2. Demuestre que = es simtrico, i.e, `DS(L) t = u u = t para cualesquiera
trminos t y u.
3. Demuestre que = es transitivo.
4. Sean x una variable, t, u trminos y una frmula. Demuestre que si t y u son
libres para x en , entonces:
`DS(L) (t = u) ([x := t] [x := u]).
180