Álgebra Capítulo 1 (Lógica)

1. CAP¶ITULO 1
NOCIONES ELEMENTALES DE L ¶OGICA
MATEM ¶ATICA
Estudiaremos brevemente un lenguaje no contradictorio ni ambivalente que nos per-
mitir¶a introducirnos a la Matem¶atica: la L¶ogica Matem¶atica, que estudia las leyes que
regulan el razonamiento.
Por ¯nes did¶acticos la dividimos en
a)l¶ogica proposicional,
b)l¶ogica funcional.
1.1. L¶OGICA PROPOSICIONAL
En la l¶ogica proposicional consideraremos dos elementos b¶asicos:Proposiciones,Conec-
tivos.
1.1.1. Proposiciones
Son rases" sobre las cuales podemos decidir, un¶³vocamente, sobre la verdad (V) o
falsedad (F) de ellas.
As¶³ entonces, una proposici¶on es una frase que esVoF, no existiendo la posibilidad
de obtener ambas decisiones conjuntamente (Principio del tercero excluido).
Las proposiciones las denotamos por letras min¶usculasp,q,r, etc., que resumir¶an, en
si mismo, el signi¯cado particular que tengan al interior de una situaci¶on concreta.
Ejemplo 1.1.1.
1.\p" resumir¶a, al interior de ¶este ejemplo, a la proposici¶on: \Hoy es Martes 10 de
Mayo\, y denotamosp: \Hoy es Martes 10 de Mayo".
1

2. 2 UNIVERSIDAD DE SANTIAGO DE CHILE, FACULTAD DE CIENCIA
2.Las siguientes rases" son proposiciones:
q:x+ 4 = 9yx= 5 (esV)
r:Sixes un n¶umero real, entonces su cuadrado es no negativo (esV):
Observaci¶on1.1.1.No son proposiciones los interrogativos y los imperativos.
1.1.2. Conectivos
S¶³mbolos que, junto con las proposiciones b¶asicas, nos permiten crear nuevas proposi-
ciones, son:
»:se lee o",
^:se lee \y",
_:se lee \ y/o",
):se lee \: : :implica: : :" ¶o \si,: : :entonces,: : :",
,:se lee \: : :equivalente con: : :".
Observaci¶on1.1.2.El conectivo \»" se usa antes de una proposici¶on, y los restantes
conectivos se usan entre dos proposiciones.
Ejemplo 1.1.2.Sip,q,rson proposiciones, entonces tambi¶en son proposiciones:
1.»p
2.p^q
3.p_q
4.p)q
5.p,q
6.p^(q_r)
7.[(»p)^(q_r)])q
1.1.3. Tablas de Verdad
Las proposiciones compuestas, es decir, aquellas que contienen al menos un conectivo,
tienen, naturalmente, un valor veritativo, y para las proposiciones compuestas b¶asicas ese
valor veritativo lo damos en las siguientes ablas de verdad".

3. CAP
¶
ITULO 1 NOCIONES ELEMENTALES DE L
¶
OGICA MATEM
¶
ATICA 3
Tabla de Verdad de la Negaci¶on(»)
Dada la proposici¶on b¶asica \p" , existe la negaci¶on de ella, denotada»p, que se lee
op", proposici¶on que tiene la siguiente tabla de verdad.
p »p
V F
F V
Observaci¶on1.1.3.Es claro que el valor veritativo de»pes el contrario dep. Por ejemplo,
si \p" es
p: \Hoy llueve"
es verdadero entonces»pes
»p: \Hoy no llueve"
es falso.
Tabla de Verdad de la Conjunci¶on(^)
Dadas las proposiciones \p", \q", existe la conjunci¶on de ellas, denotadap^q, que se
lee \pyq", proposici¶on tal que su tabla de verdad es
p q p^q
V V V
V F F
F V F
F F F
Observaci¶on1.1.4.La conjunci¶on es verdadera s¶olo si las proposiciones que la componen
lo son.
Tabla de Verdad de la Disyunci¶on(_)
Dadas las proposiciones \p", \q" existe la disyunci¶on de ellas, denotadap_qque se
lee \poq", proposici¶on tal que su tabla de verdad es
p q p_q
V V V
V F V
F V V
F F F

