Matematicas Discreta
Matematicas Discreta
Matematicas Discreta
Versión preliminar
Departamento de Matemática
Universidad Nacional del Sur
Material elaborado por
• Estela Bianco
• Aldo V. Figallo
• Claudia Sanza
• Alicia N. Ziliani
2 Conjuntos 36
2.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2 El conjunto vacı́o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3 Descripción gráfica de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4 Subconjuntos de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.5 El conjunto de las partes de un conjunto . . . . . . . . . . . . . . . . . . . . . . 43
2.6 Operaciones con conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7 Diagramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.8 Propiedades de las operaciones conjuntistas . . . . . . . . . . . . . . . . . . . . 49
2.9 Principio de inclusión y exclusión . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.10 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3 Relaciones y funciones 56
3.1 Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 Relaciones n−arias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4 Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.5 Producto directo de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.6 Conjuntos coordinables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
i
4 Multigrafos y multidigrafos 92
4.1 Multigrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.2 Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.3 Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.4 Multidigrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
ii
6.8 El semigrupo libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
6.9 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9 Bibliografı́a 249
iii
1 Introducción informal a la lógica matemática
En este capı́tulo describiremos, de manera intuitiva, algunos conceptos importantes de la
lógica matemática. Como creador de esta disciplina debemos considerar al filósofo y matemático
alemán del siglo XVII, G. W. Leibniz (1646—1716), pero quien la redescubre y desarrolla es el
matemático inglés G. Boole (1815—1864). Entre los que hicieron un aporte decisivo se encuen-
tran el lógico alemán G. Frege (1848-1925) y el lógico y filósofo norteamericano Ch. S. Peirce
(1839—1914).
De los múltiples usos del lenguaje, los que interesan a la lógica son aquellos que cumplen
una función informativa, esto es, cuando se lo utiliza para suministrar información mediante
oraciones declarativas o para presentar argumentos.
Además, lo que interesa de las oraciones declarativas es su significado.
(i) Oración: Palabra o conjunto de ellas, con sentido completo (plano semántico) y au-
tonomı́a sintáctica (plano sintáctico). No necesita de ningún elemento extraoracional
para completar su significación.
(ii) Oraciones declarativas: Son las oraciones que cumplen una función informativa, es decir,
las que afirman o niegan algo y a las cuales se les puede asignar un valor de verdad
verdadero o falso.
Cuando admitimos la noción de equivalencia entre las oraciones declarativas, a las clases de
oraciones equivalentes las llamaremos proposiciones.1
1
El uso que se le da en Lógica a la palabra `proposición´ no coincide con el que se le da en Gramática. En
Matemática también se utiliza `enunciado´ como sinónimo de `proposición´.
1
Ejemplos
Las oraciones declarativas indicadas en (1) y (2) tienen el mismo significado y por lo tanto
representan a la misma proposición.
Las enunciadas en (3) y (4) representan la misma proposición siempre que aceptemos a la
palabra `detestar´ como sinónimo de la palabra `aborrecer´.
Las enunciadas en (5), . . . ,(8) están referidas a propiedades de los números reales y en
Matemática se acepta que representan a la misma proposición.
Otros ejemplos
(12) En otros planetas del sistema solar hay diversos tipos de seres vivos.
La oración indicada en (9) es una proposición, y más precisamente una proposición falsa.
La oración del ejemplo (10) es interrogativa y no cumple una función informativa, entonces
no puede considerarse ni verdadera ni falsa. Por lo tanto no es una proposición.
En (11) la palabra ella es variable, la oración no es ni verdadera ni falsa ya que ella no
está especificada, luego no es una proposición. La oración de (12) es una proposición ya que es
verdadera o falsa, aunque nosotros no estamos en condiciones de decidir cómo es.
2
Proposiciones simples y compuestas
Proposiciones simples
Ejemplo
Proposiciones compuestas
Ejemplo
Garcı́a ha estudiado,
Las conectivas
Son palabras, frases o expresiones lingüı́sticas que ligan a dos proposiciones llamadas com-
ponentes, y tales que la expresión ası́ obtenida es una proposición cuyo valor de verdad queda
definido en términos de los valores de verdad de sus componentes.
3
Ejemplo
La proposición compuesta que resulta al unir dos proposiciones por la palabra o se denomina
disyunción de dichas proposiciones.
Observemos que en el lenguaje coloquial la palabra o tiene al menos dos significaciones
distintas.
Ejemplos
(i) Los clientes que sean estudiantes universitarios o jubilados serán favorecidos con un 20%
de descuento.
(ii) Juan acepta ser el candidato a intendente por la lista blanca o renuncia al partido.
Los clientes que sean estudiantes universitarios serán favorecidos con un 20% de descuento
o los clientes que sean jubilados serán favorecidos con un 20% de descuento.
En este caso, la palabra o se usa en sentido no excluyente puesto que no se niega la posibili-
dad de descuento a los jubilados que estudien en la universidad. En cambio en (ii), o está usada
en un sentido excluyente ya que, o es el candidato a intendente o renuncia, y no se pueden dar
las dos posibilidades simultáneamente.
En general, es difı́cil determinar el sentido en que está usada la conectiva o.
En Latı́n se usan ‘aut’ y ‘vel’ para el o excluyente y el no excluyente respectivamente.
En Lógica y en Matemática la palabra o se usa siempre en el sentido no excluyente.
Ejemplos
(ii) El gobierno argentino establece un control sobre la caza del zorro colorado, o esas especies
se extinguirán en un futuro muy próximo.
4
(iii) 13 es un número primo, o es divisible por un número distinto de 1 y 13.
En las proposiciones dadas en (i) y (iv) el sentido del o es no excluyente, en cambio en (ii)
y (iii) es excluyente.
Ejemplo
y por consecuente a
A las conectivas que acabamos de ver las llamaremos conectivas binarias porque siempre
ligan a dos proposiciones dando origen a una nueva proposición.
Ahora consideraremos una conectiva unaria, es decir una conectiva que aplicada a una
proposición produce una nueva proposición.
Ejemplo
Si la proposición es
1 es un número par,
5
su negación es
1 no es un número par.
Ejemplo
La negación de
1 es un número par,
Constantes y variables
Hay disciplinas como la Matemática que desarrollan su propio lenguaje coloquial. A veces
se hace necesario distinguir en él dos tipos de términos, las constantes y las variables.
Constantes
Son términos que tienen un significado fijo que permanece invariable en el curso de las
consideraciones. Por ejemplo, en la aritmética intervienen constantes tales como uno (1), cero
(0), suma (+), producto (·), etc.
Variables
Funciones proposicionales
6
x es un número natural,
Ejemplos
x es un número natural,
1
y reemplazamos x por 3 y posteriormente x por obtenemos las proposiciones:
2
3 es un número natural, [proposición verdadera]
1
es un número natural. [proposición falsa]
2
Fórmulas
Ejemplos
(ii) x + y = 9, [fórmula]
7
Funciones designativas
Son aquellas expresiones en las cuales al reemplazar las variables por constantes se trans-
forman en constantes.
Ejemplos
Cuantificadores
(i ) (∀x)(∀y) . . . ,
(ii ) (∃x)(∃y) . . . .
respectivamente.
Ejemplos
Podemos usar variables y cuantificadores para escribir oraciones equivalentes a las anteriores,
del siguiente modo:
8
Estos ejemplos ilustran que existen casos en que si anteponemos cuantificadores a las fun-
ciones proposicionales obtenemos proposiciones, aunque no siempre es ası́.
Ejemplos
Ejemplos
Variables proposicionales
Llamaremos variables proposicionales (v.p.) a los sı́mbolos utilizados para designar a las
proposiciones simples.
Observemos que las variables proposicionales no son variables en el sentido del párrafo
Constantes y variables.
3
Es decir, el sı́mbolo P representa a todos los miembros de la colección de oraciones declarativas que tienen
el mismo significado.
9
Meta-variables
(R4) (de cierre) las únicas f.p. son las determinadas por R1, R2 y R3.
Si p y q son f.p. que designan a ciertas proposiciones del lenguaje coloquial, entonces
p ∧ q, p ∨ q, p → q,
∼p
10
El sol es una estrella,
entonces p ∧ q designa
Tablas de verdad
Ahora bien, como toda proposición es verdadera o falsa, podemos pensar que cualquier f.p.
dada toma el valor de verdad verdadero o el valor de verdad falso.
Consideremos el conjunto IB = {F, V}, donde F y V son sı́mbolos arbitrarios para designar
las nociones falso y verdadero respectivamente. Entonces, dada una f.p. p tendrá sentido hablar
del valor de verdad de p o de la valuación de p, que notaremos con v(p), y escribiremos v(p) = F
ó v(p) = V, si p designa una proposición falsa o verdadera, respectivamente.
En este apartado indicaremos de qué modo se puede definir el valor de verdad de una f.p.
a partir de los valores de verdad de las v.p. que la constituyen.
En cada caso, lo haremos por medio de una tabla llamada tabla de verdad asociada a la f.p..
El producto lógico
Dadas dos proposiciones parece adecuado considerar que la conjunción de ellas sea verdadera
cuando ambas lo sean. Luego si p, q ∈ X, la valuación de p ∧ q queda definida a partir de la
valuación de p y la valuación de q según se indica en la tabla 1.2.1:
La tabla anterior nos permite definir sobre IB, lo que llamaremos producto lógico y notaremos
con ·, del siguiente modo:
11
· F V
F F F tabla 1.2.2
V F V
La suma lógica
Ella induce una operación binaria sobre IB, lo que llamaremos suma lógica y que notaremos
con +, de la siguiente manera:
+ F V
F F V tabla 1.2.4
V V V
Ejemplos
(i) En el lenguaje coloquial unimos dos proposiciones simples con la letra o cuando ellas
tienen alguna relación; jamás podrı́amos considerar la siguiente proposición:
12
(ii) En el lenguaje coloquial el o se halla influı́do de ciertos factores de carácter sicológico.
En efecto
La implicación lógica
si P , entonces Q,
P implica Q,
de P se deduce Q,
Q es consecuencia de P .
13
Observemos que, como en los casos anteriores, una vez construı́da la tabla 1.2.5, podremos
definir sobre IB, lo que llamaremos implicación lógica, y que designaremos con →, de modo tal
que se verifique:
(i) F → F,
(ii) F → V,
(iii) V → F,
(iv) V → V.
(i) F → F = V,
(ii) F → V = V,
(iii) V → F = F,
(iv) V → V = V.
14
(i) Es verdadero (2do. miembro) que de algo falso (antecedente) se puede deducir algo falso
(consecuente).
(ii) Es verdadero (2do. miembro)que de algo falso (antecedente) se puede deducir algo ver-
dadero (consecuente).
(iii) Es falso (2do. miembro)que de algo verdadero (antecedente) se puede deducir algo falso
(consecuente).
(iv) Es verdadero (2do. miembro) que de algo verdadero (antecedente) se puede deducir algo
verdadero (consecuente).
(i) De
2 = 0. [proposición falsa]
(ii) De
1 = 1. [proposición verdadera]
Por otra parte, dado que la Matemática no es una ciencia contradictoria, jamás probaremos
a partir de una hipótesis verdadera una conclusión falsa. Esto motiva la definición (iii).
Finalmente, resulta adecuado considerar como verdaderas las conclusiones obtenidas de
hipótesis verdaderas lo que justifica la definición de (iv).
Resumiendo, la tabla 1.2.5 se completa como sigue:
15
v(p) v(q) v(p → q)
F F V
F V V
V F F tabla 1.2.7
V V V
Luego, la tabla 1.2.7 nos permite definir la implicación lógica del siguiente modo:
→ F V
F V V tabla 1.2.8
V F V
La negación lógica
Dada una proposición, su negación será verdadera si ella es falsa y será falsa si ella es
verdadera. Luego, la tabla de verdad es:
v(p) v(∼ p)
F V tabla 1.2.9
V F
En IB queda definida la llamada negación lógica, que notaremos con −, como sigue:
x −x
F V tabla 1.2.10
V F
Ejemplos
Para simplificar, cuando no haya lugar a confusión al calcular las tablas de verdad, escribire-
mos p en lugar v(p).
(i) p ∧ (∼ q)
16
p q ∼q p ∧ (∼ q)
F F V F
F V F F
V F V V
V V F F
(ii) p → (q ∨ r)
p q r q∨r p → (q ∨ r)
F F F F V
F F V V V
F V F V V
F V V V V
V F F F F
V F V V V
V V F V V
V V V V V
El álgebra de prueba
Ejemplos
17
(i) (p → q) → ((p → r) → (p → (q ∧ r))).
α = (p → r) → (p → (q ∧ r)),
β = (p → q) → ((p → r) → (p → (q ∧ r))).
(ii) p ∧ ∼ p
p ∼ p p∧ ∼ p
0 1 0
1 0 0
Tautologı́as importantes
(2) (p ∧ q) → p,
(3) p → (p ∨ q),
18
(4) (p → q) → ((q → r) → (p → r)), [ley del silogismo hipotético]
(1) de p se deduce p,
(2) p y q implican p,
p y q implican q,
(3) de p se deduce p o q,
de q se deduce p o q,
(6) p o no p,
19
Ejemplos
(i) p → q ≈ ∼ p ∨ q,
p q ∼p p→q ∼p∨q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1
(ii) p ∨ q ≈ (p → q) → q,
p q p→q p∨q (p → q) → q
0 0 1 0 0
0 1 1 1 1
1 0 0 1 1
1 1 1 1 1
Equivalencias importantes
(1) p ∨ q ≈ q ∨ p,
(2) p ∧ q ≈ q ∧ p,
(3) p ∨ (q ∨ r) ≈ (p ∨ q) ∨ r,
(4) p ∧ (q ∧ r) ≈ (p ∧ q) ∧ r,
(5) p ∧ (q ∨ r) ≈ (p ∧ q) ∨ (p ∧ r),
(6) p ∨ (q ∧ r) ≈ (p ∨ q) ∧ (p ∨ r),
(7) p ∧ q ≈ ∼ (∼ p ∨ ∼ q),
(8) p ∨ q ≈ ∼ (∼ p ∧ ∼ q),
(9) p ≈ p ∨ p,
(10) p ≈ p ∧ p.
20
Como consecuencia de (3) de ahora en más escribiremos p∨q∨r para indicar indistintamente
p ∨ (q ∨ r) ó (p ∨ q) ∨ r. Análogamente, de (4) escribiremos p ∧ q ∧ r para indicar p ∧ (q ∧ r)
ó (p ∧ q) ∧ r.
Ejemplos
(i) p1 , p2 , . . . , pn , ∴ p,
(ii) p1 ,
p2 ,
..
.
pn ,
∴ p.
Ejemplos
p → q,
p,
∴ q.
21
(ii) modus tollens:
p,
∼ q →∼ p,
∴ q.
Validez de una forma argumentativa
Ejemplos
(i) p,
∼ q → p,
∴ q.
p q ∼q ∼q→p p ∼q→p q
0 0 1 0 0 0 0
0 1 0 1 0 1 1
1 0 1 1 1 1 0
1 1 0 1 1 1 1
(ii) p,
∼ q →∼ p,
∴ q.
p q ∼q ∼ p ∼ q →∼ p p ∼ q →∼ p q
0 0 1 1 1 0 1 0
0 1 0 1 1 0 1 1
1 0 1 0 0 1 0 0
1 1 0 0 1 1 1 1
22
1.7 Consecuencias semánticas
Si una forma argumentativa
p1 , p2 , . . . , pn , ∴ p
{p1 , p2 , . . . , pn } |= p.
Teoremas semánticos
(i) {p1 , p2 , . . . , pn } |= p,
(ii) |= (p1 ∧ p2 ∧ . . . ∧ pn ) → p.
Ejemplo
23
p q r p→q q→r p→r
0 0 0 1 1 1
0 0 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1
1 0 0 0 1 0
1 0 1 0 1 1
1 1 0 1 0 0
1 1 1 1 1 1
Llamaremos forma normal disyuntiva (f.n.d.) a toda f.p. α = α(x1 , x2 , . . . , xn ) tal que
m n
α= x∗ij , donde x∗ij = xt ó x∗ij = ∼ xt .
i=1 j=1
Paso 1
Paso 2
Hallamos todas las n—uplas t = (t1 , . . . , tn ) de las valuaciones de las variables, para
cuales α toma el valor 1.
24
Paso 3
Paso 4
Ejemplo
p q r ∼q ∼q∧r p → (∼ q ∧ r)
0 0 0 1 0 1
0 0 1 1 1 1
0 1 0 0 0 1
0 1 1 0 0 1
1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 0
(∼ p ∧ ∼ q ∧ ∼ r) ∨ (∼ p ∧ ∼ q ∧ r) ∨ (∼ p ∧ q ∧ ∼ r) ∨ (∼ p ∧ q ∧ r) ∨ (p ∧ ∼ q ∧ r).
25
m n
x∗ij , donde x∗ij = xt ó x∗ij = ∼ xt .
i=1 j=1
Paso 1
Paso 2
Hallamos todas las n—uplas t = (t1 , . . . , tn ) de las valuaciones de las variables, para
cuales α toma el valor 0.
Paso 3
Paso 4
Ejemplo
Hallar la f.n.c. de (∼ p → q) ∧ r.
p q r ∼p ∼p→q (∼ p → q) ∧ r
0 0 0 1 0 0
0 0 1 1 0 0
0 1 0 1 1 0
0 1 1 1 1 1
1 0 0 0 1 0
1 0 1 0 1 1
1 1 0 0 1 0
1 1 1 0 1 1
26
t1 = (0, 0, 0), αt1 = p ∨ q ∨ r,
(p ∨ q ∨ r) ∧ (p ∨ q ∨ ∼ r) ∧ (p ∨ ∼ q ∨ r) ∧ (∼ p ∨ q ∨ r) ∧ (∼ p ∨ ∼ q ∨ r).
1.9 Ejercicios
E 1.9.1
(a) En la Argentina no se han producido epidemias de viruela en los últimos diez años.
(b) Juan no está bien informado o no quiere aceptar las noticias.
(c) Comprendo los puntos de vista de Marta, pero no los comparto.
(d) Si me levanto temprano, tomo el tren de las ocho.
(e) En los dı́as feriados el centro de Bahı́a Blanca permanece desierto.
E 1.9.2
27
(i) x es hermano de Juan.
√
(ii) x2 = |x|.
(iii) 2x2 − 3y + 1.
E 1.9.3
Las funciones proposicionales que aparecen en la aritmética y que sólo contienen una variable
(aunque ésta puede intervenir, como es natural, en varios lugares de la función dada) se pueden
dividir en tres categorı́as:
(c) funciones que se satisfacen para algunos números y no se satisfacen para otros.
(iii) x2 + 2x + 1 = 0.
(iv) x ≤ |x|.
(v) x + 10 = x + 1.
(vi) x + 10 > 1 + x.
E 1.9.4
28
(a) para números cualesquiera x e y, x + y = x,
(b) para un número cualequiera x, existe un número y tal que x + y = x,
(c) existe un número y tal que para todo número x, x + y = x.
Formular las retantes proposiciones y estudiar cuáles de ellas son verdaderas, considerando
como dominio de interpretación al conjunto de los números reales.
E 1.9.5
Indicar en cada caso una proposición del lenguaje coloquial que no contenga cuantificadores ni
variables y con significado equivalente a:
E 1.9.6
Sustituir cada una de las siguientes proposiciones por otra con significado equivalente formulada
con cuantificadores y variables:
E 1.9.7
Escribir las siguiente expresiones en lenguaje simbólico y distinguir variables libres y ligadas:
29
(iv) x · (y + z) = (x · y) + (x · z),
E 1.9.8
¿Qué números reales satisfacen cada una de las siguientes funciones proposicionales?
(d) existen números y y z tales que para todo número x, z < x + y y z > y,
(e) para números cualesquiera x e y, si (x + y)2 = z, entonces x2 + 2xy + y 2 = z,
(f) para números cualesquiera y y z, existe un número x tal que si y < x y z < x,
entonces no es el caso que y + z ≥ x.
Señalar en cada una de las expresiones (a), . . . , (f) cuáles son variables libres y cuáles ligadas. Si
alguna variable es libre, dar ejemplos siempre que sea posible, de números reales que satisfacen y
que no satisfacen las funciones proposicionales. Para aquellas expresiones que son proposiciones,
determinar si son verdaderas o falsas considerando como dominio de interpretación al conjunto
de los números reales.
E 1.9.10
A: 15 es múltiplo de 5,
30
B: 4 es divisible por 2,
C: 9 es divisible por 7,
E 1.9.11
Escribir en lenguaje simbólico e indicar el valor de verdad de cada una de las siguientes proposi-
ciones:
E 1.9.12
Indicar en cada caso, cuál es la forma correcta de negar las siguientes proposiciones:
31
(ii) Llueve o voy al cine.
(iii) 6 es múltiplo de 2 y 3.
E 1.9.13
p q p↔q
0 0 1
0 1 0
1 0 0
1 1 1
Sean r, s, t ∈ F or[X] tales que v(s) = v(r) = 1 y v(t) = 0. Calcular el valor de verdad de
las siguientes f.p.:
E 1.9.14
Construir las tablas de verdad de las siguientes f.p. y clasificarlas en tautologı́as, contradicciones
y contingencias:
(i) ∼ p → (q ∨ ∼ p),
(ii) ((p ∧ q) → p) → q,
32
(iii) (p ∧ q) → ∼ p,
(iv) (∼ p → q) → (∼ q → p),
(v) p∧ ∼ (p ∨ q),
E 1.9.15
Determinar, en cada caso, α, β ∈ F or[X] tales que las siguientes f.p. sean tautologı́as:
(i) ∼ α → α,
(ii) α ∨ β,
(iii) α ∧ (∼ α → β).
E 1.9.16
(i) ∼∼ p, p,
(ii) p ↔ q, (p ∧ q) ∨ (∼ p∧ ∼ q),
(iii) (p ∧ q) → r, p → (q → r),
(iv) p → q, ∼ q →∼ p,
(v) p → q, ∼ p ∨ q,
(vi) ∼ (p ∨ q), ∼ p∧ ∼ q,
(vii) (p → q) → q, p ∨ q,
(viii) p → (q → r), q → (p → r),
(ix) (p → q) ∧ (q → p), (p ∧ q) ∨ (∼ p∧ ∼ q).
E 1.9.17
E 1.9.18
33
Investigar la validez de las siguientes formas argumentativas:
E 1.9.19
Para cada una de las siguientes argumentaciones escribir una forma argumentativa que se
corresponda con ella y determinar si es válida o si es no válida.
(i) Si Marta ha ido al museo, entonces conoce esa famosa escultura. Marta no conoce esa
famosa escultura. Luego, Marta no ha ido al museo.
(ii) Los soldados encontraron cerrado el paso, o si temieron un ataque enemigo, se refugiaron
en las montañas. Pero los soldados no se refugiaron en las montañas. Luego, los soldados
encontraron cerrado el paso o no temieron un ataque enemigo.
(iii) Pedro no fue debidamente defendido o es realmente culpable. Si Carlos fue su abogado,
fue debidamente defendido. Por lo tanto, si Carlos fue su abogado, Pedro es realmente
culpable.
(iv) Si Carlos aumenta de peso, entonces abusó de dulces o abusó de pastas. Si Carlos no
abusó de dulces, entonces está mintiendo. Si Carlos está mintiendo y aumenta de peso,
entonces no abusó de pastas. Por lo tanto, Carlos abusó de dulces.
E 1.9.20
34
E 1.9.21
E 1.9.22
(a) (p ∨ q) → ∼ q,
(b) ∼ (p ∧ q) ↔ (p ∨ q),
(c) (p → q) ∨ (p∧ ∼ r).
(a) (p ∨ q) → (∼ q → ∼ p),
(b) (p → q) ∧ r,
(c) p → (q ↔ r).
35
2 Conjuntos
2.1 Introducción
La siguiente es una exposición de la teorı́a de conjuntos de naturaleza intuitiva. Tomaremos
como conceptos primitivos, es decir no definidos, a las nociones de elemento y de conjunto.
También utilizaremos una relación primitiva que notaremos ∈ y que llamaremos relación de
pertenencia.
Habitualmente designaremos a los elementos y a los conjuntos con letras latinas minúsculas
y mayúsculas respectivamente, aunque a veces no es posible o no es conveniente respetar estas
convenciones.
Un conjunto está determinado cuando disponemos de un criterio para establecer si un
elemento pertenece o no a dicho conjunto.
A las fórmulas a ∈ A, a ∈
/ A las leeremos: el elemento a pertenece al conjunto A y el
elemento a no pertenece al conjunto A, respectivamente.
Igualdad de conjuntos
A y B son dos conjuntos que tienen los mismos elementos y por lo tanto deben ser
idénticos.
Representaciones de conjuntos
36
Entonces diremos que el segundo miembro de esta igualdad es una representación por ex-
tensión de E.
Generalizando lo anterior, para designar conjuntos por extensión, con respecto a sus ele-
mentos, tendremos en cuenta las siguientes reglas:
(R1) Los escribiremos separados por comas y encerrados por una llave inicial y otra final.
Es claro que los conjuntos que no tienen un número finito de elementos, a los que llamaremos
conjuntos infinitos, no admiten representaciones por extensión. Sin embargo, en algunos casos
de conjuntos infinitos, es frecuente utilizar representaciones similares a ellas, ası́ por ejemplo se
suele designar al conjunto IN de los números naturales con {1, 2, 3, . . . }.
Si D es el conjunto de los dı́as del año 1994, para representarlo por extensión deberemos
escribir sus 365 elementos, utilizando sı́mbolos de algún tipo, por ejemplo
donde los puntos suspensivos significan que hemos omitido escribir algunos de sus elementos.
La siguiente, es una manera más sencilla de describir a D:
Diremos que el segundo miembro de esta igualdad es una representación por comprensión
de D y la leeremos: D es el conjunto de los elementos x tales que x es dı́a del año 1994.
37
H = {x : x es habitante de la R.A.}.
(C1) Determinaremos una cláusula que notaremos con P y tal que la verifiquen únicamente los
elementos de A.
En general, existe más de una cláusula para definir a un conjunto. En efecto, si consideramos
A = {3, 4, 5, 6, 7}
y las cláusulas
Observemos que existen expresiones lingüı́sticas con apariencia de cláusulas, que no pueden
ser utilizadas como tales. Ası́ por ejemplo,
Por otra parte, hay expresiones de naturaleza subjetiva que no definen a un conjunto; una
de ellas es:
38
S = {x : x es dı́a de la semana}
= {lunes, martes, miércoles, jueves, viernes, sábado, domingo}
= {monday, tuesday, wednesday, thursday, friday, saturday, sunday}
= {lu, ma, mi, ju, vi, sa, do}.
39
(R2) Si A = ∅, dibujaremos una curva cerrada que no se entrecruce, como la de la figura 2.3.1
y representaremos a A con la región sombreada y sin la curva, como la de la figura 2.3.2.
(R3) Si A es un conjunto finito y queremos representar todos sus elementos, para cada uno de
ellos, dibujaremos un punto o una señal cualquiera en la zona que representa a A.
Observación importante
Sea A = ∅ y supongamos que la figura 2.3.2 es un diagrama de dicho conjunto, por R3 todos
los elementos de A están en el interior de la zona acotada, pero no tenemos porqué suponer
que todos los puntos de la misma representan elementos de A.
Más aun, si A es un conjunto finito seguramente hay puntos de dicha zona que no represen-
tan elementos de A.
Ası́ por ejemplo si A = {1, 2, 3, 4, 5}, la figura 2.3.3 será un diagrama de A.
figura 2.3.3
La relación de inclusión
40
(C1) ∅ ⊆ A, para todo conjunto A.
De C2 resulta que para comprobar que A ⊆ B tenemos que ejecutar el siguiente esquema
de trabajo:
Paso 1:
Paso 2:
de la hipótesis
H: x ∈ A,
resulta la tesis
T: x ∈ A.
Nota. Si queremos representar a A por comprensión por medio de la cláusula P y sabemos que
A ⊆ B, entonces en algunos casos por ser conveniente, escribiremos A = {x ∈ B : x verifica P}.
Propiedades de ⊆
Las propiedades que indicaremos a continuación, son las más importantes de la relación ⊆.
Cualquiera sean los conjuntos A, B y C se verifican:
41
(O1) A ⊆ A. [propiedad reflexiva]
Observación
Paso 1:
Verificamos que A ⊆ B.
Paso 2:
Verificamos que B ⊆ A.
Paso 3:
Ejemplos
(i) Los conjuntos A = {4, 5, 7, 10, 24}, B = {5, 10}, C = {3, 10, 24} y D = {1, 4} son tales
que B ⊆ A, C ⊆ A, D ⊆ A.
42
Entonces A = {d,u,r,a,z,n,o}, B = {z,o,r,a}, C = {a,r,o} y se cumple C ⊂ B, B ⊂ A.
En algunos textos se utiliza el sı́mbolo ⊂ para la relación ⊆. Pero no nos parece adecuado.
Ejemplos
La intersección
A ∩ B = {x ∈ R : x ∈ A y x ∈ B}.
x ∈ A ∧ x ∈ B.
Observemos que es aquı́ donde aparece la necesidad de contar con el conjunto vacı́o.
43
La unión
Tenemos ası́ que x ∈ A ∪ B si, y sólo si, x satisface alguna de las tres condiciones siguientes:
x ∈ A ∨ x ∈ B.
A ∪ B = {x ∈ R : x ∈ A ∨ x ∈ B}.
La diferencia
A \ B = {x ∈ R : x ∈ A y x ∈
/ B}.
La complementación
Es frecuente usar también, alguno de los siguientes sı́mbolos para designar al complemento
de A: CR A, CA, A , A. Luego,
A = {x ∈ R : x ∈
/ A}.
La noción de complemento depende del conjunto referencial R elegido, esto es, si variamos
el referencial varı́a el complemento.
44
Ejemplos
A = {1, 2, 5, 6, 7, 9},
B = {1, 3, 4, 5, 9, 10},
C = {2, 7}.
Entonces
A ∩ C = C,
A ∩ B = {1, 5, 9},
A ∪ C = A,
B \ A = {3, 4, 10},
B = {2, 6, 7, 8, 11}.
Entonces
A ∩ B = {l,o},
45
A \ B = {e,i,c},
A ∪ B = {e,i,c,l,o,r},
B \ A = {r},
R \ A = {m,u,a,g,r},
B \ R = ∅.
2.7 Diagramas
Sean A y B conjuntos no vacı́os. Entonces se pueden presentar las siguientes situaciones:
(i) A ⊆ B, B ⊆ A y A ∩ B = ∅,
(ii) A ⊆ B, B ⊆ A y A ∩ B = ∅,
(iii) A ⊆ B y B ⊆ A,
(iv) A ⊆ B y B ⊆ A,
(v) A = B.
La intersección
46
La unión
47
La diferencia
La complementación
48
2.8 Propiedades de las operaciones conjuntistas
Las propiedades fundamentales de las operaciones indicadas anteriormente son:
(P1) A ∩ (B ∩ C) = (A ∩ B) ∩ C, [asociativa]
(P2) A ∩ A = A, [idempotencia]
(P3) A ∩ B = B ∩ A, [conmutativa]
(P4) A ∪ (B ∪ C) = (A ∪ B) ∪ C, [asociativa]
(P5) A ∪ A = A, [idempotencia]
(P6) A ∪ B = B ∪ A, [conmutativa]
(P7) A ∩ (A ∪ B) = A, [absorción]
(P8) A ∪ (A ∩ B) = A, [absorción]
(P11) (A ∩ B) = A ∪ B ,
(A ∪ B) = A ∩ B . [leyes de De Morgan]
Dem.
|A ∪ B| = |A| + |B|.
Luego,
49
|A ∪ B| = |A| + |B| − 0 = |A| + |B| − |A ∩ B|.
= |A \ B| + |B| + |A ∩ B| − |A ∩ B|
2.10 Ejercicios
E 2.10.1
Dados los siguientes conjuntos representados por comprensión, representarlos por extensión:
E 2.10.2
Representar por comprensión, de dos maneras distintas, cada uno de los siguientes conjuntos:
E 2.10.3
Sean A = {∅, {1, 2, 3}, {4}, 4, {5, 6}}, B = {{∅}, {1}, {2}, {3}, {4}, {5}, {6}} y
C = {{∅}, 1, 2, 3, 4, 5, 6}.
50
(a) ¿Es A = B = C? Justificar la respuesta.
∅ ∈ A, ∅ ∈ B, ∅ ∈ C,
∅ ⊆ A, ∅ ⊆ B, ∅ ⊆ C,
{∅} ⊆ A, {∅} ⊆ B, {∅} ⊆ C,
{1, 2, 3} ∈ A, {1, 2, 3} ∈ B, {1, 2, 3} ∈ C,
{{4}} ⊆ A, {{4}} ⊆ B, {{4}} ⊆ C,
4 ∈ A, 4 ∈ B, 4 ∈ C,
{1, 2, 3} ⊆ A, {1, 2, 3} ⊆ B, {1, 2, 3} ⊆ C,
{{∅}, 4} ⊆ A, {{∅}, 4} ⊆ B, {{∅}, 4} ⊆ C.
E 2.10.4
(a) Escribir las operaciones que dan por resultado la zona sombreada.
(i) (A ∩ B) ∪ C,
(ii) (A ∪ B) \ C,
(iii) (A \ B) ∩ C ,
51
(iv) (B ∩ C) ∪ A.
E 2.10.5
E 2.10.6
(a) A ∩ A = A,
(b) A ∩ (A ∪ B) = A,
(c) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
(d) (A ) = A,
(e) (A ∩ B) = A ∪ B ,
(f) A ∪ A = U ,
(g) A ∩ A = ∅,
(h) ∅ = U,
(i) U = ∅.
E 2.10.7
Sea U el conjunto de las letras del alfabeto y sean A = {a, b, c} y C = {a, b, d, e}. Si
|A ∩ B| = 2 y A ∩ B ⊂ B ⊂ C, hallar B.
E 2.10.8
52
Usando un diagrama de Venn determinar, si existen, conjuntos A, B y C que verifiquen
simultáneamente las siguientes condiciones:
(i) A ∩ B = ∅,
(ii) (C ∩ B) \ A = ∅,
(iii) (C ∩ A) \ B = ∅,
(iv) (C ∩ A) ∪ (C ∩ B) ∪ (A ∩ B) = ∅.
E 2.10.9
(a) A B = (A ∪ B) \ (B ∩ A),
(b) A B = B A,
(c) A ∅ = A,
(d) si A B = A C, entonces B = C.
E 2.10.10
(a) si A ∪ B = A ∪ C, entonces B = C,
(b) si A ∩ B = A ∩ C, entonces B = C,
(c) si A B = A C, entonces B = C.
E 2.10.11
Probar que
(a) A \ (B ∪ C) = (A \ B) ∩ (A \ C),
53
(c) (A ∪ B) ∩ B = A si, y sólo si, A ∩ B = ∅,
E 2.10.12
(a) (A ∩ B ) ∪ (B ∩ C),
(b) (A ∪ B ∪ C) ∩ (A ∩ B ∩ C ) ∩ C ,
(c) (((A ∩ B) ∪ C) ∩ B ) ,
(d) ((A ∪ B) ∩ A ) ∪ (B ∩ A) .
E 2.10.13
(b) P(A),
(c) P(B),
(e) P(P(C)).
E 2.10.14
Probar que P(A ∩ B) = P(A) ∩ P(B). ¿Es esta igualdad válida para la unión?. Justificar
la respuesta.
E 2.10.15
54
(b) Los dueños de un video club desean conocer las preferencias de sus 1049 asociados para
los fines de semana. Realizada una encuesta se obtienen los siguientes resultados:
55
3 Relaciones y funciones
Pares ordenados
Diremos que (u, v) es un par ordenado que tiene a u como primera componente y a v como
segunda componente.
D 3.1.1 Dos pares ordenados (a, b) y (c, d) son iguales si, y sólo si, a = c y b = d.
A × B = {(a, b) : a ∈ A, b ∈ B}.
A × B = {(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)}.
56
También se lo puede representar por medio del siguiente diagrama:
3.2 Relaciones
Relaciones binarias
D 3.2.1 Sean A y B dos conjuntos. Llamaremos relación binaria entre los elementos de A y
los de B a cualquier subconjunto R de A × B.
Es claro que ∅ y A × B son relaciones binarias entre los elementos de A y los de B. Repre-
sentaremos con Rel(A, B) al conjunto de las relaciones binarias entre los elementos de A y B.
Entonces
Notaciones útiles
57
(i) Frecuentemente escribiremos aRb (que leeremos: a está en relación R con b) para indicar
que (a, b) ∈ R.
(ii) Si aRb, diremos que b es un correspondiente de a por R, o que b es una imagen directa
de a por R. Al conjunto de todas las imágenes de a por R lo notaremos R(a), esto es
(iii) Si aRb, diremos que a es una preimagen de b, o que a es una imagen inversa de b. Al
conjunto de todas las imágenes inversas de b lo notaremos R−1 (b), esto es
Ejemplo
Sean A = {1, 2, 3, 4}, B = {a, b, c, d} y R = {(1, a), (1, b), (2, c), (3, c), (3, d), (4, d)},
entonces
R(1) = {a, b}, R(2) = {c}, R(3) = {c, d}, R(4) = {d},
R−1 (a) = {1}, R−1 (b) = {1}, R−1 (c) = {2, 3}, R−1 (d) = {3, 4}.
(iii) B es el rango de R,
58
Ejemplo
Sean A = {1, 2, 3, 4}, B = {a, b, c, d} y R = {(1, a), (1, b), (1, c), (3, b)}, entonces
Ejemplo
Si R = {(a, b), (a, c)}, entonces Rop = {(b, a), (c, a)}.
Observemos que el sı́mbolo R2 ◦R1 se lee en forma inversa a como está escrito: R1 compuesto
con R2 .
Ejemplo
Si las relaciones están definidas sobre conjuntos finitos, la forma más sencilla de hallar la
composición es mediante diagramas.
59
R2 ◦ R1 = {(a, x), (b, z)}.
R3 ◦ (R2 ◦ R1 ) = (R3 ◦ R2 ) ◦ R1 .
Toda relación binaria finita puede ser representada por una matriz del siguiente modo:
D 3.2.5 Sea R una relación binaria entre los elementos de los conjuntos A = {a1 , . . . , an } y
B = {b1 , . . . , bm }. Llamaremos matriz asociada a R, y la indicaremos con M (R), a M (R) =
(rij )n×m donde
1 si (ai , bj ) ∈ R
rij = .
0 en caso contrario
Ejemplo
Si A = {a, b, c}, B = {1, 2, 7, 10} y R = {(a, 7), (a, 10), (b, 2), (c, 1), (c, 7)}, entonces
1 2 7 10
a0 0 1 1
M (R) = b 0 1 0 0
.
c 1 0 1 0
(i) La suma de los números de la i—ésima fila representa la cantidad de correspondientes que
tiene ai por R.
60
(iii) A partir de los datos A, B y M (R) podemos obtener R.
(iv) Dada una matriz M = (rij )n×m existe una relación R tal que M = M (R). Dicha relación
no es única.
Ejemplo
1 1 0
Sea M =
0 0 1
entonces R1 = {(a, 1), (a, 2), (b, 3)} y R2 = {(1, a), (1, b), (2, c)} son tales que M(R1 ) =
M (R2 ) pero R1 = R2 .
Este ejemplo muestra que la correspondencia que a cada relación binaria le asigna su matriz
asociada no es inyectiva. Si R1 = R2 con M(R1 ) = M (R2 ), tenemos que los gráficos de dichas
relaciones coinciden (y esto es lo que importa).
n−uplas
Diremos que (a1 , a2 , . . . , an ) es una n−upla que tiene a aj como j−ésima coordenada, j =
1, 2, . . . , n.
Igualdad de n−uplas
D 3.3.1 Dos n−uplas (a1 , a2 , . . . , an ) y (b1 , b2 , . . . , bn ) son iguales si, y sólo si, se verifica
a1 = b1 , a2 = b2 , . . . , an = bn .
61
Producto cartesiano de varios conjuntos
A1 × A2 × · · · × An = {(a1 , a2 , . . . , an ) : a1 ∈ A1 , a2 ∈ A2 , . . . , an ∈ An }.
n
Si A1 = A2 = . . . = An = A, a Ai lo representaremos con An .
i=1
Ejemplo
A1 × A2 × A3 = {(a, x, 1), (a, y, 1), (b, x, 1), (b, y, 1), (c, x, 1), (c, y, 1)}.
Relaciones n−arias
Al conjunto de todas las relaciones n−arias entre los elementos de los conjuntos A1 , A2 ,
. . . , An lo representaremos con Rel(A1 , A2 , . . . , An ). Entonces
n
Rel(A1 , A2 , . . . , An ) = {X : X ⊆ A1 × A2 × · · · × An } = P( Ai ).
i=1
R(X) = An .
Ejemplo
Sean A1 = A2 = {0, 1, 2}, A3 = {1, 3, 4} y X = {(0, 0, 1), (0, 1, 1), (2, 1, 1)}, entonces
62
Dom(X) = {(0, 0), (0, 1), (2, 1)},
Im(X) = {1},
Ejemplo
X ⊆ P1 × P2 × . . . × Pn .
Es decir, podemos considerar que X es una relación entre los conjuntos proyecciones de
la relación.
Si llamamos coordenada superflua a cualquier elemento a ∈ Aj que no es j−ésima coor-
denada de ninguna de las n−uplas de X, y tomamos a X como una relación entre los
elementos de los conjuntos proyecciones en lugar de los conjuntos A1 , A2 , . . . , An , elimi-
naremos las coordenadas superfluas.
Ejemplo
63
X = {(a, 1, 1), (b, 0, 1), (c, 0, 1), (c, 1, 1)}.
3.4 Funciones
Ahora veremos un tipo especial de relación binaria particularmente importante.
Relaciones funcionales
(a, b) ∈ f y (a, c) ∈ f ⇒ b = c.
Ejemplo
f3 = {(c, 2)},
Observaciones
(i) Siendo que las funciones son relaciones especiales, podemos determinar dominio de f ,
imagen de f y rango de f de la manera ya vista.
Si f1 y f3 son las del ejemplo anterior, tenemos que
64
Dom(f1 ) = {a, b, c} = A, Im(f1 ) = {1, 2}, R(f1 ) = B,
Dom(f3 ) = {c}, Im(f3 ) = {2}, R(f3 ) = B.
(ii) Si f es una relación funcional, entonces para cada a ∈ Dom(f ) el conjunto f (a) tiene un
solo elemento.
Para abreviar escribiremos b = f (a) en lugar de f (a) = {b}, y diremos que b es el
correspondiente de a por f .
(iii) Cuando el dominio de f es finito, en lugar de definir a f por extensión se suele hacer por
medio de una tabla.
x f1 (x)
x a b c
a 1 o
f1 (x) 1 1 2
b 1
c 2
(iv) En casi todos los textos se suele escribir: sea y = f (x) una función dada, que es una ex-
presión incorrecta pues una función es un conjunto y f (x) es solamente el correspondiente
de x por f . A pesar de ello cuando nos sea conveniente también la utilizaremos.
Funciones totales
Ejemplo
Sea f = {(a, 1), (b, 2), (c, 2)}, entonces si elegimos A = Dom(f ) = {a, b, c} y B = {1, 2},
tenemos que f : A −→ B.
65
Funciones parciales
Toda función parcial f puede ser transformada en una función total. En efecto, basta
considerar a f como un subconjunto de Dom(f ) × B.
Funciones especiales
f = {(x, b) : x ∈ A, b ∈ B fijo }.
IA = {(x, x) : x ∈ A}.
i = {(x, x) : x ∈ A}.
66
(iv) Funciones proyecciones: Sean A y B conjuntos no vacı́os. Las funciones
p1 : A × B −→ A,
p2 : A × B −→ B,
p1 ((a, b)) = a,
p2 ((a, b)) = b,
pj : A1 × . . . × Aj × . . . × An −→ Aj ,
pj ((a1 , . . . , aj , . . . , an )) = aj .
Todas las funciones que acabamos de definir, desempeñan un papel importante en la teorı́a
de funciones como veremos más adelante.
f −1 (Y ) = {x ∈ A : f (x) ∈ Y }.
67
Ejemplo
y consideremos
entonces tenemos
F : P(A) −→ P(B),
F ∗ : P(B) −→ P(A),
definidas por
respectivamente.
Estas dos funciones se denominan las funciones de conjuntos asociadas a la función f .
68
Ejemplo
x 1 2 3
f (x) a b b
Entonces tenemos
P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A},
Y ∅ {a} {b} B
F ∗ (Y ) ∅ {1} {2, 3} A
69
Propiedades importantes de las funciones de conjuntos asociadas a una función
(i) F (∅) = ∅,
(v) F ∗ (∅) = ∅,
70
(ii) f (x) = g(x), para todo x ∈ Dom(f ).
Para indicar que f es una restricción de g a veces usaremos el sı́mbolo f = g|Dom(f ) que
leeremos f es igual a g restringida a Dom(f ).
Ejemplo
entonces
Como Dom(g) ⊆ Dom(f ) y vale g(x) = f (x) para todo x ∈ Dom(g), tenemos que g =
f |Dom(g) . Es decir, f extiende a g y también decimos que g restringe a f .
Composición de funciones
Ejemplo
71
Algunas propiedades de la composición de funciones
Dem.
(ii) z ∈ Dom(g ◦ f ) ⇔
w = f (z) y (f (z), y) ∈ g ⇔
72
z ∈ {x ∈ Dom(f ) : f (x) ∈ Dom(g)}.
(iii) x ∈ Dom(g ◦ f ) ⇔
x ∈ f −1 (Im(f ) ∩ Dom(g)).
Clasificación de funciones
Funciones inyectivas
(x, y) ∈ f y (z, y) ∈ f ⇒ x = z.
Observaciones
(i) Si nos dan la función por medio de una expresión de la forma y = f (x) y nos piden que
demostremos que f es inyectiva procedemos de la siguiente manera:
73
(5) −a = −b, [(4), def. de valor absoluto y a, b ∈ IR− ]
(6) a = b. [(5)]
Funciones epiyectivas
Im(f ) = B.
Observación
Es claro que siempre vale Im(f ) ⊆ B, luego para probar que f es sobreyectiva, solamente
debemos probar que B ⊆ Im(f ).
Entonces si debemos demostrar que f es sobreyectiva procedemos de la siguiente manera:
(1) suponemos b ∈ B,
74
Funciones biyectivas
Ejemplos
Entonces
f no es inyectiva ni sobreyectiva,
g es inyectiva y no es sobreyectiva,
h es biyectiva.
(i) Si f = {(a, 1), (b, 1), (c, 2)}, entonces f op = {(1, a), (1, b), (2, c)} no es función.
(ii) Si f = {(a, 1), (b, 2), (c, 4)}, entonces f op = {(1, a), (2, b), (4, c)} es función.
75
(ii) f es inyectiva.
Dem.
(i) =⇒ (ii): Caso 1. Si f = ∅ ó f tiene un solo elemento, entonces es inyectiva.
(1) (x, y) ∈ f ,
(2) (z, y) ∈ f .
Luego,
(5) x = z, [(i),(3),(4)]
(1) (x, u) ∈ f op ,
(2) (x, v) ∈ f op .
Luego,
(5) u = v, [(ii),(3),(4)]
76
(ii) f es biyectiva,
(a) g ◦ f = IA ,
(b) f ◦ g = IB .
Dem.
⇒ (ii): Sea
(i) =
(1) b ∈ B,
entonces
Además
(1) f es inyectiva,
(2) f es sobreyectiva.
Luego
77
(5) f op : B −→ A. [(4),(3)]
⇒ (i): Dejaremos como ejercicio probar que Dom(f op ) = B y sólo demostraremos que
(iii) =
f op es función.
(1) (x, y) ∈ f op
(2) (x, z) ∈ f op .
Entonces
(9) y = z, [(8),(iii)(a)]
78
3.5 Producto directo de conjuntos
D 3.5.1 Sea I un conjunto no vacı́o y sea {Ai }i∈I una familia de conjuntos. Llamaremos
producto directo de los conjuntos Ai y lo indicaremos con Ai , al conjunto
i∈I
Ejemplo
Ai = {a, b, x, y, z, t}.
i∈I
Es claro que fj queda determinada por las segundas coordenadas de los pares ordenados, es
decir, podemos reconocerla por medio de la terna (fj (1), fj (2), fj (3)).
Más precisamente, podemos establecer la correspondencia
T 3.5.1 Si {Ai }i∈I es una familia de conjuntos con I = {1, 2, . . . , n}, entonces la función Ψ
que a cada f ∈ Ai le hace corresponder Ψ(f ) = (f (1), f (2), . . . , f (n)) es una biyección de
i∈I
n
Ai en Ai .
i∈I i=1
79
Dem.
(i) Ψ es inyectiva:
Sean f, g ∈ Ai tales que
i∈I
(ii) Ψ es sobreyectiva:
n
Sea (a1 , . . . , an ) ∈ Ai y sea f : I −→ Ai la función tal que para cada i ∈ I,
i=1 i∈I
f (i) = ai . Entonces es fácil verificar que Ψ(f ) = (a1 , . . . , an ).
Este último teorema es muy importante pues nos permite identificar las nociones de producto
directo y producto cartesiano de conjuntos, esto es, podemos trabajar con n—uplas o funciones
según nos sea más cómodo.
Por otra parte, el producto cartesiano se puede definir solamente para un número finito de
conjuntos en cambio el producto directo se puede definir para familias arbitrarias de conjuntos.
Observaciones
80
= =
(i) A≈B si, y sólo si, existe f : A −→ B biyectiva.
= = = = = =
(ii) Es fácil verificar que A≺B si, y sólo si, A B y A≈B .
(iii) Si A y B son conjuntos finitos entonces las siguientes condiciones son equivalentes:
= =
(a) A≈B ,
(b) |A| = |B|, es decir A y B tienen la misma cantidad de elementos.
(iv) En adelante, teniendo en cuenta (iii), dados los conjuntos A y B finitos o no, escribire-
= = =
mos en los casos que no haya lugar a confusión, |A| y |A| = |B| en lugar de A y A≈B
respectivamente. En el caso que A sea finito también seguiremos escribiendo |A| = n para
indicar que A tiene n elementos.
(v) Se puede demostrar que para todo par de conjuntos A y B se verifica una y sólo una de
las tres condiciones siguientes:
(1) |A| ≺ |B|, (2) |A| = |B|, (3) |B| ≺ |A|.
3.7 Ejercicios
E 3.7.1
(a) Calcular A × C, C × A, A × B, B × A, A × B × C y C × A × B.
81
E 3.7.2
(i) A × (B ∩ C) = (A × B) ∩ (A × C),
(ii) A × (B \ C) = (A × B) \ (A × C).
E 3.7.3
E 3.7.4
Sean A = {1, 2, 3} y B = {2, 3, 4, 5}. Dar ejemplos, en cada caso, de dos relaciones binarias
no vacı́as
(a) entre A y B,
(b) entre B y A,
(c) sobre A,
E 3.7.5
(i) |A × B|,
(ii) el número de relaciones binarias entre A y B,
(iii) el número de relaciones binarias sobre A,
(iv) el número de relaciones binarias entre A y B que contienen los pares (1, 2),(2, 3),
(2, 4) y (1, 5),
(v) el número de relaciones binarias entre A y B que contienen exactamente 5 pares
ordenados,
82
(vi) el número de relaciones binarias sobre A que contienen al menos 7 elementos.
(c) Sean A y B conjuntos con |B| = 3. Si existen 4096 relaciones binarias entre A y B, hallar
|A|.
E 3.7.6
(a) xRy si, y sólo si, x divide a y, (2, 4), (2, 5), (2, 6),
(b) xRy si, y sólo si, x > y 2 , (1, 2), (2, 1), (5, 2), (6, 4), (4, 3),
(c) xRy si, y sólo si, 2x + 3y = 10, (5, 0), (2, 2), (3, 1), (1, 3).
E 3.7.7
Para cada una de las siguientes figuras indicar la relación binaria sobre el conjunto IR que
determina la zona marcada:
(a) (b)
(c) (d)
83
E 3.7.8
Sean A = {1, 2, 3, 4}, B = {a, b, c, d, e, f } y C = {x, y, w}. Dadas las siguientes relaciones
indicar, en cada caso, dominio, imagen, rango, P1 y P2 :
(b) S = {(a, 1, x), (c, 1, w), (e, 3, w)}. ¿Es P1 (S) = Dom(S) y P2 (S) = Im(S)?
(c) T = {(x, a), (x, b), (y, b), (x, c), (y, f ), (y, c)},
(d) W = {(x, f, 1), (x, f, 2), (y, e, 3), (w, b, 3)}. ¿Es P3 (W ) = R(W) ?
E 3.7.9
(a) (S op )op = S,
(e) R ◦ (S ∪ T ) = (R ◦ S) ∪ (R ◦ T ),
(f) (R ∪ S) ◦ T = (R ◦ T ) ∪ (S ◦ T ).
E 3.7.10
(a) R = {(1, 2), (3, 4), (1, 8), (2, 9), (2, 2)},
84
E 3.7.11
E 3.7.12
(a) Hallar una matriz asociada a las relaciones R y T del ejercicio 3.7.8. ¿Qué interpretación
puede darse a la suma de los números de una fila? ¿Y a los de una columna?
E 3.7.13
(iii) (iv)
85
(v)
(ix) A = {a, b, c, d}, B = {1, 2, 3}, (x) A = {a, b}, B = {1, 2, 3},
(xi) A = [a, b] ⊆ IR, B = [c, d] ⊆ IR, (xii) A = [0, c] ⊆ IR, B = [0, b] ⊆ IR,
86
(b) dominio e imagen de cada una de las funciones,
E 3.7.14
E 3.7.15
Hallar, en los casos posibles, una matriz asociada a las funciones del ejercicio 3.7.13 ¿Qué
caracterı́sticas especiales tiene la matriz asociada a una relación cuando ésta es funcional?
E 3.7.16
(a)
x a b c d e s g
f (x) 1 1 1 2 2 1 3
87
X = {a, g}, Y = {1, 5}.
E 3.7.17
E 3.7.18
88
x
(d) A = B = IN, f es la función parcial de A en B definida por f (x) =
2
x
y g : IN −→ Q,
I g(x) = .
2
E 3.7.19
Sean Y = {(0, y) : y ∈ IN} y f : ZZ×IN −→ ZZ tal que f ((x, y)) = x+y. Si p2 : ZZ×IN −→ IN
es la segunda proyección, probar que p2 |Y es una restricción de f .
E 3.7.20
x 1 2 3 4 5 6
.
g(x) 7 6 9 7 8 9
Hallar g ◦ f y f ◦ g.
(i) f1 ◦ f2 , (ii) f2 ◦ f1 ,
(iii) f3 ◦ f1 , (iv) f1 ◦ f3 ,
(v) f5 ◦ f4 , (vi) f1 ◦ f5 ,
(vii) f5 ◦ f3 , (viii) f3 ◦ f4 ,
(ix) f6 ◦ f7 , (x) f5 ◦ f7 .
89
√
Determinar, si es posible, (f5 ◦ f7 )( 11) y (f5 ◦ f7 )(3).
E 3.7.21
Clasificar las funciones del ejercicio 3.7.13, inciso (c) en inyectivas, epiyectivas y/o biyectivas.
E 3.7.22
(a) Sean S = {a, b, c, d} y T = {x, y, z}. Hallar en cada caso, si es posible, una función
f : S −→ T tal que
(i) f : IN × Q
I −→ Q
I epiyectiva,
(ii) f : ZZ −→ Q
I inyectiva,
(iii) total epiyectiva, del conjunto de los números naturales pares en el conjunto de los
números naturales múltiplos de 3.
E 3.7.23
Hallar una restricción biyectiva de cada una de las siguientes funciones reales de variable
real:
1
(a) f (x) = ,
x2
(b) f (x) = 2x2 ,
E 3.7.24
f1 : IR −→ IR, f1 (x) = 2x + 1,
90
f2 = {(x, y) : x ∈ IN ∪ {0}, y = 2x + 1},
(b) Calcular, cuando sea posible, la función inversa, indicando dominio e imagen de la misma.
E 3.7.25
Sean f : A −→ B y g : B −→ C.
91
4 Multigrafos y multidigrafos
Muchas situaciones de la vida real pueden ser esquematizadas por medio de diagramas
construı́dos por puntos (vértices o nodos) y lı́neas que conectan algunos pares de vértices,
eventualmente alguna lı́nea puede unir un vértice consigo mismo.
Estos esquemas, que facilitan la comprensión del problema a resolver, aparecen frecuente-
mente en disciplinas dispares y bajo nombres diversos, a saber: redes (en ingenierı́a, economı́a),
sociogramas (en sicologı́a), organigramas (en economı́a y planificación), diagramas de flujo (en
programación).
La teorı́a que se ocupa del estudio de estos diagramas se conoce con el nombre de Teorı́a de
Grafos.
En esta Teorı́a se estudian dos tipos de nociones: dirigidas u orientadas y no dirigidas.
Nosotros comenzaremos por esta última.
Consideremos por ejemplo un mapa de ciudades y rutas que unen dichas ciudades.
Ciudades: A, B, C, D, E, rutas: a, b, c, d.
De este diagrama podemos obtener cierta información. Por ejemplo:
4.1 Multigrafos
La noción matemática con que se pueden abordar este tipo de problemas es la siguiente:
92
(ii) un conjunto A, disjunto con V , cuyos elementos llamaremos aristas,
Ejemplo
x a b c d
ϕ(x) {1, 2} {1, 2} {2, 3} {3}
Los vértices se representan por puntos y las aristas por lı́neas continuas que unen dichos
puntos. Como no se especifica la forma de la lı́nea podrı́amos utilizar
93
Observemos que dos aristas pueden intersectarse en puntos que no son vértices, por ejemplo
no es vértice.
Nociones elementales
x a1 a2 a3 a4 a5 a6
ϕ(x) {1, 2} {1, 2} {2, 4} {1, 3} {3, 4} {4}
D 4.1.2 Dos vértices son adyacentes si son extremos de una misma arista.
1 y 2 son adyacentes,
2 y 3 no lo son,
D 4.1.3 Una arista que une un vértice consigo mismo se denomina un bucle.
a6 es un bucle.
D 4.1.4 Se llama grado de un vértice v y se nota gr(v) al número de aristas que se apoyan en
él.
94
Adoptaremos la siguiente convención: los bucles cuentan doble.
gr(4) = 4, gr(5) = 0.
5 es vértice aislado.
D 4.1.9 Un grafo simple se dice completo si cualquier par de vértices distintos son adyacentes.
D 4.1.10 Una cadena entre v1 y vk es una sucesión de vértices y aristas del tipo
v1 a1 v2 a2 · · · vk−1 ak−1 vk ,
donde para cada i, ai es la arista de extremos vi , vi+1 .
c1 : 1 a4 3 a5 4 a6 4 a3 2,
c2 : 1 a4 3 a5 4 a5 3 a4 1,
95
c3 : 1 a1 2 a2 1,
c4 : 1 a1 2 a3 4 a3 2 a2 1.
D 4.1.11 Llamaremos longitud de una cadena al número de aristas que intervienen en ella,
contando cada arista tantas veces como figure en la sucesión que la define.
long(c1 ) = 4,
long(c2 ) = 4.
D 4.1.12 Llamaremos ciclo a toda cadena que comienza y termina en un mismo vértice v, sin
aristas ni vértices repetidos excepto v (en los extremos).
1 a1 2 a2 1,
1 a1 2 a3 4 a5 3 a4 1.
Muchas veces deseamos que los vértices de un multigrafo G lleven cierta información, por
ejemplo si se trata de un mapa de rutas, los nombres de las ciudades. En este caso diremos que
G es un multigrafo etiquetado.
Otras veces podemos necesitar adosar cierta información a las aristas, por ejemplo la dis-
tancia entre dos ciudades, en este caso diremos que G es un multigrafo valuado.
96
Submultigrafos
(i) V ⊆ V ,
(ii) A ⊆ A,
(iii) ϕ = ϕ|AI .
Ejemplos
un submultigrafo de G es
Submultigrafos cubrientes
97
Ejemplos
Ejemplos
Hemos dicho que la mayor ventaja de los multigrafos es la representación visual de la informa-
ción, sin embargo para utilizar la computadora debemos representar esta información de otras
formas. Consideraremos dos maneras distintas de hacerlo:
98
(i) la matriz de adyacencia,
Matriz de adyacencia
Ejemplo
Sea G
entonces,
1 2 3
1 0 2 1
M (G) = 2
2 0 1 .
3 1 1 1
T 4.1.1 Sean G un multigrafo con n vértices, M(G) = (aij )n×n su matriz de adyacencia y
M 2 (G) = (bij )n×n . Entonces bij es el número de cadenas de longitud 2 entre el vértice vi y el
vj .
Dem. Sabemos que bij = ai1 a1j + ai2 a2j + · · · + ain anj , 1 ≤ i, j ≤ n. Si consideramos un
término cualquiera de esta suma, por ejemplo ai1 · a1j , se pueden presentar los siguientes casos:
99
(i.1) ai1 = 0, es decir, no hay ninguna arista de extremos vi , v1 , ó
(i.2) a1j = 0, es decir, no hay ninguna arista de extremos v1 , vj .
Luego, no puede haber ninguna cadena de longitud 2 entre vi y vj pasando por v1 .
(ii) ai1 · a1j = 0, entonces tendremos una situación como la indicada en la siguiente figura:
Si consideramos una arista fija que une vi con v1 , a partir de ella tenemos a1j cadenas de
longitud 2 que unen vi con vj pasando por v1 .
Reemplazando esta arista por otra arista fija tenemos nuevamente a1j cadenas de longitud
2 entre vi y vj pasando por v1 .
Repitiendo el proceso ai1 veces obtenemos ai1 · a1j cadenas de longitud 2 entre vi y vj
pasando por v1 .
De manera análoga se prueba que ait · atj es el número de cadenas de longitud 2 entre vi
y vj pasando por vt . Luego bij es el número total de cadenas de longitud 2 entre vi y
vj .
Ejemplo
Sea G
entonces
1 2 3
1 0 1 0 1 0 2
M (G) = 2
1 0 2 y M 2 (G) = 0 5 0 .
3 0 2 0 2 0 4
100
En particular, hay cinco cadenas de longitud 2 que unen el vértice 2 con sı́ mismo, que son:
2 b 3 b 2,
2 b 3 c 2,
2 c 3 c 2,
2 a 1 a 2,
2 c 3 b 2.
T 4.1.2 Sean G un multigrafo con n vértices, M(G) = (aij )n×n su matriz de adyacencia y
M m (G) = (dij )n×n . Entonces dij es el número de cadenas de longitud m entre el vértice vi y el
vj .
Lista de adyacencia
Existe un tipo de multigrafos G para el cual la matriz de adyacencia es rala, es decir contiene
muchos ceros y es el caso en que G tiene pocas aristas. De todas maneras si G tiene n vértices,
2
para informar M (G) a la máquina debemos introducir n 2+ n números.
Este hecho nos conduce a buscar un procedimiento donde no haya que informar los ceros.
El método más eficiente es el llamado lista de adyacencia de un multigrafo y consiste en lo
siguiente:
(i) hacemos una lista con todos los vértices del multigrafo,
(ii) para cada vértice indicamos todos los vértices adyacentes a él, colocándose un punto al
finalizar la lista de cada vértice.
Ejemplo
Dado el multigrafo G
101
la lista de adyacencia de G es
4.2 Arboles
Hay un tipo de grafos, llamados árboles, de particular importancia en computación. Ellos
son usados por ejemplo:
(ii) en estructura de datos para la representación de archivos. Allı́ se emplean los llamados
árboles de búsqueda.
Ejemplos
102
En computación, los de mayor aplicación son los árboles con raı́z, es decir árboles en los
cuales hay un vértice distinguido r que se denomina la raı́z del árbol.
Es usual tomar como raı́z al vértice que se encuentra en la parte superior del dibujo.
(2) si un árbol T tiene más de un vértice, entonces un único vértice r es la raı́z del árbol, y
los vértices r1 , r2 , . . . , rt unidos a r por una única arista son raı́ces de árboles disjuntos.
Los vértices r1 , r2 , . . . , rt se denominan los hijos de r y r se llama el padre de r1 , r2 , . . . , rt .
Como un árbol con raı́z es un grafo conexo, existe siempre una cadena que une la raı́z con
cualquier vértice del árbol y como es acı́clico dicha cadena es única.
Esto nos permite introducir la siguiente noción:
103
D 4.2.2 La profundidad de un vértice v en un árbol con raı́z r, que notaremos pr(v), es la
longitud de la cadena que une v con r. Aceptaremos que pr(r) = 0.
D 4.2.3 Se denomina altura de un árbol T con raı́z, y la notaremos h(T ), al máximo de las
profundidades de los vértices.
Ejemplo
D 4.2.4 Se denomina hoja a todo vértice de T sin hijos, en caso contrario, diremos que es un
vértice interno.
Como el árbol es finito este proceso finaliza y el vértice en el que para, es una hoja.
104
Arbol cubriente minimal
Un problema que se presenta en el diseño de redes es como conectar todos los vértices
eficientemente, donde los vértices pueden ser computadoras, teléfonos, etc. Un árbol cubriente
minimal puede proveernos una solución económica.
(i) se elige un vértice arbitrario de G como primer elemento de un conjunto que notaremos
IN ,
(iii) se repite el paso (ii) hasta que |IN | = n, esto es, hasta que todos los vértices de G estén
en el conjunto IN .
Observemos que en (ii) puede haber más de un vértice en las condiciones pedidas, de donde
resulta que el árbol cubriente minimal hallado no es único. Lo que es única es la valuación
mı́nima.
Ejemplo
105
En este caso IN = {d, b, e, a, h, c, f, g} y el árbol cubriente minimal correspondiente es
Recorrido de árboles
Indicaremos tres algoritmos muy útiles para recorrer un árbol, ellos nos permitirán recorrerlo
en pre—orden, orden simétrico y post—orden, respectivamente.
En estos métodos es conveniente emplear la definición recursiva de árbol con raı́z, donde de
la raı́z parten las aristas que sostienen las raı́ces de los subárboles.
Sea T un árbol con raı́z r, tal que todos los subárboles de T están etiquetados de izquierda
a derecha con T1 , T2 , . . . , Tt .
Pre—orden
Si lo recorremos en pre—orden, la raı́z del árbol es visitada primero y luego los subárboles
106
son procesados de izquierda a derecha en pre—orden.
Algoritmo
(1) escribir r,
Orden simétrico
Algoritmo
(2) escribir r,
Post—orden
En este caso la raı́z es visitada al final, después que todos los subárboles han sido procesados
de izquierda a derecha en post—orden.
Algoritmo
(2) escribir r.
107
Ejemplo
Si consideramos el árbol T
La lista de vértices en
Ejemplo
D 4.3.2 Un árbol binario se dice lleno cuando todos los vértices internos tienen dos hijos y
todas las hojas tienen la misma profundidad.
108
Ejemplo
Aplicaciones
(R4) (de cierre) las únicas f.p. son las determinadas por R1, R2 y R3.
Entonces, cualquier p ∈ F or[X] puede representarse por medio de un árbol binario etique-
tado del siguiente modo:
Paso 1:
109
Paso 2:
Ejemplos
(1) α = (x → y) → ((x ∨ y) ∧ z)
(2) β = x →∼ y
(ii) pre—orden,
(1) →→ xy ∧ ∨xyz,
(2) → x ∼ y,
(iii) post—orden,
110
(1) xy → xy ∨ z∧ →,
(2) xy ∼→.
Es decir,
(a) en (i) obtenemos la expresión de partida, donde los paréntesis se colocan al terminar de
procesar cada subárbol. Esta manera de escribir a las fórmulas se denomina notación
infija,
(b) en (ii) los sı́mbolos de las operaciones preceden a los operandos. Esta manera de escribir
a las fórmulas se denomina notación polaca a derecha o prefija,
(c) en (iii) los sı́mbolos de las operaciones se escriben a continuación de los operandos. Esta
manera de escribir a las fórmulas se denomina notación polaca a izquierda o postfija.
Observemos que ni la notación prefija ni la postfija requieren paréntesis, luego estas nota-
ciones son más eficientes, aunque menos familiares que la infija. Los compiladores a menudo
cambian la notación infija en los programas de computación por la prefija o la postfija para
hacer más eficiente el proceso.
4.4 Multidigrafos
Antes de indicar la definición de multidigrafo veamos un ejemplo de tal noción. Considere-
mos el diagrama de flujo correspondiente a un programa de computación que lee una sucesión
de enteros no negativos, imprime aquellos enteros mayores que 7 y para cuando ingresa como
dato a 0.
111
−
→
D 4.4.1 Llamaremos multidigrafo G a una terna (V, A, ϕ) formada por
(i) un conjunto no vacı́o V , cuyos elementos denominaremos vértices o nodos,
(iii) una función ϕ : A −→ V × V tal que ϕ(a) = (v1 , v2 ), v1 se llama vértice inicial u origen
y v2 se denomina vértice final o extremo del arco a.
Ejemplo
−
→
Sea G = (V, A, ϕ), donde V = {1, 2, 3, 4} y A = {a, b, c, d, e, f, g} y ϕ está dada por la tabla
x a b c d e f g
ϕ(x) (1, 1) (1, 2) (4, 3) (3, 3) (1, 2) (2, 4) (3, 4)
112
Nociones elementales
D 4.4.2 Llamaremos grado positivo (negativo) de un vértice v, y lo denotaremos con gr+ (v)
(gr− (v)), al número de arcos con origen (extremo) en v.
v1 a1 v2 a2 . . . vk−1 ak−1 vk ,
En el ejemplo anterior,
c1 : 2 a2 4 a3 3 a5 3,
c2 : 4 a3 3 a4 4 a3 3,
c3 : 1 a1 2.
113
D 4.4.8 Llamaremos longitud de un camino al número de arcos que intervienen en él, contando
cada arco tantas veces como figure en la sucesión que lo define.
En el ejemplo anterior,
long(c1 ) = 3, long(c3 ) = 1.
−
→
D 4.4.9 Diremos que el vértice vk es alcanzable desde vj , vk = vj si en G existe un camino
de vj a vk .
En el ejemplo anterior,
3 es alcanzable desde 2,
2 es alcanzable desde 1.
D 4.4.10 Llamaremos circuito a todo camino que comienza y termina en un mismo vértice v
sin arcos y sin vértices repetidos excepto v (en los extremos).
En el ejemplo anterior,
3 a5 3,
4 a3 3 a4 4.
−
→ −
→
D 4.4.11 Dado un multidigrafo G , llamaremos multigrafo subyacente o soporte de G , al que
−
→
se obtiene a partir de G suprimiendo las orientaciones.
D 4.4.13 Un multidigrafo es fuertemente conexo, si todo par de vértices distintos puede unirse
por un camino.
114
−
→
El multidigrafo G no es fuertemente conexo pues no hay un camino de 2 a 1.
Las nociones de submultidigrafos, submultidigrafos cubrientes e inducidos se definen de
manera análoga al caso no dirigido.
Ejemplos
−
→
(i) G1 y G2 son submultidigrafos cubrientes de G .
−
→ −
→
(ii) G 3 es inducido por {3, 4} y G 4 es inducido por {1, 2, 4}.
De manera análoga a lo visto para multigrafos, indicaremos dos formas distintas de informar
un multidigrafo a una computadora, por medio de
Matriz de precedencia
−→ −
→
Sea G un multidigrafo con n vértices v1 , v2 , . . . , vn . La matriz de precedencia de G es
−→
la matriz M ( G ) = (aij )n×n , donde aij es el número de arcos con origen vi y extremo vj ,
1 ≤ i, j ≤ n.
115
Ejemplo
1 2 3
1 0 1 2
−→
M ( G ) = 2
0 0 1
3 0 1 1
−→ −
→
T 4.4.1 Sean G un multidigrafo con n vértices, M( G ) = (aij )n×n su matriz de precedencia,
−→
m ∈ IN y M m ( G ) = (dij )n×n . Entonces dij es el número de caminos de longitud m del vértice
vi al vj .
Ejemplo
−
→
Si G es el multidigrafo del ejemplo anterior, entonces
0 2 3
2 −
→
M (G) = 0 1 1
0 1 2
1 a 2 d 3,
1 b 3 f 3,
1 c 3 f 3.
Un problema que se presenta con frecuencia es, dado un multidigrafo, saber si un vértice
puede ser alcanzado o no desde otro. Recordemos que un vértice vj es alcanzable desde vi , vi =
−
→ −
→
vj , si existe algún camino de vi a vj . Si consideramos la matriz M( G ) y calculamos M 2 ( G ),
−
→
M 3 ( G ), . . . , entonces para que haya cualquier camino de vi a vj el lugar ij de alguna de estas
matrices debe ser no nulo.
116
−
→
Se puede demostrar que en un multidigrafo G con m vértices, cualquier camino que no
tenga vértices repetidos puede tener a lo sumo m − 1 arcos (y m vértices) antes que un vértice
se repita. Además, en todo camino de longitud mayor que m − 1, cualquier sección entre dos
vértices repetidos es un circuito y por lo tanto puede eliminarse, luego la longitud del camino
disminuye. Entonces si existe un camino desde vi a vj deberá ser de longitud a lo sumo m − 1.
−
→ −→ −→ −→
Luego, sólo debemos calcular M ( G ), M 2 ( G ), M 3 ( G ), . . . , M m−1 ( G ), para decidir si vi es
alcanzable desde vj .
Otra manera más eficiente de hacerlo, pues se ocupa menos lugar de memoria, consiste en
calcular las matrices:
−→ −→ −→ −→
M ( G ), M 2 ( G ), M 3 ( G ), . . . , M m−1 ( G )
Lista de precedencia
Ejemplo
4.5 Ejercicios
E 4.5.1
Suponiendo que
117
A habla español, francés e inglés,
D habla francés,
E 4.5.2
x a b c d e f g
ϕ1 (x) {1, 2} {1, 4} {1} {1, 3} {2, 4} {4, 3} {2, 3}
x a b c d e f g
ϕ2 (x) {1, 2} {1, 4} {2, 4} {2, 3} {2, 3} {4, 5} {4, 5}
E 4.5.3
Dado el multigrafo G
118
(i) hallar, en cada caso, el multigrafo inducido por cada uno de los siguientes conjuntos de
vértices:
(iii) hallar la suma de los grados de todos los vértices de G y verificar que dicha suma es dos
veces el número de aristas de G.
E 4.5.4
E 4.5.5
119
E 4.5.6
E 4.5.7
(ii) Idem inciso (i), sabiendo además que tiene 6 vértices aislados.
(iii) Un multigrafo donde todos los vértices tienen el mismo grado se dice regular. ¿Existen
multigrafos regulares con 10 aristas en el que cada vértice tiene grado 4?. ¿Existen
multigrafos regulares con 15 aristas en el que cada vértice tiene grado 4?. En caso de ser
posible, dar ejemplos.
E 4.5.8
120
Determinar su raı́z y su altura. ¿Es binario lleno?. ¿Cuál es el hijo izquierdo de 9?. ¿Qué
profundidad tiene 4?
(ii) Hallar un árbol binario de altura 4 con cuatro hojas, una de ellas de profundidad 2, otra
de profundidad 3 y tal que su raı́z no tenga hijo derecho.
E 4.5.9
Hallar dos árboles minimales cubrientes para cada uno de los siguientes grafos:
E 4.5.10
Escribir la lista de vértices en preorden, orden simétrico y post-orden para cada uno de los
siguientes árboles:
121
E 4.5.11
Hallar la fórmula asociada a cada uno de los siguientes árboles binarios en notación prefija,
infija y post-fija:
E 4.5.12
(ii) infija.
(a) · + · 2 x y t,
(b) → ∧ → → p q ∼ ∼ r ∼ s ↓ t r,
(c) x y · z t · + x y + ·,
122
(d) p q r ∧ ↓ s ∧ p q ∧ ∼ r ∧ →.
E 4.5.13
E 4.5.14
x a b c d e f g h i j
ϕ(x) (1, 2) (2, 3) (2, 5) (4, 2) (1, 3) (5, 1) (4, 5) (5, 3) (1, 4) (3, 4)
E 4.5.15
E 4.5.16
E 4.5.17
Hallar la matriz de precedencia y la lista de precedencia para los multidigrafos de los ejer-
cicios 4.5.13 y 4.5.14.
123
5 Relaciones binarias especiales
En toda esta sección, cuando no digamos lo contrario, las relaciones consideradas serán
entre los elementos de un conjunto.
(iv) transitiva si: (x, y), (y, z) ∈ R ⇒ (x, z) ∈ R. [xRy, yRz ⇒ xRz]
Ejemplos
R2 = {(a, a), (b, b), (c, c), (d, d), (e, e)},
124
Entonces
R1 : no es reflexiva, [(a, a) ∈
/ R1 ]
es transitiva y antisimétrica.
Nota. La relación R2 del ejemplo muestra que una relación puede ser simétrica y antisimétrica
a la vez.
Relaciones especiales
Para todo conjunto X = ∅, Rel(X) siempre contiene tres elementos muy importantes:
−→
R( G ) = {(x, y) : existe un arco con origen x y extremo y}.
125
Ejemplo
−
→
Sea G el digrafo indicado en la figura
−→
entonces R( G ) = {(1, 2), (1, 3), (2, 1), (3, 3)}.
Ejemplo
Sean X = {a, b, c} y R = {(a, a), (a, b), (b, c), (c, a)}, entonces
−
→
V = {a, b, c} y G (R) es el indicado en la figura siguiente
−→
Nota. La correspondencia que a cada R ∈ Rel(X), R = ∅ le asigna el digrafo R( G ), establece
una biyección entre el conjunto de relaciones no vacı́as sobre el conjunto X y el conjunto de
digrafos que tienen como conjunto de vértices al conjunto X.
126
(ii) simétrica: si para cada arco existe su opuesto.
(iii) antisimétrica: si para cada par de vértices x, y, x = y se verifica una y sólo una de las
siguientes condiciones:
127
(P1) R ⊆ RP ,
(i) R ⊆ R∗ ,
(ii) R∗ tiene la propiedad P ,
entonces RP ⊆ R∗ .
Observaciones
Vamos a ver ahora un resultado que nos será de utilidad para determinar las clausuras
reflexiva, simétrica y transitiva de una relación.
(i.1) R es reflexiva,
(i.2) IX ⊆ R.
(ii.1) R es simétrica,
(ii.2) Rop = R.
(iii.1) R es transitiva,
128
(iii.2) R2 ⊆ R, donde R2 = R ◦ R.
Dem.
⇒ (ii.2):
(ii) (ii.1) =
(ii.2) =⇒ (ii.1):
Sea
⇒ (iii.2):
(iii) (iii.1) =
Sea
129
⇒ (iii.1):
(iii.2) =
Sean
→y−
transitiva: para cada par de arcos −
ac
→ −
→ −
→
cb de G (RP ), debe estar el arco ab.
Dada R ∈ Rel(X), indicaremos con RRF , RSIM , RT R las clausuras reflexiva, simétrica y
transitiva de R, respectivamente.
Ejemplo
Sea X = {a, b, c, d} y R = {(a, a), (b, c), (b, d), (c, b), (c, a)}.
Para determinar la clausura reflexiva, incorporamos a R los pares (x, x) que le faltan para
que contenga a IX . Luego,
Para determinar la clausura simétrica, incorporamos a R los pares (x, y) que le faltan cuando
(y, x) está en R. Luego,
130
Para determinar la clausura transitiva, incorporamos los pares (x, z) que le faltan a R
cuando los pares (x, y), (y, z) están en R
(i) RRF = R ∪ IX ,
−
→
(P1) R ⊆ B: Sea (x, y) ∈ R, entonces en G (R) existe un camino de longitud uno que une el
vértice x con el vértice y. Luego, (x, y) ∈ B.
(P2) B es transitiva:
Sean
(1) (u, v) ∈ B,
(2) (v, w) ∈ B,
131
−
→
entonces en G (R)
(3) existe un camino de longitud l1 del vértice u al v, [(1)]
(4) existe un camino de longitud l2 del vértice v al w, [(2)]
(5) existe un camino de longitud finita del vértice u al w, [(3) y (4)]
(6) (u, w) ∈ B. [(5) y definición de B]
Supongamos que
(1) R ⊆ R∗ ,
(2) R∗ es transitiva,
y sea
(3) (u, v) ∈ B,
entonces
(4) (u, w1 ) ∈ R, (w1 , w2 ) ∈ R, . . . , (wn−1 , wn ) ∈ R, (wn , v) ∈ R [(3)
y definición de B]
(5) (u, w1 ) ∈ R∗ , (w1 , w2 ) ∈ R∗ , . . . , (wn−1 , wn ) ∈ R∗ , (wn , v) ∈ R∗ [(4) y (1)]
(6) (u, v) ∈ R∗ , [(5) y (2)]
(7) B ⊆ R∗ . [(3) y (6)]
132
Notaciones
(i) Denotaremos con Ref (X), Sim(X), T ran(X) y EQ(X) al conjunto de todas las rela-
ciones reflexivas, simétricas, transitivas y de equivalencia definidas sobre un conjunto X
respectivamente.
(ii) Es habitual representar a una relación de equivalencia con alguno de los sı́mbolos ∼, ,
≡.
Entonces si (x, y) pertenece a la relación se escribe x ∼ y, x y, ó x ≡ y y se lee x e y
son equivalentes.
Ejemplo
IA = {(x, x) : x ∈ A} y τA = A2 ,
Ejemplo
x a b c d
f (x) 1 2 2 1
133
5.7 Relación de equivalencia asociada a una partición
D 5.7.1 Una partición de un conjunto X no vacı́o, es una familia F de subconjuntos de X
con las siguientes propiedades:
(Pa1) si A ∈ F, entonces A = ∅,
(Pa2) si A, B ∈ F y A ∩ B = ∅, entonces A = B,
(Pa3) A = X.
A∈F
Dem.
(E1) RF es reflexiva:
134
(E3) RF es transitiva:
Sean
Ejemplo
RF = IX ∪ {(a, d), (d, a), (b, e), (e, b), (b, f ), (f, b), (e, f ), (f, e)}.
Clases de equivalencia
También usaremos las notaciones xR , x o |x|, para designar a la clase de equivalencia que
contiene a x. En general, las dos últimas se emplean cuando la relación R es una relación de
equivalencia fija.
135
(C1) x ∈ xR , cualquiera sea x ∈ X,
(a) (x, y) ∈ R,
(b) xR = yR .
Dem.
(i) xR ⊆ yR :
Sean
(1) (x, y) ∈ R, [hipótesis]
(2) u ∈ xR , [hipótesis]
entonces
(5) u ∈ yR , [(4)]
(6) xR ⊆ yR . [(2),(5)]
⇒ (a):
(b) =
(1) xR = yR , [hipótesis]
(2) y ∈ xR , [(C1),(1)]
136
Conjunto cociente
Ejemplos
x a b c d e g
f (x) 1 1 2 2 2 3
gRf = {g}.
Luego A/Rf = {aRf , cRf , gRf } = {{a, b}, {c, d, e}, {g}}.
137
Dem.
(Pa2) xR ∩ yR = ∅ ⇒ xR = yR :
Sean
(1) xR , yR ∈ X/R tales que xR ∩ yR = ∅, [hipótesis]
entonces,
(2) c ∈ xR ∩ yR , [(1)]
(6) xR = yR . [(5),(C2)]
(Pa3) xR = X:
x∈X
(i) xR ⊆ X:
x∈X
(2) xR ⊆ X, [(1)]
(3) xR ⊆ X. [(2)]
x∈X
(ii) X ⊆ xR :
x∈X
Sea
(1) z ∈ X, [hipótesis]
(2) z ∈ zR , [(C1)]
(3) z ∈ xR , [(2)]
x∈X
138
(4) X ⊆ xR , [(1),(3)]
x∈X
De (i) y (ii) resulta Pa3.
De T 5.9.2 resulta que para hallar las relaciones de equivalencia sobre un conjunto A basta
hallar las particiones de A y recı́procamente.
(i) p0 = 1,
n
n−1
(ii) pn = j−1
pn−j .
j=1
Observemos que qR es una función pues cada x ∈ A pertenece a una y sólo una clase de
equivalencia. Por otra parte, es claro que qR es sobreyectiva.
El siguiente resultado expresa la conexión existente entre las nociones de función y relación
de equivalencia.
139
(i) f ∗ es inyectiva,
f = f ∗ ◦ qR
A - B
½>
qR ½
½
½ f∗
? ½
½
A/R
(a) f ∗ es funcional:
Sean
(b) f ∗ ◦ qR = f :
En efecto, sea
g : A/R −→ B tal que g ◦ q = f ,
entonces dado aR ∈ A/R se verifica
g(aR ) = g(q(a))
= f (a) [g ◦ q = f ]
= f ∗ (q(a)) [f ∗ ◦ q = f ]
140
= f ∗ (aR ).
Luego, g = f ∗ .
Además,
(i) f es inyectiva:
Sean
(1) (C, f (x)), (D, f (x)) ∈ f ∗ ,
entonces,
(2) x ∈ C y x ∈ D, [de (1)]
(3) C ∩ D = ∅, [de (2)]
(1) C = D. [de (3)]
(ii) f ∗ es sobreyectiva si, y sólo si, f lo es: la demostración queda como ejercicio.
Nota. Las relaciones de orden (de equivalencia) son las relaciones de pre — orden que verifican
la propiedad antisimétrica (simétrica).
Conjuntos ordenados
D 5.11.2 Llamaremos conjunto ordenado ( c.o.) a todo par (A, R) formado por un conjunto
no vacı́o A y una relación R de orden definida sobre A. También diremos que A es el soporte
del c.o. (A, R).
Ejemplo
El par (A, R), donde A = {a, b, c} y R = {(a, a), (b, b), (c, c), (a, c), (b, c)} es un c.o..
141
Notaciones
(i) A veces para simplificar, representaremos al c.o. por medio de su conjunto soporte y
diremos, sea A un c.o..
(iii) Sea A = (A, ≤) un c.o.. De acuerdo a una convención ya fijada escribiremos a ≤ b para
indicar que se verifica (a, b) ∈≤.
Si a ≤ b diremos que, a precede a b, o que a es menor o igual que b.
a1 ≤ a2 , a2 ≤ a3 , . . . , an−1 ≤ an .
Ejemplo
A = {1, 2, 3, 4},
≤= {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}.
1 ≤ 1, 1 ≤ 2, 1 ≤ 3, 1 ≤ 4,
2 ≤ 2, 2 ≤ 3, 2 ≤ 4,
3 ≤ 3, 3 ≤ 4,
4 ≤ 4.
142
La relación de orden estricto determinada por una relación de orden
Nota. La relación < asociada a una relación de orden ≤ es transitiva y además verifica la
propiedad a < a, para todo a ∈ A.
Entonces < nunca es una relación de orden. Sin embargo, algunos autores dicen que es una
relación de orden estricto, lo cual nos parece inapropiado por la razón expuesta.
Paso 1
Paso 2
Si a < b el afijo de b se dibuja por encima del afijo de a (en algunos casos especiales
a esta regla no se la tendrá en cuenta).
Paso 3
143
Ejemplos
a ≤ a, a ≤ b, a ≤ c, a ≤ d,
b ≤ b, b ≤ c, b ≤ d,
c ≤ c, c ≤ d,
d ≤ d.
(ii) A = {a, b, c, d, e} y
≤= {(a, a), (a, b), (b, b), (c, d), (d, d), (a, c), (c, c), (a, d), (a, e), (b, d), (d, e), (b, e),
(e, e), (c, e)}.
En general es conveniente escribir la relación <, y partir de ella detectar cuáles son los
sucesores inmediatos de cada elemento. Entonces escribimos < del siguiente modo:
(a, b), (a, c), (a, d), (a, e), [b, c, d, e siguen a a]
144
Entonces su diagrama de Hasse es
Ejemplo
entonces:
a ≤ a, a ≤ c, a ≤ d, a ≤ e, a ≤ f ,
b ≤ b, b ≤ d, b ≤ e, b ≤ f ,
c ≤ c,
d ≤ d, d ≤ e, d ≤ f ,
145
e ≤ e,
f ≤ f.
D 5.12.2 Sea (A, ≤) un c.o.. Diremos que ≤ es un orden total y que (A, ≤) es un conjunto
totalmente ordenado, o cadena, si se verifica
a, b ∈ A y a = b ⇒ a ≤ b ó b ≤ a.
Ejemplo
A = {a, b, c, d},
≤= IA ∪ {(a, b), (a, c)(a, d), (b, c), (b, d)(c, d)}.
Entonces
Nota. Algunos autores llaman orden parcial a las relaciones que nosotros hemos llamado orden
y orden a las que hemos llamado orden total.
146
5.13 Subconjuntos ordenados
D 5.13.1 Sean (A, ≤) un c.o. y B ⊆ A. Llamaremos orden sobre B inducido por ≤ a
≤1 = (B × B)∩ ≤, y diremos que (B, ≤1 ) es un subconjunto ordenado de (A, ≤).
Cuando no haya lugar a confusión, para simplificar la notación, escribiremos (B, ≤) en lugar
de (B, ≤1 ), aún cuando tengamos que ≤=≤1 .
A veces simplificaremos más y diremos, sea B el subconjunto ordenado del c.o. A.
Ejemplo
Sean
A = {a, b, c, d, e},
≤= IA ∪ {(e, c), (d, c), (d, b), (d, a), (e, a), (b, a), (c, a)}.
Entonces
B × B = IB ∪ {(d, a), (d, e), (a, d), (a, e), (e, d), (e, a)},
147
5.14 Elementos especiales de un conjunto ordenado
Sea (A, ≤) un conjunto ordenado. A continuación definiremos ciertos elementos especiales, los
cuales pueden existir o no.
(i) minimal si x ≤ m ⇒ x = m,
(ii) maximal si m ≤ x ⇒ x = m,
Ejemplo
Notas.
(i) El ejemplo anterior muestra que existen c.o. que no tienen ni primer ni último elemento.
148
Existencia de elementos minimales en un c.o. finito
Dem.
(2) Existe a2 ∈ A tal que a2 < a1 . Si a2 es minimal, entonces (A, ≤) tiene elementos
minimales. En caso contrario vale (3).
Como el conjunto ordenado A es finito, el proceso anterior debe parar en algún elemento
an , el cual es minimal.
Notas.
(i) De manera totalmente análoga se demuestra que todo c.o. finito tiene elementos maxi-
males.
(ii) Si un c.o. finito A tiene un único elemento minimal (maximal), entonces dicho elemento
es el primer (último) elemento.
Dem. La demostración la haremos por inducción sobre el número de elementos del c.o..
(i) Si A es un c.o. con un solo elemento, entonces A tiene diagrama de Hasse, el cual se
reduce a un punto.
149
(ii) Supongamos que el enunciado vale para todo conjunto ordenado B tal que |B| ≤ n.
(hipótesis de inducción)
150
5.15 Cotas y conjuntos acotados
D 5.15.1 Sean (A, ≤) un c.o., X ⊆ A y c ∈ A. Diremos que:
Ejemplo
entonces,
{a, b} – d, f, g
{f } a, b, c, d, f f
{d, e} b g
{c, g} a –
151
(iii) si existen cotas inferiores (superiores) de un conjunto X, éstas pueden pertenecer o no a
X.
Ejemplo
Sea (A, ≤) el conjunto ordenado cuyo diagrama de Hasse es
entonces
X inf X supX
{c, d} – f
{d, f, g, h, i} d –
152
El ejemplo anterior, muestra que el ı́nfimo (supremo) de un conjunto X puede existir o no
y que, en caso de existir, puede pertenecer o no a X.
Nota. Observemos que el ı́nfimo (supremo) de un conjunto, si existe, es único.
5.16 Retı́culos
D 5.16.1 Sea A un c.o.. Diremos que A es un:
(i) retı́culo inferior, si cualquier subconjunto de A con dos elementos tiene ı́nfimo,
(ii) retı́culo superior, si cualquier subconjunto de A con dos elementos tiene supremo,
Nota. Observemos que si (A, ≤) es un retı́culo inferior (superior), entonces (A, ≥) es un retı́culo
superior (inferior). Luego, si (A, ≤) es un retı́culo, entonces (A, ≥) también es un retı́culo.
Ejemplos
(i)
es retı́culo inferior,
no es retı́culo superior,
no es retı́culo,
(ii)
no es retı́culo inferior,
es retı́culo superior,
no es retı́culo,
153
(iii)
no es retı́culo inferior,
no es retı́culo superior,
no es retı́culo,
(iv)
es retı́culo inferior,
es retı́culo superior,
es retı́culo,
Observemos que existen retı́culos que no tienen primer elemento o último elemento.
Ejemplos
154
Probemos ahora que A tiene un único minimal y que dicho minimal es primer elemento de
A. Sean
entonces,
(6) i ≤ m1 , [(5)]
(7) i ≤ m2 , [(5)]
(8) i = m1 , [(6),(3)]
(9) i = m2 , [(7),(4)]
(10) m1 = m2 . [(8),(9)]
(12) a ≤ m1 , [(11)]
(13) a ≤ x, [(11)]
(14) a = m1 , [(12),(3)]
(15) m1 ≤ x, [(13),(14)]
Nota. En forma análoga se demuestra que todo retı́culo superior finito tiene último elemento.
155
Retı́culos complementados
D 5.16.2 Sea (A, ≤) un retı́culo con primer elemento 0 y último elemento 1. Dado a ∈ A,
diremos que b ∈ A es un complemento de a si
Ejemplos
x complementos de x
0 1
a b, c
b a, c
c a, b
1 0
x complementos de x
0 1
a —
b —
c e
d —
e c
f —
g —
1 0
156
D 5.16.3 Sea (A, ≤) un retı́culo con primer elemento 0 y último elemento 1. Diremos que A
es complementado si todo elemento tiene complemento.
5.17 Ejercicios
E 5.17.1
(a) A = {1, 2, 3}
(b) A = {1, 2, 3, 4}
(i) (ii)
(iii)
157
(c) A = {a, b, c, d}
(i) (ii)
(iii) (iv)
(d) A = {a, b, c}
(f) A = ZZ,
xRy si, y sólo si, x − y es par,
158
(g) A = ZZ2 ,
(a, b)R(c, d) si, y sólo si, a ≤ c.
E 5.17.2
R ∈ Rel(A) se dice circular si para todo x, y, z ∈ A, las hipótesis xRy e yRz implican zRx.
Probar que
(a) si R ∈ Rel(A) es una relación simétrica, entonces las siguientes condiciones son equiva-
lentes:
(i) R es transitiva,
(ii) R es circular.
E 5.17.3
Sean R1 , R2 ∈ Rel(A). Averiguar si las siguientes afirmaciones son verdaderas o falsas, justifi-
cando las respuestas:
E 5.17.4
159
(c) Sea R2 ∈ Ref (X). Probar que si R2 ◦ R1 ⊆ R2 , entonces R1 ⊆ R2 . ¿Es válida la
recı́proca?
E 5.17.5
Dada R ∈ Rel(X), sean RRF y RSIM las clausuras reflexiva y simétrica de R, respectiva-
mente. Probar que
(a) RRF = R ∪ IX ,
E 5.17.6
(a) R = {(a, a), (c, b), (b, b), (a, c), (c, e), (c, c), (d, d), (e, e), (e, b), (c, a), (a, e)},
(b)
E 5.17.7
(b) A = {1, 2, 3, 4}, R = {(1, 1), (2, 2), (1, 3), (3, 3), (2, 4), (4, 4), (4, 2), (3, 1)},
160
(d) A = ZZ, xRy si, y sólo si, 7/(x − y),
a b c d
a 1 0 0 1
b 0 1 0 0
M (R) = .
c
0 0 1 0
d 1 0 0 1
E 5.17.8
Sean A = {1, 2, 3, 4} y S = {(1, 1), (2, 1), (3, 2), (2, 3)} ⊆ A × A:
(b) hallar S EQ .
E 5.17.9
E 5.17.10
(a) R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1)},
(b) R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (1, 4), (4, 1), (2, 4), (4, 2)}.
E 5.17.11
161
(a) determinar la relación de equivalencia Rf asociada a f ,
E 5.17.12
E 5.17.13
(a) Sea P = {{1, 2, 3}, {4}, {5, 6}} una partición de A = {1, 2, 3, 4, 5, 6}.
Indicar la relación R(P ) asociada a dicha partición.
(c) Dados U = {1, 2, 3}, C = {1, 2} y R la relación de equivalencia del ejercicio 5.17.7 inciso
(c). Determinar la partición asociada a R.
E 5.17.14
(a) Hallar las clases de equivalencia y el conjunto cociente para cada una de las relaciones
dadas en:
162
(i) ejercicio 5.17.10,
(ii) ejercicio 5.17.7, incisos (b), (e), (g), (h).
(b) Hallar el conjunto cociente para cada una de las relaciones dadas en el ejercicio 5.17.11.
E 5.17.15
x 1 2 3 4 5 6 7
f (x) a b b c b a d
(b) A = {−4, −3, −2, −1, 0, 1, 2, 3, 4}, B = IN, f : A −→ B definida por f (x) = 2x2 + 3,
E 5.17.16
Dibujar el diagrama de Hasse correspondiente a cada uno de los siguientes conjuntos orde-
nados:
(c) A = {{1}, {5}, {2, 3}, {1, 3}, {1, 3, 5}, ∅},
163
(i) |A| = 0, (ii) |A| = 1,
E 5.17.17
Para cada uno de los conjuntos ordenados del Ejercicio 5.17.16, hallar
E 5.17.18
(a) hallar
(iv) inf {c, b}, (v) inf {d, x}, (vi) inf {c, e},
E 5.17.19
164
(i) (ii)
(iii) (iv)
(b) en los subconjuntos que se indican en cada diagrama hallar, si existen, cotas superiores,
cotas inferiores, supremo e ı́nfimo.
E 5.17.20
E 5.17.21
E 5.17.22
165
Sea A un c.o.. Probar que:
E 5.17.23
Sea (A, R) un c.o. finito y M (R) una matriz asociada a R. Observando dicha matriz,
determinar cómo se puede reconocer:
166
6 Sistemas algebraicos
En este capı́tulo presentaremos las definiciones y los teoremas en forma general para ope-
raciones n—arias donde n es un entero no negativo, pero en este curso trabajaremos sólo con
n = 0, n = 1 y n = 2, y las demostraciones las haremos solamente para los dos últimos valores
de n. Todos los temas generales que veremos, pertenecen a la disciplina matemática conocida
con el nombre de álgebra universal.
Ejemplos
(ii) p : IR −→ IR,
D 6.1.2 Sea A un conjunto no vacı́o, una operación 0−aria definida sobre A es cualquier
elemento fijo de A.
6.2 Algebras
D 6.2.1 Un sistema algebraico, conjunto algebrizado o simplemente álgebra es un par A =
A, F , donde A = ∅ y F es un conjunto de operaciones finitarias sobre A.
167
Ejemplos
(i) soporte del álgebra al conjunto A. Cuando no haya lugar a confusión sobre F represen-
taremos al álgebra por su conjunto soporte y diremos sea A un álgebra.
Ejemplos
En general n1 ≤ n2 ≤ . . . ≤ nk .
Ejemplos
Ejemplos
168
Clases de álgebras
Observaciones
(i) Cuando no haya lugar a confusión usaremos el mismo conjunto F para todas las álgebras
de la clase.
(ii) Cuando trabajemos en forma teórica diremos sea K una clase de álgebras y A ∈ K o
también, sea A una K−álgebra.
Ejemplos
+ 0 1
0 0 1
1 1 1
169
D 6.2.8 Un álgebra A, ∗, e de tipo (2, 0) es un semigrupo con unidad o monoide si se verifica:
(i) A, ∗ ∈ S,
(i) el reducto A, ∗, e ∈ SU ,
Ejemplos
(i) ZZ, +, −, 0 , Q,
I +, −, 0 y IR, +, −, 0 son grupos.
(ii) Mn (IR), +, −, O ∈ G.
(ii) Sea X un conjunto. Representaremos con B(X) al conjunto de todas las biyecciones de
X sobre X. Entonces BX = B(X), ◦,−1 , IX es un grupo llamado el grupo simétrico
sobre X.
Si X = {1, 2, . . . , n} escribiremos Bn en lugar de BX y diremos que Bn es el grupo
simétrico de orden n.
170
Ejemplos
(i) ZZ, +, −, 0 , IR∗ , ·,−1 , 1 , con IR∗ = IR \ {0}, son grupos abelianos.
/ Ga pues, en general, f ◦ g = g ◦ f .
(ii) Bn ∈
(i) A, +, −, 0 ∈ Ga ,
(ii) A, · ∈ S,
Ejemplos
ZZ, +, ·, −, 0 , Mn (IR), +, ·, −, O , Q,
I +, ·, −, 0 y IR, +, ·, −, 0 son anillos.
(i) A, +, ·, −, 0 ∈ A,
(i) A, +, ·, −, 0 ∈ A,
(ii) A, ·, 1 ∈ SU .
171
(P) la hipótesis x · y = 0 implica x = 0 o y = 0.
Ejemplos
(i) ZZ, +, ·, −, 0, 1 , Q,
I +, ·, −, 0, 1 , IR, +, ·, −, 0, 1 son anillos unitarios,
/ AU ,
(ii) Mn (IR), +, ·, −, O, I ∈
/ AD , IR, +, ·, −, 0, 1 ∈ A0 .
(iii) ZZ, +, ·, −, 0, 1 ∈
Ejemplos
I +, ·, −, 0, 1 , IR, +, ·, −, 0, 1 y C,
Q, I +, ·, −, 0, 1 son cuerpos.
6.3 Subálgebras
D 6.3.1 Sean A ∈ K y S ⊆ A. Diremos que S es una subálgebra de A, y lo notaremos S A,
si se verifican:
(S0) S = ∅,
Notas.
(i) Es usual decir que S es una subálgebra de A si, y sólo si, S es un subconjunto no vacı́o
de A cerrado con respecto a todas las operaciones de A.
172
Ejemplo
Sea A, +, 0 de tipo (2, 0) donde A = {0, a, b, c} y + está definida por medio de la siguiente
tabla:
+ 0 a b c
0 0 a b c
a a a c c
b b c b c
c c c b c
Entonces se verifican:
(b) {0, a} A.
Ejercicio
Observemos que:
(i) la definición de subálgebra generada tiene sentido por que siempre existe una subálgebra
de A que contiene a X y la intersección no vacı́a de subálgebras es una subálgebra.
(ii) [X] es la menor (en el sentido de la inclusión) de todas las subálgebras de A que contienen
a X.
Ejercicio
173
(i) B = [X],
(a) X ⊆ B,
(b) B A,
(c) las hipótesis X ⊆ S y S A implican que B ⊆ S.
Ejemplo
En efecto, sea
B = {u ∈ A : existen x1 , . . . , xk ∈ X tal que u = x1 ∗ . . . ∗ xn },
entonces
(b) B A: sean
u = x1 ∗ . . . ∗ xn ,
v = y1 ∗ . . . ∗ yn ,
entonces
u ∗ v = x1 ∗ . . . ∗ xk ∗ y1 ∗ . . . ∗ yn ∈ B.
(c) S A y X ⊆ S implican B ⊆ S:
(1) u ∈ B, [hipótesis]
(3) X ⊆ S, [hipótesis]
(5) S A, [hipótesis]
174
Sistemas de generadores
D 6.4.4 Diremos que la clase K es localmente finita si toda álgebra de K f.g. es finita.
6.5 Homomorfismos
D 6.5.1 Sean A, B ∈ K. Una aplicación h : A −→ B es un K−homomorfismo, o simplemente
un homomorfismo, si se verifican:
Además si:
175
(v) A = B, diremos que h es endomorfismo y en lugar de Hom(A, A) escribiremos End(A).
Ejemplo
◦ a b
a b a
b a b
es un S−epimorfismo.
Dem. Esbozaremos la demostración para el caso de las operaciones binarias ya que para las
restantes el razonamiento es análogo.
176
= h(s ∗ t) [h es homomorfismo]
(4) s ∗ t ∈ S, [(1),(2) y S A]
x ∗ y ∈ h(S).
Ejemplo
Sean A, B ∈ S, donde A = {a, b, c}, B = {m, n, p} y las operaciones están dadas por las
siguientes tablas:
∗ a b c ∗ m n p
a a b c m m m m
b b b c n m n m
c c c c p m m p
(i) h(X) ⊆ C:
(ii) C B:
(1) X ⊆ A, [hipótesis]
177
(3) h ∈ Hom(A, B), [hipótesis]
(3) S B, [hipótesis]
y probemos que h = h1 .
Sea S = {x ∈ A : h(x) = h1 (x)}, entonces
(i) G ⊆ S, [(1)]
(ii) S A:
178
(3) h(y) = h1 (y), [hipótesis]
(6) x ∗ y ∈ S.
Ejemplo
+ a b c
+ 0 1
a a b c
0 0 1
b b c a
1 1 0
c c a b
pero
h(c + c) = h(b) = 1,
h(c) + h(c) = 1 + 1 = 0,
luego,
179
6.6 Congruencias y álgebras cociente
D 6.6.1 Sea A ∈ K. R ∈ EQ(A) es una K—congruencia, o simplemente una congruencia
sobre A, si R es compatible con todas las operaciones n—arias, n > 0 definidas sobre A. Esto
es, si se verifica:
Relación núcleo
(2) x Rh y , [hipótesis]
180
(5) h(x) ◦ h(x ) = h(y) ◦ h(y ), [(3) y (4)]
Algebras cociente
Dem. Es claro que de acuerdo a la forma en que han sido definidas las operaciones en A/R,
solamente debemos verificar que las mismas son independientes de los representantes elegidos
en cada clase.
Haremos la demostración para el caso de las operaciones binarias.
Sean C1 , C2 ∈ A/R, x1 , x2 ∈ C1 , y1 , y2 ∈ C2 y supongamos que C = (x1 ◦ y1 )R y C =
(x2 ◦ y2 )R , entonces probemos que C = C .
En efecto,
(5) C = C .
181
Nota. En lo que sigue también representaremos con F al conjunto F ∗ , es decir usaremos en
A y A/R los mismos sı́mbolos de operaciones.
(i) h es inyectiva,
Dem. Sabemos que existe una única función h : A/N (h) −→ B tal que h ◦ q = h, que verifica
las condiciones (i) y (ii).
Probemos que h ∈ Hom(A/N (h), B).
Sean xR , yR ∈ A/N (h) y ∗ ∈ F una operación binaria, entonces:
= h(q(x ∗ y))
= (h ◦ q)(x ∗ y)
= h(x ∗ y)
= h(q(x)) ∗ h(q(y))
= h(xR ) ∗ h(yR ).
182
6.7 Algebras libres
(A1) [X] = L,
T 6.7.1 Sean L(X), F y L(X ), F dos álgebras libres similares que tienen a X y X como
conjunto de generadores libres, respectivamente. Si |X| = |X |, entonces existe un isomorfismo
h : L(X) −→ L(X ).
Dem. Sea
183
(1) α : X −→ X biyectiva, [hipótesis]
entonces existen
(i) h ◦ h = IL(X) :
(6) X ⊆ B: Si x ∈ X,
f (x) = h (h(x)) [(5)]
= h (α(x)) [(3)]
= β(α(x)) [(4)]
= x. [(2)]
T 6.7.2 Sea L, F un álgebra absolutamente libre tal que X y X son conjunto de generadores
libres. Entonces se verifica |X| = |X |.
184
Dem. Supongamos que
entonces
(4) [f (X)] es libre con f (X) como conjunto de generadores libres, [(2), Ejercicio 6.9.17]
(i) De T 6.7.1 resulta la unicidad del álgebra libre L que tiene a X como conjunto de ge-
neradores libres, en el sentido de que cualquier otra álgebra que tenga un conjunto de
generadores libres con el cardinal de X, es isomorfa a L.
(ii) De T 6.7.2 resulta que álgebra libre L puede tener más de un conjunto de generadores
libres, pero todos ellos tienen el mismo cardinal. En particular si L = L(X) y |X| = n,
entonces cualquier otro conjunto de generadores libres tiene n elementos.
185
Una construcción del álgebra absolutamente libre
Ahora consideraremos ciertas álgebras cuyos conjuntos soportes se construyen por medio de
las reglas indicadas para construir al conjunto F or[X] de las formas polinomiales estudiados
en la sección 1.2 del capı́tulo 1.
(R1) X ⊆ F or[X],
(R4) (de cierre) Las únicas f.p. son las determinadas por R1, R2 y R3.
Ahora algebrizaremos a F or[X] tomando como operaciones sobre este conjunto al propio
F , es decir:
(i) Elegimos como operaciones 0—arias de F or[X] a los sı́mbolos de operaciones 0—arias de
F . Esto es posible, pues por R1, estos objetos están en F or[X].
186
(L1) [X]K = L,
Sea S(X) el conjunto de todas las palabras construı́bles sobre X. En S(X) vamos a definir
una operación binaria llamada operación de concatenación del siguiente modo:
dadas
p = x1 x2 . . . xm , x1 , x2 , . . . , xm ∈ X,
q = y1 y2 . . . yk , y1 , y2 , . . . , yk ∈ X,
entonces
p · q = x1 x2 . . . xm y1 y2 . . . yk .
Luego
En efecto, sean
p = x1 . . . xm , q = y1 . . . yk , r = z1 . . . zs ∈ S(X),
entonces
(p · q) · r = (x1 . . . xm y1 . . . yk ) · r
= x1 . . . xm y1 . . . yk z1 . . . zs
= x1 . . . xm (y1 . . . yk z1 . . . zs )
187
= p · (q · r).
(a) X ⊆ S(X):
Sea p = x1 . . . xn ∈ S(X), x1 , . . . , xn ∈ X,
entonces
x1 · x2 · x3 · . . . · xn = x1 x2 . . . xn , [verificarlo]
x1 · x2 · x3 · . . . · xn ∈ [X]S , [verificarlo]
luego
p = x1 x2 x3 . . . xn ∈ [X]S .
p = x1 x2 . . . xn , x1 , x2 , . . . , xn ∈ X,
q = y1 y2 . . . ym , y1 , y2 , . . . , ym ∈ X,
entonces
h(p · q) = h(x1 x2 . . . xn y1 y2 . . . ym )
= f (x1 ) ∗ . . . ∗ f (xn ) ∗ f (y1 ) ∗ . . . ∗ f (ym )
188
= h(p) ∗ h(q).
Además, si
p = x, con x ∈ X,
vale
6.9 Ejercicios
E 6.9.1
Determinar si las siguientes aplicaciones definen una operación n-aria sobre A. En caso afir-
mativo, indicar su aridad.
E 6.9.2
189
x
(ii) IR>0 , ∗ , donde x ∗ y = ,
y
(iii) P(S), ∗ , donde S = ∅ y ∗ es la intersección de conjuntos,
E 6.9.3
(iii) si a, b ∈ A, entonces
(a) a · 0 = 0 · a = 0,
(b) a · (−b) = (−a) · b = −(a · b),
(c) (−a) · (−b) = a · b.
E 6.9.4
190
(b) T = {(x, y, z) ∈ ZZ3 : x = 0, z = 1}.
E 6.9.6
(a) X = {1},
(b) X = {−1, 2}.
1 2 3 1 2 3
(c) X = { , }.
2 3 1 2 1 3
E 6.9.7
191
Sean A, ∗, p ∈ SU y B, ◦, d ∈ SU , donde A = {m, n, p}, B = {a, b, c, d} y ∗, ◦ están dadas
por las tablas
◦ a b c d
∗ m n p
a a a a a
m m m m
b a b a b
n m n n
c a a c c
p m n p
d a b c d
E 6.9.8
(ii) h ∈ HomSU (A, B), siendo A = ZZ, +, 0 , B = ZZ, ·, 1 y h definida como en el ejercicio
5.9.8 (i) (b).
E 6.9.9
192
Sean G1 , G2 ∈ G. Probar que si f : G1 −→ G2 verifica f (x · y) = f (x) · f (y), entonces
f ∈ HomG (G1 , G2 ).
E 6.9.10
E 6.9.11
(i) Sean G, ∗, , e ∈ G y R ∈ EQ(G). Probar que las siguientes condiciones son equivalentes:
(ii) Sea A, +, ·, −, 0 ∈ A y R ∈ EQ(A). Probar que las siguientes condiciones son equiva-
lentes:
E 6.9.12
Sea ZZ, +, −, 0 ∈ Ga . Dado n ∈ IN fijo, sea ≡n la relación definida sobre ZZ del siguiente
modo:
E 6.9.13
193
(ii) Calcular los anillos ZZ3 , +, ·, −, 0 y ZZ4 , +, ·, −, 0 .
E 6.9.14
Sea L un álgebra absolutamente libre (relativamente libre) que tiene a X como conjunto de
generadores libres. Probar que si Y ⊆ X, entonces L0 = [Y ] es un álgebra absolutamente libre
(relativamente libre) que tiene a Y como conjunto de generadores libres.
E 6.9.15
Sea L un álgebra absolutamente libre (relativamente libre) que tiene a X como conjunto de
generadores libres. Probar que [X \ {x}] = L para todo x ∈ X.
E 6.9.16
(i) A = [X],
y A no es libre.
E 6.9.17
Sea L un álgebra absolutamente libre (relativamente libre) que tiene a X y a Y como conjuntos
de generadores libres. Probar que para toda f : X −→ Y se verifica que [f (X)] es el álgebra
absolutamente libre (relativamente libre) que tiene a f (X) como conjunto de generadores libres.
Además si f es inyectiva, entonces [f (X)] = L.
E 6.9.18
Indicar un ejemplo de un álgebra L relativamente libre que tiene a X como conjunto de ge-
neradores libres y tal que existen Y ⊆ L, f : X −→ Y inyectiva y sin embargo [f (X)] no es
relativamente libre.
Este ejemplo muestra que la hipótesis de que Y es un conjunto de generadores libres del
ejercicio 6.9.17 no se puede eliminar.
194
7 Retı́culos distributivos y álgebras de Boole
(R1) x + (y + z) = (x + y) + z,
(R2) x + y = y + x,
(R3) x + x = x,
(R4) x · (y · z) = (x · y) · z,
(R5) x · y = y · x,
(R6) x · x = x,
(R7) x + (x · y) = x,
(R8) x · (x + y) = x.
T 7.1.1 Sea A, ∗ una banda. La relación ≤∗ definida por x ≤∗ y si, y sólo si, x ∗ y = x, es
una relación de orden sobre A.
Dem.
(O2) x ≤∗ y, y ≤∗ x implican x = y:
195
(O3) x ≤∗ y e y ≤∗ z, implican x ≤∗ z:
Nota. Si A, +, · ∈ R, entonces sobre A podemos definir dos órdenes inducidos por las
operaciones + y · respectivamente. Obtenemos ası́ dos estructuras ordenadas:
(i) A, ≤+ , donde x ≤+ y ⇔ x = x + y,
(ii) A, ≤· , donde x ≤· y ⇔ x = x · y.
Dem.
(i) ≤op
· ⊆ ≤+ :
(ii) ≤+ ⊆ ≤op
· :
De lo expuesto todo retı́culo es un conjunto ordenado, por lo tanto la teorı́a de los retı́culos
puede ubicarse dentro de la teorı́a de las estructuras ordenadas.
De ahora en adelante dado un retı́culo consideraremos únicamente el orden ≤· = ≤op
+ y para
196
x ≤ y ⇔ x = x · y ⇔ x + y = y.
T 7.1.3 Sea A, +, · ∈ R. Entonces (A, ≤) es un conjunto ordenado retı́culo donde para todo
a, b ∈ A se verifican:
Dem.
(a) a · b ≤ a:
(1) (a · b) · a = a · (a · b) [R5]
= (a · a) · b [R4]
= a · b. [R6]
(b) a · b ≤ b:
Es análoga a la de (a).
(3) z · (a · b) = (z · a) · b [R4]
=z·b [(1)]
= z. [(2)]
De (a) y (b) resulta que a · b es cota inferior de {a, b} y de (c) resulta que es la mayor de
las cotas inferiores, luego (i) queda demostrado.
197
T 7.1.4 Sea (A, ≤) un conjunto ordenado retı́culo. Si para todo x, y ∈ A definimos:
entonces A, +, · ∈ R.
Dem. Ejercicio.
Ejemplos
(A, ≤) es un conjunto ordenado retı́culo, luego por T 7.1.4 resulta que A, +, · ∈ R donde
+ y · están dadas por las tablas
+ 0 a b c 1 · 0 a b c 1
0 0 a b c 1 0 0 0 0 0 0
a a a b c 1 a 0 a a a a
b 0 b b 1 1 b 0 a b a b
c c c 1 c 1 c 0 a a c c
1 1 1 1 1 1 1 0 a b c 1
(ii) Sea A, +, · ∈ R, donde A = {a, b} y las operaciones están dadas por las tablas
+ a b · a b
a a b a a a
b b b b a b
198
Entonces por T 7.1.1,
(i) A, +, · ∈ R,
(R9) x · 0 = 0,
(R10) x + 1 = 1.
Ya hemos visto que las nociones de conjunto ordenado retı́culo y retı́culo son equivalentes.
Luego si A es un retı́culo finito, entonces A ∈ R0,1 .
(D) x · (y + z) = (x · y) + (x · z).
199
Ejemplos
c · (a + b) = c · 1 = c,
(c · a) + (c · b) = a + 0 = a.
Luego c · (a + b) = (c · a) + (c · b).
200
7.3 Elementos irreducibles, primos y átomos
D 7.3.1 Sea A, +, ·, 0, 1 ∈ R0,1 y a ∈ A. Diremos que
(I1) a = 0,
(I2) la hipótesis a = x + y, implica a = x ó a = y.
(P1) a = 0,
(P2) la hipótesis a ≤ x + y, implica a ≤ x ó a ≤ y.
(A1) a = 0,
(A2) las hipótesis b ∈ A y 0 ≤ b ≤ a implican b = 0 o b = a.
Con Ir(A), P r(A) y Π(A) indicaremos al conjunto de los elementos irreducibles, primos y
átomos de A respectivamente.
A continuación vamos a indicar métodos para determinar elementos irreducibles y primos
de A, +, ·, 0, 1 ∈ R0,1
Dado a ∈ A, a = 0:
Ejemplo
201
Li (a) = {0}, su diagrama de Hasse es
Luego, a es irreducible.
Li (b) = {0}, es análogo al caso anterior. Luego, b es irreducible.
Li (c) = {0, a}, su diagrama es
Luego, c es irreducible.
Li (1) = {0, a, b, c}, su diagrama es
Entonces 1 no es irreducible.
202
Por lo tanto Ir(A) = {a, b, c}.
Dado a ∈ A, a = 0:
Ejemplo
203
Ts (b) = {b, 1}, A \ Ts (b) = {0, a, c} y su diagrama es
Luego, b es primo.
Ts (c) = {c, 1}, A \ Ts (c) = {0, a, b} y su diagrama es
Entonces, c no es primo.
Ts (1) = {1}, A \ Ts (1) = {0, a, b, c} y su diagrama es
Luego, 1 no es primo.
Dem. Sea
entonces
204
(I1) a = 0. [(1)]
(2) a = x + y,
(3) x ≤ a, [(2), a = sup{x, y}]
(4) y ≤ a, [(2), a = sup{x, y}]
(5) a ≤ x + y, [(2)]
(6) a ≤ x o a ≤ y, [(5),(1)]
(7) a = x o a = y. [(3),(4),(6)]
La otra inclusión sólo vale para retı́culos distributivos, más precisamente se verifica:
T 7.3.2 Sea A, +, ·, 0, 1 ∈ R0,1 finito. Entonces las siguientes condiciones son equivalentes:
(i) A ∈ D0,1 ,
Elementos booleanos
a + b = 1,
a · b = 0.
205
Representaremos con B(A) al conjunto de los elementos booleanos de A.
Ejemplos
(i) x complemento de x
0 1
a d
b —
c —
d a
1 0
(ii) x complemento de x
0 1
a b
b a
1 0
B(D) = D.
(iii) x complemento de x
0 1
a c
b c
c a, b
1 0
B(C) = C.
206
(1) b1 , b2 son complementos de a, [hipótesis]
entonces
(2) b1 + a = 1 = b2 + a,
b1 · a = 0 = b2 · a, [(1)]
Es claro que la familia de los retı́culos booleanos constituyen una subclase de D0,1 , donde
las álgebras de esta subclase no están definidas por axiomas que son igualdades. Sin embargo,
existen ciertas álgebras, llamadas álgebras de Boole, que son definibles por igualdades y que
son equivalentes a los retı́culos booleanos.
(B1) x · x = 0,
(B2) x + x = 1.
207
Ejemplos
(i) Sea X un conjunto no vacı́o. Sabemos que P(X), ∪, ∩, ∅, X ∈ D0,1 . Para cada A ∈
P(X), sea C(A) el complemento de A en X. Entonces se verifican:
(1) A ∩ C(A) = ∅,
(2) A ∪ C(A) = X.
Dem. Consideremos F ∗ : P(Y ) −→ P(X) definida por F ∗ (A) = f −1 (A), para cada A ∈ P(Y )
y veamos que
208
(4) A = B. [(3), f sobreyectiva]
Congruencias booleanas
(F1) 1 ∈ F ,
(F2) si x, y ∈ F , entonces x · y ∈ F ,
(F3) si x ∈ F y x ≤ y, entonces y ∈ F .
Representaremos con F(A) a la familia de todos los filtros de A. Observemos que para toda
A ∈ B se verifica que F(A) = Ø, ya que {1}, A ∈ F(A).
es una congruencia de A.
209
Dem. En primer lugar veamos que
Además,
210
(iii) R(F ) es compatible con : Sea
(F2) Sean
(1) x ∈ 1R , [hip.]
(2) y ∈ 1R , [hip.]
entonces
(3) (x, 1) ∈ R, [(1)]
(4) (y, 1) ∈ R, [(2)]
(5) (x · y, 1) ∈ R, [(3), (4), R ∈ Con(A)]
(6) x · y ∈ 1R , [(5)]
(F3) Si
211
(1) x ∈ 1R , [hip.]
(2) x ≤ y, [hip.]
entonces
(3) (x, 1) ∈ R, [(1)]
(4) (x + y, 1 + y) ∈ R, [(3), R ∈ Con(A)]
(5) (x + y, 1 + y) = (y, 1), [(2)]
(6) y ∈ 1R , [(5)]2
Dem.
212
(12) (y + x , 1) ∈ T , [(10), (1)]
(13) ((x + y ) · (y + x ), 1) ∈ T , [(11), (12), (1)]
(14) f = (x + y ) · (y + x ) ∈ 1T , [(13)]
(15) x · f = x · (x + y ) · (y + x )
= x · (y + x ) [R8]
=x·y [D]
(16) y · f = y · (x + y ) · (y + x ) [(14)]
= y · x, [R8, D]
(17) (x, y) ∈ R(1T ). [(14), (15), (16), T7.4.3]2
Notas.
(i) De lo expuesto resulta que para hallar todas la congruencias de un álgebra de Boole A
podemos proceder de la siguiente manera:
(2) para cada filtro F de A hallamos R(F ) = {(x, y) ∈ A × A : existe f ∈ F tal que
x · f = y · f }.
(ii) En la sección siguiente referida a las álgebras de Boole finitas, aplicaremos el método
anterior a un ejemplo concreto.
Congruencias
T 7.5.1 Sean A un álgebra de Boole finita y F ⊆ A. Entonces las siguientes condiciones son
equivalentes:
(i) F ∈ F(A),
213
⇒ (ii): Sea
Dem. (i) =
(3) f ∈ F , [hip.]
(4) a ≤ f , [(2), (3)]
(5) f ∈ [a). [(4)]
⇒ (i): Ejercicio.
(ii) = 2
Ejemplo
Sea A el álgebra de Boole indicada en la figura
Entonces F(A) = {[0), [a), [b), [c), [d), [e), [f ), [1)}, donde
214
[0) = A, A/[0) = A,
[a) = {a, d, e, 1}, A/[a) = {{0, b, c, f }, {a, d, e, 1}},
[b) = {b, d, f, 1}, A/[b) = {{0, a, c, e}, {b, d, f, 1}},
[c) = {c, e, f, 1}, A/[c) = {{0, a, b, d}, {c, e, f, 1}},
[d) = {d, , 1}, A/[d) = {{0, c}, {a, e}, {b, f }, {d, 1}},
[e) = {e, 1}, A/[e) = {{0, b}, {a, d}, {c, f }, {e, 1}},
[f ) = {f, 1}, A/[f ) = {{0, a}, {b, d}, {c, e}, {f, 1}},
[1) = {1}, A/[1) = {{0}, {a}, {b}, {c}, {d}, {e}, {f }, {1}} A.
A continuación veremos que en las álgebras de Boole finitas los átomos desempeñan un
papel análogo al de las bases en los espacios vectoriales.
(i) a es un átomo de A,
(ii) a verifica:
(a) a = 0,
⇒ (ii):
Dem. (i) =
(2) a · x = 0 ó a · x = a. [(1),(i)]
⇒ (i):
(ii) =
(1) 0 ≤ b ≤ a, [hipótesis]
entonces
215
(2) b = a · b, [(1)]
(3) a · b = 0 ó a · b = a, [(b)]
(4) b = 0 ó b = a. [(2),(3)]
∅, si x = 0
Πx = .
{a ∈ Π(A) : a ≤ x}, en otro caso
Ejemplo
x Πx
0 ∅
a {a}
b {b}
c {c}
d {a, b}
e {a, c}
f {b, c}
1 Π(A)
Dem.
(ii) Si x ∈
/ Π(A), existe x1 ∈ A tal que
(1) x1 · x = 0 y x1 · x = x, [T 7.5.2]
Si
216
(3) x1 · x ∈ Π(A),
entonces
(4) x1 · x ∈ Πx , [(2),(3)]
(5) Πx = ∅. [(4)]
Si
(6) x1 · x ∈
/ Π(A), se repite el razonamiento a partir de (ii).
Dem. Como x = 0, por T 7.5.3 tenemos que Πx = ∅. Además, por la hipótesis, Πx es finito.
Sean
(1) Πx = {a1 , . . . , ak },
(2) y = a1 + a2 + . . . + ak ,
(a) y ≤ x:
(5) a1 + . . . + ak ≤ x. [(4)]
217
(b) x ≤ y:
Si suponemos x · y = 0, entonces
(8) x · y ≤ y ,
(9) x · y ≤ x,
(11) a ≤ x, [(7),(9)]
(12) a ∈ Πx , [(7),(11)]
(13) a ≤ y, [(12),(1),(2)]
(14) a ≤ y · y , [(10),(13)]
Por lo tanto
(16) x · y = 0.
Entonces
(17) x = x · y, [(6),(16)]
de donde resulta x ≤ y.
218
Nota. El T 7.5.4 expresa que, en las álgebras de Boole finitas todo elemento distinto de cero
es la suma de los átomos que lo preceden, lo que significa que conociendo los átomos se pueden
determinar todos sus elementos. Es decir, Π(A) es la información mı́nima que se debe tener
para conocer todos los elementos de un álgebra de Boole finita.
(i) Π(A) = ∅,
(ii) a = 1.
a∈Π(A)
Dem.
(ii) Como 1 = 0,
Además,
(2) Π(A) = Π1 .
En efecto,
(b) Π(A) ⊆ Π1 . [a ≤ 1]
Entonces, a = 1. [(1),(2)]
a∈Π(A)
Teoremas de representación
Dem. Sea f : A −→ P(Π(A)) definida por f (x) = Πx , para cada x ∈ A. Veamos que:
219
(i) f es inyectiva.
Si x1 , x2 ∈ A y
(5) a= a, [(4)]
a∈Πx1 a∈Πx1
(ii) f es sobre.
Sea X ∈ P(Π(A)),
(1) X = {a1 , . . . , ak },
(2) y = a1 + · · · + ak .
(3) b ∈ Πy ,
entonces
(5) b · y = b, [(4)]
220
= (b · a1 ) + . . . + (b · ak ).
Si
(7) b = ai , 1 ≤ i ≤ k,
entonces
(9) b · y = 0, [(6),(8)]
(10) b = 0.
Luego, para algún i, 1 ≤ i ≤ k, se verifica [de (5) y (9)]
(11) b = ai ,
(12) b ∈ X, [(11),(1)]
(13) Πy ⊆ X, [(3),(12)]
(14) X ⊆ Πy . [(1),(2)]
(iii) f (0) = ∅.
a ∈ Πx·y ⇔ a ≤ x · y
⇔ a ≤ x, a ≤ y
⇔ a ∈ Πx ∩ Πy .
(v) f (x ) = Cf (x).
Debemos probar que ΠxI = CΠx .
221
Sea
(1) a ∈ ΠxI , [hip.]
(2) a ≤ x . [(1)]
Si suponemos que
(3) a ≤ x,
entonces
(4) a ≤ x · x , [(2),(3)]
(5) a = 0, absurdo. [(4)]
Luego
(6) a ≤ x,
(7) a ∈ Πx , [(6)]
(8) a ∈ CΠx , [(7)]
(b) CΠx ⊆ Πx :
Sea a ∈ Π(A) tal que
(1) a ∈ CΠx , [hip.]
(2) a ≤ x. [(1)]
(3) a ≤ 1 = x + x .
(4) a ≤ x , [(2),(3), Ej. 7.6.9(ii)]
(5) a ∈ ΠxI . [(4)]
x + y = (x1 + y1 , . . . , xn + yn ),
222
x · y = (x1 · y1 , . . . , xn · yn ),
x = (x1 , x2 , . . . , xn ),
O = (0, 0, . . . , 0),
I = (1, 1, . . . , 1).
n
Entonces Ai , +, ·, , O, I es un álgebra de Boole que se denomina álgebra producto de las
i=1
álgebras Ai , 1 ≤ i ≤ n.
n
Si A1 = A2 = . . . = An = A, entonces Ai se nota An .
i=1
T 7.5.8 Sea A un álgebra de Boole finita tal que |Π(A)| = n. Entonces A y Bn1 son álgebras
isomorfas.
Dem. Como A P(Π(A)) y Bn1 P(Π(Bn1 )), para completar la demostración es suficiente
probar que Π(Bn1 ) tiene n elementos y aplicar T 7.4.2 y T 7.5.6.
Ahora probaremos que Π(Bn1 ) = {e1 , e2 , . . . , en } donde ei = (xij ) con xij = 1 si i = j y
xij = 0 en caso contrario. En efecto, es claro que ei = O para todo i, 1 ≤ i ≤ n. Además,
si b = (bj )1≤j≤n ∈ Bn1 y O ≤ b ≤ ei , entonces 0 ≤ bj ≤ xij , para todo j, 1 ≤ j ≤ n. Luego,
bj = 0 para todo j = i, 1 ≤ j ≤ n y bi = 0 ó bi = 1. Si bi = 0, entonces b = O, en caso
contrario b = ei .
Por lo tanto, ei ∈ Π(Bn1 ) para todo i, 1 ≤ i ≤ n. Además, es claro que éstos son los únicos
átomos. Luego, |Π(Bn1 )| = n.
7.6 Ejercicios
E 7.6.1
Indicar si las siguientes álgebras son bandas, retı́culos o retı́culos distributivos. En caso que
sean retı́culos determinar si tienen primer y último elemento.
223
(ii) IN, ◦, ∗ , donde x ◦ y = max {x, y} y x ∗ y = min {x, y}.
E 7.6.2
Sea A ∈ R0,1 , donde A = {0, a, b, c, 1} y +, · están dadas por las siguientes tablas:
+ 0 a b c 1 · 0 a b c 1
0 0 a b c 1 0 0 0 0 0 0
a a a c c 1 a 0 a 0 a a
b b c b c 1 b 0 0 b b b
c c c c c 1 c 0 a b c c
1 1 1 1 1 1 1 0 a b c 1
Determinar si B ¢ A, siendo
E 7.6.3
E 7.6.4
(i) [a) ¢R A,
224
(iii) si a ≤ b, entonces [b) ⊆ [a).
E 7.6.5
E 7.6.6
E 7.6.7
(i) si x ≤ y y z ≤ w, entonces x · z ≤ y · w y x + z ≤ y + w,
(iii) (x · y) + (z · y) ≤ (x + z) · y,
(iv) x + (y · z) ≤ (x + y) · (x + z),
E 7.6.8
E 7.6.9
225
(ii) Sea A ∈ D0,1 . Si a ∈ Π(A) y x1 , ..., xn ∈ A son tales que a ≤ x1 + ... + xn , probar
que a ≤ xi , para algún i, 1 ≤ i ≤ n.
E 7.6.10
(i) x + (y · z) = (x + y) · (x + z),
E 7.6.11
x 0 a b 1 x 0 c 1
f (x) 0 0 c 1 g(x) 0 a 1
E 7.6.12
Sea A, +, ·, , a, b un álgebra de tipo (2, 2, 1, 0, 0), donde A = {a, b}. Indicar, en cada caso, si
A es un álgebra de Boole.
226
(i) + a b · a b x x
a a b a a a a a
b b a b a b b b
(ii) + a b · a b x x
a a b a a a a b
b b b b a b b a
E 7.6.13
(iv) I : X −→ A, I(x) = 1,
(v) O : X −→ A, O(x) = 0.
Probar que AX , +, ·, , O, I ∈ B.
E 7.6.14
(i) (x ) = x,
(ii) si x + y = 1 y x · y = 0, entonces y = x ,
(iii) 0 = 1, 1 = 0,
(iv) (x + y) = x · y ,
(v) (x · y) = x + y ,
227
(vi) x + (x · y) = x + y,
(vii) x · (x + y) = x · y,
(viii) (x + y ) · z = ((x + z ) · (y + z )) ,
E 7.6.15
Sea A ∈ B. Definimos en A una nueva operación binaria por medio de la siguiente fórmula:
x ⊕ y = (x · y ) + (y · x ).
(i) x ⊕ y = y ⊕ x,
(ii) x ⊕ x = 0,
(iii) 0 ⊕ x = x,
(iv) 1 ⊕ x = x .
E 7.6.16
(a) a + b = b,
(b) a · b = a,
(c) a + b = 1,
(d) a · b = 0.
(ii) si x · y = x · z y x · y = x · z, entonces y = z.
228
E 7.6.17
(ii) Indicar todas las subálgebras de las álgebras de Boole cuyos diagramas son:
E 7.6.18
(ii) Sean A, B ∈ B y sea h : A −→ B. Probar que las siguientes condiciones son equivalentes:
(b) h verifica
(c) h verifica
(3) h(x · y) = h(x) · h(y),
229
8 Sistemas proposicionales
Ejemplos
(ii) Llamaremos álgebra de las formas booleanas al álgebra absolutamente libre ForBol [X] =
F or[X], F cuando elegimos como conjunto de operaciones a F0 = ∅, F1 = {∼} y
F2 = {∧, ∨}.
Sustituciones
Ejemplo
ρ(x1 ) = x3 → x2 ,
ρ(x2 ) = ∼ x1 ,
ρ(x3 ) = x4 ∨ x2 ,
y sea
230
p = ((x1 → x2 ) → (x3 → (x1 ∧ x2 ))) ∈ F orX,
entonces
Valuaciones
D 8.2.1 Diremos que una función C : P(F or[X]) −→ P(F or[X]) es un operador de clausura
sobre F or[X] si para todo H, K ∈ P(F or[X]) se verifican:
D 8.2.2 Llamaremos sistema proposicional (s.p.) o lógica de orden cero a toda terna C =
F or[X], F, C , donde C es un operador de clausura sobre F or[X] y diremos que los elementos
de C(∅) son los C—teoremas de C.
231
Fragmentos y extensiones de un sistema proposicional
(i) F ⊂ F ,
Matrices
Consecuencias semánticas
D 8.3.2 Sea M(A) = A, F, U una matriz dada. Para cada H ⊆ F or[X] y cada p ∈ F or[X]
diremos que p es consecuencia semántica de H según la matriz M(A) y escribiremos H |=A p,
si existen p1 , p2 , . . . , pn ∈ H tales que para toda valuación v ∈ Hom(F or[X], A), las hipótesis
v(p1 ) ∈ U, v(p2 ) ∈ U, . . . , v(pn ) ∈ U implican v(p) ∈ U.
Se verifica sin dificultad que la aplicación CA : P(F or[X]) −→ P(F or[X]) tal que a cada
H ⊆ F or[X] le asigna el conjunto CA (H) es un operador de clausura sobre F or[X]. Los
operadores de clausura obtenidos por matrices se llaman operadores semánticos.
232
D 8.3.4 Diremos que un operador de clausura C sobre F or[X], F es semántico si existe una
matriz M(A) = A, F, U tal que C = CA .
Es decir un s.p. es semántico si existe una matriz M(A) tal que para todo H ⊆ F or[X] se
verifique que
C(H) = CA (H) = {p ∈ F or[X] : H |=A p}.
Ejemplos
al s.p. CB2 = F or[X], F, CB2 lo llamaremos la versión semántica del sistema proposi-
cional clásico.
(a) I2 = B2 ,
al s.p. CI2 = F or[X], F, CI2 lo llamaremos la versión semántica del sistema proposicional
implicativo clásico.
233
x ∧ y = min{x, y},
x ∨ y = max{x, y},
1, si x = 0
¬x = ,
0, en otro caso
1, si x ≤ y
x→y= ,
y, en otro caso
(c) U = {1},
x → y = min{1, 1 − x + y},
∼ x = 1 − x,
(c) U = {1},
234
(vi) Dada la matriz M(Ln+1 ) = Ln+1 , {→, ∼}, U donde:
1 2 n−1
(a) Ln+1 = {0, , , . . . , , 1} ⊂ [0, 1],
n n n
(b) → y ∼ son las indicadas en (v2) del ejemplo anterior,
(c) U = {1},
al s.p. CLn+1 = F or[X], F, CLn+1 lo llamaremos la versión semántica del sistema proposi-
cional de Lukasiewicz (n + 1)—valuado.
M(A)—tautologı́as
D 8.3.6 Sea M(A) = A, F, U una matriz asociada a For[X]. Diremos que p ∈ F or[X] es
una M(A)—tautologı́a si v(p) ∈ U , para toda A—valuación v.
Axiomas
Reglas de inferencia
Usualmente escribiremos
p1 , p2 , · · · , pn
r:
p
en lugar de p = r(p1 , p2 , · · · , pn ).
235
Demostraciones formales
(1) p1 ∈ H ∪ A,
(2) p2 ∈ H ∪ A,
..
.
pi1 , pi2 , . . . , pim
(j) pj ∈ H ∪ A, o rt : , is ∈ {1, 2, . . . , j − 1}, t ∈ {1, 2, . . . , k},
pj
..
.
(n) pn es p.
Consecuencias sintácticas
La aplicación CS : P(F or[X]) −→ P(F or[X]) tal que a cada H ⊆ F or[X] le asigna el
conjunto CS (H) = {p ∈ F or[X] : H p} es un operador de clausura.
236
Es decir un s.p. es sintáctico si existen axiomas y reglas de inferencia tales que para todo
H ⊆ F or[X] se verifique
CS (H) = {p ∈ F or[X] : H p}.
Teoremas sintácticos
La definición de demostración formal se puede generalizar, de modo tal que podamos usar
los teoremas sintácticos que ya han sido demostrados. En efecto, supongamos que estamos
construyendo una demostración formal de la fórmula p, a partir del conjunto H y nos damos
cuenta que para obtener la fórmula del paso (j) nos hace falta el teorema sintáctico q que ya
habı́amos obtenido. Entonces podemos agregar todas las fórmulas de la demostración de q y
continuar con la obtencion de la demostración de la fórmula p.
Pero es claro, que la única fórmula de la demostración de q en la que estamos interesados
es la propia q. Entonces, para simplificar, podemos modificar la definición de demostración
formal del siguiente modo:
(1) p1 ∈ H ∪ TS ,
(2) p2 ∈ H ∪ TS ,
..
.
pi1 , pi2 , . . . , pim
(j) pj ∈ H ∪ TS , o rt : , is ∈ {1, 2, . . . , j − 1}, t ∈ {1, 2, . . . , k}
pj
..
.
(k) pn es p.
237
Simplificación de las notaciones
(i) Cualquier s.p. que se obtenga de C, agregando operaciones a F y conservando los axiomas
y reglas (pudiendo además, agregar axiomas o reglas) es un s.p. sintáctico, ampliación
del primero.
(ii) Cualquier s.p. que se obtenga de C, eliminando operaciones de F y los axiomas y reglas
en que figuran las operaciones suprimidas, y conservando los restantes axiomas y reglas
es un s.p. sintáctico, fragmento del primero.
Todos los ejemplos de s.p. semánticos que hemos indicado son implicacionales.
238
Ejemplos de reglas de inferencia para s.p. implicacionales sintácticos
(i) modus ponens: Sea P = {(p, p → q) : p, q ∈ F or[X]}, llamaremos regla de modus ponens
a mp : P −→ F or[X], definida por mp (p, p → q) = q, esto es
p, p → q
mp : ,
q
(ii) modus tollens: Sea P = {(p, ∼ q →∼ p) : p, q ∈ F or[X]}, llamaremos regla de modus
tollens a mt : P −→ F or[X], definida por mt (p, ∼ q →∼ p) = q, esto es
p, ∼ q →∼ p
mt : ,
q
(iii) contraposición: Sea P = {p → q : p, q ∈ F or[X]}, llamaremos regla de contraposición a
c : P −→ F or[X], definida por c(p → q) =∼ q →∼ p, esto es
p→q
c: .
∼ q →∼ p
Los elementos de ACl son las fórmulas indicadas en A1, . . . , A11, y las que se pueden obtener
de ellas por la regla de sustitución.
(A1) x1 → (x2 → x1 ),
(A3) (x1 ∧ x2 ) → x1 ,
(A4) (x1 ∧ x2 ) → x2 ,
(A6) x1 → (x1 ∨ x2 ),
239
(A7) x2 → (x1 ∨ x2 ),
(A9) ∼ x1 → (x1 → x2 ),
(A10) (x1 →∼ x1 ) →∼ x1 ,
(A11) (∼ x1 → x1 ) → x1 .
Observemos que podemos eliminar la regla de sustitución usando axiomas esquemas, del
siguiente modo:
Los axiomas son esquemas de la forma:
(E1) p → (q → p),
(E3) (p ∧ q) → p,
(E4) (p ∧ q) → q,
(E6) p → (p ∨ q),
(E7) q → (p ∨ q),
(E9) ∼ p → (p → q),
(E10) (p →∼ p) →∼ p,
(E11) (∼ p → p) → p.
Entonces cualquier fórmula que tenga el esquema (la forma esquemática) de alguno de los
E1,. . . ,E11 es un axioma. Ası́ por ejemplo,
240
((∼ x1 → x1 ) → (x1 ∧ x2 )) → (((x2 → x3 ) → (x1 ∧ x2 )) → (((∼ x1 → x1 ) ∨ (x2 → x3 )) →
(x1 ∧ x2 ))
(1) p por (∼ x1 → x1 ),
(T1) p→p
(5) p → p. [(1),(4),mp ]
p
(R1) ,
q→p
(1) p, [hip.]
(3) q → p. [(1),(2),mp ]
p → (q → r)
(R2) ,
(p → q) → (p → r)
241
(3) (p → q) → (p → r). [(1),(2),mp ]
(1) p → q, [hip.]
(3) p → p, [T1]
(p → q) → (p → r)
(R4) ,
q → (p → r)
242
(3) q → (p → q), [E1]
p → (q → r)
(R5) ,
q → (p → r)
T 8.6.1 Sea C = (F or[X], {∧, ∨, →, ∼}, Cl ) y H ⊆ F or[X], entonces las siguientes condiciones
son equivalentes:
(i) H (p → q),
(ii) H ∪ {p} q.
Dem.
(1) p1 , [H ∪ TS ]
(2) p2 , [H ∪ TS ]
..
.
(n) p → q.
243
Entonces
(1) p,
(2) p1 ,
(3) p2 ,
..
.
(n + 1) p → q.
(n + 2) q, [(1),(n + 1),mp ]
Caso 1. q ∈ TS ∪ H:
(1) q, [hipótesis]
(3) p → q. [(1),(2) y mp ]
Por lo tanto,
H (p → q).
Caso 2. q ∈ {p}:
(2) ∅ ⊆ H,
244
Hipótesis de inducción: Supongamos que el enunciado vale para toda fórmula r cuya
demostración es de longitud menor o igual que n − 1 y sea
(1) p1 ,
(2) p2 ,
..
.
(n) q,
Caso 1. q ∈ H ∪ TS ∪ {p}.
Es análogo al caso 1 de n = 1.
Caso 2. q ∈
/ H ∪ TS ∪ {p}.
(1) p1 ,
..
.
(j) pj ,
..
.
(n − 1) pj → q,
(n) q.
Como pj y pj → q tienen una demostración a partir de H∪{p}, de longitud menor o igual que
n − 1, entonces por la hipótesis de inducción tenemos que H (p → pj ) y H (p → (pj → q)).
Por lo tanto podemos escribir
(1) q1 ,
..
. [demostración de p → pj a partir de H,
(t) p → pj , (qi = p, 1 ≤ i ≤ t − 1)]
245
(1) r1 ,
..
. [demostración de p → (pj → q) a partir de H,
(s) p → (pj → q). (ri = p, 1 ≤ i ≤ s − 1)]
Entonces,
(1) q1 ,
..
.
(t) p → pj ,
(t + 1) r1 ,
..
.
(m + 2) (p → pj ) → (p → q), [(m),(m+1),mp ]
(m + 3) p → q. [(t),(m+2),mp ]
(i) H p,
(ii) H |=B2 p.
246
8.8 Ejercicios
Para el cálculo proposicional clásico C = (F or[X], →, ∧, ∨, ∼, Cl ), tomamos como axiomas los
elementos de UCl = {E1, ..., E11} dados en teorı́a y como regla de inferencia
p, p → q
mp :
q
E 8.8.1
(i) UCl ⊆ TS ,
(ii) si p, p → q ∈ TS , entonces q ∈ TS ,
E 8.8.2
(O2) si p ≤ q y q ≤ r, entonces p ≤ r.
E 8.8.3
E 8.8.4
247
(iv) (p → q) → ((p ∧ r) → (q ∧ r)),
E 8.8.5
(i) q → r ≤ p → r, (ii) r → p ≤ r → q,
(iii) p ∧ r ≤ q ∧ r, (iv) r ∧ p ≤ r ∧ q.
E 8.8.6
248
9 Bibliografı́a
[1] A. Barnes, J.M. Mark, Una Introducción algebraica a la lógica matemática, EUNIBAR,
1975.
[2] C. Berge, The theory of graphs and its applications, New York, John — Wiley, 1962.
[6] J.L. Gersting, Mathematical structures for computer science, New York, 2nd ed.,W. H.
Freeman and Co., 1987.
[7] A.G. Hamilton, Lógica para matemáticos, Madrid, Ed. Paraninfo, 1981.
[8] I.S. Levy, Discrete structures of computer sciences, New York, John Wiley, 1980.
[9] L. Oubiña, Introducción a la teorı́a de conjuntos, 7ma ed., Bs. As., Eudeba, 1974.
[10] A. Tarski, Introducción a la lógica y a la metodologı́a de las ciencias deductivas, 2da ed.,
Madrid, Espasa-Calpe, 1968.
[11] J. Whitesitt, Boolean algebra and its applications, London, Addison — Wesley,1961.
Bibliografı́a básica
1. C. Berge, The Theory of Graphs and its Applications, John Wiley, New York, 1962.
249
5. J. Gersting, Mathematical Structures for Computer Science, W. H. Freeman and Co.,
New York, 1987.
8. I. Levy, Discrete Structures for Computer Sciences, John Wiley, New York, 1980.
11. J. Whitesitt, Boolean Algebra and its Applications, Addison—Wesley, London, 1962.
Bibliografı́a de consulta
9. F. Hohn, Applied Boolean Algebra, The Macmillan Company, New York, Collier — Macmil-
lan Limited, London.
250
10. E. Mendelson, Boolean Algebra and Switching Circuits, Mc Graw—Hill, New York, 1970.
12. L. Oubiña, Introducción a la teorı́a de conjuntos, 7ed , Buenos Aires, Eudeba, 1974.
251