João Sampaio - Introdução à Teoria dos Conjuntos

Prévia do material em texto

1
L¶ogica Elementar
Neste cap¶³tulo, apresentamos uma introdu»c~ao µa l¶ogica, que nos ser¶a su¯ciente como
ferramenta de trabalho nos cap¶³tulos posteriores.
1.1 Proposi»c~oes e seus conectivos
O estudo da l¶ogica ¶e o estudo dos princ¶³pios e m¶etodos usados para distinguir argumentos
v¶alidos dos n~ao v¶alidos. O prop¶osito deste cap¶³tulo preliminar em l¶ogica ¶e ajudar o leitor
a entender os princ¶³pios e m¶etodos usados em cada passo de uma demonstra»c~ao.
O ponto de partida em l¶ogica ¶e o termo \proposi»c~ao", que ¶e usado num sentido
t¶ecnico. Por uma proposi»c~ao queremos dizer uma declara»c~ao que ¶e verdadeira ou falsa,
mas n~ao ambos. N~ao ¶e necess¶ario que saibamos se a proposi»c~ao ¶e verdadeira ou falsa;
a ¶unica quali¯ca»c~ao exigida ¶e que ela deve ser de¯nitivamente uma coisa ou outra.
Habitualmente, podemos determinar imediatamente se uma proposi»c~ao ¶e verdadeira ou
falsa, mas em alguns casos um pouco de esfor»co ¶e preciso, e em outros casos pode
ser imposs¶³vel chegar a uma conclus~ao. Os seguintes exemplos dever~ao ilustrar o que
queremos dizer.
Exemplo 1.1 Cada uma das seguintes frases ¶e uma proposi»c~ao.
(a) Londrina ¶e uma cidade no estado do Paran¶a.
(b) 2 + 1 ¶e 5.
(c) O d¶³gito na 105a casa decimal, na expans~ao decimal de
p
3, ¶e 7.
(d) A lua ¶e feita de queijo mineiro.
(e) N~ao h¶a vida inteligente em Marte.
(f) Est¶a chovendo.
Claramente, (a) ¶e verdadeira, enquanto (b) e (d) s~ao falsas. Podemos ter d¶uvidas
quanto ao status (verdadeiro ou falso) de (c) e (e). A veracidade ou falsidade da senten»ca
(f) depende das condi»c~oes meteorol¶ogicas no instante em que essa declara»c~ao ¶e feita.
1
2 L¶ogica Elementar
Exemplo 1.2 Nenhuma das frases seguintes ¶e uma proposi»c~ao, porque n~ao faz sentido
questionar se alguma delas ¶e verdadeira ou falsa.
(a) Venha µa nossa festa!
(b) Tudo bem com voce^?
(c) Tiau, benzinho.
As proposi»c~oes do Exemplo 1.1 s~ao todas proposi»c~oes simples. Uma combina»c~ao
de duas ou mais proposi»c~oes ¶e uma proposi»c~ao composta. Por exemplo, \2 + 1 ¶e 5
e o d¶³gito na 105a casa decimal na expans~ao decimal de
p
3 ¶e 7" ¶e uma proposi»c~ao
composta.
Estamos familiarizados com o uso de letras para representar n¶umeros na ¶algebra.
No estudo da l¶ogica usamos letras, tais como p, q, r, : : : para representar proposi»c~oes.
Uma letra, tal como p, pode representar uma proposi»c~ao simples ou composta. A menos
que digamos em contr¶ario, usaremos letras mai¶usculas P , Q, R, : : : para representar
proposi»c~oes compostas. Existem muitos modos de se ligar proposi»c~oes tais como p,
q, r, : : : para formar proposi»c~oes compostas, mas apenas cinco modos s~ao usados
freqÄuentemente. Estes cinco conectivos comuns s~ao (a) \n~ao", simbolizado por »;
(b) \e", simbolizado por ^; (c) \ou", simbolizado por _; (d) \se : : : ent~ao : : : ",
simbolizado por !; e (e) \ : : : se e somente se : : : ", simbolizado por $.
Nesta se»c~ao discutiremos os conectivos » e ^, adiando os demais conectivos, _,
!, e $, at¶e a pr¶oxima se»c~ao.
Seja p uma proposi»c~ao. A proposi»c~ao » p, lida \n~ao p" ou \a nega»c~ao de p", ¶e
verdadeira quando a proposi»c~ao p ¶e falsa, e ¶e falsa quando p ¶e verdadeira. Por exemplo,
seja p a proposi»c~ao \Este ¶e um curso f¶acil". Ent~ao sua nega»c~ao » p representa \Este
n~ao ¶e um curso f¶acil".
A verdade de » p depende da verdade de p. ¶E conveniente anotar essa depende^ncia
em uma tabela verdade:
Tabela 1.1:
p » p
V F
F V
na qual as letras V e F signi¯cam \verdadeiro" e \falso", respectivamente. Na primeira
coluna da tabela 1.1, listamos os dois poss¶³veis valores l¶ogicos da proposi»c~ao p, sendo eles
V e F . Cada linha em uma tabela verdade representa um caso que deve ser considerado,
e claramente, nesta situa»c~ao bastante simples, h¶a apenas dois casos. Usando as linhas
da Tabela 1.1 vemos que se p ¶e verdadeira ent~ao » p ¶e falsa, e se p ¶e falsa, ent~ao » p ¶e
verdadeira. ConseqÄuentemente, a Tabela 1.1 nos diz o valor verdade1 de » p em cada
caso.
1ou valor l¶ogico (N. do T.)
L¶ogica Elementar 3
De¯ni»c~ao 1.1 O conectivo ^ pode ser colocado entre duas proposi»c~oes p e q para
formar uma proposi»c~ao composta p ^ q cujos valores verdade s~ao dados na seguinte
tabela verdade.
Tabela 1.2:
p q p ^ q
V V V
V F F
F V F
F F F
O s¶³mbolo p ^ q ¶e lido \p e q" ou \conjun»c~ao de p e q". Por exemplo, seja p
a proposi»c~ao \O c¶eu ¶e azul" e seja q a proposi»c~ao \As rosas s~ao vermelhas". Ent~ao a
conjun»c~ao p ^ q representa \O c¶eu ¶e azul e as rosas s~ao vermelhas". Numa proposi»c~ao
composta, tal como p ^ q, as proposi»c~oes individuais p e q s~ao chamadas componentes.
Uma componente pode ser uma proposi»c~ao simples ou uma proposi»c~ao composta. Numa
proposi»c~ao composta com duas componentes, tal como p ^ q, existem no m¶aximo 4 (=
2£ 2) possibilidades, chamadas possibilidades l¶ogicas, a serem consideradas; sendo elas:
(1) p ¶e verdadeira e q ¶e verdadeira;
(2) p ¶e verdadeira e q ¶e falsa;
(3) p ¶e falsa e q ¶e verdadeira;
(4) p ¶e falsa e q ¶e falsa.
Cada uma destas quatro possibilidades ¶e coberta nas quatro linhas da Tabela 1.2.
A ¶ultima coluna d¶a os valores verdade de p ^ q. Uma inspe»c~ao mostra que p ^ q ¶e
verdadeira em apenas um caso. Isto ¶e, p^ q ¶e verdadeira quando ambas as componentes
s~ao verdadeiras, e nos outros tre^s casos p ^ q ¶e falsa. O leitor sensato perceber¶a que a
Tabela 1.2 re°ete o modo pelo qual a conjun»c~ao \e" ¶e usada no portugue^s cotidiano.
Usando as Tabelas 1.1 e 1.2, podemos encontrar valores verdade de proposi»c~oes
complicadas envolvendo os conectivos » e ^.
Exemplo 1.3 Construa a tabela verdade para a proposi»c~ao composta
» [(» p) ^ (» q)]
Solu»c~ao.
Se o m¶etodo usado na constru»c~ao da Tabela 1.3 n~ao ¶e ¶obvio, uma palavra de
explica»c~ao pode ajudar. Os cabe»calhos s~ao selecionados de modo que a proposi»c~ao
composta (¶ultima coluna) ¶e gradualmente constru¶³da a partir de suas v¶arias componentes.
4 L¶ogica Elementar
Tabela 1.3:
p q » p » q (» p) ^ (» q) » [(» p) ^ (» q)
V V F F F V
V F F V F V
F V V F F V
F F V V V F
Passo 1 1 2 3
As duas primeiras colunas simplesmente registram todos os casos para os valores
verdade de p e q. Usamos ent~ao a Tabela 1.1 para obter as entradas nas terceira e quarta
colunas, os valores verdade correspondentes para » p e » q. No pr¶oximo passo usamos
as entradas das terceira e quarta colunas e a Tabela 1.2 para obter as entradas na quinta
coluna. Finalmente, as entradas da quinta coluna e a Tabela 1.1 d~ao as entradas na sexta
coluna|os valores verdade de » [(» p) ^ (» q)]. O estudante aplicado deveria agora
copiar esta ¶ultima proposi»c~ao composta, fechar o livro, e tentar reproduzir a Tabela 1.3.
A proposi»c~ao no exemplo acima, » [(» p) ^ (» q)], usa pare^nteses e colchetes
para indicar a ordem segundo a qual os conectivos se aplicam. FreqÄuentemente, uma
express~ao pode ser simpli¯cada se pudermos eliminar alguns dos pare^nteses ou colchetes.
A conven»c~ao habitual ¶e concordar que » tem prioridade sobre ^, isto ¶e, o conectivo »
deve ser aplicado primeiro. Assim, por exemplo, a express~ao (» p)^ (» q) ¶e simpli¯cada
na forma » p ^ » q.
1.1.1 Exerc¶³cios
Nos problemas de 1 a 10, uma senten»ca em portugue^s ¶e dada. Determine se a senten»ca
¶e uma proposi»c~ao (S) ou n~ao (N).
1. Em 7 de junho de 1442 nevou em algum lugar no Rio Grande do Sul.
2. Arist¶oteles tinha p¶es chatos.
3. O socialismo est¶a errado.
4. O homem mais rico do mundo ¶e o Sr. Malagutti, de S~ao Carlos.
5. Joana e Pedro s~ao pessoas boas.
6. Quanto vale este carro?
7. Saia da grama.
8. Use sempre cinto de seguran»ca.
9. O n¶umero 2987654321 + 37 ¶e primo.
10. Beethoven escreveu algumas das m¶usicas de Chopin.
11. Dentre as proposi»c~oes dadas nos problemas de 1 a 10, indique aquelas que voce^
acha que devem ser verdadeiras(V) ou falsas (F), e aquelas cujo status pode ser dif¶³cil
determinar.
L¶ogica Elementar 5
Nos problemas 12 a 19 encontre as tabelas verdade das proposi»c~oes dadas. Use o
formato da Tabela 1.1 ou da Tabela 1.2 para os dois ou quatro casos respectivamente.
12. » (» p) 13. » [» (» p)]
14. p ^ p 15. » (p^ » p)
16. p^ » q 17. » p ^ q
18. (p ^ p)^ » p 19. » (p ^ q)
20. Numa proposi»c~ao composta, envolvendo tre^s componentes distintas p, q e r, quantos
casos s~ao necess¶arios para cobrir todas as possibilidades l¶ogicas? Quantos casos s~ao
necess¶arios se houver quatro componentes distintas? Quantos casos s~ao necess¶arios se
houver n componentes distintas?
21. O seguinte ¶e uma tentativa de arranjar todos os casos em uma tabela verdade, para
uma proposi»c~ao envolvendo tre^s componentes p, q, e r. Complete o trabalho inacabado.
p q r ¢
V V
V V F
V V
V F
V V
V F
F F
F F
Nos problemas 22 a 25, encontre as tabelas verdade para as proposi»c~oes dadas.
Use o padr~ao desenvolvido no problema 21 para os v¶arios casos.
22. (p ^ q) ^ r 23. p ^ (q ^ r)
24. (p^ » q) ^ r 25. » q ^ (r ^ p)
1.2 Tre^s conectivos mais
Na l¶³ngua portuguesa h¶a uma ambigÄuidade envolvida no uso do \ou". A proposi»c~ao
\Obterei grau de mestre ou grau de doutor" indica que quem o a¯rma pode obter
ambos, o grau de mestre e o de doutor. Mas em outra proposi»c~ao, \Me casarei com
L¶³via ou L¶ucia", a palavra \ou" signi¯ca que apenas uma das duas mo»cas ser¶a escolhida.
Na matem¶atica e na l¶ogica, n~ao podemos permitir ambigÄuidades. Portanto, devemos
nos decidir sobre o signi¯cado da palavra \ou".
6 L¶ogica Elementar
De¯ni»c~ao 1.2 O conectivo _ pode ser colocado entre duas proposi»c~oes quaisquer p e
q para formar a proposi»c~ao composta p _ q. Os valores verdade de p _ q s~ao de¯nidos
na Tabela 1.4. Portanto _ ¶e de¯nido como sendo o \ou" inclusivo, tal como usado na
primeira proposi»c~ao acima.
Tabela 1.4:
p q p _ q
V V V
V F V
F V V
F F F
O s¶³mbolo p_q ¶e lido \p ou q" ou a \disjun»c~ao de p e q". Repare que a conjun»c~ao
de p e q ¶e verdadeira apenas quando as duas componentes s~ao ambas verdadeiras (Tabela
1.2), enquanto que a disjun»c~ao ¶e falsa quando e apenas quando as duas componentes
s~ao falsas (Tabela 1.4).
Comparemos as tabelas verdade de p _ q e » (» p^ » q), nas Tabelas 1.3 e
1.4. Notamos que em cada caso a ¶ultima coluna ¶e V V V F , de modo que estas duas
proposi»c~oes tem os mesmos valores verdade em cada uma das quatro possibilidades
l¶ogicas. Mostrar que certas proposi»c~oes tem os mesmos valores verdade em cada caso ¶e
uma parte importante da l¶ogica. Na verdade, a l¶ogica trata duas tais proposi»c~oes como
sendo uma s¶o.
De¯ni»c~ao 1.3 Quando duas proposi»c~oes P e Q, simples ou compostas, tem os mes-
mos valores verdade em cada uma de todas as possibilidades l¶ogicas, dizemos que P ¶e
logicamente equivalente ou simplesmente equivalente a Q, e escrevemos P ´ Q.
Resumidamente, duas proposi»c~oes s~ao logicamente equivalentes desde que tenham
a mesma tabela verdade. Portanto, temos
p _ q ´» (» p^ » q)
Embora duas proposi»c~oes equivalentes sejam consideradas como a mesma, do ponto de
vista da l¶ogica, preferimos a proposi»c~ao mais simples \p ou q" em vez da proposi»c~ao
equivalente mais complicada \N~ao ¶e verdade que nem p e nem q".
De¯ni»c~ao 1.4 O conectivo ! ¶e chamado condicional e pode ser colocado entre duas
proposi»c~oes p e q para formar a proposi»c~ao composta p ! q (lida: \se p ent~ao q").
Por de¯ni»c~ao, a proposi»c~ao p! q ¶e equivalente µa proposi»c~ao » (p^ » q), e os valores
verdade de p! q s~ao dados na Tabela 1.5.
L¶ogica Elementar 7
Tabela 1.5:
Caso p q » q p^ » q p! q [´» (p^ » q)]
1 V V F F V
2 V F V V F
3 F V F F V
4 F F V F V
A motiva»c~ao da De¯ni»c~ao 1.4 ¶e a seguinte. Sejam p a proposi»c~ao \O sol est¶a
brilhando" e q a proposi»c~ao \Eu estou jogando te^nis". Ent~ao a proposi»c~ao composta
p ! q ¶e \Se o sol est¶a brilhando ent~ao eu estou jogando te^nis". Agora, quando ¶e que
uma tal proposi»c~ao 'considerada falsa? Claramente p! q ¶e falsa se o sol est¶a brilhando
mas eu n~ao estou jogando te^nis, e apenas neste caso. Em outras palavras p! q ¶e falsa
se p^ » q ¶e verdadeira, a apenas neste caso. Mas isto ¶e precisamente a De¯ni»c~ao 1.4.
Estudaremos agora a tabela verdade de p! q, isto ¶e, de » (p^ » q).
Conforme a De¯ni»c~ao 1.4, o signi¯cado da proposi»c~ao condicional p! q afasta-se
radicalmente do nosso uso ordin¶ario de \Se p ent~ao q". Na nossa linguagem ordin¶aria,2
uma senten»c~ao da forma \Se p ent~ao q" ¶e considerada como querendo dizer que q ¶e
verdadeira sempre que p ¶e verdadeira. Portanto os casos em que p ¶e falsa n~ao precisam
ser considerados.
Por exemplo, a proposi»c~ao \Se Collor atirou em Figueiredo, ent~ao Itamar foi o
primeiro presidente" ¶e considerada sem sentido, pois ambas as componentes s~ao falsas.
ConseqÄuentemente, no uso ordin¶ario n~ao se questiona se uma proposi»c~ao componente ¶e
verdadeira. Ao criar a linguagem formal, o l¶ogico deseja designar um valor verdade a
p ! q para cada uma das quatro possibilidades l¶ogicas, muito embora dois dos casos
pare»cam ser sem sentido em nossa linguagem ordin¶aria. Por v¶arias raz~oes, que aparecer~ao
no tempo devido, os l¶ogicos decidiram-se pela de¯ni»c~ao adotada aqui. Portanto, em nossa
linguagem formal, p! q ¶e verdadeira em todos os casos exceto no caso 2 (veja Tabela
1.5). Como conseqÄue^ncia desse acerto, seremos capazes de demonstrar alguns teoremas
¶uteis bastante simples, cujas demonstra»c~oes, sem tal acerto, seriam desajeitadas ou muito
dif¶³ceis.
Introduzimos agora o ¶ultimo dos cinco conectivos mais comuns, um que aparece
freqÄuentemente nos enunciados (proposi»c~oes) de teoremas matem¶aticos.
De¯ni»c~ao 1.5 O conectivo $ ¶e chamado o bicondicional e pode ser colocado entre
duas proposi»c~oes p e q para formar a proposi»c~ao composta p$ q (lida: \p se e somente
se q"). A proposi»c~ao p$ q ¶e equivalente µa proposi»c~ao (p! q) ^ (q ! p), e os valores
verdade de p$ q s~ao dados na Tabela 1.6.
2Em oposi»c~ao µa \linguagem ordin¶aria", l¶ogica ¶e chamada uma linguagem formal.
8 L¶ogica Elementar
Exemplo 1.4 Encontre a tabela verdade para p$ q.
Solu»c~ao. Seguindo o m¶etodo descrito anteriormente, obtemos a Tabela 1.6.
Tabela 1.6:
Caso p q p! q q ! p p$ q [´ (p! q) ^ (q ! p)]
1 V V V V V
2 V F F V F
3 F V V F F
4 F F V V V
Passo 1 1 2
Da tabela verdade acima, observamos que p $ q ¶e verdadeira se ambas as com-
ponentes s~ao verdadeiras ou ambas as componentes s~ao falsas. Em qualquer outro caso
(casos 2 e 3) a proposi»c~ao p$ q ¶e falsa.
1.2.1 Exerc¶³cios
Nos problemas de 1 a 12, construa as tabelas verdade para as proposi»c~oes dadas.
1. p_ » p 2. » (p_ » p)
3. » (» p_ » q) 4. » p _ q
5. (» q)! (» p) 6. q $ p
7. p ^ (q _ r) 8. (p ^ q) _ (p ^ r)
9. p _ (q ^ r) 10. (p _ q) ^ (p _ r)
11.(p _ q) _ r 12. p _ (q _ r)
13. ¶E a proposi»c~ao (» q)! (» p) (Problema 5) logicamente equivalente µa proposi»c~ao
p! q?
14. ¶E a proposi»c~ao » p _ q (Problema 4) logicamente equivalente µa proposi»c~ao p! q?
15. Dentre as proposi»c~oes nos Problemas 1 a 12, encontre os pares de proposi»c~oes
logicamente equivalentes.
16. Em cada um dos seguintes itens, traduza a proposi»c~ao composta dada em uma
forma simb¶olica usando os s¶³mbolos sugeridos.
(a) N~ao ocorre que eu seja amig¶avel a voce^. (A)
(b) Se ela ¶e uma gata, ent~ao ela tem quatro pernas. (G;P )
(c) O pre»co do arroz aumenta se e somente se o suprimento de arroz n~ao atende µa
demanda. (P; S)
(d) Ou os grandes laborat¶orios reduzem os pre»cos ou o governo intervir¶a. (L;G)
(e) Se a exporta»c~ao de carne aumentar ou se a produ»c~ao pecu¶aria decair, ent~ao o custo
de vida subir¶a. (E;P;C)
L¶ogica Elementar 9
1.3 Tautologia, implica»c~ao e equivale^ncia
Examinemos a tabela verdade para a proposi»c~aop_ » p:
Tabela 1.7:
p » p p_ » p
V F V
F V V
Reparemos que a proposi»c~ao p_ » p ¶e verdadeira em todos os casos, isto ¶e, em
todas as possibilidades l¶ogicas. Tal tipo importante de proposi»c~ao merece um nome
especial.
De¯ni»c~ao 1.6 Uma proposi»c~ao ¶e dita ser uma tautologia quando ¶e verdadeira em cada
uma de todas as possibilidades l¶ogicas.
Sejam P e Q duas proposi»c~oes, compostas ou simples. Se a proposi»c~ao condicional
P ! Q ¶e uma tautologia, a proposi»c~ao ¶e chamada uma implica»c~ao e ¶e denotada por P )
Q (le^-se: P implica Q). Assim as seguintes proposi»c~oes condicionais s~ao tautologias:
(1) p! p.
(2) p ^ q ! q ^ p.
(3) p! p ^ p.
(4) p ^ q ! q.3
Na l¶ogica ou na matem¶atica, \teoremas" signi¯cam proposi»c~oes verdadeiras, e uma
\demonstra»c~ao" (de um teorema) ¶e uma justi¯ca»c~ao do teorema.
Teorema 1.1 Sejam p e q duas proposi»c~oes quaisquer. Ent~ao
(a) Lei da Adi»c~ao (Ad.): p) p _ q.
(b) Leis de Simpli¯ca»c~ao (Simp.): p ^ q ) p, p ^ q ) q.
(c) Silogismo Disjuntivo (S.D.): (p _ q)^ » p) q.
Demonstra»c~ao. Deixamos as demonstra»c~oes de (a) e (b) ao leitor, como exerc¶³cios. A
seguinte ¶e uma tabela verdade simpli¯cada para (p _ q)^ » p! q:
Tomemos um instante para explicar a constru»c~ao da tabela verdade simpli¯cada:
Os valores verdade na Tabela 1.8 s~ao atribu¶³dos, coluna por coluna, na ordem indicada
3Consideraremos _ e ^ como conectivos priorit¶arios em rela»c~ao a ! e $, e escreveremos p! p_ q
em lugar de p! (p _ q), etc. Veja tamb¶em o ¶ultimo par¶agrafo da se»c~ao 1.1
10 L¶ogica Elementar
Tabela 1.8:
(p _ q) ^ » p ! q
V V V F F V V
V V F F F V F
F V V V V V V
F F F F V V F
Passo 1 2 1 3 2 4 1
pelos n¶umeros que aparecem na ¶ultima linha da tabela. Em uma tabela verdade sim-
pli¯cada, escrevemos os valores verdade diretamente, primeiro sob cada componente e
ent~ao sob os conectivos. Isto poupa espa»co e tempo.
Agora, retornando µa demonstra»c~ao do teorema, como o passo ¯nal (passo 4) na
Tabela 1.8 consiste s¶o de V 's, a proposi»c~ao condicional (p _ q)^ » p ! q ¶e de fato
uma implica»c~ao.
Se a proposi»c~ao bicondicional P $ Q for uma tautologia, ela ¶e chamada uma
equivale^ncia e ¶e denotada por P , Q (leia-se: P ¶e equivalente a Q).
Da de¯ni»c~ao 1.5 e da Tabela 1.6, P , Q se P e Q tem os mesmos valores verdade
em cada uma de todas as possibilidades l¶ogicas, e reciprocamente, P e Q tem os mesmos
valores verdade em cada uma de todas as possibilidades l¶ogicas se P , Q. Portanto,
pela de¯ni»c~ao 1.3, P , Q e P ´ Q tem o mesmo signi¯cado, e portanto podemos
trocar , por ´ e vice-versa.
Teorema 1.2 Sejam p e q duas proposi»c~oes quaisquer. Ent~ao
(a) Lei da Dupla Nega»c~ao (D.N.): » (» p) ´ p.
(b) Leis Comutativas (Com.): p ^ q ´ q ^ p, p _ q ´ q _ p,
(c) Leis de Idempote^ncia (Idemp.): p ^ p ´ p, p _ p ´ p,
(d) Lei Contrapositiva (Contrap.): (p! q) ´ (» q !» p).
Demonstra»c~ao. Deixaremos as demonstra»c~oes das partes (a), (b) e (c) para o leitor,
como exerc¶³cios, e delinearemos a demonstra»c~ao de (d).
Temos a seguinte tabela verdade simpli¯cada para a proposi»c~ao bicondicional
(p! q)$ (» q !» p):
L¶ogica Elementar 11
Tabela 1.9:
(p ! q) $ (» q ! » p)
V V V V F V V
V F F V V F F
F V V V F V V
F V F V V V V
Passo 1 2 1 4 2 3 2
Logo, a Tabela 1.9 mostra que p$ q ¶e equivalente a » q !» p.
O seguinte teorema, creditado a Augustus De Morgan (1806{1871), ¶e uma das
ferramentas mais convenientes da l¶ogica.
Teorema 1.3 (Leis de De Morgan (De M.)) Sejam p e q duas proposi»c~oes quais-
quer. Ent~ao
» (p ^ q) ´ » p_ » q; e
» (p _ q) ´ » p^ » q:
Demonstra»c~ao. Demonstraremos a primeira parte deste teorema e deixaremos a outra
parte ao leitor, como exerc¶³cio. Constru¶³mos uma tabela verdade simpli¯cada para a
bicondicional » (p ^ q)$ (» p_ » q):
Tabela 1.10:
» (p ^ q) $ (» p _ » q)
F V V V V F F F
V V F F V F V V
V F F V V V V F
V F F F V V V V
Passo 3 1 2 1 4 2 3 2
A tabela verdade acima mostra que » (p ^ q) ¶e equivalente a » p_ » q.
Teorema 1.4 Sejam p, q e r proposi»c~oes quaisquer. Ent~ao
(a) Leis Associativas (Assoc.): (p ^ q) ^ r ´ p ^ (q ^ r)
(p _ q) _ r ´ p _ (q _ r)
(b) Leis Distributivas (Dist.): p ^ (q _ r) ´ (p ^ q) _ (p ^ r)
p _ (q ^ r) ´ (p _ q) ^ (p _ r)
(c) Lei Transitiva (Trans.): (p! q) ^ (q ! r)) (p! r).
12 L¶ogica Elementar
Demonstra»c~ao. Deixaremos as demonstra»c~oes das Leis Associativas e da segunda Lei
Distributiva para o leitor, como exerc¶³cios.
Demonstremos que p ^ (q _ r) ´ (p ^ q) _ (p ^ r). Como isto envolve tre^s
componentes, existem 23 = 8 possibilidades l¶ogicas a considerar. A seguinte tabela
verdade mostra que p ^ (q _ r) e (p ^ q) _ (p ^ r) tem os mesmos valores verdade em
cada uma das oito possibilidades l¶ogicas. Portanto, p ^ (q _ r) e (p ^ q) _ (p ^ r) s~ao
equivalentes.
Tabela 1.11:
p q r q _ r p ^ q p ^ r p ^ (q _ r) (p ^ q) _ (p ^ r)
V V V V V V V V
V V F V V F V V
V F V V F V V V
V F F F F F F F
F V V V F F F F
F V F V F F F F
F F V V F F F F
F F F F F F F F
Por simplicidade e por economia de espa»co, constru¶³mos uma tabela verdade sim-
pli¯cada, como apresentado na Tabela 1.8, para (p! q) ^ (p! r)! (p! r).
Tabela 1.12:
(p ! q) ^ (q ! r) ! (p ! r)
V V V V V V V V V V V
V V V F V F F V V F F
V F F F F V V V V V V
V F F F F V F V V F F
F V V V V V V V F V V
F V V F V F F V F V F
F V F V F V V V F V V
F V F V F V F V F V F
Passo 1 2 1 3 1 2 1 4 1 2 1
Como o ¶ultimo passo (passo 4) consiste inteiramente de valores V , a Lei Transitiva
est¶a demonstrada.
Por causa das Leis Associativas, os pare^nteses em (p ^ q) ^ r ´ p ^ (q ^ r) e
L¶ogica Elementar 13
(p_ q)_ r ´ p _ (q _ r) tornam-se desnecess¶arios, e as express~oes p^ q ^ r e p _ q _ r
tem agora signi¯cados de¯nidos, bem como p1 ^ p2 ^ ¢ ¢ ¢ ^ pn e p1 _ p2 _ ¢ ¢ ¢ _ pn.
Teorema 1.5 Sejam p, q, r e s proposi»c~oes quaisquer. Ent~ao
(a) Dilemas Construtivos (D.C.):
(p! q) ^ (r ! s) ) (p _ r! q _ s);
(p! q) ^ (r ! s) ) (p ^ r! q ^ s):
(b) Dilemas Destrutivos (D.D.):
(p! q) ^ (r! s) ) (» q_ » s!» p_ » r);
(p! q) ^ (r! s) ) (» q^ » s!» p^ » r):
Demonstra»c~ao. A demonstra»c~ao do Teorema 1.5 ¶e deixada ao leitor como exerc¶³cio.
Teorema 1.6 Sejam p e q duas proposi»c~oes. Ent~ao
(a) Modus Ponens (M.P.): (p! q) ^ p) q.
(b) Modus Tolens (M.T.): (p! q)^ » q )» p.
(c) Reductio ad Absurdum (R.A.): (p! q), (p^ » q ! q ^ » q).
Demonstra»c~ao. Exerc¶³cio.
1.3.1 Exerc¶³cios
1. Demonstre as partes (a) e (b) do Teorema 1.1.
2. Demonstre as partes (a), (b) e (c) do Teorema 1.2.
3. Demonstre que » (p _ q) ´» p^ » q.
4. Demonstre a parte (a) do Teorema 1.4.
5. Demonstre que p _ (q ^ r) ´ (p _ q) ^ (p _ r).
6. Demonstre que (p! q)) (p ^ r ! q ^ r).
7. Demonstre que (p$ q) ´ (p ^ q) _ (» p^ » q).
8. Usando as Leis de De Morgan, escreva em linguagem ordin¶aria a nega»c~ao da
proposi»c~ao \Esta fun»c~ao tem uma derivada ou eu sou burro."
9. Demonstre as seguintes Leis de De Morgan para tre^s componentes.
(a) » (p ^ q ^ r) ´» p_ » q_ » r
(b) » (p _ q _ r) ´» p^ » q^ » r.
10. Pode voce^ generalizar, sem demonstra»c~ao, as Leis de De Morgan para n compo-
nentes? Veja o Problema 9 para n = 3.
11. Demonstre as seguintes Leis de Absor»c~ao.
(a) p ^ (p _ r) ´ p
(b) p _ (p ^ q) ´ p
12. Demonstre o Teorema 1.5.
13. Demonstre o Teorema 1.6.
14 L¶ogica Elementar
1.4 Contradi»c~ao
Em contraste com as tautologias, h¶a proposi»c~oes cujos valores verdade s~ao todos F ,
para cada uma das possibilidades l¶ogicas. Tais proposi»c~oes s~ao chamadas contradi»c~oes.
Por exemplo, p^ » p ¶e uma contradi»c~ao.
¶E obvio que se t ¶e uma tautologia, ent~ao » t ¶e uma contradi»c~ao; reciprocamente,
se c ¶e uma contradi»c~ao, ent~ao » c ¶e uma tautologia.
Teorema 1.7 Sejam t, c e p, uma tautologia, uma contradi»c~ao e uma proposi»c~ao arbi-
tr¶aria, respectivamente.Ent~ao
(a) p ^ t , p,
p _ t , t.
(b) p _ c , p,
p ^ c , c.
(c) c) p, e p) t.
Demonstra»c~ao.
(a) A seguinte tabela verdade para p ^ t$ p mostra que p ^ t ¶e equivalente a p.
Tabela 1.13:
p ^ t $ p
V V V V V
F F V V F
Passo 1 2 1 3 1
A outra equivale^ncia, p _ t, t, pode ser demonstrada analogamente.
(b) Da seguinte tabela verdade, conclu¶³mos que a proposi»c~ao condicional p_c$ p
¶e uma tautologia, e portanto p _ c, p.
Tabela 1.14:
p _ c $ p
V V F V V
F F F V F
Passo 1 2 1 3 1
A demonstra»c~ao de p ^ c, p ¶e similar.
L¶ogica Elementar 15
(c) As tabelas verdade de c ! p e p ! t mostram que as duas proposi»c~oes s~ao
tautologias, logo c) p e p) t.
Tabela 1.15:
c ! p
F V V
F V F
p ! t
V V V
F V V
No restante deste livro, o s¶³mbolo c, com ou sem¶³ndice, denotar¶a uma contradi»c~ao;
e o s¶³mbolo t, com ou sem ¶³ndice, denotar¶a uma tautologia.
1.4.1 Exerc¶³cios
1. Demonstre que p _ t, t e p ^ c, c.
2. Demonstre que » t, c e » c, t.
3. Demonstre a seguinte Reductio ad Absurdum.
(p^ » q ! c), (p! q)
4. Demonstre que p ^ (p! q) ^ (p!» q), c.
5. Demonstre que (p! q)) (p _ r ! q _ r), para qualquer proposi»c~ao r.
1.5 Racioc¶³nio dedutivo
As 17 leis sumarizadas nos Teoremas de 1.1 a 1.6 s~ao ferramentas muito ¶uteis para
justi¯car equivale^ncias l¶ogicas e implica»c~oes, como ilustrado nos Exemplos de 1.5 a 1.7.
Chamaremos estas 17 leis de regras de infere^ncia. Chamamos a aten»c~ao para o fato
de que estas regras foram selecionadas como refere^ncias convenientes e n~ao precisam
ser independentes entre si. Por exemplo, a Lei Contrapositiva pode ser estabelecida
\dedutivamente" pelo uso de outras leis e de de¯ni»c~oes relevantes, como mostra o
pr¶oximo exemplo.
Exemplo 1.5 Demonstre a Lei Contrapositiva, (p ! q) ´ (» q !» p), usando
de¯ni»c~oes relevantes e outras regras de infere^ncia.
Solu»c~ao.
(p! q) ´ » (p^ » q) Def. 1.4
´ » (» q ^ p) Com.
´ » [» q^ » (» p)] D.N.
´ (» q !» p) Def. 1.4
16 L¶ogica Elementar
Portanto, (p! q) ´ (» q !» p), pela Lei Transitiva.
O m¶etodo de demonstra»c~ao usado no Exemplo 1.5 ¶e chamado racioc¶³nio dedutivo4
ou m¶etodo dedutivo, e difere do m¶etodo de demonstra»c~ao por tabelas verdade.
Em geral, no racioc¶³nio dedutivo, quaisquer axiomas, de¯ni»c~oes, teoremas e regras
de infere^ncia, previamente enunciados, podem ser usados.
Exemplo 1.6 Prove o Silogismo Disjuntivo por racioc¶³nio dedutivo.
Solu»c~ao.
(p _ q)^ » p ´ » p ^ (p _ q) Com.
´ (» p ^ p) _ (» p ^ q) Dist.
´ c _ (» p ^ q) » p ^ p ´ c
´ (» p ^ q) _ c Com.
´ » p ^ q Teorema 1.7(b)
)q Simp.
Finalmente, pela Lei Transitiva, (p _ q)^ » p) q.
Exemplo 1.7 Demonstre a seguinte Lei de Exporta»c~ao:
(p ^ q ! r) ´ [p! (q ! r)]
por racioc¶³nio dedutivo.
Solu»c~ao.
p! (q ! r) ´ [p!» (q^ » r) De¯ni»c~ao 1.4
´ » [p ^ (q^ » r)] Def. 1.4, D.N.
´ » [(p ^ q)^ » r] Assoc.
´ (p ^ q ! r) De¯ni»c~ao 1.4
Portanto, (p ^ q)! r ´ [p! (q ! r)].
Exemplo 1.8 Demonstre que (p ! r) _ (q ! s) ´ (p ^ q ! r _ s) por racioc¶³cio
dedutivo.
Solu»c~ao.
(p! r) _ (q ! s) ´ » (p^ » r)_ » (q^ » s) De¯ni»c~ao 1.4
´ (» p _ r) _ (» q _ s) De M., D.N.
´ (» p_ » q) _ (r _ s) Com., Assoc.
´ » [(p ^ q)^ » (r _ s)] De M., D.N.
´ (p ^ q ! r _ s) De¯ni»c~ao 1.4
4ou argumenta»c~ao dedutiva (N. do T.)
L¶ogica Elementar 17
O porque^ de querermos usar racioc¶³cio dedutivo, em oposi»c~ao a tabelas verdade,
pode ser visto da seguinte compara»c~ao: Para veri¯car a equivale^ncia no Exemplo 1.8,
pelo m¶etodo das tabelas verdade, ter¶³amos que construir uma grande tabela verdade com
16 (= 24) casos (veja Problema 20 dos Exerc¶³cios 1.1.1 ou Problema 12 dos Exerc¶³cios
1.3.1); por outro lado, na solu»c~ao do Exemplo 1.8, acima, estabelecemos tal equivale^ncia
em apenas cinco passos.
1.5.1 Exerc¶³cios
Demonstre as seguintes tautologias pelo m¶etodo dedutivo.
1. Modus Ponens: p ^ (p! q)) q
2. Modus Tollens: » q ^ (p! q))» p
3. Reductio ad Absurdum: (p! q), (p^ » q ! c)
4. Silogismo Disjuntivo: (p _ q)^ » p) q
5. Teorema 1.7(c): c) p
6. (p! q), (p! p ^ q)
7. (p! q), (p _ q ! q)
8. (p! q),» p _ q
9. (p! r) ^ (q ! r), (p _ q ! r)
10. (p! q) ^ (p! r), (p! q ^ r)
11. (p! q) ^ (p!» q),» p
12. (p! q) _ (p! r), (p! q _ r)
13. (p! r) _ (q ! r), (p ^ q ! r)
1.6 Regras de quanti¯ca»c~ao
Em qualquer discuss~ao geral, temos em mente um universo particular ou dom¶³nio do
discurso, isto ¶e, uma cole»c~ao de objetos cujas propriedades est~ao sob considera»c~ao. Por
exemplo, na a¯rma»c~ao \Todos os humanos s~ao mortais", o universo ¶e a cole»c~ao de todos
os humanos. Com este entendimento do universo, a a¯rma»c~ao \Todos os humanos s~ao
mortais" poder ser expressada alternativamente como:
Para todo x no universo, x ¶e mortal.
A frase \Para todo x no universo" ¶e chamada um quanti¯cador universal, e ¶e simbolizada
por (8x). A senten»ca \x ¶e mortal" diz algo sobre x; simbolizaremos isto por p(x). Usando
estes novos s¶³mbolos, podemos agora escrever a a¯rma»c~ao geral \Todos os homens s~ao
mortais" como
(8x)(p(x))
Agora considere a a¯rma»c~ao \Alguns homens s~ao mortais". Aqui o universo (ou
dom¶³nio de discurso) ¶e ainda o mesmo da a¯rma»c~ao pr¶evia. Com este universo em mente,
podemos refazer a a¯rma»c~ao \Alguns homens s~ao mortais" sucessivamente como:
18 L¶ogica Elementar
Existe pelo menos um indiv¶³duo que ¶e mortal.
Existe pelo menos um x tal que x ¶e mortal.
e como
Existe pelo menos um x tal que p(x).
A frase \Existe ao menos um x tal que" ¶e chamada um quanti¯cador existencial e ¶e
simbolizada por (9x). Usando este novo s¶³mbolo podemos agora reescrever a a¯rma»c~ao
\Alguns homens s~ao mortais" como
(9x)(p(x))
De um modo geral, suponhamos que temos um dom¶³nio de discurso U e uma
a¯rma»c~ao geral, p(x), chamada um predicado proposicional, cuja \vari¶avel" x varia em
U . Ent~ao (8x)(p(x)) a¯rma que para todo x, em U , a proposi»c~ao p(x), a respeito de
x, ¶e verdadeira, e (9x)(p(x)) signi¯ca que existe pelo menos um x, em U , tal que p(x)
¶e verdadeira.
Em matem¶atica elementar, quanti¯cadores s~ao freqÄuentemente suprimidos pelo
bem da simplicidade. Por exemplo, \(x+1)(x¡1) = x2¡1", em livros do ensino b¶asico,
deve ser entendido como dizendo \para todo n¶umero real x, (x+ 1)(x¡ 1) = x2 ¡ 1".
Na matem¶atica, \qualquer que seja" e \para todo" signi¯cam a mesma coisa e s~ao
ambos simbolizados por 8; e \para algum" signi¯ca o mesmo que \existe" e ¶e simboliza-
do por 9. Em express~oes menos formais, freqÄuentemente colocamos o quanti¯cador
ap¶os a a¯rma»c~ao. Por exemplo, a a¯rma»c~ao \f(x) = 0 para todo x" ¶e a mesma que
\(8x)(f(x) = 0)".
Na l¶ogica e na matem¶atica, a nega»c~ao da proposi»c~ao \p(x) ¶e verdadeira para todo
x (em U)", » [(8x)(p(x))], ¶e considerada o mesmo que a asser»c~ao \existe pelo menos
um x (em U) para o qual p(x) ¶e falsa", (9x)(» p(x)). Analogamente, » [(9x)(p(x))]
¶e considerada o mesmo que \n~ao h¶a nenhum5 x (em U) tal que p(x) ¶e verdadeira"; ou,
em outras palavras, \p(x) ¶e falsa para todo x (em U)", ou (8x)(» p(x)). Sumarizamos
tudo isto no seguinte axioma:
Axioma 1.1 (Regra da Nega»c~ao do Quanti¯cador (N.Q.)) Seja p(x) um predica-
do proposicional, isto ¶e, uma proposi»c~ao sobre um objeto n~ao especi¯cado de um dado
universo. Ent~ao
» [(8x)(p(x))] ´ (9x)(» p(x))
e
» [(9x)(p(x))] ´ (8x)(» p(x))
5Na l¶³ngua portuguesa, \n~ao h¶a nenhum" tem o signi¯cado de \existe nenhum" (N. do T.).
L¶ogica Elementar 19
Estamos usando \´" para denotar que as duas proposi»c~oes quanti¯cadas, nos dois
lados de ´, s~ao consideradas a mesma em l¶ogica; este uso ¶e consistente com o uso de
´ para equivale^ncias l¶ogicas, como ser¶a visto no pr¶oximo par¶agrafo.
Para entender melhor as proposi»c~oes quanti¯cadas (8x)(p(x)) e (9x)(p(x)), in-
specionemos o caso em que o universo de discurso consiste de um n¶umero ¯nito de
indiv¶³duos denotadospor a1; a2; a3; : : : ; an. Ent~ao, como (8x)(p(x)) a¯rma que p(x)
¶e verdadeira para todos, a1; a2; a3; : : : ; an, a proposi»c~ao (8x)(p(x)) ¶e verdadeira se e
somente se a conjun»c~ao de
p(a1); p(a2); p(a3); : : : ; p(an)
¶e verdadeira. ConseqÄuentemente,
(8x)(p(x)) corresponde a p(a1) ^ p(a2) ^ ¢ ¢ ¢ ^ p(an)
Analogamente,
(9x)(p(x)) signi¯ca p(a1) _ p(a2) _ ¢ ¢ ¢ _ p(an)
Portanto, a Regra da Nega»c~ao do Quanti¯cador pode ser vista com uma generaliza»c~ao
das Leis de De Morgan (Teorema 1.3).
Exemplo 1.9 Quais das seguintes proposi»c~oes ¶e equivalente µa nega»c~ao da proposi»c~ao
\Todas as cobras s~ao venenosas"?
(a) Todas as cobras s~ao n~ao venenosas.
(b) Algumas cobras s~ao venenosas.
(c) Algumas cobras n~ao s~ao venenosas.
Solu»c~ao. O dom¶³nio de discurso U ¶e a cole»c~ao de todas as cobras. Seja p(x) o predicado
proposicional que a¯rma que x ¶e venenosa (onde a vari¶avel x varia sobre U). A a¯rma»c~ao
\Todas as cobras s~ao venenosas" ¶e ent~ao traduzida em (8x)(p(x)). Conforme a regra
de nega»c~ao do quanti¯cador, Axioma 1.1, » [(8x)(p(x))] ¶e equivalente a (9x)(» p(x)),
que representa \Algumas cobras n~ao s~ao venenosas".
1.6.1 Exerc¶³cios
1. Traduza a proposi»c~ao da ¶algebra elementar \A equa»c~ao x2¡3x+2 = 0 tem solu»c~oes"
em linguagem l¶ogica, usando um quanti¯cador. Qual ¶e o dom¶³nio de discurso aqui?
2. Encontre a proposi»c~ao equivalente µa nega»c~ao de cada uma das seguintes proposi»c~oes,
usando N.Q.
(a) Todas as cobras s~ao r¶epteis.
(b) Alguns cavalos s~ao mansos.
(c) Alguns matem¶aticos n~ao s~ao soci¶aveis.
(d) Todas as estudantes s~ao ou inteligentes ou atraentes.
(e) N~ao h¶a bebe^ que n~ao seja fofo.
20 L¶ogica Elementar
3. Encontre o dom¶³nio de discurso de cada uma das proposi»c~oes do Problema 2.
4. Deduza
» [(9x)(p(x))] ´ (8x)(» p(x))
a partir de
» [(8x)(q(x))] ´ (9x)(» q(x)):
5. Deduza
» [(8x)(p(x))] ´ (9x)(» p(x))
a partir de
» [(9x)(q(x))] ´ (8x)(» q(x)):
6. Demonstre que » [(8x)(» q(x))] ´ (9x)(q(x)) e » [(9x)(» q(x))] ´ (8x)(q(x)):
[Sugest~ao: Use N.Q.]
1.7 Demonstra»c~ao de validade
Uma das mais importantes tarefas de um l¶ogico est¶a em testar argumentos. Um ar-
gumento ¶e a asser»c~ao de que uma proposi»c~ao, chamada a conclus~ao, ¶e conseqÄue^ncia
de outras proposi»c~oes, chamadas hip¶oteses ou premissas. Um argumento ¶e considerado
v¶alido se a conjun»c~ao das hip¶oteses implica a conclus~ao. Como exemplo, o seguinte ¶e um
argumento no qual as primeiras quatro proposi»c~oes s~ao hip¶oteses, e a ¶ultima proposi»c~ao
¶e a conclus~ao.
Se ele estuda medicina, ent~ao prepara-se para ganhar uma boa renda.
Se ele estuda artes, ent~ao prepara-se para viver bem.
Se ele prepara-se para ganhar uma boa renda ou para viver bem, ent~ao suas des-
pesas de estudos n~ao s~ao desperdi»cadas.
Suas despesas de estudos s~ao desperdi»cadas.
Portanto, ele n~ao estuda nem medicina e nem artes.
Este argumento pode ser simbolizado como:
H1. M ! R
H2. A! B
H3. (R _B)!» D
H4. D
C. :
.
: »M ^ » A
Para estabelecer a validade deste argumento por meio de uma tabela verdade,
precisar¶³amos de uma tabela com 32 (= 25) linhas. Mas podemos demonstrar que este
argumento ¶e v¶alido deduzindo a conclus~ao a partir das hip¶oteses em poucos passos
usando as regras de infere^ncia.
Das hip¶oteses H3 e H4, (R _ B) !» D e D, inferimos » (R _ B), ou equiva-
lentemente, » R^ » B, por Modus Tollens e Lei de De Morgan. De » R^ » B,
inferimos, de maneira v¶alida, » R (e tamb¶em » B), pelas Leis de Simpli¯ca»c~ao. De
H1, M ! R; com » R inferimos »M .
L¶ogica Elementar 21
Analogamente, A ! B (de H2), e » B, nos faz inferir » A. Finalmente a
conjun»c~ao de » M e » A nos d¶a a conclus~ao » M ^ » A. Nesta demonstra»c~ao,
as regras de infere^ncia Modus Tollens (M.T.), Leis de De Morgan (D.M.), e Leis de
Simpli¯ca»c~ao (Simp.) s~ao usadas.
Um modo mais formal e conciso de expressar esta demonstra»c~ao de validade, ¶e
listar as hip¶oteses e as proposi»c~oes deduzidas a partir delas em uma coluna, com a
justi¯ca»c~ao de cada passo numa coluna ao lado. Em cada passo, a \justi¯ca»c~ao" indica
as a¯rma»c~oes precedentes das quais, e as regras de infere^ncia pelas quais, a a¯rma»c~ao
dada naquele passo foi obtida. Para f¶acil infere^ncia, ¶e conveniente enumerar as hip¶oteses
e as a¯rma»c~oes deduzidas a partir delas e colocar a conclus~ao µa direita da ¶ultima premissa,
separada desta por uma barra = que indica que todas as proposi»c~oes acima s~ao hip¶oteses.
A demonstra»c~ao de validade formal para o argumento acima pode ent~ao ser escrita como
1. M ! R (Hip.)
2. A! B (Hip.)
3. (R _B)!» D (Hip.)
4. D=:
.
: »M ^ » A (Hip./ Concl.)
5. » (R _B) 3, 4, M.T.
6. » R^ » B 5, De M.
7. » R 6, Simp.
8. » B 6, Simp.
9. »M 1, 7, M.T.
10. » A 2, 8, M.T.
11. »M ^ » A 9, 10, Conj.
Uma demonstra»c~ao formal de validade para um dado argumento ¶e uma seqÄue^ncia
de proposi»c~oes, cada uma das quais ¶e ou uma premissa do argumento ou segue de
proposi»c~oes precedentes por um argumento v¶alido conhecido, terminando com a con-
clus~ao do argumento.
Exemplo 1.10 Construir uma demonstra»c~ao formal de validade para o seguinte argu-
mento, usando os s¶³mbolos sugeridos:
Wilson ser¶a eleito presidente do Centro Acade^mico ou ambos, H¶elio e L¶ucio ser~ao
eleitos vice-presidentes do Centro Acade^mico. Se Wilson for eleito presidente ou H¶elio
for eleito vice, ent~ao David encaminhar¶a um protesto. Portanto, ou Wilson ser¶a eleito
presidente do Centro Acade^mico ou David encaminhar¶a um protesto. (W;H;L;D).
Demonstra»c~ao.
1. W _ (H ^ L)
2. W _H ! D=:.: W _D
3. (W _H) ^ (W _ L) 1, Dist.
4. W _H (Hip./ Concl.)
5. D 2, 4, M.P.
6. D _W 5, Ad.
7. W _D 6, Com.
22 L¶ogica Elementar
Existe um outro m¶etodo de demonstra»c~ao chamado demonstra»c~ao indireta, ou
m¶etodo de demonstra»c~ao por redu»c~ao ao absurdo. Uma demonstra»c~ao indireta de vali-
dade, para um dado argumento, ¶e feita incluindo-se, como premissa adicional, a nega»c~ao
de sua conclus~ao, e ent~ao derivando uma contradi»c~ao; assim que uma contradi»c~ao ¶e
obtida, a demonstra»c~ao est¶a completa.
Exemplo 1.11 De^ uma demonstra»c~ao indireta de validade para o seguinte argumento:
p _ q ! r
s! p ^ u
q _ s =:.: r
Demonstra»c~ao.
1. p _ q ! r
2. s! p ^ u
3. q _ s =:.: r
4. » r P.I. (Demonstra»c~ao Indireta)
5. » (p _ q) 1, 4, M.T.
6. » p^ » q 5, De M.
7. » p 6, Simp.
8. » q 6, Simp.
9. s 3, 8, S.D.
10. p ^ u 2, 9, M.P.
11. p 10, Simp.
12. p^ » p 7, 11, Conj.
A proposi»c~ao p^ » p, no passo 12, ¶e uma contradi»c~ao; portanto a demonstra»c~ao
indireta de validade est¶a completa.
Em contraste a uma \demonstra»c~ao indireta", a demonstra»c~ao formal de validade
introduzida anteriormente pode ser chamada \demonstra»c~ao direta". Numa demons-
tra»c~ao matem¶atica, pode ser usada uma demonstra»c~ao direta ou uma demonstra»c~ao
indireta. A escolha do m¶etodo de demonstra»c~ao, para um argumento matem¶atico dado,
depende da prefere^ncia e da convenie^ncia.
1.7.1 Exerc¶³cios
Para cada um dos seguintes argumentos, de^ uma demonstra»c~ao direta e uma demons-
tra»c~ao indireta de validade, e compare seus tamanhos.
L¶ogica Elementar 23
1. A _ (B ^ C) 4. A _B
B ! D » B _ C = :.: A _ C
C ! E
D ^ E ! A _ C
» A= :.: C
2. B _ (C ! E) 5. B _ C ! B ^ A
B ! D » B = :.: » C
» D! (E ! A)
» D= :.: C ! A
3. (A _B)! (A! D ^ E) 6. A ^B ! C
A ^D = :.: E _ F (A! C)! D
» B _E = :.: B ! D ^E
Nas demonstra»c~oes dos seguintes argumentos, use os s¶³mbolos sugeridos.
7. Se a popula»c~ao cresce rapidamente e a produ»c~ao permanece constante, ent~ao os
pre»cos sobem. Se os pre»cos sobem, ent~ao o governo controla os pre»cos. Se sou rico,
ent~ao n~ao me preocupo com o aumento dos pre»cos. N~ao ¶e verdade que n~ao sou rico. O
governo n~ao controla os pre»cos ou preocupo-me com o aumento dos pre»cos. Portanto,
n~ao ¶e verdade que a popula»c~aocresce rapidamente e a produ»c~ao permanece constante
(P : A popula»c~ao cresce rapidamente. C: A produ»c~ao permanece constante. S: Os
pre»cos sobem. G: O governo controla os pre»cos. R: Eu sou rico. A: Eu me preocupo
com o aumento dos pre»cos.)
8. Se Wilson ou Alberto ganham ent~ao L¶ucio e Susana choram. Susana n~ao est¶a
chorando. Portanto, Alberto n~ao ganhou. (W : Wilson ganha. A: Alberto ganha. L:
L¶ucio chora. S: Susana chora.)
9. Se eu me inscrevo neste curso e estudo bastante ent~ao tiro boas notas. Se tiro boas
notas, ¯co feliz. N~ao estou feliz. Portanto, n~ao me inscrevi neste curso ou n~ao estudei
bastante. (I: Me inscrevo neste curso. E: Estudo bastante. B: Tiro boas notas. F :
Estou feliz.)
1.8 Indu»c~ao Matem¶atica
Um outro m¶etodo de demonstra»c~ao, muito ¶util para demonstrar a validade de uma
proposi»c~ao P (n), envolvendo o n¶umero natural n, ¶e o seguinte princ¶³pio de indu»c~ao
matem¶atica.
Indu»c~ao Matem¶atica. Se P (n) ¶e uma proposi»c~ao envolvendo o n¶umero natural n,
tal que
(1) P (1) ¶e verdadeira, e
(2) P (k)) P (k + 1) para qualquer n¶umero natural arbitr¶ario k,
ent~ao P (n) ¶e verdadeira para todo n¶umero natural n.
24 L¶ogica Elementar
O princ¶³pio acima ¶e uma conseqÄue^ncia de um dos Axiomas de Peano para os
n¶umeros naturais.
De modo a aplicarmos o princ¶³pio de indu»c~ao matem¶atica para demonstrarmos
um teorema, o teorema tem que ser subdividido em casos, uma caso para cada n¶umero
natural. Assim, devemos veri¯car ambas as condi»c~oes (1) e (2). A veri¯ca»c~ao de (1),
habitualmente f¶acil, nos garante que o teorema ¶e verdadeiro pelo menos no caso n =
1. Para veri¯car a condi»c~ao (2), devemos provar um teorema auxiliar cuja premissa
(hip¶otese) ¶e \P (k) ¶e verdadeira", e cuja conclus~ao (tese) ¶e \P (k + 1) ¶e verdadeira". A
premissa \P (k) ¶e verdadeira" ¶e chamada a hip¶otese de indu»c~ao.
Exemplo 1.12 Demonstre, por indu»c~ao matem¶atica, que
1 + 2 + 3 + ¢ ¢ ¢+ n = n(n+ 1)
2
Demonstra»c~ao. Aqui P (n) representa a proposi»c~ao
\1 + 2 + 3 + ¢ ¢ ¢+ n = n(n+ 1)
2
"
Em particular, P (1) representa \1 = (1 ¢ 2)=2", que obviamente ¶e uma a¯rma»c~ao
verdadeira. Portanto, a condi»c~ao (1) para a indu»c~ao matem¶atica est¶a satisfeita.
Para demonstrar que a condi»c~ao (2) ¶e satisfeita, assumimos que \P (k)", que ¶e
\1 + 2 + 3 + ¢ ¢ ¢ + k = k(k + 1)=2", seja verdadeira. Ent~ao, somamos k + 1 a ambos
os membros da igualdade. Temos portanto
1 + 2 + 3 + ¢ ¢ ¢+ k + (k + 1) = k(k + 1)
2
+ (k + 1)
=
k(k + 1)
2
+
2(k + 1)
2
=
(k + 2)(k + 1)
2
=
(k + 1)(k + 2)
2
o que mostra que P (k + 1) ¶e verdadeira. Mostramos assim que as condi»c~oes (1) e (2)
da indu»c~ao matem¶atica s~ao satisfeitas. Portanto, pelo princ¶³pio de indu»c~ao matem¶atica,
1 + 2 + 3 + ¢ ¢ ¢+ n = n(n+ 1)=2 ¶e verdadeira para cada n¶umero natural n.
A id¶eia de indu»c~ao matem¶atica pode ser usada para fazer de¯ni»c~oes matem¶aticas
envolvendo n¶umeros naturais. Por exemplo, a de¯ni»c~ao de pote^ncias de um n¶umero real
qualquer x podem ser de¯nidas por:
x1 = x
xn+1 = xn ¢ x; para cada n¶umero natural n
L¶ogica Elementar 25
As duas equa»c~oes acima indicam que x1 = x, x2 = x ¢ x, x3 = x2 ¢ x, : : : e assim
por diante. Como outra aplica»c~ao, daremos a seguinte de¯ni»c~ao indutiva do s¶³mbolo
C(n; r).
De¯ni»c~ao 1.7 Sejam n um n¶umero natural e r um inteiro. O s¶³mbolo C(n; r) ¶e de¯nido
por
C(0; 0) = 1, C(0; r) = 0 para cada r6= 0, e
C(n+ 1; r) = C(n; r) + C(n; r ¡ 1)
Teorema 1.8 Se n e r s~ao inteiros, tais que 0 6 r 6 n, ent~ao
C(n; r) =
n!
r!(n¡ r)!
sendo n! o produto n ¢ (n¡1) ¢ ¢ ¢ 3 ¢2 ¢1, dos primeiros n n¶umeros naturais consecutivos,
se n > 0 e 0! = 1 por conven»c~ao.
Demonstra»c~ao. Exerc¶³cio.
Teorema 1.9 (O Teorema Binomial) Se x e y s~ao dois n¶umeros reais e n ¶e um
n¶umero natural, ent~ao
(x+ y)n = C(n; 0)xn + C(n; 1)xn¡1y + ¢ ¢ ¢+ C(n; r)xn¡ryr + ¢ ¢ ¢+ C(n; n)yn
Demonstra»c~ao. Demonstraremos a validade deste teorema por indu»c~ao matem¶atica.
Primeiramente, o teorema ¶e claramente verdadeiro para n = 1. Para completar a
demonstra»c~ao, assumiremos a validade do teorema para n = k; isto ¶e, assumiremos
que
(x+ y)k = C(k; 0)xk + C(k; 1)xk¡1y + ¢ ¢ ¢+ C(k; r)xk¡ryr + ¢ ¢ ¢+ C(k; k)yk
Ent~ao, multiplicando ambos os membros da igualdade acima por (x+ y), temos
(x+ y)k+1 = (x+ y)[xk + C(k; 1)xk¡1y + ¢ ¢ ¢+ C(k; r)xk¡ryr + ¢ ¢ ¢+ yk]
= xk+1 + [C(k; 0) + C(k; 1)]xky + ¢ ¢ ¢
+ [C(k; r ¡ 1) + C(k; r)]x(k+1)¡ryr + ¢ ¢ ¢+ yk+1
= C(k + 1; 0)xk+1 + C(k + 1; 1)xky + ¢ ¢ ¢
+ C(k + 1; r)xk+1¡ryr + ¢ ¢ ¢+ C(k + 1; k + 1)yk+1
que mostra que o teorema ¶e v¶alido para n = k + 1 se for v¶alido para n = k.
Assim, por indu»c~ao matem¶atica, o teorema binomial ¶e verdadeiro para todos os
n¶umeros naturais n.
26 L¶ogica Elementar
1.8.1 Exerc¶³cios
1. Demonstre o teorema 1.8 por indu»c~ao matem¶atica.
2. Mostre que C(n; 0) = 1 = C(n; n) para todo n¶umero natural n.
3. Demonstre por indu»c~ao matem¶atica que, para todo n¶umero natural n,
1 ¢ 2 + 2 ¢ 3 + ¢ ¢ ¢+ r ¢ (r + 1) + ¢ ¢ ¢+ n ¢ (n+ 1) = 1
3
n(n+ 1)(n+ 2):
4. Demonstre por indu»c~ao matem¶atica que, para todo n¶umero natural n,
12 + 22 + 32 + ¢ ¢ ¢+ n2 = 1
6
n(n+ 1)(2n+ 1):
5. Demonstre que para todo n¶umero natural n,
13 + 23 + 33 + ¢ ¢ ¢+ n3 = 1
4
n2(n+ 1)2:
6. Demonstre que para todo n¶umero natural n, 1 + 3 + 5 + ¢ ¢ ¢+ (2n¡ 1) = n2.
7. Demonstre que para todo n¶umero natural n,
1
1 ¢ 2 +
1
2 ¢ 3 +
1
3 ¢ 4 + ¢ ¢ ¢+
1
n ¢ (n+ 1) =
n
n+ 1
:
8. Demonstre as seguintes Leis de De Morgan Generalizadas,
(a) » (p1 ^ p2 ^ ¢ ¢ ¢ ^ pn),» p1 _ » p2 _ ¢ ¢ ¢ _ » pn
(b) » (p1 _ p2 _ ¢ ¢ ¢ _ pn),» p1 ^ » p2 ^ ¢ ¢ ¢ ^ » pn
9. Demonstre as seguintes Leis Distributivas Generalizadas.
(a) p ^ (q1 _ q2 _ ¢ ¢ ¢ _ qn), (p ^ q1) _ (p ^ q2) _ ¢ ¢ ¢ _ (p ^ qn)
(b) p _ (q1 ^ q2 ^ ¢ ¢ ¢ ^ qn), (p _ q1) ^ (p _ q2) ^ ¢ ¢ ¢ ^ (p _ qn)
2
O Conceito de Conjunto
Neste cap¶³tulo, apresentamos os conceitos de conjuntos, subconjuntos, e opera»c~oes entre
conjuntos (uni~ao, interse»c~ao, e complementa»c~ao), juntamente com as regras fundamen-
tais dessas opera»c~oes. Estas s~ao desenvolvidas em paralelo com o Cap¶³tulo 1 sobre l¶ogica.
Fam¶³lias indexadas de conjuntos s~ao discutidas. O Cap¶³tulo termina com o Paradoxo de
Russel e uma nota hist¶orica.
2.1 Conjuntos e subconjuntos
\O que ¶e um conjunto" ¶e uma quest~ao muito dif¶³cil de se responder.1 Neste tratado
elementar, n~ao entraremos em nenhuma abordagem axiom¶atica complicada da Teoria dos
Conjuntos, e conter-nos-emos em aceitar o seguinte: um conjunto ¶e qualquer cole»c~ao,
dentro de um todo de objetos de¯nidos e distingÄu¶³veis, chamados elementos, de nossa
intui»c~ao ou pensamento. Esta de¯ni»c~ao intuitiva de um conjunto foi dada primeiramente
por Georg Cantor (1845{1918), que criou a teoria dos conjuntos em 1895. Exemplos:
(a) O conjunto de todas as cadeiras na sala de aula de Teoria dos Conjuntos.
(b) O conjunto de todos os estudantes desta universidade.
(c) O conjunto das letras a, b, c e d.
(d) O conjunto das regras de uso do laborat¶orio de inform¶atica.
(e) O conjunto de todos os n¶umeros racionais cujo quadrado ¶e 2.
(f) O conjunto de todos os n¶umeros naturais.
(g) O conjunto de todos os n¶umeros reais entre 0 e 1.
Um conjunto que cont¶em apenas um n¶umero ¯nito de elementos ¶e chamado um
conjunto ¯nito; um conjunto in¯nito ¶e um conjunto que n~ao ¶e ¯nito. Exemplos de (a) a
(e) acima s~ao todos de conjuntos ¯nitos, e Exemplos (f) e (g) s~ao de conjuntos in¯nitos.
Conjuntos s~ao freqÄuentemente designados fechando-se entre chaves os s¶³mbolos
que representam seus elementos, quando for poss¶³vel faze^-lo. Assim, o conjunto no Ex-
emplo (c) ¶e fa; b; c; dg e o conjunto no Exemplo (f) pode ser denotado por f1; 2; 3; : : : g.
1O estudante tomar¶a cie^ncia da di¯culdade quando chegarmos µas se»c~oes 2.7 e 2.8.
2728 O Conceito de Conjunto
O conjunto do Exemplo (e) n~ao tem elementos; um tal conjunto ¶e chamado o conjunto
vazio, sendo denotado pelo s¶³mbolo ¿.
Usaremos letras mai¶usculas para denotar conjuntos, e letras min¶usculas para de-
notar elementos. Se a ¶e um elemento de um conjunto A, escrevemos a 2 A (leia-se: \a
¶e um elemento de A" ou \a pertence a A"), enquanto que a62 A signi¯ca que a n~ao ¶e
elemento de A.
De¯ni»c~ao 2.1 Dois conjuntos A e B s~ao iguais ou ide^nticos quando cont¶em os mesmos
elementos. Isto ¶e, A = B signi¯ca (8x)[(x 2 A)$ (x 2 B)].
A ordem em que aparecem os elementos num conjunto n~ao tem importa^ncia. As-
sim, o conjunto fa; b; cg ¶e o mesmo que fb; c; ag, etc. Al¶em disso, como os elementos de
um conjuntos s~ao distintos, fa; a; bg, por exemplo, n~ao ¶e uma nota»c~ao apropriada de um
conjunto, e deveria ser substitu¶³da por fa; bg. Se a ¶e um elemento de um conjunto, a e
fag s~ao considerados diferentes, isto ¶e, a6= fag. Pois fag denota o conjunto consistindo
do elemento a somente, enquanto que a ¶e apenas o elemento do conjunto fag.
De¯ni»c~ao 2.2 Sejam A e B conjuntos. Se todo elemento de A ¶e elemento de B,
ent~ao A ¶e chamado um subconjunto de B, em s¶³mbolos: A ½ B ou B ¾ A. Se A ¶e
subconjunto de B, ent~ao B ¶e chamado um superconjunto de A.
Assim, escrevendo logicamente,
A ½ B ´ (8x)[(x 2 A)! (x 2 B)]
Obviamente, todo conjunto ¶e um subconjunto (e um superconjunto) de si mesmo.
Quando A ½ B e A 6= B, escrevemos A Ã B, ou B ! A, e dizemos que A ¶e um
subconjunto pr¶oprio de B, ou que B ¶e um superconjunto pr¶oprio de A. Em outras
palavras, A ¶e um subconjunto pr¶oprio de B quando todo elemento de A ¶e um elemento
de B, mas existe um elemento de B que n~ao ¶e elemento de A. Se A n~ao ¶e subconjunto
de B, escrevemos A6½ B.
Teorema 2.1 O conjunto ¿ ¶e um subconjunto de qualquer conjunto.
Demonstra»c~ao. Seja A um conjunto qualquer. Provaremos que a proposi»c~ao condicional
(x 2 ¿)! (x 2 A)
¶e verdadeira para todo x. Como o conjunto ¿ n~ao tem nenhum elemento, a a¯rma»c~ao
\x 2 ¿" ¶e falsa, enquanto que \x 2 A" pode ser verdadeira ou falsa. Em qualquer dos
casos, a a¯rma»c~ao condicional \(x 2 ¿) ! (x 2 A)" ¶e verdadeira, conforme a tabela
verdade para a condicional (casos 3 e 4 da Tabela 1.5, Cap¶³tulo 1).
Assim, ¿ ½ A, para qualquer conjunto A.
O Conceito de Conjunto 29
Teorema 2.2 Se A ½ B e B ½ C ent~ao A ½ C.
Demonstra»c~ao. Demonstraremos que (x 2 A)) (x 2 C):
(x 2 A) ) (x 2 B); porque A ½ B
) (x 2 C); porque B ½ C
Portanto, pela Lei Transitiva (Teorema 1.4(c) do Cap¶³tulo 1), temos
(x 2 A)) (x 2 C)
ConseqÄuentemente, demonstramos que A ½ C.
2.1.1 Exerc¶³cios
1. Demonstre que o conjunto de letras da palavra \catarata" e o conjunto de letras da
palavra \catraca" s~ao iguais.
2. Decida, dentre os seguintes conjuntos, quais s~ao subconjuntos de quais:
(a) A = ftodos os n¶umeros reais satisfazendo x2 ¡ 8x+ 12 = 0g
(b) B = f2; 4; 6g
(c) C = f2; 4; 6; 8; : : : g
(d) D = f6g
3. Liste todos os subconjuntos do conjunto f¡1; 0; 1g.
4. Demonstre que [(A ½ B) ^ (B ½ A)] , (A = B) [Nota: FreqÄuentemente, em
matem¶atica, o melhor meio de demonstrar que A = B ¶e mostrar que A ½ B e B ½ A.]
5. Demonstre que (A ½ ¿)) (A = ¿).
6. Demonstre que
(a) [(A Ã B) ^ (B ½ C)]) (A Ã C)
(b) [(A ½ B) ^ (B Ã C)]) (A Ã C)
7. De^ um exemplo de um conjunto cujos elementos s~ao tamb¶em conjuntos.
8. Em cada um dos seguintes itens, determine se a a¯rma»c~ao ¶e verdadeira ou falsa.
Se for verdadeira, demonstre-a. Se for falsa, mostre-o atrav¶es de um exemplo (um tal
exemplo, mostrando que uma proposi»c~ao ¶e falsa, ¶e chamado um contra-exemplo).
(a) Se x 2 A e A 2 B ent~ao x 2 B.
(b) Se A ½ B e B 2 C ent~ao A 2 C.
(c) Se A6½ B e B ½ C ent~ao A6½ C.
(d) Se A6½ B e B6½ C ent~ao A6½ C.
(e) Se x 2 A e A6½ B ent~ao x62 B.
(f) Se A ½ B e x62 B ent~ao x62 A.
9. Dado um conjunto com n elementos, demonstre que existem exatemente C(n; r)
subconjuntos com r elementos.
30 O Conceito de Conjunto
2.2 Especi¯ca»c~ao de conjuntos
Um modo de construir um novo conjunto, a partir de um conjunto dado, ¶e especi¯car
aqueles elementos, do conjunto dado, que satisfazem uma propriedade particular. Por
exemplo, seja A o conjunto de todos os estudantes desta universidade. A proposi»c~ao \x
¶e paulista" ¶e verdadeira para alguns elementos x de A e falsa para outros. Empregaremos
a nota»c~ao
fx 2 A jx ¶e paulistag
para especi¯car o conjunto de todas os estudantes paulistas desta universidade. Similar-
mente,
fx 2 A jx n~ao ¶e paulistag
especi¯ca o conjunto de estudantes n~ao paulistas desta universidade.
Como regra, a todo conjunto A e a toda proposi»c~ao p(x) sobre x 2 A, existe um
conjunto fx 2 A j p(x)g, cujos elementos s~ao precisamente aqueles elementos x 2 A
para os quais a a¯rma»c~ao p(x) ¶e verdadeira. Numa abordagem axiom¶atica da teoria dos
conjuntos, esta regra ¶e habitualmente postulada como um axioma, chamado o Axioma
da Especi¯ca»c~ao. O s¶³mbolo fx 2 A j p(x)g ¶e lido: o conjunto de todos os x em A tais
que p(x) ¶e verdadeira. A nota»c~ao da forma fx 2 A j p(x)g, que descreve um conjunto ¶e
chamada a nota»c~ao de constru»c~ao do conjunto.
Exemplo 2.1 Seja R o conjunto dos n¶umeros reais. Ent~ao
(a) fx 2 R jx = x+ 1g ¶e o conjunto vazio.
(b) fx 2 R j 2x2 ¡ 5x¡ 3 = 0g ¶e o conjunto f¡1=2; 3g.
(c) fx 2 R j x2 + 1 = 0g ¶e o conjunto vazio.
Por causa de freqÄuente aparecimento, atrav¶es do restante deste e dos demais
cap¶³tulos, e em outros t¶opicos de matem¶atica, os seguintes s¶³mbolos especiais ser~ao
reservados para os conjuntos descritos:
R = fx jx ¶e um n¶umero realg
Q = fx jx ¶e um n¶umero racionalg
Z = fx jx ¶e um n¶umero inteirog
N = fx jx ¶e um n¶umero naturalg
I = fx 2 R j 0 · x · 1g
R+= fx 2 R j x > 0g
Note que N ½ Z ½ Q ½ R e N ½ R+ ½ R.
¶E bem poss¶³vel que elementos de um conjunto possam ser tamb¶em conjuntos. Por
exemplo, o conjunto de todos os subconjuntos de um conjunto dado A tem conjuntos
como seus elementos. Este conjunto ¶e chamado conjunto das partes2 de A, e ¶e denotado
2Na teoria dos conjuntos, a existe^ncia do conjunto das partes n~ao ¶e tida como ¶obvia. Como a
existe^ncia de um conjunto das partes n~ao ¶e conseqÄue^ncia do axioma da especi¯ca»c~ao, um novo axioma
¶e necess¶ario; este axioma ¶e habitualmente chamado o Axioma do Conjunto das Partes e pode ser assim
enunciado: Para cada conjunto, existe um conjunto de conjuntos que consiste de todos os subconjuntos
do conjunto dado.
O Conceito de Conjunto 31
por }(A).
Exemplo 2.2 }(fag) = f¿; fagg, }(¿) = f¿g, e }(fa; bg) =
f¿; fag; fbg; fa; bgg.
Teorema 2.3 Se A consiste de n elementos, ent~ao seu conjunto das partes }(A) cont¶em
exatamente 2n elementos.
Demonstra»c~ao. O teorema ¶e claramente verdadeiro para A = ¿. Para um conjunto n~ao
vazio A, seja A = fa1; a2; a3; : : : ; ang. Dado um elemento ak de A, para cada subcon-
junto de A temos duas possibilidades: ou ele cont¶em ak ou n~ao o cont¶em. Portanto,
o problema de encontrar o n¶umero de subconjuntos de A pode ser considerado como o
problema de preencher uma lista de n espa»cos em branco 2 2 2 ¢ ¢ ¢2, aleatoriamente,
com os n¶umeros 0 e 1, um n¶umero em cada espa»co. Cada preenchimento dos n espa»cos
determina um subconjunto X de A da seguinte maneira: ak 2 X se e somente se 1
aparece no k-¶esimo espa»co (para cada k 2 f1; 2; : : : ; ng). Como existem exatamente
2n preenchimentos distintos, existem 2n subconjuntos de A.
¶E tamb¶em interessante a seguinte demonstra»c~ao alternativa do Teorema 2.3:
Demonstra»c~ao alternativa. Primeiramente, o conjunto vazio ¿ pertence a }(A). Em
seguida, cada elemento x 2 A forma um subconjunto fxg pertencente a }(A). Observe
que o n¶umero desse conjuntos unit¶arios ¶e C(n; 1). Continuando, existem exatamente
C(n; 2) subconjuntos de A contendo exatemente 2 elementos de A.3 Finalmente, existe
exatamente C(n; n) = 1 subconjuntode A contendo n elementos de A, que ¶e o pr¶oprio
A. Contando o conjunto vazio, o n¶umero total de subconjuntos de A ¶e igual a C(n; 0)+
C(n; 1) + ¢ ¢ ¢+ C(n; n). Ent~ao, usando a expans~ao binomial para (1 + 1)n, temos
(1 + 1)n = C(n; 0) + C(n; 1) + ¢ ¢ ¢+ C(n; n)
Assim, o n¶umero de elementos de }(A) ¶e (1 + 1)n = 2n.
2.2.1 Exerc¶³cios
1. Exiba entre chaves os elementos de cada um dos seguintes conjuntos.
A = fx 2 N jx < 5g
B = fx 2 Z j x2 · 25g
C = fx 2 Q j 10x2 + 3x¡ 1 = 0g
D = fx 2 R jx3 + 1 = 0g
E = fx 2 R+ j 4x2 ¡ 4x¡ 1 = 0g
2. Denote cada um dos seguintes conjuntos pela nota»c~ao de constru»c~ao do conjunto.
A = f1; 2; 3g
B = f¡1;¡2
3
;¡1
3
; 0g
3Veja problema 9, Exerc¶³cios 2.1.1
32 O Conceito de Conjunto
C = f1; 3; 5; 7; 9; : : : g
D = f1¡p3; 1 +p3g
3. Quais s~ao os elementos do conjunto das partes do conjunto fx; fy; zgg? Quantos
elementos tem esse conjunto das partes?
4. Seja B um subconjunto de A, e seja }(A : B) = fX 2 }(A) jX ¾ Bg.
(a) Seja B = fa; bg e A = fa; b; c; d; eg. Liste os membros do conjunto }(A : B);
quantos s~ao eles?
(b) Demonstre que }(A : ¿) = }(A).
5. Sejam A um conjunto com n elementos e B um subconjunto com m elementos,
n ¸ m.
(a) Encontre o n¶umero de elementos do conjunto }(A : B).
(b) Deduza o Teorema 2.3 a partir de (a), fazendo B = ¿.
2.3 Uni~oes e interse»c~oes
Na aritm¶etica, podemos somar, multiplicar, ou subtrair dois n¶umeros quaisquer. Na teoria
dos conjuntos, h¶a tre^s opera»c~oes|uni~ao, interse»c~ao, e complementa»c~ao| respectiva-
mente an¶alogas µas opera»c~oes adi»c~ao, multiplica»c~ao, e subtra»c~ao de n¶umeros.
De¯ni»c~ao 2.3 A uni~ao de dois conjuntos quaisquer A e B, denotada por A [ B, ¶e o
conjunto dos elementos x tais que x pertence a pelo menos um dos dois conjuntos A e
B. Ou seja, x 2 A [B se e somente se x 2 A _ x 2 B.
De¯ni»c~ao 2.4 A interse»c~ao de dois conjuntos quaisquer A e B, denotada por A \ B,
¶e o conjunto dos elementos x tais que x pertence a ambos os conjuntos A e B. Em
s¶³mbolos, A \ B = fx j (x 2 A) ^ (x 2 B)g, ou fx 2 A jx 2 Bg. Se A \ B = ¿,
dizemos que A e B s~ao conjuntos disjuntos.
Por exemplo, se A = f1; 2; 3; 4g e B = f3; 4; 5g, ent~ao A [ B = f1; 2; 3; 4; 5g e
A \ B = f3; 4g; se Im denota o conjunto de n¶umeros imagin¶arios, ent~ao os conjuntos
Im e R s~ao disjuntos.
Exemplo 2.3 No que segue, os conjuntos I;N;Z; : : : s~ao de¯nidos como na ¶ultima
se»c~ao.
(a) I \ Z = f0; 1g e N \ I = f1g.
(b) Z [Q = Q e Z \Q = Z.
(c) I [ I = I e I \ I = I.
O Conceito de Conjunto 33
Teorema 2.4 Sejam X um conjunto e A, B e C subconjuntos de X. Ent~ao temos:
(a) Os elementos neutros:
A [ ¿ = A
A \X = A
(b) As leis de idempote^ncia:
A [ A = A
A \ A = A
(c) As leis comutativas:
A [B = B [ A
A \B = B \ A
(d) As leis associativas:
A [ (B [ C) = (A [B) [ C
A \ (B \ C) = (A \B) \ C
(e) As leis distributivas:
A \ (B [ C) = (A \B) [ (A \ C)
A [ (B \ C) = (A [B) \ (A [ C)
Demonstra»c~ao. Deixaremos as demonstra»c~oes das partes (a), (b) e (c) para o leitor,
como exerc¶³cios.
(d) De acordo com a De¯ni»c~ao 2.3,
x 2 A [ (B [ C), x 2 A _ (x 2 B [ C)
e
x 2 B [ C , x 2 B _ x 2 C
Assim,
x 2 A [ (B [ C), x 2 A _ (x 2 B _ x 2 C)
Pela Lei Associativa (para a disjun»c~ao), (x 2 A) _ (x 2 B _ x 2 C) ¶e equivalente a
(x 2 A _ x 2 B) _ (x 2 C). A ¶ultima a¯rma»c~ao, pela De¯ni»c~ao 2.3, ¶e equivalente a
(x 2 A [B) _ (x 2 C), e portanto x 2 (A [B) [ C.
Assim, temos
x 2 A [ (B [ C), x 2 (A [B) [ C
Pela de¯ni»c~ao 2.1, A [ (B [ C) = (A [B) [ C.
A demonstra»c~ao acima pode ser condensada em uma exposi»c~ao limpa de passos
l¶ogicos essenciais, com a justi¯cativa de cada passo escrita µa direita para f¶acil refere^ncia:
34 O Conceito de Conjunto
x 2 A [ (B [ C) , (x 2 A) _ (x 2 B [ C) Def. de [
, (x 2 A) _ [(x 2 B) _ (x 2 C)] Def. de [
, [(x 2 A) _ (x 2 B)] _ (x 2 C) Assoc. para _
, (x 2 A [B) _ (x 2 C) Def. de [
, x 2 (A [B) [ C Def. de [
Portanto, pela De¯ni»c~ao 2.1, acabamos de provar que A[ (B[C) = (A[B)[C.
O estudante deveria tentar apreciar este tipo de demonstra»c~ao, ordenada precisa-
mente pela l¶ogica.
Deixaremos a demonstra»c~ao de A \ (B \ C) = (A \ B) \ C ao leitor, como
exerc¶³cio.
(e) Novamente, apenas a primeira parte do item (e) ser¶a demonstrada, sendo a segunda
parte deixada como exerc¶³cio.
x 2 A \ (B [ C) , (x 2 A) ^ (x 2 B [ C) Def. de \
, (x 2 A) ^ [(x 2 B) _ (x 2 C)] Def. de [
, [(x 2 A) ^ (x 2 B)] _ [(x 2 A) ^ (x 2 C)]
Lei Dist. da l¶ogica (Cap. 1)
, (x 2 A \B) _ (x 2 A \ C) Def. de \
, x 2 (A \B) [ (A \ C) Def. de [
Portanto, pela De¯ni»c~ao 2.1, A \ (B [ C) = (A \B) [ (A \ C).
2.3.1 Exerc¶³cios
1. Demonstre que A ½ B , A [B = B.
2. Demonstre que A ½ B , A \B = A.
3. Demonstre as partes (a), (b), e (c) do Teorema 2.4.
4. Demonstre a segunda metade do Teorema 2.4(d).
5. Demonstre a segunda metade do Teorema 2.4(e).
6. Demonstre que
(a) A ½ C e B ½ C implica A [B ½ C.
(b) A ½ B e A ½ C implica A ½ B \ C.
[Sugest~ao: Use o Teorema 1.5, do Cap¶³tulo 1, se desejar.]
7. Demonstre que (A \B) [ C = A \ (B [ C), C ½ A.
8. Demonstre que se A ½ B ent~ao }(A) ½ }(B).
9. Demonstre que A [B = A \B , A = B.
10. Demonstre que se A ½ B, ent~ao A [ C ½ B [ C e A \C ½ B \C, para qualquer
conjunto C.
11. Demonstre que se A ½ C e B ½ D ent~ao A [B ½ C [D.
O Conceito de Conjunto 35
2.4 Complementos
Existe, na teoria dos conjuntos, uma opera»c~ao conhecida como complementa»c~ao, que ¶e
similar µa opera»c~ao de subtra»c~ao na aritm¶etica.
De¯ni»c~ao 2.5 Se A e B s~ao conjuntos, o complemento relativo de B em A ¶e o conjunto
A¡B, de¯nido por
A¡B = fx 2 A j x62 Bg
Nesta de¯ni»c~ao, n~ao ¶e assumido que B ½ A.
Exemplo 2.4 Sejam
A = fa; b; c; dg e B = fc; d; e; fg
Encontre A¡B e A¡ (A \B).
Solu»c~ao.
A¡B = fa; b; c; dg ¡ fc; d; e; fg = fa; bg
e
A¡ (A \B) = fa; b; c; dg ¡ fc; dg = fa; bg
Embora o conjunto universal no sentido absoluto, o conjunto de todos os conjuntos,
n~ao exista (veja o Paradoxo de Russel na se»c~ao 2.7), n~ao h¶a problema em assumirmos
temporariamente que todos os conjuntos mencionados, no restante deste e dos demais
cap¶³tulos, s~ao subconjuntos de um conjunto ¯xado U , que pode ser considerado (tem-
porariamente) como um conjunto universal no sentido restrito. De modo a enunciar as
regras b¶asicas a respeito de complementa»c~oes, do modo mais simples poss¶³vel, assumire-
mos, a menos que seja dito em contr¶ario, que todos os complementos s~ao formados
relativamente a este conjunto U . Escreveremos ent~ao A0 como sendo U ¡A.
Exemplo 2.5 Demonstre que A¡B = A \B0.
Solu»c~ao.
x 2 A \B0 ´ (x 2 A) ^ (x 2 U ¡B) Def. de \, Def. de 0
´ (x 2 A) ^ [(x 2 U) ^ (x62 B)] Def. 2.5
´ (x 2 A \ U) ^ (x62 B)] Assoc. de ^, Def. de \
´ (x 2 A) ^ (x62 B) A \ U = A
, x 2 (A¡B) Def. 2.5
Portanto, pela De¯ni»c~ao 2.1, A \B0 = A¡B.
36 O Conceito de Conjunto
Teorema 2.5 Sejam A e B conjuntos. Ent~ao
(a) (A0)0 = A.
(b) ¿0 = U e U 0 = ¿.
(c) A \ A0 = ¿ e A [A0 = U .
(d) A ½ B se e somente se B0 ½ A0
Demonstra»c~ao. As demonstra»c~oes das partes (a), (b), e (c) usam apenas de¯ni»c~oes e
s~ao deixadas ao leitor, como exerc¶³cio. Daremos uma demonstra»c~ao da parte (d):
A ½ B ´ [(x 2 A)! (x 2 B)] Def. de ½
´ [(x62 B)! (x62 A)] 4 Contrap.
´ [(x 2 B0)! (x 2 A0)] Def. de 0
´ B0 ½ A0 Def. de ½
Portanto, acabamos de demonstrar que (A ½ B) ´ (B0 ½ A0).
Na demonstra»c~ao acima, novamente s¶³mbolos e leis da l¶ogica (do Cap¶³tulo 1) s~ao
usados, o que nos permite exibir cada passo da demonstra»c~ao de maneira simples e
elegante, com justi¯cativas ao lado direito. O leitor ¶e encorajado a fazer uso total do
Cap¶³tulo 1, nas demonstra»c~oes, sempre que poss¶³vel.
A propriedade mais ¶util de complementos ¶e o seguinte Teorema de De Morgan.
Compare-o com as Leis de De Morgan no Cap¶³tulo 1.
Teorema 2.6 (Teorema de De Morgan) Para quaisquer dois conjuntosA e B,
(a) (A [B)0 = A0 \B0
(b) (A \B)0 = A0 [B0.
Demonstra»c~a de (a):
x 2 (A [B)0 ´» [x 2 A [B] Def. de 0
´» [(x 2 A) _ (x 2 B)] Def. de [
´» (x 2 A)^ » (x 2 B) De M. da l¶ogica
´ (x 2 A0) ^ (x 2 B0) Def. de 0
´ x 2 (A0 \B0) Def. de \
Portanto, pela De¯ni»c~ao 2.1, (A [B)0 = A0 \B0.
A demonstra»c~ao de (b) ¶e deixada ao leitor.
4Lembremo-nos que a nega»c~ao de x 2 B, » (x 2 B), ¶e denotada por x62 B.
O Conceito de Conjunto 37
Exemplo 2.6 Sejam A, B, e C tre^s conjuntos quaisquer. Decida se o conjunto
A \ (B ¡ C) ¶e o mesmo que (A \B)¡ (A \ C).
Solu»c~ao.
(A \B)¡ (A \ C) = (A \B) \ (A \ C)0 Exemplo 2.5
= (A \B) \ (A0 [ C 0) Teor. de De M. (Teor. 2.6)
= (A \B \ A0) [ (A \B \ C 0) Dist.
= (A \A0 \B) [ (A \B \ C 0) Com.
= ¿ [ [A \ (B \ C 0)] Teor. 2.5(c): A \ A0 = ¿
= A \ (B ¡ C) Teor. 2.4(a), Exemplo 2.5
Portanto, demonstramos que A \ (B ¡ C) = (A \B)¡ (A \ C).
2.4.1 Exerc¶³cios
1. Sejam A e B conjuntos. Demonstre que A¡B = A¡ (A \B).
2. Demonstre as partes (a), (b), e (c) do Teorema 2.5.
3. Sejam A e B conjuntos. Demonstre que B ½ A0 se e somente se A \B = ¿.
4. Sejam A e B conjuntos. Demonstre que (A¡B) [B = A se e somente se B ½ A.
5. Demonstre o Teorema 2.6(b).
6. Sejam A, B, e C tre^s conjuntos quaisquer. Demonstre que
(a) (A¡ C) [ (B ¡ C) = (A [B)¡ C,
(b) (A¡ C) \ (B ¡ C) = (A \B)¡ C.
7. Sejam A e B dois conjuntos quaisquer. Demonstre que A e B ¡ A s~ao disjuntos, e
que A [ B = A [ (B ¡ A). (Isto mostra como representar a uni~ao A [ B como uma
uni~ao disjunta.)
8. Sejam A, B, e C tre^s conjuntos quaisquer. Demonstre que
(a) (A \B \ C)0 = A0 [B0 [ C 0
(b) (A [B [ C)0 = A0 \B0 \ C 0.
Generalize estes resultados a proposi»c~oes envolvendo n conjuntos
A1; A2; A3; : : : ; An:
9. Para conjuntos quaisquer A e B demonstre ou refute que
(a) }(A) \ }(B) = }(A \B)
(b) }(A) [ }(B) = }(A [B).
10. Demonstre que se A ½ C, B ½ C, A [B = C, e A \B = ¿, ent~ao A = C ¡B.
11. Sejam A e B dois conjuntos quaisquer. Demonstre que
(A¡B) [ (B ¡ A) = (A [B)¡ (A \B):
38 O Conceito de Conjunto
2.5 Diagramas de Venn
Como aux¶³lio na vizualiza»c~ao de opera»c~oes de conjuntos, introduziremos diagramas,
chamados diagramas de Venn, que representam conjuntos geometricamente. Repre-
sentaremos o conjunto universal relativo U por um reta^ngulo, e os subconjuntos de U
por c¶³rculos desenhados dentro do reta^ngulo. Por exemplo, na Figura 1, representamos
dois conjuntos A e B como dois c¶³rculos sombreados; a parte duplamente hachurada ¶e
a interse»c~ao A \B, e a ¶area sombreada total ¶e a uni~ao A [B.
Figura 1.
A Figura 2 mostra dois conjuntos A e B que s~ao disjuntos. A ¶area sombreada na
Figura 3 representa o complemento A0 do conjunto A. O conjunto A¡B, o complemento
relativo de B em A, ¶e representado pela parte sombreada na Figura 4.
Figura 2.
Figura 3.
O Conceito de Conjunto 39
Figura 4.
Figura 5.
Figura 6.
Um diagrama de Venn t¶³pico de tre^s conjuntos A, B, e C pode ser desenhado
como na Figura 5. Esses tre^s conjuntos dividem o conjunto universal U em 8 partes, tal
como indicado na ¯gura 6.
Usando os diagramas acima, podemos dar argumentos heur¶³sticos simples para
a validade de, por exemplo, a lei distributiva A \ (B [ C) = (A \ B) [ (A \ C),
como segue: Da Figura 6, A \ (B [ C) consiste das ¶areas 2, 3 e 7. Por outro lado,
(A\B)[ (A\C) ¶e representada pela uni~ao das ¶areas 2 e 7, e ¶areas 3 e 7. Portanto, a
igualdade A\(B[C) = (A\B)[(A\C) parece plaus¶³vel. Entretanto, em matem¶atica,
um argumento heur¶³stico n~ao pode ser aceito como uma demonstra»c~ao.
40 O Conceito de Conjunto
2.5.1 Exerc¶³cios
1. Desenhe um diagrama de Venn para A ½ B.
2. Desenhe diagramas de Venn para A \B0, A0 \B e A0 \B0.
3. Desenhe diagramas de Venn para A [B0, A0 [B e A0 [B0.
Nos problemas de 4 a 10, desenhe diagramas de Venn e de^ argumentos heur¶³sticos
de que cada uma das a¯rma»c~oes ¶e plaus¶³vel.
4. A \ (B \ C) = (A \B) \ C.
5. A [ (B [ C) = (A [B) [ C.
6. A [ (B \ C) = (A [B) \ (A [ C).
7. (A [B)0 = A0 \B0.
8. (A \B)0 = A0 [B0.
9. A \ (B ¡ A) = ¿ e A [ (B ¡ A) = A [B.
10. (A [B)¡ (A \B) = (A¡B) [ (B ¡ A).
2.6 Fam¶³lias indexadas de conjuntos
Recordemos que um conjunto ¶e uma cole»c~ao de elementos que s~ao todos distintos.
Grosseiramente falando, uma fam¶³lia ¶e uma cole»c~ao de objetos, n~ao necessariamente
distintos, chamados membros. Por exemplo, fa; a; ag ¶e uma fam¶³lia com tre^s membros,
a, a e a. Mas a mesma fam¶³lia fa; a; ag, considerada como um conjunto ¶e apenas o
conjunto unit¶ario fag com um ¶unico elemento, a.
Seja ¡ um conjunto e suponhamos que para cada elemento ° de ¡, existe um
conjunto associado A°. A fam¶³lia de todos esses conjuntos A° ¶e chamada uma fam¶³lia
indexada de conjuntos, indexada pelo conjunto ¡, e ¶e denotada por
fA° j ° 2 ¡g
Por exemplo, a fam¶³lia de conjuntos, f1; 2g; f2; 4g; f3; 6g; : : : ; fn; 2ng; : : : , pode
ser considerada como uma fam¶³lia indexada de conjuntos, indexada pelo conjunto N dos
n¶umeros naturais, sendo An = fn; 2ng para cada n 2 N. Esta fam¶³lia de conjuntos pode
ser denotada por ffn; 2ng jn 2 Ng.
Uma fam¶³lia arbitr¶aria de conjuntos pode parecer n~ao ser indexada, mas na maioria
dos casos podemos facilmente encontrar um conjunto ¡ que pode ser usado para indexar
a fam¶³lia de conjuntos dada.
Exemplo 2.7 Indexe a fam¶³lia F de conjuntos ¿;N;Z;Q;R;R.
Solu»c~ao. Como esta fam¶³lia cont¶em exatamente seis membros (embora dois deles sejam
o mesmo), escolhemos ¡ = f1; 2; 3; 4; 5; 6g e fazemos A1 = ¿, A2 = N, A3 = Z,
A4 = Q, A5 = R e A6 = R. A fam¶³lia de conjuntos est¶a ent~ao indexada.
Virtualmente todos os s¶³mbolos e nota»c~oes usados para conjuntos aplicam-se a
fam¶³lias tamb¶em. Por exemplo, ¿ 2 F e R+ 62 F indicam, respectivamente, que ¿
O Conceito de Conjunto 41
¶e um membro da fam¶³lia F e R+ n~ao ¶e membro de F. Podemos tamb¶em escrever
F = f¿;N;Z;Q;R;Rg.
Estendamos agora os conceitos de uni~ao [ e interse»c~ao \, das De¯ni»c~oes 1.3 e
1.4, a uma fam¶³lia arbitr¶aria de conjuntos.
De¯ni»c~ao 2.6 Seja F uma fam¶³lia arbitr¶aria de conjuntos. A uni~ao dos conjuntos em
F, denotada por
S
A2F A ou
S
F, ¶e o conjunto de todos os elementos que est~ao em A
para algum A 2 F. Ou seja,[
A2F
A = fx 2 U jx 2 A para algum A 2 Fg
Se a fam¶³lia F ¶e indexada pelo conjunto ¡, a seguinte nota»c~ao alternativa pode ser usada:[
°2¡
A° = fx 2 U jx 2 A° para algum ° 2 ¡g
Se o conjunto ¡ de¶³ndices ¶e ¯nito, ¡ = f1; 2; 3; : : : ; ng para algum n¶umero natural
n, nota»c~oes mais intuitivas, tais como
n[
i=1
Ai ou A1 [ A2 [ ¢ ¢ ¢ [ An
s~ao usadas freqÄuentemente para
S
°2¡A°.
Exemplo 2.8 Encontre a uni~ao da fam¶³lia de conjuntos
f1g; f2; 3g; f3; 4; 5g; : : : ; fn; n+ 1; : : : ; 2n¡ 1g:
Solu»c~ao. Esta fam¶³lia de conjuntos pode ser considerada como indexada por ¡ =
f1; 2; 3; : : : ; ng, sendo Ai = fi; i + 1; : : : ; 2i ¡ 1g, para cada i 2 ¡. O problema
se reduz a encontrar
Sn
i=1fi; i + 1; : : : ; 2i ¡ 1g. Observe que cada inteiro entre 1 e
2n ¡ 1 pertence a algum Ai na fam¶³lia, e nenhum outro elemento pertence a qualquer
desses Ai. Portanto,
n[
i=1
fi; i+ 1; : : : ; 2i¡ 1g = f1; 2; 3; : : : ; 2n¡ 1g
De¯ni»c~ao 2.7 Seja F uma fam¶³lia arbitr¶aria de conjuntos. A interse»c~ao de conjuntos
em F, denotada por
T
A2F ou
T
F, ¶e o conjunto de todos os elementos que est~ao em A
para todo A 2 F. Ou seja,\
A2F
= fx 2 U jx 2 A para todo A 2 Fg
42 O Conceito de Conjunto
Aqui, a a¯rma»c~ao \x 2 A para todo A 2 F" pode ser expressada alternativamente
como \A 2 F ! x 2 A. Esta ¶ultima express~ao ¶e melhor na demonstra»c~ao de teoremas,
como veremos no Teorema 2.7 adiante.
Se a fam¶³lia F ¶e indexada pelo conjunto ¡, a seguinte nota»c~ao alternativa pode ser
usada: \
°2¡
A° = fx 2 U jx 2 A° para todo ° 2 ¡g
Se o conjunto de ¶³ndices ¡ for ¯nito, ¡ = f1; 2; : : : ; ng para alguminteiro positivo
n, ent~ao como no caso da uni~ao, escrevemos habitualmente
n\
i=1
Ai ou A1 \ A2 \ ¢ ¢ ¢An
em vez de
T
°2¡A°.
Sejam a e b dois n¶umeros reais quaisquer. Por intervalo aberto ]a; b[ entendemos
o subconjunto fx 2 R j a < x < bg de R. Segue que se a ¸ b ent~ao ]a; b[ = ¿.
Exemplo 2.9 Encontre a interse»c~ao da fam¶³lia de intervalos abertos
]0; 1[ ; ]0; 1
2
[ ; ]0; 1
3
[ ; : : :
Solu»c~ao. Devemos encontrar o conjunto
T
n2N ]0;
1
n
[. Falando intuitivamente, a fam¶³lia
dada ¶e uma seqÄue^ncia de intervalos \decrescentes" ]0; 1=n[ , em que o intervalo ]0; 1=n[
se \aproxima" do conjunto vazio ¿ quando n torna-se grande. Portanto, podemos
conjeturar que a interse»c~ao
T
n2N ]0; 1=n[ deve ser o conjunto vazio. Demonstraremos
que nossa conjetura ¶e verdadeira. Suponha em contr¶ario, que existe algum n¶umero real
a 2 Tn2N ]0; 1=n[. Ent~ao ter¶³amos 0 < a < 1=n para todo n 2 N. Isto contradiz o fato
de que para um n¶umero real ¯xado a > 0, sempre existe um n 2 N, su¯cientemente
grande, tal que 1=n < a. A contradi»c~ao mostra que
T
n2N ]0; 1=n[ = ¿.
Teorema 2.7 Seja fA° j ° 2 ¡g uma fam¶³lia vazia de conjuntos; isto ¶e, ¡ = ¿. Ent~ao
(a)
S
°2¿A° = ¿.
(b)
T
°2¿A° = U .
Demonstra»c~ao. (a) Para mostrar
S
°2¿A° = ¿, mostramos equivalentemente que x62S
°2¿A° para todo x (em U):
x62 S
°2¿
A° ´»
0
@x 2 S
°2¿
A°
1
A Nota»c~ao
´» (x 2 A° para algum ° 2 ¿) Def. 2.6
´ (x62 A° para todo ° 2 ¿) N.Q. (Cap. 1)
´ (° 2 ¿! x62 A°)
O Conceito de Conjunto 43
A ¶ultima a¯rma»c~ao ¶e, pelo Teorema 1.7 do Cap¶³tulo 1, verdadeira para todo x 2 U ,
pois ° 2 ¿ ¶e uma contradi»c~ao. Isto completa a demonstra»c~ao da parte (a).
(b) Demonstraremos que x 2 T
°2¿A° , para todo x em U . Observe que
x 2 T
°2¿
A° ´ (x 2 A° ; 8° 2 ¿) Def. 2.7
´ (° 2 ¿! x 2 A°)
A ¶ultima asser»c~ao ¶e, como explicamos na demonstra»c~ao da parte (a), uma a¯r-
ma»c~ao verdadeira para todo x 2 U . A demonstra»c~ao est¶a terminada.
Muitos teoremas, a respeito de opera»c~oes de um n¶umero ¯nito de conjuntos, podem
ser generalizados a teoremas a respeito de opera»c~oes de uma fam¶³lia arbitr¶aria de con-
juntos. Por exemplo, o seguinte teorema generaliza o Teorema de De Morgan. Compare
este teorema com o Teorema 2.6.
Teorema 2.8 (Teorema de De Morgan Generalizado) Seja fA° j ° 2 ¡g uma
fam¶³lia arbitr¶aria de conjuntos. Ent~ao
(a)
³S
°2¡A°
´0
=
T
°2¡A
0
°.
(b)
³T
°2¡A°
´
0
=
S
°2¡A
0
° .
Demonstra»c~ao. Demonstraremos apenas a parte (a), e deixaremos a parte (b) ao estu-
dante.
x 2
ÃS
°2¡
A°
!
0
´»
Ã
x 2 S
°2¡
A°
!
Def. de 0
´» (9° 2 ¡)(x 2 A°) Def. 2.6
´ (8° 2 ¡)(x62 A°) N.Q. (Cap. 1)
´ (8° 2 ¡)(x 2 A0°) Def. de 0
´ x 2 T°2¡A0° Def. 2.7
Portanto, pela De¯ni»c~ao 2.1,
³S
°2¡A°
´0
=
T
°2¡A
0
° .
O seguinte teorema ¶e uma generaliza»c~ao do Teorema 2.4(e).
Teorema 2.9 (Leis Distributivas Generalizadas) Seja A um conjunto e seja F =
fB° j ° 2 ¡g uma fam¶³lia arbitr¶aria de conjuntos. Ent~ao
(a) A \
³S
°2¡B°
´
=
S
°2¡(A \B°):
(b) A [
³T
°2¡B°
´
=
T
°2¡(A [B°):
44 O Conceito de Conjunto
Demonstra»c~ao. Um elemento x est¶a no conjunto A\
³S
°2¡B°
´
se e somente se x 2 A
e x 2 S°2¡B° , o que, de acordo com a De¯ni»c~ao 2.6, ¶e equivalente a
x 2 A e x 2 B° para algum ° 2 ¡
Esta ¶ultima asser»c~ao pode ser expressa, pela De¯ni»c~ao 2.4, como
x 2 A \B° para algum ° 2 ¡
o que, pela De¯ni»c~ao 2.6, ¶e precisamente x 2 S°2¡(A\B°). Assim, pela De¯ni»c~ao 2.1,
A \
³S
°2¡B°
´
=
S
°2¡(A \B°).
A demonstra»c~ao da parte (b) ¶e um exerc¶³cio.
2.6.1 Exerc¶³cios
1. Sejam ¡ = f1; 2; 3; 4g, e A1 = fa; b; c; dg, A2 = fb; c; dg, A3 = fa; b; cg, A4 =
fa; bg. Encontre o seguinte.
(a)
S4
i=1Ai.
(b)
T4
i=1Ai.
2. Para dois n¶umeros reais quaisquer a e b, por intervalo fechado [a; b] entendemos o
conjunto fx 2 R j a · x · bg. Se a > b, [a; b] = ¿. Encontre os seguintes conjuntos.
(a)
T
n2N[0; 1=n]
(b)
S
n2N[0; 1=n]
(c)
T99
n=1[0; 1=n]
3. Demonstre o Teorema 2.8(b):
³T
°2¡A°
´
0
=
S
°2¡A
0
°.
4. Demonstre o Teorema 2.9(b): A [
³T
°2¡B°
´
=
T
°2¡(A [B°).
5. Expanda
(a) (A1 [A2) \ (B1 [B2 [B3) em uma uni~ao de interse»c~oes, e
(b) (A1 \ A2) [ (B1 \ B2 \ B3) em uma interse»c~ao de uni~oes. [Sugest~ao: Use o
Teorema 2.9 v¶arias vezes.]
6. Expanda
(a) (
Sm
i=1Ai) \ (
Sn
j=1Bj) em uma uni~ao de interse»c~oes, e
(b) (
Tm
i=1Ai) [ (
Tn
j=1Bj) em uma interse»c~ao de uni~oes. [Veja Problema 5.]
7. Sejam fA° j ° 2 ¡g e fB± j ± 2 ¢g duas fam¶³lias de conjuntos. Expanda
(a) (
S
°2¡A°) \ (
S
±2¢B±) em uma uni~ao de interse»c~oes, e
(b) (
T
°2¡A°) [ (
T
±2¢B±) em uma interse»c~ao de uni~oes. [Veja Problemas 5 e 6.]
2.7 O paradoxo de Russel
Neste momento muitos de n¶os achamos que entendemos o signi¯cado de conjunto|pelo
menos intuitivamente. A maioria de n¶os, fazendo um curso de teoria dos conjuntos pela
O Conceito de Conjunto 45
primeira vez, n~ao perceberia o que h¶a de errado em considerar \o conjunto de todos os
conjuntos" ou o assim chamado \conjunto universal" no sentido absoluto. Na verdade,
por um per¶³odo de tempo (pelo menos de 1895, quando Georg Cantor pioneiramente
criou uma teoria dos conjuntos, at¶e 1902, quando o Paradoxo de Russel apareceu),
a existe^ncia de um tal conjunto universal era considerada como certa. Foi o famoso
¯l¶osofo ingle^s Bertrand Russel (1872{1970)5 que chocou a comunidade matem¶atica em
1902, declarando que a admiss~ao de um conjunto de todos os conjuntos levaria a uma
contradi»c~ao. Este ¶e o famoso Paradoxo de Russel. Apresentaremos este paradoxo na
forma de dois lemas aparentemente contradit¶orios, dos quais um teorema ¶e conseqÄue^ncia.
Lema 2.1 Suponhamos que existe um conjunto U de todos os conjuntos. Seja R =
fS 2 U jS62 Sg.6 Ent~ao R62 R.
Demonstra»c~ao. Suponhamos, ao contr¶ario, que R 2 R. Ent~ao, pela especi¯ca»c~ao
do conjunto R, devemos ter R 62 R, o que contradiz a hip¶otese de que R 2 R. A
contradi»c~ao prova que R62 R.
Lema 2.2 Suponhamos que existe um conjunto U de todos os conjuntos. Seja R o
conjunto fS 2 U jS62 Sg. Ent~ao R 2 R.
Demonstra»c~ao. Suponha o contr¶ario, que R62 R. Ent~ao, como R 2 U , temos R 2 R
pela de¯ni»c~ao de R. Isto ¶e uma contradi»c~ao. Assim, R 2 R.
Teorema 2.10 N~ao existe um conjunto de todos os conjuntos.
Demonstra»c~ao. Em vista dos Lemas 2.1 e 2.2, o conjunto de todos os conjuntos n~ao
pode existir. Pois, se existisse, levaria µa contradi»c~ao \R62 R e R 2 R".
Paul R. Halmos coloca-o do seguinte modo: \Nada cont¶em tudo."7
5Bertrand Russel nasceu em 18 de maio de 1872, em Trelleck, Wales, Inglaterra. Antes que comple-
tasse quatro anos, seus pais faleceram. Foi sempre um garoto quieto e t¶³mido, at¶e ingressar no Trinity
College, na Universidade de Cambridge, em 1890. Ap¶os tre^s anos de Matem¶atica, concluiu que o que
lhe estava sendo ensinado estava cheio de erros. Vendeu seus livros de matem¶atica e mudou-se para
a ¯loso¯a. No seu Principia Mathematica (1910{1913), um trabalho monumental em tre^s volumes,
em co-autoria com Alfred North Whitehead (1861{1947), tentou remodelar a teoria dos conjuntos, de
modo a evitar paradoxos. Em 1918 escreveu \Quero posicionar-me µa borda do mundo e perscrutar a
escurid~ao al¶em, e ver um pouco mais do que outros viram. : : : Quero trazer de volta ao mundo dos
homens um pouquinho de sabedoria". Ele seguramente o fez, mais do que \um pouquinho". No mesmo
ano, foi preso por um coment¶ario desfavor¶avel sobre o ex¶ercito americano. Em 1950 recebeu a Ordem
do M¶erito do rei da Inglaterra e o Pre^mio Nobel de Literatura. Em seus ¶ultimos anos, liderou v¶arias
manifesta»c~oes contra os armamentos nucleares.
6Conforme a regra da especi¯ca»c~ao, R ¶e um conjunto freqÄuentemente chamado