4. 4 UNIVERSIDAD DE SANTIAGO DE CHILE, FACULTAD DE CIENCIA
Observaci¶on1.1.5.
1.La disyunci¶on es verdadera siempre, menos cuando las proposiciones que la compo-
nen son ambas falsas.
2.La disyunci¶on presentada es incluyente, es decir, admite como verdadera a la proposi-
ci¶onp_qcuando ambas proposiciones que la componen lo son, sin embargo, si de-
seamos la disyunci¶on excluyente, la denotamospYq, en este caso, si las proposiciones
p,qson ambas verdaderas entoncespYqes falsa.
Tabla de Verdad de la Implicaci¶on())
Dadas las proposiciones \p", \q" existe la implicaci¶on depconq, denotadap)q,
que se lee \pimplicaq" o \si ocurrep, entonces ocurreq", proposici¶on tal que su tabla de
verdad es
p q p)q
V V V
V F F
F V V
F F V
Observaci¶on1.1.6.La implicaci¶on es verdadera siempre, menos cuando elantecedentep
es verdadero y elconsecuenteqes falso.
Tabla de Verdad de la Equivalencia(,)
Dadas las proposiciones \p", \q", existe la equivalencia depconq, denotadap,q,
que se lee \pequivalenteq" o \psi y s¶olo siq", proposici¶on tal que su tabla de verdad es
p q p,q
V V V
V F F
F V F
F F V
Observaci¶on1.1.7.Resulta natural que la equivalencia sea verdadera cuando las dos
proposiciones que la componen tienen el valor el mismo valor veritativo.
Ejemplo 1.1.3.Determine el valor veritativo de»(p^q),[(»p)_(»q)].
Soluci¶on.Su tabla de verdad es:
pqp^q»(p^q)»p»q(»p)_(»q)»(p^q),[(»p)_(»q)]
VVV F FF F V
VFF V FV V V
FVF V VF V V
FFF V VV V V

5. CAP
¶
ITULO 1 NOCIONES ELEMENTALES DE L
¶
OGICA MATEM
¶
ATICA 5
Ejemplo 1.1.4.Determine el valor veritativo de[p^(q_r)])r.
Soluci¶on.Su tabla de verdad es
pqrq_rp^(q_r)[p^(q_r)])r
VVVV V V
VVFV V F
VFVV V V
VFFF F V
FVVV F V
FVFV F V
FFVV F V
FFFF F V
En el ejemplo anterior, dado que consideramos tres proposiciones b¶asicas, el total
de variaciones de tres elementos, cada uno con respuestas dicot¶omica (grupos con tres
elementos donde interesa el orden) es 2
3
= 8. Si son 4 las proposiciones b¶asicas entonces
el total de variaciones, en estas condiciones, es 2
4
= 16.
Ejemplo 1.1.5.Si(»p^q))res Falso, determine el valor de verdad de
(q_s))»(r^p).
Soluci¶on.Como (»p^q))res Falso entonces»p^qes Verdadero yres Falso; es
decir, conseguimos»pesV,qesV,resF.
Dado queqesVentonces la proposici¶onq_sesV, adem¶as, comoresFentonces
r^pesFde donde»(r^p) esV.
Finalmente, (q_s))»(r^p) esV.
1.1.4. Tautolog¶³a, Contradicci¶on, Contingencia
Tautolog¶³a
Una proposici¶on compuesta que siempre es verdadera, es unaTautolog¶³a. Una tau-
tolog¶³a la denotamos porI.
Ejemplo 1.1.6.Demuestre quep_(»p)es tautolog¶³a.
Soluci¶on.Debemos encontrar su tabla de verdad y veri¯car que siempre es verdadera
p »p p_(»p)
V F V
F V V
Ejemplo 1.1.7.Demuestre que»(»p),pes tautolog¶³a.

