Matematicadiscreta PDF
Matematicadiscreta PDF
Matematicadiscreta PDF
PRIMERA EDICIÓN
ROBERTO H. FANJUL
Email: [email protected]
ISBN 987-43-9433-1
Derechos Reservados
Quedan reservados todos los derechos para todos los
países. Esta obra es propiedad intelectual de su autor.
Ninguna parte de esta publicación, incluido el diseño
gráfico de la tapa y de las páginas interiores pueden
ser reproducidas, almacenadas o transmitida de ninguna
forma, por ningún medio, sea este electrónico, mecánico,
grabación, fotocopia, o cualquier medio sin la previa
autorización por escrito del propietario de los derechos
del copyright.
2.6.- EL RAZONAMIENTO 59
2.6.1.- FORMAS DE RAZONAMIENTO Y FORMAS DE ENUNCIADOS 62
2.6.2.- LA DECISIÓN EN EL RAZONAMIENTO 65
IV
Sintaxis y Semántica del Lenguaje Formal
CAPITULO I
El estudio de la lógica fue iniciado por los antiguos griegos cuyo sistema educativo
recalcaba la competencia en la filosofía y la retórica. La lógica fue utilizada para formalizar la
deducción, la derivación de nuevas declaraciones verdaderas a partir de suposiciones. Dado un
conjunto de premisas, presumiblemente aceptadas por todos, la deducción de acuerdo a las
reglas de la lógica, asegura que también la conclusión es verdadera. La retórica, el arte del buen
hablar en público, incluye el estudio de la lógica que define las reglas que deben ser practicadas
por todas las personas en todos lados en un debate público.
Las reglas de la lógica fueron clasificadas y denominadas. Una de las más famosas
reglas de la lógica, el silogismo, se presenta de la siguiente forma:
2.- X es un hombre.
Si suponemos que las premisas son verdaderas, las dos primeras oraciones, entonces la Ley del
Silogismo nos asegura que la tercera oración es verdadera independientemente de la identidad
de X. En particular si X es un hombre determinado tal como Sócrates, podemos deducir que
Sócrates es mortal.
El uso de una notación imprecisa, tal como lo es un lenguaje natural, significa que el uso
descuidado de la lógica puede llevarnos a declarar que ciertas declaraciones falsas son
verdaderas, o a declarar que una declaración o proposición es verdadera aún cuando dicha
afirmación de verdad no necesariamente dependa de las premisas. Un ejemplo adecuado al
anterior comentario, es el siguiente silogismo dado por Smullyan:
1
Sintaxis y Semántica del Lenguaje Formal
El marco filosófico de la lógica construida por los Griegos permanece intacto hasta
nuestros días, lo que está demostrado a través del uso inalterable de las palabras griegas
teorema y axioma. Sin embargo, hasta el siglo XIX, la lógica nunca supero a sus orígenes para
convertirse en una herramienta científica, quizás debido a la falta de una notación simbólica
apropiada. Aún más, desafortunadamente la familiaridad con la lógica no es más requerida en
nuestro sistema educacional.
S es P
Los razonamientos se construyen con juicios, así como los juicios se construyen con
conceptos. Un ejemplo de razonamiento muy simple, es el siguiente:
En esta primera parte trataremos principalmente con los juicios. Pero no los llamaremos
juicios, pues esta palabra conserva un fuerte residuo psicológico, puede engañarnos al
sugerirnos que estamos tratando a los juicios como procesos mentales. Emplearemos
indistintamente las palabras proposición y enunciado para referirnos al juicio como realidad
lógica, es decir como entidad formal y vacía de significado real. A menudo daremos un contenido
significativo cualquiera a las proposiciones por razones didácticas, para facilitar la comprensión
de algunos temas volviéndolos más intituibles. Pero la Lógica, ciencia de las formas puras del
2
Sintaxis y Semántica del Lenguaje Formal
Un lenguaje lógico puede ser utilizado de diferentes formas. Por ejemplo, un lenguaje
puede ser utilizado como un Sistema de Deducción; o sea para construir pruebas o refutaciones.
Este uso del lenguaje lógico es conocido como la Teoría de la Comprobación. En este caso, se
especifica un conjunto de hechos denominados axiomas y un conjunto de reglas de deducción
(reglas de inferencia) y el objetivo es determinar cuales son los hechos que se derivan de los
axiomas y de las reglas de inferencia. Cuando utilizamos la lógica como un sistema de
comprobación, no nos interesamos en el significado de las declaraciones que estamos manipu-
lando, pero si estamos interesados en la distribución de estas declaraciones, y específicamente,
en que pruebas o refutaciones pueden construirse. En este sentido, las declaraciones del
lenguaje son visualizadas como hechos fríos, y las manipulaciones involucradas son puramente
mecánicas, hasta el punto tal de que pueden ser realizadas por una computadora. Esto no
significa que encontrar una prueba para una declaración no requiere creatividad, pero donde la
interpretación de la declaración es irrelevante. El uso de la lógica es similar a la práctica de un
juego. Se dan ciertos hechos y reglas, y se supone que los jugadores son perfectos, en el sentido
de que ellos obedecen siempre a las reglas. Ocasionalmente puede suceder que siguiendo las
reglas nos lleve a inconsistencias, en cuyo caso puede ser necesario revisar las reglas.
Uno de los aspectos interesantes de la teoría del modelo es que nos obliga a tener una
definición precisa y rigurosa del concepto de verdad de la estructura. Dependiendo de la
interpretación que uno posea en la mente, la verdad puede tener un significado bastante diferente.
Por ejemplo, que una declaración sea verdad o falsa puede depender de sus parámetros. Una
declaración verdadera bajo todas las interpretaciones de los parámetros es definida como válida.
3
Sintaxis y Semántica del Lenguaje Formal
Una suposición matemática útil (y bastante razonable) es que la verdad de una declaración puede
ser obtenida a partir de la verdad (o falsedad) de sus partes (sub declaraciones). Desde un punto
de vista técnico, esto significa que la verdad de una declaración o proposición está definida por
recursión de la estructura sintáctica de la proposición. La noción de verdad que hemos descrito
(debida a Tarski) formaliza la anterior intuición, y es firmemente justificada en términos de los
conceptos del álgebra y sus correspondientes homomorfismos.
Para resumir, un lenguaje lógico tiene cierta sintaxis y el significado o semántica, de una
declaración o proposición expresada en este lenguaje está dado por una interpretación en su
estructura. Dados un lenguaje lógico y su semántica, podemos tener una o más sistemas de
comprobación para este sistema lógico.
La lógica proposicional es el sistema lógico con la semántica más simple. Sin embargo
muchos de los conceptos y técnicas utilizadas para estudiar la lógica proposicional es
4
Sintaxis y Semántica del Lenguaje Formal
Este argumento lógico tiene tres líneas, y cada línea contiene una afirmación u oración
declarativa. Las oraciones de las líneas 1 y 2 proporcionan las premisas del argumento, y la línea
3 contiene la conclusión. Se puede argumentar contra las premisas y reivindicar que son erróneas.
Sin embargo, tan pronto como las premisas sean aceptadas, la conclusión también debe
aceptarse, porque se sigue lógicamente de las premisas y por lo tanto, el argumento es válido.
Nuevamente existen dos premisas, que corresponden a las líneas 1 y 2 del argumento.
Estas premisas pueden ser verdaderas o falsas en un caso en particular. Sin embargo, si las
premisas son verdaderas, no podemos evitar la conclusión de que el programa de computadora
tiene errores. Esta conclusión se desprende lógicamente de las premisas.
Esta declaración tiene dos partes, que son declaraciones por derecho propio. Son Ala demanda
crece@ y Alas compañías se expanden@. Estas dos afirmaciones están conectadas mediante:
ASi ... entonces@. Es segundo argumento contiene la declaración siguiente:
Nuevamente esta declaración contiene dos partes: A Este programa de computadora tiene
5
Sintaxis y Semántica del Lenguaje Formal
error@ y A la entrada es errónea @. Ambas partes son declaraciones y están conectadas mediante
la palabra AoA.
Para ver que argumentos son correctos y cuáles no, Aristóteles abrevió los enunciados
esenciales de los argumentos, sustituyéndolos por letras. De esta forma el patrón de argumentos
válidos se puede describir concisamente. Siguiendo la convención de Aristóteles, utilizaremos
letras mayúsculas para denotar las declaraciones esenciales. La letra P puede expresar la
declaración A la demanda crece@ , la letra Q puede expresar la declaración @las compañías se
expanden@, y la letra R puede representar la declaración Alas compañías contratan
trabajadores@. Utilizando estos símbolos, podemos expresar el argumento que involucra el
crecimiento de la demanda, de la siguiente forma:
1.-Si P, entonces Q
2.-Si Q, entonces R
3.-Si P, entonces R
Aristóteles incluso dio nombre a este tipo de argumento, lo denomino silogismo hipotético. En
el silogismo hipotético P, Q y R, pueden representar a cualquier declaración. Por ejemplo, si P
representa: AEl gato ve al pez@, Q para AEl gato agarra al pez@ y R AEl gato se come al pez@,
entonces el silogismo hipotético se convierte en:
Las premisas de este argumento pueden ser verdaderas o falsas. El gato puede estar
bien entrenado y nunca hará algo tan desagradable como el de atrapar al pez. Más aún, incluso
si el gato agarra al pez, puede decirse que la comida para gatos es preferible al pez vivo. Sin
embargo, tan pronto como aceptamos las premisas,
no tenemos otra opción que aceptar la conclusión, que es que el gato se come al pez, si ve al pez.
1.- P o Q
2.- No P
3.- P
6
Sintaxis y Semántica del Lenguaje Formal
1.- Si P entonces Q
2.- P
3.- Q
Por ejemplo, si P es A El semáforo se pone en rojo@ y Q es A Los coches paran@, entonces las
premisas A Si el semáforo se pone en rojo, entonces los coches paran@ y AEl semáforo se
pone en rojo@ permite concluir A Los coches paran@.
El alfabeto L del lenguaje formal, es un conjunto conformado por tres conjuntos sin
elementos en común (conjuntos disyuntos). Ellos son:
K={¬}∪{∧,∨,⇒,⇔)
P={(,)}
L=VcKcP
Decimos que una proposición representa a todos los tipos y formas de oraciones
declarativas del lenguaje natural. Decimos que una proposición es simple o atómica cuando no
contiene a otra proposición. Tal es el caso del siguiente ejemplo:
El niño juega
Pero si decimos:
7
Sintaxis y Semántica del Lenguaje Formal
fácilmente pueden distinguirse aquí dos proposiciones: El niño juega, El niño no llora. Ambas
están unidas por la conjunción y. En lógica esta conjunción recibe un tratamiento diferente del
gramatical. Mientras la conjunción gramatical y enlaza adjetivos, sustantivos, verbos, etc. la
conjunción lógica enlaza solamente proposiciones. Cuando tal enlace es de dos o más
proposiciones simples, como en el último ejemplo, el resultado es una proposición compuesta o
molecular.
Definiremos a una proposición compuesta como aquella proposición formada por dos o
más proposiciones simples unidades entre si por alguna partícula lógica. Se establece además
que cualquier proposición simple puede ser simbolizada por las letras minúsculas p, q, r, s, t, etc.
Las letras ante mencionadas, que por convención representan proposiciones, reciben el
nombre de variables lógicas. Así como en las matemáticas se emplean variables como x, y, z,
que pueden recibir cualquier valor (valores numéricos fijos como 1, 345, 5, etc.), así también en
lógica las variables p, q, r, s, t, etc. pueden recibir valores fijos, constantes. Cuáles valores? Los
siguientes dos valores: V y F. Es decir los valores de verdad y falsedad.
Por emplear dos valores esta lógica recibe el nombre de Lógica Bivalente. Hay otras
lógicas que emplean más de dos valores, que reconocen en las proposiciones no sólo su carácter
de verdaderas o falsas sino algunos valores más, como por ejemplo, "más falso que verdadero",
"ni falso ni verdadero". Según el número de valores que emplee, la lógica construida sobre ellos
será trivalente, tetravalente, polivalente, fuzzy o borrosa, etc.
En esta lógica bivalente, pues, distinguiremos elementos cuyo valor es variable (p, q, r,
s, t, etc.) y otros cuya significación es constante (V, F). En este último grupo debemos incluir a las
conectivas, porque todas ellas poseen un sentido invariable.
Ese algo parecerá, en un principio, nada o muy poco: la lógica proposicional quiere saber
que derivaciones formales se obtienen al combinar proposiciones verdaderas o falsas.
También, se establece una vinculación entre las proposiciones "le cuentan un cuento" y
"no se duerme". Esta vez las proposiciones simples no están unidas por la conjunción, sino por la
disyunción. Enumeremos ahora las partículas o conectivos más importantes, con su
correspondiente simbolización, que se emplea en la lógica proposicional y/o simbólica:
8
Sintaxis y Semántica del Lenguaje Formal
∧ Conjunción y
∨ Disyunción o
¬ Negación no
p ∧ q , se leerá p y q
p ∨ q , se leerá p o q
p⇒ q , se leerá : si p, entonces q
Se observará que el último conectivo lógico, "5", actúa sobre una sola proposición, sin
unir, como las cuatro anteriores, dos proposiciones. Por eso la negación, se dice, es una
conectiva unaria o monaria, en tanto que las restantes son conectivas binarias.
9
Sintaxis y Semántica del Lenguaje Formal
(p ⇒ q) ∧ r
p ⇒ (q ∧ r)
Fácil es ver que tiene mayor alcance siempre la conectiva que está fuera del signo de
puntuación. En (1) tiene mayor alcance la implicación fuera del corchete que la conjunción dentro
del corchete. Este, a su vez, tiene mayor alcance que la disyunción y la implicación encerrada en
los paréntesis.
En (2) la negación es la conectiva que afecta más, pues afecta a todo el conjunto. Le
sigue la implicación externa al corchete, pero dentro de la llave. En tercer lugar la conjunción que
une los dos paréntesis. Finalmente éstos, la disyunción y el condicional, sólo afectan a las dos
proposiciones encerradas en los paréntesis respectivos. También se notará que el paréntesis
tiene menor alcance que el corchete y éste que la llave, desde este punto de vista aceptado en la
sintaxis del lenguaje formal.
Muy poca gente trabaja con expresiones completamente entre paréntesis, porque tales
expresiones son largas y con frecuencia difíciles de leer. En particular, los paréntesis externos de
una expresión son casi siempre omitidos. Por lo tanto en lugar de ( p ∧ q ), escribimos p ∧ q y en
lugar de (( p ∧ q) ⇒ ( p ∨ q )) se escribe ( p ∧ q ) ⇒ ( p ∨ q ). Cuando hacemos esto, no debemos
olvidar nunca añadir paréntesis detrás cuando la expresión en cuestión esté compuesta con
alguna otra expresión. Los paréntesis dentro de la expresión también pueden ser omitidos. Para
interpretar correctamente la expresión resultante, se utilizan las llamadas reglas de prioridad o
precedencia. Generalmente, cada conectivo tiene dada una prioridad, y los conectivos con una
prioridad más alta introducen una unión más fuerte que los conectivos con una prioridad más
baja.
El conectivo ¬ tiene siempre la prioridad más alta. Por consiguiente ¬ p ∨ q debe ser
entendida como ( ¬ p) ∨ q y no como ( ¬ p ∨ q). En el caso de los conectivos binarios, la prioridad
más alta esta dada por ∧, seguida de ∨, ⇒, y ⇔, en ese orden. En la expresión p ∧ q ∨ r, por
ejemplo, ∧ tiene la prioridad sobre ∨ cuando forma sub expresiones y debe ser entendida como (p
∧ q)∨ r. De igual modo p ⇒ q ∨ r debe ser entendida como p ⇒ (q ∨ r ), porque ∨ toma prioridad
sobre ⇒ . El conectivo correspondiente a la doble implicación ⇔ recibe la prioridad más baja, lo
que implica que la expresión p ⇔ q ⇒ r debe entenderse como p ⇔ (q ⇒ r).
10
Sintaxis y Semántica del Lenguaje Formal
Disponiendo símbolos o signos del alfabeto L, uno tras otro conformamos series finitas
de signos o cadenas de signos. A estas series las denominamos CADENAS DE CARACTERES.
En los siguientes ejemplos indicamos algunos casos de cadenas de caracteres que son
proposiciones atómicas y/o compuestas.
Ejemplo 1.3.1:
Ejemplo 1.3.2:
CADENA VACÍA: es aquella cadena que no contiene ningún signo o símbolo del alfabeto
L y la denotamos de la siguiente forma: " < > ".
( A { B ) { C es lo mismo que A { ( B { C )
CADENA NEUTRA: La cadena vacía es denominada también cadena neutra a derecha e iz-
quierda para la concatenación ( no altera a la cadena concatenada con
ella ).
A{<>=<>{A=A
LONGITUD DE UNA CADENA: Es igual al número de signos o símbolos que constituyen a dicha
cadena.
Existe un único tipo de cadenas, a partir del alfabeto L, que nos interesa, el denominado
conjunto de EXPRESIONES BIEN FORMADAS (EBF) O FORMULAS PROPOSICIONALES.
11
Sintaxis y Semántica del Lenguaje Formal
Ejemplo 1.4.1:
; ⇓ ⇓ ⇓ C
< 1 2 3 D
œ p 0 V; p 0 F o lo que es lo mismo V d F
REGLA II Las sub reglas siguientes permiten formar nuevas EBF, a partir de
EBF ya existentes.
Ejemplo 1.4.2:
Contra ejemplo: ( p ∧ q ⇒ p)
( p ∧ q ⇒ p) es una variación de (( p ∧ q ) ⇒ p)
12
Sintaxis y Semántica del Lenguaje Formal
Debido a que las EBF son recurrentes, podemos establecer por RECURRENCIA las
propiedades de las EBF.
Para establecer que toda EBF posee una propiedad P determinada, basta con demostrar
que
1.- Todas las EBF iniciales (fijadas por la Regla I) poseen la propiedad P.
2.- Qué la aplicación de la Regla II - 1 a una EBF que posee P, da nacimiento a una
EBF que posee P y que la aplicación de la Regla II - 2 a dos EBF que poseen P,
da nacimiento a una EBF que posee P.
Sea P una propiedad. La etapa 1, equivale a demostrar P para las fórmulas de complejidad 0.
1.- Es cierto para las EBF atómicas: una variable proposicional se escribe sin
paréntesis.
Caso (a): Por hipótesis, G posee un número igual de paréntesis abiertos y cerra-
dos. Luego 5G posee esta propiedad.
Caso (b): G y H poseen un número igual de paréntesis abiertos y cerrados (por ser
EBF de complejidad inferior). Luego ( G * H ) contiene solamente un
paréntesis abierto y uno cerrado, además de los que contienen G y H.
El lenguaje que hemos construido está exento de ambigüedad, esto significa que:
1.- Si una EBF A es de la forma 5B, no existe una EBF B' distinta de B, tal que 5B'
sea lo mismo que A.
13
Sintaxis y Semántica del Lenguaje Formal
No existe un límite superior para una cadena y en consecuencia la simple lectura puede
ser insuficiente. Es necesario buscar un procedimiento seguro, que al cabo de un número FINITO
de etapas no diga, si A es o no es una EBF. Este procedimiento es un ALGORITMO.
Toda EBF que no está reducida a un variable proposicional única contiene un Conector
Principal. Se busca si la cadena tiene un conector que cumpla con esta función. En caso
negativo (y si la cadena no se reduce a una sola variable), la cadena no es una EBF.
En caso afirmativo, se debe verificar, empleando el mismo método, si las cadenas unidas
por el conector principal son EBF, utilizando el mismo método o sea buscando el conector
principal de cada una de las cadenas componentes y así sucesivamente.
14
Sintaxis y Semántica del Lenguaje Formal
1.- En general suprimimos los paréntesis exteriores y escribiremos, por ejemplo " p
w (q w r) " en lugar de " (p ∨ (q ∨ r)) ".
2.- Eventualmente reemplazaremos los paréntesis por corchetes o llaves sin prestar
a esto último ninguna significación particular.
3.- Hasta ahora hemos respetado la convención que consiste, para hablar de una
cadena de caracteres, en escribir dicha cadena entre comillas, por ejemplo,
hemos escrito " " (p ⇒ q) " es una EBF".
Por un abuso de escritura universalmente aceptado, escribiremos en adelan-
te " (p ⇒ q) es una EBF".
OBSERVACIÓN Los signos a, b, c, ..., A, B, ..., *, etc., que solemos introducir para
determinar, ya sea una variable proposicional, ya sea un conector o una
fórmula, no pertenece al alfabeto L del lenguaje artificial; como las co-
millas, pertenecen a la lengua que utilizamos para hablar del lenguaje
artificial y que llamamos metalenguaje. Estos signos son denominados
VARIABLES SINTÁCTICAS. Destaquemos en este sentido, que el
enunciado de las reglas, son en general las variables sintácticas quienes
intervienen.
f0 Una función cuyo resultado es siempre falso, independientemente del valor que
tome la proposición a la cual afecta.
Existen 16 posibles conectores diádicos o binarios, identificados con las letras g0 a g15.
De estos, seis representan a conectivos degenerados correspondientes a verum (función binaria
que siempre retorna el valor verdadero, una tautología binaria g15), falsum (que siempre retorna
el valor falso de la proposición a la cual afecta, g0), p (siempre toma el valor de p, g12), q (siempre
toma el valor de q, g10), 5 p (siempre toma el valor de 5 p, g3), y 5 q (siempre toma el valor de 5
q, g5), dejando 10 conectivos realmente de interés para las aplicaciones lógicas. Por supuesto
dentro de ellos están los conectivos considerados más comunes, como por ejemplo; la disyunción
w ( g14), la conjunción ∧ (g8), la doble implicación ⇔ (g9), y la implicación ⇒ (la cual no es con-
mutativa, por lo tanto existen dos conectivos g11 y g13). Los cinco conectivos restantes se detallan
a continuación:
15
Sintaxis y Semántica del Lenguaje Formal
pxq=T(pwq)v5(pvq)
p x q = T ( p v 5 q )w ( q v 5 p )
p↓q=T5(pwq)=T5pv5q
p / q = T 5 ( p v q )= T 5 p w 5 q
p ¹ q = T 5 ( p ⇒ q )= T p v ( 5 q )
Podemos utilizar los mismos argumentos para determinar los Operadores o Conectivos
Triádicos, aquellos que toman tres operandos o proposiciones simples. Algunos de ellos son de
interés directo sobre un total 256 posibles conectivos. Estos conectivos triádicos son difíciles de
escribirlos como operadores, ya que no pueden ser representados por un simple símbolo infijo.
Describiremos aquellos que son considerados importantes, a saber:
Disyunción Condicionada
[ p, q, r ] = T (q v p ) w ( 5 q v r )
Incompatibilidad Condicionada
[[ p, q, r ]] = T ( q v 5 p ) w ( 5 q v 5 r )
[[ p, q, r ]] = T 5 [ p, q, r ]
L 2 (Mayoría)
El conectivo considerado:
16
Sintaxis y Semántica del Lenguaje Formal
L 2 ( p, q, r )
toma el valor verdadero si y sólo si dos o más de las proposiciones participantes toman el valor
verdadero. L2 significa al menos dos. Este conectivo puede ser expresado de la siguiente forma:
L 2 ( p, q, r )= T ( p v q ) w ( q v r ) w ( r v p )
L 2 ( p, q, r )= T [ q w r , p , q v r ]
L 1 ( p , q, r )= T p w q w r
L 3 ( p , q, r )= T p v q v r
El presente capítulo tiene por función definir una interpretación para el lenguaje
proposicional. Hasta ahora, en efecto, nuestras EBF o expresiones del lenguaje son puras
combinaciones de signos sin sentido alguno. La definición de una interpretación revierte esta
situación y dota al lenguaje de un poder singular de expresión. Este aspecto del lenguaje se
denomina SEMÁNTICA DEL LENGUAJE FORMAL.
Advertencia: A los efectos de poder tratar de la manera booleana la semántica del lenguaje,
confundiremos los valores de verdad (FALSO, VERDADERO) con la dupla (0, 1).
Una distribución de los valores de verdad es una aplicación δ del conjunto V de todas las
variables proposicionales sobre el conjunto Z = {0, 1}.
δ:V→Z
17
Sintaxis y Semántica del Lenguaje Formal
Sea F una fórmula donde figuran los átomos p1, p2, p3, ...., pK. La semántica formal no
dice bajo que condición p1, p2, p3, ...., pK son verdaderos o falsos. Lo que permite deducir, en
cambio, es cómo un Interpretación determinada de p1, p2, p3, ...., pK, es decir, una determinada
distribución de valores de verdad restringida a p1, p2, p3, ...., pK, determina el valor de verdad de
la fórmula F.
Por ejemplo, de la semántica formal se deduce que si una distribución de verdad, asigna
a la variable p el valor 0 y a la variable q el valor 1, el valor de verdad (δ (p) = 0 y δ (q) = 1) de la
fórmula p ⇒ q es 1, el de la fórmula p v q es 0, el de la fórmula 5 p es 1, etc.
En general estos valores se introducen por medio de las 5 (cinco) "tablas de verdad"
correspondientes a cada uno de los conectivos lógicos o proposicionales. Sin embargo, esto
apenas daría la semántica de las fórmulas más simples, conectadas por un solo conectivo,
cuando en realidad es necesario definir la semántica de toda expresión del lenguaje. Sólo la
definición por recurrencia puede satisfacer esta exigencia.
Sea δ una distribución de valores de verdad, de forma tal que asigna a las variables
proposicionales p1, p2, p3, ...., pn, ...., valores tomados del conjunto {0, 1}, que anotaremos de la
siguiente forma δ (p1), δ (p2), ...., δ (pn), ...., denominadas funciones de verdad.
Definir el valor de verdad que toma una fórmula A de acuerdo con las distribuciones δ, es
definir una aplicación Φδ del conjunto F de las EBF sobre el conjunto Z = {0, 1}.
Φδ : F → {0, 1}
18
Sintaxis y Semántica del Lenguaje Formal
Observaciones:
Teorema de Restricción
Demostración
Sea F una EBF y a una variable proposicional, que no figura en F. Sea δ una distribución
de valores de verdad cualquiera. Definimos δ' de la siguiente manera:
1.- F = p , luego a … p y por definición δ' (p) = δ (p) . Por lo tanto, se cumplirá
que : Φδ (p) = Φδ' (p).
Observaciones:
2.- Esta inducción puede servir de esqueleto para las pruebas venideras; el
esquema es el siguiente:
En la expresión matemática x = 2.y, se establece una vinculación tal entre las variables
x e y, que cualquiera sea el valor de y, x asumirá un valor equivalente al valor de y multiplicado
19
Sintaxis y Semántica del Lenguaje Formal
por 2. El valor de x, pues, depende del valor de y. Eso quiere expresarse cuando se afirma que
x es una función de y.
También la lógica estudia la relación funcional que existe entre las variables
proposicionales y/o EBF. Consideremos el siguiente ejemplo:
que simbolizamos como p v q, es una fórmula o EBF molecular. Será como toda proposición,
verdadera o falsa. A la lógica le interesa establecer de qué modo el valor de verdad (V o F) de las
proposiciones moleculares depende, es una función, de los valores de verdad de las
proposiciones que componen a dichas proposiciones moleculares. En nuestro ejemplo, la
proposición compuesta será verdadera cuando las proposiciones "las naranjas maduran", "el
invierno se avecina" sean ambas verdaderas. Bastará que una de ellas sea falsa para que la
proposición compuesta también lo sea. Y si son falsas las dos proposiciones atómicas, con mayor
razón será también falsa la proposición molecular. Cuando el valor de verdad de una proposición
compuesta depende de los valores de verdad de las proposiciones que la componen, estamos
ante una función de verdad.
En rigor, para esta lógica hay sólo dos proposiciones; una verdadera, otra falsa. Las
infinitas proposiciones posibles pueden reducirse a dos grupos. el de las verdaderas, el de las
falsas. Todas las verdaderas son equivalentes. Todas las falsas son equivalentes. La lógica
bivalente no distingue (pues no se ocupa del sentido) entre:
20
Sintaxis y Semántica del Lenguaje Formal
La Tierra es cuadrada
Arriba dijimos que cuando el valor de verdad de una proposición molecular depende de
los valores de verdad de las proposiciones que la componen, estamos ante una función de verdad.
Pero no es imprescindible que una función de verdad sea una proposición molecular. Un
esquema proposicional más simple, como 5 p, por ejemplo, también es función de verdad.
Veamos ahora con más detalles cómo un esquema proposicional realizado con una o
más variables y conectivos es función de verdad de la proposición o proposiciones que la
componen. Para ello formamos una Tabla de Verdad. Esta tabla se compone de dos partes. Una,
ubicada a la izquierda, es la columna de referencia. Se coloca allí todos los valores posibles que
pueden asumir una o más proposiciones. Si se trata de una sola proposición, la columna de
referencia será:
p q
V V
V F
F V
F F
21
Sintaxis y Semántica del Lenguaje Formal
p q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
p 5p
V F
F V
En el ejemplo del apartado anterior, hemos mostrado cómo 5 p es una función de verdad.
Pero hemos definido también la negación. En efecto, la columna de la derecha, la columna matriz
donde consignamos los resultados del cálculo, define al elemento " 5 ", operador monódico.
Daremos a continuación las tablas de verdad de los restantes conectivos lógicos o functores de
verdad.
22
Sintaxis y Semántica del Lenguaje Formal
p q p∧q
V V V
V F F
F V F
F F F
Es preciso distinguir en este conectivo dos sentidos muy diferentes que también posee la
" O " en el lenguaje español. Veamos los dos ejemplos siguientes:
En el último ejemplo, las dos proposiciones vinculadas por "O" son incompatibles. Una excluye a
la otra y lo mismo ocurre al revés. Para que la proposición molecular sea verdadera, pues, es
preciso que una de las proposiciones componentes sea falsa y es preciso también que otra sea
verdadera. En el primer ejemplo, en cambio no hay incompatibilidad entre ambas proposiciones.
"Juan es escritor" y "Juan es músico" pueden ser ambas verdaderas. Lo cual no ocurre con "La
mesa es circular" y "La mesa es rectangular".
p q pwq p q pxq
V V V V V F
V F V V F V
F V V F V V
F F F F F F
23
Sintaxis y Semántica del Lenguaje Formal
* El bicondicional o equivalencia :
p q p/q
V V V
V F F
F V F
F F V
Lo que afirma el bicondicional es que p es condición necesaria y suficiente para q, del mismo
modo que q es condición necesaria y suficiente para p. En
En estos dos ejemplos la tabla nos informa que existe equivalencia. El primero, en efecto, es un
ejemplo de la última línea horizontal (F, F); el segundo lo es de la primera línea (V, V). Los
resultados muestran, en ambos casos, V. A nadie se le escapará que dicha equivalencia está
lejos de cumplirse en el campo de las significaciones de las proposiciones en cuestión. Pero
debemos recordar una vez más que la significación no es tenida en cuenta por la lógica de las
proposiciones. )De qué equivalencia hablamos, entonces?. Pura y simplemente de ésta: F es
equivalente a F, por eso las dos proposiciones del primer ejemplo dan V; igualmente V es equiva-
lente a V, por eso las dos proposiciones del segundo ejemplo conducen al resultado V.
* El condicional o implicación:
Este conectivo presenta algunas dificultades, pues su equivalencia con el giro gramatical
"Si ...... entonces" es solo parcial. En efecto, "Si ..... entonces" en el lenguaje español permite
conectar dos proposiciones en muy diversos sentidos. Los siguientes ejemplos son algunos de
ellos:
1 Si es mamífero, es vertebrado.
Todos son enunciados hipotéticos. En la estructura de estos enunciados hay, al menos, tres
elementos importantes: (a) el antecedente, es decir la proposición comprendida entre el signo
"Si" y el signo "entonces"; (b) el consecuente, o sea la proposición que sigue al signo "entonces";
(c) la afirmación de que siendo verdadero el antecedente, el consecuente también lo será. Es
24
Sintaxis y Semántica del Lenguaje Formal
decir que estos enunciados afirman, no que el antecedente sea verdadero, sino que en caso de
serlo también lo será el consecuente. Esto quiere afirmarse cuando se dice que el antecedente
implica al consecuente.
Ahora bien, esa implicación es de naturaleza múltiple. Los ejemplos antes mencionados
son algunos modos de implicación. Los dos primeros establecen una relación entre dos órdenes
de la realidad; 1 señala un vínculo permanente entre dos fenómenos; 2 indica no sólo un nexo
constante entre dos hechos sino que además la producción del segundo por el primero, es decir
apunta a un nexo causal. 3 alude no ya a una vinculación entre dos fenómenos reales sino
posibles. Es más sugiere que el antecedente es falso, que no es un hecho. De ahí el nombre de
contra fácticos que reciben estos enunciados hipotéticos formulados de un modo subjuntivo. Los
órdenes que enlaza 4 son de distinta naturaleza; uno pertenece al ámbito de la conciencia, el otro
forma parte de la realidad. 5 muestra una implicación completamente distinta porque no se refiere
ni a la realidad ni a un hecho de conciencia; establece un nexo entre dos órdenes formales,
ideales. Aquí el antecedente implica necesariamente, forzosamente al consecuente.
Pero entre tantas diferencias (y otras muchas que aún pueden señalarse) de sentido que
tiene "Si ..... entonces" en un idioma natural, como el español, habrá quizás un elemento común,
un parentesco básico afín a esos múltiples sentidos. La lógica, cuando emplea el signo " ⇒ "
pretende representar ese núcleo descarnado del concepto de implicación, sin procurar recoger en
él, las múltiples significaciones que le otorga el lenguaje natural.
Cualquiera sea el ejemplo de condicional que tomemos, lo que allí se afirma básicamente
es que aceptando la verdad del antecedente, el consecuente no puede ser falso. Es decir que
al afirmar que p ⇒ q, suponemos que p v 5 q será una proposición falsa. En la oración 1, por
ejemplo, decir "Es mamífero y no vertebrado" sería precisamente lo opuesto de lo que el
condicional quiso afirmar. Ahora bien, si la oración "Es mamífero y no vertebrado" es lo opuesto
de "Si es mamífero entonces es vertebrado", una proposición equivalente a este último con-
dicional, será la negación de "Es mamífero y no vertebrado". En símbolos lógicos, tal negación
se expresa de la siguiente forma: 5 (p v 5 q). Esta fórmula es, efectivamente, equivalente a p ⇒
q. Por lo tanto, en la tabla de verdad ambas fórmulas tendrán igual matriz de valores de verdad.
Veamos:
p q ¬q p∧¬q ¬ (p ∧ ¬ q) p⇒q
V V F F V V
V F V V F F
F V F F V V
F F V F V V
Esta vez hemos utilizado la misma columna de referencia para calcular el valor de varias
proposiciones. Como queríamos establecer el valor de 5 (p v 5 q), empezamos calculando 5 q,
luego p v 5 q. Para el cálculo de Esta última fórmula usamos como referencia la columna de p y
la de 5 q; se tuvo en cuenta, asimismo, la definición de conjunción. Una vez resuelto p v 5 q, es
fácil resolver también su negación. Para ello simplemente se invierten los valores de verdad de la
fórmula p v 5 q.
25
Sintaxis y Semántica del Lenguaje Formal
donde símbolo puede ser reemplazado por cualquier secuencia de N símbolos. Reglas de la
forma:
donde esta regla significa que símbolo puede ser reemplazado por cualquiera de los símbolos del
lado derecho de la regla. Los símbolos que aparecen en el lado izquierdo son denominados no
terminales, mientras que los símbolos que aparecen a la derecha de la regla son denominados
terminales. Los no terminales representan gramaticalmente clases mientras que los terminales
son palabras del lenguaje. Comenzando en un no terminal inicial, rescribir un no terminal
reemplazándolo con una secuencia de símbolos del lado izquierdo de la regla. Esta construcción
finaliza cuando la secuencia de símbolos consiste únicamente de terminales. Tal cadena de
símbolos está correcta sintácticamente o bien formada en el lenguaje definido por la
gramática.
Definición 1.12.1: Una fórmula en el cálculo proposicional es una cadena generada por la
siguiente gramática:
1.- fórmula
2.- fórmula op fórmula
3.- fórmula v fórmula
4.- p v fórmula
5.- p v q,
p⇒q≡5p⇒5q
26
Sintaxis y Semántica del Lenguaje Formal
≡
↓ ↓
⇒ ⇒
↓ ↓ ↓ ↓
p q 5 5
↓ ↓
p q
1.- fórmula
2.- fórmula ≡ fórmula
3.- fórmula ⇒ fórmula ≡ fórmula
4.- p ⇒ fórmula ≡ fórmula
5.- p ⇒ q ≡ fórmula
6.- p ⇒ q ≡ fórmula ⇒ fórmula
7.- p ⇒ q ≡ 5 fórmula ⇒ fórmula
8.- p ⇒ q ≡ 5 p ⇒ fórmula
9.- p ⇒ q ≡ 5 p ⇒ 5 fórmula
10.- p⇒q≡ 5 p⇒5q
* Considerar la raíz.
* Considerar el sub-árbol izquierdo.
* Considerar el sub-árbol derecho.
≡ ⇒ pq ⇒ 5 p 5 q
⇒p≡q5 ⇒p5q
Esta notación es denominada Notación Polaca luego que el grupo de lógicos comandados por
J. Lukasiewicz la inventaran a principios de siglo. La notación es difícil de interpretar para muchas
personas y no es muy utilizada, excepto en la representación interna de una expresión en una
computadora y en algunas operaciones de cálculo. La ventaja de la notación polaca es que una
expresión puede ser ejecutada o calculada en un orden lineal a medida que aparecen los
símbolos.
27
Sintaxis y Semántica del Lenguaje Formal
Las dos fórmulas siguientes son ahora representadas por distintas cadenas y de esa forma no
existirá ambigüedad:
(p ⇒ (q / (5 (p ⇒ (5 q)))))
El problema con los paréntesis es que cargan demasiado a las fórmulas y las hacen difícil de
leerlas.
5 , v , w , ⇒ , ⇐ ,⇔ ,≡
Consideremos las expresiones aritméticas. Dada una expresión E tal como por ejemplo
la siguiente a ( b + 2, podemos asignar valores a los elementos a y b y luego evaluar la
expresión. Por ejemplo si a = 2 y b = 3 entonces la evaluación de E es de 8 . Debemos ahora
definir un concepto análogo para las fórmulas booleanas o expresiones lógicas, o más bien las
denominadas interpretaciones booleanas, que por razones históricas utilizan terminologías
diferentes.
Antes de seguir adelante debemos incluir una regla más dentro de la sintaxis de las
fórmulas proposicionales y es aquella que considera a dos proposiciones atómicas constantes
falsas y verdaderas, que de algún modo es similar a la valorización de las expresiones lógicas
o de las proposiciones. En consecuencia tenemos que:
Definición 1.12.2.1:Sea A una fórmula proposicional y sea el conjunto {p1, ... , pn} de
proposiciones o átomos que aparecen en A. Una Interpretación para A es la siguiente función:
o sea que v asigna uno de los valores de verdad F o V a la fórmula A de acuerdo a los valores
de verdad asignados en las diferentes tablas de verdad para cada uno de los conectivos lógicos.
(p ⇒ q) ≡ (5 q ⇒ 5 p)
y la interpretación siguiente :
v(p) = F , v(q) = V
v (p ⇒ q) = V
28
Sintaxis y Semántica del Lenguaje Formal
v (5 q) = F
v (5 p) = V
v (5 q ⇒ 5 p) = V
v ((p ⇒ q) ≡ (5 q ⇒ 5 p)) = V
Ya que cada fórmula A está representada por un único árbol de formación, v está bien definida.
Ello significa que dado un A y una interpretación v, v(A) tiene exactamente un valor cuando la
definición inductiva se lleva a cabo. Si tratamos de usar la definición sobre la cadena p ⇒ q ⇒ p
sin el concepto de árbol de formación, entonces para v(p) = F y v(q) = V, la interpretación v(A)
podrá evaluarse como V o F dependiendo del orden de la evaluación :
v ( p ⇒ ( q ⇒ p )) = V
v (( p ⇒ q ) ⇒ p ) = F
Como un punto técnico, es conveniente decir que v es una interpretación para A si v asigna
valores al menos a los átomos de A. Si se asigna a más átomos que aquellos que aparecen en
A, podemos ignorar las asignaciones extras cuando computamos v(A).
Hemos empleado las tablas de verdad para mostrar cómo una función de verdad
depende efectivamente de los valores de verdad de la proposición o de las proposiciones que la
componen. En la columna izquierda, que llamamos de referencia, colocamos todos los valores de
verdad posibles que pueden asumir dichas proposiciones componentes. En la columna derecha,
que llamamos matriz, consignamos los resultados del cálculo.
En segundo lugar, hemos utilizado las tablas de verdad para definir cada una de los
conectivos lógicos. Pero aún existen otros usos más que haremos de las tablas de verdad:
Cualquier esquema proposicional que enlace sus proposiciones componentes con una o
más conectivos lógicos, ya lo indicamos, tiene un valor de verdad determinado. La determinación
de dicho valor puede hacerse recurriendo a la tabla. En el apartado anterior vimos dos ejemplos
sencillos, 5 p y 5 (p v 5 q), cuyos valores de verdad calculamos usando como punto de partida la
columna de referencia. Aunque la complejidad de la fórmula aumente, la tabla nos permitirá en
forma mecánica establecer cuáles valores corresponden a la misma.
5 [(p ⇒ q) ≡ (p v q)]
Para ello seguimos este orden: calculamos primero los conectores de menor alcance (el
condicional y la conjunción), luego el que los sigue en mayor alcance (el bicondicional) y final-
mente el de mayor alcance (la negación). Las matrices primera y segunda (todas las matrices se
colocan debajo del conectivo, pues él determina los valores de la fórmula) se calcularon te-
29
Sintaxis y Semántica del Lenguaje Formal
niendo en cuenta la columna de referencia; la tercer matriz está construida en base a las dos
primeras y la cuarta matriz en función de la tercera. Como se verá, es imprescindible para poder
hacer el cálculo de valores de verdad tener presente las definiciones de los diferentes conectivos
o conectores lógicos.
p q (p ⇒ q) (p v q) (p ⇒ q) ≡ (p v q) 5[(p⇒ q) ≡ (pvq)]
V V V V V F
V F F F V F
F V V F F V
F F V F F V
p q (p w q) (p ⇒ q) ≡ (5 p w q) p v (5 p v q)
V V V V V V F F
V F V F V F F F
F V V V V V F V
F F F V V V F F
Si se observan los valores de verdad que muestran las tres EBF (dichos valores están
ubicados en todos los casos debajo del conectivo de mayor alcance) se percibirá una notable
diferencia entre ellos; el primero es verdadero algunas veces (tres veces) y falso otra; el segundo
es siempre verdadero y el tercero es siempre falso. Los enunciados o fórmulas del primer tipo,
aquellos que a veces son falsos y otros verdaderos, reciben el nombre de INDEFINIDOS. Los del
segundo tipo, siempre verdaderos, se denominan TAUTOLOGÍAS; los del tercer tipo, siempre
falsos, son denominados CONTRADICCIONES.
Ahora podemos definir a la Tautología como aquella fórmula cuyo dominio es pleno, o en
la que todas las interpretaciones son verdaderas. Esto también suele denominarse como que el
modelo es válido. A la contradicción como aquella fórmula que tiene un dominio vacío, o cuando
todas las interpretaciones son falsas, suele decirse que la fórmula no es satisfacible o
satisfecha. A la indefinida (o sintética) como una fórmula cuyo dominio es parcial, es decir que
incluye V en su avaloración, pero también F, o cuando las interpretaciones son algunas falsas y
30
Sintaxis y Semántica del Lenguaje Formal
otras verdaderas, en cuyo caso diremos que la fórmula es satisfacible o que está satisfecha.
V V V V F
V F F V F
F V F V F
F F F V F
El segundo ejemplo, en cambio, algo nos informa sobre la realidad cuando es in-
terpretado. Efectivamente, si se que p v q es verdadero, si se que "El zorzal silba y el loro
habla" es verdadero, tengo un conocimiento del modo de ser de la realidad en cuestión. No
ocurre aquí, lo que ocurría con p w 5 p. Pues podíamos estar seguros de que esta última
expresión era absolutamente verdadera y sin embargo nada conocer de la realidad que hablaba.
La verdad de p v q es más fuerte que la de p w 5 p cuando ponemos en vinculación ambas
fórmulas con la realidad. La tautología parece ser un esquema no apto para retener significados
del mundo real. La contradicción es un esquema incompatible con la realidad. Las fórmulas
indefinidas, en cambio, pueden expresar una significación real.
Para terminar este punto recordemos que nuestro propósito era mostrar cómo la tabla de
verdad sirve para determinar el carácter de las proposiciones, es decir determinar en forma
indudable, si cualquier fórmula, EBF o enunciado es contradictoria, tautológica o indefinida.
Hemos visto varios ejemplos. Si al resolver el valor de verdad de una fórmula nos damos con que
su matriz tiene dominio pleno estamos ante una tautología; si el dominio es vacío, ante una
contradicción y si es parcial estamos ante una fórmula indefinida o sintética.
Veamos cómo la tabla de verdad sirve también para descubrir relaciones diferentes entre
dos fórmulas cualesquiera. Observemos los siguientes dos ejemplos:
p⇒q y 5 (5 p w q)
A simple vista no podemos saber qué relación guardan ambas fórmulas entre sí. Pero
31
Sintaxis y Semántica del Lenguaje Formal
haciendo la tabla de verdad de ambas esa relación puede mostrarse claramente a través de ella.
Salta a la vista que la matriz de la segunda fórmula (ubicada bajo la negación fuera del
paréntesis) es inversa punto por punto a la matriz de la primera fórmula; cuando aquella es F, ésta
es V; cuando aquella es V, ésta es F. Decimos, en casos así, que una fórmula es la negación de
la otra, que una contradice a la otra y viceversa. En suma, que la relación entre ambas es la
contradicción.
p q p⇒q 5 (5 p w q)
V V V F V
V F F V F
F V V F V
F F V F V
Pero existen otras relaciones posibles. Consideremos las siguientes dos expresiones lógicas:
pvq y p≡q
p q pvq p≡q
V V V V
V F F F
F V F F
F F F V
p q (p v q) ⇒ (p ≡ q)
V V V V V
V F F V F
F V F V F
F F F V V
32
Sintaxis y Semántica del Lenguaje Formal
Pero existe una relación posible entre dos fórmulas que para nosotros tendrá mayor
utilidad en los cálculos a realizar en otros apartados. Como en los dos casos anteriores, también
aquí la tabla pone al descubierto esta nueva relación.
p q 5 (p v q) (5 p w 5 q)
V V F F
V F V V
F V V V
F F V V
Las matrices de ambas fórmulas son idénticas, son equivalentes. Es decir que si
colocamos entre ambas el signo del conectivo bicondicional o equivalencia, obtendremos una
matriz tautológica, una matriz que sólo tendrá V. Lo mismo ocurrirá con este segundo ejemplo :
5 (p w q) y (5 p v 5 q).
p q 5 (p w q) (5 p v 5 q)
V V F F
V F F F
F V F F
F F V V
Ambas fórmulas son, pues, equivalentes. Es decir que la fórmula compuesta por estas últimas:
5 (p w q) ≡ (5 p v 5 q)
es tautológica. Y también la resultante de unir las dos del primer ejemplo con el bicondicional:
5 (p v q) ≡ (5 p w 5 q)
Ambas tautologías, como todas las tautologías, son Teoremas de la lógica proposicional.
Pero estas equivalencias tienen para nosotros un particular interés. Porque, como se
puede observar, no sólo son equivalentes dos fórmulas entre sí en los ejemplos dados. Existen
en ellas, además, un detalle importante: emplean conectivos diferentes y a pesar de ello sus
33
Sintaxis y Semántica del Lenguaje Formal
matrices son idénticas. Ello hace que nos preguntemos, en una forma más general: )toda fórmula
expresada por un conectivo tiene su equivalente en otra expresión bien formada que utiliza un
conectivo diferente?. La respuesta a ello es afirmativa. Veamos ahora a qué reglas debe
someterse el traslado de una fórmula a su equivalente con un conectivo diferente. Empecemos
con la conjunción y con la disyunción.
(a).- Para pasar de una expresión expresada en conjunción a otra expresión equivalente
expresada en disyunción: primero cambiar el valor del conjunto (si el conjunto está
negado, pasa a ser afirmativo y viceversa). Segundo, cambiar también el valor de las
proposiciones componentes.
Esto es lo que se hizo en el ejemplo 5 (p v q). Primero se cambió el valor del conjunto y
segundo se invirtió también el de las proposiciones componentes, p y q; el resultado fue
la fórmula equivalente: (5 p w 5 q). Es importante destacar que la misma regla se emplea
para pasar de disyunción a conjunción. Es lo que vimos en el segundo teorema de De
Morgan. La fórmula original era 5 (p w q). Siguiendo iguales indicaciones que en el caso
anterior, resulta la fórmula equivalente expresada en conjunción : (5 p v 5 q).
Si se construyen las tablas de las siguientes equivalencias, se comprobará que todas
ellas son tautologías, o teoremas:
( p v q ) ≡ 5 (5 p w 5 q)
(5 p v q ) ≡ 5 ( p w 5 q)
5 ( p v 5 q) ≡ (5 p w q)
( p w q ) ≡ 5 (5 p v 5 q)
(b).- Para pasar de una fórmula expresada en conjunción a otra fórmula equivalente, pero
expresada en condicional, la regla que utilizamos es distinta a la anterior. Esta vez
debemos, primero cambiar el valor del conjunto y, segundo, cambiar el valor del segundo
miembro. Por ejemplo, (p v q) será equivalente a la expresión 5 (p ⇒ 5 q), lo cual se
confirma fácilmente con la siguiente tabla:
p q (p v q) 5 (p ⇒ 5 q)
V V V V
V F F F
F V F F
F F F F
La misma regla nos permite pasar de condicional a conjunción. Es lo que se hizo cuando
definimos la implicación (p ⇒ q) como sinónimo o equivalente de la expresión 5 (p v 5 q).
(c).- Para pasar de disyunción a condicional o viceversa, la regla indica simplemente: cambiar
solamente el valor del primer miembro. La proposición (p w q), por ejemplo, será
equivalente a (5 p ⇒ q).
34
Sintaxis y Semántica del Lenguaje Formal
p q (p w q) (5 p ⇒ q)
V V V V
V F V V
F V V V
F F F F
(3) (p w q) ≡ (q w p) Conmutación de w
(4) (p v q) ≡ (q v p) Conmutación de v
(8) (p ⇒ q) ≡ (5 q ⇒ 5 p) Transposición
(9) p ≡ (p w p) Tautología
35
Sintaxis y Semántica del Lenguaje Formal
Consideramos una lógica con tres valores de verdad designados por las letras "V", "F"
y "I" (Verdadero, Falso, Indeterminado), con los mismos conectivos lógicos: Negación "5",
Conjunción "v", Disyunción "w", Condicional "⇒" y Bicondicional "/", definidos por las tablas de
verdad siguientes:
V I V V V V V V
I F V I V I I I
F V V F V F F F
I V V I I I
I I I I I I
I F I F I I
F V V F V F
F I I F V I
F F F F V V
36
Sintaxis y Semántica del Lenguaje Formal
37
Sintaxis y Semántica del Lenguaje Formal
11.- Traduzca las siguientes oraciones al cálculo proposicional y dé el alcance de todas las
conexiones lógicas:
(a) María practica básquetbol, pero su hermano fútbol y voley
(b) Si 5 es mayor que 3, y 3 es mayor que 2, entonces 5 es mayor que 2
(c) Si no llueve, iremos al cine o al teatro
(d) Me curaré, si tomo los remedios y hago reposo.
(e) La extracción de minerales es provechosa si la concentración de mineral es alta
pero sólo si la distancia hasta el mercado es corta.
38
Sintaxis y Semántica del Lenguaje Formal
13.- Encuentre la negación de los siguientes enunciados aplicando las equivalencias lógicas
correspondientes:
a) Juan estudia Ingles y Computación
b) | - 3 | = 3 y 2 ≥ 3
c) Juan y Javier aprobaron el examen.
d) Podemos comprar esta casa o comprar un auto
e) Es suficiente que sea feriado para que no trabaje.
f) Si no hay sol, no iré a la pileta.
g) Si no hay paga, no hay trabajo
h) El programa es legible solamente si está bien estructurado.
i) El público se dormirá cuando el presidente de la sesión dicte la conferencia
j) Nos veremos en el parque en caso que no llueva
k) Si llueve, nos reuniremos en el club o en la casa de María
l) Solicitaré un préstamo, si viajo a Brasil o a Chile.
m) Terminar de escribir mi programa antes del almuerzo es necesario para que juegue
al tenis esta tarde.
n) María puede subir a la motocicleta de Luís sólo si usa el casco
14.- Determinar si las expresiones lógicas del Problema Nº 4, son las denominadas
expresiones bien formadas (EBF), utilizando las Reglas de buena formación.
15.- Determinar si las expresiones lógicas del Problema Nº 6, son las denominadas
expresiones bien formadas (EBF), utilizando las Reglas de buena formación.
16.- Determinar si las expresiones lógicas del Problema Nº 7, son las denominadas
expresiones bien formadas (EBF), utilizando las Reglas de buena formación.
18.- Aunque normalmente utilizaremos "implica" y "si ..... entonces" para describir una
implicación, en la práctica surgen otras palabras y frases como las de los siguientes
ejemplos.
Sean p, q y r las siguientes proposiciones:
Traducir cada una de las siguientes proposiciones a símbolos usando las letras p, q, r y
los conectivos lógicos.
39
Sintaxis y Semántica del Lenguaje Formal
Notar la ambigüedad del punto (f); hay dos respuestas distintas, cada una con su propia
validez. ¿Ayudaría la puntuación?
20.- (a) Demostrar que x = -1 es un contraejemplo de "(x + 1)2 ≥ x2 para toda x ∈ ℜ"
(b) Encontrar otro contraejemplo.
(c) ¿Puede servir de contraejemplo cualquier número no negativo? Justifique su
respuesta.
21.- Construir la tabla de verdad para cada una de las siguientes expresiones bien formadas
lógicas siguientes:
(a) (n ∨ c) (b) (n ∧ c)
(c) (¬ n ∧ ¬ c) (d) (n ⇔ (¬ w ∨ c))
(e) ((w ∨ ¬ c) ⇒ n) (f) ((w ∨ n) ⇒ (w ⇒ ¬ c))
(g) ((w ⇔ ¬ n) ⇔ (n ⇔ c)) (h) {(w ⇒ n) ⇒ [(n ⇒ ¬ c) ⇒ (¬ c ⇒ w)]}
22.- Construir la tabla de verdad para cada una de las siguientes expresiones bien formadas
lógicas siguientes:
23.- Construir la tabla de verdad para cada una de las siguientes expresiones bien formadas
lógicas siguientes:
(a) (p ∧ q) ⇒ r (b) (p ⇒ r) ⇒ q
(c) ¬ p ⇔ (q ∨ r) (d) ¬ (p ⇔ (q ∨ r))
(e) ¬ (p ∨ q) ∧ r
24.- Construir la tabla de verdad para cada una de las siguientes expresiones bien formadas
lógicas siguientes:
40
Sintaxis y Semántica del Lenguaje Formal
29.- Transformar las siguientes expresiones lógicas en otras equivalentes con la conectiva
que se indique en cada caso y simplificar si es posible:
(a) (¬ p ⇒ q) ⇔ (p ∨ q) a conjunción
(b) (p ⇔ q) ⇔ [(p ⇒ q) v (q ⇒ p)] a conjunción
(c) (p ⇒ q) ⇔ r a disyunción
(d) ¬ (¬ p ∨ q) a condicional
(e) (p ∨ q) ∧ (p ⇒ q) a disyunción (f) (¬ p ∧ q) ⇒ (¬ q ∨ p) a conjunción
(g) (p ⇒ ¬ q) ∧ (p ∨ ¬ q) a condicional (h) (p ∧ ¬ q) ⇔ ¬ (¬p ∨ q) a conjunción
(i) (¬ p ∧ q) ⇔ ¬ (¬ p ⇒ ¬ q) a condicional
30.- Utilizando las propiedades de la lógica formal, simplificar las siguientes expresiones y/o
expresarlas únicamente como disyunciones:
31.- Utilizando las propiedades de la lógica formal, simplificar las siguientes expresiones y/o
expresarlas únicamente como conjunciones:
32.- Utilizando las propiedades de la lógica formal, simplificar las siguientes expresiones y/o
expresarlas únicamente como conjunciones:
(a) (p ⇒ q) ⇒ (¬ q ⇒ p) (b) ¬ (p ⇒ q) ⇔ (¬ q v p)
(c) (p ∨ q) ⇔ (p ⇒ q) (d) (p ⇔ q) ⇒ ¬ (p ⇒ q)
(e) [(p ⇒ q) ∧ ¬ q] ⇒ ¬ p (f) [(p ⇒ q) ∧ ¬ p] ⇒ ¬ q
(g) [(p ⇒ q) ∨ (q ⇒ p)] (h) p ∧ ¬ [¬ (p ⇒ q) ∨ q]
(i) ¬ [(p ∨ q) ⇔ (p ⇒ q)] ⇔ [¬ (p ∨ q) ⇔ (p ⇒ q)]
(j) p ⇒ (p ∨ q)
41
Sintaxis y Semántica del Lenguaje Formal
a) ¬ ((p ∧ q) ∨ p) ≡ (¬ p ∧ q)
b) (p ∧ (q ∧ (r ∧ ¬ p ))) ≡ F , donde F es la constante proposicional “Falso”
c) ((¬ q ∨ (q ∧ r )) ∨ ¬ r ) ≡ V , donde V es la constante proposicional “Verdadero”
d) ¬ (¬ p ∨ ¬ ( r ∨ s )) ≡ (( p ∧ r ) ∨ ( p ∧ s ))
e) (( p ∨ r ) ∧ ( q ∨ s )) ≡ (( p ∧ q ) ∨ ( p ∧ s ) ∨ ( r ∧ q ) ∨ ( r ∧ s ))
f) (( p ⇒ r ) ∧ ( q ⇒ r )) ≡ (( p ∨ q ) ⇒ r )
g) (( p ⇒ q ) ∧ ( p ⇒ r )) ≡ ( p ⇒ ( q ∧ r ))
h) (( p ∧ q ) ⇒ r ) ≡ ( p ⇒ ( q ⇒ r ))
i) ( p ⇒ q ) ≡ (( p ∧ ¬ q ) ⇒ F)
j) ( p ∨ ( p ∧ ( p ∨ q )) ≡ p
k) ( p ∨ q ∨ ( ¬ p ∧ ¬ q ∧ r )) ≡ ( p ∨ q ∨ r )
l) ( p ∧ (( ¬ q | ( r ∧ r )) ∨ ¬ ( q ∨ (( r ∧ s ) ∨ ( r ∧ ¬ s ))))
( II ) Simplifique las siguientes expresiones. Establezca cada ley que use.
a) (( p ∧ V ) ∧ ( q ∨ F ))
b) ( p ∧ ( q ∧ ( r ∧ ¬ p )))
c) (( p ∧ V ) ∧ ( q ∧ ¬ p ))
d) (( p ∨ ( q ∧ s)) ∨ ( ¬ q ∧ s ))
e) ¬ (( p ∧ ¬ ( q ∨ ¬ r ))
f) ( p ∨ ¬ ( p ∧ ¬ (q ∨ r )))
g) ((¬ p ∨ q ) ∧ ( p ∧ ( p ∧ q )))
h) (¬(q∧r∧¬q)∧p)
i) ((( p ∨ q ) ∧ ( p ∨ ¬ q )) ∨ q )
j) (¬ ( p ∨ q ) ∨ (( ¬ p ∧ q ) ∨ ¬ q ))
k) (( p ⇒ q ) ∧ ( ¬ q ∧ ( r ∨ ¬ q )))
==============================
42
Sintaxis y Semántica del Lenguaje Formal
¬¬ p ≡ p Doble negación
( p ∧ q ) ≡ (q ∧ p) Leyes conmutativas
( p ∨ q ) ≡ (q ∨ p)
( p ⇒ q ) ≡ (q ⇒ p)
( p ⇒ q) ≡( ¬ q ⇒ ¬ p) Ley de la Contrarecíproca
(( p ∧ q ) ∨ p ) ≡ p Leyes de Absorción
(( p ∨ q ) ∧ p ) ≡ p
43
Decisión en el Lenguaje Formal
CAPITULO II
Anexado al Sistema Axiomático se admite la lógica bivalente, con cuyas leyes es posible
demostrar los teoremas de la teoría. Cuando se sustituyen las variables o términos primitivos por
significados concretos, se tiene una interpretación del sistema axiomático; si esta interpretación
es tal que los axiomas se convierten en proposiciones verdaderas, entonces se tiene un modelo
del sistema axiomático. En este caso, todo lo demostrado en abstracto en el sistema es válido
para el modelo, y nada hay que probar en particular.
Ejemplo 2.1.1.
RdAxA
ii) axiomas
A1: R es reflexiva en A.
A2: R es antisimétrica en A.
A3: R es transitiva en A.
44
Decisión en el Lenguaje Formal
(a, b) 0 S ≡ (b, a) 0 R
S es reflexiva en A.
œ a : a 0 A → (a, a) 0 R por A1
(a, a) 0 R → (a, a) 0 R por iii)
El análisis del cálculo proposicional ha seguido un orden determinado; este orden está
bien lejos de constituir lo que comúnmente denominamos como Sistema. Es decir una
organización tal del conocimiento en la que unos aspectos de la misma se deducen de otros
aspectos y que unos determinados símbolos se definan a partir de otros símbolos.
45
Decisión en el Lenguaje Formal
tautologías que deben satisfacer dichos términos primitivos. Los axiomas son fbf
tautológicas que no pueden ser deducidos de otras fbf tautológicas, es decir son
independientes. En cambio los teoremas son fbf tautológicas que pueden ser
deducidos o probados a través de la utilización de los axiomas.
iii) definiciones, expresiones, fórmulas lógicas que son derivadas de los teoremas
o axiomas y que a veces son considerados como términos no primitivos.
iv) reglas, es decir, propiedades que deben cumplir las proposiciones o fórmulas
lógicas. De entre ellas tenemos:
U1 ^ (α1, α2)
U1 ^ (α)
donde las descomposiciones α y β, se indican en las figuras 4.2.1 y 4.2.2. El conjunto de fórmulas
por encima de la línea son denominadas premisas y el conjunto de fórmulas por debajo de la
línea es denominada como la conclusión.
A partir de las premisas podemos inferir la conclusión o que la conclusión puede ser
probada o comprobada a partir de las premisas Intuitivamente, si tenemos pruebas indepen-
dientes de dos fórmulas podemos en consecuencia inferir su conjunción y si tenemos una prueba
de un conjunto de fórmulas podemos entonces inferir sus conjunciones.
DEFINICIÓN 2.2: Una prueba en G es una secuencia de fórmulas tal que cada elemento
es un axioma o puede ser inferido a partir de uno o dos elementos
previos de una secuencia utilizando una regla de inferencia. Si A es el
último elemento de una secuencia, la secuencia es denominada como
una prueba de A y de este modo A es demostrable. Notación emplead
|A
46
Decisión en el Lenguaje Formal
α α1 α2
A ¬¬ A
¬ (A1 ∧ A2) ¬ A1 ¬ A2
A 1 ∨ A2 A1 A2
A1 ⇒ A2 ¬ A1 A2
A1 ⇐ A2 A1 ¬ A2
La comprobación es escrita como una secuencia de conjuntos de fórmulas las que son
numeradas para una referencia conveniente. A la derecha de cada conjunto numerado de
fórmulas colocamos la justificación con la cual cada conjunto puede ser inferido. La justificación
puede ser el axioma a aplicarse o una regla de inferencia aplicada al conjunto o conjuntos de
fórmulas en el paso anterior de la secuencia. Si se ha utilizado una regla de inferencia, debe ser
identificada como regla-α o regla-β sobre el conectivo principal de la conclusión y el número o
números de las líneas conteniendo las premisas.
β β1 β2
¬ (B1 ∨ B2) ¬ B1 ¬ B2
B 1 ∧ B2 B1 B2
¬ (B1 ⇒ B2) B1 ¬ B2
¬ (B1 ⇐ B2) ¬ B1 B2
B1 ≡ B2 B1 ⇒ B2 B2 ⇒ B1
Consideremos un ejemplo:
Ejemplo 2.2.1: | (p ∨ q) ⇒ (q ∨ p)
Demostración:
1.- 5 p, q, p Axioma
2.- 5 q, q, p Axioma
3.- 5 (p ∨ q), q, p Regla-β - ∨ , (1), (2)
4.- 5 (p ∨ q), q ∨ p Regla-α - ∨ , (3)
5.- (p ∨ q) ⇒ (q ∨ p) Regla-α - ⇒ , (4)
47
Decisión en el Lenguaje Formal
Los elementos básicos del sistema proposicional de Russel son los siguientes:
1: "5" Negación.
2: "∨" Disyunción
3: p, q, s Proposiciones
A1: (p ∨ q) ⇒ p
A2: q ⇒ (p ∨ q)
A3: (p w q) ⇒ (q w p)
C.- Definiciones
1: p ⇒ q / df. (5 p w q)
2: p v q ≡ df. 5 (5 p w 1q)
3: (p ≡ q) ≡ df. (p v q) w (5 p v 5 q)
D.- Reglas
a).- De Formación
b).- De Transformación
48
Decisión en el Lenguaje Formal
A2 1) q⇒ (p w q)
En 1) p ⇒ q/ q 2) (p ⇒ q) ⇒ [p w (p ⇒ q)]
A3 1) (p w q) ⇒ (q w p)
En 1) def. de ⇒ 2) (5 p ⇒ q) ⇒ (q w p)
Al comparar este Sistema Axiomático de Hilbert con el de Russel, podemos indicar las
diferencias que se presentan y que son las que se presentan en los Términos Primitivos a los que
se agregan la Implicación y la Conjunción; y dentro de los Axiomas debemos considerar 10 (diez)
más importantes, sin embargo enunciaremos algunos otros teoremas o tautologías.
1: "5" Negación.
2: "w" Disyunción
3: "v" Conjunción
4: "⇒" Implicación
5: p, q, s Proposiciones
A partir de ahora enunciamos teoremas (a veces son definidos como propiedades de los
símbolos no terminales) dentro del sistema axiomático de Hilbert, los que como ya hemos
definido no son axiomas, pero pueden ser deducidos de los 10 axiomas considerados.
11.| p≡p
12.| 5 p ⇒ (p ⇒ q)
13.| (p ⇒ (q ⇒ r)) ≡ (q ⇒ (p ⇒ r))
14.| (p ⇒ q) ⇒ ((q ⇒ r) ⇒ (p ⇒ r))
15.| (q ⇒ r) ⇒ ((p ⇒ q) ⇒ (p ⇒ r))
16.| (p ⇒ (q ⇒ r)) ⇒ ((p v q) ⇒ r)
17.| ((p v q) ⇒ r) ⇒ (p ⇒ ( q ⇒ r))
18.| (p ⇒ q) ⇒ ((p ⇒ r) ⇒ (p ⇒ (q v r)))
19.| (p ⇒ q) ⇒ ((r ⇒ s) ⇒ ((p v r) ⇒ (q v s)))
20.| (p ⇒ r) ⇒ ((q ⇒ r) ⇒ ((p w q) ⇒ r))
21.| (5p ≡ q) ≡ (p ≡ 5q)
49
Decisión en el Lenguaje Formal
C.- Definiciones
Def.: p ⇒ q ≡ (5p w q) ≡ 5(p v 5q)
D.- Reglas
a).- De Formación
b).- De Transformación
((p ⇒ q) v p) ⇒ q p⇒q
p
⎯⎯⎯⎯⎯
∴q
50
Decisión en el Lenguaje Formal
En los capítulos anteriores vimos dos puntos importantes, que ahora pondremos en
relación. El primero es el empleo de la tabla de verdad para determinar el carácter de una
proposición, fórmula o EBF. Dicha determinación tiene en la lógica un nombre técnico: Decisión.
Para decidir con certeza lógica, si una expresión bien formada es tautológica, contradictoria o
indefinida, se recurre a diferentes procedimientos. Uno de ellos, como vimos en el capítulo
anterior, es la tabla de verdad. Estos procedimientos son mecánicos y finitos. Mecánicos, porque
sin interpretar la fórmula, sin intuir significado alguno, podemos concluir en que la misma es o
invariablemente verdadera, o invariablemente falsa o unas veces falsa y otras veces verdadera.
Finitos, pues por compleja que sea la fórmula, en un número limitado de pasos y siguiendo reglas
precisas, puede establecerse el carácter del expresión lógica.
Cuando hablamos de poner en relación ambos temas, los dos puntos mencionados en el
apartado anterior, pensamos en un procedimiento de decisión que emplee la transformación de
una fórmula dada en otra fórmula derivada y equivalente a la original. Esto es lo que hace el
procedimiento llamado de decisión por Formas Normales.
Una forma normal conjuntiva es una serie continua de conjunciones y donde los
factores de esas conjunciones son sólo disyunciones.
(5 p w q) v (p w 5 q) v (5 p w 5 q)
Una forma normal disyuntiva es una serie continua de disyunciones y donde los
factores de esas disyunciones son sólo conjunciones.
(p v q) w (p v 5 q) w (5 p v q)
Ambas formas normales deben aún cumplir con este otro requisito: no deben tener
negaciones compactas, es decir negaciones que afecten a proposiciones moleculares o
51
Decisión en el Lenguaje Formal
compuestas. La negación puede aparecer solamente en una forma normal afectando a las
proposiciones atómicas o simples.
La diferencia visible entre una y otra forma normal es, como se habrá notado en los ejem-
plos dados, que mientras la f.n.c. emplea a la conjunción como conectivo de mayor alcance y a la
disyunción como conectivo de menor alcance, en la f.n.d. se utiliza a la conjunción como
conectivo de menor alcance y a la disyunción como conectivo de mayor alcance.
Para la transformación de una expresión lógica dada en una forma normal emplearemos
especialmente las reglas que permitan pasar de un conectivo a otro en la expresión. Muy
importantes también serán los teoremas de la distribución, asociación y conmutación,
propiedades éstas, que caracterizan a la conjunción y a la disyunción. Más adelante iremos
incorporando otros teoremas a los ya conocidos y cuyo uso facilitará la transformación de
cualquier expresión o fórmula a una forma normal.
Para utilizar las formas normales como procedimiento de decisión, deben seguirse dos
pasos generales: transformar primero la fórmula dada en una forma normal; en segundo lugar
interpretar la forma normal para saber si la misma es tautológica, contradictoria o indefinida.
(p ⇒ q) v (p w q)
Esta expresión no es una forma normal, no coincide con ninguna de las definiciones de
forma normal. Por lo pronto incluye el signo de la implicación, conectivo que no aceptan las
formas normales. Lo primero que realizaremos será eliminar el mencionado conectivo, convertirlo
en alguno de los que permiten las formas normales.
1) (p ⇒ q) v (p w q) Fórmula dada
2) (5 p w q) v (p w q) Definición de "⇒"
El paso dos es una forma normal conjuntiva. Consideremos otro ejemplo simple:
1) (p ⇒ q) ⇒ (p v q) Fórmula dada
2) 5 (p ⇒ q) w (p v q) Def. de "⇒"
3) 5 (5 p w q) w (p v q) Def. de "⇒"
4) (p v 5 q) w (p v q) T. de De Morgan
La expresión indicada en (4) es una forma normal conjuntiva. Pero puede suceder que el
resultado no sea tan claro, como en los ejemplos vistos, el carácter de forma normal de la
expresión a la que se llego por medio de las transformaciones. Consideremos el siguiente ejemplo
en el cual se muestra un caso de esa situación en que a pesar de no cumplir en forma aparente
con los requisitos de la f.n., la expresión realmente es una f.n.:
1) p ⇒ (q ⇒ p) Fórmula dada
2) 5 p w (5 q w p) Def. de "⇒"
3) 5pw5qwp Asociatividad
4) pw5pwq Conmutatividad
La expresión en (4) es una forma normal conjuntiva. Puede objetarse que la misma no cumple con
los requisitos de una f.n., no es una conjunción de disyunciones, pues sólo se ven disyunciones
en ella. La cuestión se aclara si mostramos que la expresión (4) es idéntica a la siguiente
expresión:
52
Decisión en el Lenguaje Formal
(p w 5 p w q) v (p w 5 p w q)
Esta fórmula es idéntica en su valor de verdad a (4). Muestra de una forma clara el aspecto total
de una f.n.c.. Pero es redundante y reiterativa, ya que el segundo paréntesis no agrega nada a la
fórmula. De igual forma, en lógica, como en matemática, podemos simplificar y reducir de esta
forma la expresión, sin repeticiones inútiles. En este caso la simplificación puede realizarse
gracias al siguiente teorema: (p v p) / p.
El ejemplo que acabamos de considerar es una f.n.c. de un solo miembro, es una forma
normal degenerada. Como caso límite de esa situación podemos tomar a p, que es una forma
normal.
1) (p ≡ q) ⇒ (p ⇒ q) Fórmula dada
2) [(p ⇒ q) v (q ⇒ p)] ⇒ (p ⇒ q) Def. de "≡"
3) 5 [(5 p w q) v (5 q w p)] w (5 p w q) Def. de "⇒"
4) [5 (5 p w q) w 5 (5 q w p)] w (5 p w q) T. de De Morgan
5) [(p v 5 q) w (q v 5 p)] w (5 p w q) T. de De Morgan
6) (p v 5 q) w (q v 5 p) w (5 p w q) Asociatividad
Es preciso tener en cuenta que todas las expresiones transformadas son equivalentes a
la original. Es por eso de que las formas normales pueden ser un método de decisión. A través de
ellas podremos determinar si la expresión lógica original es tautológica, contradictoria o
indefinida.
Deber tenerse en cuenta asimismo, que para obtener un f.n. pueden existir varios
caminos. En el ejemplo anterior (cuyo punto final mostrará una forma normal disyuntiva),
podríamos haber partido de otra definición de bicondicional y seguir un ordenamiento diferente en
las transformaciones. Pero cualquiera sea el camino seguido, llegaremos siempre a una f.n.c y a
una f.n.d., ambas equivalentes. Es decir cada fórmula tiene una f.n.c. y una f.n.d., pero lo
recíproco no es válido, porque una misma forma normal corresponde a muchas fórmulas.
Las dos formas normales no sólo se diferencian por el empleo distinto que hacen de la
conjunción y de la disyunción. Cada f.n. revela algo importante de la expresión original. La f.n.c.
nos informa acerca de la verdad de la expresión. Veamos de qué forma. Consideremos el ejemplo
siguiente:
(p w 5 p) v (q w 5 q) f.n.c.
tenemos el caso de una conjunción cuyos dos factores o paréntesis son verdaderos. Y lo son
ambos, por simbolizar el clásico Principio Lógico del Tercero Excluido, uno de los tres
principios formulados por la lógica tradicional. Este principio afirma que dos proposiciones
contradictorias no pueden ser ambas falsas: (p w 5 p), p o no p significa que una es verdadera o
la otra lo es. No existe una tercera posibilidad. Interprétese con cualquier ejemplo esa fórmula y
se verá que es tautológica ("Las mariposas son canarios" o "Las mariposas no son canarios", "El
espacio es infinito" o "El espacio no es infinito", etc.). Ahora bien, si la conjunción que vimos une
dos tautologías, entonces es verdadero. Pues una conjunción exige, para ser verdadera, que los
miembros unidos por ella sean ambos verdaderos. En este caso se cumple. Pero existe algo más.
Una expresión como:
(p w 5 p w q)
53
Decisión en el Lenguaje Formal
es igualmente tautológica, por el solo hecho de que p w 5 p forma parte de ella. En efecto,
cualquiera sea el valor de q, el valor de verdad del conjunto será verdadero. Si construimos la
tabla de p w 5 p, siempre tendremos verdadero. Si a partir de ahí, construimos la tabla de (p w 5
p) w q, como ya existe una columna de dominio total, cualquiera sea el valor de q, el resultado de
su disyunción con una tautología será otra tautología. Debido a que una disyunción exige para ser
verdadera que al menos uno de sus factores lo sea. Podemos expandir la fórmula, agregarle
cuántas proposiciones queramos (r, s, t, u, etc.) a las anteriores, siempre será un conjunto
tautológico. La tautología del Tercero Excluido trasmitirá su carácter de invariablemente
verdadera a cualquier fórmula que lo incluya y le agregue proposiciones mediante la disyunción:
(p v q v 5 p) w (5 p v q v 5 q)
Se trata de una f.n.d... Y es contradictoria, porque cada una de las expresiones que
vincula la disyunción incluye una variable proposicional y su negación. Es decir que ambos
factores son falsos, contradictorios. Como se recordará, este era el único caso en que una
disyunción es falsa. Si en la f.n.c. nos basábamos en el Principio del Tercero Excluido, ahora
estamos empleando otro principio lógico no menos importante, el Principio de la Contradicción.
Del análisis realizado hasta ahora con las formas normales, se desprenden dos
interrogantes aún no contestados, a saber:
54
Decisión en el Lenguaje Formal
Los dos interrogantes tienen una sola respuesta: en ambos casos es preciso transformar
una forma normal en otra. Si es f.n.c. transformarla en f.n.d. y si es f.n.d. transformarla en f.n.c..
Es decir que para determinar si una forma normal es indefinida, es preciso transformar esa forma
normal en la otra forma normal. El método es claro si se tiene en cuenta que las dos formas
normales nos dan información restringida, es tautología o contradicción. Y como existe una
tercera posibilidad, el carácter indefinido de la expresión, si realizamos la transformación de una
forma normal en otra, ocurrirá forzosamente alguna de estas posibilidades:
2).- La f.n.c. no es tautológica. Transformada en f.n.d. cada factor incluye una variable
proposicional y su negación. Entonces es una contradicción.
4).- La f.n.d. no es contradictoria. Transformada en f.n.c. cada factor incluye una va-
riable proposicional y su negación. Entonces es una tautología.
El problema consiste ahora en saber como transformar una f.n.c. en una f.n.d. y viceversa,
para luego decidir si la fórmula es indefinida o no. Esa transformación se realiza utilizando la
Propiedad Distributiva. En los teoremas 11 y 12 de la lista de teoremas del Capítulo II, podemos
ver en qué consiste y a qué reglas se somete la distribución. El teorema:
afirma que la conjunción (producto lógico) es distributivo respecto de la disyunción (suma lógica).
La misma propiedad la tiene el producto algebraico con respecto a la suma:
(a).- Distribuir cada variable proposicional de un factor con cada variable pro-
posicional de los factores restantes.
1) (5 p w 5 q) v (p w r) f.n.c.
2) (5 p v p) w (5 p v r) w (5 q v p) w (5 q v r) Por Distribución
3) (p v 5 p) w (5 p v r) w (p v 5 q) w (5 q v r) Por Distribución
La expresión (1) es una f.n.c., que como no tiene una variable proposicional y su negación en
cada factor, no es tautología. En (2), por el teorema de la distribución, la f.n.c es transformada en
f.n.d., y aplicamos la propiedad conmutativa en (3) para poder ver mejor si todos los factores
poseen una variable proposicional y su negación. Pero como observamos que ello se cumple
únicamente en el primer factor, la f.n.d. no es contradictoria. En consecuencia es indefinida. Se
55
Decisión en el Lenguaje Formal
cumplió la posibilidad 1.
Veamos ahora el otro teorema de la propiedad distributiva, el que nos permite transformar
una f.n.d. en una f.n.c.:
El teorema afirma que la suma lógica (disyunción) es distributiva con respecto al producto lógico
(conjunción). Dicha propiedad no la posee la suma algebraica o aritmética:
En cambio la disyunción (suma lógica) acepta la distribución con el producto lógico (conjunción).
Ello puede confirmarse fácilmente mediante la tabla de verdad.
1) (p v q) w (5 q v 5 p) f.n.d.
2) (p w 5 q) v (p w 5 p) v (q w 5 q) v (q w 5 p) Por Distribución
La f.n.d. no es contradictoria y la transformamos en una f.n.c.. Como ésta no incluye en todos sus
factores a una variable proposicional y su negación, no es tautológica. Por lo tanto es una
expresión lógica indefinida. Luego se verá que los paréntesis segundo y tercero de la expresión
(2) pueden simplificarse, en un tercer paso. Como ambos son tautologías, al eliminarlos de la
expresión no altera en nada el valor de verdad de la fórmula total y quedará reducida a la siguiente
expresión: (p w 5 q) v (q w 5 p).
(p v 5 q) w (5 q w p)
Observar que en esta fórmula el conectivo de mayor alcance aparece también en el segundo
factor. En casos como el indicado, el factor se distribuye en bloque, de la forma dada a
continuación:
1) (p v 5 q) w (5 q w p) Expresión dada
2) (5 q w p w p) v (5 q w p w 5 q) Por Distribución
La distribución ofrece algunas dificultades cuando se trata de más de dos miembros. Los
ejemplos siguientes indicarán como debemos proceder en cada caso:
1) (p w q) v (5 p w r) v (5 q w s) f.n.c.
(p v 5 p v 5 q) w (p v 5 p v s) w (p v r v 5 q) w (p v r v s) w (q v 5 p v 5 q) w
(q v 5 p v s) w (q v r v 5 q) w (q v r v s)
Se observará que hemos distribuido primero la primera variable proposicional del primer miembro
con la primera del segundo y ambas con las restantes variables del tercer miembro. Así surgen los
dos primeros miembros de la f.n.d.. Luego está distribuida la primera variable del primer miembro
con la segunda del segundo y ambas con las variables del tercer miembro: de allí los miembros
56
Decisión en el Lenguaje Formal
tercero y cuarto de la f.n.d.. Finalmente se realizo lo mismo con la segunda variable del primer
miembro; fácil es ver que los cuatro últimos miembros de la f.n.d. se diferencian de los cuatro
primeros en que donde éstos tienen p, aquellos tienen q.
2) (p v q) w (r v s) w (5 p v 5 r) w (5 q w s) f.n.d.
Esta vez tenemos como ejemplo una f.n.d., que tiene un miembro (el último) cuyo conectivo es el
mismo que el de mayor alcance de la fórmula. En casos así, como ya vimos, se distribuye
compactamente dicho miembro:
(5 q w s w p w r w 5 p) v (5 q w s w p w r w 5 r) v (5 q w s w p w s w 5 p) v
(5 q w s w p w s w 5 r) v (5 q w s w q w r w 5 p) v (5 q w s w q w r w 5 r) v
(5 q w s w q w s w 5 p) v (5 q w s w q w s w 5 r) f.n.c.
1) (p ⇔ q) ⇒ (p ⇒ q) Fórmula dada
2) 5 (p ⇔ q) w (5 p w q) Def. de "⇒"
3) 5 [(p v q) w (5 p v 5 q)] w (5 p w q) Def. de "⇔"
4) [5 (p v q) v 5 (5 p v 5 q)] w (5 p w q) T. de De Morgan
5) [(5 p w 5 q) v (p w q)] w (5 p w q) T. de De Morgan
La expresión (5) aún no es una forma normal. Para continuar con las transformaciones
hasta lograrlo, utilizaremos la propiedad distributiva. Para hacer más fácil el método, reduciremos
la complejidad de la expresión (5) utilizando las letras mayúsculas R, S, T, etc., como elementos
metalógicos para representar fórmulas o expresiones lógicas cualesquiera. Veamos cómo:
5) [(5 p w 5 q) v (p w q)] w (5 p w q)
( R v S ) w T
Donde (R v S) w T tiene una estructura general idéntica que la expresión (5). Apliquemos en
consecuencia la propiedad distributiva a esta nueva expresión y reemplacemos luego
nuevamente los signos metalógicos por las fórmulas que representan:
Hemos obtenido como resultado final una f.n.c., cuyos dos paréntesis incluyen una variable
proposicional y su negación, en consecuencia la fórmula es tautológica.
En el paso (10) hemos simplificado, o sea hemos eliminado las repeticiones innecesarias.
Teníamos dos veces 5 p en el primer miembro y también dos veces q en el segundo miembro,
ambas repeticiones no agregaban nada al valor de verdad de la expresión del paso (9). La
simplificación se hizo en función del teorema que ya mencionamos en el capítulo II: (p w p) / p.
Existen otros teoremas que permiten simplificar expresiones lógicas. Por ejemplo, cuando existe
una tautología conocida como miembro de una conjunción, dicha tautología puede eliminarse. Por
57
Decisión en el Lenguaje Formal
ejemplo:
(5 p w p) v (q w r)
Podemos simplificar el primer miembro o paréntesis, porque el valor de verdad de ese conjunto
depende únicamente del valor de verdad de (q w r), ya que (5 p w p) es siempre verdadero. La
simplificación se realizo en función del siguiente teorema lógico:
[p v (q w 5 q)] ≡ p.
Es decir que en una f.n.c. no tautológica podemos simplificar todos aquellos miembros o
factores que incluyan una variable y su negación. En efecto, el valor de la expresión no se alterará
si suprimimos esas tautologías. Por ejemplo:
Algo semejante podemos realizar con las f.n.d. no contradictorias. En ellas podemos simplificar
todos aquellos factores que contengan una variable proposicional y su negación. El valor de la
expresión lógica permanecerá intacto si eliminamos esas contradicciones. Por ejemplo:
[(p v q v 5 q) w (r v q v s)] ≡ (r v q v s)
Para finalizar, agregaremos nuevos teoremas a la lista anterior y cuyo empleo facilitará la
decisión por el método de las formas normales.
Para distinguir entre enunciados y formas de enunciados, distinción que hasta aquí no
hemos realizado, utilizaremos la noción de constante proposicional. Una constante proposicional
se simboliza con las letras mayúsculas (letras iniciales A, B, C, D, etc.) y representa sólo una
proposición dentro del contexto. El siguiente ejemplo :
Aw5B
58
Decisión en el Lenguaje Formal
Ahora podemos decir que una forma de enunciado es una fórmula o expresión lógica EBF,
construida con variables proposicionales. Si se reemplazan las variables por constantes
proposicionales, cuidando en todos y en cada caso de sustituir la misma variable por la misma
constante, obtenemos un enunciado. Continuando con la significación atribuida a A y a 5 B, los
ejemplos siguientes muestran enunciados y sus correspondientes formas:
1) A v B 1) p v q
2) A ⇒ 5 B 2) p ⇒ 5 q
3) 5 A w A 3) 5 p w p
4) B v 5 B 4) p v 5 p
Fácil sería, en efecto, encontrar otra sustitución verdadera de la misma forma de enun-
ciado: "Si es triángulo, entonces no es cuadrado", por ejemplo. En casos así decimos que se
trata de enunciados indefinidos o contingentes, pues su verdad o falsedad depende del
contenido y no de su forma.
El enunciado (4), también es falso pero por razones distintas que el anterior. Aquí su
falsedad proviene de ser un caso de sustitución de una forma de enunciado contradictorio. No se
encontrará, en efecto, un solo caso de sustitución verdadero de p v 5 p.
Razonamiento semejante podemos realizar también con los dos enunciados restantes.
El enunciado (1) es verdadero pero contingente, pues su forma de enunciado es indefinida. Es
decir que su verdad depende del contenido, del significado de sus enunciados componentes, y no
de su forma de enunciado. En cambio el enunciado (3) es verdadero en razón de constituir un
caso de sustitución de una forma de enunciado tautológico.
2.6.- EL RAZONAMIENTO
Hasta este punto nos hemos dedicado a los enunciados y a sus formas. Sobre la base de
lo que hemos estudiado, podremos avanzar hacia la comprensión de lo que es un razonamiento.
Un razonamiento está constituido por enunciados de tal modo que el último (conclusión)
se deriva con necesidad lógica de los anteriores (premisas).
59
Decisión en el Lenguaje Formal
Así como distinguimos entre enunciados y formas de enunciados, veremos también que
existen razonamientos y formas de razonamientos. Analizaremos los ejemplos siguientes:
Como podemos observar, el razonamiento está formado por enunciados. En tanto que la
forma de razonamiento está formada por variables proposicionales. Por lo cual podemos decir,
que un razonamiento resulta de sustituir, en una forma de razonamiento las variables proposicio-
nales por constantes proposicionales, reemplazando siempre la misma variable por la misma
constante.
Los ejemplos (1) y (2) tienen la misma forma de razonamiento. El ejemplo (1) tiene premi-
sas verdaderas y conclusión verdadera, en tanto que en el ejemplo (2), se llega a conclusión falsa
a cuando hemos partido de premisas verdaderas. Cuando una forma de razonamiento permite
esto último, o sea extraer conclusión falsa de premisas verdaderas, decimos que se trata de una
forma de razonamiento inválida.
En cambio las formas de razonamiento (3) y (4) no permiten la derivación de una conclusión falsa
a partir de premisas verdaderas, porque se trata de formas de razonamiento válidas. Si intenta-
mos buscar un caso de sustitución de este tipo, donde exista conclusión falsa a partir de premisas
verdaderas, no lo encontraremos.
En los ejemplos considerados existe algo curioso. La forma de los razonamientos (1) y (2),
que es inválida, permite sin embargo que en ciertos casos de sustitución, las premisas y conclu-
sión sean verdaderas. Tal cual lo es el caso (1). La forma de los razonamientos (3) y (4), forma
válida, permite que una de las premisas y la conclusión sean falsas, caso (3). Esto revelaría que
la validez o invalidez de las formas de razonamiento, es en alguna medida independiente de la
verdad o falsedad de las variables proposicionales, que la componen. Lo extraño es que
definimos validez e invalidez de las formas de razonamiento en función de la verdad o falsedad
de las proposiciones componentes.
)Qué ocurre, pues?. Definimos las nociones de validez e invalidez a pelando a la relación
que guardan premisas y conclusión respecto de sus valores de verdad. Y ahora afirmamos que la
validez o invalidez sería independiente de esos valores, según parecen mostrar los ejemplos (1)
y (3). Y no sólo ese par de afirmaciones parece contradictoria sino también esta otra: al comienzo
dijimos que la lógica es una ciencia formal, que para nada tiene en cuenta el contenido de las pro-
posiciones. Pero ahora hemos definido la validez de una forma de razonamiento, como aquella
60
Decisión en el Lenguaje Formal
forma que no permite un caso de sustitución donde haya premisas verdaderas y conclusión falsa.
Y sustituir en una forma de razonamiento es, dijimos, reemplazar variables por constantes, es de-
cir formas vacías (p, q, r, s, etc.) por constantes con un significado específico. )No es esto una
contradicción?. Entre la forma (V, F) y el contenido de las proposiciones, la lógica como ciencia
formal debe optar por la primera, desechar el contenido. Y aquí, al parecer, hemos realizado lo
contrario:
(a) y (b) son las subformas que corresponden a los razonamientos (1) y (2). Podemos ahora preci-
sar nuestra definición de validez. No hablaremos de que una forma general de razonamiento es
válida si no tiene sustituciones de constantes proposicionales que sean verdaderas en las
premisas y falsas en la conclusión. Diremos más bien que una forma general de razonamiento
es válida si no tiene alguna sub forma que permite la conclusión Falsa (F) a partir de
premisas Verdaderas (V).
Esta definición es más formal, pues no hace reposar en el contenido significativo de las
constantes, la noción lógica de validez. De esta forma hemos contestado a la segunda con-
tradicción mencionadas anteriormente. Veamos ahora que sucede con la primera contradicción
mencionada.
Para comprender mejor la respuesta, nos anticiparemos a algo que se verá luego con
más detalle: toda forma de razonamiento tiene una correspondiente forma de enunciado. La
forma de enunciado que corresponde a la siguiente forma de razonamiento:
p⇒ q
q Es : [(p ⇒ q) v q] ⇒ p
ˆ p
61
Decisión en el Lenguaje Formal
p q [(p ⇒ q) v q] ⇒ p
V V V V V V V
V F F F F V V
F V V V V F F
F F V F F V F
Las cuatro subformas de que antes hablamos aparecen en cada línea horizontal de la
tabla; (a) es la primera línea; (b) es la tercera línea; (c) es la segunda línea y (d) es la cuarta línea.
Notar que si empezáramos de otra definición de validez, como la siguiente: "una forma
de razonamiento es válida si nos garantiza concluir en verdad", tendríamos que aceptar como
válidas las subformas (a), (c) y (d) de la forma general inválida de razonamiento y también mu-
chas otras formas inválidas de razonamiento.
Como vimos, una forma válida de razonamiento acepta solamente estas relaciones
posibles entre premisas y conclusión:
Premisas Conclusión
V V
F V
F F
Premisas Conclusión
V F
Nótese que los casos aceptados por la forma válida coincide punto a punto con el dominio
del condicional. En efecto, el condicional es verdadero cuando el consecuente es verdadero o el
antecedente es falso. Y una forma de razonamiento es válida cuando únicamente tiene
sustituciones de variables cuyo valor general es F en las premisas o V en la conclusión.
Por otro lado el condicional es falso cuando tiene antecedente verdadero y consecuente
falso. Y la forma de razonamiento es inválida cuando tiene al menos un caso de sustitución de
variables proposicionales, cuyo valor general es V en las premisas y F en la conclusión.
62
Decisión en el Lenguaje Formal
Todo esto quiere decir que el signo "ˆ" colocado entre las premisas y la conclusión tiene
un comportamiento semejante al condicional "⇒". Esto nos permite, que al sustituir "ˆ" por "⇒",
encontrar para cualquier razonamiento un enunciado que le corresponda. Por ejemplo:
A⇒B
1) B⇒C 2) (A ⇒ B) v (B ⇒ C) v (A w B) ⇒ (C w B)
AwB
ˆ CwB
En (2) hemos unido las distintas premisas del razonamiento (1), mediante la conjunción.
Este procedimiento está justificado por una de las formas válidas de razonamiento que veremos
más adelante.
Destaquemos que si bien a todo razonamiento le corresponde un enunciado, que une las
premisas mediante la conjunción y reemplaza "ˆ" por "⇒", lo recíproco no es válido: no todo
enunciado tiene su correspondiente razonamiento. El siguiente enunciado (A w B), por
ejemplo, no puede ser convertido en razonamiento, no tiene una proposición que se derive de otra
u otras proposiciones. De lo dicho, podemos concluir en la siguiente regla general: toda forma de
enunciado cuyo conectivo de mayor alcance sea "⇒", tiene su correspondiente forma de
razonamiento.
1) [(p v q) w r] ⇒ p 1) (p v q) w r
ˆ p
2) [(p ⇒ q) v 5 q] ⇒ 5 p 2) p ⇒ q
5q
ˆ 5p
3) p ⇒ q 3) p
ˆ q
Podemos preguntarnos ahora, qué relación guarda una forma de razonamiento con su
forma de enunciado correspondiente. La respuesta que obtenemos es la siguiente: si la forma de
enunciado es tautológica, entonces la forma de razonamiento es válida. Si la forma de enunciado
es contradictoria o indefinida, la forma de razonamiento es inválida. Porque si válida es una forma
de razonamiento cuando no acepta que de premisas verdaderas, se concluya en falsedad, la
forma de enunciado correspondiente sólo puede ser tautológica. Porque )qué ocurriría si la forma
de enunciado en cuestión fuese indefinida?.
Válida Tautológica
Un vistazo a los valores de premisas y conclusión nos anticipa desde ya la invalidez del
razonamiento. Pero construyamos la tabla de verdad de la forma de enunciado correspondiente,
para decidir si la invalidez proviene que la forma de enunciado sea contradictoria o indefinida.
p q [(p ⇒ q) v 5 p] ⇒ 5q
V V V F F V F
V F F F F V V
F V V V V F F
F F V V V V V
64
Decisión en el Lenguaje Formal
5) (p ⇒ q) v (r ⇒ s) Dilema Constructivo
(p w r)
----------------------
ˆ (q w s)
6) (p ⇒ q) v (r ⇒ s) Dilema Destructivo
5qw5s
-----------------------
ˆ 5pw5r
7) pvq Simplificación
--------
ˆ p
8) p Conjunción
q
-----------
ˆ pvq
9) p Adición
---------
ˆ pwq
Si, como hemos visto en los apartados anteriores, a todo razonamiento le corresponde
una forma de enunciado, es fácil comprender que los métodos de decisión aplicados a enun-
ciados permiten decidir también sobre la validez o invalidez de los razonamientos. Las formas
normales, por ejemplo, que permiten decidir sobre si un enunciado es tautológico, contradictorio
o indefinido, también deciden la validez o invalidez de un razonamiento dado. Sólo debemos
considerar la relación entre razonamiento y enunciado correspondiente: aquel es válido -
únicamente cuando éste es tautológico; e inválido cuando el enunciado es indefinido o
contradictorio. Dado un razonamiento cualquiera, pues, si queremos decidir por las formas
normales si es válido o no, tendremos que proceder de la siguiente forma: transformar el
razonamiento en su enunciado correspondiente; aplicar a éste el método de las formas normales;
si el resultado establece que el enunciado es tautológico, el razonamiento es válido; si el enun-
ciado resulta ser indefinido o contradictorio, el razonamiento es inválido. El empleo de las formas
normales para decidir la naturaleza de un razonamiento, es particularmente útil cuando el número
de proposiciones, que componen al razonamiento en cuestión, es abultado. En esos casos la
decisión por las tablas requiere una proliferación de columnas de referencia para realizar el cál-
culo y eso complica demasiado la decisión.
65
Decisión en el Lenguaje Formal
Estudiaremos ahora la implicación lógica y la forma en que puede utilizarse como base
de un razonamiento válido. Hay, por supuesto, razonamientos que no son válidos y algunos de
ellos serán identificados en secciones posteriores. Los argumentos o razonamientos no válidos
se los denominan falacias. Utilizando el método de la tabla de verdad, se puede distinguir entre
razonamientos válidos y falacias.
Los patrones de razonamiento pueden expresarse de diferentes forma, tal cual vimos en
secciones anteriores. En el idioma español, la conclusión se establece típicamente después de
las premisas, y se presenta mediante palabras tales como: Apor tanto@, Acomo consecuencia@
y Aen conclusión@. En los razonamientos presentados en secciones anteriores, enumerábamos
primero todas las premisas, una debajo de la otra. Existía una línea horizontal por debajo de la
última premisa, y debajo de esta línea, estaba la conclusión. En el caso del modus ponens, esto
tiene el siguiente aspecto:
p , p ⇒ q ⎥═ q
(( p º q ) ¸ ( 5 p ∨ q )) ≡ q
66
Decisión en el Lenguaje Formal
(( p ∨ q ) ¸ ( 5 p ∨ q )) ≡〉 q
Por supuesto, cualquier implicación lógica se puede demostrar mediante la tabla de verdad.
Ejemplo 2.7.1.- Demostrar las siguientes formas de enunciados son tautologías o enun-
ciados válidos p ≡〉 ( p º q ) y ( p ¸ q ) ≡〉 p.
p q (p∨q) p ≡〉 ( p ∨ q )
V V V V
V F V V
F V V V
F F F V
Tabla 2.7.1
p q (p∧q) ( p ∧ q ) ≡〉 p.
V V V V
V F F V
F V F V
F F F V
Tabla 2.7.2
( p ⇒ q ) , ( q ⇒ r ) ⎥═ ( p ⇒ r )
67
Decisión en el Lenguaje Formal
V V V V V V V V
V V F V F F F V
V F V F V F V V
V F F F V F F V
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V
Consideremos el caso en el que si todas las premisas son verdaderas, y este es el caso sólo si
p y q son F, entonces la conclusión 5 p es verdadera. La forma de enunciado correspondiente a
un razonamiento como el considerado, se denomina Modus Tollens.
( p ⇒ q) , 5 q ⎥═ 5 p
V V V F F F V
V F F V F F V
F V V F F V V
F F V V V V V
Existen diferentes sistemas para hacer derivaciones. Todos estos sistemas tienen las
siguientes características en común.
68
Decisión en el Lenguaje Formal
Si existe una derivación para la conclusión C, dado que A1, A2, . . . ., An son las premisas
y dado que L es el conjunto de reglas de inferencia admisibles, entonces escribimos:
A1, A2, . . . ., An | L C
( P ⇒ Q ) , ( Q ⇒ 5 R ) , ( 5 P ⇒ 5 R ) ⎥═ 5 R
Nota: La regla de Inferencia conocida como la Ley de Casos está indicada en el siguiente
esquema o enunciado:
( A ⇒ B ) , ( 5 A ⇒ B ) ⎥═ B
Ejemplo 2.7.3.- Una pareja tiene un niño, y están esperando un segundo hijo. Demostrar que si
el segundo hijo es una niña entonces la pareja tendrá una niña y un niño.
Sea P Ael primer hijo es un niño@ y Q Ael segundo hijo es una niña@ . Queremos demostrar
que Q ⇒ P ∧ Q , dado que la premisa es P. De acuerdo con el método en discusión puede
hacerse de la siguiente forma:
69
Decisión en el Lenguaje Formal
2.- Se supone Q; esto es, se supone que el segundo hijo es una niña.
4.- En este momento, se nos permite concluir que Q ⇒ P ∧ Q. Q puede ahora ser
licenciada, esto es Q ⇒ P ∧ Q es verdadera aun si Q resulta falsa como
resultado: en este caso Q ⇒ P ∧ Q es trivialmente verdadera.
Es clara la razón por la cual es válido este patrón para realizar demostraciones. Cuando
demostramos A ⇒ B , solamente necesitamos considerar el caso en que A es verdadera: si A es
falsa, A ⇒ B es trivialmente verdadera. Si A es verdadera entonces puede añadirse a las
premisas. Lo que muestra la validez del procedimiento. Esencialmente, el argumento establece
que una hipótesis puede convertirse en un antecedente de un condicional> Este es el contenido
del Teorema de la Deducción, que se enuncia de la siguiente forma:
TEOREMA 2.2.- Sean A y B dos expresiones y sean A1, A2, A3, . . . , las premisas. Si B, A1,
A2, A3, . . . , juntos implican lógicamente C, entonces A1, A2, A3, . . . , implican
lógicamente B ⇒ C.
Junto con este teorema, las reglas de inferencia admisibles, mencionadas anteriormente,
forman un sistema completo de deducción.
Ejemplo 2.7.4.- Utilizar el teorema de la deducción para derivar el Silogismo Hipotético. Usar el
Modus Ponens (MP) como única regla de inferencia.
Demostrar: P ⇒ Q, Q ⇒ R ⎥═ P⇒R
Demostrar: P⇒ Q, P ⇒ 5 Q ⎥═ 5P
70
Decisión en el Lenguaje Formal
DEFINICIÓN 2.4.- Un literal es una proposición simple o una fórmula atómica o la negación de
la fórmula atómica. Definimos a {p, 5p} como el par complementario de
literales, si y solo si p es una fórmula atómica.
DEFINICIÓN 2.5.- Para cualquier tipo de fórmula A, el conjunto {A, 5A} es el par
complementario de fórmulas. A es el complemento de 5A y por lo tanto 5A
es el complemento de A.
sus literales.
DEFINICIÓN 2.7.- Una fórmula es Válida si su valor es verdadero para todas las
interpretaciones.
B ≡ (p w q) v (5p v 5q)
El árbol etiquetado que resulta de esta descomposición y análisis posterior recibe el nom-
bre de CUADRO SEMÁNTICO. Consideremos la expresión B, descompuesta a través de las
denominadas Reglas α, indicada en la Figura 2.8.2
72
Decisión en el Lenguaje Formal
p v (5q w 5p)
⇓
p , 5q w 5p
⇓ ⇓
p , 5q p , 5p
F X
(p w q) v (5p v 5q)
⇓
pwq , 5p v 5q
⇓
pwq , 5p , 5q
⇓ ⇓
p , 5p , 5q q , 5p , 5q
X X
(p w q) v (5p v 5q)
⇓
pwq , 5p v 5q
⇓ ⇓
p , 5p v 5q q , 5p v 5q
⇓ ⇓
p , 5p , 5q q , 5p , 5q
X X
Podemos considerar una variación del cuadro semántico para la expresión B si utilizamos las
denominadas Reglas β, tal cual se indica en la Figura 2.8.3.
Una presentación concisa de las reglas utilizadas para la creación de los cuadros o
marcos semánticos, puede indicarse, si las fórmulas lógicas son clasificadas tomando en cuenta
la negación y el conectivo principal.
Existen dos tipos de reglas de este tipo; las denominadas Reglas α y las denominadas Reglas β.
1.- Las fórmulas α que son conjuntivas y satisfactorias si y solo si ambas sub fórmulas α1 y
α2 también son satisfactorias.
73
Decisión en el Lenguaje Formal
α α1 α2
55A A
A 1 ∧ A2 A1 A2
5 ( A1 ∨ A2 ) 5 A1 5 A2
5 ( A1 ⇒ A2 ) A1 5 A2
5 ( A1 ⇐ A2 ) 5 A1 A2
A1 ⇔ A2 A1 ⇒ A2 A 2 ⇒ A1
2.- Las fórmulas β que son disyuntivas y son satisfactorias aún si solo una de las sub
fórmulas β1 y/o β2 es satisfactoria.
β β1 β2
B 1 ∨ B2 B1 B2
5 (B1 ∧ B2) 5 B1 5 B2
B1 ⇒ B2 5 B1 B2
B1 ⇐ B2 B1 5 B2
* Cada nodo del cuadro semántico T será marcado y etiquetado con un conjunto de fórmu-
las. Inicialmente T consiste de un nodo simple, etiquetado con un conjunto simple {c}. Es
cuadro semántico se construye inductivamente de la siguiente forma :
* Seleccionar una hoja l no marcada sobre el árbol de descomposición. Esta hoja l es eti-
quetada por el conjunto de fórmulas U(l), utilizando las siguientes reglas.
74
Decisión en el Lenguaje Formal
- Si la fórmula A es una fórmula-α, crear un nuevo nodo l' como hijo del nodo
l y etiquetarlo como l' , de la siguiente forma :
- Si la fórmula B es una fórmula-β, crear dos nuevos nodos l' y l" como hijos
de l , Etiquetar a l' con la siguiente fórmula :
La construcción termina cuando todas las hojas del árbol están marcadas con un símbolo
X o bien F.
TEOREMA 2.3: Sea T un cuadro semántico completo para una fórmula A. La expresión A es
No Satisfactoria si y solo si T es cerrado.
COROLARIO 2.1: La expresión A es una expresión lógica satisfactoria si y solo si T está abierto.
COROLARIO 2.2: La expresión A es una expresión lógica válida si y solo si el cuadro semántico
para 5 A es cerrado.
Consideremos el siguiente ejemplo. Podemos demostrar que la siguiente expresión 5(p ∧ 5p) es
válida utilizando en el cuadro semántico el conjunto de la Reglas-α y Reglas-β.
5 5 (p ∧ 5p)
⇓
p ∧ 5p
⇓
p , 5p
X
Cerrado para 5 A y Abierto para todo A
75
Decisión en el Lenguaje Formal
p ∨ (q ∧ 5 q)
⇓ ⇓
P q∧¬q
F ⇓
q , 5q
X
1.- Utilizando las propiedades de la lógica formal, simplificar las siguientes expresiones y/o
expresarlas únicamente como conjunciones: determinar las formas normales conjuntivas
(fnc) y las formas normales disyuntivas (fnd):
2.- Utilizando las propiedades de la lógica formal, simplificar las siguientes expresiones y/o
expresarlas únicamente como conjunciones: determinar las formas normales conjuntivas
(fnc) y las formas normales disyuntivas (fnd):
3.- Determinar si las siguientes expresiones lógicas, a través de las fnc y fnd, son tautologías,
contradicciones, o indefiniciones.
(a) (p ⇒ q) ⇒ (¬ q ⇒ p) (b) ¬ (p ⇒ q) ≡ (¬ q ∧ p)
(c) (p ∨ q) ≡ (p ⇒ q) (d) (p ≡ q) ⇒ ¬ (p ⇒ q)
(e) [(p ⇒ q) ∧ ¬ q] ⇒ ¬ p (f) [(p ⇒ q) ∧ ¬ p] ⇒ ¬ q
(g) [(p ⇒ q) ∨ (q ⇒ p)]
(h) p ∧ ¬ [¬ (p ⇒ q) ∨ q]
(i) ¬ [(p ∨ q) ≡ (p ⇒ q)] ≡ [¬ (p ∨ q) ≡ (p ⇒ q)]
(j) p ⇒ (p ∨ q)
4.- Determinar si las expresiones lógicas consideradas en el Problema 1, a través de las fnc
y fnd, son tautologías, contradicciones, o indefiniciones.
5.- Determinar si las expresiones lógicas consideradas en el Problema 2, a través de las fnc
y fnd, son tautologías, contradicciones, o indefiniciones.
76
Decisión en el Lenguaje Formal
10.- Sea ⊕ (OR exclusivo) la función de verdad definida por la siguiente proposición:
(p ∧ ¬ q) ∨ (¬ p ∧ q)
11.- Mostrar que los siguientes argumentos son válidos usando el concepto de
i) tautología y ii ) contradicción.
a) ( p ∨ q ), ¬ p, ( ¬ p ∨ r ) ≡> (q ∨ r )
b) ( p ⇒ q ), ( p ⇒ r ) ≡> ( p ⇒ ( q ∧ r ))
c) ( p ∨ q ), ( p ⇒ r ), ( q ⇒ r) ≡> r
12.- Para cada uno de los siguientes argumentos válidos indique cual de las reglas de
inferencia dadas en la Tabla 2 se utilizan:
a) Si el Sr. Juárez o la Sra. Juárez ganan más de $30.000 al año, la familia Juárez puede
pasar sus vacaciones en Hawai. Puesto que yo sé que, o el Sr. Juárez o su esposa,
ganan más de $30.000, concluyo que la familia puede afrontar sus vacaciones en Hawai.
b) Si Juan descubre que el producto que le vendiste está defectuoso, se pondrá furioso.
Desafortunadamente ha descubierto que el producto está defectuoso. Por lo tanto Juan
va a estar furioso
c) Si José estuvo ayer en el partido, necesitará dormir. José no pudo dormir. Por consi-
guiente él no fue al partido.
77
Decisión en el Lenguaje Formal
a) p, ( p ⇒ ( q ∨ r )) , (( q ∨ r ) ⇒ s ) ≡> s
b) ( p ⇒ q ) , ( q ⇒ r ) , ¬ r ≡> ¬ p
c) p, ( p ⇒ q ) ≡> ( p ∧ q )
d) ( p ∨ q ) , ( p ⇒ r ) , ( q ⇒ r ) ≡> r
e) ( p ⇒ q ) , ( p ⇒ ¬ q ) ≡> ¬ p
f) ( p ⇒ r ) , ( ¬ p ⇒ q ) , ( q ⇒ s ) ≡> ( ¬ r ⇒ q )
g) ( p ⇒ q ) , ( q ⇒ ( r ∧ s )) , ( ¬ r ∨ ( ¬ t ∨ u)) , ( p ∧ t ) ≡> u
h) ( p ⇒ ( q ⇒ r )) , ( p ∨ s) , ( t ⇒ q ) , ¬ s ≡> ( ¬ r ⇒ ¬ t )
78
Decisión en el Lenguaje Formal
A ∨ B , ¬ B ≡> A
79
Lógica de Predicados
CAPITULO III
LÓGICA DE PREDICADOS
3.1.- INTRODUCCIÓN
Por el lado positivo, las ideas de la lógica, que han madurado durante varios siglos, son
concisas y comprendidas universalmente, como lo es el Latín. Más aún, hasta épocas
recientes, los lógicos han enfocado en probar cosas acerca de lo que podemos hacer con el
conocimiento. Consecuentemente, cuando el dominio de un problema es atacado con éxito por
la lógica, como lo es en la matemática, estamos con suerte, pues podemos conocer los límites
de lo que podemos realizar con lo que nos está permitido. Por el lado negativo, la lógica puede
ser como una cama de Procusto, pues concentrarnos sobre la lógica puede llevarnos a
concentrarnos sobre la matemática de la lógica desviando nuestra atención de las técnicas
valorizadas de resolver problemas que resisten el análisis matemático.
Sabemos que algo es un pájaro, si ese algo tiene plumas o si vuela o si pone huevos.
Estos hechos pueden expresarse a través de reglas antecedente-consecuente de la siguiente
forma:
80
Lógica de Predicados
Plumas (Albatros)
Pájaro (Albatros)
Plumas (Canario)
Evidentemente, Canario es un símbolo que representa a algo que tiene plumas, debido a que
satisface el predicado Plumas. De esta forma tenemos una compulsión sobre que puede hacer
un Canario. Podemos expresar otras compulsiones y otros predicados como por ejemplo, Volar
y Poner Huevos. De hecho, podemos limitar las cosas que Canario puede nominar sobre
aquellas cosas que satisfacen ambos predicados conjuntamente, diciendo que las siguientes
expresiones son ambas VERDAD:
Volar (Canario)
Existe un modo más tradicional para expresar esta idea. Simplemente combinamos la primera
expresión con la segunda expresión y decimos que la combinación es VERDAD:
Por supuesto, podemos decir también que debemos interpretar a Canario como el nombre de
algo que satisface a uno de ambos predicados. Esto es realizado utilizando la siguiente
combinación :
Los lógicos prefieren una notación diferente. O sea escribimos v para representar a y (and) y
escribimos w para representar a o (or).
Podemos en consecuencia escribir las mismas cosas de antes de la forma en que los
lógicos lo harían:
Cuando las expresiones son unidas a través de ∧, decimos que forman una conjunción y cada
parte forma conjuncto. Del mismo modo, cuando las expresiones están unidas a través de ∨,
forman una disyunción y cada parte de forma un disyuncto. Debemos notar que estos
operadores son los denominados conectivos lógicos de la lógica formal y mapean
combinaciones de VERDAD y FALSO a VERDAD y FALSO.
81
Lógica de Predicados
¬ Plumas (Susana)
Para que esto sea VERDAD, Susana debe representar algo para lo cual Plumas (Susana) no
es VERDAD. O sea que Susana debe ser algo para lo cual el predicado Plumas no es
satisfacido. Si utilizamos ⇒, podemos escribir expresiones que se parecen a una de las reglas
antecedente-consecuente, comenzamos con el siguiente ejemplo:
Implicación E2 E2
E1 ⇒ E2 V F
E1 V V F
E1 F V V
Conjunción E2 E2
E1 ∧ E2 V F
E1 V V F
E1 F F F
Disyunción E2 E2
E1 ∨ E2 V F
E1 V V V
E1 F V F
Negación E V F
¬E 5E F V
82
Lógica de Predicados
Quizás es tiempo de ser más preciso acerca de los conectivos considerados (negación,
disyunción, conjunción e implicación) antes de que sea demasiado tarde. Pensando en ellos
como funciones, es fácil definirlos listando los valores aprobados para cada combinación
posible de argumentos. Ello está indicado en la Figura 5.1 utilizando diagramas que se
denominan Tablas de Verdad.
Debemos hacer notar que los conectivos tienen una Precedencia Aceptada. El
símbolo ¬ tiene mayor precedencia que el conectivo de disyunción, ∨, de forma tal que
podemos escribir ¬ E1 ∨ E2, significando con ello la siguiente expresión evitando de esta forma
la posible confusión con otra expresión: (¬ E1) ∨ E2, sin ningún tipo de confusión con la
expresión (¬ E1 ∨ E2).
Observar que los valores de la tabla correspondiente a la implicación, son los mismos
que los valores de verdad en la correspondiente tabla de la expresión siguiente: ¬ E1 ∨ E2 y
podemos decir que ambas expresiones son equivalentes.
(E1 ⇒ E2) ≡ ¬ E1 ∨ E2
œx[Plumas(x) ⇒ Pájaro(x)]
Igual que cualquier otra expresión, la misma puede ser VERDAD o FALSO. Si la misma es
83
Lógica de Predicados
VERDAD, una expresión œ significa que tendremos un valor de VERDAD cuando substituimos
cualquier objeto por la variable x dentro de los corchetes. Por ejemplo si la expresión
œx[Plumas(x) ⇒ Pájaro(x)] es VERDAD, entonces ciertamente la siguiente interpretación
Plumas(Canario) ⇒ Pájaro(Canario) es VERDAD y lo es también en el siguiente caso
Plumas(Susana) ⇒ Pájaro(Susana).
Cuando una expresión está rodeada por los corchetes asociados a un cuantificador,
decimos que la expresión se encuentra dentro de la Extensión (Scope) del cuantificador. En
consecuencia la expresión Plumas(x) ⇒ Pájaro(x) es una Extensión del cuantificador œx[... ].
Cuando esta expresión es VERDAD, significa que existe al menos un elemento que
cuando es substituido por la variable x, hace que la expresión dentro de los corchetes sea
VERDAD. Quizás la expresión Pájaro(Canarios) es VERDAD, de cualquier modo, algo parecido
a Pájaro(Canario) es VERDAD. Expresiones que utilizan el cuantificador (›), denominado
Cuantificador Existencial, se dicen que están cuantificadas existencialmente.
84
Lógica de Predicados
Los términos son los únicos elementos que aparecerán como argumentos de los diferentes
predicados sobre un dominio o conjunto de dominios dados.
Para las FBF existen algunos casos especiales que deben ser considerados, a saber:
* Una Fórmula Bien Formada en la cual todas sus variables, si existen, están
dentro de una extensión del correspondiente cuantificador, es definida como
una Oración. La siguiente expresión es una oración
œx [Plumas(x) ⇒ Pájaro(x)]
Plumas (Albatros) ⇒ Pájaro(Albatros)
La siguiente expresión no es una oración, debido a que contiene una variable libre, la
variable y:
Debemos hacer notar que permitimos variables solo para representar objetos. Está
prohibido utilizar variables para representar predicados. Estamos tratando en consecuencia con
las lógicas denominadas de Cálculo de Predicados de Primer Orden. En una segunda
instancia tenemos el Cálculo de Predicados de Segundo Orden donde se permiten que las
variables representen a los predicados. En cambio una lógica o Cálculo Proposicional no se
permiten variables de ninguna clase.
Una Fórmula Bien Formada que está formada por disyunciones de literales recibe la
denominación de Cláusula.
85
Lógica de Predicados
Tales lógicas pueden ser utilizadas para describir y razonar acerca de partes del
universo visualizado como Estructuras Relacionales, donde la denominada estructura
relacional consiste de un conjunto de entidades E, un conjunto de relaciones definidas sobre E
y un conjunto de funciones sobre E. Las entidades en un subconjunto de E son conocidas
como Entidades Distinguidas.
U = (E, N, R, H)
(a) E es un conjunto de entidades o términos {e1, e2, ...., en}, denominado como el
dominio de la estructura U.
(b) N es el conjunto de las entidades distinguidas {n1, n2, ...., nn}, de forma tal que
N es un subconjunto de E.
(c) R es un conjunto de relaciones {r1, r2, ...., rn} definidas sobre el conjunto de
entidades E.
(d) H es un conjunto de funciones {h1, h2, ...., hn} definidas sobre el conjunto de
entidades E.
Las relaciones y funciones en una estructura relacional puede ser Arity (o sea, que puede
tener varios números de argumentos). Por ejemplo Novios tiene un arity de 2 (dos). Doble tiene
un arity de 1 (uno) y es denominada como una función de un solo argumento.
86
Lógica de Predicados
Una relación también puede ser formalizada como una función Booleana sobre n-
tuplas:
Sea R una relación n-aria sobre un dominio D. El predicado R asociado con la relación
R, está dado por la siguiente expresión:
Por ejemplo:
SQ(2, 1) = F
SQ(2, 2) = F
SQ(2, 3) = F
SQ(2, 4) = V
PR(1) = F
PR(2) = V
PR(3) = V
PR(4) = F
87
Lógica de Predicados
88
Lógica de Predicados
S = { ¬, ∧, ∨, ⇒, ⇔}
donde A(x) es una fórmula determinada y x es una variable lógica. De la misma forma
podemos definir la implicación en la lógica de predicados:
(c) Si t1, t2, t3, .... tn son términos y f es una función n-aria, entonces tenemos que
f(t1, t2, t3, .... tn) es un término.
(d) Si t1, t2, t3, .... tn son términos y p es un símbolo de un predicado n-ario,
entonces tenemos que la siguiente expresión p(t1, t2, t3, .... tn) es una fórmula
atómica.
(b) Si A y B son FBF, entonces tenemos que las siguientes expresiones son
también FBF:
(A) , 5A , A∨B
A∧B , A⇒B , A⇔B
œx A donde x 0 Var , ›x A donde x 0 Var
89
Lógica de Predicados
(c) Las únicas FBF son aquellas obtenidas por un número finito de aplicaciones de
las reglas antes indicadas.
Por facilidad de lectura, las letras x, y, z, w serán utilizadas para representar variables
individuales, cadenas tales como "Sally" son utilizadas para representar constantes
individuales, las letras P, Q, R o cadenas del tipo "Tiene" son utilizadas para representar
predicados y las letras f, g, h o cadenas tales como "Doble" son utilizadas para representar
símbolos de función.
Las fórmulas atómicas y las FBF de L1 están definidas de acuerdo a las reglas dadas
anteriormente. Ejemplos de FBF de L1 son:
(g) Edad (x, y) , y lo leemos de la siguiente forma : "x tiene la edad y".
Las fórmulas (a) a (f) son denominadas fórmulas Cerradas, ya que ellas no contienen variables
libres (las variables, si las hay, están ligadas por uno u otro cuantificador). La fórmula (g) es
una fórmula Abierta. Si A es una fórmula, entonces la extensión de la ocurrencia de un
cuantificador, tal como qx en qx A, es A (donde q = œ o q = ›). Una Ocurrencia de una variable
x en A está Ligada si y solo si está inmediatamente después de un cuantificador o si se
encuentra en la extensión de la ocurrencia de un cuantificador. La ocurrencia de una variable
que no está ligada decimos que es Libre.
3.3.1.- FORMULAS DE PREDICADOS
90
Lógica de Predicados
P = {p, q}
A = {a, b}
X = {x, y}
(x = y) ⇒ (y = x)
2.- œx ›y p(x, y)
Si p es interpretada como una función, entonces p debe ser total.
91
Lógica de Predicados
Esta fórmula solo puede ser cierta en un dominio con al menos dos elementos.
4.- œx p(a, x)
Expresa la existencia de un elemento especial. Por ejemplo, si p es
interpretado como la relación "≤", entonces la fórmula es cierta para a = 1 en el
dominio de los enteros positivos, porque 1 es menor o igual a cada elemento
del dominio. Sobre el dominio de todos los enteros (positivos y negativos), la
fórmula no es cierta o verdadera.
DEFINICIÓN 3.3: Sean A una fórmula, x una variable y a una constante. La siguiente
expresión
A [x ⇐ a], representa la sustitución de a por x y está definida por la
inducción:
* Si A es una fórmula atómica, A [x ⇐ a] es obtenida reemplazando
cada ocurrencia de x en A (si existe) por a.
* Si A = 5A1 , A [x ⇐ a] = 5A1[x ⇐ a].
* Si A = A1 op A2 , A [x ⇐ a] = A1[x ⇐ a] op A2[x ⇐ a].
* Si A = œxA1 , A [x ⇐ a] = A. Similar para A = ›xA1.
* Si A = œyA1 para y … x, A[x ⇐ a] = œyA1[x ⇐ a]. Similar para A =
›yA1.
La siguiente notación:
indica que las variables libres de la fórmula A están en {x1, ..... , xn}. (Usualmente todas estas
variables son libres en A.)
92
Lógica de Predicados
Si la fórmula no tiene variables libres, es denominada una fórmula cerrada. Si {x1, .....
, xn} son todas variables libres de A, es cierre universal de A está dado por:
Por ejemplo, si A(x, y) = p(x, y) tiene dos variables libres {x, y}, ›y p(x, y) tiene una sola variable
libre {x} y œx›y p(x, y) es cerrado. El cierre universal de A(x, y) es œxœy p(x, y) y el cierre
existencial es ›x›y p(x, y).
DEFINICIÓN 3.5: Sea A = œx A(x) una fórmula cuantificada y sea a una constante,
entonces A [x ⇐ a], denotada como A(a) es una instancia de œx A(x).
La operación de sustituir una constante específica por una variable
cuantificada es denominada instanciación.
DEFINICIÓN 3.6: Sea A una expresión, sea x una variable y sea t un término. Entonces
SxtA representa la expresión que se obtiene al sustituir todas las
apariciones de x en A por t. SxtA es denominada como una
particularización (un caso, un ejemplo) de A, y se dice que t es un
caso (instancia) de x.
Solución: Sxa (P(a) ⇒ Q(x)) es (P(a) ⇒ Q(a)), y Syb (P(y) ∨ Q(y)) es (P(b) ∨ Q(b)). Dado
que Q(a) no contiene ningún y, al sustituir todos los casos de y por a se tiene
que Q(a) queda intacto, lo cual significa que:
SxtA Es una operación que puede aplicarse a los predicados; por lo tanto, no es un predicado
en sí mismo y esto hace que SxtA sea una meta expresión.
93
Lógica de Predicados
Una interpretación de una frase debe contener información suficiente para determinar
si la frase es falsa o verdadera. Para estudiar esto, consideremos una frase concreta, tal como
“han pagado todos los clientes”. ¿Qué se necesita para determinar si esta frase es
verdadera?. Evidentemente, necesitamos saber quienes son los clientes, o sea, necesitamos
un universo de discurso. En segundo lugar, es necesario saber quién ha pagado y quién no.
Esto quiere decir que necesitamos alguna forma de asignación del predicado “ha pagado”.
Como segundo ejemplo, consideremos la frase: “y ha solicitado el objeto X”. Para averiguar
si esta frase es verdadera, es preciso una vez más definir el universo de discurso, tal como por
ejemplo, todos los clientes de una empresa de comercialización. Además tenemos que saber
quién es y, y es preciso tener una asignación del predicado “ha solicitado X”. Estos dos
ejemplos sugieren un cierto número de elementos de los cuales hay que disponer para tener
una interpretación. Formalmente una interpretación de una expresión lógica contiene los
siguientes componentes:
Debe quedar en claro que podemos asociar el lenguaje L1 con la estructura relacional
U1, definiendo una interpretación (1 tal que:
(1(Susana) = SUSANA
(1(Roberto) = ROBERTO
(1(Novios) = NOVIOS
(1(20) = VEINTE
DEFINICIÓN 3.7: Sea D un dominio. Una fórmula sobre D está definida como antes
excepto que los elementos de D reemplazan constantes de un
conjunto !.
DEFINICIÓN 3.8: Sea A una fórmula de forma tal que {p1, ..., pn} son todos predicados y
{a1, ..., an} son todas constantes que aparecen en A. Decimos en
94
Lógica de Predicados
* Un dominio no vacío D.
* Una asignación de la relación n-aria Ri sobre D para cada predicado n-ario pi.
* Una asignación de un elemento dj 0 D para cada constante aj.
en las cuales hemos utilizado el operador de menor o igual para las relaciones binarias y el
operador de inclusión para la relación de subcadenas.
J M S
P(x) V V F
Ahora formularemos lo que significa, en general, que una expresión como œx P(x) sea
verdadera. Para la interpretación, seleccionaremos un dominio finito que consta de los n
individuos a1, a2, a3, . . . , an . œx P(x) sólo es verdadero si P(a1), P(a2), P(a3), . . . , P(an) son
todos verdaderos. Por lo tanto, œx P(x) esta dado por:
95
Lógica de Predicados
interpretación dada P(J) es verdadero, y esto basta para hacer que ›x P(x) sea verdadero.
Existe un cliente, Juan, que ha pagado. En el dominio de los n individuos a1, a2, a3, . . . , an
podemos encontrar una expresión para el cuantificador existencial. ›x P(x) es verdadero en
toda la interpretación que haga verdadero a P(a1), o P(a2), o P(a3), o . . . , o P(an). Por lo tanto:
Por ejemplo, utilizando las expresiones (3.4.1) y (3.4.2) podemos demostrar la validez de una
expresión para cualquier dominio finito. Consideremos la siguiente expresión 5œx P(x)
≡ ›x 5 P(x)
Ejemplo 3.4.1: Analicemos la interpretación de la siguiente frase “Hay alguien que admira a
todo el mundo”. El universo de discurso consta de tres personas Juan, María
y Ricardo. El predicado en cuestión es Q; esto es, Q(x, y) significa que “x
admira a y”, la tabla siguiente nos da una asignación para el predicado
mencionado. A partir de esta tabla, se ve que Juan admira a María y a Ricardo,
que María sólo admira a Juan y que Ricardo admira a María y a si mismo. Para
averiguar si la frase planteada es cierta o no, lo mejor es traducirla al cálculo
de predicados. “Hay alguien” se puede expresar como ›x.
Juan F V V F V
María V F F F V
Ricardo F V V F V
œx Q(x, y) F F F
›x Q(x, y) V V V
La frase “x admira a todo el mundo” se puede traducir ahora en la forma œy Q(x, y). Como
resultado, “Hay alguien que admira a todo el mundo” se puede expresar de la siguiente
forma:
›x œy Q(x, y)
Para averiguar si esta frase es cierta, buscaremos primero el valor de verdad de œy Q(x, y).
Para la interpretación dada esta sub expresión es falsa, independientemente del valor de x, por
lo tanto, œy Q(x, y) es falsa para todo x: no existe un valor de x para el cual œy Q(x, y) sea
verdadero y consiguientemente ›x œy Q(x, y) es falso a los efectos de la interpretación
considerada.
96
Lógica de Predicados
siguiente expresión ›x Q(x, y). Esta expresión es verdadera para todo x; es verdadera para
los valores de x = Juan, x = María y x = Ricardo. Esto significa que œx ›y Q(x, y) es verdadero
para la interpretación dada. Con esta misma interpretación, sin embargo, ›x œy Q(x, y) es
falsa, tal como se mostró anteriormente. Por lo tanto, el valor de verdad puede cambiar si se
intercambian los cuantificadores universal y existencial.
œx œy Q(x, y) ≡ œy œx œy Q(x, y)
›x ›y Q(x, y) ≡ ›y ›x Q(x, y)
"1(x) = GUILLERMO
"1(y) = ROBERTO
"1(z) = VEINTE
DEFINICIÓN 3.9:Sea A una fórmula cerrada Definimos a v(A), como el valor de A , bajo una
interpretación I , obtenida reemplazando primero cada constante aj de A por el
elemento del dominio dj asignado y que pertenece a I y luego por inducción
sobre la estructura de A:
En otras palabras, primero utilizamos las asignaciones de los elementos del dominio a
los símbolos constantes (si existe alguno) para transformar la fórmula en una fórmula sobre D.
Luego usar la definición inductiva, la cual reduce la computación del valor de A a preguntas
acerca de las siguientes fórmulas atómicas pi(c1, ...., cn). La fórmula atómica es V si y solo si
esta secuencia de elementos del dominio está en la relación Ri asignada por la interpretación.
97
Lógica de Predicados
[[A]] U, (, "
Debemos resaltar que en (c), la notación de una expresión de una función es una entidad en la
estructura relacional asociada. En general, el valor semántico de una expresión de una función
de la forma siguiente f(t1, t2, t3, .... tn), donde t1, t2, t3, .... tn son términos, está dado por :
o sea que el valor semántico de una expresión función f(t1, t2, t3, .... tn) es obtenido aplicando la
función que está representada por (o sea es el valor semántico de) f para los argumentos que
son denominados por t1, t2, t3, .... tn.
U ⎥= A [(, "]
(a) Si p(t1, t2, t3, .... tn) es una fórmula atómica en L entonces :
U ⎥= p(t1, t2, t3, .... tn) ssi ([[ t1 ]] (, ", . . . , [[ tn ]] (, ") 0 [[ p ]] (, "
O sea que U satisface una fórmula atómica p(t1, t2, t3, .... tn) con respecto a una
interpretación ( y a una valorización " si y solo si (e1, e2, e3, .... en) 0 r, donde r es la
relación asignada a p por (, y ei es la entidad asignada a ti por (, o ".
(7) U ⎥= ›x A [(, "] ssi existe una entidad e en U tal que U ⎥= A [(, "'] , donde "'
es idéntica a " excepto que "' (x) = e mientras que " (x) puede serlo.
98
Lógica de Predicados
(8) U ⎥= œx A [(, "] ssi para toda entidad e en U tal que U ⎥= A [(, "'] , donde "'
es idéntica a " excepto que "' (x) = e mientras que " (x) puede serlo.
A ≡ œx p(a, x)
œx p(x) ⇒ p(a)
Suponer que la fórmula anterior no es válida, debe existir entonces una interpretación (D, {R},
{d}) tal que v(œx p(x)) = V y v(p(a)) = F. Por la definición inductiva de v, para todo c 0 D, v(p(c))
= V, o sea que tenemos que c 0 R. En particular, ya que d 0 D, d 0 R, entonces v(p(d)) = V
contradiciendo con la expresión v(p(d)) = F.
›x p(x) ⇒ p(a)
99
Lógica de Predicados
no es válida ya que es posible encontrar una interpretación de forma tal que se cumpla que
v(p(d')) = V y v(p(d)) = F para algún valor que cumpla con d' ≠ d.
p(x) w q(y)
DEFINICIÓN 3.14: Una fórmula o expresión B que no tenga ningún modelo se denomina
una expresión contradictoria.
es suficiente si solo si existe una interpretación I y una asignación de valores del dominio (d1,
...., dn) a las variables libres, tal que se cumpla:
TEOREMA 3.1: Una fórmula no cerrada A(x1, ...., xn) es suficiente si y solo si lo es un
cierre existencial:
si y solo si:
100
Lógica de Predicados
œx1 ....œxn A(x1, ...., xn) ≡ œx1 ....œxn A'(x1, ...., xn)
Tal como en el cálculo proposicional, se pueden utilizar las equivalencias lógicas para
manipular fórmulas, y se pueden utilizar las implicaciones lógicas como base para unos
argumentos correctos. Tal como en el cálculo proposicional, escribiremos A1, A2, . . . , An ⎥= C,
si A1, A2, . . . , An en conjunto implican lógicamente a C.
La ley siguiente la utilizaremos como ejemplo. Sin embargo esta ley es muy importante.
Estas dos equivalencias son válidas. Dado que V⇒ Q(x) es Q(x), el lado izquierdo de (3.5.2) se
reduce a œx Q(x). Por una razón similar el lado derecho de (3.5.2) se reduce a œx Q(x) y es
evidente que œx Q(x) ≡œx Q(x) es verdadera. Además la expresión (3.5.3) es verdadera,
porque ambos lados son siempre verdaderos F ⇒ œx Q(x) es trivialmente verdadero por
definición de implicación lógica. En conclusión la expresión (3.5.1) es válida
independientemente de que P sea verdadero o falso.
Por tanto si es cierto que ”para todo el mundo que si brilla el sol y hace buen tiempo,
entonces son felices, se puede concluir que si brilla el sol y hace buen tiempo, entonces
todo el mundo es feliz”.
101
Lógica de Predicados
El resto de esta sección motiva y explica alguna de las fórmulas más importantes de
esta lista. Consideremos las siguientes fórmulas:
muestran que cualquier cuantificador puede ser definido en términos del otro cuantificador. Ello
puede ser utilizado en desarrollos teóricos para reducir el número de casos que deben ser
tratados. Otras fórmulas importantes que relacionan a los cuantificadores, son las indicadas a
continuación:
œx A(x) ⇒ ›x A(x)
›xœy A(x, y) ⇒ œy›x A(x, y)
pero solo es válido en una dirección para los cuantificadores existenciales sobre la conjunción y
para los cuantificadores universales sobre la disyunción.
102
Lógica de Predicados
v(A(d)) = V
v(B(d')) = V
v(›x(A(x) v B(x))) = F
Si una subfórmula no contiene variables libres, entonces los cuantificadores sobre tal
variable pueden ser pasados libremente a través de la subfórmula:
recordando que cuando una variable no es libre debe cumplirse la siguiente condición B[x ⇐
d] = B. De forma tal que:
Fórmulas similares para la implicación pueden obtenerse a partir de las fórmulas para
la disyunción reemplazando la implicación por la disyunción equivalente y observando la
alteración de los cuantificadores a medida que la negación pasa a través de ellos:
œx(A(x) ⇒ B) ≡
œx(5A(x) w B) ≡
œx5A(x) w B ≡
5›x A(x) w B ≡
›x A(x) ⇒ B
Las fórmulas para implicación no son siempre obvias y deber ser estudiadas muy
cuidadosamente.
siguiendo las fórmulas para '›' sobre 'w' y 'œ' sobre 'v', respectivamente. Consideremos la
siguiente expresión:
103
Lógica de Predicados
podemos además probar su validez. Sea I una interpretación arbitraria de forma tal que se
cumpla lo siguiente:
v(5œx A(x)) = V
entonces
v(›5x A(x)) = V
tal que d sea algún elemento de dominio en D 0 I tal que v(5A(d)) = V. A partir del antecedente
de la fórmula:
œx(A(x) w B(x))
obtenemos lo siguiente
v(A(d) w B(d)) = V
v(›x B(x)) = V
Aplicando dos reglas-" a fórmulas de la forma 5(A ⇒ B), podemos obtener el siguiente
conjunto de fórmulas para las cuales no se pueden aplicar más reglas de cuadros
proposicionales:
La fórmula 5œx q(x) es equivalente a ›x 5q(x), tal que si queremos crear un contra-ejemplo,
debemos instanciar la fórmula con algún elemento de dominio concreto siendo substituido por
x. Más allá de inventar algún dominio artificial, usaremos el conjunto de los símbolos
constantes como un dominio. Sea a 0 A, establecido para un elemento de dominio y extendido
104
Lógica de Predicados
al cuadro con un nuevo nodo cuya etiqueta reemplaza la fórmula cuantificada con la siguiente
instanciación:
Las dos primeras fórmulas son cuantificadas universalmente, de forma tal que imponen
requerimientos sobre cada elemento del dominio propuesto. Por lo tanto, instanciamos cada
uno de ellos para el elemento de dominio a, que hemos introducido. En dos etapas obtenemos
lo siguiente:
la cual es satisfecha pero no es válida (Figura 3.6.1). Tenemos un cuadro cerrado, pero para
una fórmula que no es válida. ¿Qué hemos realizado en forma errónea?. La respuesta es que a
no tendría que haber sido elegido como un elemento de dominio para la instanciación de 5œx
p(x), si ya fue elegido para 5œx q(x). En realidad la fórmula es verdadera en todas las
interpretaciones sobre dominios de un único elemento. Cuando creamos elementos de dominio
para fórmulas existenciales, debemos elegir un nuevo elemento cada vez. Si elegimos una
constante diferente, la quinta línea del cuadro es:
105
Lógica de Predicados
Ahora debemos instanciar la fórmula universal con b, ya que debe ser cierta para todos los
elementos del dominio, pero desafortunadamente, la fórmula ha sido ya utilizada en la
construcción del cuadro. Para evitar esto, las fórmulas universales nunca deben ser borradas
de la etiqueta de un nodo. Ellas permanecen como reservas de posibles interpretaciones para
cada nueva constante (elemento de dominio) que es introducida.
seguido por:
Dejamos como ejercicio la extensión del cuadro utilizando reglas-$, y para demostrar que
exactamente una rama del cuadro está abierta, definimos el modelo:
v(p(a)) = v(q(b)) = V
v(p(b)) = v(q(a)) = F
A1 = œx›y p(x, y)
A2 = œx5p(x, x)
A3 = œxœyœz(p(x, y) v p(y, z) ⇒ p(x, z))
Obviamente, las primeras dos etapas pueden ser reglas-" para descomponer la conjunción
para obtener el conjunto de fórmulas:
A1, A2, A3
Ahora tenemos un problema menor, ya que debemos instanciar las fórmulas cuantificadas
universalmente, pero no se han introducido constantes por intermedio de las fórmulas
existenciales. Recalcamos que la definición de una interpretación requiere que el dominio no
sea un conjunto vacío, de forma tal que podemos elegir arbitrariamente un elemento a1, el cual
se encuentra en el dominio. La construcción del cuadro continua a través de la instanciación de
A1 para obtener la siguiente subfórmula ›yp(a1, y) y luego realizar la instanciación de la fórmula
existencial con una nueva constante (Figura 5.4). Notar que ya que A1 es universal, la misma
es copiada en la etiqueta de un nuevo nodo.
106
Lógica de Predicados
Continuando, la nueva constante a2 debe ser utilizada para instanciar nuevamente a A1 (Figura
5.6.2). Este proceso no finalizará. En lugar de ello, creamos una secuencia de finalización de
elementos de dominio a1, a2, .... de forma tal que p(ai, ai+1) debe ser verdadero. También
podemos instanciar A2 o A3 con cualquier constante que no cierre o finalice al cuadro
semántico. En tal caso tenemos un cuadro que no cierra ni termina y al cual lo definimos como
un modelo infinito, o sea, un modelo con un dominio infinito. De hecho, (ù, {<}) es un modelo
para la fórmula A.
Si j = i, p(ai, ai), producirá el cierre del cuadro cuando se está instanciando a A2 con ai para dar
5 p(ai, ai).
están alrededor del nodo etiquetado. Desde p(aj, aj+1) y p(a1, aj+2), por intanciación de A3 y
utilizando las reglas-$, obtenemos p(aj, aj+2). Repitiendo el proceso, p(aj, ai) eventualmente será
obtenida en el nodo etiquetado. Pero conjuntamente con p(aj, aj) obtenido por la intanciación
original ocasiona el cierre del cuadro cuando es instanciado A2.
Debemos desarrollar la maquinaria teórica para tratar con dominios infinitos. Podemos
concluir también que la construcción de un cuadro semántico no es un procedimiento de
decisión para validar el cálculo de predicado. Podemos no conocer nunca si una rama que no
está cerrada define realmente un modelo infinito o si será eventualmente cerrada, por ejemplo,
en una secuencia de un millón de aplicaciones de la reglas del cuadro. Por supuesto, esto no
prueba que no exista un procedimiento de decisión para el cálculo de predicado, solo que el
método del cuadro semántico no es un procedimiento de decisión. Una complicación final en la
construcción de la tabla semántica está dada por la fórmula:
107
Lógica de Predicados
A1 v A2 v A3 v œx(q(x) v 5 q(x))
tal que
A1, A2, A3, œx(q(x) v 5 q(x))
En el cálculo proposicional, las fórmulas siempre simplifican, tal que cada fórmula en la etiqueta
de un nodo eventualmente tiene una regla aplicada a ella. Sin embargo, una vez que
requerimos que fórmulas cuantificadas universalmente no sean borradas, podemos finalmente
aplicar reglas a A1 y nunca rodearla utilizando la cuarta subfórmula, la cual cierra
inmediatamente el cuadro. De esta manera, una construcción semántica es necesaria para
asegurar qué reglas serán eventualmente aplicadas a todas las fórmulas etiquetando un nodo
del cuadro.
* Si A es una fórmula ( (tal como œxA1(x)), crear un nuevo nodo l' como un hijo de l y etiqueta
l' con:
* Si A es una fórmula * (tal como ›xA1(x)), crear un nuevo nodo l' como un hijo de l y etiqueta
l' con:
Final de la Construcción
( ((a)
œxA(x) A(a)
5›xA(x) 5A(a)
108
Lógica de Predicados
* *(a)
›xA(x) A(a)
5œxA(x) 5A(a)
La diferencia entre conjunto y lista de fórmulas, es que la lista está ordenada. La barra
" *" es usada para indicar la posición actual del puntero dentro de la lista, la i-ava fórmula Ai.
Además, un nodo está etiquetado con una lista de todas las constantes utilizadas en todas las
instanciaciones de las fórmulas en los nodos sobre la rama o arco a partir de la raíz de este
nodo:
Seleccionar la próxima hoja lr a partir de la lista ‹. lr está etiquetado con una lista de fórmulas
U(lr):
109
Lógica de Predicados
Si U(lr) contiene un par complementario de literales, borrar lr a partir de la lista de hojas. De otro
modo, extender el cuadro de acuerdo a los casos sobre la estructura de la fórmula Ai:
* Si Ai es un literal, entonces:
Final de la Construcción
Inicialmente la etiqueta de la raíz es U(n0) = [* A], donde A es la fórmula cuyo cuadro estamos
creando, la lista de las constantes es A = [ * a1, ....., am] donde A = { a1, ....., am} es el conjunto
de las constantes que aparecen en A y la lista de hojas es [* n0]. Si no existen constantes en A,
elegir una constante arbitraria a y seleccionar A = [* a].
En otras palabras: los literales atraviesan creando un nodo superfluo. Las fórmulas -"
y -$ se comportan de la misma forma que en los casos anteriores -la fórmula original es
borrada y reemplazada por sub fórmulas. Las fórmulas -( permanecen en la etiqueta y además
se crea una instancia con la próxima constante de la lista. Las fórmulas -* son borradas y
reemplazadas por una instancia usando una nueva constante.
110
Lógica de Predicados
LEMA 3.2: Sea b una rama abierta del cuadro sistemático, n un nodo de b, y A una
fórmula de U(n). Luego se aplica una regla a A (eventualmente durante la
construcción) para algún nodo n' sobre b, tal que n' $ n. Además, si A es una
fórmula -( y a es una constante que aparece en b, entonces sobre tal n', la
regla -( crea una instancia de A con a.
5.- Si A es una fórmula -*, tal que ›x A'(x), A'(a) 0 U para alguna de las
constantes a en U.
TEOREMA 3.4: (Lema de Hintikka para el Cálculo de Predicado) Sea b una rama
abierta de un cuadro sistemático y U = Un0b U(n). U es el conjunto
de Hintikka.
LEMA 3.3: Sea U un conjunto de Hintikka. Por lo tanto existe un modelo (se valida la
interpretación) para U.
Demostración: Sea A = {a1, ....} el conjunto de constantes que aparecen en las fórmulas de U.
Definimos una interpretación I de la siguiente forma.
111
Lógica de Predicados
La relación está bien definida por la Condición 1 de la definición de los conjuntos de Hintikka.
Demostración: Supongamos que el cuadro para 5 A no está cerrado. Luego existe una
rama abierta b tal que U, la unión de las etiquetas de los nodos sobre b,
forman un conjunto de Hintikka a través del Lema de Hintikka. Por el Lema
5.5.6 existe un modelo I para U.
A partir de œx A(x) debería ser posible derivar A(t) para cualquier término t. Por
ejemplo si, A(x) significa “x está dormido”, entonces œx A(x) significa “todo el mundo está
dormido”, y de aquí debería ser posible derivar, por ejemplo, que Juan está dormido. Más
formalmente, si x representa una variable, t representa un término y A representa una
expresión, entonces la expresión siguiente debería ser válida:
œ x A ≡ > S xt A
œx A
S xt A
112
Lógica de Predicados
Sócrates es mortal.
Ejemplo 3.7.2: Como segundo ejemplo, derivamos que Pablo es hijo de David a partir de
las siguientes premisas:
Toda persona cuyo padre sea David debe ser o bien su hijo o bien su hija.
113
Lógica de Predicados
1.- œx (f(D, x) ⇒ s(x, D) w d(x, D)) Premisa Toda persona cuyo padre
sea David, debe ser o
bien su hijo o bien su hija
A
œx A
Esta regla de inferencia se denomina Generalización Universal (GU). Dado que x
queda ligada en el proceso, decimos que la generalización universal es con respecto a x, o
bien que se generaliza sobre x. Debemos hacer notar que la generalización universal está
sometida a restricciones. Si se generaliza sobre x, entonces x no debe aparecer en ninguna
premisa como variable libre. Si x aparece como variable libre en alguna premisa, entonces x se
refiere al mismo, y está fijada en ese sentido. Por ejemplo, si P(x) aparece en una premisa,
entonces P(x) sólo es verdadero para x, y no es necesariamente verdadero para ningún otro
individuo. Si x está fijado, entonces no se puede generalizar sobre x. Las generalizaciones que
parten de un solo individuo para llegar a toda una población son incorrectas. Por otra parte, si x
no aparece en ninguna premisa o si x está ligada en todas las premisas, entonces se supone
que x representa a cualquier individuo, y se puede aplicar sin restricción la generalización
universal. Para demostrar la generalización universal desarrollaremos algunos ejemplos.
114
Lógica de Predicados
œx Q(x)
Ejemplo 3.7.4: Derivaremos œyœx P(x, y) a partir de œxœy P(x, y). Esta derivación se
desarrolla en la Figura 6.1.4. Esto confirma el hecho de que los
cuantificadores universales se pueden intercambiar. En la Figura 6.1.5 se da
un tercer ejemplo de la Generalización Universal, ejemplo que muestra que
la variable x de un cuantificador universal se puede cambiar por la variable
y.
115
Lógica de Predicados
116
Lógica de Predicados
ninguna variable. Por tanto, si x no es libre en ninguna otra premisa, es posible generalizar
sobre x aun cuando x aparezca como variable libre sobre B.
Ejemplo 6.6: Supongamos que S(x) denota a la expresión “x ha estudiado” y que P(x)
denota la expresión “x ha aprobado”. La premisa es que todo el que haya
estudiado ha aprobado. Demostrar que los que no hayan aprobado no han
estudiado.
117
Lógica de Predicados
Ejemplo 3.7.7: Sea P(x, y, z): x + y = z. Dadas las premisas P(x, 0, x) y P(x, y, z) ⇒ P(y, x,
z) donde x, y, z son variables verdaderas, demostrar que 0 + x = x, o sea,
P(0, x, x).
Solución: Se utiliza la derivación siguiente para demostrar que P(0, x, x). Observese
que la dos primeras líneas son premisas, y que x, y, z se han declarado
explícitamente como variables verdaderas.
118
Lógica de Predicados
Ejemplo 3.7.8: Q(a, y, z) y Q(y, b, c) son expresiones que aparecen en líneas diferentes.
Mostrar que estas dos expresiones se unifican, y dar un unificador. Aquí a,
b, y c son fijas e y y z son variables verdaderas.
Solución: Si “madre(x, y)” es un predicado tal que toma el valor verdadero cuando x
es la madre de y, y si “hermana(x, y)” y “tía(x, y)” de definen de forma
similar, podemos enuncia las premisas de la siguiente forma:
Ahora el problema es crear una expresión que unifique con el antecedente de la línea
1. Para hacer esto, se combinan las líneas 2 y 3, obteniendo:
Las demostraciones que se acaban de dar son sencillas, en el sentido de que sólo
119
Lógica de Predicados
hay unas pocas expresiones disponibles para la unificación, lo cual hace que sea relativamente
sencillo decidir el paso siguiente. En casos más complicados, la selección de posibles
expresiones que están disponibles para la unificación es más extensa, y la decisión deja de ser
trivial. Para hacer una buena elección en lo referente a las expresiones que hay que unificar a
continuación, es preciso pensar en la meta que se persigue. En algunos casos, es necesario
considerar todas las expresiones que se puedan derivar, y seleccionar aquella que, en algún
sentido, sea la más próxima a la conclusión. Este suele ser un buen sistema, aun cuando falle
en algunos casos. En otras ocasiones, esta política no resulta aplicable porque no está claro lo
que se encuentra más próximo o más alejado de la conclusión.
Si la tía Claudia tiene más de cien años, entonces es evidente que hay alguien, a
saber, la tía Claudia, que tiene más de cien años. Si existe algún término t para el cual sea
válida P(t), entonces se puede concluir que algún x satisface P(x). Consiguientemente, P(t)
implica lógicamente lo siguiente: ›x P(x). Más generalmente ›x A se puede derivar que
X
partiendo de S t A, en donde t es cualquier término. Esto da lugar a la siguiente regla de
inferencia:
S Xt A,
›x A
Ejemplo 3.7.10: Sea C la tía Claudia, y supongamos que P(x) indica “x tiene más de 100
años”
Entonces se tiene:
P(C)
›x P(x)
120
Lógica de Predicados
121
Lógica de Predicados
Si es cierto que ›x P(x), entonces tiene que existir algún término t que satisfaga P(x);
X
esto es, tiene que ser cierto S t P(x) para algún t . Por ejemplo, si P(x) significa “x da saltos
mortales”, entonces ›x P(x) significa que S Xt P(x) = P(t) tiene que ser cierto para algún t . El
problema es que no sabemos para que término. Si sabemos que alguien da saltos mortales,
seguimos sin saber si es la tía Eulalia, el tío Petronio o, incluso, alguna otra persona que da
saltos mortales. En una demostración, por lo tanto, hay que mantener abierta la cuestión de
quién es el individuo que da saltos mortales.
Para hacer esto, seleccionamos una nueva variable, digamos b, para denotar a este
individuo desconocido. Ello da lugar a la siguiente regla de inferencia:
›x A
S XAb
Ejemplo 3.7.12: Supongamos que hay alguien que haya ganado 100 millones y deseamos
demostrar que alguien es rico. Entonces las premisas son:
Deseamos demostrar que estas dos frases implican lógicamente la siguiente frase:
Ejemplo 3.7.13: Demostraremos en la Figura 3.7.10 que œx 5P(x) implica lógicamente que
5›x P(x) Según se vio en apartados anteriores, demostrar una negación es
algo que suele hacerse normalmente mediante una demostración indirecta:
122
Lógica de Predicados
para demostrar 5A, uno supone que A es cierto y deriva una contradicción.
Dado que deseamos demostrar que 5›x P(x), la suposición que hay que
rechazar es ›x P(x). Aún cuando esta suposición es cierta, la derivación se
ha sangrado. La particularización existencial nos permite derivar P(b) en la
línea 2, lo cual contradice a 5P(b) que se ha derivado en la línea 4
empleando una particularización universal. La contradicción resultante se
encuentra en la línea 5. Esta línea nos permite rechazar la suposición ›x
P(x); esto es, tiene que ser cierto que 5›x P(x). Por lo tanto, œx 5P(x)
implica 5›x P(x).
123
Lógica de Predicados
1.- Para cada uno de los predicados siguientes, halle un universo de discurso adecuado
dentro de la lista siguiente: números reales, enteros, seres humanos y animales.
a) pájaro(x) b) está casado(x) c) par(x)
d) negativo(x) e) madre(x , y) f) tiene alas(x)
2.- Confeccione las tablas de verdad de los siguientes predicados siendo el universo de
discurso el conjunto U = {1 , 2 , 4 , 8}
a) P ( x ): x es primo
b) Q( x ): x es potencia de 2
c) R( x , y ): x es mayor o igual que y
d) S ( x , y ): x es divisor de y
e) T( x , y ): x es el doble de y
3.- Exprese las siguientes frases en cálculo de predicados suponiendo que el Universo de
Discurso es: I ) El conjunto de los Nº Naturales; II ) El conjunto de los Nº Enteros.
a) Todos los números naturales son pares
b) No existen números naturales negativos.
c) Por lo menos un número natural es múltiplo de 3.
d) Ningún número natural es raíz de la ecuación x2 + 1 = 0
e) Los números naturales son primos.
4.- En el dominio de los números naturales, ¿cómo traduciría las frases siguientes?
a) Algunos números primos son pares
b) Todos los números pares son mayores que 1
c) Los números pares son primos solamente si son menores que 3
d) No hay primos menores que 3.
6.- Traduzca las siguientes frases al lenguaje de cálculo de predicados. Suponga que el
universo está formado por todas las personas.
a) Alguien que es amable con todo el mundo.
b) Todos queremos a alguien.
c) Nadie es cariñoso con todos los demás.
7.- Particularizar:
a) Sx3 P(x) b) Sxa (P(x) ⇒ Q(b))
c) Syb (P(a) ∧ Q(y)) d) Sxa (P(x)∧ Q(y) ∧R(x, y))
124
Lógica de Predicados
a)
a b c
P(x) V V V
b)
a b c
P(x) V F F
c)
a b c
P(x) F F F
10.- Un universo contiene los tres individuos a , b y c. Para estos individuos, se define un
predicado Q( x , y ) y sus valores de verdad están dados por la tabla siguiente:
Q(x, y) a b c
a V F V
b F V V
c F V V
P(x, y) A B C Q(x, y) A B C
A V V F A F F V
B F V V B V F V
C V V V C F V V
12.- Sea un universo de discurso que consta de tres personas solamente, a saber, Juan,
Juana y María. Los tres son alumnos, y ninguno de ellos es rico. Denote con A(x), M(x),
V(x) y R(x) a las propiedades de ser alumno, mujer, varón y rico respectivamente.
Confeccione una tabla con los valores de verdad de los predicados A, M , V y R, y
encuentre el valor de verdad de:
125
Lógica de Predicados
14.- Construya una derivación formal para demostrar que los siguientes argumentos son
válidos:
d) ∀x (P(x) ⇒ Q(x))
∀x (Q(x) ⇒ R(x))
∴ ∀x (P(x) ⇒ R(x))
15.- Considere la siguiente expresión: ∀x P(x) ∨ ∀x (Q(x) ⇒ P(x)). Traslade todos los
cuantificadores universales al comienzo de esta expresión.
16.- Considere la siguiente expresión: ∃x P(x) ∧ ∃x (Q(x) ⇒ P(x)). Traslade todos los
cuantificadores existenciales al comienzo de la expresión.
a) ∀n ∈ ℵ, n < 3 b) ∃ n ∈ ℵ / n3 - n = 0
c) ∀n ∈ ℵ, (n + 1) 2 = n 2 + 2n + 1 d) ∃ n ∈ ℵ / n2 + 1 = 0
e) ∀ x ∈ ℜ, x 2 > x f) ∀x ∈ ℜ / ⏐x⏐ = x
g) ∃ x ∈ ℜ, x 2 + 3x - 6 + 0 h) ∃ x ∈ ℜ / 1/x ∉ ℜ
i) ∃ x / x > 1 ∧ x2 = 9 j) ∀x , [ x ≠ 0 ⇒ x 2 > 0]
126
Lógica de Predicados
18.- Interprete las equivalencias dadas en la siguiente tabla, pues la usará posteriormente
TABLA 1
EQUIVALENCIAS QUE IMPLICAN CUANTIFICADORES
∀x A ≡ A Si x no es libre en A
∃x A ≡ A Si x no es libre en A
∀x A ≡ ∀y SXy A ∧ ∀x A Si y no es libre en A
∀x(A ∨ B) ≡ A ∨ ∀x B Si x no es libre en A
∃x(A ∧ B) ≡ A ∧ ∃x B Si x no es libre en A
∀x(A ∧ B) ≡ ∀x A ∧ ∀x A
∃x(A ∨ B) ≡ ∃x A ∨ ∃x B
∀x∀y A ≡ ∀y∀x A
∃x∃y A ≡ ∃y∃x A
¬ ∃x A ≡ ∀x ¬ A
¬ ∀x A ≡ ∃x ¬ A
a) ∃x(P(x) ∨ Q(x))
b) ∀x(A(x) ∧ ¬ B(x))
c) ∀x∃y [(A(x, y) ∧ B(x, y)) ⇒ C(x, y)]
d) ∀x∃y [P(x, y) ⇒ (R(x, y) ∨ S(x, y))]
20.- Las siguientes reglas nos permiten hacer derivaciones en cálculo de predicados:
TABLA 2
REGLAS DE INFERENCIA PARA CÁLCULO DE PREDICADOS
127
Lógica de Predicados
22.- Probar que las siguientes fórmulas son válidas para todas las interpretaciones,
utilizando cuadro semántico:
23.- Para las siguientes fórmulas probar ya sea que es válida o dar una interpretación que
la falsifique dentro de cierto dominio:
128
Lógica de Predicados
24.- Probar que las siguientes fórmulas (Axiomas dentro del Sistema Axiomático de Hilbert)
son siempre válidas:
25.- Probar si es factible deducir las siguientes fórmulas a partir de algunos de los axiomas
de l problema 4 o de alguna suposición válida o inválida:
========================================
129
Retículo y Algebra de Boole
CAPITULO IV
• Sea capaz de extender un orden parcial para convertirlo en un orden total que
contenga las relaciones del orden parcial.
Aunque son definiciones ya conocidas vamos a recordar, en este primer párrafo, los
conceptos que necesitamos.
131
Retículo y Algebra de Boole
A un par (A, R) formado por un conjunto y una relación de orden parcial le llamaremos
conjunto parcialmente ordenado. Si la relación es de orden total diremos conjunto
totalmente ordenado.
Ejemplo 4.1.1.-
i) Como ya señalamos en el capítulo tercero, los números naturales
admiten una relación de orden total que viene definida por: dados a, b
∈ se dice que b ≥ a si o bien b = a o bien existe un número natural c
tal que b = a + c.
ii) También vimos que los números enteros admiten una relación de
orden total que es una extensión natural de la relación definida en los
números naturales: a ≤ b si y solamente si b – a ∈ + ∪ {0}.
iii) Los números reales admiten una relación de orden total definida por la
+
existencia de la semirrecta real positiva , (un subconjunto de con
las propiedades de que para cada a ∈ no nulo o bien a o bien –a
pertenecen a +; si a, b ∈ + entonces a + b ∈ +, ab ∈ + y 0 ∉ +)
de modo que a ≤ b si y solamente si b – a ∈ + ∪ {0}.
iv) Sea el conjunto F = {r/s : r,s ∈ s ≠ 0}. La relación que se define
como r/s ∼ u/v si y solamente si ru = su es una relación de
equivalencia en F.
v) En el conjunto de los números enteros hemos definido la relación de
equivalencia módulo p: a ≡ b mod p si y solamente si a – b es un
múltiplo de p.
vi) Dados dos conjuntos A y B, una función A en B es una relación R ⊂ A
× B con las propiedades: el dominio de R es A; para cada elemento a ∈
A existe un único elemento b ∈ B tal que (a, b) ∈ R.
ā = {b ∈ A : b ∼ a}
132
Retículo y Algebra de Boole
Solución:
A = {a : a ∈ A}
~
Ejemplo 4.1.3.-
i) Como ya vimos, la relación de congruencia módulo p es una relación
de equivalencia en y el conjunto cociente es:
{
Z p = 0 ,1 ,..., p − 1 }
ii) El conjunto conciente del conjunto F del ejemplo iv) del párrafo anterior
por la relación de equivalencia allí definida es el conjunto de los
números racionales.
b) Sea A = {a, b, c, d} y R={(a, a),(b, b),(c, c),(d, d),(a, b),(a, c),(b, c)}
133
Retículo y Algebra de Boole
Solución:
ii) Es reflexiva pues {(a, a),(b, b),(c, c),(d, d)} ⊂ R. No es simétrica pues (a, b) ∈
R pero (b, a) ∉ R. Es antisimétrica pues nunca se tienen m ≠ l tal que (m, l) ∈
R y (l, m) ∈ R. Es transitiva pues el único caso relevante es (a, b),(b, c) ∈ R y
efectivamente (a, c) ∈ R. Por lo tanto es una relación de orden (parcial) pero
no de equivalencia. Su diagrama de Hasse está en la Figura 4.1.1.
iii) Como todo número entero no nulo n tiene el mismo signo que n se tiene la
propiedad reflexiva. Si a, b enteros no nulos verifican que signo(a) = signo(b)
entonces signo(b) = signo(a) con lo que la relación es simétrica. También es
transitiva pues se tiene que si signo(a) = signo(b) y signo(b) = signo(c)
entonces signo(a) = signo(c). Por tanto es una relación de equivalencia y no
es de orden porque no es antisimétrica (hay
números distintos con el mismo signo).El e
conjunto cociente tiene dos elementos,
digamos signo+ y signo-, que son, d
respectivamente, la clase de equivalencia de
los positivos y la de los negativos.
c
iv) Es reflexiva pues para cada número real a
se tiene que a – a = 0 ∈ . Es simétrica ya
que si a – b ∈ entonces la suma es un
número entero: a – b + b – c = a – c ∈ Z. a b
Por tanto es una relación de equivalencia
que no es de orden..Se tiene que ā = {a + k: Figura 4.1.1
k ∈ }.
134
Retículo y Algebra de Boole
Δ= {(a, a) : a ∈ A}
Ejemplo 4.2.1.-
Vamos a ver como la relación también puede ser representada por un grafo dirigido
que llamaremos grafo dirigido asociado a la relación. Esté multidigrafo puede tener lazos
(elementos de la forma (a, a)) y puede tener, como máximo, dos aristas conectando dos
vértices a y b (las aristas (a, b) y (b, a)).
Ejemplo 4.2.2.-
La propiedad simétrica consiste en que cada par de vértices adyacentes presentan dos
aristas (una en cada sentido) que los conectan.
135
Retículo y Algebra de Boole
En el ejemplo i) se ve que es reflexiva (un lazo sobre cada vértice) y antisimétrica (no
hay dos vértices conectados por dos artistas).
En el ejemplo ii) se ve que es simétrica (dos aristas entre cada par de vértices
conectados y no es reflexiva (por ejemplo el vértice 2 no es adyacente con el mismo).
Ejemplo 4.2.3.- Sean los siguientes conjuntos y relaciones definidos sobre ellos.
Representarlas mediante tablas y grafos dirigidos y verificar que propiedades
satisfacen.
Solución:
136
Retículo y Algebra de Boole
DEFINICIÓN 4.8.- Dada una relación R en un conjunto A se define una matriz asociada a
la relación M como una matriz de adyacencias del grafo dirigido
asociado a la relación.
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
Ejemplo 4.2.5.- Computar las matrices de adyacencias de los grafos del Ejemplo 4.2.3.
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
0 0 1 0 0 1 0 0 1 0
0 0 0 1 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1
0 1 1 1 1 1
0 0 1 1 1 1
0 0 0 1 1 1
0 0 0 0 1 1
0 0 0 0 0 1
0 0 1 1
0 1 0 0
0 0 1 1
0 0 0 1
137
Retículo y Algebra de Boole
Si i = j o j = k no hay nada que comprobar. En caso contrario, existe un camino de longitud dos
entre vi y vk por lo que mij(2) ≠ 0. Por hipótesis se tiene mij ≠ 0, con lo que (vi, vk) ∈ R, como
queríamos demostrar.
Por otro lado (la implicación en el otro sentido) si R es transitiva y mij(2) ≠ 0 entonces
existe un camino de longitud 2 entre vi y vj por tanto existirá un vértice vk de modo que (vi, vk)
∈ R y (vk, vj) ∈ R. Por la transitividad de R se tiene que (vi, vj) ∈ R, es decir mij ≠ 0, como
queríamos demostrar.
Esto quiere decir que para comprobar la transitividad de una relación basta ver que M2
no tiene entradas no nulas nuevas con respecto a M.
Ejemplo 4.2.6.- Sea el conjunto A = {a, b, c, d} y la relación R = {(a, a), (b, b), (a, b), (b, a)}. La
relación es transitiva porque M2 = 2M.
Ejemplo 4.2.7.- Comprobar si las relaciones del ejercicio 144 son transitivas mediante esta
caracterización de la transitividad.
138
Retículo y Algebra de Boole
Ejemplo 4.3.1.- Tenemos una red de ordenadores numerados del 1 al 5 y tenemos cables de
comunicación del 1 al 2, del 2 al 3, del 1 al 4 y del 2 al 5. Aunque el 1 y el 3 no
están directamente comunicados entre sí, se pueden comunicar a partir del 2.
Nos interesaría conocer los ordenadores que están conectados entre sí.
De la teoría de grafos podemos extraer una solución sin más que preguntarnos por las
componentes conexas del grafo cuyos vértices son los ordenadores y sus aristas las
comunicaciones directas.
En el contexto de las relaciones podemos definir una relación N5 de modo que (a, b) ∈
R si y solamente si el ordenador con número a está conectado directamente con el que tiene
número b (o a = b o hay un cable directo entre a y b). Ésta relación es claramente reflexiva y
simétrica por definición. El problema de encontrar todas las parejas de ordenadores conectados
(directa o indirectamente), es equivalente al cómputo de la clausura transitiva, es decir, el
mínimo conjunto de parejas C que contiene a R y hace que C sea transitiva.
Cr = R ∪ Δ.
Ejemplo 4.3.2.-Sea el conjunto 10 y sobre él la relación de menor escrito <. Ésta relación no
es reflexiva porque no se verifica a < a. se verifica que la clausura reflexiva de
la relación z es la relación ≤.
Ejemplo 4.3.3.-Dadas las relaciones del Ejemplo 4.2.3 que no son reflexivas computar su
clausura reflexiva.
Solución:
i) La relación no es reflexiva, para convertirla en reflexiva hay que unir a R el
siguiente conjunto {(2, 2), (3, 3), (4, 4), (5, 5)}
Cs = R ∪ S
139
Retículo y Algebra de Boole
La matriz del grafo asociado a Cs se obtiene tomando la matriz del grafo asociado a R,
digamos M, sumando esta matriz con su transpuesta M t, esto es N = M + M t y construyendo
una matriz que tengo un uno donde N tiene un elemento no nulo y cero donde N tiene un cero.
Ejemplo 4.3.4.- Sea el conjunto N10 y sobre él la relación de orden ≤. La clausura simétrica de
dicha relación es Cs = N10 x N10. En efecto, por definición Cs ⊂ N10 x N10. Para
demostrar el otro contenido, sea cualquier elemento (a, b) ∈ N10 x N10. Si a ≤ b
entonces (a, b) ∈ R ⊂ Cs, en caso contrario b < a y por tanto (b, a) ∈ R lo que
significa (a, b) ∈ S ⊂ Cs, lo que concluye la demostración.
Ejemplo 4.3.5.-Dadas las relaciones del Ejemplo 4.2.3 que no son simétricas computar su
clausura simétrica.
Solución:
i) La relación es simétrica.
iv) La relación no es simétrica, hay que unirle los siguientes elementos (c, a), (d, c)
y (a, d)
LEMA 4.1.- Sea A un conjunto, R una relación sobre A y G el grafo dirigido asociado a la
relación. Sean a y b dos elementos de A tales que existe un camino (a, v1), (v1,
v2),….. (vm, b) en G que une a con b. Entonces (a, b) pertenece a la clausura
transitiva, Ct, de R.
Según este lema, la clausura transitiva debe contener todos los pares (a, b) de vértices
tales que existe un camino que une a con b.
LEMA 4.2.- Sea A un conjunto y R una relación en A de modo que el grafo dirigido G
asociado a la relación verifica que si dos vértices a y están unidos por un
camino entonces (a, b) ∈ R. En estas condiciones la relación R es transitiva.
Demostración. Si tenemos que (a, b), (b, c) ∈ R entonces a y c están unidos por un camino de
longitud 2 y por tanto (a, c) ∈ R.
Los dos lemas previos muestran que la clausura transitiva de una relación R en un
conjunto A es entonces:
Ct = T,
donde T es el conjunto de pares (a, b) de modo que existe un camino en el grafo asociado G
que une a con b.
140
Retículo y Algebra de Boole
Ejemplo 4.3.6.- Dadas las relaciones del Ejemplo 4.2.3 que no son transitivas computar su
clausura transitiva.
Ejemplo 4.3.7.-Entendiendo una matriz como una lista de números con dos subíndices (el
primero la fila y el segundo la columna):
i) escribir un algoritmo que multiplica matrices de tamaño n x n;
ii) escribir un algoritmo que tome una matriz M de tamaño n x n y
construya una matriz N que tenga las entradas verificando nij = 1 si mij
≠ 0 y nij = 0 en caso contrario.
Solución:
141
Retículo y Algebra de Boole
Sea como siempre A un conjunto finito (|A| = n), R una relación en A, G = (A, R) el
grafo dirigido asociado a R y M una de sus matrices de adyacencias. Nuestro objetivo es
calcular la matriz asociada a Ct, que sabemos cómo es por el algoritmo anterior. Recordamos
que M se obtiene mediante una ordenación de los vértices de G, es decir A = {v1,…., vn}.
DEFINICIÓN 4.10.- Sea un camino (x0, x1), (x1, x2),…, (xn-1, xn) en un grafo dirigido G. A
los vértices x1,…, xn-1 se les llama vértices interiores del camino.
En el caso k = n tenemos que w ij( n ) = 1 si existe un camino que une vi con vj (porque el
conjunto de posibles vértices interiores es A). Por tanto se tiene que Wn es la matriz de
adyacencias buscada.
A = {a, b, c, d, e, f}
R={(a, a), (a, b), (c, c), (c, d), (c, f), (f, f), (f, c), (f, a)}
1 1 0 0 0 0
0 0 0 0 0 0
W = 0 0 1 1 0 1
0 0 0 0 0 0
0 0 0 0 0 0
1 1 0 0 1 1
142
Retículo y Algebra de Boole
Para analizar la complejidad de algoritmo debemos aportar algún método para construir
las matrices Wk. La siguiente observación obvia es la que permite construir Wk a partir de la
matriz anterior Wk-1.
OBSERVACIÓN 4.3.- Los caminos sin vértices interiores repetidos que unen los vértices vi y
vj cuyos vértices interiores pertenecen al conjunto {vi,…,vk} son de dos
tipos:
( ) (
w ijk = 1 ⇔ w ijk −1 = 1 ∨ w ik
k −1 k −1
= 1 = w kj )
Esto nos permite calcular la complejidad del algoritmo. Para construir Wk a partir de Wk-
1hay que construir sus n2 entradas. Para cada entrada, usando la observación anterior, hay
que hacer (como máximo) 3 comparaciones y una asignación. Por tanto cada construcción de
Wk es un algoritmo de complejidad cuadrática (4n2). Como hay que hacer n construcciones de
este tipo, el algoritmo de Warshall tiene complejidad cúbica, es decir, del orden O(n3).
Ejemplo 4.3.9.-Dadas las relaciones del Ejemplo 4.2.3 que no son transitivas computar su
clausura transitiva mediante el Algoritmo de Warshall.
0 0 0 0 0
0 0 0 0 1
W0 = 0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
La matriz W1 tiene un uno donde W0 tenga un uno y además se verifica que wij1= 1 si
wi10 = 1 = w1j0. Como en nuestro caso la primera fila de W0 es toda nula, entonces:
W0 = W1
La matriz W2 tiene un uno donde W1 tenga un uno y además se verifica que wij2= 1 si wi21 = 1 =
w2j1. Esta condición se verifica sólo en w521 = 1 = w251, por lo tanto se tiene w552 = 1.
0 0 0 0 0
0 0 0 0 1
W2 = 0 0 0 1 0
0 0 1 0 0
0 1 0 1 1
La matriz W3 tiene un uno donde W2 tenga un uno y además se verifica que wij3= 1 si wi32 = 1 =
w3j2. Esta condición se verifica sólo en w432 = 1 = w342, por lo tanto se tiene w443 = 1.
0 0 0 0 0
0 0 0 0 1
W3 = 0 0 0 1 0
0 0 1 1 0
0 1 0 1 1
143
Retículo y Algebra de Boole
La matriz W4 tiene un uno donde W3 tenga un uno y además se verifica que wij4= 1 si wi43 = 1 =
w4j3. Esta condición se verifica sólo en w343 = 1 = w433, por lo tanto se tiene w334 = 1.
0 0 0 0 0
0 0 0 0 1
W4 = 0 0 1 1 0
0 0 1 1 0
0 1 0 1 1
La matriz W5 tiene un uno donde W4 tenga un uno y además se verifica que wij5= 1 si wi54 = 1 =
w5j4. Esta condición se verifica sólo en w254 = 1 = w524, por lo tanto se tiene w225 = 1.
0 0 0 0 0
0 1 0 0 1
W5 = 0 0 1 1 0
0 0 1 1 0
0 1 0 1 1
En las condiciones del párrafo anterior partimos de G. Como sabemos que la relación ≤
es reflexiva podemos borrar todos los lazos, ya que necesariamente a ≤ a para cada a ∈ A.
144
Retículo y Algebra de Boole
Como sabemos que la relación ≤ es transitiva podemos borrar las aristas que son
consecuencia de esta propiedad. Por ejemplo, si a ≤ b y b ≤ c necesariamente a ≤ c, entonces
los pares (a, b), (b, c) y (a, c) son aristas del grafo y podemos borrar la arista (a, c).
Finalmente, en lugar de dirigir las aristas del grafo, elegimos una disposición vertical de
manera que si un elemento a está debajo de otro b y ambos están unidos por un camino
ascendente en el grafo simple final entonces a ≤ b.
Ejemplo 4.4.1:
Ejemplo 4.4.2: Dado el conjunto A = {a, b, c, d, e} y la relación R = {(a, a), (a, c), (c, e), (c, d),
(b, d)}
Solución:
De este modo:
Cr = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (c, e), (c, d), (b, d)}
Para completar la clausura transitiva observamos que (a, c), (c, e) ∈ Cr, por lo
tanto debemos unir (a, e). De igual modo (a, c), (c, d) ∈ Cr,, por lo tanto
debemos unir (a, d).
Es una comprobación demostrar la siguiente igualdad, siendo Ct la clausura
transitiva de Cr.
Ct = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (c, e), (a, e), (c, d), (a, d), (b, d)}
145
Retículo y Algebra de Boole
En los diagramas de Hasse los elementos maximales son aquellos que son extremo
superior de un camino ascendente que no se puede prolongar; recíprocamente los elementos
minimales son extremos inferiores de caminos descendentes que no se pueden prolongar.
{a, b}
{a} {b}
{}
Ejemplo 4.4.4: Un conjunto parcialmente ordenado ({1, 2, 3, 4, 5}, ≤) cuyo diagrama de Hasse
es el de la Figura 4.4.3 tiene dos elementos maximales, 3 y 5, y dos minimales,
1 y 4.
3
1 4
146
Retículo y Algebra de Boole
Ejemplo 4.4.6: El Ejemplo 4.4.4 del párrafo anterior representado en la Figura 4.4.3 con dos
elementos maximales y dos minimales, no tiene máximo ni mínimo. Por
ejemplo, 1 no es un mínimo porque se verifica que 1 ≤ 4, hecho 1 y 4 no son
comparables.
Ejemplo 4.4.7: Sea el conjunto A = {a, b, c, d, e, f} y la relación de orden dada por la clausura
reflexiva y transitiva de:
R = {(f, a), (a, c), (c, e), (c, d), (f, b), (b, d)}.
Solución:
Para calcular la clausura reflexiva hay que unir todos los miembros de la
diagonal. Como (f, a), (a, c) ∈ R, entonces (f, c) ∈ Ct. Ahora (f, c), (c, e) ∈ Ct
implica (f, e) ∈ Ct. Como (a, c), (c, c) ∈ R, entonces (a, e) ∈ Ct. Como el par
ordenado (a, c), (c, d) ∈ R, entonces (a, d) ∈ Ct. Como (f, c), (c, d) ∈ R,
entonces (f, d) ∈ Ct. de este modo:
Ct. = {(a, a), (a, c), (a, d), (a, e), (b, b), (b, d), (c, c), (c, d), (c, e), (d, d), (e, e), (f, a), (f, b),
(f, c), (f, d), (f, e), (f, f)}
1 0 1 1 1 0
0 1 0 1 0 0
A = 0 0 1 1 1 0
0 0 0 1 0 0
0 0 0 0 1 0
1 1 1 1 1 1
Y se tiene que A2 no tiene entradas no nulas nuevas, luego es en efecto una relación transitiva.
147
Retículo y Algebra de Boole
1 0 2 3 3 0
0 1 0 2 0 0
A2 = 0 0 1 2 2 0
0 0 0 1 0 0
0 0 0 0 1 0
2 2 3 5 4 1
Viendo el diagrama de Hasse (Figura 4.4.4) se tiene que existen dos elementos maximales,
que son d y e y por lo tanto no hay máximo. Hay un elemento minimal f que es además el
mínimo. El elemento d es cota superior de B y es además la única, por lo tanto es el supremo.
La única cota inferior es f que por lo tanto es el ínfimo.
a
b
Supongamos que tenemos un conjunto de tareas que realizar de modo que hay una
serie de prioridades, estableciéndose una relación de orden parcial sobre el conjunto de tareas.
Por ejemplo un conjunto de asignaturas (que no pueden cursarse simultáneamente) que
aprobar para conseguir una licenciatura con una serie de asignaturas que han de cursarse
después de aprobarse unas asignaturas previas. Nos interesará establecer un orden total para
realizarse las tareas, por ejemplo, una manera de cursar las asignaturas sabiendo en que
orden han de realizarse. Veamos un ejemplo simple:
C = {MI, MII, F}
Las distintas maneras de cursar estas asignaturas corresponden a los distintos órdenes totales
de que se puede dotar a C respetando el orden parcial.
148
Retículo y Algebra de Boole
Esto es, de las posibles 6 permutaciones del conjunto de las tres asignaturas, elegimos una de
las tres en que MI precede a MII.
Por tanto abordamos este problema general, que se puede aplicar a la planificación de
tareas:
Problema: Dado un conjunto parcialmente ordenado (A, R) encontrar una relación de orden
total T de modo que R ⊂ T.
LEMA 4.3.- Cada conjunto finito parcialmente ordenado (A, R) tiene un elemento minimal.
Este lema permite construir un algoritmo para la construcción del orden total T ⊇ R.
Partimos de A y elegimos un elemento minimal a1, que existe por el lema, aunque no
es necesariamente único (elección de una tarea para realizarla la primera de entre las tares
prioritarias). Ahora el conjunto A – {a1} es un conjunto parcialmente ordenado con el orden que
índice T sobre él. Repetimos el proceso para elegir un elemento minimal a2 (que por el lema
anterior necesariamente existe) y así sucesivamente hasta agotar los elementos de A.
El orden total T es
a1 ≤ a2 ≤ a3 ≤ … ≤ an
R = {(1,1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 3), (2, 3), (1, 4), (1, 5), (4, 5)}.
R1 = {(2, 2), (3, 3), (4, 4), (5, 5), (2, 3), (4, 5)}.
Elegimos un elemento minimal entre los dos posibles candidatos que son el 2 o el 4. Tomemos
x2 = 2. En el conjunto A – {1,2} tenemos un orden inducido:
1 ≤ 2 ≤ 3 ≤ 4 ≤ 5.
Obsérvese que podríamos haber elegido de otra manera la xi, para obtener un orden total
distinto, también compatible con el orden parcial con el que comenzamos.
149
Retículo y Algebra de Boole
Ejemplo 4.4.10: Se tiene que montar una cadena de montaje de una pieza según el siguiente
esquema de tareas.
Tareas: ensamblar, atornillar, pintar, empaquetar, limpiar, registrar.
Prioridades: Ensamblar antes de atornillar, atornillar antes de pintar, pintar
antes de empaquetar, limpiar antes de pintar.
Diseñar una posible planificación de tareas.
4.5. RETÍCULO
Ejemplo 4.5.1: Sea S un conjunto y sea L = P(S). Hemos visto que⊆, la contención, es una
relación de orden parcial en L. Si A y B son dos elementos de L (subconjuntos
de S), entonces la junta de A y B es su unión A ∪ B, y la reunión de A y B es
su intersección, A ∩ B. De aquí que L sea un retículo.
Ejemplo 4.5.2: Examinemos el conjunto parcialmente ordenado (Z+, ≤), donde a y b en Z+, y
que a ≤ b si y sólo si a | b. Entonces L es un retículo en cuya junta está su
mínimo común múltiplo (MCM) y en cuya reunión está su máximo común
divisor (MCD). O sea que:
Ejemplo 4.5.3: Sea n un entero positivo y Dn el conjunto de todos los divisores de n. Entonces
Dn es un retículo bajo la relación de divisibilidad como en el Ejemplo 4.5.2. Por
consiguiente, si n = 20, se tiene que D20 = {1, 2, 4, 5, 10, 20}. El diagrama de
Hasse se muestra en la Figura 4.5.1 (a). Si n = 30, se tiene D30 = {1, 2, 3, 5, 6,
10, 15, 30}. El diagrama de Hasse de D30 se muestra en la Figura 4.5.1 (b).
20 30
4 10 6 10 15
2 5 2 3 5
1 1
D20 D30
(a) (b)
Figura 4.5.1
150
Retículo y Algebra de Boole
TEOREMA 4.2.- Si (L1,≤) y (L2,≤) son retículos, entonces (L,≤) es un retículo donde se
cumple L = L1 x L2 y el orden parcial ≤ de L es una relación de orden
parcial producto.
Ejemplo 4.5.4: Sean L1 y L2 los retículos mostrados en la Figura 4.5.2 (a) y (b)
respectivamente. Entonces L = L1 x L2 es el retículo que se muestra en la
Figura 4.5.2 (c).
(I1, I2)
I2
I1
(I1, a) (01, I2) (I1, b)
a b
(I1, 02)
(01, a)
(01, b)
01 02
(01, 02)
L1 L2 L = L1 x L2
(a) (b) (c)
Figura 4.5.2
Ejemplo 4.5.5: El retículo Dn de todos los divisores positivos de n (véase Ejemplo 4.5.3) es un
subretículo Z+ bajo la relación de divisibilidad (véase el Ejemplo 4.5.2).
Sea (L,≤) un subretículo con junta ∨ y reunión ∧ y sea (L’,≤’) un retículo con junta ∨ ‘y
reunión ∧’. A una función f: L → L’ que sea inyectiva y sobreyectiva se denomina isomorfismo
de (L,≤) en (L’,≤’) si para cualquier a y b en L se tiene:
151
Retículo y Algebra de Boole
Esto significa que dos retículos son isomorfos si y sólo si los diagramas de Hasse de los dos
retículos son idénticos o los vértices del diagrama de Hasse de L pueden reetiquetarse de tal
manera que den por resultado un diagrama idéntico al diagrama de Hasse de L’.
(a). a ∨ b = b si y solo si a ≤ b.
(b). a ∧ b = a si y sólo si a ≤ b.
(c). a ∧ b = a si y sólo si a ∨ b = b
1. (a) a∨a=a
(b) a∧a=a Propiedad de Idempotencia
2. (a) a∨b=b∨a
(b) a∧b=b∧a Propiedad Conmutativa
3. (a) a ∨ (b ∨ c) = (a ∨ b) ∨ c
(b) a ∧ (b ∧ c) = (a ∧ b) ∧ c Propiedad Asociativa
4. (a) a ∨ (a ∧ b) = a
(b) a ∧ (a ∨ b) = a Propiedad de Absorción
152
Retículo y Algebra de Boole
Ejemplo 4.5.7: Un Retículo Z+ bajo la relación de orden parcial de divisibilidad, como se define
en el Ejemplo 4.5.2, no es un retículo acotado ya que tiene un elemento
mínimo, el número 1, pero no tiene un elemento máximo.
Ejemplo 4.5.9: Un Retículo P(S) de todos los subconjuntos de un conjunto S, como se define
en el Ejemplo 4.5.1, es un retículo acotado. Su elemento máximo es S y su
elemento mínimo es el conjunto vacío ∅.
0≤a≤1
a∨0=a a∧0=0
a∨I=I a∧I=a
TEOREMA 4.6.- Sea L = {a1. a2, …., an} un retículo finito. Entonces L es un retículo
acotado.
(a). a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
(b). a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
a ∨ a’ = I y a ∧ a’ = 0
0’ = I y I’ = 0
153
Retículo y Algebra de Boole
4.6.1.- CONCEPTO
B.- Axiomas
B1: La junta (∨) y la reunión (∧) son ambas leyes de composición interna dentro del
conjunto B.
∀ a, b ∈ B → a ∨ b ∈ B ∀ a, b ∈ B → a ∧ b ∈B
B2: La junta (∨) y la reunión (∧) son ambas leyes conmutativas dentro del conjunto
B.
∀ a, b ∈ B : a ∨ b = b ∨ a ∀ a, b ∈ B : a ∧ b = b ∧ a
B3: La junta (∨) y la reunión (∧) son ambas leyes asociativas dentro del conjunto B.
∀ a, b, c ∈ B: a ∨ (b ∨ c) = (a ∨ b) ∨ c; a ∧ (b ∧ c) = (a ∧ b) ∧ c
B4: La junta (∨) y la reunión (∧) son ambas leyes distributivas, cada una de ellas
con respecto de la otra, dentro del conjunto B.
∀ a, b, c ∈ B: a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
∀ a, b ∈ B: a∨0=a ; a∧1=a
∀ a, b ∈ B: a ∨ a' = 1 ; a ∧ a' = 0
Ejemplo 4.6.1: El siguiente ejemplo es un modelo del Álgebra de Boole muy particular.
Consideremos el siguiente conjunto:
154
Retículo y Algebra de Boole
Este principio establece que el dual de un Axioma o Teorema del Álgebra de Boole, es
también un Axioma o Teorema del mismo sistema axiomático
(1) Idempotencia
(1)' ∀a∈B⇒a∨a=a
a∨1=1
(2)' a∧0=0
∀ a ∈ B ⇒ (a')' = a
Aplicando sucesivamente B5, B6, B2, B4, B2, B6, B6, B4, B6 y B5 resulta:
155
Retículo y Algebra de Boole
Consideremos:
O sea:
Análogamente, se llega a:
Ejemplo 4.6.2:
Sea (B, ∨, ∧) un álgebra booleana, tal que B = {0, 1}. Podemos representar las dos
operaciones definidas a través del Álgebra de Boole por medio de tablas denominadas tablas
de verdad, de una manera análoga a la lógica proposicional.
∨ 0 1 ∧ 0 1
0 0 1 0 0 0
1 1 1 1 0 1
Ejemplo 4.6.3:
156
Retículo y Algebra de Boole
entonces:
Podemos representar las dos operaciones definidas a través del Álgebra de Boole por
medio de tablas denominadas tablas de verdad, de una manera análoga a la lógica
proposicional.
a b NOR (a ∨ b)’
0 0 1
0 1 0
1 0 0
1 1 0
a NOT (a)’
0 1
1 0
157
Retículo y Algebra de Boole
Sea B = {0, 1} y sea Bn álgebras de Boole tal cual se las definió anteriormente.
Podemos entonces discutir las funciones f de Bn en B. Para estas funciones f y para cualquier
n-tupla (x1, x2,....., xn) Bn, f(x1, x2,....., xn) es 0 o 1. Estas funciones pueden verse como
funciones de "n variables", donde cada una de ellas sólo toma los valores 0 y 1. Es frecuente
expresarlas a través de tablas dando cada n-tupla posible (x1, x2,....., xn) y el valor
correspondiente de la función f. La figura 4.6.1(a) nos muestra una función f particular de tres
variables; o sea, f: B3 → B. Cualquier distribución posible de 2m ceros y unos puede ser el
conjunto de los valores de alguna función de la siguiente forma f: Bm → B.
La importancia de tales funciones es que, tal como lo muestra la Figura 4.6.1 (b)
esquemáticamente, pueden usarse para representar los requerimientos de salida de un circuito
para todos los posibles valores de las entradas. Y así cada xi representa una entrada al circuito
capaz de transportar dos voltajes indicadores (un voltaje para cero y otro diferente para el uno).
La función f representa la respuesta de salida deseada en todos los casos. Tales
requerimientos se presentan al diseñar los pasos de todas las combinaciones y secuencias de
los circuitos para computadora. Como antes, las tablas de la figura 4.6.1(a) son denominadas a
menudo como tablas de verdad de f, debido a la analogía con la lógica proposicional.
3.- Si E1(x1, x2,....., xn) y E2(x1, x2,....., xn) son expresiones booleanas en x1, x2,.....,
xn, entonces también lo son las siguientes expresiones:
4.- No existirán otras expresiones booleanas; sólo las que se obtengan al utilizar
las reglas mencionadas en los puntos 1, 2 y 3.
E1(x, y, z) = (x ∨ y) ∧ z
E2(x, y, z) = (x ∨ y') ∨ (y ∧ I)
158
Retículo y Algebra de Boole
Los polinomios comunes en varias variables, tales como x2y + z4, xy + yz + x2y2, x3y3 +
4
xz , etc., suelen interpretarse como expresiones que representan cálculos algebraicos con
números no especificados. Por tanto, están sujetos a las reglas comunes de la aritmética.
x1 x2 x3 f(x1,x2,x3)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
(a)
y
F(x1,…,xn)
x2 f
xn
(b)
159
Retículo y Algebra de Boole
Ejemplo 4.7.2: Demostrar que las siguientes expresiones booleanas son equivalentes:
E2(x, y, z) = x ∧ z'
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
160
Retículo y Algebra de Boole
si la función está dada por alguna expresión booleana, es posible construir un diagrama lógico
con ella y así modelar la implementación de la función. En esta sección se mostrará que todas
las funciones de Bn en B están dadas por expresiones booleanas y, por lo tanto, los diagramas
lógicos pueden construirse para cualquiera de esas funciones. Este análisis ilustra el método
de encontrar una expresión booleana que produce una función dada.
Demostración:
Ejemplo 4.8.1: Sea f1: B2 → B producida por la expresión E(x, y) = x', y sea f2: B2 → B
producida por la expresión E(x, y) = y'. Entonces las tablas de verdad de f1 y f2
se indican en la Figura 4.8.1 (a) y (b), respectivamente.
0 0 1 0 0 1 0 0 1
0 1 1 0 1 0 0 1 1
1 0 0 1 0 1 1 0 1
1 1 0 1 1 0 1 1 0
Sea f: B2 → B la función cuya tabla de verdad se indica en la Figura 4.8.1(c). Esta claro
que S(f) = S(f1) ∪ S(f2), ya que f1 es 1 en los elementos (0,0) y (0,1) de B2, f2 es 1 en
los elementos (0,0) y (1,0) de B2, y f es 1 en los elementos (0,0), (0,1) y (1,0) de B2. Por
el Teorema 4.6.1, f = f1 ∨ f2, por lo cual la expresión de Boole que produce f es x' ∨ y'.
161
Retículo y Algebra de Boole
Ejemplo 4.8.2: Sea f: B2 → B la función cuya tabla de verdad se indica en la Figura 4.8.2(a).
Esta función es igual a 1 sólo en el elemento (0,1) de B2, o sea, S(f) = {(0,1)}
producida por la expresión. Por lo tanto, f(x, y) = 1 sólo cuando x = 0 y y = 1.
Esto también es verdadero para la expresión E(x, y) = x' ∧ y, por la cual f
produce esta expresión. La siguiente tabla de verdad muestra la
correspondencia entre las funciones que son 1 sólo en un elemento y las
expresiones booleanas que producen estas funciones.
{(0,1)} x' ∧ y 0 1 1 0 0 1 0
{(1,0)} x ∧ y' 1 0 0 0 1 0 0
{(1,1)} x ∧y 1 1 0 0 1 1 1
1 0 0 0
(a) 1 0 1 0
1 1 0 0
1 1 1 0
(b)
TEOREMA 4.10.- Cualquier función f: Bn → B está producida por una expresión booleana.
Demostración:
Sea S(f) = {b1, b2, ....., bk}, y para cada i, sea fi: Bn → B la función definida por:
fi(bi) = 1 ; fi(b) = 0 si b ≠ bi
Entonces S(fi) = {bi}, por lo cual S(f) = S(f1) ∪ S(f2) ∪ ... ∪ S(fn) y según el Teorema 4.3,
f = f1 ∨ f2 ∨ ..... ∨ fn
162
Retículo y Algebra de Boole
f ( x1, x2, . . . , xn ) = M 1 ∧ M 2 ∧ . . . ∧ M k
M j = y 1 ∨ y 2 ∨ . . . .∨ y n
Ejemplo 4.8.3: Examinar la función f1: B3 → B cuya tabla de verdad se indica en la Figura
4.8.3. Ya que S(f) = {(0,1,1), (1,1,1)}, el teorema 4.3 demuestra que f está
producida por la siguiente expresión
(x' ∧ y ∧ z) ∨ (x ∧ y ∧ z) = (x' ∨ x) ∧ (y ∧ z) = I ∧ (y ∧ z) = y ∧ z
x y z f(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
163
Retículo y Algebra de Boole
A. RELACIONES Y RETÍCULO
R = {(x, y) ⏐ 2x + y = 16}
Se pide: (a) Definir por extensión R; (b) Dominio y rango de R, (c) Relación R -1, por
extensión.
3.- Sea A = {1, 2, 3, 4} y a R b la relación que significa ’’a es divisor de b’’. Definir por
extensión el dominio y la imagen de la relación dada, de la relación inversa y de la
complementaria. Construir los digrafos y las matrices de incidencia de las tres relaciones
indicadas.
4.- Dados los conjuntos A = {1, 2, 3}, B = {a, b, c} y C = {x, y, z} y las siguientes relaciones:
R = {(1, b), (2, a), (2, c)} y F = {(a, y), (b, x), (c, y), (c, z)}
7.- Sobre el conjunto de los números reales se da la siguiente relación (x, y) R (r, s), cuyo
significado es:
x+s =y+r
8.- Representar mediante dígrafos y sus matrices las relaciones del ejercicio Nro. 6
definidas sobre conjuntos finitos.
164
Retículo y Algebra de Boole
9.- En las relaciones del ejercicio 6 definidas sobre conjuntos finitos que no sean reflexivas
(respectivamente simétricas, respectivamente transitivas) calcular su clausura reflexiva
(respectivamente simétrica, respectivamente transitiva).
(a) R = {(a, a), (a, c), (b, b), (c, c), (c, d), (d, d)} sobre A = {a, b, c, d}
(b) R = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c), (d, d)} sobre A = {a, b, c, d}
(c) R = {(a, a), (a, b), (a, d), (b, b), (b, a), (c, c), (c, b), (d, d), (d, c)} sobre
A = {a, b, c, d}
Construir los digrafos correspondientes y sus matrices de incidencia.
18.- ¿Cuales de los siguientes pares de elementos son comparables en el conjunto de los
números enteros con la relación de orden de divisibilidad?
19.- Describir todos los pares ordenados en cada uno de los órdenes parciales
representados por los diagramas de Hasse de la Figura 4.9.1.
21.- Hallar las cotas superiores, cotas inferiores, supremo e ínfimo del conjunto B (si existen)
en cada uno de los casos de la Figura 4.9.2 y de cada uno de los diagramas de Hasse
de la Figura 4.9.3.
165
Retículo y Algebra de Boole
Figura 4.9.1
22.- Representar el diagrama de Hasse de los siguientes conjuntos ordenados y hallar los
elementos notables de los subconjuntos señalados:
(a) (D 60, ⏐), A = {2, 5, 6, 10, 12, 30} y B = {2, 3, 6, 10, 15, 30}
(b) (D 48, ⏐), A = {2, 4, 6, 12} y B = {3, 6, 8, 16}
Figura 4.9.2
Figura 4.9.3
23.- Se considera en el conjunto A = {2, 3, 4, 6, 12, 15, 24, 90, 180, 360} la relación de
orden de divisibilidad. Se pide lo siguiente:
(a) Obtener, si existen, las cotas inferiores, cotas superiores, ínfimo, supremo,
mínimo, máximo, elementos minimales y maximales del conjunto B = {2, 3, 4, 6,
12, 180};
(b) Representar el diagrama de Hasse del conjunto ordenado (A, ⏐). ¿Es (A, ⏐) un
Retículo?
166
Retículo y Algebra de Boole
26.- Obtener los diagramas de Hasse de todos los retículos, salvo isomorfismos, de uno,
dos, tres, cuatro y cinco elementos.
1.- Verifique los axiomas que definen al Álgebra de Boole en el conjunto de los enteros
divisores de 6 adonde están definidas las operaciones “máximo común divisor” (M) y
“mínimo común múltiplo” (m).
2.- Los axiomas del Álgebra de Boole también se cumplen cuando los elementos en
cuestión son conjuntos y las operaciones son las conocidas “unión” e “intersección”
entre conjuntos. Suponiendo que A, B y C son subconjuntos de un universo U y siendo
el conjunto vacío, diga Verdadero o Falso, justificando su respuesta:
a) A ∪ (B ∩ C) = (A ∪ B) ∩ C
b) A∪(B∩C)=(A∪B)∩(A∪C)
c) Si U = {a, b, c, d} y A = { a, b, c }, entonces Ā = { a, d }
d) (A ∪ ∅) ∩ Ā = ∅
e) B ∪ ( B’ ∩ U) = ( A ∪ A’)
3.- Un contacto, tal como una llave común de luz eléctrica, presenta dos estados “cerrado”
o “abierto”. Los mismos suelen identificarse con los símbolos 1 y 0, respectivamente,
pero con un significado cualitativo “si-no” o “V-F”, éste último por su relación con la
lógica clásica. En el conjunto de contactos, se definen las operaciones “combinar
contactos en paralelos” o “combinar contactos en serie”. Verifique que dicho conjunto
es un Álgebra de Boole.
4.- Demostrar directamente que no existen álgebras booleanas que tengan tres elementos.
167
Retículo y Algebra de Boole
7.- Sea el conjunto B = {0, 1} con∨, ∧ definidas mediante las siguientes tablas:
∨ 0 1 ∧ 0 1
0 0 1 0 0 0
1 1 1 1 0 1
8.- Demostrar los teoremas más importantes que se deducen de los axiomas que definen
al Álgebra de Boole.
9.- Escriba los duales de los siguientes enunciados y demuestre alguno de ellos usando
los axiomas y/o propiedades que se cumplen en toda Álgebra Booleana.
(a) (x ∨ y) ∧ (x ∨ 1) = (x ∨ x) ∧ (y ∨ y)
(b) (x ∨ 0) ∨ ( 1 ∧ x’) = 1
(c) x ∨ (x’ ∧ y) = x ∨ y
(d) Si x ∨ y = x ∨ z y x’ ∨ y = x’ ∨ z ., entonces y = z
(e) x ∧ y’= 0 si y solo si x ∧ y = x
10.- Demuestre las siguientes igualdades usando los axiomas y/o propiedades de un
Álgebra Booleana:
11.- Represente las siguientes funciones booleanas por medio de un circuito combinatorio y
por medio de su tabla de verdad (o tabla lógica). ¿Cuántos circuitos y cuantas tablas
poseen una función booleana?
(a) z = f(a, b, c) = a ∨ ( b’ ∧ c )
(b) z = f(a, b, c) = ( a ∧ b’) ∨ ( a ∧ c’)
168
Retículo y Algebra de Boole
c) Z = F(A , B, C) = A + B + A.C
d) Z = F(A, B, C) = A . ( B + C) .( A + B)
13.- Encuentre las formas normales de las siguientes funciones dadas por su tabla:
a) b) c) d)
e) f)
x y z f(x, y, z) x y z f(x, y, z)
0 0 0 1 0 0 0 0
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 1
0 1 1 1 0 1 1 0
1 0 0 0 1 0 0 0
1 0 1 1 1 0 1 0
1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 0
I. F ( A, B , C ) = A.B + C
II. F ( A, B , C ) = ( A + B ).(C + A)
IV. F ( A, B , C , D ) = ( A + C ).B + D
F ( A, B, C ) = A + ( B + ( AB + AC ))
V.
F ( A, B ) = B + B. A
I.
169
Retículo y Algebra de Boole
II.
( )( )
F ( A, B , C ) = B. B + C . A + C
III. F ( A, B , C , D ) = (A + B + C ).(D + A + B )
E(x, y, z) = x ∧ (y ∨ z')
E(x, y, z) = (x ∨ y) ∧ (z ∨ x')
===============================
170
Teoría de Grafos
CAPITULO V
TEORIA DE GRAFOS
5.1.- INTRODUCCIÓN (¿QUE ES UN GRAFO?)
Los grafos, los objetos que estudiaremos en este y en el siguiente capítulo, resultan ser
un modelo matemático extremadamente útil para analizar problemas muy diversos como, por
ejemplo, los siguientes:
Los grafos son, como veremos, un lenguaje, una notación, que permite representar
relaciones binarias discretas — es decir, entre pares de objetos— en un conjunto. De una
manera informal, podríamos decir que un grafo es una colección de vértices y de aristas que
unen estos vértices.
Los vértices los dibujaremos como puntos del plano o pequeños círculos, y las aristas
serán líneas que unen estos puntos. Veamos ahora las definiciones formales:
171
Teoría de Grafos
Para ser precisos, deberíamos decir que esta definición se refiere a lo que se conoce
como un grafo simple y sin lazos. En la subsección 5.1.1 presentaremos varias
generalizaciones de este concepto, que resultarán muy útiles para otras cuestiones. Mientras
no se diga lo contrario, cuando hablemos de un grafo siempre estaremos refiriéndonos a este
caso sencillo.
Por supuesto, diremos que dos grafos son iguales si tienen el mismo conjunto de
vértices y la misma colección de aristas. Nombraremos un grafo G mediante G = (V, A). A
veces, cuando manejemos varios grafos a la vez, utilizaremos símbolos como V (G) y A(G)
para recordar a qué grafo corresponden los conjuntos de vértices y aristas a las que nos
estamos refiriendo.
2. Para el problema de la construcción de la red, las ciudades serían los vértices y las
conexiones, las aristas. Y, por supuesto, lo que buscaremos serla unir todos los
vértices con el menor número posible de aristas y de manera que la red resultante sea
lo mas barata posible.
Los subconjuntos de dos elementos de V son {1, 2}, {1, 3} y {2, 3}. Dos elecciones
distintas de conjunto de aristas son A1 = {{1, 2}, {2, 3}} y A2 = {{1, 2}}, que dan lugar a los
grafos G1 y G2 que dibujamos a continuación:
2
G1 2 G2
1 3
1 3
Figura 5.1.2: Grafos del problema 5.1.2
En muchas ocasiones, conviene considerar grafos que están incluidos “dentro” de otros.
Dado un grafo G = (V, A), formamos un subgrafo H = (V’, A’) de G seleccionando algunos de
los vértices de G (esto es, V’ ⊆ V ). Y, de las aristas que unieran vértices del conjunto V’ en el
grafo original G, nos quedamos con algunas de ellas (o todas)
Hay que ser cuidadosos con esto: si nos limitáramos a pedir que H contuviera a
algunos de los vértices y algunas de las aristas de G, podríamos llegar a situaciones sin sentido
como incluir una arista pero no alguno de sus vértices (no sería un grafo verdadero)
172
Teoría de Grafos
Una red informática puede contener una línea telefónica que conecte a una
computadora consigo misma (a efectos de diagnóstico) como se ilustra en la Figura 5.1.3. El
grafo G1 es un multigrafo (aristas múltiples entre {d, c}) No podemos utilizar multigrados para
representar estas redes, ya que no admiten bucles o lazos (aristas que conectan un vértice
consigo mismo) en un multigrafo. En lugar de multigrafo, utilizaremos pseudografos, que son
más generales que los multigrados, ya que un pseudografo admite bucles (En G2 bucles o
Lazos en los vértices a y d, aristas múltiples entre {d, c}).
G1 b G2 b
a a
e e
f f
c
c
d d
En el problema de la red informática telefónica puede ser que entre dos puntos la
misma no opere en las dos direcciones. Por ejemplo, la computadora en Bs. As. Puede enviar
datos a la computadora en la ciudad de Córdoba, pero no recibir datos de Córdoba. Otros tipos
de redes telefónicas si funcionan en ambas direcciones. Se utiliza grafos dirigidos para modelar
redes de este tipo. Las aristas de un grafo dirigido son pares ordenados, se admiten bucles,
pares ordenados con los dos elementos iguales, pero no se admiten aristas múltiples en la
misma dirección entre dos vértices.
Debemos observar que las aristas dirigidas múltiples están asociadas a un mismo par
de vértices. No obstante, diremos que (a, b) es una arista de G = (V, A) siempre que haya al
173
Teoría de Grafos
menos una arista e con f (e) = (a, b). No haremos distinción entre la arista e y el par ordenado
(a, b) a no ser que la identidad de alguna de las aristas múltiples en particular sea importante.
A B
A
C
F
E
D
La Tabla 1 resume la terminología que se emplea para los diferentes tipos de grafos.
Utilizaremos la palabra grafo para describir grafos con aristas no dirigidas o dirigidas, con o sin
bucles y aristas múltiples. Emplearemos los términos grafo no dirigido o pseudografo para
indicar grafos no dirigidos que pueden tener aristas múltiples y bucles. Usaremos siempre el
adjetivo dirigido para referirnos a grafos cuyas aristas estén asociadas a pares ordenados,
como por ejemplo grafos dirigidos o dígrafos.
5.2.- SUBGRAFOS
Hay ocasiones en que solo necesitamos una parte del grafo para resolver un problema.
Por ejemplo, solo estamos interesados en la parte de la red interconectada de energía eléctrica
que involucre las provincias de Buenos Aires, Córdoba, Santiago del Estero y Tucumán. En
este caso, podemos ignorar todas las redes que conectan al resto de las provincias. En el grafo
que represente la red total podemos eliminar los vértices que corresponden a las ciudades del
resto de las provincias no contempladas y suprimir todas las aristas que vienen y van a esos
vértices eliminados. Una vez eliminados estos vértices y aristas del grafo, sin eliminar ningún
extremo de las aristas que quedan, se obtiene un grafo más pequeño. Se dice que este grafo
es un subgrafo del grafo original.
DEFINICIÓN 5.7.- La unión de dos grafos simples G1 = (V1, A1) y G2 = (V2, A2) es un
grafo simple cuyo conjunto de vértices es V1 U V2 y cuyo conjunto de
aristas es A1 U A2. La unión de G1 y de G2se representa por G1 U G2
174
Teoría de Grafos
• Dados un par de grafos H y G, diremos que H es un subgrafo recubridor (el ejemplo más
relevante de un subgrafo recubridor lo encontraremos en el Capítulo 6, cuando
desarrollemos árbol recubridor) de G si H es un subgrafo de G y, además, V (H) = V (G). Es
decir, si H contiene a todos los vértices de G.
2
G
3
1
4
5
Figura 5.2.1: Grafo G del Problema 5.2.1
2 2
H1 H2
3 3
1 1
4 4
5 5
2 2
H3 3 H4 3
4 4
5
175
Teoría de Grafos
2 2
H5 H6
3 3
1 a
4 4
5 5
El grafo H5, porque incluye una arista, la {1, 5} que no estaba en G. Y el H6, porque su
conjunto de vértices no es un subconjunto del de G.
Todo lo que queda es escoger unas cuantas aristas de entre estos candidatos; así que
el número de grafos distintos con vértices {1, 2, . . . , n} es:
Por cierto, un número gigantesco, en cuanto n sea grande. Ya en el caso en que haya
siete vértices, tendremos
Hemos contado aquí el número de grafos distintos con n vértices. La elección de los
símbolos {1, . . . , n} para representar los vértices es cómoda, y la haremos habitualmente, pero
el cálculo sería válido para cualquier otra elección de n símbolos para los vértices. En lo que
sigue, los símbolo, u, v, w. . . representarían, generalmente, a vértices. Las aristas serían a o
quizás e (del inglés edge).
En la representación gráfica habitual, para saber de qué grafo se trata, tendremos que
etiquetar los vértices. Pero, para muchas cuestiones, las etiquetas que se utilicen son
irrelevantes.
176
Teoría de Grafos
Una forma muy útil de representar un grafo G = (V, A) es mediante su matriz de adyacencia (o
matriz de vecindades). La idea es formar una matriz de ceros y unos. Si el conjunto de vértices
es V = {v1, . . . , vn}, el grafo se puede describir mediante una matriz n × n:
v1 V2 V3 …. Vn
v1 0 1 0 … 1
V2 1 0 1 … 1
V3 0 1 0 … 0
: : : : : :
Vn 1 1 0 … 0
Esta identificación es muy importante. Para muchos de las cuestiones que trataremos
en lo sucesivo, bastaría considerar el dibujo asociado al grafo. Pero, como veremos, el de los
grafos es un lenguaje especialmente diseñado para un uso algorítmico, algoritmos que
requeriría la intervención de la computadora. Y para una computadora, por supuesto, un grafo
es una matriz de ceros y unos. Conviene tener esto en mente en los argumentos que
desarrollemos.
• Por ejemplo, si permitiéramos lazos, esto es, aristas cuyos dos vértices sean el mismo,
estaríamos considerando, simplemente, matrices (cuadradas) simétricas de ceros y unos
(con, posiblemente, unos en la diagonal).
• Pero también podríamos permitir que hubiera aristas múltiples (por ejemplo, dos vértices
conectados por dos o más aristas); en este caso hablaremos de multigrafos. En términos
matriciales, un multigrafo seria una matriz simétrica cuyas entradas son ceros o números
naturales: en la diagonal irían ceros si no permitiéramos lazos.
• Otra posibilidad, que estudiamos con detalle en la subsección 5.2, es la de dar orientación
a las aristas. En los grafos dirigidos o digrafos, las entradas de la matriz siguen siendo
ceros y unos, pero esta ya no necesariamente simétrica.
177
Teoría de Grafos
Pero insistimos en que en lo sucesivo, mientras no se diga lo contrario, todos los grafos
a los que nos referiremos serían simples y sin lazos. Un concepto fundamental en un grafo es
el de grado de un vértice:
DEFINICIÓN 5.8.- Dado un grafo G = (V, A), diremos que dos vértices v, w ∈ V son
adyacentes o vecinos si {v, w} ∈ A. Si e = {v, w}, se dice que la
arista e es incidente con los vértices v y w. También se dice que la
arista e conecta v con w. Se dice que los vértices v y w son extremos
de la arista e.
Por convenio, se suele escribir esta lista con los valores ordenados de menor a mayor.
Ejemplo 5.3.1: ¿Cuáles son los grados de los vértices de los grafos de la Figura 5.2.1?
∑ δ (v ) = 2 | A |
v ∈V
DEMOSTRACIÓN. El resultado es casi obvio, pues cada arista involucra a dos vértices. Una
prueba rigurosa requiere invocar a otra matriz asociada a un grafo, la MATRIZ DE INCIDENCIA:
178
Teoría de Grafos
v1 V2 V3 …. Vn
a1 1 1 0 … 0
a2 1 0 1 … 0
a3 0 1 0 … 0
: : : : : :
am 0 1 0 … 1
Las columnas están etiquetadas con los vértices {v1, . . . , vn}, y las filas, con las aristas
{a1, . . . , am}. En la posición (ai, vj) colocaremos un 1 si el vértice vj es extremo de la arista ai;
y un 0 en caso contrario. Apliquemos ahora un argumento de doble conteo. En la fila etiquetada
por la arista a1 aparecerían sólo dos unos (sus dos extremos); lo mismo ocurre con el resto de
las filas. Así que, sumando por filas, obtenemos 2m = 2|A|. Al hacerlo por columnas,
observamos que la columna correspondiente al vértice vj contendría tantos unos como vecinos
tenga este vértice: su suma valdría justamente gr(vj ) = δ(vj). Sumando los resultados de todas
las columnas, obtenemos lo que buscábamos.
Si los dos números coinciden, por ejemplo en el valor k, entonces todos los vértices del
grafo tendrían grado k, y hablaremos de un grafo k-regular.
TEOREMA 5.2: Todo grafo no dirigido G = (V, A) tiene un número par de vértices de
grado impar.
La terminología para grafos dirigidos refleja el hecho de que a las aristas se les asigna
un sentido.
Como las aristas de un grafo dirigido son pares ordenados, podemos refinar la
definición de grado de un vértice a fin de reflejar el número de aristas que tienen a ese vértice
como vértice inicial o como vértice final.
179
Teoría de Grafos
Ejemplo 5.3.2: ¿Cuáles son los grados de entrada y de salida los vértices de los
grafos de la Figura 5.1.4?
DEFINICIÓN 5.13.- Un grafo (o multigrafo) no dirigido donde los vértices tienen el mismo
grado se denomina grafo regular. Si δ-(v) = k para todos los vértices v
∈ V (G), entonces el grafo es k - regular.
Observemos los dos grafos que aparecen dibujados a la derecha. En ambos casos, el
conjunto de vértices es {1, 2, 3, 4}. Pero son grafos distintos: en un caso, el conjunto de aristas
es {{1, 2}, {2, 3}, {3, 4}, {4, 1}}, mientras que en el otro es {{1, 2}, {1, 3}, {2, 4}, {3, 4}}. Aún
siendo distintos, estos dos grafos contienen, en cierto sentido, la misma información (un simple
cambio de nombres transforma uno en el otro). En ambos casos, hablaríamos del “grafo del
cuadrado”. Esta idea es la que pretendemos desarrollar en esta subsección.
1 2 1
4
4 3 2 3
DEFINICIÓN 5.14.- Sean G y G’ dos grafos, con conjuntos de vértices y aristas (V, A) y (V’,
A’), respectivamente. Decimos que una aplicación biyectiva φ: V →V’
es un isomorfismo de grafos si:
En el caso de los dos grafos con los que abríamos esta subsección, el lector podría
comprobar que la aplicación φ: {1, 2, 3, 4} → {1, 2, 3, 4} dada por φ(1) = 1, φ(2) = 4, φ(3) = 2 y
φ(4) = 3 es un isomorfismo entre los dos grafos.
180
Teoría de Grafos
No es fácil, en general, decidir si dos grafos son isomorfos o no. En los casos sencillos,
si los dos grafos son isomorfos, se puede encontrar la biyección “a ojo”. ¡Sobre todo si el dibujo
nos ayuda! Los dos grafos que aparecen a la derecha también son isomorfos, pese a que la
manera de dibujarlos no parezca indicarlo. Una manera de comprobar si dos grafos son
isomorfos (que, por supuesto, habrían de tener el mismo número de vértices, digamos n), seria
comprobar si alguna de las n! aplicaciones biyectivas entre los conjuntos de vértices
respectivos cumple las propiedades necesarias para ser un isomorfismo entre los dos grafos.
Pero esto, desde luego, no es un procedimiento razonable si n es grande.
a b
1
d c 2 3
Sin embargo, para decidir que dos grafos no son isomorfos contamos con ciertas propiedades
de un grafo que se han de conservar por isomorfismos:
1. Ambos grafos han de tener el mismo número de vértices (si no lo tienen, no podremos
construir una aplicación biyectiva entre los conjuntos de vértices).
δ (v) = δ (φ(v)).
Si, por ejemplo, en un grafo tenemos un vértice de grado 7 y en el otro no, no podrían ser
isomorfos.
3. Con más generalidad, si dos grafos son isomorfos, entonces han de tener la misma
sucesión de grados. Sin embargo, el que dos grafos tengan la misma sucesión de grados
no garantiza que sean isomorfos, como muestra el ejemplo 5.4.1.
Ejemplo 5.4.1 Consideremos los dos grafos siguientes (nos olvidamos de las etiquetas de los
vértices):
4
a
e 1 6
b
d f 2 3 5
c
G1 G2
Figura 5.4.3: Grafos del Problema 5.4.1
181
Teoría de Grafos
Ambos grafos tienen seis vértices, cinco aristas y su sucesión de grados es (1, 1, 1, 2, 2, 3). Sin
embargo, no son isomorfos pues, por ejemplo, el vértice de grado 3 es, en un caso, vecino de
dos de grado 1 y de uno de grado 2; y en el otro, de uno de grado 1 y de dos de grado 2.
Hay otras propiedades que son conservadas bajo isomorfismos (todas las relacionadas
con vecindades); por ejemplo, el llamado cuello de un grafo, del que hablaremos más adelante.
Sin embargo, no existe una caracterización para el isomorfismo de dos grafos (una serie de
propiedades que determinen si dos grafos son o no isomorfos).
Ejemplo 5.4.2 Clasifiquemos por clases todos los grafos distintos que podemos formar con el
conjunto de tres vértices V = {1, 2, 3}, en la Figura 5.4.4.
Como hay tres posibles aristas, habría 23 = 8 grafos distintos. Vistos salvo isomorfismos,
¿cuántos hay? Sin aristas, hay sólo uno. Nótese que, para esta configuración sin aristas,
también hay un único grafo (al etiquetar los vértices). Con una arista, hay una única
configuración, a la que corresponden tres grafos distintos, pues basta decidir qué vértice va
solo (o qué dos comparten arista).
Con dos aristas hay, de nuevo, una única configuración (un único grafo salvo
isomorfismo), aquél en el que los tres vértices forman una “cadena”:
Como se señala en la figura, hay tres grafos distintos que pertenecen a esta clase,
pues basta determinar el símbolo que situamos en el vértice de grado 2; y esto lo podemos
hacer de tres formas distintas. El lector podría comprobar que los otros tres posibles
etiquetados no producen grafos nuevos. Por ultimo, con tres aristas hay uno, al que
corresponde un único grafo:
En total, los 8 grafos distintos se engloban en cuatro clases, un grafo sin aristas, tres
grafos distintos con una arista, otros tres con dos aristas, y uno con las tres aristas.
Pero, en general, esta clasificación seria más complicada (habría, por ejemplo, varios
grafos no isomorfos con el mismo número de aristas). Animamos al lector a que intente la
clasificación en los casos n = 4 y n = 5 (hay 11 y 35 grafos no isomorfos con ese número de
vértices, respectivamente). El estudio general requiere herramientas mas complicadas que
veremos en el capitulo 14.
GRAFO LINEAL: Diremos que un grafo es un Ln, un grafo lineal con n vértices (n ≥ 2) si tiene
n vértices (dos de grado 1 y el resto, si los hay, de grado 2) y es isomorfo a:
a b c d e f g
182
Teoría de Grafos
1 3
(a) 0 arista 2
1 3 1 2 2 1
2 3 3
(b) 1 arista
1 2 3
1 3 2
2 1 3
(c) 2 aristas
3
(d) 3 aristas
GRAFO CIRCULAR: Otra clase de grafos muy relevante son los llamados grafos circulares
con n vértices (todos de grado 2), para n ≥ 3, que denotaremos por Cn:
C3 C4 C5 C8
183
Teoría de Grafos
K3 K4 K5 K8
GRAFO VACIO: En los otros extremos encontramos los grafos vacíos Nn, con n vértices y
ninguna arista.
GRAFO BIPARTITO: Una clase de grafos que tienen relevancia en diversos problemas (por
ejemplo, en los problemas de asignación de tareas), son los llamados grafos bipartitos. Se
trata de aquéllos en los que podemos partir el conjunto de vértices en dos clases, de manera
que no haya aristas entre vértices de la misma clase. Un caso particular son los grafos
bipartitos completos, que nombraremos como Kr,s. En el dibujo de la derecha aparece un
K4,6. Un grafo Kr,s consta de r +s vértices, divididos en dos clases; e incluye las r × s aristas
que van de los vértices de un tipo a los del otro. Obsérvese que un grafo bipartito con r vértices
de un tipo y s de otro se puede obtener del Kr,s escogiendo un subconjunto de las aristas.
a 1
b 2
c 3
d 4
5
6
El grafo del cubo, Qn, tiene como vértices los puntos del retículo n-dimensional de
coordenadas 0 o 1. Esto es, el conjunto de los vértices de Qn son todas las listas de longitud n
que podemos formar con ceros y unos. En total, pues, tiene 2n vértices. Dos vértices de Qn
serían vecinos si las listas de ceros y unos que los identifican difieren en una única posición.
Por tanto, todos los vértices tienen el mismo grado, n (hay n distintas maneras de variar una
posición en una n-lista): Qn es un grafo n-regular. Una simple cuenta nos permite calcular el
número de aristas:
2n
2 A(Qn ) = ∑ δ (v ) = ∑ n = n 2 n
v ∈V (Qn ) j =1
⇒ A(Qn ) = n 2 n −1
184
Teoría de Grafos
(0,0,1) (0,1,1)
(1,0,1)
(1,1,1)
(0,1,0) y
(0,0,0)
(1,0,0) (1,1,0)
Obsérvese que Q1 es isomorfo a L2, y Q2, a C4. Los grafos Qn, pese a que los dibujos
esbozados no hagan sospecharlo, son bipartitos: observemos que la mitad de los vértices
están etiquetados con listas de n posiciones que contienen un número par de ceros, y la otra
mitad, un número impar. Y dos listas que tienen un número par de ceros no pueden ser vecinas
en este grafo (e igual para las impares).
G1 G2
¿En qué se diferencian? Parece claro que en el de la derecha las aristas del grafo nos permiten
“llegar” de un vértice a cualquier otro; algo que no podemos hacer en el de la izquierda. El
objetivo de esta subsección es el de entender el concepto de “conexión” en grafos.
DEFINICIÓN 5.16.- Sean x, y vértices (no necesariamente distintos) de un grafo G = (V, A).
Un camino x – y en G es una sucesión alternada finita (sin lazos):
185
Teoría de Grafos
Ejemplo 5.6.1.- Para el grafos de la Figura 5.6.2, tenemos por ejemplo, los siguientes
tres caminos abiertos. Podemos enumerar solamente las aristas o
solamente los vértices (si el otro queda determinado claramente).
1.- {a, b}, {b, d}, {d, c}, {c, e}, {e, d}, {d, b}: este es un camino a - b de
longitud 6, en el que se repiten los vértices d y b, como así también la arista
{b, d} = {d, b}.
3.- {f, c}, {c, e}, {e, d}, {d, a}: en este caso el camino f – a tiene longitud 4, sin
repetición de vértices o aristas.
a c
b
f
d
Ejemplo 5.6.2.- Para el grafos de la Figura 5.6.2, tenemos por ejemplo, las siguientes
tres situaciones. Podemos enumerar solamente las aristas o solamente
los vértices (si el otro queda determinado claramente).
2) En la Figura 5.6.2, las aristas {a, b}, {b, d}, {d, c}, {c, e}, {e, d} y {d, a} dan
lugar al circuito a – a. El vértice d se repite, por lo que las aristas no nos
dan un ciclo a –a.
3) Las aristas {a, b}, {b, c}, {c, d} y {d, a} proporcionan un ciclo a – a (de
longitud). Cuando estas mismas aristas se ordenan apropiadamente,
también pueden definir un ciclo b – b, c – c o d – d. Cada uno de estos
ciclos es también un circuito.
186
Teoría de Grafos
Los términos que utilizamos aquí, paseo, camino, etc., podrían no coincidir con los
usados en otros textos. Para un grafo dirigido utilizaremos el adjetivo dirigido, como se usa,
por ejemplo, en caminos dirigidos, caminos simples dirigidos y ciclos dirigidos.
Estos nuevos conceptos nos permiten añadir criterios nuevos para decidir si dos grafos
son o no isomorfos: dados dos grafos G y G´ isomorfos mediante φ, entonces si C = {v0, . . . , v r}
es un ciclo en G, entonces C_ = {φ(v0), . . . , φ(v r)} es un ciclo en G´. En particular se
conservaría la longitud del menor ciclo que haya en el grafo:
DEFINICIÓN 5.19.- Sea G = (V, A) un grafo no dirigido. Diremos que G es conexo si existe
un camino simple entre cualesquiera dos vértices distintos de G.
a b e g
f
c d
187
Teoría de Grafos
DEFINICIÓN 5.20.- Dado un grafo G = (V, A), una componente conexa de G sería el
grafo que se obtiene al tomar todos los vértices que están en la
componente conexa de un cierto vértice de V y todas las aristas del
grafo que conectan estos vértices.
.
Señalemos que las componentes conexas de un grafo son grafos conexos y es fácil ver que
todo grafo se puede representar como unión de grafos conexos (sus componentes conexas).
DEFINICIÓN 5.21.- Para cualquier grafo G = (V, A), el número de componentes conexas
de G se denota por Κ (G).
DEFINICIÓN 5.22.- Diremos que una arista a de un grafo G es un puente si el grafo G \ {a}
que se obtiene de G al quitar la arista a (y dejar los mismos vértices)
tiene más componentes conexas que G.
Por ejemplo, en el siguiente grafo conexo a es la única arista del grafo que es puente. En
particular, si el grafo G de partida es conexo, entonces se tiene el siguiente resultado:
V1 V6
V4 V5
V2 a
V3 V7
LEMA 5.1.- Si G es un grafo conexo y a es una arista puente de G, entonces G \ {a} tiene
exactamente dos componentes conexas.
Demostración. Llamemos v y w a los vértices que son extremos de la arista a. Y dividamos los
vértices de G en dos clases:
1. el conjunto de vértices V1, formado por aquéllos para los que existe un camino que los
conecta con v sin usar la arista a (esto es, sin pasar por el vértice u). Entre éstos está,
por supuesto, el propio vértice v.
2. El conjunto V2 de los vértices que necesariamente han de usar la arista a para
conectarse a v. Entre ellos está w (¿por qué?).
Que esto es una partición de los vértices de G es obvia. Pero, además, la intersección de V1 y
V2 es vacía: si un vértice x ∈ V(G) estuviera en V1 y en V2 a la vez, a no sería arista puente,
porque podríamos quitarla sin que se desconectara el grafo. Si ahora formamos el grafo G \ {a},
sus dos componentes conexas son, precisamente, los vértices de V1 (y sus aristas) y los
vértices de V2 (y sus aristas). _
Demostración. La razón es que la conexión óptima (con menor número de aristas) se produce
cuando tenemos exactamente una arista menos que vértices (veremos este hecho cuando
hablemos de árboles). Pero en general tendremos más aristas. La prueba la haremos utilizando
188
Teoría de Grafos
Si no tenemos aristas, para que el grafo sea conexo, sólo puede haber un vértice. Si lo
que tenemos es un grafo conexo con | A | = 1, la única posibilidad es que sea el grafo L2, que
tiene dos vértices. Supongamos cierto que si tenemos un grafo conexo con k aristas, para
cualquier k ≤ m, entonces | V | ≤ k + 1. Consideremos entonces un grafo conexo G con:
|A(G)| = m + 1.
Sea a una arista cualquiera de G y construyamos un nuevo grafo H quitando esta arista a. El
grafo H tiene los mismos vértices que G pero una arista menos (la a) que G. Caben dos
posibilidades para este nuevo grafo:
1. Si H sigue siendo conexo (es decir, si a no era arista puente en G), por hipótesis de
inducción (tiene m aristas), y teniendo en cuenta que |A(H)| = |A(G)| − 1 y que V (G) = V
(H), tendremos que
2. Pero si a era puente en G, H ya no es conexo, sino que tiene dos componentes conexas;
llamémoslas H1 y H2. Ambas son grafos conexos y tienen menos aristas que G (fijémonos
en que estos subgrafos pueden constar de un único vértice). Teniendo en cuenta que
|A(H1)| ≥ |V (H1)| − 1
|A(H2)| ≥ |V (H2)| − 1 ⇒ |A(G)| − 1 ≥ |V (G)| − 2 ⇒ |A(G)| ≥ |V (G)| − 1 .
_
Podemos generalizar este resultado al caso de que el grafo conste de más de una componente
conexa. La demostración del siguiente enunciado sólo exige aplicar el anterior a cada
componente conexa de G y sumar:
Aunque por ahora suene poco informativo, podemos interpretar el número aij como el
número de caminos de longitud 1 que hay entre el vértice vi y el vértice vj. Lo interesante es
que esta interpretación se puede generalizar.
189
Teoría de Grafos
n
a ij( k ) = ∑a
l =1
( k −1 )
il a ij
Observemos ahora que ail (k−1)alj es igual a ail (k−1) si es que vl es adyacente de vj, mientras que
vale 0 en caso contrario.
Por hipótesis, ail (k−1) cuenta el número de paseos de longitud k −1 entre vi y vl. Así que, en la
suma de arriba, estamos contando todos los posibles paseos de vi a vj de longitud k
clasificándolos en función del vértice que, en cada paseo, sea justo el anterior a vj .
1 2
5 4
0 1 0 1 1 3 1 2 1 0 2 6 2 6 3
1 0 1 1 0 1 3 1 2 1 6 4 5 5 1
M = 0 1 0 1 0 M2 = 2 1 2 1 0 M3 = 2 5 2 5 2
1 1 1 0 0 1 2 1 3 1 6 5 5 4 1
1 0 0 0 0 0 1 0 1 1 3 1 2 1 0
Obsérvese que en la diagonal de M2 aparecen los grados de cada vértice. Esto es general: la
entrada aij(2) coincide con el grado de vi, pues el número aii (2) cuenta los caminos de longitud 2
de vi a vi.
3
De la matriz M deducimos, por ejemplo, que hay seis paseos distintos de longitud tres
entre los vértices 1 y 2. El lector podrí encontrar los seis caminos 1−5−1−2 , 1−4−1−2 , 1−
2−1−1 , 1−2−3−2 , 1−2−4−2 , 1−4−3−2 sobre el grafo.
∼M = I +M +M2 + · · · +Mn−1
190
Teoría de Grafos
La ciudad prusiana de Königsberg estaba dividida en cuatro partes por los dos brazos
en los que se bifurca el río Pregel. Estas cuatro partes eran las dos regiones a orillas de río
Pregel, la isla de Kneiphof y la región que quedaba entre ambos brazos del río Pregel. Siete
puentes conectaban entre si estas regiones en el siglo XVIII. La Figura 5.8.1 ilustra las regiones
y los puentes.
Los habitantes de Königsberg solían dar largos paseos por la ciudad los domingos.
Hubo quien se preguntó si era posible comenzar el paseo en algún sitio de la ciudad, atravesar
todos los puentes sin cruzar ninguno dos veces y regresar al punto de partida.
B A C
191
Teoría de Grafos
El problema de recorrer todos los puentes sin cruzar ninguno de ellos más de una vez
puede replantearse en términos de este modelo. La pregunta se convierte entonces en la de si
hay o no algún circuito simple en el multigrafo que contenga todas las aristas del grafo.
DEFINICIÓN 5.23.- Sea G = (V, A), un grafo o multigrafo no dirigido sin vértices aislados.
Entonces G tiene un circuito euleriano si existe un circuito de G que
recorra cada arista del grafo exactamente una vez. Si existe un
recorrido abierto de x a y en G que recorra cada arista de G
exactamente una vez, este recorrido se denominara recorrido
euleriano. Un camino euleriano es un camino simple que contiene
todas las aristas de G.
Ejemplo 5.8.1.- ¿Cuales de los grafos de la Figura 5.8.3 contienen un circuito euleriano? Entre
aquellos que no lo contienen, ¿Cuáles contienen un camino euleriano?:
a b a b a b
e e
e
d c d c d c
G1 G2 G3
TEOREMA 5.5.- Sea G = (V, A) un grafo o multigrafo no dirigido, sin vértices aislados.
Entonces G tiene un circuito euleriano en G si y sólo si G es conexo y
todo vértice de G tiene grado par.
COROLARIO 5.1.- Sea G = (V, A) un grafo o multigrafo no dirigido, sin vértices aislados,
entonces podemos construir un recorrido euleriano si y sólo si G es
conexo y tiene exactamente dos vértice de G grado impar.
DEFINICIÓN 5.24.- Se dice que un camino x0, x1, x2, . . . ,xn-1, xn del grafo G = (V, A), es
un camino hamiltoniano si V = { x0, x1, x2, . . . ,xn-1, xn} y xi ≠ xj para
el siguiente rango 0 ≤ i < j ≤n. Se dice que un circuito x0, x1, x2, . . . ,xn-
1, xn, x0 (con n>1) del grafo G = (V, A) es un circuito hamiltoniano si
la secuencia x0, x1, x2, . . . ,xn-1, xn es un camino hamiltoniano.
Ejemplo 5.8.2.- ¿Cuales de los grafos de la Figura 5.8.4 contienen un circuito hamiltoniano o
sino un camino hamiltoniano?
192
Teoría de Grafos
a b a b a b g
e c d c d c e
G2 G3
G1 d f
TEOREMA 5.6.- TEOREMA DE DIRAC: Sea G = (V, A) un grafo simple con n vértices para n ≥
3, tal que todos los vértices de G tienen grado mayor o igual a n/2. Entonces
G contiene un circuito hamiltoniano.
TEOREMA 5.7.- TEOREMA DE ORE: Sea G = (V, A) un grafo simple con n vértices para n ≥ 3,
tal que δ(u) + δ(v) ≥n, para cada par de vértices no adyacentes u y v de G.
Entonces G tiene un circuito hamiltoniano..
a w x w x
e f
b c z y z y
(a) G1 (b) G2 (c) G2
193
Teoría de Grafos
Ejemplo 5.9.1.- Los grafos de la Figura 5.9.1 son planos. El primero G1 es un grafo 3-regular,
ya que cada vértice tiene grado 3; es plano pues ningún par de aristas se
intersecan, excepto en los vértices. El grafo (b) G2 parece un grafo no plano;
las aristas {x, z} y {w, y} se cruzan en un punto distinto a un vértice. Sin
embargo podemos trazar nuevamente este grafo, como se muestra en la parte
(c) de la figura. En consecuencia K4 es plano.
Ejemplo 5.9.2.- Al igual que K4, los grafos K1, K2, y K3 son planos.
DEFINICIÓN 5.26.- Sea G = (V, A), un grafo no dirigido sin lazos, tal que A ≠ ∅. Una
subdivisión elemental de G resulta cuando eliminamos una arista tal
como a = {v, w} de G y entonces las aristas {u,ν} y {ν, w} se añaden a
G – a, donde ν ∉ V.
DEFINICIÓN 5.27.- Los grafos no dirigidos sin lazos G1 = (V1, A1) y G2 = (V2. A2) son
homeomorfos si son isomorfos o si ambos pueden obtenerse del
mismo grafo no dirigido sin lazos H por una sucesión de subdivisiones
elementales.
Ejemplo 5.9.3.- Al igual que los ejemplos anteriores tenemos los siguientes grafos:
G G1 G2 G3
a b a w b a b a w b
c c c c
y x y x
z
e d e d e d e d
(a) (b) (c) (d)
194
Teoría de Grafos
Podría pensarse que los grafos homeomorfos son isomorfos excepto, posiblemente,
por los vértices de grado 2. En particular, si dos grafos son homeomorfos, son simultáneamente
planos (o no planos). Estos antecedentes llevan al siguiente resultado.
(a) G1 (b) G2 b
a b a
R1
R2
d
R3 c d c
R4
TEOREMA 5.9.- Sea G = (V, A) un grafo o multigrafo plano conexo con ⎜V⎟ = ν y ⎜A⎟ = a.
Sea r el número de regiones en el plano determinadas por una
inmersión (o representación) plana de G, una de estas regiones tiene
un área infinita y se conoce como región infinita. Entonces: ν – a + r = 2
COROLARIO 5.2.- Sea G = (V, A) un grafo o multigrafo plano conexo sin lazos con los
valores ⎜V⎟ = ν y ⎜A⎟ = a > 2. y r regiones. Entonces se deben cumplir
las siguientes condiciones 3r ≤ 2a y a ≤ 3ν - 6.
Ejemplo 5.9.4.- El grafo K5 no tiene lazos y es conexo con 10 aristas y cinco vértices.
En consecuencia: 3ν - 6 = 15 – 6 = 9 < 10 = a. Por lo tanto por el
Corolario 5.2, vemos que K5 no es plano.
Ejemplo 5.9.5.- El grafo K3, 3 no tiene lazos y es conexo con 9 aristas y seis vértices.
En consecuencia: 3ν - 6 = 18 – 6 = 12 ≥ 9 = a. Sería un error concluir a
partir de esto que K3, 3 es plano; cometeríamos el error de estar
argumentando al revés.
Sin embargo, K3, 3 no es plano. Si K3, 3 fuera plano, entonces como
cada región del grafo está limitada por al menos cuatro aristas,
tendríamos 4r ≤ 2ª. Del teorema de Euler, tenemos ν – a + r = 2 o de
r = a - ν + 2 = 9 – 6 + 2 = 5, y 20 = 4r ≤ 2ª = 18. De esta demostración
surge que K3, 3 no es plano.
195
Teoría de Grafos
a b
h g
Figura 5.10.2
e f
d c
3– ¿Cuál de los grafos de la Figura 5.10.3 es conexo? En el caso que no sea conexo,
¿cuántas componentes conexas tiene?
G2 a
a b
G1
g
c
d f
b
f e
e h
c
Figura 5.10.3
d
4– a) Dé un ejemplo de un grafo conexo G tal que al eliminarle cualquier arista se
obtenga un grafo disconexo.
b) Sea G un grafo que satisface la condición del apartado a) ¿Debe G carecer de
lazos? ¿Puede G ser un multígrafo? Si G tiene n vértices, ¿podemos determinar
cuántas aristas tiene?
196
Teoría de Grafos
a G a G1 G2
b b b
c d d c d
f f
f
j j
h i i i j
g g g
Figura 5.10.4 (a) (b) (c)
7− Sea G un grafo con V (G) ⊆ {1, . . . , n} con |V (G)| = v y |A(G)| = a. ¿Cuántos grafos
distintos con vértices en {1, . . . , n} contienen a G como subgrafo?
8− Probar que si G es un grafo con al menos dos vértices, entonces G tiene al menos dos
vértices con el mismo grado.
G1 G2 G3
Figura 5.10.6
b) Trace un grafo, sin lados paralelos, representado por las siguientes matrices
de adyacencia:
⎛1 0 0 1 0⎞
⎛1 0 0 0⎞
i) ⎜ ⎟ ii) ⎜ ⎟
⎜0 0 1 0 1⎟
⎜0 1 1 0⎟
A = ⎜0 1 1 1 1⎟ A=⎜
1 1 0⎟
⎜ ⎟ ⎜
0
⎟
⎜1 0 1 0 0⎟ ⎜0 0 0 0 ⎟⎠
⎜0 ⎝
⎝ 1 1 0 0 ⎟⎠
197
Teoría de Grafos
i) ⎛1 0 0 0 0 1⎞ ii)
⎜ ⎟ ⎛0 1 0 0 1 1⎞
⎜0 1 1 0 1 0⎟ ⎜ ⎟
⎜0 1 1 0 1 0⎟
I = ⎜0 0 0 0 0 0⎟
⎜ ⎟ I = ⎜0 0 0 0 0 1⎟
⎜1 1 0 1 0 0⎟ ⎜ ⎟
⎜0 ⎜1 0 0 1 0 0⎟
0 1 1 1 1 ⎟⎠ ⎜1
⎝
⎝ 0 0 1 0 0 ⎟⎠
14 − Sea G un grafo conexo con cuello c(G). Probar que si d(u, v) ≤ 2 c(G), entonces hay
una única geodésica de u a v. a
Figura 5.10.7 d c
+
16 – Si n ∈Z y n ≥ 3, el grafo Rueda con n radios se define como el grafo formado por un
ciclo de longitud n y un vértice adicional que es adyacente a los n vértices del ciclo.
Este grafo se denota con R n
a) Trace R3 ,R4 , R5 y R6
b) ¿Es algún grafo Rn isomorfo a un grafo completo Kn?
a)
b)
198
Teoría de Grafos
c)
d)
Figura 5.10.8
18 − Construir cinco grafos con 8 vértices, todos de grado 3, de forma que cada dos de esos
grafos no sean isomorfos.
19 – En cada uno de los siguientes apartados, use el concepto de grafos complementarios
para determinar si cada par de grafos que se da son isomorfos o no:
a)
G1 G2
b)
G1 G2 Figura 5.10.9
c)
G1 G2
199
Teoría de Grafos
20 − Probar que Cn es el único grafo conexo (salvo isomorfismos) con n vértices de forma
que el grado de todos sus vértices es 2.
21 − ¿Cuántos grafos de tres vértices pueden construirse de manera que cada dos no sean
isomorfos? ¿Y cuántos con cuatro?
Sugerencia. Hacer una partición de los grafos según haya o no vértices de grado tres;
luego según haya o no de grado dos, etc.
22 − Fijemos los vértices {1, . . . , n} y sea G el grafo completo con esos vértices.
(a) ¿Cuántos grafos isomorfos a un C3 distintos se pueden formar que sean subgrafos
del grafo G?
(b) ¿Cuántos grafos isomorfos a un Ck distintos se pueden formar que sean subgrafos
del grafo G?
(c) ¿Cuántos grafos isomorfos a un Kr se pueden formar con los vértices {1, . . . , n}?
(Obsérvese que el apartado (a) es un caso particular de (b) y (c)).
(d) La misma pregunta, pero para un Kr,s.
23 – Trace grafos o multígrafos que tengan las propiedades dadas en cada uno de los
siguientes apartados o explique por que no existen tales grafos:
a) Que tenga tres aristas y dos vértices.
b) Que tenga tres aristas y la suma de los grados de sus vértices sea 10.
c) Que sea 3-regular y que tenga cinco vértices.
d) Que sea 3-regular y que tenga seis vértices.
e) Que posea seis vértices y cuatro aristas
f) Que posea cuatro vértices con grados 1, 2 , 3 y 4
g) Que sea un grafo simple que tenga seis vértices con grados 1,2,3,4,5,5
25 – Determine los valores de n para los que el grafo completo Kn tiene un circuito euleriano.
¿Cuáles Kn tienen recorrido euleriano pero no circuito euleriano?
a b c
d e f g
Figura 5.10.10
h i j k
200
Teoría de Grafos
a) Utilizando vértices para representar los pueblos y aristas para los tramos de
carretera que los unen; dibuje un grafo que ilustre esta situación.
b) ¿Es posible comenzar en algún pueblo y viajar por todas las carreteras
mencionadas exactamente una vez,
i) volviendo al mismo pueblo?;
ii) si no es necesario regresar al pueblo en el que inició el recorrido?
n − p ≤ m ≤ ½ (n − p)(n − p + 1) .
Comentario: si un grafo tiene δ grande (todos los vértices tienen muchos vecinos) y c grande
(todos los ciclos son largos), estos resultados nos dicen que tendría muchos vértices. Por
ejemplo, si de un grafo sabemos que no tiene triángulos (C3) ni cuadrados (C4) y tiene menos
de 100 vértices, entonces al menos uno tiene grado ≤ 10. O si δ = 10 y c = 10, entonces el
grafo tiene al menos 6561 vértices.
Sin embargo, esto ocurre cuando exigimos que ambos números sean altos simultáneamente:
un grafo como el K11 tiene δ = 10, y sólo tiene 11 vértices. Mientras que un C10 tiene c = 10 (y
10 vértices).
30 − La siguiente figura muestra un grafo que representa una sección de una tienda. Los
vértices indican donde se localizan las cajas, mientras que las aristas indican los
pasillos entre ellas. La tienda contrata a una empresa de vigilancia y desea saber:
a) ¿Puede un solo vigilante recorrer todos los pasillos pasando una sola vez por cada
pasillo y volver al punto de partida?
b) ¿Puede un solo vigilante recorrer todos los pasillos pasando una sola vez por cada
pasillo sin necesidad de volver al punto de partida?
Figura 5.10.11
31 – Al visitar el museo de ciencias, Pablo y David se preguntan si podrían pasar por las
siete habitaciones y el pasillo que las rodea sin cruzar ninguna puerta más de una vez.
Si comienzan desde la posición del pasillo marcada con una estrella en la Figura
5.10.12, ¿pueden lograr su objetivo?
201
Teoría de Grafos
Figura 5.10.12
32 – a) ¿Cuántos vértices y cuántas aristas tienen los grafos bipartitos completos K4,7, K7,11
y Km,n donde m,n ∈ Z+
Figura 5.10.13
34 - ¿Cuál es la longitud del camino simple más largo en cada uno de los siguientes grafos?
a) K1,4 b) K3,7 c) K7,12 d) Km,n
35 - ¿Puede un grafo bipartito contener un ciclo de longitud impar? Explique por qué.
Figura 5.10.14
G
38 – Determine cuáles de los siguientes grafos son planos. Si un grafo es plano, vuelva a
dibujarlo sin aristas solapadas. Si no es plano, encuentre un subgrafo homeomorfo a K5
o a K3,3 .
202
Teoría de Grafos
a) b)
a
a b c d
e f
b
j
e c
d
i h g f
c) d)
e
f b
d h
g
c Figura 5.10.15
u v w x y z
39 – Determine el número de vértices, aristas y regiones para cada uno de los siguientes
grafos planos. Verifique que se cumple el Teorema de Euler.
a) b)
Figura 5.10.16
=============================
203
Árboles
CAPITULO VI
ÁRBOLES
La de los Bernoulli de Basilea es, quizás, la familia más famosa de las Matemáticas.
Nicolás (1623-1708)
Famosa por la cantidad de excelentes matemáticos que “produjo” (hasta ocho, los que
aparecen en negrita en el esquema anterior, en tres generaciones distintas) y, también, por la
especial personalidad de algunos de ellos. Lo que aquí nos interesa es, precisamente, la
manera en que hemos exhibido la información sobre la familia,
su árbol genealógico. Es un grafo, donde los vértices van
etiquetados con los nombres de los componentes de la familia,
que tiene una estructura especial.
204
Árboles
La primera definición de la noción de árbol (de las varias que daremos) es la sugerida
por los ejemplos vistos anteriormente:
En el mismo tono botánico, se define un bosque como un grafo sin ciclos (si es conexo,
sería un árbol; si no lo es, sus componentes conexas serían árboles). Por ejemplo, los grafos
lineales Ln son árboles, mientras que los circulares Cn o los completos Kn no lo son en cuanto n
≥ 3. Los grafos bipartitos completos Kr,s, que son siempre conexos, sólo son árboles si s = 1 ó
r = 1 (si r ≥ 2 y s ≥ 2 hay al menos un ciclo de orden cuatro).
PROPOSICIÓN 6.1.- Un grafo G es un árbol (un conexo sin ciclos) ⇔ Es conexo y tiene la
propiedad de que al eliminar una arista cualquiera del grafo, éste deja
de ser conexo.
Sea a una arista de G y formemos el grafo G \ {a} eliminándola. Si G \ {a} fuera conexo,
podríamos conectar en G \ {a} los vértices de a. Pero añadiendo la arista a, lo que tendríamos
sería un ciclo en G (contradicción). Así que G \ {a} es no conexo (sea cual sea la arista a de G
que elijamos).
PROPOSICIÓN 6.2.- Un grafo G es un árbol (un conexo sin ciclos) ⇔ No tiene ciclos y, si
añadimos una arista cualquiera, se forma un ciclo.
Demostración: En un sentido, sea G un grafo conexo y sin ciclos. Consideremos dos vértices
cualesquiera que no estén unidos por arista alguna en G. Por estar en un grafo conexo, existirá
un paseo que los conecte en G. Al añadir una arista entre los vértices, se formará un ciclo.
En el otro sentido, sea G un grafo sin ciclos para el que añadir una arista cualquiera
supone la formación de un ciclo. Supongamos que no fuera conexo. En este caso, al menos
existirían dos vértices que no podríamos conectar en G. Pero entonces todavía podríamos
añadir la arista que los une sin que se nos formara un ciclo, contradicción.
Sabemos que en un grafo conexo el número de aristas |A (G)| no puede ser menor
que |V (G)| − 1. La igualdad se alcanza para los árboles, como nos dice el siguiente resultado:
205
Árboles
Demostración: En un sentido, vamos a proceder por inducción (en su versión fuerte) sobre el
número de aristas, |A|:
• Si G es un árbol con una arista, |A(G)| = 1, sólo cabe la posibilidad de que sea un L2,
para el que |V (G)| = 2.
• Supongamos cierto que para todo árbol con |A(G)| ≤ d se tiene que |A(G)| = |V (G)|−1.
G \ {e} = G1 ∪ G2,
|A(G1)| = |V (G1)| − 1
+ |A(G2)| = |V (G2)| − 1
−−−−−−−−−−−−−−−−−−−−−−−−
|A(G)| −1 = |V (G)| − 2 ,
Los ejercicios 6.1.1 y 6.1.2 recogen algunas otras caracterizaciones. Resumamos todas
las características que hacen de un grafo G un árbol: es conexo, sin ciclos, tiene que |A(G)| =
|V (G)| − 1 aristas y, si quitamos una arista cualquiera, se desconecta; y si añadimos una arista
cualquiera, se forma un ciclo. Es decir, como ya adelantábamos, es el grafo conexo más barato
(en el sentido de que no sobra ni falta arista alguna) que podemos construir.
Como parece claro, la sucesión de grados de los vértices de un árbol ha de ser muy
especial. Ya sabemos que en cualquier grafo G = (V, A) se tiene que
∑ δ (v) = 2 A
v ∈V
∑ δ (v) = 2 V
v ∈V
-2
206
Árboles
Obsérvese que ahora sólo tenemos un “grado de libertad”, el número de vértices |V |, pues el
de aristas ya queda fijado. De esta igualdad podemos deducir el siguiente resultado.
TEOREMA 6.1.- Todo árbol con |V | ≥ 2 tiene, al menos, dos vértices de grado 1.
Demostración: Supongamos que no hay vértices de grado 1, es decir, que δ(v) ≥ 2, para todo
v ∈ V . Entonces,
2V − 2 = ∑ δ (v) ≥ ∑ 2 = 2 V
v ∈V v ∈V
lo que resulta imposible. Pero tampoco puede ocurrir que haya un sólo vértice w de grado 1,
porque tendríamos
2V − 2 = ∑ δ (v) = δ ( w ) + ∑ δ ( v ) ≥ 1 + 2 (V
v ∈V v ≠w
− 1) = 2 V − 1
Ejemplo 6.1.1.- ¿Cómo son los árboles con n vértices que tienen el menor y el mayor número
posible de vértices de grado 1?
Sabemos que el mínimo número de vértices de grado 1 es 2. Así que, si un árbol con n
vértices tiene exactamente dos vértices, digamos w y u, de grado 1, se cumplirá que
2n − 2 = ∑ δ (v) = 1 + 1 + ∑ δ ( v )
v ∈V v ≠ u ,w
En la suma final tenemos n−2 términos, todos ellos mayores o iguales que 2; la única forma de
conseguir la igualdad será que δ(v) = 2 para todo v ∈ V, v ≠ u, w. Y esta configuración de
grados es la del grafo lineal con n vértices, Ln.
207
Árboles
2n − 2 = ∑ δ (v) = ( n − 1 ) + δ ( w ) ⇒ δ ( w ) = n − 1
v ∈V
TEOREMA 6.3.- Si a y b son vértices distintos en un árbol T = (V, A), entonces hay un
único camino que conecta a esos vértices.
Pero volvamos a los esfuerzos de Cayley, que estaba interesado, por ejemplo, en la
cuestión de enumerar los isómeros de hidrocarburos saturados, cuya fórmula es Ck H2k+2: los
átomos de carbono tienen valencia 4, mientras que los de hidrógeno, valencia 1. Se trata de un
grafo con 3k + 2 vértices, cuya suma de grados es 4k + (2k + 2) = 6k + 2, así que el grafo,
debe tener 3k +1 aristas. ¡Ah!, el número de aristas es el de vértices menos 1: se trata de un
árbol (si suponemos, como parece razonable, que el grafo es conexo).
Enumerar los grafos no isomorfos con n vértices y una cierta estructura (por ejemplo,
ser árboles, tener una determinada sucesión de grados) es, en general, una cuestión muy
complicada. Cayley sólo consiguió resolver algunos casos particulares y, años después, Pólya
desarrollaría su teoría enumerativa para dar respuesta a los problemas de este tipo. Sin
embargo, si etiquetamos los vértices, las cosas se simplifican a veces. Por ejemplo, sabemos
que, dado el conjunto {v1, . . . , vn}, hay 2 (n 2) grafos distintos con ese conjunto de vértices.
Cayley obtuvo, en 1889, una fórmula, sorprendentemente simple, para el caso de los árboles
con n vértices. Veamos qué nos sugieren algunos ejemplos sencillos.
Si tenemos dos vértices, sólo cabe una posibilidad, que el árbol sea isomorfo a un L2. Y si el
conjunto de vértices es {1, 2}, hay también un único árbol (los dos posibles etiquetados de los
vértices dan el mismo resultado).
Los árboles con tres vértices también han de ser isomorfos al grafo lineal
correspondiente, L3. Si el conjunto de vértices es {1, 2, 3}, basta con decidir qué símbolo va,
208
Árboles
por ejemplo, en la posición central (cuál es el vértice de grado 2). Esto se puede hacer de tres
formas distintas, así que hay 3 árboles distintos con vértices {1, 2, 3}.
Vamos con el caso de cuatro vértices. Para asegurarnos de no olvidarnos ningún caso,
ayudémonos de la relación:
∑δ (v
i =1
I )=8
así que no puede haber vértices de grado 5 o mayor. Si hay de grado 4, la sucesión de grados
ha de ser (1, 1, 1, 1, 4), a la que le corresponde un único árbol, el que aparece en la Figura
6.1.4 (a). Etiquetarlo con {1, 2, 3, 4, 5} es muy sencillo, pues basta decidir qué situamos en el
vértice central: en total, 5 posibilidades.
Resumiendo, con 5 vértices hay tres árboles no isomorfos, y 125 árboles distintos con vértices
{1, 2, 3, 4, 5}.
209
Árboles
De nuevo nos dejamos guiar por la relación δ (v1) + · · · + δ (v6) = 10, que nos dice que no
puede haber vértices de grado 6 o mayor.
Si hay vértices de grado 5, sólo podría haber uno, y la sucesión de grados sería (1, 1, 1, 1, 1, 5).
El único grafo con estas características es el que aparece en la Figura 6.1.5 (a). Y el etiquetado
de los vértices con {1, . . . , 6} sólo requiere decidir el símbolo del vértice central: seis
posibilidades.
Si no hay de grado 5, pero hay de grado 4, sólo cabe que la sucesión sea (1, 1, 1, 1, 2, 4). El
árbol correspondiente aparece en la Figura 6.1.5 (b). Dejamos como ejercicio para el lector la
comprobación de que hay 120 árboles con vértices {1, . . . , 6} asociados a esta estructura. Si
no hay vértices de grado 4, pero si de grado 3, las cosas se ponen interesantes. Tenemos, por
un lado, la sucesión de grados (1, 1, 1, 1, 3, 3), cuyo árbol asociado es el de la Figura 6.1.5 (c).
El lector debería comprobar que hay 90 formas distintas de etiquetar los vértices de este árbol.
Pero, por otro lado, tenemos la sucesión de grados (1, 1, 1, 2, 2, 3), que tiene un único vértice
de grado 3. Como ya vimos, hay dos árboles no isomorfos a esta sucesión, los que se
muestran en la Figura 6.1.5 (d) y (e). Es, de nuevo, un sencillo ejercicio comprobar que hay 180
etiquetados distintos para el de arriba y 360 para el de abajo.
Por último, si no hay de grado 3, entonces sólo cabe tener cuatro vértices de grado 2,
(1, 1, 2, 2, 2, 2), y el grafo es isomorfo a un L6. Y hay 360 distintos árboles que podemos
construir con esta estructura y vértices {1, . . . , 6}, indicado en la Figura 6.1.5 (f).
(a) (b)
(c) (d)
(e)
(f)
Figura 6.1.5
En resumen, hay seis árboles no isomorfos con 6 vértices, y 1296 árboles distintos con
vértices {1, . . . , 6}.
210
Árboles
Los resultados que hemos ido obteniendo hasta ahora son especialmente
“sospechosos”; y más, si como aparece en la tabla, calculamos los dos siguientes casos:
TEOREMA 6.4.- (Cayley) El número de árboles distintos que se pueden formar con el
conjunto de vértices {1, . . . , n} es nn−2.
En una cierta empresa hay m jefes y k empleados. Los queremos organizar de manera
que cada empleado tenga un único supervisor (que pudiera ser otro empleado o quizás un jefe).
Al número de maneras distintas en que esto se puede hacer lo llamaremos P(m, k).
1. Distinguimos a los empleados cuyos supervisores son jefes. A estos empleados, de los que
habría un cierto número s, con 1 ≤ s ≤ k, se les asigna, desde este momento, y como no
podría ser de otro modo, el papel de jefecillos.
2. Decidimos, pues, qué s empleados son jefecillos; esto se puede hacer de (k s) maneras.
En total,
k
⎛k ⎞
P( m, k ) = ∑ ⎜⎜⎝ s ⎟⎟⎠ m
s =1
s
P( s, k − s )
Esta regla de recurrencia, junto con los valores iniciales de antes, determina de manera única
el valor de los P (m, k), como el lector podría comprobar construyéndose la correspondiente
tabla de valores.
211
Árboles
términos, consiste en decidir qué vértices van en la segunda generación (por debajo de las
raíces), y cómo se distribuyen en esa segunda generación::
J1 J2 J3 Jm
Figura 6.1.6
Sólo queda resolver la recurrencia de antes para obtener el valor particular de los P(m,
k) que perseguimos. Aquí llega el ingrediente ingenioso de la prueba. La ecuación de antes nos
recuerda vagamente a las sumas que se obtienen en el teorema del binomio. El lector podría
comprobar, utilizando este teorema, que la función f(m, k) = m(m+ k)k−1 cumple la misma
regla de recurrencia y los mismos valores iniciales. Así que P(m, k) = f(m, k) para todo m y k.
En particular,
Nivel 0 = {raíz}
Llamaremos a, la altura del árbol, al máximo nivel no vacío. Es importante recordar que el valor
de a depende de la raíz elegida. Por ejemplo, si partimos del árbol que aparece dibujado en la
Figura 6.2.1, cualquiera de sus vértices puede servir como raíz. Elegir, por ejemplo, el vértice 1
o el 3 lleva a que la altura del árbol sea 2 ó 4, como sugieren los siguientes esquemas,
indicados en la Figura 6.2.1:
212
Árboles
2 3 2 3
1 1
4 5 4 5
6 6
5
3 2 1 4
6
Figura 6.2.1
• Los descendientes de un vértice v son los vértices del nivel siguiente al de v que sean
vecinos suyos (al vértice v se le dice progenitor de sus descendientes).
• Un árbol con raíz serla q-ario si cada progenitor tiene exactamente q descendientes (es
decir, el número de descendientes es 0 si el vértice es hoja y q si es progenitor). Seria casi
q-ario si el número de descendientes de cada vértice está comprendido entre 0 y q.
• el número de vértices, n;
• el número de hojas, h;
• y el tipo de árbol, definido por el entero positivo q (podría ser q-ario o casi q-ario).
La importancia de estos árboles con raíz radica en que se utilizan para representar algoritmos
en los que intervienen operaciones binarias (o q-arias) sucesivas. Veamos algunos ejemplos.
Tenemos 4 monedas, {1, 2, 3, 4}, y, a lo sumo, una de ellas no tiene el peso correcto (no es
legal). Disponemos además de una moneda patrón, la 0, con el peso correcto. El problema es
el siguiente: con una balanza, que tiene tres resultados posibles, queremos averiguar de la
manera más económica posible (con menos usos de la balanza) cuál es la no legal. Podemos,
por supuesto, comparar sucesivamente la moneda patrón con las otras cuatro. Este
procedimiento emplea, en el peor de los casos, cuatro pesadas para obtener la respuesta
213
Árboles
0,1 2,3
> = <
2 3 0 4 2 3
Los símbolos casi se explican por sí mismos: < significa que la balanza se vence hacia la
derecha, > hacia la izquierda, e =, se queda equilibrada. El árbol que hemos diseñado es
ternario (q = 3), tiene altura a = 2 (el número de pesadas) y número de hojas h = 9. Lo
fundamental en este caso es que el algoritmo funciona porque el árbol tiene 9 hojas, justo el
número de respuestas posibles (1 pesa más, 2 pesa menos, etc.).
Dada una lista de tres números cualesquiera, (a, b, c), queremos ordenarlos con
comparaciones binarias. Diseñamos el siguiente algoritmo: en el primer paso, comprobamos si
el primer elemento es menor o igual que el tercero. Si la respuesta es si, los dejamos tal como
están; si es no, los permutamos. En el segundo, miramos si el primero es menor o igual que el
segundo, y de nuevo procedemos como antes, dependiendo de la respuesta. Por último, en el
tercer paso investigamos si el segundo es menor o igual que el tercero (observamos que aquí
hay respuestas que son incompatibles con las obtenidas anteriormente). Si representamos este
proceso en un árbol, obtenemos el árbol de la Figura 6.2.2.
El árbol así construido es casi binario, con a = 3 y h = 6, que de nuevo coincide con el número
de resultados posibles (las 3! = 6 posibles ordenaciones). Podríamos preguntarnos si se
podrían ordenar estos tres números, con comparaciones binarias, en menos pasos, por
ejemplo dos. Veremos que no, porque en un árbol casi binario se cumplirá que h ≤ 2a; si a es 2,
obtenemos que h ≤ 4, y con ese número de hojas no podríamos cubrir todos los resultados
posibles, que recordamos que eran 6. ♣
214
Árboles
abc
a a
¿1 ≤ 3 ? si no
abc cba
¿1a ≤ 2a? si no si no
Figura 6.2.3
Esta es una de las muchas variantes del llamado juego de Nim, que analizaremos
detalladamente mas adelante. Lo que ahora nos interesa es que podemos describir los
posibles desarrollos de la partida con árboles: representaremos cada configuración de
monedas con un vértice, que etiquetaremos con un I o un II, dependiendo de cuál sea el
jugador al que le toca jugar, y un número, para recordar cuántas monedas quedan en el
montón. Así, para el montón de partida que dibujamos a la derecha, el primer vértice vendría
etiquetado con un I6, para recordar que juega I y que hay seis monedas en el montón.
El jugador I tiene dos opciones, quitar una o dos monedas; estas dos acciones
vendrían representadas por aristas, hacia la derecha si quita dos monedas, hacia la izquierda si
quita una. Para cada una de estas elecciones, el jugador II se encuentra con dos
configuraciones distintas y en cada una de ellas puede tomar, a su vez, dos decisiones:
I6 I6
Figura 6.2.4 I4 I3 I3 I2
Obsérvese que, en cada paso, lo que obtenemos es un árbol. Además, como en cada
movimiento se reduce el tamaño del montón, el juego es finito y, por tanto, el árbol que
representa los diferentes desarrollos del mismo también lo serla. Para el caso que nos ocupa,
un montón inicial de seis monedas, el árbol completo del juego es el que aparece debajo de
215
Árboles
estas líneas. Como preparación al análisis que haremos mas adelante, etiquetamos las hojas
del árbol con G si en esa hoja el jugador I ha ganado la partida y con P si ha perdido:
En los ejemplos anteriores, la clave para que los algoritmos (representados por árboles
q-arios, o casi q-arios) funcionaran era que el número de hojas cubriera todas las posibles
respuestas. Estos dos parámetros, la altura y el número de hojas, no son independientes, y las
cotas que obtendremos nos permitirán establecer estimaciones a priori sobre, por ejemplo, el
mínimo número de pasos que puede tener un cierto algoritmo.
Esto nos sugiere, por un lado, que h ≤ qa. Para la otra situación extrema, como en cada
nivel, desde el 1 hasta el a − 1, aparecen q − 1 hojas nuevas y en el nivel a hay q hojas,
sospechamos que h ≥ (a − 1)(q − 1) + q = (q − 1)a + 1.
Demostración. Nótese que hemos relajado las condiciones sobre el tipo de árbol, basta con
que sea casi q-ario (por supuesto, un árbol q-ario es también casi q-ario; pero no al revés, en
general).
h= ∑h ≤ ∑q
i
i
i
ai
≤ qq a −1 = q a Figura 6.2.5
216
Árboles
Ejemplo 6.2.4.- Apliquemos las cotas obtenidas al problema de la balanza, pero ahora con r
monedas (en lugar de cuatro), de las cuales a lo suma una es falsa, y la
moneda patrón.
Es claro que el número de posibles resultados es 2r + 1, porque para cada moneda hay dos
posibles (pesa más o menos de lo legal) y hay un resultado extra, que es que todas sean
legales. Un algoritmo que permita detectar la moneda falsa debe recoger todos estos
resultados. Si lo representamos por un árbol ternario, la altura será el número máximo de
pesadas necesarias para alcanzar todos los posibles resultados; y el número de hojas debe
poder cubrir todos los resultados. Como h ≤ 3a, necesitaremos:
Recordemos que con r pesadas siempre lo podemos hacer; aquí comprobamos que, sea cual
sea el algoritmo, si está basado en comparaciones ternarias, entonces requerirá, como mínimo,
un número de pasos del orden de log r. Por ejemplo, si r = 4, como en el ejemplo que
proponíamos, tendremos que:
r = 4 ⇒ a ≥ log39 = 2,
así que al menos se requieren dos pesadas. De la misma manera obtendríamos que para r
entre 3 y 13 necesitaríamos al menos necesitaremos 3 pesadas. Y se requerirían cuatro
pesadas, al menos, para cualquier r entre 14 y 40. Pero éstas son cotas teóricas; otra cosa, por
supuesto, es diseñar un algoritmo que permita hacerlo con ese número mínimo de pesadas.
Por ejemplo,
En el ejemplo que hemos descrito, el juego de Nim con seis monedas, podemos contar en el
árbol que hay exactamente 13 hojas. Aunque hemos etiquetado las hojas sólo con G y P,
dependiendo de si el jugador I gana o pierde, en realidad cada hoja representa un posible final
del juego (y de hecho, a cada hoja le corresponde un desarrollo del juego distinto). Si el juego
de Nim parte de n monedas, es fácil convencerse de que la altura del árbol (que es casi-binario)
es siempre n, porque el camino de mayor longitud en el árbol es aquél en el que vamos
quitando una sola moneda en cada turno (la rama de la izquierda), así que podemos estimar
n
#{ posibles partidas en un Nim con n monedas} = #{hojas del árbol} ≤ 2 .
También podemos observar que el último nivel sólo tiene una hoja, así que podemos mejorar la
estimación. Si llamamos Pn al número de hojas que tiene el árbol del juego de Nim con n
monedas tendremos que:
217
Árboles
Pn ≤ 2n−1 + 1.
Pero en realidad podemos calcular explícitamente el número de hojas que hay. Para ello,
fijémonos en que un árbol de Nim con n monedas se compone de un árbol de Nim con n − 1
monedas (el árbol que encontramos a partir del descendiente de la raíz que está a la izquierda)
y otro con n−2 monedas (el de la derecha). De acuerdo, los papeles de I y II están
intercambiados, pero eso no afecta al número de hojas que tenga cada árbol. Por supuesto, el
número de hojas del árbol total es la suma del número de hojas que tenga cada subárbol, es
decir,
Nuestra conocida ecuación de Fibonacci. Los valores iniciales son P1 = 1 y P2 = 2; así que el
número de hojas de un juego de Nim con n monedas es justamente el número de Fibonacci
Fn+1.
DEFINICIÓN 6.3.- Consideremos un grafo G = (V, A). Diremos que un árbol H es árbol
recubridor o recubridor de G si cumple que:
Es decir, es un subgrafo recubridor del grafo inicial que, además, es un árbol. Asegurémonos
primero de que tales árboles existen si, como es razonable, partimos de un grafo conexo.
218
Árboles
cada paso, los sucesivos grafos son conexos; cuando el número de aristas llegue a |V (G)| − 1,
habremos llegado a un árbol recubridor.
Existen otros algoritmos para construir un árbol recubridor, que van “haciendo crecer” el
árbol en pasos sucesivos, y que resultan ser más sencillos desde el punto de vista
computacional. Los veremos en la subsección 6.3.2, aunque allí, por el mismo precio,
resolveremos una cuestión mas general, pues permitiremos que las aristas tengan “peso”.
Como veremos, la cuestión de hallar un árbol recubridor en un grafo sin pesos no es sino un
caso particular de este planteamiento mas general.
Consideremos el grafo circular con n vértices, Cn, para el que |A(Cn)| = |V (Cn)|. Formar un
árbol recubridor consiste, simplemente, en quitar una arista; y cualquiera de las n que hay vale
para ello. Así que Cn tiene n posibles árboles recubridores.
El grafo lineal con n vértices, Ln, es ya un árbol. Así que Ln es el único árbol recubridor
que tenemos. Esto es un resultado general: si G es un árbol, sólo tiene un árbol recubridor (él
mismo).
Por último, consideremos el grafo completo con n vértices, Kn. Buscamos subgrafos H
de Kn que sean árboles, que tengan V (H) = V (Kn) = {1, . . . , n}. Pero en Kn están todas las
aristas posibles, así que:
Kn es, claro, el grafo con n vértices que más árboles recubridores tiene.
219
Árboles
Lo que buscamos son conjuntos A y B tales que entre los dos tengamos todos los vértices de
la derecha y de forma que su intersección conste de un único vértice:
2. Una vez elegido el elemento especial, basta decidir si el resto de los elementos están
en A ó en B. O, lo que es equivalente, basta formar una lista de longitud s − 1 con
repetición permitida con dos símbolos (uno corresponde a estar en A y el otro a estar
en B). Esto se puede hacer de 2s−1 formas distintas.
En total tenemos que hay s 2s−1 árboles recubridores de K2,s. El resultado general es el
siguiente: un grafo Kr,s tiene s r−1 r s−1 árboles recubridores distintos .
Obsérvese que, en la matriz D − M, todas sus filas y columnas suman 1, así que es una matriz
singular. Este resultado permite, por ejemplo, calcular el número de árboles recubridores del
grafo escalera que aparece en la Figura 6.3.3. Las matrices M y D son
0 1 0 0 0 1 2 0 0 0 0 0
1 0 1 0 1 0 0 3 0 0 0 0
M = 0 1 0 1 0 0 D = 0 0 2 0 0 0
0 0 1 0 1 0 0 0 0 2 0 0
0 1 0 1 0 1 0 0 0 0 3 0
1 0 0 0 1 0 0 0 0 0 0 2
1 2 3
4 5 6
Figura 6.3.3
220
Árboles
Queremos contar cuántos árboles recubridores tiene un grafo completo Kn, cuyos vértices
tienen todos grados n − 1, tal cual se indican en las matrices de la página siguiente.
0 1 1 …. …. 1 n-1 -1 -1 …. …. 0
1 0 1 …. …. 0 -1 n-1 -1 …. …. 0
M = 0 1 0 …. …. 0 ⇒ D-M = -1 -1 n-1 …. …. 0
…. …. …. …. …. …. …. …. …. …. …. ….
…. …. …. …. …. …. …. …. …. …. …. ….
1 0 0 …. …. 0 -1 -1 -1 …. …. n-1
p( G ) = ∑ p( a )
a∈A( G )
El problema es el siguiente: elegir, de entre todos los posibles árboles recubridores de G, uno,
H, de forma que:
221
Árboles
p( H ) = ∑ p( a )
a∈A( H )
sea lo menor posible. Vamos a describir un par de algoritmos sencillos que consiguen este
objetivo. Ambos son algoritmos austeros, como el que describimos para la coloración de un
grafo: en cada paso, elegiremos la mejor decisión posible (que sea compatible con las
restricciones del problema). Obsérvese que estos algoritmos servirán también para resolver la
cuestión cuando se trate de un grafo sin pesos. Bastaría, por ejemplo, asignar peso 1 a cada
arista. En estas condiciones, todos los árboles recubridores tienen el mismo peso (exactamente
|V | − 1), y el resultado del algoritmo será, simplemente, uno de estos árboles recubridores.
ALGORITMO DE PRIM
• Examinamos todas las aristas que tienen a v como uno de sus extremos y, de entre
ellas, seleccionamos la que tenga un peso menor. Digamos que es la arista a, y sea w
su otro extremo. Formamos entonces V1 = {v, w} y A1 = {a}.
• Supongamos que hemos construido los conjuntos Vi−1 (que contendría i vértices) y Ai−1
(con i−1 aristas). De entre las aristas que unan vértices de Vi−1 con vértices de V \Vi−1,
escogemos la de menor peso, que añadimos a Ai−1 para formar Ai. El “nuevo” vértice
se añade a los de Vi−1 para formar Vi.
Observemos que, tal como está diseñado el algoritmo, los sucesivos grafos Gj = (Vj, Aj)
no pueden contener ciclos (y además son conexos). Si cuando el proceso acaba hemos
incluido todos los vértices del grafo, el resultado es un árbol recubridor. Sobre el hecho de que
sea de peso mínimo reflexionamos mas adelante. Observemos que no hemos exigido que el
grafo G fuera conexo. Si lo fuera, el algoritmo produciría un árbol recubridor; pero si no, el
resultado es un árbol recubridor de la componente conexa en la que se encuentre el vértice de
partida v.
ALGORITMO DE KRUSKAAL
• Al principio, A0 = Ø.
• Supongamos que ya hemos determinado Ai−1. El conjunto Ai seria Ai−1 ∪ {ai} si es que
el grafo (V, Ai−1 ∪ {ai}) no contiene ciclos. Es decir, si la adición de la arista ai no hace
que se forme un ciclo en el grafo producido hasta el momento. En caso contrario, Ai =
Ai−1.
222
Árboles
Observaciones
Empecemos insistiendo en que, si G es conexo, ambos algoritmos producen árboles
recubridores. Así que estos procedimientos sirven de comprobación de la conexión de un grafo
arbitrario. En el de Prim, los sucesivos grafos son siempre árboles, mientras que en el de
Kruskal no necesariamente: son bosques y sólo al final, si G es conexo, tendremos con
seguridad un árbol recubridor.
En el grafo con pesos que aparece en la Figura 6.3.5, el algoritmo de Prim, empezando
por ejemplo en el vértice 3, iría incluyendo,
sucesivamente, las aristas {3, 4}, {3, 5}, {5, 2} y {2, 2 5 3
1
1}. En el ultimo paso, se pueden elegir tanto la {2, 6} 2
como la {1, 6}. Uno de los posibles resultados es el 1
árbol recubridor, que es de peso mínimo, que 2 3 3 4
dibujamos abajo a la izquierda. El de Prim partiría de 2
4
una ordenación de las aristas según sus pesos. 6
6 5
Podría ser, por ejemplo, la siguiente:
({1, 2}, {3, 4}, {2, 6}, {1, 6}, {2, 5}, {3, 5}, {4, 5}, {2, 5
3}, {5, 6}). 2 3
1
2
El algoritmo iría incluyendo las aristas en el 1
2 3 3 4
orden que aparecen en esa lista, saltándose {1, 6} 2
(pues se formaría un ciclo), y acabando con la 4
elección de la arista {3, 5} (ya tendríamos cinco 6 6 5
aristas, las que necesitamos). El resultado seria el
mismo árbol recubridor de antes, Si cambiamos la Figura 6.3.5
ordenación de las aristas, respetando el que
aparezcan en orden creciente de pesos,
obtendríamos un árbol recubridor distinto (lo mismo ocurriría con el de Prim en cada momento
en que tengamos varias elecciones posibles).
En un grafo G conexo con pesos, siempre existe, al menos, un árbol recubridor de peso
mínimo, pero podría haber varios con ese peso mínimo. Piénsese, por ejemplo, en un grafo
completo Kn con pesos 1 en cada una de sus aristas: hay nn−2 árboles recubridores distintos, y
todos tienen el mismo peso, n−1. Los dos algoritmos que aquí hemos descrito pertenecen a los
que hemos dado en llamar la clase de los algoritmos austeros, porque en cada etapa toman la
decisión óptima, la mas “barata” en este caso, que sea compatible con las restricciones del
problema (en el de Prim, mantener en cada paso el carácter de árbol, en el de Kruskal, que no
se formen ciclos). No siempre estas estrategias
“austeras” garantizan que el resultado obtenido sea B
el mejor posible (recuérdese el algoritmo de
coloreado de grafos). Pero, en este caso, se puede 3 8
demostrar que, dado un grafo G conexo con pesos, 4 C 4
el resultado de ambos algoritmos, tanto el de Prim A E
como el de Kruskal, es un árbol recubridor de peso
5 1
mínimo (si hay varios, producen uno de ellos).
223
Árboles
DEFINICIÓN 6.4.- Un árbol con raíz es binario si para cada vértice v, el grado del mismo
es δ (v)=0, 1 o 2; es decir, si v tiene cuando mucho dos hijos. Si δ (v)=
0 o 2 para todo v, entonces el árbol con raíz es un árbol binario
completo.
Mediante árboles binarios podemos representar a cualquier expresión algebraica Veamos los
siguientes ejemplos:
Ejemplo 6.4.1:
*
/ ↑
((7 − a ) / 5 ) ∗ ((a + b ) ↑ 3 )
- - 5 + 3
7 a a b
Figura 6.4.1
Ejemplo 6.4.2: –
a − (3 / (b + 5 )) a /
3 +
b 5
Figura 6.4.2
DEFINICIÓN 6.6.- Sea T = (V, A) un árbol con raíz r. Si T no tiene otros vértices,
entonces la misma raíz el recorrido en orden previo y posterior de T. Si
⏐V⏐ >1. Sean T1, T2, T3,. . ., Tn, los subárboles de T, de izquierda a
derecha, entonces (como en la Figura 6.4.3):
224
Árboles
Ejemplo 6.4.3: El recorrido en orden previo de los vértices de este árbol es: 1, 2, 5, 11, 12,
13, 14, 3, 6, 7, 4, 8, 9, 10, 15, 16, 17. El recorrido en orden posterior visita
los vértices en el orden: 11, 12, 13, 14, 5, 2, 6, 7, 3, 8, 9, 15, 16, 17, 10, 4, 1.
2 3 4
5 6 7 8 9 10
11 12 13 14 15 16 17
Figura 6.4.4
DEFINICIÓN 6.7.- Recorrido en orden simétrico. Sea T = (V, E) un árbol binario con
raíz, donde r es la raíz.
1) Si | V | = 1, entonces el vértice r es el recorrido en orden
simétrico de T.
2) Si | V | > 1, sean TI y TD los subárboles izquierdo y derecho de T. El
recorrido en orden simétrico de T recorre primero los vértices de TI, en
orden simétrico, después visita la raíz y luego recorre, en el orden
simétrico, los vértices de TD.
a b
c e
d
Figura 6.4.5
f g i
h
j k m n
p q s t u
225
Árboles
V3
V1
V2 V4
Figura 6.4.6
Exigir esta condición hace pensar que los vértices seleccionados no pueden estar
todos muy “arriba” en el árbol, es decir, que los hj no pueden ser arbitrariamente pequeños. De
manera más precisa, y esto es lo que nos interesa comprobar, en una poda cualquiera, los hj
correspondientes han de cumplir que
∑2
j =1
−h j
≤1
Veámoslo: hemos seleccionado unos vértices v1,. . ., vk que están a alturas h1,. . ., hk.
Llamemos H = máx. {h1, . . . , hk} a la mayor altura a la que encontramos alguno de los vértices
señalados.
226
Árboles
análogo, pero ahora para los vértices seleccionados en segundo lugar, nos lleva al mismo
resultado.
k k k
∑2
v ∈A'
− h( v )
= ∑ ∑2j =1 v ∈D ( v j )
− h( v )
= ∑2 j =1
−H
D( v j ) = ∑2
j =1
−h j
= ∑2
v ∈A
− h( v )
El valor de la suma es el mismo para A que para A’. Pero claro, en A’ hay, a lo sumo, 2H
vértices, así que:
∑2
j =1
−h j
= ∑2
v ∈A
− h( v )
= A' 2 − H ≤ 2 H 2 − H = 1
Lo interesante del asunto es que el resultado es cierto en el otro sentido: si damos unos
números h1,. . ., hk tales que ∑ 2−hj ≤ 1, entonces en el árbol binario (infinito) podemos señalar
k vértices v1,. . ., vk de alturas respectivas h1,. . ., hk y de manera que ninguno sea antecesor
de ningún otro. Llamamos, como antes, H = máx. {h1, . . . , hk}. Y observamos que:
k k k
1≥ ∑2 j =1
−h j
= 2 −H ∑2
j =1
H −h j
⇒ 2H ≥ ∑2
j =1
H −h j
Mas adelante llamaremos a esta restricción condición de prefijo y veremos que será
fundamental a la hora de construir ciertos códigos. Veamos ahora otro ejemplo en el que esta
condición de prefijo es relevante.
227
Árboles
Tenemos k objetos que se pueden identificar con una sucesión de preguntas cuya respuesta
es un SI o un NO.
Sea G = (V, A) un grafo no dirigido, conexo, sin lazos, tal que | V | = n y donde los
vértices están ordenados como v1, v2, v3,..., vn. Para encontrar el árbol recubridor en
profundidad T, ordenado, con raíz, se siguen los siguientes pasos:
Sea G = (V, A) un grafo no dirigido (Figura 6.4.10), conexo, sin lazos, tal que | V | = n y
donde los vértices están ordenados como v1, v2, v3,..., vn. Para encontrar el árbol recubridor en
anchura T, ordenado, con raíz, se siguen los siguientes pasos:
228
Árboles
G a b
c d e f
Figura 6.4.10
g j
h i
T2 a
b c d
Figura 6.4.11
e g
f h i j
======================
229
Árboles
1.- Probar que un grafo G es un árbol (conexo sin ciclos) si y sólo si no tiene ciclos y que
se cumple |A(G)| = |V (G)| − 1.
2.- Probar que en un árbol existe un único camino que conecta dos vértices cualesquiera.
3.- Probar que el grafo G con n vértices es un árbol si y sólo si su polinomio cromático es
G(k) = k (k − 1)n−1.
Sugerencia. Para la implicación⇒, probar por inducción, y para ello, considerar un
vértice de grado 1 del árbol y aplicar el algoritmo de “quitar aristas”. Para la implicación
⇐, usar el teorema del binomio y la caracterización de árboles como grafos conexos
con n − 1 aristas.
4.- Sea G un grafo con n vértices cuyo polinomio cromático PG cumple que P’G (0) ≠ 0 y
que P(n−1)G (0) = (1 − n)(n − 1)!. Demostrar que G es un árbol.
5.- (a) ¿Existen árboles de siete vértices y con cinco vértices de grado 1 y dos de grado 2?
(b) ¿Y con siete vértices de grados 1, 1, 1, 2, 2, 2, 3?
6.- Si G es árbol con p vértices de grado 1, q vértices de grado 4 y ningún otro vértice,
¿qué relación hay entre p y q?
7.- Denotemos por N(d1, d2, . . . , dn) el número de árboles distintos que se pueden formar
con el conjunto de vértices {1, 2, . . . , n}, donde δ (j) = dj + 1.
(a) Observar que si ∑ d j ≠ n − 2 entonces N(d1, d2, . . . , dn) = 0.
n
j =1
8.- Hallar el número de árboles distintos que se pueden formar con los siguientes vértices
{1, 2,. . ., n} si (a) n = 6 y cuatro vértices tienen grado 2; (b) n = 5 y exactamente tres
vértices tienen grado 1.
9.- ¿Cuántos árboles distintos se pueden formar con un conjunto de ocho vértices, {1, 2,
3,. . ., 8}, de manera que 2 de los vértices tengan grado 4 y los 6 restantes tengan
grado 1?
10.- ¿Cuántos árboles con vértices {1, 2,. . ., n} tienen los grados de todos sus vértices
menores o iguales a 2?
230
Árboles
G1
G2
a b a b
c d c d
e f e f
G3 a b G4 a b
c c
d e f d e f
g
Figura 6.6.1 g
11.- Para los grafos de la Figura 6.6.1, diga cual de ellos es un bosque
G1 G2
a b
a
h g b
c
g c
f e d
f d
Figura 6.6.2
e
13.- Sean H y G dos grafos con los mismos vértices y de forma que toda arista de H lo sea
también de G. Probar que pG(x) ≤ pH(x), para todo x, x natural.
Sugerencia. Observar que en G hay mas prohibiciones (habrá menos coloraciones
válidas).
14.- Deducir del ejercicio anterior que si G es un grafo conexo con n vértices entonces:
16.- Consideremos el grafo que se obtiene al tomar n triángulos con exactamente un vértice
común. (El número total de vértices es 2n + 1 y el número de aristas es 3n.) ¿Cuántos
árboles recubridores tiene?
Sugerencia. Hay que quitar una arista en cada triangulo.
17.- Sea H un árbol recubridor de peso mínimo de un grafo ponderado G. Sea f una arista
de G que no está en H. Y sea e cualquier arista del camino (único) en H que une los
vértices de f. Probar que el peso de e es menor o igual que el peso de f.
Sugerencia. Obsérvese que si no se cumpliera esa condición podríamos escoger un
árbol recubridor con menor peso.
231
Árboles
18.- Sea G el grafo con vértices {a, b, 1, 2,. . ., 10} (12 vértices) y aristas {{a, j}, j = 1, 2,. . .,
10} y {{b, j}, j = 1, 2,. . ., 10} (20 aristas). Las aristas que tienen a a como extremo
pesan 1 y las aristas que tiene a b como extremo pesan 2. ¿Cuál es el peso mínimo de
entre los árboles recubridores de G?
Sugerencia. Hay que mantener una (y sólo una) arista de las que llegan a b.
19.- Encuentre dos árboles recubridores no isomorfos para el grafo completo bipartito K2,3 .
¿Cuántos árboles recubridores no isomorfos tiene K2,3 ?
21.- Trace un árbol recubridor del grafo G 1 de l a Figura 6.10.2 tal que posea n vértices
colgantes siendo:
a) n = 2
b) n = 3
c) n = 5
22.- a) Si un árbol tiene cuatro vértices de grado 2, uno de grado 3, dos de grado 4 y uno de
grado 5, ¿cuántos vértices colgantes tiene?
23.- Trace, si existe, un árbol que corresponda a cada una de las propiedades dadas en los
siguientes apartados. En caso de no existir explique la causa.
24.- Sean los siguientes árboles dirigidos. Determine cuál de ellos es árbol dirigido con
raíz
T1 T2 d e
b
a
a
d c f
c
e h g
b
g f h i i
Figura 6.6.3
232
Árboles
a
25.- - Sea el siguiente árbol:
a) ¿Qué vértices son las hojas?
b) ¿Qué vértice es la raíz?
c) ¿Qué vértice es el padre de g? b c
d) ¿Qué vértices son los descendientes de c?
e) ¿Qué vértices son los hermanos de m?
f) ¿Cuál es el número de nivel del vértice f?
g) ¿Cuál es la altura del árbol? d
h) ¿Es un árbol binario? e
i) ¿Cuál es el sub-árbol inducido por e? f
g h i
Figura 6.6.4
j k l m n
26.- Traza árboles binarios que represente a las siguientes expresiones algebraicas:
a) (a + b ) ↑ 2 − 4 / (a − b ) b) 3
5 + x / (2 + a − b )
27.- Encuentra las expresiones algebraicas que están representadas por los siguientes
árboles
a) b)
↑ +
- /
+
1/2
- x ↑ z 3
a
c d Figura 6.6.5 x y
28.- ( )
a) Escriba la expresión (w + x − y ) / π ∗ z 3 en notación polaca, mediante un árbol con
raíz.
/ ↑ a − bc + d ∗ ef , si a = c = d = e = 2 , b = f = 4 ?.
29.- Para los siguientes árboles, enumere los vértices según el recorrido en orden previo, el
recorrido en orden simétrico y el recorrido en orden posterior.
233
Árboles
a)
a
b c
d e f g
h i j k
b)
1 Figura 6.6.6
2 3
4 5 6 7
8 9 10
11 12 13 14 15
16 17 18
19 20
Figura 6.6.7
21
43 – a) Para el grafo G1, encuentre dos árboles recubridores si el orden de los vértices es
i) a , b , c , d , e , f , g , h ii) h , g , f , e , d , c , b , a iii) a , b , c , d , h , g , f , e
c f
e d a
f h e
g g c
h
Figura 6.6.8
234
Árboles
235