6. 6 UNIVERSIDAD DE SANTIAGO DE CHILE, FACULTAD DE CIENCIA
Soluci¶on.Su tabla de verdad es
p»p»(»p)»(»p),p
VF V V
FV F V
Ejemplo 1.1.8.Demuestre quefp)[q^(»q)]g )(»p)es tautolog¶³a.
Soluci¶on.Su tabla de verdad es
pq»qq^(»q)p)[q^(»q)]»pfp)[q^(»q)]g )(»p)
VVF F F F V
VFV F F F V
FVF F V V V
FFV F V V V
Esta proposici¶on se llama \m¶etodo de demostraci¶on por reducci¶on al absurdo".
Contradicci¶on
Una proposici¶on que siempre es falsa, es unaContradicci¶on. Una contradicci¶on la
denotamos por 0.
Ejemplo 1.1.9.Demuestre quep^(»p)es una contradicci¶on.
Soluci¶on.Debemos encontrar la tabla de verdad de la proposici¶on y veri¯car que siempre
es falsa
p »p p^(»p)
V F F
F V F
Contingencia
Una proposici¶on que no es tautolog¶³a ni contradicci¶on se llamaContingencia.
Ejemplo 1.1.10.Demuestre quep_(»q)es una contingencia.
Soluci¶on.Su tabla de verdad es
p q »q p_(»q)
V V F V
V F V V
F V F F
F F V V
Concluimos quep_(»q) es una contingencia.

7. CAP
¶
ITULO 1 NOCIONES ELEMENTALES DE L
¶
OGICA MATEM
¶
ATICA 7
Leyes Fundamentales del¶Algebra de Proposiciones
Identidad p^I,p p _0,p
p^0,0 p_I,I
Idempotencia p^p,p p _p,p
Involuci¶on »(»p),p
Complemento »0,I »I,0
p^(»p),0 p_(»p),I
Conmutatividadp^q,q^p p _q,q_p
Asociatividadp^(q^r),(p^q)^r p _(q_r),(p_q)_r
Distributividadp^(q_r),(p^q)_(p^r)p_(q^r),(p_q)^(p_r)
De Morgan »(p^q),(»p)_(»q) »(p_q),(»p)^(»q)
Observaci¶on1.1.8.Una ley fundamental, muy importante es (p)q),((»p)_q).
Ejemplo 1.1.11.Si de¯nimosry¢comoprq= (»p)^(»q),p¢q= (»p)_(»q),
demuestre, sin usar tablas de verdad que
a)prp,»p.
b)p^q,»(p¢q).
c)p_q,»(prq).
Soluci¶on.
a)prp,(»p)^(»p),»p.
b)»(p¢q),»[(»p)_(»q)],»(»p)^ »(»q),p^q.
c)»(prq),»[(»p)^(»q)],»(»p)_ »(»q),p_q.
Ejemplo 1.1.12.Sin usar tablas de verdad, demuestre quep_[(»p)^q],p_q.
Soluci¶on.
p_[(»p)^q],[p_(»p)]^[p_q],I^[p_q],p_q:
Ejemplo 1.1.13.Demuestre quep)(p_q)es una tautolog¶³a.

8. 8 UNIVERSIDAD DE SANTIAGO DE CHILE, FACULTAD DE CIENCIA
Soluci¶on.
[p)(p_q)],[»p_(p_q)],[(»p_p)_q],I_q,I:
Ejemplo 1.1.14.Demuestre que[p^(p)q)])qes una tautolog¶³a.
Soluci¶on.
[p^(p)q)])q, »[p^(p)q)]_q
, » fp^[(»p)_q]g _q
, f(»p)_ »[(»p)_q]g _q
, f(»p)_[p^(»q)]g _q
, f[(»p)_p]^[(»p)_(»q)]g _q
, f[I^[(»p)_(»q)]]g _q
,[(»p)_(»q)]_q
,(»p)_[(»q)_q]
, »p_I
,I:
Ejemplo 1.1.15.Demuestre, sin usar tablasf[(p^q)_r]^ »qg _q,(r_q).
Soluci¶on.
f[(p^q)_r]^ »qg _q, f[(p^q)^ »q]_(r^ »q)g _q
, f[p^(q^ »q)]_(r^ »q)g _q
, f[p^0]_(r^ »q)g _q
, f0_(r^ »q)g _q
,(r^ »q)_q
,(r_q)^(»q_q)
,(r_q)^I
,r_q:
1.2. L¶OGICA FUNCIONAL
1.2.1. Cuanti¯cadores
Consideremos la siguiente frase: \xes un n¶umero par". Claramente esta frase no es
proposici¶on; es una f¶ormula proposicional y la denotamos porp(x):\xes un n¶umero par".
>C¶omo transformar una f¶ormula proposicional (FP) a proposici¶on?.

9. CAP
¶
ITULO 1 NOCIONES ELEMENTALES DE L
¶
OGICA MATEM
¶
ATICA 9
1.Reemplazando \x" por un elemento determinado de un conjunto especi¯coD, llama-
do Dominio de la variablex. As¶³, si para esta FP,Des el conjunto cuyos elementos
son 1;2;3;4, entonces:
p(1) : 1 es un n¶umero par, es una proposici¶on, ya quep(1) es falso.
p(2) : 2 es un n¶umero par, es una proposici¶on, ya quep(2) es verdadero.
2.Anteponiendo a la FP un s¶³mbolo que responde a la pregunta >cu¶antos elementos
deDveri¯canp(x)?.
Estos s¶³mbolos, llamados Cuanti¯cadores, son:
8:signi¯ca odos".
9:signi¯ca \algunos".
adicionalmente tenemos
9! :signi¯ca \un ¶unico".
Ejemplo 1.2.1.
1.8xdeD:p(x)se lee: odos los elementos deDson n¶umeros pares" y, claramente
es una proposici¶on, ya que es falsa.
2.9xdeD:p(x)se lee:\alg¶un elemento deDes un n¶umero par", es una proposici¶on,
ya que es verdadera.
3.9!xdeD:p(x)se lee:\un ¶unico elemento deDes un n¶umero par", claramente es
una proposici¶on, ya que es falsa.
Observaci¶on1.2.1.
1.Adelant¶andonos, escribiremos:8x2D:p(x) en lugar de8xdeD:p(x).
2.Las de¯niciones, tanto en Matem¶atica como en otras Ciencias que usan la Matem¶atica,
de¯nen sus conceptos y declaran sus proposiciones usando, en particular, los cuan-
ti¯cadores. Necesitamos conocer las leyes que regulan la cuanti¯caci¶on.
1.2.2. Leyes de la Cuanti¯caci¶on
Se cumple
1.»[8x2D:p(x)], 9x2D:»p(x).
2.»[9x2D:p(x)], 8x2D:»p(x).

10. 10 UNIVERSIDAD DE SANTIAGO DE CHILE, FACULTAD DE CIENCIA
Demostraci¶on.
1.Si»[8x2D:P(x)] esVentonces8x2D:p(x) esF, luego9x2D:»p(x) esV.
Si»[8x2D:P(x)] esFentonces8x2D:p(x) esVde donde9x2D:»p(x)
esF.
Por lo anterior concluimos que»[8x2D:p(x)], 9x2D:»p(x) es tautolog¶³a.
2.Si»[9x2D:P(x)] esV) 9x2D:p(x) esF) 8x2D:»p(x) esV.
Si»[9x2D:P(x)] esF) 9x2D:p(x) esV) 8x2D:»p(x) esF.
As¶³ entonces:»[9x2D:p(x)], 8x2D:»p(x) es una tautolog¶³a.
Ejemplo 1.2.2.Se de¯ne, para los conjuntosAyB, la noci¶on de \subconjunto", denotado
AµBcomo
AµB,[8x:x2A)x2B]:
Determine en que condicionesAno es subconjunto deB.
Notaci¶on:»(AµB) =A6½B.
Soluci¶on.ComoAµB,[8x:x2A)x2B] entonces
A6½B, »[8x:x =2A_x2B]
, 9x:»(x =2A_x2B)
, 9x:x2A^x =2B:
1.3. EJERCICIOS PROPUESTOS
Ejercicio 1.1.Indique el valor veritativo de las siguientes proposiciones
a)Todo n¶umero natural es mayor que 2.
b)(8x2R)(9y2R) :xy >0.
c)9x2N:x
2
>100.
Ejercicio 1.2.Use tablas de verdad para clasi¯car las siguientes proposiciones como:
Tautolog¶³a, Contradicci¶on o Contingencia.
a)[(p_q))q])(»p_q).
b)(p)q))[(p^r))(q^r)].
c)»[(»p)q)^ »(p^q)]^q.
d)[(p)q)^(q)r)])(p)r).

11. CAP
¶
ITULO 1 NOCIONES ELEMENTALES DE L
¶
OGICA MATEM
¶
ATICA 11
Ejercicio 1.3.Demuestre mediante Algebra de proposiciones
a)[(p_q)^ »p],(»p^q).
b)[»(p_q)_(»p^q)],»p.
c)[p)(q^r)],[(p)q)^(p)r)].
Ejercicio 1.4.Usando los datos proporcionados en cada caso, obtenga el valor veritativo
pedido
a)Si se sabe quep^qesVy adem¶asr^pesF, determine el valor de (r_q))(r^q).
Resp.F
b)Sabiendo quep)qesF,r^pesF, determine el valor veritativo de
i)p,r. Resp.F
ii)»[p^(»r)]. Resp.F
c)De la falsedad de (p)»q)_(»r)s) deduzca el valor veritativo de
i)(»p^ »q)_(»q). Resp.F
ii)[(»r_q)^q],[(»q_r)^s]. Resp.F
iii)(p)r))[(p_q)^(»q)]. Resp.V
Ejercicio 1.5.Sip#qsigni¯ca ipy niq", >cu¶ales de las siguientes proposiciones son
tautolog¶³as?.
a)[(p#q)#(q#p)],(p_q).
b)»(p^q),p#q.
c)(p#q),»(p_q).
d)»(p#q),p_q.
Ejercicio 1.6.Sabiendo que la proposici¶on compuesta»pY[q)(»r_ »s)] es ver-
dadera, determine el valor de verdad de [»p)(»r_q)]_s. Resp.V
Ejercicio 1.7.Demuestre que cada uno de los siguientes argumentos es v¶alido (es decir,
que la proposici¶on es una tautolog¶³a), usando el ¶algebra de proposiciones.
a)[(p)q)^p])q.
b)[(p)q)^(»p)])»p.
c)[(p)q)^(q)r)])(p)r).

12. 12 UNIVERSIDAD DE SANTIAGO DE CHILE, FACULTAD DE CIENCIA
d)[(p_q)^(»p)])q.
e)(p^q))p, (p^q))q.
f)p)(p_q).
Adem¶as, identi¯que cada una de las siguientes rases" con alguno de los argumentos
anteriores
1.Jos¶e tiene un cuaderno o un l¶apiz , Jos¶e no tiene un cuaderno, por lo tanto, Jos¶e tiene
un l¶apiz.
2.Si Jos¶e gana el concurso entonces obtendr¶a una beca, Jos¶e gan¶o el concurso, por lo
tanto, Jos¶e obtendr¶a la beca.
3.Si Jos¶e gana el concurso entonces obtendr¶a una beca, Jos¶e no obtuvo la beca, por lo
tanto, Jos¶e no gan¶o el concurso.
4.Todos los monos son desordenados, luego, los monos son desordenados o son peludos.
5.Si no llueve entonces se perder¶a la cosecha, si se pierde la cosecha entonces no se
podr¶a cancelar la deuda entonces, si no llueve, no se podr¶a cancelar la deuda.
6.Ning¶un estudiante es ocioso y Mar¶³a es una excelente bailarina, luego, ning¶un estu-
diante es ocioso.